03. Disk Geometry & Arm Scheduling

For over five decades, magnetic Hard Disk Drives (HDDs) served as the primary secondary storage substrate in computer systems. While modern operating systems increasingly boot from solid-state flash memory, understanding mechanical disk geometry and head scheduling remains essential for studying physical latency modeling, mechanical movement optimization, and sequential data locality.

1. Physical Disk Geometry: Platters, Cylinders, and Sectors

For over half a century, the magnetic hard disk drive (HDD) served as the primary secondary storage substrate in computing. Although solid-state flash drives (SSDs) have surpassed magnetic disks in random transaction performance, mechanical disk drives remain the dominant medium for massive, exabyte-scale datacenter storage due to their favorable cost-per-terabyte profile.

From an operating system engineering perspective, magnetic disks provide a textbook case study in mechanical latency modeling, asymmetric access costs, and physical resource scheduling. To write efficient filesystem and buffer cache algorithms, kernel developers must understand the microscopic electro-mechanical physics governing disk hardware.

Anatomy of the Mechanical Hard Disk

A modern hard disk drive is an ultra-precise, hermetically sealed unit containing several key mechanical and magnetic subsystems:

The Geometry Hierarchy: Tracks, Cylinders, and Sectors

Data recorded on platters is organized along three geometric dimensions:

• Tracks: Data is recorded along concentric circular rings called tracks. Unlike a vinyl phonograph record or an optical compact disc (which use a single continuous spiral), magnetic disk tracks are closed, discrete circles.
  Track density is extraordinarily high, often exceeding 300,000 to 500,000 Tracks Per Inch (TPI). The width of an individual magnetic track is less than 50 nanometers!
• Cylinders: The actuator arm moves all read/write heads simultaneously across all platter surfaces. The collection of all tracks across every platter surface situated at the identical radial arm distance forms an imaginary geometric vertical tube called a Cylinder:
  The Cylinder Optimization Principle:
  If a file spans multiple blocks, placing those blocks on the same cylinder across different platter surfaces allows the drive to switch from reading Head 0 to Head 1, 2, or 3 via purely electronic head-selection logic (consuming less than 0.5 milliseconds) without executing any physical, mechanical voice-coil movement!
• Sectors: A track is partitioned into discrete arc segments called sectors. The sector is the smallest unit of physical storage and transfer that the disk controller can read or write atomically:
  • Legacy Standard (512-Byte Sectors): Historically, sectors stored exactly 512 bytes of user data.
  • Advanced Format (4Kn / 4096-Byte Sectors): Modern drives use 4 KB physical sectors. A 4096-byte sector reduces the overhead of inter-sector gaps and preambles, and significantly increases error-correction efficiency by providing larger data blocks for modern Low-Density Parity-Check (LDPC) error-correction codes.

The Evolution of Addressing: From CHS to Logical Block Addressing (LBA)

1. Cylinder-Head-Sector (CHS) Addressing & Historical Barriers

In early operating systems (such as MS-DOS and early Unix on IBM PCs), the kernel had to explicitly calculate and provide the 3-dimensional physical coordinates for every disk operation:

/* Historical CHS Access: Read Cylinder 20, Head 2, Sector 5 */
struct chs_address {
    uint16_t cylinder; /* 0 .. 1023 (10 bits) */
    uint8_t  head;     /* 0 .. 15 (4 bits)   */
    uint8_t  sector;   /* 1 .. 63 (6 bits - 1-indexed!) */
};

CHS addressing contained a fatal flaw: the combination of BIOS register limitations (10 bits for cylinders, 4 bits for heads, 6 bits for sectors) created the notorious 504 MiB Barrier:

2. Zoned Bit Recording (ZBR / Zone CAV)

Beyond the BIOS architectural limits, CHS was destroyed by basic physics: rigid geometry is geometrically inefficient.

Because a disk platter is circular, the circumference of an outer track is more than twice the circumference of an inner track:

Under historical CHS, every track was forced to contain the exact same number of sectors (e.g. 63 sectors per track). This meant magnetic bit transitions on outer tracks were spaced far apart, wasting massive amounts of surface area.

Modern drives implement Zoned Bit Recording (ZBR):

• The disk surface is grouped into 16 to 30 concentric zones.
• Outer zones (with larger radii) pack significantly more sectors per track (e.g. 1,200 sectors per track) than inner zones (e.g. 600 sectors per track), maintaining a uniform magnetic recording density across the entire platter.
• Operating System Performance Consequence: Because the spindle motor rotates at a constant angular speed, outer tracks pass beneath the read/write heads faster, streaming data at more than double the throughput of inner tracks (e.g. 260 MB/s on outer tracks vs. 120 MB/s on inner tracks)! Operating system partition formatters deliberately place root filesystems and high-performance swap partitions on the outer edge of the disk.

3. Logical Block Addressing (LBA) & Controller Virtualization

Because Zoned Bit Recording destroyed uniform CHS dimensions, the storage industry transitioned universally to Logical Block Addressing (LBA):

• The operating system completely abandons tracking cylinders, heads, and tracks.
• The disk controller exposes the disk as a flat, linear array of 64-bit integer blocks:

  LBA 0, LBA 1, LBA 2, LBA 3, …, LBA (TotalSectors - 1)

• The on-board disk controller firmware maintains an internal mathematical mapping table, translating logical LBA numbers to physical zones, cylinders, heads, and physical sectors.

Physical Latency Mitigations: Track and Cylinder Skewing

To prevent catastrophic rotational latency penalties during sequential reads, disk controllers implement microscopic angular offsets known as skewing:

2. Modeling I/O Access Latency (T_I/O)

To an operating system kernel, secondary storage operations are enormously expensive compared to register and cache access. Reading a block of data from main DRAM requires tens of nanoseconds, whereas reading a block from a mechanical hard disk requires millions of nanoseconds.

To design effective disk scheduling algorithms and filesystem page caches, we must construct a rigorous mathematical latency model decomposed into its physical and electronic sub-components:

1. Seek Time (T_seek): The Voice-Coil Mechanics

Seek time is the physical delay required for the voice-coil actuator arm to position the read/write heads radially across the platters and align precisely over the target cylinder.

An actuator movement is not an instantaneous, uniform velocity slide. The voice-coil motor must obey classical Newtonian mechanics across four distinct physical phases:

1. Acceleration Phase: Maximum electrical current is driven through the coil, creating an intense magnetic field against the permanent rare-earth magnets to accelerate the mass of the arm.
2. Coasting Phase: For long seeks across hundreds of cylinders, the arm reaches its maximum terminal velocity and coasts across the platter radius.
3. Deceleration Phase: Reverse current is applied through the voice coil, exerting braking force to bring the high-speed arm to a controlled stop over the target cylinder.
4. Head Settling Time: The heads vibrate slightly upon arrival. The closed-loop servo mechanism reads embedded magnetic servo bursts to dampen oscillations and settle the head within the target track boundary (a mechanical settling budget of 0.5 to 1.5 milliseconds).

2. Rotational Latency (T_rotational): Platter RPM Physics

Once the voice-coil arm settles precisely over the target cylinder, the read head cannot immediately begin reading data. The target sector may currently be on the opposite side of the rotating platter. The time required for the target sector to rotate underneath the read head is the Rotational Latency.

Because disk platters rotate at a strict Constant Angular Velocity (CAV) measured in Revolutions Per Minute (RPM), the period of one complete physical revolution (T_rev) is constant:

Assuming random access, the target sector may arrive immediately beneath the head (best case: 0 ms), or it may have just passed the head by a fraction of a millimeter (worst case: one full physical revolution, T_rev).
Under a uniform distribution, the Average Rotational Latency (T_{rot (avg)}) is exactly half a revolution:

3. Transfer Time (T_transfer) & Controller Overhead

Once the head settles over the cylinder and the target sector rotates underneath, the drive enters the Transfer Phase.

• Media Transfer Time: The time required for the sector's magnetic bits to sweep past the TMR sensor:
  T_transfer = ^{Transfer Size (Bytes)}⁄_{Internal Track Media Transfer Rate (Bytes/sec)}
  For a standard 4 KB (4,096 bytes) block read on an outer track streaming at 200 MB/s:
  T_transfer = ^{4,096 Bytes}⁄_{200,000,000 Bytes/sec} ≈ 0.0000205 seconds = 0.02 ms
• Controller Overhead (T_controller): The electronic setup time required for the controller's ASIC to decode commands, program DMA registers, verify ECC checksums, and trigger host interrupts (typically < 0.02 milliseconds).

The 500× Asymmetry: Random vs. Sequential Performance

We can now calculate the catastrophic performance penalty of random I/O versus sequential streaming on a modern 7,200 RPM mechanical drive:

3. Disk Arm Scheduling Algorithms

In a multiprogramming operating system, dozens of processes issue concurrent reads and writes to storage. Because mechanical seek time and rotational delay dwarf electronic transfer speeds by over 500 to 1, the order in which pending disk requests are serviced directly dictates overall system throughput and interactive responsiveness.

When an application issues a file read, the operating system block layer enqueues the request into a kernel dispatch queue. The Disk Arm Scheduler (or I/O elevator) reorders, merges, and dispatches pending requests to optimize physical head trajectory.

The Dual Mandate of the Disk Arm Scheduler

An effective disk scheduler must balance two fundamentally competing objectives:

1. Throughput Maximization: Squeezing the maximum number of megabytes per second out of the physical platters. This requires minimizing aggregate seek distance and reducing the frequency of head turnaround reversals:
   Total Seek Cost = ∑_i=1^K | Cylinder_i - Cylinder_i-1 |
2. Fairness & Bounded Latency: Ensuring that no single I/O request starves in the queue indefinitely while the arm services requests closer to the active cylinder cluster.

Detailed Algorithmic Analysis

1. First-Come, First-Served (FCFS)

The baseline scheduling policy services requests strictly in the chronological order of their arrival into the queue:

• Advantages: Completely fair; zero starvation; trivial O(1) FIFO queue implementation.
• The Defect — Wild Head Thrashing: FCFS pays zero attention to spatial locality. If Process A requests an inner cylinder (Cylinder 14) and Process B requests an outer cylinder (Cylinder 183), the arm thrashes back and forth across the entire platter width.
  On our classical benchmark workload, FCFS generates 640 cylinders of head movement, operating at less than one-third the throughput of an elevator scheduler.

2. Shortest Seek Time First (SSTF)

SSTF applies a greedy heuristic: among all pending requests in the queue, it selects the request that requires the minimum physical seek distance from the current head position:

• Performance: Slashes head travel from 640 cylinders down to 236 cylinders, dramatically increasing throughput under low-to-medium loads.
• The Fatal Flaw — Pathological Starvation: Because SSTF is greedy, it favors requests clustered near the current cylinder. If an application continuously generates requests around Cylinders 50–70, the head lingers in that cluster indefinitely.
  A request pending on Cylinder 183 will starve forever as long as new requests arrive in the local neighborhood! For this reason, pure SSTF is never deployed in general-purpose production operating systems.

3. SCAN (The Elevator Algorithm)

To eliminate starvation while preserving spatial locality, the SCAN algorithm mimics a commercial building elevator:

• The arm maintains a directional vector (e.g. Moving Outward toward Cylinder 199).
• The head sweeps continuously in that direction, servicing all pending requests encountered along its path.
• When the arm reaches the extreme cylinder of the disk (Cylinder 199), the arm reverses direction and begins sweeping inward toward Cylinder 0, servicing requests in reverse.
• Starvation Bound: A request is guaranteed to be serviced in at most two full sweeps of the platter radius, permanently eliminating starvation.
• The SCAN Defect — Non-Uniform Waiting Distribution: SCAN suffers from an asymmetric waiting time distribution. When the arm passes Cylinder 50 heading right, the area directly behind it (Cylinders 0–49) has just been cleared of requests.
  A new request arriving at Cylinder 48 must wait for the arm to travel all the way to 199, reverse, and sweep back down to 48—a wait of nearly two full disk strokes! In contrast, requests ahead of the advancing arm experience negligible wait times.

4. C-SCAN (Circular SCAN)

C-SCAN corrects the non-uniform wait distribution of SCAN by restricting servicing to a single sweep direction:

• The arm sweeps in one direction only (e.g. from lowest cylinder toward highest cylinder), servicing requests along the way.
• Upon reaching the outer extreme (Cylinder 199), the arm immediately performs a high-speed return jump back to Cylinder 0 without servicing any requests on the return journey!
• Once reset to Cylinder 0, it resumes its forward sweep.
• Mathematical Fairness: By treating the cylinders as a circular ring, C-SCAN provides a mathematically uniform average waiting time for all cylinders across the platter surface.

5. LOOK and C-LOOK (Industrial Optimizations)

Standard SCAN and C-SCAN waste significant mechanical travel by driving the arm all the way to the absolute physical edge of the disk (Cylinder 0 and Cylinder 199) even when no requests are pending at those extreme boundaries.

LOOK and C-LOOK add a forward-inspection lookahead:

• The arm advances in its current direction only as far as the highest pending request in the queue.
• In our benchmark workload, the highest pending request is Cylinder 183. LOOK reverses immediately at 183; it never wastes mechanical motion traveling to the unused Cylinder 199.
• Similarly, C-LOOK executes its circular return jump immediately upon completing Cylinder 183, jumping directly to the lowest pending request (Cylinder 14) rather than Cylinder 0.
• C-LOOK is the universal gold standard for rotational mechanical arm scheduling in production systems.

Modern Operating System Scheduling Architectures

In modern Linux and Windows kernels, disk scheduling has moved beyond pure geometric heuristics to address quality-of-service and hardware-offloaded queues:

Algorithm Analysis & Comparisons