📘 CPU Scheduling

With more runnable tasks than CPU cores, the scheduler decides who runs next and for how long. This page covers the classic algorithms with worked examples (a favorite of written tests and interviews), then how real schedulers like Linux's work. All example numbers were computed with a small simulation script.

Table of Contents

1. Terms and Criteria
2. Preemptive vs Non-Preemptive
3. The Example Workload
4. FCFS
5. SJF and SRTF
6. Round Robin
7. Priority Scheduling
8. Multilevel Queues and MLFQ
9. Comparison
10. Multiprocessor Scheduling
11. How Linux Schedules
12. Questions

1. Terms and Criteria

Goals conflict: batch systems maximize throughput, interactive systems minimize response time, and every system wants fairness and no starvation.

Processes alternate between CPU bursts and I/O bursts. CPU-bound tasks have long bursts (video encoding); I/O-bound tasks have short bursts (editors, web servers). Good schedulers favor I/O-bound tasks briefly so devices stay busy and the system feels responsive.

2. Preemptive vs Non-Preemptive

The dispatcher performs the actual switch; dispatch latency is the time it takes.

3. The Example Workload

All examples below use this set of processes (times in ms).

4. FCFS

First come, first served: run in arrival order, no preemption.

| P1        | P2    | P3           | P4      |
0           8       12             21        26

Simple and fair in order, but suffers the convoy effect: short jobs wait behind one long job, like cars behind a truck.

5. SJF and SRTF

Shortest job first (non-preemptive): when the CPU frees up, pick the ready job with the shortest burst.

At time 0 only P1 is ready, so it runs to completion. At 8, P2 (4) is shortest, then P4 (5), then P3 (9).

| P1        | P2    | P4      | P3           |
0           8       12        17             26

Shortest remaining time first (preemptive SJF): whenever a job arrives, run whichever has the least remaining time.

At 1, P2 arrives with 4 < P1's remaining 7, so P2 preempts P1.

| P1 | P2    | P4      | P1          | P3           |
0    1       5         10            17             26

SRTF gives the minimum average waiting time of any algorithm, provably. Two problems:

1. The OS does not know burst times in advance, so it predicts them with an exponential average of past bursts: next = a * last_actual + (1 - a) * last_prediction.
2. Long jobs can starve if short ones keep arriving.

6. Round Robin

Each process gets a time quantum; when it expires, the process goes to the back of the ready queue. Convention: processes that arrive during a quantum join the queue before the preempted process.

With quantum 4:

| P1    | P2    | P3    | P4    | P1    | P3    | P4 | P3 |
0       4       8       12      16      20      24   25   26

Round robin has worse average waiting time here but much better response time: every process starts within 12 ms, and no one starves.

Choosing the quantum:

7. Priority Scheduling

Each process has a priority; the highest runs first (preemptive or not). SJF is priority scheduling where priority is the inverse of burst length.

Priority inversion famously reset the Mars Pathfinder lander repeatedly in 1997, and was fixed remotely by enabling priority inheritance on a mutex in VxWorks.

8. Multilevel Queues and MLFQ

Multilevel queue: separate ready queues by class (system, interactive, batch), each with its own algorithm, and a rule between queues (strict priority or time slices).

Multilevel feedback queue (MLFQ) lets processes move between queues based on behavior, so the scheduler learns which tasks are interactive without being told.

MLFQ rules:

1. Higher queue always runs first; round robin within a queue.
2. New tasks start at the top.
3. Using up the time allotment at a level moves the task down (count total time at a level, not per burst, so tasks cannot game it by yielding just before the quantum ends).
4. Periodically boost everyone to the top, so CPU-bound tasks do not starve and tasks that became interactive recover.

Windows and classic Unix schedulers were MLFQ variants.

9. Comparison

10. Multiprocessor Scheduling

11. How Linux Schedules

Linux has scheduling classes, checked in priority order:

CFS and EEVDF

From 2007 to 2023, the fair class used CFS (Completely Fair Scheduler):

• Each task has a virtual runtime (vruntime): actual CPU time, scaled by weight.
• Pick the task with the smallest vruntime, kept in a red-black tree (O(log n) insert, O(1) pick of the leftmost).
• No fixed quantum: time slices come from a target latency divided among runnable tasks.
• A task that sleeps (I/O-bound) falls behind in vruntime and runs soon after waking, which makes it feel responsive.

Since Linux 6.6 (2023), the fair class uses EEVDF (Earliest Eligible Virtual Deadline First). It keeps the fairness idea but gives each task a virtual deadline, so latency-sensitive tasks can request shorter slices and get scheduled sooner, with fewer heuristics than CFS.

Nice values and weights

• nice ranges from -20 (highest priority) to 19 (lowest); default 0.
• Each step is about a 10 percent change in CPU share (weight ratio about 1.25).
• nice -n 10 ./backup.sh, renice -n 5 -p 1234; only root can lower the nice value.

Containers and CPU limits

cgroups control CPU for groups of tasks:

The quota is enforced per 100 ms period, so a multi-threaded app with a 1-core limit can burn its quota in 25 ms on 4 threads and then be throttled for 75 ms. This causes mysterious latency spikes; many teams set CPU requests but no CPU limits for latency-sensitive services, and watch nr_throttled in cpu.stat. Runtimes must also respect container limits when sizing thread pools (the JVM and Go runtime detect cgroup limits; Go 1.25 made GOMAXPROCS container-aware by default).

12. Questions

Next: Synchronization and Deadlocks.