Introduction

Every time your program reads a file or writes data, the operating system sends a block request to the storage device — a ticket that says "fetch cylinder 1847, sector 12." On a spinning hard disk, satisfying that request means physically moving a read/write head to the right track. That movement takes time: roughly 5–10 ms per seek, which sounds tiny until you realize a busy server can queue hundreds of requests per second.

If the OS honored requests in arrival order, the head would zigzag across the disk at random — an expensive pattern called a seek storm. The I/O scheduler sits between the application and the hardware driver and answers a deceptively simple question: in what order should we serve these pending requests?

The answer matters more than it sounds. The right order can cut total head travel by 60–80 %, turning what would be seconds of waiting into milliseconds. The wrong policies can starve some requests indefinitely, letting a flood of nearby requests monopolize the disk while a distant but urgent one waits forever. Balancing throughput and latency — moving fast and staying fair — is the core tension every disk scheduler must resolve.

Watch the Disk Head Move

Add block requests by clicking on the disk track below, then choose a scheduling algorithm and press Run. Watch the head sweep across the disk and count how many cylinders it travels.

<!-- Interactive I/O scheduler demo — three classic disk scheduling algorithms. -->
<p class="hint">Click anywhere on the track to add a disk block request. Add several, pick a scheduling algorithm, then press <b>Run</b> to watch the disk head sweep through them.</p>
<div class="controls">
  <label>Algorithm:
    <select id="algo">
      <option value="sstf">SSTF</option>
      <option value="scan" selected>SCAN (elevator)</option>
      <option value="deadline">Deadline</option>
    </select>
  </label>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<!-- Disk track visualization — dots = pending requests, red square = head position. -->
<div class="track-wrap">
  <div id="track" class="track"></div>
  <div id="head" class="head" title="Disk head"></div>
</div>
<p class="track-label"><span>0</span><span>200 cylinders</span></p>
<!-- Status and serve-order output. -->
<div class="status" id="status">Click the track to add requests.</div>
<div id="order-wrap" class="order-wrap"></div>

/* Base layout and typography. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
select { font: inherit; padding: .2rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
/* Track, dot, and head styles. */
.track-wrap { position: relative; height: 36px; margin: .4rem 0 0; }
.track { position: absolute; top: 50%; left: 0; right: 0; height: 6px;
         background: #c9ccd1; border-radius: 3px; transform: translateY(-50%); cursor: crosshair; }
.req-dot { position: absolute; width: 14px; height: 14px; border-radius: 50%;
           background: #1d3557; border: 2px solid #fff; top: 50%; transform: translate(-50%, -50%);
           cursor: pointer; transition: background .2s; }
.req-dot.served { background: #0a7d33; }
.req-dot.expired { background: #e63946; }
.head { position: absolute; width: 20px; height: 20px; border-radius: 4px;
        background: #e63946; top: 50%; transform: translate(-50%, -50%);
        border: 2px solid #fff; z-index: 2; transition: left .35s ease-in-out; }
.track-label { display: flex; justify-content: space-between; font-size: .75rem; color: #888; margin: .1rem 0 .4rem; }
/* Status line and serve-order display. */
.status { font-size: .95rem; font-weight: 600; min-height: 1.5em; margin: .4rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.order-wrap { font-size: .82rem; color: #444; line-height: 1.6; min-height: 1.4em; }
.order-wrap .seq-label { font-weight: 600; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Simulation constants. */
const MAX_CYL = 200;
const DEADLINE_MS = 3000; /* requests older than 3 s are considered expired and get priority */
let requests = []; /* request list, each entry has { cyl, arrivedAt, served, expired } { cyl, arrivedAt } */
let headPos = 50;
let running = false;

const trackEl = document.getElementById('track');
const headEl  = document.getElementById('head');
const statusEl = document.getElementById('status');
const orderEl  = document.getElementById('order-wrap');

/* Convert between percentage position and cylinder number. */
function pctToCyl(pct) { return Math.round(pct * MAX_CYL); }
function cylToPct(cyl)  { return cyl / MAX_CYL; }

function renderHead() {
  headEl.style.left = (cylToPct(headPos) * 100) + '%';
}

/* Render all pending requests as colored dots on the track. */
function renderDots() {
  trackEl.querySelectorAll('.req-dot').forEach(d => d.remove());
  requests.forEach((r, i) => {
    const d = document.createElement('div');
    d.className = 'req-dot' + (r.served ? ' served' : '') + (r.expired ? ' expired' : '');
    d.style.left = (cylToPct(r.cyl) * 100) + '%';
    d.title = i18nFmt('Cylinder %cyl% — click to remove', { cyl: r.cyl });
    /* Allow removing a request by clicking its dot (only when not running). */
    d.addEventListener('click', e => {
      if (running) return;
      requests.splice(i, 1);
      renderDots();
    });
    trackEl.appendChild(d);
  });
}

/* Add a new request at the clicked position on the track. */
trackEl.addEventListener('click', e => {
  if (running) return;
  const rect = trackEl.getBoundingClientRect();
  const pct  = (e.clientX - rect.left) / rect.width;
  const cyl  = pctToCyl(Math.max(0, Math.min(1, pct)));
  requests.push({ cyl, arrivedAt: Date.now(), served: false, expired: false });
  renderDots();
  setStatus('Click the track to add requests.', '');
});

function setStatus(t, cls) {
  statusEl.textContent = t;
  statusEl.className = 'status ' + cls;
}

/* SSTF: always serve the nearest pending request. */
function sstfOrder(head, reqs) {
  const rem = reqs.map((r, i) => ({ ...r, idx: i }));
  const order = [];
  let pos = head;
  while (rem.length) {
    rem.sort((a, b) => Math.abs(a.cyl - pos) - Math.abs(b.cyl - pos));
    const next = rem.shift();
    order.push(next.idx);
    pos = next.cyl;
  }
  return order;
}

/* SCAN (elevator): sweep upward first, then reverse. */
function scanOrder(head, reqs) {
  const above = reqs.map((r, i) => ({ ...r, idx: i })).filter(r => r.cyl >= head).sort((a, b) => a.cyl - b.cyl);
  const below = reqs.map((r, i) => ({ ...r, idx: i })).filter(r => r.cyl < head).sort((a, b) => b.cyl - a.cyl);
  return [...above, ...below].map(r => r.idx);
}

/* Deadline: like SCAN but expired requests jump to the front. */
function deadlineOrder(head, reqs, now) {
  const expired = reqs.map((r, i) => ({ ...r, idx: i })).filter(r => (now - r.arrivedAt) >= DEADLINE_MS);
  if (expired.length) {
    /* Serve expired requests first (in SSTF order among themselves), then the rest via SCAN. */
    const expOrder = sstfOrder(head, expired.map(r => ({ cyl: r.cyl })));
    const expIdxs  = expOrder.map(i => expired[i].idx);
    const remaining = reqs.map((r, i) => ({ ...r, idx: i })).filter((_, i) => !expIdxs.includes(i));
    const restOrder = scanOrder(head, remaining.map(r => ({ cyl: r.cyl, arrivedAt: r.arrivedAt })));
    const restIdxs  = restOrder.map(i => remaining[i].idx);
    return [...expIdxs, ...restIdxs];
  }
  return scanOrder(head, reqs);
}

/* Animate the head moving through the computed serve order. */
async function animate(order) {
  running = true;
  document.getElementById('run').disabled = true;
  const algo = document.getElementById('algo').value;
  let totalSeek = 0;
  let prevPos = headPos;
  const seqLabels = [];
  const now = Date.now();

  for (let step = 0; step < order.length; step++) {
    const idx = order[step];
    const r   = requests[idx];
    /* Mark visually if this request was already expired when Run was pressed. */
    if (algo === 'deadline' && (now - r.arrivedAt) >= DEADLINE_MS) {
      r.expired = true;
    }
    const dest = r.cyl;
    totalSeek += Math.abs(dest - prevPos);
    headPos = dest;
    renderHead();
    r.served = true;
    renderDots();
    seqLabels.push(dest);
    setStatus(i18nFmt('Step %step%/%total%: serving cylinder %cyl% (total seek: %seek%)', { step: step + 1, total: order.length, cyl: dest, seek: totalSeek }), '');
    await new Promise(res => setTimeout(res, 380));
    prevPos = dest;
  }
  setStatus(i18nFmt('Done! Total seek distance: %seek% cylinders.', { seek: totalSeek }), 'ok');
  orderEl.innerHTML = '<span class="seq-label">Serve order:</span> ' + seqLabels.join(' → ');
  running = false;
  document.getElementById('run').disabled = false;
}

document.getElementById('run').addEventListener('click', () => {
  if (running) return;
  if (!requests.length) { setStatus('Add at least one request first.', 'bad'); return; }
  requests.forEach(r => { r.served = false; r.expired = false; });
  const algo = document.getElementById('algo').value;
  let order;
  /* Dispatch to the selected algorithm. */
  if (algo === 'sstf')     order = sstfOrder(headPos, requests);
  else if (algo === 'scan') order = scanOrder(headPos, requests);
  else                      order = deadlineOrder(headPos, requests, Date.now());
  animate(order);
});

document.getElementById('reset').addEventListener('click', () => {
  if (running) return;
  requests = [];
  headPos = 50;
  renderHead();
  renderDots();
  setStatus('Click the track to add requests.', '');
  orderEl.innerHTML = '';
});

/* Initial render. */
renderHead();
setStatus('Click the track to add requests.', '');
Result
Console

Notice how SSTF (Shortest Seek Time First) always jumps to the nearest pending request — great for throughput but prone to starvation: requests far from the current cluster wait indefinitely while closer ones keep arriving. SCAN (the elevator) sweeps in one direction, serves everything in its path, then reverses — fair to all requests but occasionally makes some wait for a full sweep. Deadline wraps SCAN in a timer: if any request has been waiting too long, it gets priority — guaranteeing a latency bound while keeping throughput high.

The Real Complexity

How hard is it to find the best order for a set of disk requests?

  • Checking a proposed order is trivial: sum the cylinder distances between consecutive requests.
  • Brute force tries every permutation — n!n! orderings for nn requests. Even for n=20n = 20, that is over 2×10182 \times 10^{18} options. Hopeless.
  • Optimal disk scheduling is NP-hard in the general case. It reduces to the Travelling Salesman Problem: the cylinders are cities, the seek distances are road lengths, and you want the shortest tour that visits every pending request exactly once.
  • Greedy heuristics work remarkably well in practice. The classic algorithms sacrifice global optimality for predictable, near-optimal behavior:
    • SSTF (Shortest Seek Time First, 1954) greedily picks the nearest request. Seek time drops but starvation is possible.
    • SCAN / Elevator (Denning, 1967) sweeps the arm back and forth like a building elevator — no starvation, predictable wait time.
    • C-SCAN (Circular SCAN) returns to the lowest cylinder after reaching the end, giving more uniform wait times.
    • Deadline (Jens Axboe, Linux kernel) adds per-request expiry timers on top of SCAN, guaranteeing a latency bound.
    • CFQ (Completely Fair Queuing) assigns each process its own queue with a time slice — fairness across competing applications.

The key insight mirrors scheduling in general: perfect optimality is intractable, but smart approximations turn a potentially chaotic hardware interface into a smooth, predictable resource.

Where It Matters

Disk scheduling is no longer just about spinning platters — its principles permeate every layer of modern storage:

  • SSDs and NVMe: flash memory has no seek time, but NVMe queues can hold 65,535 commands across 65,535 parallel queues. Schedulers still reorder writes for write amplification reduction and wear leveling.
  • Database storage engines: InnoDB, PostgreSQL, and RocksDB maintain their own internal I/O queues, merging and reordering flushes to match the underlying device's access pattern.
  • RAID and storage arrays: controllers aggregate requests across many spindles and must schedule across physical disks simultaneously, a multi-dimensional version of the same problem.
  • Cloud block storage: services like AWS EBS and Google Persistent Disk expose a virtual block device to VMs; the backend schedules requests across hundreds of physical disks, using deadline-style bounds to meet SLA latency guarantees.
  • OS I/O schedulers today: Linux's mq-deadline and kyber schedulers are the successors of the classic algorithms — adapted for NVMe's multiqueue architecture while preserving the core deadline guarantee.

Understanding disk scheduling means understanding why load balancing and queue management matter everywhere throughput and latency must coexist.

Conclusion

The disk scheduler solves an ancient version of the same problem that appears in airline routing, job shop scheduling, and delivery optimization: visit many locations in an order that minimizes total travel, subject to urgency constraints.

Optimal ordering is NP-hard, but the elevator metaphor turns out to be close enough to perfect in practice. SCAN, Deadline, and CFQ sacrifice provable optimality for predictable latency bounds and fairness guarantees — and that trade-off is exactly what a real-time system needs.

So the next time a file loads in milliseconds instead of seconds, a small piece of that speed comes from a scheduler quietly reordering your requests, sweeping the disk head back and forth like a patient elevator, making sure every floor gets visited — and no one waits too long.

Share this article

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

Comments

Loading comments...

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