How does CPU scheduling work, and what are the common algorithms?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** is the kernel's decision of *which* ready thread gets the CPU *next*, and for *how long*. Since there are usually more runnable threads than cores, the **scheduler** multiplexes them, aiming to balance competing goals — **throughput**, **low latency / response time**, and **fairness** — while avoiding **starvation**.

## Common algorithms

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** illustrates the core knob — the **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Real schedulers

Linux's long-standing default was **CFS (Completely Fair Scheduler)**: instead of fixed slices it tracks each task's **virtual runtime (vruntime)** and always runs the thread that has received the least CPU so far, weighted by its **nice** value — approximating "everyone gets a fair share." It keys a red-black tree by vruntime, so picking the next task is O(log n). (Newer kernels use EEVDF, a refinement with the same fairness goal plus tighter latency bounds.)

**Preemptive vs cooperative:** modern OSes are **preemptive** — a timer interrupt lets the scheduler forcibly take the CPU back, so one thread can't monopolize a core.

## Why it matters

Scheduling directly shapes the latency and throughput users feel. Interviewers probe it to see whether you understand trade-offs — why an interactive workload wants short quanta or a priority boost, why priority scheduling needs **aging** to prevent starvation, and how MLFQ/CFS get good interactive behavior without knowing job lengths in advance. It's also the mental model behind tuning `nice`, real-time priorities, and diagnosing a starved or laggy service.

Common algorithms

Real schedulers

Why it matters

Related questions