Introduction

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.

Try the Policies

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.

<!-- Scheduler demo — policy selector + Gantt chart -->
<div class="controls">
  <label for="policy">Policy:</label>
  <select id="policy">
    <option value="rr">Round-Robin</option>
    <option value="mlfq">MLFQ</option>
    <option value="cfs">CFS (Linux)</option>
  </select>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="task-list" id="task-list" aria-label="Task list with burst lengths">
  <!-- task badges injected by JS -->
</div>
<div class="gantt-wrap">
  <div class="gantt-label">Gantt chart (each box = 1 time unit):</div>
  <div class="gantt" id="gantt" aria-label="Gantt chart showing CPU allocation over time"></div>
</div>
<div class="metrics" id="metrics"></div>
<div class="status" id="status"></div>

/* Demo styles — Gantt ticks, task badges, metrics strip */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// CPU scheduling simulator — Round-Robin, MLFQ, CFS

// Task definitions: id, burst length (CPU units), display color
const TASKS = [
  { id: 'A', burst: 8,  color: '#e63946', label: 'A' },
  { id: 'B', burst: 4,  color: '#2a9d8f', label: 'B' },
  { id: 'C', burst: 12, color: '#e9c46a', label: 'C' },
  { id: 'D', burst: 2,  color: '#457b9d', label: 'D' }
];
const QUANTUM = 3; // Round-Robin time quantum (units)
const TOTAL_TICKS = 32;

// Round-Robin: cycle through all tasks in fixed QUANTUM slices
function scheduleRR(tasks) {
  const q = tasks.map(t => ({ ...t, rem: t.burst }));
  const gantt = [];
  let done = false;
  while (!done) {
    done = true;
    for (const t of q) {
      if (t.rem <= 0) continue;
      done = false;
      const run = Math.min(QUANTUM, t.rem);
      for (let i = 0; i < run; i++) gantt.push(t.id);
      t.rem -= run;
    }
  }
  return gantt;
}

// MLFQ: three queues with growing quanta; tasks demote on exhaustion
function scheduleMLFQ(tasks) {
  // queues[0] = highest priority (short quantum), queues[2] = lowest
  const queues = [[], [], []];
  const quanta = [2, 4, 8];
  const state = tasks.map(t => ({ ...t, rem: t.burst, q: 0 }));
  state.forEach(t => queues[0].push(t));
  const gantt = [];
  let ticks = 0;
  while (ticks < TOTAL_TICKS) {
    let ran = false;
    for (let qi = 0; qi < queues.length; qi++) {
      if (queues[qi].length === 0) continue;
      const t = queues[qi].shift();
      if (t.rem <= 0) { ran = true; break; }
      const run = Math.min(quanta[qi], t.rem);
      for (let i = 0; i < run; i++) { gantt.push(t.id); ticks++; }
      t.rem -= run;
      if (t.rem > 0) {
        const nq = Math.min(qi + 1, queues.length - 1);
        queues[nq].push(t);
      }
      ran = true;
      break;
    }
    if (!ran) break;
  }
  return gantt;
}

// CFS: always run the task with the lowest virtual runtime
function scheduleCFS(tasks) {
  // vrt = accumulated CPU time; CFS minimises max deviation
  const state = tasks.map(t => ({ ...t, rem: t.burst, vrt: 0 }));
  const gantt = [];
  let ticks = 0;
  while (ticks < TOTAL_TICKS) {
    const ready = state.filter(t => t.rem > 0);
    if (ready.length === 0) break;
    // Pick task with lowest virtual runtime — pick task with lowest virtual runtime
    ready.sort((a, b) => a.vrt - b.vrt);
    const t = ready[0];
    // Target slice shrinks as more tasks compete
    const slice = Math.max(1, Math.floor(6 / ready.length));
    const run = Math.min(slice, t.rem);
    for (let i = 0; i < run; i++) { gantt.push(t.id); ticks++; }
    t.vrt += run;
    t.rem -= run;
  }
  return gantt;
}

// Compute avg turnaround (finish - arrival) and avg response (first run)
function computeMetrics(gantt, tasks) {
  const finish = {};
  const first = {};
  gantt.forEach((id, i) => {
    if (!(id in first)) first[id] = i;
    finish[id] = i + 1;
  });
  let totalTurnaround = 0, totalResponse = 0;
  tasks.forEach(t => {
    totalTurnaround += (finish[t.id] ?? 0) - 0;
    totalResponse += (first[t.id] ?? 0);
  });
  return {
    avgTurnaround: (totalTurnaround / tasks.length).toFixed(1),
    avgResponse: (totalResponse / tasks.length).toFixed(1)
  };
}

function renderTasks() {
  const el = document.getElementById('task-list');
  el.innerHTML = TASKS.map(t =>
    `<div class="task-badge" style="background:${t.color}">${t.label} <span>(${t.burst} units)</span></div>`
  ).join('');
}

function renderGantt(gantt) {
  const el = document.getElementById('gantt');
  el.innerHTML = '';
  gantt.forEach(id => {
    const t = TASKS.find(x => x.id === id);
    const d = document.createElement('div');
    d.className = 'tick';
    d.textContent = t ? t.label : '';
    d.style.background = t ? t.color : '';
    d.title = t ? t.label : '';
    el.appendChild(d);
  });
}

function renderMetrics(gantt) {
  const m = computeMetrics(gantt, TASKS);
  document.getElementById('metrics').innerHTML =
    `<div class="metric"><strong>Avg turnaround:</strong> ${m.avgTurnaround}</div>` +
    `<div class="metric"><strong>Avg response:</strong> ${m.avgResponse}</div>`;
}

function run() {
  const policy = document.getElementById('policy').value;
  let gantt;
  // Dispatch to the selected scheduling algorithm
  if (policy === 'rr')   gantt = scheduleRR(TASKS);
  else if (policy === 'mlfq') gantt = scheduleMLFQ(TASKS);
  else                   gantt = scheduleCFS(TASKS);

  renderGantt(gantt.slice(0, TOTAL_TICKS));
  renderMetrics(gantt.slice(0, TOTAL_TICKS));
  const names = { rr: 'Round-Robin', mlfq: 'MLFQ', cfs: 'CFS (Linux)' };
  document.getElementById('status').textContent =
    i18nFmt('Scheduled with %policy%.', { policy: names[policy] });
}

function reset() {
  document.getElementById('gantt').innerHTML = '';
  document.getElementById('metrics').innerHTML = '';
  document.getElementById('status').textContent = '';
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', reset);
renderTasks();
Result
Console

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.

The Real Complexity

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 vv. Picking the next task is O(log⁡n)O(\log n). The key invariant: after nn tasks each run for time tt, 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 qiq_{i}. Tasks that exhaust their slice in queue ii are demoted to queue i+1i+1 with a longer slice qi+1>qiq_{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.

Where It Matters

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.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cpu-scheduling/Content licensed under CC BY-NC 4.0.