CPU Scheduling
How the OS shares one CPU across many processes — FCFS, round-robin, priority, and the metrics that judge them.
Why Schedule?
There are always more runnable processes than CPU cores. The scheduler decides who runs next and for how long, aiming to balance conflicting goals: high throughput, low latency/response time, low turnaround, and fairness. A context switch saves the current process and loads the next.
Core Algorithms
| Algorithm | Idea | Watch out for |
|---|---|---|
| FCFS | First come, first served (a queue) | Convoy effect — one long job stalls everyone |
| SJF | Shortest job first | Optimal average wait, but starves long jobs; needs burst prediction |
| Round Robin | Each gets a fixed time quantum, then rotates | Quantum too big → FCFS; too small → switch overhead |
| Priority | Highest priority runs | Starvation — fix with aging |
| MLFQ | Multiple queues, jobs move by behavior | The practical default in real OSes |
The Metrics
| Metric | Definition |
|---|---|
| Arrival time | When the process enters Ready |
| Burst time | CPU time it needs |
| Completion time | When it finishes |
| Turnaround | Completion − Arrival |
| Waiting | Turnaround − Burst |
| Response | First-run time − Arrival |
Interviewers hand you a table of arrival + burst times and ask for average waiting/turnaround under FCFS or Round Robin. Draw the Gantt chart first, then read the numbers off it.
Round Robin — Worked Example
Three processes, all arrive at t=0, quantum = 2:
Processes: P1 burst 5, P2 burst 3, P3 burst 1 | P1 | P2 | P3 | P1 | P2 | P1 | 0 2 4 5 7 8 9 Completion: P1=9, P2=8, P3=5 Turnaround: P1=9, P2=8, P3=5 (arrival 0) Waiting: P1=4, P2=5, P3=4 Avg waiting = (4+5+4)/3 = 4.33
Interview Questions
Preemptive vs non-preemptive?
Preemptive can forcibly pause a running process (via a timer interrupt) to schedule another — needed for responsiveness and fairness. Non-preemptive only switches when the process blocks or exits.
What is the convoy effect?
Under FCFS, one long CPU-bound job at the front makes many short jobs wait behind it, tanking average waiting time.
How do you prevent starvation in priority scheduling?
Aging — gradually raise the priority of processes that have waited a long time, so they eventually run.
Why is choosing the Round-Robin quantum hard?
Too large and it degenerates to FCFS (poor response); too small and context-switch overhead dominates. Typical values are 10–100 ms.