What are some well known scheduling algorithms?

For all the examples,

Process 1: Runtime 1000ms

Process 2: Runtime 2000ms

Process 3: Runtime 3000ms

Process 4: Runtime 4000ms

Process 5: Runtime 5000ms

Shortest Job First (SJF)

• P1 Arrival: 0ms
• P2 Arrival: 0ms
• P3 Arrival: 0ms
• P4 Arrival: 0ms
• P5 Arrival: 0ms

The processes all arrive at the start and the scheduler schedules the job with the shortest total CPU time. The glaring problem is that this scheduler needs to know how long this program will run over time before it ran the program.

Technical Note: A realistic SJF implementation would not use the total execution time of the process but the burst time (the total CPU time including future computational execution before the process will no longer be ready to run). The expected burst time can be estimated by using an exponentially decaying weighted rolling average based on the previous burst time but for this exposition we will simplify this discussion to use the total running time of the process as a proxy for the burst time.

Advantages

• Shorter jobs tend to get run first

Disadvantages

• Needs algorithm to be omniscient

Preemptive Shortest Job First (PSJF)

Preemptive shortest job first is like shortest job first but if a new job comes in with a shorter runtime than the total runtime of the current job, it is run instead. (If it is equal like our example our algorithm can choose). The scheduler uses the total runtime of the process. If you want the shortest remaining time left, that is a variant of PSJF called Shortest Remaining Time First (SRTF).

• P2 at 0ms
• P1 at 1000ms
• P5 at 3000ms
• P4 at 4000ms
• P3 at 5000ms

Here's what our algorithm does. It runs P2 because it is the only thing to run. Then P1 comes in at 1000ms, P2 runs for 2000ms, so our scheduler preemptively stops P2, and let's P1 run all the way through (this is completely up to the algorithm because the times are equal). Then, P5 Comes in -- since there are no processes running, the scheduler will run process 5. P4 comes in, and since the runtimes are equal P5, the scheduler stops P5 and runs P4. Finally P3 comes in, preempts P4, and runs to completion. Then P4 runs, then P5 runs.

Advantages

• Ensures shorter jobs get run first

Disadvantages

• Need to know the runtime again

First Come First Served (FCFS)

• P2 at 0ms
• P1 at 1000ms
• P5 at 3000ms
• P4 at 4000ms
• P3 at 5000ms

Processes are scheduled in the order of arrival. One advantage of FCFS is that scheduling algorithm is simple: the ready queue is a just a FIFO (first in first out) queue. FCFS suffers from the Convoy effect.

Here P2 Arrives, then P1 arrives, then P5, then P4, then P3. You can see the convoy effect for P5.

Advantages

• Simple implementation

Disadvantages

• Long running processes could block all other processes

Round Robin (RR)

Processes are scheduled in order of their arrival in the ready queue. However after a small time step a running process will be forcibly removed from the running state and placed back on the ready queue. This ensures that a long-running process can not starve all other processes from running. The maximum amount of time that a process can execute before being returned to the ready queue is called the time quanta. In the limit of large time quanta (where the time quanta is longer than the running time of all processes) round robin will be equivalent to FCFS.

• P1 Arrival: 0ms
• P2 Arrival: 0ms
• P3 Arrival: 0ms
• P4 Arrival: 0ms
• P5 Arrival: 0ms

Quantum = 1000ms

Here all processes arrive at the same time. P1 is run for 1 quantum and is finished. P2 for one quantum; then, it is stopped for P3. After all other processes run for a quantum we cycle back to P2 until all the processes are finished.

Advantages

• Ensures some notion of fairness

Disadvantages

• Large number of processes = Lots of switching

Priority

Processes are scheduled in the order of priority value. For example, a navigation process might be more important to execute than a logging process.