CPU scheduling

1Turnaround, waiting and response

Maya's laptop has one CPU and three programs that want it. Call them Print (burst 4), Spell (burst 3) and Save (burst 5). Burst time is how long a job needs the CPU in total. Arrival time is when it became Ready. Completion time is when it finished. Those three clocks give three scores.

Turnaround time is completion minus arrival — how long the job lived in the system. Waiting time is turnaround minus burst — how long it sat in Ready. Response time is the first moment on the CPU minus arrival — how long until it first ran. Waiting and response are not the same: a job can run, be preempted, and wait again.

One walk already on this card: a job arrives at 2, first runs at 5, completes at 12, burst 7. TAT = 12 − 2 = 10. WT = 10 − 7 = 3. Response = 5 − 2 = 3.

Figure. The wide bar is lifetime in the system (AT to CT). Response is only the left stub until first dispatch; waiting is TAT minus the burst, not that stub alone.

How it works

1. Read completionOff the Gantt chart's right edge for that process — that is CT.
2. TurnaroundTAT = CT − AT. This is always non-negative and at least the burst.
3. Waiting and responseWT = TAT − BT. Response = first-on-CPU − AT. Average WT is the sum of waiting times over the number of processes.

2FCFS and the convoy

First-Come-First-Served runs Ready jobs in arrival order and does not steal the CPU for another Ready job. Print, Spell and Save all arrive at time 0 in that order, bursts 4, 3, 5. FCFS runs Print 0→4, Spell 4→7, Save 7→12.

Waiting times: Print 0, Spell 4, Save 4+3 = 7. Average 11/3 ≈ 3.67. The convoy effect is the same picture with a long job at the head: everyone behind sits idle. FCFS is simple and unfair to short jobs stuck behind a long one.

Figure. FCFS Gantt for bursts 4, 3, 5 in arrival order. Block widths are proportional to burst (scale 0.07 per time unit from x = 0.08). Waiting times are the left edges: 0, 4, 7.

How it works

1. Queue by arrivalThe ready queue is a FIFO. The process that arrived earliest runs next.
2. Run to completionNo timer steals the CPU for another ready process; FCFS yields only on finish or block.
3. Read waitingWith equal arrivals, each process waits for the sum of all bursts ahead of it in the order.

Coding lab. FCFS waiting times for Print, Spell, Save runs in the app, with checks on your output.

3SJF picks the shortest burst

Shortest-Job-First always picks the Ready job with the smallest burst. Among non-preemptive policies it minimises average waiting time. Same three jobs, all arrived at 0: Spell (3), then Print (4), then Save (5).

Waiting: Spell 0, Print 3, Save 3+4 = 7. Average 10/3 ≈ 3.33, below FCFS's 3.67. The cost: bursts must be known or guessed, and a stream of short jobs can starve Save forever.

Figure. SJF Gantt for the same three bursts: shortest first. Widths still use 0.07 per time unit. Waiting times 0, 3, 7 — total 10 versus FCFS's 11.

How it works

1. Sort by burstWhen the CPU is free, choose the ready process with the shortest declared burst.
2. Run non-preemptivelyThat process keeps the CPU until it finishes or blocks; newcomers wait their turn by burst length, not arrival.
3. Trade-offAverage WT drops versus FCFS on the same set, but long jobs can wait indefinitely if short jobs keep arriving.

4SRTF re-evaluates on every arrival

Shortest-Remaining-Time-First is preemptive SJF. Whenever a new job arrives, compare its burst to the running job's remaining time and switch if the newcomer is shorter. Re-check at every arrival, not only when a job ends.

A later morning on the same laptop: Print arrives at 0 with burst 7; Spell arrives at 2 with burst 4. Print runs 0→2 (5 left). Spell's 4 is shorter than 5, so Print is preempted. Spell runs 2→6. Print finishes 6→11. Waiting: Print 11−7 = 4, Spell 0. Average 2.

Figure. SRTF Gantt: P1 runs until t = 2, yields to shorter P2 (burst 4 vs remaining 5), then finishes after P2. Segment widths use 0.84/11 per time unit from x = 0.08. Not to be read as FCFS — P1 appears twice.

How it works

1. Run shortest remainingAmong ready processes, the CPU holds the one with the least time left.
2. Arrival interruptOn each new arrival, compare the new burst to the current remaining time; preempt if the newcomer wins.
3. Resume laterThe preempted process returns to Ready with its reduced remaining time and competes again.

5Round Robin and the quantum

Round Robin gives every Ready job a fixed time quantum in a circle. Fair, and the usual choice when a human is waiting on a response. Too small a quantum explodes context-switch overhead. If the quantum is at least the longest burst, nobody is ever cut and Round Robin is FCFS.

Print burst 4 and Spell burst 2, both arrive at 0, quantum 2. Slice 1: Print 0→2 (2 left). Slice 2: Spell 2→4 (done). Slice 3: Print 4→6 (done). Print's completion time is 6.

Figure. RR Gantt with quantum 2: equal-width slices (0.28 = 2 × 0.14). P1 appears twice because its leftover returns after P2 finishes.

How it works

1. Dispatch for qThe head of the ready queue runs for at most one quantum.
2. Expire or finishIf it still has remaining time when q expires, it is preempted and rejoins the tail; if it finishes earlier, the next process starts immediately.
3. Tune qSmall q ≈ processor sharing with heavy switching; large q ≈ FCFS.

6Priority and aging

Priority scheduling always runs the Ready job with the best priority. Convention varies — sometimes a smaller number wins. Static priorities starve: if Print keeps arriving with a better priority, Save never runs.

Aging fixes starvation by gradually raising the priority of a job that has waited a long time, so a neglected Save eventually outranks the next Print. Aging is not a different scheduler; it is a rule added to priority.

Figure. Static priority can starve low jobs; aging bumps waiters so they eventually run.

How it works

1. Pick by priorityAmong ready processes, dispatch the highest-priority one (preemptive variants re-check on every arrival).
2. Starvation riskA steady stream of high-priority arrivals can leave a low-priority process ready forever.
3. Age the waitersPeriodically bump waiting processes' priorities so the oldest waiter eventually runs.

7Preemptive versus non-preemptive

Preemptive scheduling may seize a still-runnable job because a better candidate appeared. SRTF, Round Robin and preemptive priority all do this. Non-preemptive scheduling lets the running job keep the CPU until it finishes or blocks. FCFS and classic SJF are non-preemptive.

A block for I/O is not that cut. maya going Running → Waiting because she read the disk is voluntary. Preemption is the timer or a newly arrived shorter job taking a process that could still have run.

Figure. Preemption lets the scheduler reclaim the CPU on a tick or higher-priority arrival; non-preemptive waits for yield.

How it works

1. Non-preemptiveFCFS and SJF: decide only when the CPU becomes free (finish or block).
2. PreemptiveSRTF, RR, preemptive priority: decide again on arrivals or quantum expiry while a process is still runnable.
3. CostPreemption buys responsiveness and can cut average wait (SRTF); every extra switch is pure overhead.