CPU Scheduling: Criteria, FCFS, SJF, SRTF and Priority

When several processes are ready and there is one CPU, the short-term scheduler decides which runs next. The decision is made over and over, every few milliseconds, so the policy shapes how long jobs take, how responsive the system feels and whether some process can be postponed forever.

Processes alternate between CPU bursts and I/O bursts. Scheduling is about CPU bursts: each scheduling algorithm takes the set of ready processes, each with an arrival time and a burst length, and builds a Gantt chart, a timeline showing who runs when. The chart gives completion, turnaround, waiting and response times.

The scheduling criteria and the preemption rule are used with the algorithms that choose by arrival order, by burst length and by priority: FCFS, SJF, SRTF, HRRN and priority scheduling, with the tie-breaking rules that make the schedule unique. Round robin and multilevel queues follow in Round Robin and Multilevel Queue Scheduling.

For a process with arrival time $A$, burst time $B$, first time on the CPU $S$ and completion time $C$:

Waiting time is time in the ready queue only. For a process that also does I/O, waiting time excludes the I/O; in these CPU-burst exercises every process has one burst, so $\text{WT} = \text{TAT} - B$ holds exactly. For a non-preemptive algorithm, response time equals waiting time, because a process never waits again once started.

Optimization goals. Maximize utilization and throughput; minimize turnaround, waiting and response time. No algorithm is best on all of them at once.

Scheduling decisions happen when a process (1) switches from running to waiting, (2) switches from running to ready (for example, after a timer interrupt), (3) switches from waiting to ready, or (4) terminates. Non-preemptive scheduling decides only at (1) and (4): a running process keeps the CPU until it blocks or finishes. Preemptive scheduling also decides at (2) and (3): an arrival can take the CPU away from the running process.

The dispatcher performs the switch; its delay is the dispatch latency (the context-switch cost).

Tie convention used in the traces. (a) When two ready processes are equal on the algorithm's key, the one that arrived earlier goes first; if they also arrived together, the lower process number goes first. (b) In a preemptive algorithm, a newly arrived process preempts the running one only if it is strictly better; on a tie the running process keeps the CPU. (c) Priority numbers: a smaller number means higher priority. (d) Unless a question gives a context-switch cost, switching is free. A stated problem may give different rules; when it does, those rules win.

Run processes in arrival order; non-preemptive. A FIFO queue implements it.

When the CPU is free, pick the ready process with the shortest burst.

At every arrival, compare the new process's burst with the remaining time of the running process; switch if the new one is strictly shorter.

Each process has a priority; the highest priority runs. Non-preemptive priority waits for the CPU to be free; preemptive priority lets a higher-priority arrival preempt. SJF is priority scheduling with priority = predicted burst.

Non-preemptive. When the CPU is free, compute for each ready process

where $W$ is the time it has waited so far, and run the one with the largest $R$. All jobs start at ratio 1. For equal positive waiting time, shorter jobs have a higher ratio and their ratio grows faster per unit waiting. This balances short-job preference with aging; starvation claims require assumptions about the workload, such as a finite set of finite jobs.

Take jobs all available at time 0, run in some order with bursts $b_1, b_2, \dots, b_n$. Job $k$ waits $b_1 + \dots + b_{k-1}$, so the total waiting time is

The burst in position $k$ is counted $n - k$ times, so to minimize the sum the largest coefficients must multiply the smallest bursts: sort in increasing order. If two adjacent jobs are out of order ($b_k > b_{k+1}$), swapping them changes the total by $b_{k+1} - b_k < 0$. This exchange argument proves optimality for simultaneous arrivals; with staggered arrivals the preemptive SRTF is the optimal one.

With $t_n$ the measured length of the $n$-th burst and $\tau_n$ its prediction,

$\alpha = 0$ ignores the measured bursts (the prediction stays $\tau_0$); $\alpha = 1$ uses only the last burst. Unrolling, the weight of $t_{n-j}$ is $\alpha (1 - \alpha)^{j}$: older bursts count geometrically less. Example with $\alpha = 0.5$, $\tau_0 = 10$ and bursts 6, 4, 6: $\tau_1 = 8$, $\tau_2 = 6$, $\tau_3 = 6$.

Gantt: P1 0 to 7, P2 7 to 11, P3 11 to 12, P4 12 to 16.

Average WT $= 19/4 = 4.75$; average TAT $= 35/4 = 8.75$.

At 7, P1 finishes and P2 (4), P3 (1) and P4 (4) are ready: P3 runs. At 8, P2 and P4 tie at 4; P2 arrived first. Gantt: P1 0 to 7, P3 7 to 8, P2 8 to 12, P4 12 to 16. WT: P1 0, P2 6, P3 3, P4 7; average 4. Average TAT 8.

Gantt: P1 0 to 2, P2 2 to 4, P3 4 to 5, P2 5 to 7, P4 7 to 11, P1 11 to 16.

Average WT $= 3$, average TAT $= 7$, average RT $= 0.5$. SRTF beats SJF (4) on average waiting time, as it must.

Non-preemptive: P1 runs 0 to 7. At 7 the ready set is P2 (priority 1), P3 (4) and P4 (2): P2 runs 7 to 11, then P4 11 to 15, then P3 15 to 16. WT: P1 0, P2 5, P3 11, P4 6; average 5.5.

Preemptive: at 2, P2 (priority 1) preempts P1 (3) and runs to 6. At 6 the best is P4 (2), which runs 6 to 10. Then P1 (3) runs 10 to 15 and P3 (4) runs last, 15 to 16. WT: P1 8, P2 0, P3 11, P4 1; average 5. P3 has the worst waiting time in both: low priority means it waits behind everyone.

Jobs A (arrival 0, burst 10), B (1, 4) and C (9, 1). A runs 0 to 10. At 10, B has waited 9: $R_B = (9 + 4)/4 = 3.25$; C has waited 1: $R_C = (1 + 1)/1 = 2$. HRRN runs B (10 to 14) then C (14 to 15). SJF would run C first (10 to 11) and then B (11 to 15). SJF has the lower average waiting time ($11/3$ against $14/3$), but HRRN rewards B for having waited.

P1 (arrival 0, burst 4) and P2 (arrival 1, burst 3). At time 1, P1 has 3 units left and P2 needs 3: a tie. Under the convention above the running P1 continues: P1 0 to 4, P2 4 to 7. Under the opposite rule (an arrival wins ties) the chart is P1 0 to 1, P2 1 to 4, P1 4 to 7. The average waiting time is 1.5 either way, but the completion times differ, so a question asking for one process's completion time depends on the rule.

Run FCFS on the four-process workload with a switch cost of 1 unit between consecutive processes (none at time 0). Gantt: P1 0 to 7, switch, P2 8 to 12, switch, P3 13 to 14, switch, P4 15 to 19. Three switches; the last process finishes at 19 instead of 16, and CPU utilization is $16/19 \approx 84.2\%$. WT becomes P1 0, P2 6, P3 9, P4 10.

SJF (non-preemptive) on P1 (arrival 0, burst 3), P2 (5, 4), P3 (5, 2), P4 (7, 1).

Average TAT $= 13/4 = 3.25$, average WT $= 3/4 = 0.75$. The idle interval counts in the schedule length but not in anyone's waiting time: CPU utilization is $10/12 \approx 83.3\%$. If P4 were (wrongly) treated as arriving after the decision at 7, P2 would run 7 to 11 and P4 would wait 4 units. SRTF gives the same chart here, because no arrival is shorter than the remaining time of the running process.

Two processes arrive at 0. A has CPU 3, I/O 5, CPU 2; B has CPU 4, I/O 2, CPU 1. FCFS, each process has its own I/O device (I/O runs in parallel with the CPU and with other I/O), and a process returning from I/O joins the back of the ready queue.

A finishes at 10 and B at 11. The CPU is busy $3 + 4 + 2 + 1 = 10$ of 11 units, so utilization is $10/11 \approx 90.9\%$ and the idle time is 1 unit. Waiting time counts only time spent ready but not running: A waits 0, B waits 3 (0 to 3) plus 1 (9 to 10) $= 4$. TAT minus the total burst does not give WT here, because the I/O time must also be subtracted: B's TAT is 11, and $11 - 4 - 2 - 1 = 4$.

Common misconceptions.