CPU Scheduling
The policy that picks the next ready thread. Fairness, latency, and throughput trade off.
Level: intermediate
What is it?
Whenever the CPU is about to sit idle or a scheduling event fires (quantum, wake, fork, yield), the scheduler chooses a ready thread. Preemptive schedulers can steal the CPU from a running thread; cooperative ones wait to be given it back.
Why does it matter?
Interactive latency, batch throughput, and fairness are different objective functions. Linux CFS, real-time FIFO/RR, and a toy FCFS exam question are all answers to different questions.
Mental model
A receptionist with a rule for who goes next. FCFS is a queue. RR is a queue with a kitchen timer. SJF is 'shortest appointment first' — optimal average wait if you can see the future.
How it works
- Metrics: waiting time, turnaround, response time, CPU utilization, throughput.
- FCFS: simple, convoy effect.
- SJF / SRTF: best average wait; starvation of long jobs; need a burst predictor.
- Round robin: quantum too small → context-switch thrash; too large → FCFS.
- Priority: aging to avoid starvation. Multilevel feedback queues combine several of the above.
Real-world usage
- OS kernels
- Thread pools and executors
- Distributed job queues (a cousin, not the same)
Common mistakes
- Optimizing the average and ignoring the tail. Humans feel p99.
- A 1ms quantum on a machine whose context switch is 0.3ms — you are measuring the scheduler, not the work.
Interview questions
Why can SJF starve?
A stream of short jobs keeps skipping a long one. Aging or a guaranteed slice fixes it.
Effect of a very small RR quantum?
Response time looks snappy until context-switch overhead eats the CPU.