Lesson 2 · Files, storage, I/O, and protection

Disk Scheduling and I/O

A mechanical disk spends most of a request moving its head, so the order requests are served in changes total time dramatically. That is the entire motivation for disk scheduling — and the reason it matters far less on an SSD.

Why Order Matters on a Disk

A hard disk request costs three things. Seek time moves the head to the right cylinder and is by far the largest, typically 5–10 ms. Rotational latency waits for the sector to come round, averaging half a rotation — about 4 ms at 7200 rpm. Transfer time is the actual read, often well under a millisecond.

Disk scheduling and IO are two halves of one story. Disk scheduling is the ordering of pending disk requests to minimise total head movement. It is worth doing because seek time dominates and depends entirely on how far the head travels: with several requests queued, choose the sequence that minimises total head movement.

The example on this page uses the standard queue — requests for cylinders 98, 183, 37, 122, 14, 124, 65 with the head starting at 53 — because it separates the algorithms cleanly. FCFS travels 640 cylinders on it; SCAN travels 236.

It is worth knowing this is a queueing problem the OS can only solve because it has several requests to look at. A single request has no ordering to optimise, which is why disk scheduling only pays off under concurrent load.

Seek 5–10 ms, rotation ~4 ms, transfer well under 1 ms
Seek dominates and scales with head distance
Ordering only helps when several requests are queued
On the standard queue: FCFS 640 cylinders, SCAN 236

The Algorithms

FCFS serves requests in arrival order. It is perfectly fair and ignores geometry entirely, so the head can zigzag across the platter — 53 to 98 to 183 back to 37 and out again to 122. Every reversal is wasted movement.

SSTF (shortest seek time first) always picks the nearest pending request. It substantially reduces head movement and is greedy in both senses: a stream of requests near the head's current position can starve a distant one indefinitely, exactly as SJF starves long jobs.

SCAN — the elevator algorithm — moves in one direction serving everything it passes, then reverses at the end. A lift going up does not stop to reverse for one passenger and it does not strand anyone. No starvation, and near-SSTF efficiency.

C-SCAN sweeps one way only, then jumps straight back to the start without serving on the return. That sounds wasteful and produces more uniform waiting time: under plain SCAN, a request just behind the head waits for a full sweep out and back, while one just ahead is served immediately. LOOK and C-LOOK refine both by reversing at the last actual request instead of the physical end of the disk, which is what real implementations use.

Head at 53, queue 98 183 37 122 14 124 65 — total travel per policy
Algorithm	Order served	Cylinders	Starvation
FCFS	98, 183, 37, 122, 14, 124, 65	638	No
SSTF	65, 37, 14, 98, 122, 124, 183	232	Yes
SCAN	65, 98, 122, 124, 183, then 37, 14	299	No
C-SCAN	65, 98, 122, 124, 183, wrap, 14, 37	382	No — most uniform waiting

FCFS: fair, ignores geometry, zigzags
SSTF: greedy and efficient, starves distant requests
SCAN: one sweep then reverse — no starvation
C-SCAN evens out waiting; LOOK stops at the last real request

Key reference

Terms, operations, and practical uses

Where the time goes

Seek timeMoving the head — 5-10 ms, and the dominant cost.
Rotational latencyWaiting for the sector, ~4 ms at 7200 rpm.
Transfer timeThe actual read, usually well under a millisecond.

Algorithms

FCFSArrival order; zigzags across the platter.
SSTFNearest request first; efficient and starves distant ones.
SCANSweep one way then reverse — the elevator, no starvation.
C-SCAN and LOOKEvens out waiting; LOOK turns at the last real request.

Getting data across

Programmed I/OThe CPU copies every byte itself.
Interrupt-drivenCPU is free between transfers but still copies.
DMAThe controller moves data; one interrupt per transfer.
Page cacheFree memory used for cached blocks by design.

Code example

Six disk scheduling algorithms on one queue

# Six disk scheduling algorithms on one request queue.
# Cost is total head movement in cylinders -- the only thing that matters
# on a spinning disk, where a seek is 1000x the cost of a transfer.
REQS = [98, 183, 37, 122, 14, 124, 65]
START, MAXC = 53, 199

def cost(order):
    return sum(abs(order[i] - order[i - 1]) for i in range(1, len(order)))

def fcfs(reqs, head):
    return [head] + reqs                      # arrival order, no reordering

def sstf(reqs, head):
    order, pending = [head], reqs[:]
    while pending:                            # always the closest one left
        nxt = min(pending, key=lambda c: abs(c - order[-1]))
        pending.remove(nxt)
        order.append(nxt)
    return order

def scan(reqs, head, end=MAXC):
    up = sorted(c for c in reqs if c >= head)
    down = sorted((c for c in reqs if c < head), reverse=True)
    return [head] + up + [end] + down         # walks to the physical end

def look(reqs, head):
    up = sorted(c for c in reqs if c >= head)
    down = sorted((c for c in reqs if c < head), reverse=True)
    return [head] + up + down                 # turns at the last request

def c_scan(reqs, head, end=MAXC):
    up = sorted(c for c in reqs if c >= head)
    low = sorted(c for c in reqs if c < head)
    return [head] + up + [end, 0] + low       # one direction, then reset

def c_look(reqs, head):
    up = sorted(c for c in reqs if c >= head)
    low = sorted(c for c in reqs if c < head)
    return [head] + up + low                  # jump straight to the lowest

algos = [("FCFS", fcfs), ("SSTF", sstf), ("SCAN", scan),
         ("LOOK", look), ("C-SCAN", c_scan), ("C-LOOK", c_look)]
parts = [f"{name} {cost(fn(REQS, START))}" for name, fn in algos]
print(" | ".join(parts))

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Six disk scheduling algorithms on one request queue.
// Cost is total head movement in cylinders -- the only thing that matters
// on a spinning disk, where a seek is 1000x the cost of a transfer.
const int START = 53, MAXC = 199;
int cost(const vector<int>& o) {
    int t = 0;
    for (size_t i = 1; i < o.size(); i++) t += abs(o[i] - o[i - 1]);
    return t;
}
vector<int> above(vector<int> r, int h) {
    vector<int> v;
    for (int c : r) if (c >= h) v.push_back(c);
    sort(v.begin(), v.end());
    return v;
}
vector<int> below(vector<int> r, int h, bool desc) {
    vector<int> v;
    for (int c : r) if (c < h) v.push_back(c);
    sort(v.begin(), v.end());
    if (desc) reverse(v.begin(), v.end());
    return v;
}
vector<int> fcfs(vector<int> r, int h) {
    vector<int> o {
        h
    }; // arrival order, no reordering
    for (int c : r) o.push_back(c);
    return o;
}
vector<int> sstf(vector<int> r, int h) {
    vector<int> o {
        h
    }, p = r;
    while (!p.empty()) {   // always the closest one left
        size_t best = 0;
        for (size_t i = 1; i < p.size(); i++)
        if (abs(p[i] - o.back()) < abs(p[best] - o.back())) best = i;
        o.push_back(p[best]);
        p.erase(p.begin() + best);
    }
    return o;
}
vector<int> scanAlgo(vector<int> r, int h) {
    vector<int> o {
        h
    }, u = above(r, h), d = below(r, h, true);
    for (int c : u) o.push_back(c);
    o.push_back(MAXC); // walks to the physical end
    for (int c : d) o.push_back(c);
    return o;
}
vector<int> look(vector<int> r, int h) {
    vector<int> o {
        h
    }, u = above(r, h), d = below(r, h, true);
    for (int c : u) o.push_back(c); // turns at the last request
    for (int c : d) o.push_back(c);
    return o;
}
vector<int> cScan(vector<int> r, int h) {
    vector<int> o {
        h
    }, u = above(r, h), l = below(r, h, false);
    for (int c : u) o.push_back(c);
    o.push_back(MAXC);
    o.push_back(0); // one direction, then reset
    for (int c : l) o.push_back(c);
    return o;
}
vector<int> cLook(vector<int> r, int h) {
    vector<int> o {
        h
    }, u = above(r, h), l = below(r, h, false);
    for (int c : u) o.push_back(c); // jump straight to the lowest
    for (int c : l) o.push_back(c);
    return o;
}
int main() {
    vector<int> reqs {
        98, 183, 37, 122, 14, 124, 65
    };
    cout << "FCFS " << cost(fcfs(reqs, START))
    << " | SSTF " << cost(sstf(reqs, START))
    << " | SCAN " << cost(scanAlgo(reqs, START))
    << " | LOOK " << cost(look(reqs, START))
    << " | C-SCAN " << cost(cScan(reqs, START))
    << " | C-LOOK " << cost(cLook(reqs, START)) << "\n";
}

import java.util.*;
class Main {
    // Six disk scheduling algorithms on one request queue.
    // Cost is total head movement in cylinders -- the only thing that matters
    // on a spinning disk, where a seek is 1000x the cost of a transfer.
    static final int START = 53, MAXC = 199;
    static int cost(List<Integer> o) {
        int t = 0;
        for (int i = 1; i < o.size(); i++) t += Math.abs(o.get(i) - o.get(i - 1));
        return t;
    }
    static List<Integer> above(int[] r, int h) {
        List<Integer> v = new ArrayList<>();
        for (int c : r) if (c >= h) v.add(c);
        Collections.sort(v);
        return v;
    }
    static List<Integer> below(int[] r, int h, boolean desc) {
        List<Integer> v = new ArrayList<>();
        for (int c : r) if (c < h) v.add(c);
        Collections.sort(v);
        if (desc) Collections.reverse(v);
        return v;
    }
    static List<Integer> fcfs(int[] r, int h) {
        List<Integer> o = new ArrayList<>(); // arrival order, no reordering
        o.add(h);
        for (int c : r) o.add(c);
        return o;
    }
    static List<Integer> sstf(int[] r, int h) {
        List<Integer> o = new ArrayList<>(), p = new ArrayList<>();
        o.add(h);
        for (int c : r) p.add(c);
        while (!p.isEmpty()) {   // always the closest one left
            int best = 0;
            for (int i = 1; i < p.size(); i++)
            if (Math.abs(p.get(i) - o.get(o.size() - 1))
            < Math.abs(p.get(best) - o.get(o.size() - 1))) best = i;
            o.add(p.remove(best));
        }
        return o;
    }
    static List<Integer> scan(int[] r, int h) {
        List<Integer> o = new ArrayList<>();
        o.add(h);
        o.addAll(above(r, h));
        o.add(MAXC); // walks to the physical end
        o.addAll(below(r, h, true));
        return o;
    }
    static List<Integer> look(int[] r, int h) {
        List<Integer> o = new ArrayList<>();
        o.add(h);
        o.addAll(above(r, h)); // turns at the last request
        o.addAll(below(r, h, true));
        return o;
    }
    static List<Integer> cScan(int[] r, int h) {
        List<Integer> o = new ArrayList<>();
        o.add(h);
        o.addAll(above(r, h));
        o.add(MAXC);
        o.add(0); // one direction, then reset
        o.addAll(below(r, h, false));
        return o;
    }
    static List<Integer> cLook(int[] r, int h) {
        List<Integer> o = new ArrayList<>();
        o.add(h);
        o.addAll(above(r, h)); // jump straight to the lowest
        o.addAll(below(r, h, false));
        return o;
    }
    public static void main(String[] args) {
        int[] reqs = {98, 183, 37, 122, 14, 124, 65};
        System.out.println("FCFS " + cost(fcfs(reqs, START))
        + " | SSTF " + cost(sstf(reqs, START))
        + " | SCAN " + cost(scan(reqs, START))
        + " | LOOK " + cost(look(reqs, START))
        + " | C-SCAN " + cost(cScan(reqs, START))
        + " | C-LOOK " + cost(cLook(reqs, START)));
    }
}

Inputqueue 98 183 37 122 14 124 65; head at 53; 200 cylinders

Example

Run the example step by step

Output

How I/O Actually Reaches the Device

A device driver presents a uniform interface — open, read, write, ioctl — over hardware that is anything but uniform, which is what lets the same read() work on an NVMe drive, a USB stick, and a network file system.

Getting data across is the interesting part. Programmed I/O has the CPU copy every byte to or from device registers, which works and wastes the entire processor on copying. Interrupt-driven I/O lets the CPU issue a request and do something else, with the device raising an interrupt on completion — better, but the CPU still performs the transfer.

DMA removes the CPU from the transfer entirely. The CPU programs a DMA controller with a source, a destination, and a length; the controller moves the data directly to or from memory and raises a single interrupt when the whole transfer is done. One interrupt per transfer instead of one per byte is what makes gigabyte-per-second devices possible.

Buffering decouples speeds — a slow device fills a kernel buffer while the application does other work — and caching keeps recently used blocks in memory so repeat reads never reach the device at all. The Linux page cache does this by default with all free memory, which is why 'free' memory looks alarmingly low on a healthy machine and is not a problem.

Three ways to move data, and what the CPU does in each
Technique	CPU copies data	Interrupts	CPU free during transfer
Programmed I/O	Yes, every byte	None	No
Interrupt-driven	Yes, every byte	One per byte or block	Between transfers only
DMA	No	One per transfer	Yes

Drivers hide device differences behind one interface
Programmed I/O burns the CPU; interrupts free it between transfers
DMA moves data with one interrupt for the whole transfer
The page cache uses free memory by design, not by accident

What SSDs Changed

Solid-state drives have no head and no platter, so seek time is essentially zero and random access costs about the same as sequential. Every algorithm above optimises a cost that no longer exists in the same form.

So elevator scheduling stops paying. Linux's default I/O scheduler for NVMe devices is none — a simple queue — because reordering costs CPU and buys nothing, and the device's own controller manages internal parallelism better than the kernel can guess. For rotational media, bfq and mq-deadline remain the right choices.

SSDs introduce constraints of their own instead. Flash cannot overwrite in place: a page must be erased before rewriting, and erases happen in much larger blocks. The flash translation layer hides this by remapping writes and garbage-collecting, and wear levelling spreads writes so no cell dies early. The TRIM command tells the drive which blocks the file system no longer needs, which is what keeps its garbage collection efficient.

The lasting lesson is that the OS optimises for the cost model of the hardware it has. Disk scheduling remains worth understanding both because rotational media still exists in bulk storage, and because it is a clean illustration of ordering work to match physical constraints — the same reasoning appears in network request batching and in cache-friendly memory access patterns.

No seek means reordering buys nothing on NVMe
Linux uses none for NVMe and bfq/mq-deadline for spinning disks
Flash needs erase-before-write, an FTL, and wear levelling
TRIM tells the drive which blocks are genuinely free