A magnetic disk is a stack of PLATTERS, each with two surfaces, each surface divided into concentric TRACKS, each track into SECTORS. PLATTER one physical disc SURFACE one side of a platter (2 per platter) TRACK one concentric ring on one surface CYLINDER the same track number on ALL surfaces — reachable without moving the arm, which is why it is the unit that matters SECTOR the smallest addressable unit (512 B or 4096 B) HEAD one read/write head per surface, all on one arm THE KEY INSIGHT ABOUT CYLINDERS: all heads move together on a single arm, so every track at the same radius is accessible with NO additional seek. Placing a file's blocks in one cylinder rather than one track therefore multiplies the data reachable per seek by the number of surfaces. CAPACITY CALCULATION — a standard numerical: capacity = cylinders × surfaces × sectors_per_track × bytes_per_sector WORKED: 16,383 cylinders, 16 heads, 63 sectors/track, 512 B = 16383 × 16 × 63 × 512 = 8,455,200,768 bytes ≈ 7.87 GiB (These are the classic CHS limits — 1024/16/63 gave the famous 504 MB barrier, and 16383/16/63 the ~8 GB one. Modern drives abandoned CHS for LBA precisely because the geometry became a fiction.) ACCESS TIME — three components, and only one is under software control: access time = SEEK TIME + ROTATIONAL LATENCY + TRANSFER TIME SEEK TIME move the arm to the right cylinder typically 3–12 ms — THE DOMINANT COST → this is what disk scheduling minimises ROTATIONAL wait for the sector to arrive under the head LATENCY average = half a revolution 7200 rpm → 60/7200 = 8.33 ms per rev → avg latency 4.17 ms 15000 rpm → 4 ms per rev → avg 2 ms TRANSFER TIME read the bytes = bytes / transfer_rate, often microseconds WORKED: 7200 rpm, 5 ms average seek, 100 MB/s transfer, reading 4 KB seek = 5.00 ms rotational = 4.17 ms transfer = 4096 / 100e6 = 0.04 ms TOTAL ≈ 9.21 ms NOTE THE PROPORTIONS: the transfer is 0.4% of the total. Over 99% of the time is spent GETTING to the data. That single fact explains every optimisation in this topic — and why reading 1 MB sequentially costs barely more than reading 4 KB. LOGICAL BLOCK ADDRESSING (LBA): the OS sees a flat array of block numbers 0..N−1 and the drive maps them to physical geometry internally. Consecutive LBAs are placed physically adjacently, which is why sequential access is fast even though the OS knows nothing about cylinders.

REQUEST QUEUE (the standard textbook example): 98, 183, 37, 122, 14, 124, 65, 67 head starts at cylinder 53, disk has cylinders 0–199 All totals below were COMPUTED. 1. FCFS — serve in arrival order order: 98 183 37 122 14 124 65 67 total head movement = 640 cylinders ✔ fair, trivially simple ✗ WORST performance — the head thrashes back and forth (53→98→183→37 alone is 235 cylinders) 2. SSTF — shortest seek time first order: 65 67 37 14 98 122 124 183 total = 236 cylinders ✔ much better than FCFS (63% less movement) ✗ STARVATION: a request at the far edge can be postponed indefinitely while nearby requests keep arriving ✗ not optimal, despite being greedy 3. SCAN (elevator) — sweep to one end, then reverse order: 65 67 98 122 124 183 199 37 14 total = 331 cylinders ✔ NO starvation — every request is served within one sweep ✔ predictable, bounded waiting ✗ worse than SSTF here (331 vs 236), because it travels to cylinder 199 with nothing to do there 4. C-SCAN (circular SCAN) — sweep one way only, then jump back order: 65 67 98 122 124 183 199 0 14 37 total = 382 cylinders ✔ UNIFORM waiting time — cylinders at both edges are treated identically, unlike SCAN where the reversal point is favoured ✗ highest movement here, because of the full return sweep 5. LOOK / C-LOOK — like SCAN/C-SCAN but reverse at the LAST REQUEST rather than at the physical end of the disk order: 65 67 98 122 124 183 37 14 total = 299 cylinders ✔ strictly better than SCAN (299 vs 331) — it never travels to 199 for nothing ✔ keeps SCAN's no-starvation property → LOOK is what real elevator schedulers actually do; "SCAN" in a textbook usually means LOOK in an implementation SUMMARY: FCFS 640 simple, fair, terrible SSTF 236 best movement, can starve LOOK 299 good movement, no starvation ← the practical choice SCAN 331 no starvation, wasted travel C-SCAN 382 most uniform waiting, most movement THE TRADE is between total movement and fairness. SSTF wins on throughput and can starve; the SCAN family bounds waiting time and pays for it in travel.

/* 78 MB file, 20,000 blocks of 4 KB, read sequentially then in
   random order. Verified on this machine's SSD. */
int fd = open("big.dat", O_CREAT|O_RDWR|O_TRUNC, 0644);
for (int i = 0; i < NBLK; i++) write(fd, buf, BLK);
fsync(fd);

/* sequential */
lseek(fd, 0, SEEK_SET);
for (int i = 0; i < NBLK; i++) read(fd, buf, BLK);

/* random */
for (int i = 0; i < NBLK; i++) {
    off_t off = (off_t)(rand() % NBLK) * BLK;
    pread(fd, buf, BLK, off);
}
MEASURED OUTPUT:
  file size          : 78 MB (20000 blocks of 4096 B)
  sequential read    : 8.9 ms  (8730 MB/s)
  random read        : 10.5 ms (7474 MB/s)
  random is 1.17x slower

1.17× — and that number changes the whole topic. ON A SPINNING DISK, random 4 KB reads cost a seek plus rotational latency EACH: sequential: ~100 MB/s random 4 KB: ~9.2 ms per block = 0.43 MB/s → roughly 230× SLOWER ON THIS SSD: 1.17× slower. There is no arm to move, so "seeking" is just a different address on a flash chip. (Note both figures here exceed the drive's raw speed — 8730 MB/s is the PAGE CACHE, since the 78 MB file fits comfortably in RAM. That is itself the point of the next topic: the cache is doing most of the work. The RATIO between sequential and random is still meaningful, because both paths are cached equally.) WHAT THIS MEANS FOR THE ALGORITHMS ABOVE: · DISK SCHEDULING IS NEARLY POINTLESS on SSDs. Reordering requests to minimise head movement optimises a cost that no longer exists. Linux's recommended scheduler for NVMe is `none`. · SSDs handle many requests IN PARALLEL (NVMe supports 65,536 queues), so serialising them into a sweep actively HURTS. Depth matters more than order. · what still matters: REQUEST SIZE (one 1 MB read beats 256 separate 4 KB reads) and ALIGNMENT to the erase block. WHAT STILL MATTERS EVEN ON SSDs: · SEQUENTIAL IS STILL FASTER, just by 1.17× rather than 230× · large requests amortise per-request overhead · the FILE SYSTEM's block placement still affects how many requests are needed · write amplification and TRIM (from the fragmentation topic) So the classical algorithms are now history for NVMe and still current for the spinning disks in archival storage and for the conceptual point: minimise the number of expensive operations, whatever "expensive" means on your hardware.