I/O Schedulers

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.

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.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label>{{label_algo}}
    <select id="algo">
      <option value="sstf">SSTF</option>
      <option value="scan" selected>SCAN ({{label_elevator}})</option>
      <option value="deadline">Deadline</option>
    </select>
  </label>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<!-- {{c_track}} -->
<div class="track-wrap">
  <div id="track" class="track"></div>
  <div id="head" class="head" title="{{label_head}}"></div>
</div>
<p class="track-label"><span>0</span><span>{{label_cylinders}}</span></p>
<!-- {{c_queue}} -->
<div class="status" id="status">{{status_idle}}</div>
<div id="order-wrap" class="order-wrap"></div>

/* {{c_base_styles}} */
* { 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; }
/* {{c_track_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; }
/* {{c_status_styles}} */
.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; }

// Code not found

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.

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!$ orderings for $n$ requests. Even for $n = 20$, that is over $2 \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.

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.

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.