LONG-TERM (job / admission scheduler) decides which jobs are ADMITTED to the system and become processes. · controls the DEGREE OF MULTIPROGRAMMING · runs rarely (seconds to minutes) · mostly absent from interactive systems — when you run a command it starts immediately · alive and well in batch clusters (Slurm) and in cloud autoscalers MEDIUM-TERM (swapper) SUSPENDS processes by swapping them out to disk and resumes them later. · used under memory pressure · produces the two "suspended" states of the seven-state model · on modern systems this is paging rather than whole-process swapping SHORT-TERM (CPU scheduler / dispatcher) decides which READY process gets the CPU next. · runs very often — every few milliseconds · MUST BE FAST: it is pure overhead · this is what "scheduling algorithm" normally means DISPATCHER is the mechanism that actually performs the switch: save context, switch memory map, restore context, jump to user mode. DISPATCH LATENCY is the time it takes. Scheduler = policy (who runs); dispatcher = mechanism (how). PREEMPTIVE vs NON-PREEMPTIVE — the fundamental split: NON-PREEMPTIVE a process keeps the CPU until it blocks or exits. Simple, no timer needed, but one long job freezes everything. PREEMPTIVE the OS can take the CPU away (timer interrupt or a higher-priority arrival). Needed for time sharing; requires care with shared kernel data.

CPU UTILISATION keep the CPU busy (maximise) THROUGHPUT processes completed per unit time (maximise) TURNAROUND TIME completion − arrival (minimise) WAITING TIME turnaround − burst (minimise) RESPONSE TIME first response − arrival (minimise) FAIRNESS no process starves THE FORMULAS, which every numerical uses: turnaround time (TAT) = completion time − arrival time waiting time (WT) = turnaround time − burst time = TAT − BT response time = first time on CPU − arrival time Waiting time is what the process spent in the READY queue. For a non-preemptive algorithm, response time = waiting time; for a preemptive one they differ, because a process may run, be preempted, and wait again. THE CRITERIA CONFLICT — you cannot maximise all of them: · minimising average waiting time favours short jobs, which starves long ones · guaranteeing fairness costs context switches, which lowers throughput · minimising response time needs a small quantum, which raises switching overhead So "the best algorithm" depends on which criterion the system is for. A batch cluster optimises throughput; a phone optimises response time.

JOB SET used throughout (all times in arbitrary units): process arrival burst P1 0 7 P2 2 4 P3 4 1 P4 5 4 total 16 All five results below were COMPUTED, not estimated. ──────────── 1. FCFS (first-come first-served) ──────────── non-preemptive, run in arrival order | P1 | P2 |P3| P4 | |0 |7 |11|12 |16 TAT: P1=7 P2=9 P3=8 P4=11 avg = 8.75 WT : P1=0 P2=5 P3=7 P4=7 avg = 4.75 context switches: 3 ✔ simplest possible; obviously fair in arrival order ✗ THE CONVOY EFFECT: P3 needs 1 unit and waits 7, because it queued behind a 7-unit job. One long job delays everything behind it. ──────────── 2. SJF (shortest job first) ──────────── non-preemptive, pick the shortest READY job | P1 |P3| P2 | P4 | |0 |7 |8 |12 |16 TAT: P1=7 P2=10 P3=4 P4=11 avg = 8.00 WT : P1=0 P2=6 P3=3 P4=7 avg = 4.00 context switches: 3 ✔ PROVABLY OPTIMAL for average waiting time among non-preemptive algorithms ✗ requires knowing the burst time IN ADVANCE — impossible in general, so it is estimated by exponential averaging: τ(n+1) = α·t(n) + (1−α)·τ(n) ✗ long jobs can starve ──────────── 3. SRTF (shortest remaining time first) ──────── preemptive SJF | P1 | P2 |P3| P2 | P4 | P1 | |0 |2 |4 |5 |7 |11 |16 TAT: P1=16 P2=5 P3=1 P4=6 avg = 7.00 WT : P1=9 P2=1 P3=0 P4=2 avg = 3.00 context switches: 5 ✔ OPTIMAL average waiting time overall — 3.00, the best of all five ✗ more switches (5 vs 3), so more overhead ✗ P1's turnaround exploded from 7 to 16: it was preempted three times. Optimal on AVERAGE, punishing for the long job. ──────────── 4. ROUND ROBIN (quantum = 2) ──────────── preemptive, each process gets q units in turn | P1 | P2 | P1 |P3| P2 | P4 | P1 | P4 |P1| |0 |2 |4 |6 |7 |9 |11 |13 |15|16 TAT: P1=16 P2=7 P3=3 P4=10 avg = 9.00 WT : P1=9 P2=3 P3=2 P4=6 avg = 5.00 context switches: 8 ✔ FAIR — no starvation, every process runs within (n−1)·q ✔ best RESPONSE time, which is why time-sharing uses it ✗ WORST average turnaround here (9.00) and the most switches THE QUANTUM TRADE-OFF: q too large → degenerates into FCFS q too small → switching overhead dominates rule of thumb: 80% of bursts should be shorter than q typical value: 10–100 ms ──────────── 5. PRIORITY (lower number = higher priority) ──── same jobs, with priorities P1=3, P2=1, P3=4, P4=2 NON-PREEMPTIVE: | P1 | P2 | P4 |P3| |0 |7 |11 |15|16 TAT: P1=7 P2=9 P3=12 P4=10 avg = 9.50 WT : P1=0 P2=5 P3=11 P4=6 avg = 5.50 PREEMPTIVE: | P1 | P2 | P4 | P1 |P3| |0 |2 |6 |10 |15|16 TAT: P1=15 P2=4 P3=12 P4=5 avg = 9.00 WT : P1=8 P2=0 P3=11 P4=1 avg = 5.00 ✗ STARVATION: P3 has the lowest priority and waits 11 units for a 1-unit job. With a steady stream of higher-priority arrivals it might never run. ✔ FIX — AGING: increase a waiting process's priority over time, so it eventually becomes the highest. ──────────── SUMMARY TABLE ──────────── algorithm avg TAT avg WT switches starves? FCFS 8.75 4.75 3 no SJF 8.00 4.00 3 long jobs SRTF 7.00 3.00 5 long jobs Round Robin q=2 9.00 5.00 8 no Priority (preempt) 9.00 5.00 4 low priority SRTF wins on waiting time. RR wins on fairness and response time. FCFS wins on simplicity. There is no single winner — which is the point of the comparison.

STARVATION is not hypothetical. Simulate a low-priority job needing 6 units, with a higher-priority 2-unit job arriving every 3 units: timeline: HI[0-2] LOW[2-3] HI[3-5] LOW[5-6] HI[6-8] LOW[8-9] HI[9-11] LOW[11-12] HI[12-14] LOW[14-15] HI[15-17] LOW[17-18] P_low needed 6 units of CPU. It finished at t = 18, so it WAITED 12 units — twice its own burst time, in 1-unit slivers. And this case is generous: the high-priority job arrives only every 3 units and needs 2, so a gap exists. Make the arrival rate slightly higher and the gap vanishes — P_low then never finishes at all. That is starvation. AGING — the standard fix: every T units of waiting, improve the waiting process's priority by one level. With aging, P_low's priority climbs until it outranks the arriving jobs, at which point it runs to completion. The guarantee is that waiting time is BOUNDED, which is exactly what priority scheduling otherwise lacks. Linux implements the same idea differently: CFS tracks each task's VIRTUAL RUNTIME and always runs the task with the smallest one, so a task that has been denied CPU automatically becomes the most urgent. Starvation is structurally impossible rather than patched afterwards. MULTILEVEL QUEUE — several queues with different algorithms: system processes → priority, quantum 8 interactive → RR, quantum 16 batch → FCFS A process is permanently assigned to one queue. MULTILEVEL FEEDBACK QUEUE — processes MOVE between queues: · start in the highest-priority queue with a small quantum · if a process uses its whole quantum, DEMOTE it (it is CPU-bound) · if it blocks before the quantum expires, keep or PROMOTE it (it is I/O-bound and interactive) · periodically promote everything (this is aging) The elegance: it INFERS whether a process is interactive from its behaviour, without being told. That is why it is the most widely used general-purpose design, and it is the ancestor of the Windows and traditional UNIX schedulers.