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