notes / os / cpu-scheduling.md · 2026-01 · 9 min

# CPU Scheduling

🔗 View on GitHub

A computer usually has more programs ready to run than it has CPU cores. The scheduler is the part of the operating system that decides which process gets the CPU, and for how long.

That one decision shapes almost everything you feel as a user: how fast apps respond, how much work gets done, and whether some programs get stuck waiting forever. The same problem shows up everywhere, from tiny embedded chips to cloud servers running thousands of virtual machines.

## 1. How we measure a scheduler

There is no single "best" scheduler. It depends on what you care about, so first we need ways to measure it.

• CPU utilization: how much of the time the CPU is doing useful work. Higher is better, but not if it makes everything slow to respond.
• Throughput: how many jobs finish per second.
• Turnaround time: total time from arriving to finishing. turnaround = completion − arrival
• Waiting time: time spent sitting in the queue, not running. waiting = turnaround − burst
• Response time: time until a process runs for the first time. This is what makes an app feel fast. response = first run − arrival
• Tail latency: the slowest responses, like the 95th or 99th percentile. Users notice the occasional slow response more than the average.
• Fairness: whether every process gets a reasonable share of the CPU.
• Overhead: time lost to the scheduler itself, mostly from switching between processes.

Burst means how much CPU time a process needs.

## 2. The classic algorithms

### First-Come, First-Served (FCFS)

Processes run in the order they arrive, each one until it finishes. Like a queue at a shop.

• ✅ Very simple, and it switches between processes as rarely as possible.
• ❌ One long job makes everyone behind it wait. This is called the convoy effect.
• Fine for batch jobs, bad for anything interactive.

### Shortest Job First (SJF) and Shortest Remaining Time First (SRTF)

Always run the job that needs the least CPU time. SRTF is the preemptive version: if a shorter job arrives, it takes over right away.

• ✅ Gives the lowest possible average waiting time, if you know how long each job will take.
• ❌ You never really know that in advance. Systems guess from past behavior, usually with an average that weights recent bursts more: next guess = α × last burst + (1 − α) × previous guess
• ❌ Long jobs can wait forever if short ones keep arriving (starvation). The fix is aging: the longer a job waits, the more important it becomes.

### Priority Scheduling

Every process gets a priority, and the highest one runs first.

• ✅ Lets important work go first.
• ❌ Low-priority processes can starve. Fixed with aging, again.
• ❌ Priority inversion: a high-priority process waits for a lock held by a low-priority one, which itself can't run. The fix is priority inheritance: the lock holder temporarily borrows the high priority.

### Round Robin (RR)

Every process gets a small time slice, called a quantum, in turn. When the slice runs out, the process goes to the back of the queue.

• ✅ Fair, and every process gets to run soon, so response time is good.
• ❌ Every switch costs time. If a switch costs c and the quantum is q, only q / (q + c) of the CPU time is useful work.
• Choosing the quantum is the whole game: too small and you waste time switching, too large and it turns into FCFS. A good rule of thumb is about the length of a typical interactive burst.

### Multilevel Feedback Queue (MLFQ)

Several queues with different priorities. New processes start at the top. A process that uses up its whole time slice gets moved down; one that gives up the CPU early (like an app waiting for a keypress) stays up.

• ✅ Interactive apps naturally stay fast, and CPU-heavy jobs sink to the bottom, without needing to know burst times in advance.
• ✅ It approximates SJF using cheap rules, which is why many general-purpose operating systems use a version of it.
• To avoid starvation, every process is periodically boosted back to the top.

## 3. A worked example

Three processes arrive close together:

• P1 arrives at 0 ms and needs 7 ms of CPU.
• P2 arrives at 1 ms and needs 4 ms.
• P3 arrives at 2 ms and needs 1 ms.

Here is the order each algorithm runs them in (Round Robin uses a 2 ms quantum):

And the results, averaged over the three processes:

What this shows:

• FCFS is worst: tiny P3 waits 9 ms behind the long P1.
• SJF helps a bit, but it can't interrupt P1 once it has started.
• SRTF wins on every average, because it lets short jobs jump in immediately. It needs to know burst times to do that.
• Round Robin doesn't know burst times at all, and still gets close on response time. The price is more context switches.

## 4. Side by side

## 5. Choosing the time quantum

The quantum is the most important setting in Round Robin. Here is how much CPU time is useful work at different quanta, assuming one context switch costs 0.5 ms:

A small quantum feels responsive but wastes a third of the CPU on switching. A large one wastes almost nothing, but processes wait longer for their turn. Real systems pick something in the middle, and some adjust it at runtime.

## 6. Real-time scheduling

Some systems, like car brakes, pacemakers or industrial robots, don't just need to be fast. They need to always meet deadlines.

• Rate Monotonic (RM): tasks that repeat more often get higher priority, and priorities never change. For n tasks, it's guaranteed to meet every deadline if total CPU usage stays below n × (2^(1/n) − 1). That's about 83% for 2 tasks, and it approaches 69% as you add more.
• Earliest Deadline First (EDF): always run the task whose deadline is closest. On a single CPU, if any algorithm can meet all deadlines, EDF can too. The catch is that when the system is overloaded, it degrades badly and unpredictably.

Real-time kernels also have to handle interrupts and locks carefully, using priority inheritance so that a high-priority task is never blocked for long.

## 7. Multiple cores

With many CPUs, the scheduler also has to decide where a process runs.

• Partitioned: each process is assigned to one core, and each core schedules on its own. Simple, but one core can be overloaded while another sits idle.
• Global: one shared queue, and any free core takes the next process. Better balanced, but processes jump between cores more.
• Hybrid: group cores into clusters and balance within each group.

Moving a process to another core isn't free. Its data has to be loaded again into that core's cache, so good schedulers try to keep processes on the same core (cache affinity). Idle cores can also take work from busy ones (work stealing).

## 8. Virtual machines and containers

In a virtual machine, there are two schedulers stacked on top of each other: the guest OS schedules its processes, and the hypervisor schedules the virtual CPUs onto real ones. The guest doesn't always know when it's been paused. The time it loses this way is called steal time. Paravirtual interfaces let the guest and the hypervisor share information so both make better decisions.

## 9. What real systems do

• Linux used the Completely Fair Scheduler (CFS) for years. Instead of fixed time slices, it tracks how much CPU time each process has had (its virtual runtime) and always runs the one that has had the least. Since Linux 6.6 it uses EEVDF, which keeps the same idea but handles latency-sensitive tasks better.
• Linux also has real-time classes: SCHED_FIFO and SCHED_RR for fixed priorities, and SCHED_DEADLINE, which works like EDF.
• Datacenters add another layer on top. Tools like Kubernetes decide which machine runs each container, and the OS uses cgroups and CPU quotas to keep one tenant from slowing down the others.

## 10. Ideas behind modern schedulers

• Mix strategies: combine MLFQ-style feedback with fair sharing, to get both responsiveness and fairness.
• Adapt at runtime: tune the quantum based on how long bursts actually are and how much switching costs.
• Prevent starvation: gradually raise the priority of anything that has waited too long.
• Respect locality: balance load across cores without needlessly moving processes away from their cache.

## 11. Comparing schedulers fairly

If you benchmark schedulers yourself:

• Describe the workload: how many short interactive jobs vs long CPU-heavy ones, and how they arrive.
• Report the slowest cases (95th and 99th percentile), not just averages.
• Test the important settings, like quantum size and context switch cost, across a range of values.
• Count switching and cache costs, since they can change which algorithm comes out on top.

## Takeaways

• No single algorithm wins everywhere. SJF is best on paper, Round Robin is fairest, FCFS is simplest.
• The theory gives guarantees (SJF is optimal, EDF meets deadlines whenever possible), but real systems also pay for switching, caches and unknown burst times.
• Modern schedulers are hybrids that measure the workload and adapt: fair sharing, feedback queues and cache-aware placement.

## References

• A. S. Tanenbaum, Modern Operating Systems.
• A. Silberschatz, P. Galvin, G. Gagne, Operating System Concepts.
• C. L. Liu, J. W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment," Journal of the ACM, 1973.
• R. Love, Linux Kernel Development.
• R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces.