CPU Scheduling
The CPU is a single resource but dozens of processes compete for it. The scheduler picks which ready process runs next. The choice matters enormously — it determines responsiveness, throughput, and fairness.
Scheduling Goals
Different systems optimise for different metrics:
| Metric | Definition | Important for |
|---|---|---|
| CPU utilisation | % time CPU is doing useful work | All systems |
| Throughput | Processes completed per unit time | Batch systems |
| Turnaround time | Time from submit to completion | Batch systems |
| Waiting time | Total time spent in ready queue | Interactive |
| Response time | Time from request to first output | Interactive / real-time |
Non-Preemptive vs Preemptive
- Non-preemptive: once a process gets the CPU, it runs until it blocks or exits. Simple but one process can monopolise the CPU.
- Preemptive: the OS can forcibly remove the CPU from a running process (e.g., on a timer interrupt). Necessary for interactive responsiveness.
First-Come, First-Served (FCFS)
Processes run in arrival order. Non-preemptive.
Example — three processes arrive at time 0:
| Process | Burst Time |
|---|---|
| P1 | 24 ms |
| P2 | 3 ms |
| P3 | 3 ms |
Convoy effect: short processes stuck behind a long one. P2 and P3 could have finished in 6 ms but waited 24 ms.
Shortest Job First (SJF)
Always picks the process with the shortest expected CPU burst. Can be non-preemptive (once started, runs to completion) or preemptive (Shortest Remaining Time First — SRTF).
Same example with SJF (non-preemptive):
SJF is optimal for minimising average waiting time — but requires knowing burst time in advance, which isn't practical. In practice, it's estimated from past behaviour (exponential averaging).
Round Robin (RR)
Each process gets a fixed time quantum (q), then goes back to the end of the ready queue. Preemptive. The de facto algorithm for interactive systems.
Example — q=4 ms, processes P1(24ms), P2(3ms), P3(3ms):
Quantum size trade-off:
- Too small → huge context-switch overhead
- Too large → degenerates toward FCFS
- Typical: 10–100 ms
Priority Scheduling
Each process has a priority; highest priority runs first. Can be preemptive or non-preemptive.
Problem: starvation — low-priority processes may never run if high-priority processes keep arriving.
Solution: aging — gradually increase priority of processes that have waited a long time.
Multilevel Queue
Separate queues for different process classes (e.g., interactive, batch, system). Each queue has its own scheduling algorithm. Processes don't move between queues.
Multilevel Feedback Queue (MLFQ)
The most sophisticated and widely used algorithm. Processes can move between queues based on observed behaviour:
- A new process starts in the highest-priority queue
- If it uses its full quantum repeatedly, it drops to a lower queue (CPU-bound → lower priority)
- If it blocks quickly, it stays or moves up (I/O-bound → high priority)
- Aging prevents starvation
Real-World Schedulers
- Linux CFS (Completely Fair Scheduler): tracks "virtual runtime" per process; always runs the process with the least vruntime. Uses a red-black tree for O(log n) operations.
- Windows: priority-based with dynamic boosts for interactive threads.
Python Simulation
Key Takeaways
- FCFS is simple but causes convoy effect
- SJF minimises average wait time but requires burst time prediction
- Round Robin is fair and responsive; quantum size is the key tuning knob
- Priority scheduling risks starvation — aging is the fix
- Real-world OSes use MLFQ variants: adapt to process behaviour automatically