CPU Scheduling

There are usually more ready tasks than CPU cores, so something has to decide who runs next and for how long. That's the CPU scheduler. Knowing the classic algorithms helps you reason about latency, fairness and starvation in operating systems and in your own job queues.

For example, six processes P1 to P6 sit in the ready queue, but there are only two cores. Only two can run at a time: who goes first, in what order, and for how long?

What a scheduler balances#

A scheduler juggles several goals at once.

These goals conflict. Maximizing throughput can starve small tasks; strict fairness can lower throughput. Every algorithm picks a trade-off.

Preemptive vs non-preemptive#

Schedulers split first on whether they ever take the CPU away from a running task.

• Non-preemptive: once a task starts, it keeps the CPU until it finishes or blocks on I/O.
• Preemptive: the OS can take the CPU away (usually via a timer interrupt) and put the task back in the ready queue.

The OS can always stop a process. "Non-preemptive" describes a scheduling policy where the OS chooses not to interrupt, not a power the process has. Think of two teachers: one lets each student finish their presentation, the other cuts everyone off at five minutes.

Non-preemptive is simpler, more predictable and has less switching overhead, but one task stuck in an infinite loop can hog the CPU forever. That's why Linux, Windows and macOS all schedule preemptively.

One exception: kernel code sometimes disables interrupts for a few instructions (for example, around a spinlock). During that tiny window even the timer can't fire. That's the kernel protecting itself, not a user process controlling its own scheduling.

Algorithm 1: First Come, First Served (FCFS)#

Run tasks in arrival order, like a grocery line with no cutting. The examples below use these three processes:

FCFS runs them in this order:

P2 waits 9 ms for a 4 ms job; P3 waits 12 ms for a 2 ms job. This is the convoy effect: one long task holds up everyone behind it, like being stuck behind a full cart when you have two items.

Algorithm 2: Shortest Job First (SJF)#

Run the task with the shortest burst first. With the same three processes:

Average wait (ignoring arrival offsets):

SJF is provably optimal for minimizing average waiting time, but it has two problems:

1. You don't know burst times in advance. Real systems can only estimate from past behavior or hints, so pure SJF is mostly theoretical.
2. Starvation. If short jobs keep arriving, a 50 ms job can be pushed back forever.

Algorithm 3: Round Robin (RR)#

Each task gets a fixed time slice (quantum). When it expires, the task goes to the back of the queue. Round robin is the basis of interactive, general-purpose scheduling.

With P1 = 10 ms, P2 = 4 ms, P3 = 2 ms and a quantum of 3 ms:

(The last P1 segment is 4 ms, longer than the quantum: P1 is the only task left, so it gets a 3 ms slice and then a 1 ms slice back to back.)

Choosing the quantum#

The quantum has to be large compared with the cost of a switch, but small enough that nobody waits long.

The overhead is the switch cost divided by the quantum:

• 20 µs / 100 ms = 0.02%, which is negligible.
• 20 µs / 1 ms = 2%, which is noticeable waste.

Algorithm 4: Priority scheduling#

Each task has a priority; the highest-priority ready task runs first. Here a lower number means a higher priority:

Where priorities come from:

• Static: set at creation, never changes (system tasks high, user tasks lower).
• Dynamic: the OS adjusts based on behavior. I/O-heavy tasks get boosted because they give up the CPU voluntarily; CPU hogs get lowered.

Preemptive vs not: if P1 (priority 3) is running and P2 (priority 1) arrives, a non-preemptive scheduler lets P1 finish; a preemptive one moves P1 back to Ready and runs P2 now. Modern systems use the preemptive form.

Starvation and aging#

If high-priority tasks keep arriving, a low-priority task may wait for hours. The fix is priority aging: raise a task's priority the longer it waits.

Eventually every waiting task reaches top priority, so none starves.

Combining them: Multi-Level Feedback Queue (MLFQ)#

Real schedulers mix these ideas. The textbook design is the multi-level feedback queue: several round-robin queues at different priorities with different quanta.

Going down the queues, priority decreases and the quantum increases.

Rules: a task moves between queues based on how it uses the CPU.

• A new task starts in Queue 0 (benefit of the doubt).
• Uses its full quantum without blocking → demoted one level.
• Blocks on I/O before the quantum ends → stays or is promoted.
• Waits too long in a low queue → aged upward, so nothing starves.

For example, follow one new task:

1. It starts in Queue 0.
2. It uses its full 5 ms, so it drops to Queue 1.
3. It uses its full 10 ms, so it drops to Queue 2.
4. It blocks on I/O after 3 ms, so it moves back up to Queue 1.

Over time, CPU hogs sink toward Queue 3, while aging promotes long-waiting tasks back up toward Queue 0.

Why the quantum grows as priority drops: interactive tasks need only short bursts (they block on input before the quantum ends), so small quanta keep response time low. CPU-heavy tasks need long stretches; tiny quanta would just switch them constantly for no benefit. "You get the CPU less often, but for longer when you do."

The result: editors and browsers stay responsive in the top queue, compilation and ML training get long slices lower down, and aging guarantees progress, all without anyone setting priorities by hand.

In practice, the same ideas show up beyond the OS: hypervisors share physical CPUs across virtual machines, and multi-tenant cloud platforms use priorities and quotas so one customer's workload can't starve another's.

All algorithms compared#

Here are the five algorithms side by side.

Key takeaways#

• The scheduler trades off throughput, fairness, waiting time and response time; no algorithm wins on all.
• FCFS suffers the convoy effect; SJF minimizes average wait but needs burst times you rarely know and can starve long jobs.
• Round robin is fair and responsive if the quantum is much larger than the context-switch cost.
• Priority scheduling needs aging to prevent starvation.
• MLFQ demotes CPU hogs, keeps I/O-bound tasks responsive, and ages waiters so nothing starves.