CPU Scheduling

Your laptop is running dozens of processes right now. Yet your processor core can only execute one instruction stream at a time. Something has to decide who runs and for how long — that something is the CPU scheduler.

Every context switch is free in theory and costly in practice. Swap tasks too often and the CPU wastes time saving and restoring state. Swap too rarely and interactive programs feel sluggish. The scheduler sits in this tension and must resolve it thousands of times per second without ever stopping to think.

Three policies dominate the history of this problem:

• Round-Robin (RR) — every task gets the same fixed time slice in turn. Simple, fair, predictable.
• Multi-Level Feedback Queue (MLFQ) — tasks are sorted into priority queues. New tasks start high; tasks that burn their slice drop lower. Interactive tasks that yield early stay high.
• Completely Fair Scheduler (CFS) — Linux's answer since 2007. Instead of time slices it tracks virtual runtime and always picks the task that has run the least. Fairness emerges from the math, not from bookkeeping.

Each policy optimizes a different thing. Understanding the tradeoff is the key to understanding operating systems.

Below are four tasks with different CPU demands. Pick a scheduling policy and press Run to watch the CPU allocate time. The Gantt chart shows which task owns each time unit.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="policy">{{label_policy}}</label>
  <select id="policy">
    <option value="rr">{{opt_rr}}</option>
    <option value="mlfq">{{opt_mlfq}}</option>
    <option value="cfs">{{opt_cfs}}</option>
  </select>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="task-list" id="task-list" aria-label="{{aria_task_list}}">
  <!-- {{c_tasks_rendered_by_js}} -->
</div>
<div class="gantt-wrap">
  <div class="gantt-label">{{label_gantt}}</div>
  <div class="gantt" id="gantt" aria-label="{{aria_gantt}}"></div>
</div>
<div class="metrics" id="metrics"></div>
<div class="status" id="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-weight: 600; font-size: .9rem; }
select { font-size: .9rem; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.task-list { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
.task-badge { display: flex; align-items: center; gap: .35rem; font-size: .85rem;
              padding: .25rem .55rem; border-radius: 6px; color: #fff; font-weight: 600; }
.task-badge span { opacity: .85; font-weight: 400; }
.gantt-wrap { margin-bottom: .5rem; }
.gantt-label { font-size: .78rem; color: #666; margin-bottom: .25rem; font-weight: 600; }
.gantt { display: flex; flex-wrap: wrap; gap: 2px; min-height: 28px; }
.tick { width: 18px; height: 28px; border-radius: 3px; display: flex; align-items: center;
        justify-content: center; font-size: 9px; color: #fff; font-weight: 700; }
.tick.idle { background: #dde1e6; color: #888; }
.metrics { display: flex; gap: .75rem; flex-wrap: wrap; font-size: .82rem; margin-bottom: .35rem; }
.metric { background: #f0f3f6; border-radius: 6px; padding: .2rem .5rem; }
.metric strong { color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.2em; color: #0a7d33; }

// Code not found

Notice what changes across policies. Round-Robin is perfectly fair by construction but gives every task the same slice regardless of need. MLFQ boosts short, interactive tasks — they finish fast while long jobs slowly sink to lower queues. CFS accumulates virtual runtime and always picks the task that has fallen most behind, producing a smooth fairness curve even when tasks arrive late.

No policy wins on every metric. That is the central insight of scheduling theory.

How hard is scheduling, really?

• Optimal offline scheduling — given all job lengths in advance, minimizing total completion time is solvable in polynomial time for simple models. But add priorities, deadlines, multiple cores, and preemption and many variants become NP-hard (see scheduling).
• Online scheduling — the OS does not know how long a task will run. It must make decisions with zero lookahead. No online algorithm can be optimal against an adversarial sequence of tasks; this is the classic competitive analysis setting.
• CFS in practice — Linux's CFS keeps tasks in a red-black tree ordered by virtual runtime $v$. Picking the next task is $O(\log n)$. The key invariant: after $n$ tasks each run for time $t$, every task's virtual runtime differs by at most $\varepsilon$, where $\varepsilon$ shrinks with the target latency parameter.
• MLFQ's feedback loop — each queue runs Round-Robin with its own slice $q_{i}$. Tasks that exhaust their slice in queue $i$ are demoted to queue $i+1$ with a longer slice $q_{i+1} > q_{i}$. Tasks that voluntarily yield (I/O wait) are promoted back. This heuristic learns burst length without knowing it upfront.

The gap between what we want (optimal average latency, no starvation, perfect fairness) and what is computable in real time is bridged by clever approximations — the same theme that runs through load balancing and all online optimization.

The scheduler is invisible until something goes wrong — then it is all you see:

• Interactive desktops: CFS's fairness keeps your music from stuttering when a compile job spikes to 100%. The scheduler is what makes multitasking feel smooth.
• Web servers: Nginx and Apache use event-loop scheduling (one thread, many connections) to serve thousands of requests without context-switch overhead. The OS scheduler and the application scheduler cooperate.
• Databases: query execution engines schedule disk I/O, CPU threads, and lock acquisition. A poorly scheduled query plan can starve other clients for seconds.
• Cloud virtual machines: hypervisors like KVM and Xen schedule virtual CPUs on physical cores. A noisy neighbor in the same host can inflate your VM's scheduler latency by 10×.
• Real-time systems: embedded controllers (cars, aircraft, medical devices) use Rate-Monotonic Scheduling (RMS) or Earliest-Deadline-First (EDF) — provably optimal policies for meeting hard deadlines.

Every system that shares a resource under uncertainty is, at its core, a scheduling problem. The same ideas that power the Linux kernel appear in load balancing, database query planning, and network packet switching.

CPU scheduling looks deceptively simple: pick the next task, run it for a while, repeat. But the moment you ask which task and how long, you are navigating a web of competing objectives — latency versus throughput, fairness versus priority, simplicity versus adaptability.

Round-Robin, MLFQ, and CFS are each the right answer to a different question. And behind all of them lurks a deeper truth: the optimal offline schedule is often NP-hard to compute, and the online version is provably impossible to perfect. Every OS is running the best approximation it can, $O(\log n)$ decisions per millisecond, in the dark.

The next time your computer feels fast, thank the scheduler. The next time it freezes, blame it — and then remember that load balancing has the exact same problem at the cluster scale.