Chapter 35 of 38

Disk Structure & Disk Scheduling

A modern CPU executes billions of instructions per second. A hard disk, in the same second, can perform only about a hundred or so random reads. When eight processes are all waiting for the disk, the order in which the OS serves them can easily double or halve how long everyone waits.

That is the subject of this chapter: what a disk looks like inside, where the time goes in a disk access, and how the OS orders requests to waste as little of that time as possible.

Disk scheduling is the OS's choice of the order in which pending disk I/O requests are served, with the goal of reducing total head movement (seek time) and keeping waiting times fair.

In File Allocation Methods we saw that a file's blocks have disk block numbers. Here we follow those block numbers down to the physical hardware. We will also look at SSDs, RAID, and what Linux actually does today.


Inside a Hard Disk Drive

A hard disk drive (HDD) is a mechanical device:

              spindle (rotates all platters together)
                   |
        ===========|===========   ← platter 0, top surface    (head 0)
                   |                          bottom surface  (head 1)
        ===========|===========   ← platter 1                 (heads 2, 3)
                   |
        ===========|===========   ← platter 2                 (heads 4, 5)
                   |
      <-- arm assembly moves all heads in and out together -->

The vocabulary you must know:

Term

Meaning

Platter

A rigid circular disk coated with magnetic material. A drive has one or more, usually with both surfaces used.

Surface

One side of a platter. Each surface has its own read/write head.

Track

One concentric ring on a surface.

Sector

The smallest addressable piece of a track. Traditionally 512 bytes; modern drives use 4096-byte physical sectors ("Advanced Format").

Cylinder

The set of tracks at the same arm position on all surfaces. Because all heads move together, the whole cylinder can be read without moving the arm.

Arm / head

The arm moves all heads across the surfaces at once. Only one head usually transfers data at a time.

Top view of one surface

          track (a ring)
        .-~~~~~~~~~-.
     .-'  .-~~~~~-.  '-.
    /   .'  .---.  '.   \      sector = one slice of a track
   |   |   | hub |   |   |
    \   '.  '---'  .'   /      outer tracks are longer, so modern drives
     '-.  '-.___.-'  .-'       put more sectors on them ("zoned recording")
        '-._______.-'

Numerical: Disk Capacity

A disk has 4 platters (both surfaces used), 10,000 cylinders, 500 sectors per track and 512 bytes per sector. What is its capacity?

surfaces = 4 × 2 = 8   (so 8 tracks per cylinder)

capacity = surfaces × tracks per surface × sectors per track × bytes per sector
         = 8 × 10,000 × 500 × 512
         = 20,480,000,000 bytes
         = 20.48 GB  (decimal, as drive makers count)  ≈ 19.07 GiB

The difference between 20.48 GB and 19.07 GiB is why a new drive always "looks smaller" in your OS than on the box.

Addressing: CHS and LBA

Old systems addressed a sector by its Cylinder, Head, Sector (CHS) triple. Modern drives instead expose a flat array of sectors numbered 0, 1, 2, ..., called Logical Block Addressing (LBA). The drive's own firmware maps LBAs to physical locations (and quietly remaps bad sectors to spares).

The traditional conversion (sectors numbered from 1, heads and cylinders from 0):

LBA = (C × heads_per_cylinder + H) × sectors_per_track + (S - 1)

Example: 16 heads, 63 sectors per track, C = 2, H = 3, S = 4
LBA = (2 × 16 + 3) × 63 + (4 - 1) = 35 × 63 + 3 = 2208

Reverse:  C = 2208 / (63 × 16) = 2
          H = (2208 / 63) % 16  = 3
          S = (2208 % 63) + 1   = 4

The key fact for scheduling: LBAs are laid out so that nearby block numbers are physically nearby, filling one cylinder before moving to the next. So the OS can treat "distance between block numbers" (or cylinder numbers) as a good estimate of how far the arm must move.


Where the Time Goes: Disk Access Time

To read a sector, three things happen in order:

  1. Seek time: move the arm to the right cylinder. The slowest step, typically a few milliseconds on average.

  2. Rotational latency: wait for the right sector to spin under the head. On average, half a rotation.

  3. Transfer time: actually read the bits as they pass under the head.

Access time = seek time + rotational latency + transfer time

Numerical: One Random 4 KB Read

A 7200 RPM disk has an average seek time of 4 ms and a transfer rate of 200 MB/s. How long does a random 4 KB read take?

One rotation       = 60 s / 7200 = 8.333 ms
Avg rotational lat = 8.333 / 2   = 4.167 ms
Transfer time      = 4096 bytes / (200 × 10^6 bytes/s) = 0.0205 ms

Access time = 4 + 4.167 + 0.0205 ≈ 8.19 ms

Look at that breakdown: more than 99.7% of the time is spent moving parts, and only 0.02 ms is spent actually reading data. That is roughly 1000 / 8.19 ≈ 122 random reads per second. Reading the same data sequentially would run at the full 200 MB/s.

On a hard disk, mechanical movement dominates. The OS cannot make the arm move faster, but it can make it move less. That is what disk scheduling does.

Disk scheduling mainly attacks seek time. (Rotational latency is mostly handled by the drive itself, which reorders requests internally using Native Command Queuing.)


Disk Scheduling Algorithms

Requests arrive from many processes and wait in a queue for the disk (the next chapter, I/O Systems, shows how a request travels from a system call down to the driver). Each request is identified by its cylinder number. The OS picks which one to serve next.

We will use one example for every algorithm so you can compare them directly:

Cylinders:     0 to 199
Head starts at cylinder 70, and was last moving toward higher numbers
Request queue (in arrival order):  120, 35, 180, 90, 10, 150, 65, 195

We measure total head movement in cylinders: the sum of the distances between consecutive positions. All the numbers below were computed with a small Python script.

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

Serve requests in the order they arrived.

Order:  70 → 120 → 35 → 180 → 90 → 10 → 150 → 65 → 195
Moves:     50    85   145    90   80   140    85   130

Total head movement = 805 cylinders
  • Fair: no request waits behind later arrivals. No starvation.

  • Wild swings across the disk: the head goes back and forth, wasting time. Here it averages 805 / 8 ≈ 100.6 cylinders per request.

2. SSTF (Shortest Seek Time First)

Always serve the pending request closest to the current head position.

At 70:  closest is 65 (distance 5)
At 65:  closest is 90 (25)       [35 is 30 away]
At 90:  120 (30)
At 120: 150 (30)
At 150: 180 (30)
At 180: 195 (15)
At 195: 35 (160)
At 35:  10 (25)

Order:  70 → 65 → 90 → 120 → 150 → 180 → 195 → 35 → 10
Moves:     5    25    30     30     30     15    160   25

Total head movement = 320 cylinders
  • Much better than FCFS (320 vs 805).

  • Starvation: SSTF is like SJF scheduling (see SJF & SRTF Scheduling). If new requests keep arriving near the head, a request far away (say at cylinder 10) may wait indefinitely.

  • Not optimal: being greedy at each step does not guarantee the smallest total. Notice it went down to 65 first and then had to come all the way back from 195 to 35. As we will see, SCAN does slightly better on this very example.

3. SCAN (Elevator Algorithm)

The arm moves in one direction serving every request it passes, goes all the way to the end of the disk, then reverses and serves requests on the way back. Exactly like a lift that goes to the top floor and then comes down.

Direction: toward higher cylinders

Order:  70 → 90 → 120 → 150 → 180 → 195 → 199 → 65 → 35 → 10
Moves:     20    30     30     30     15     4    134   30   25

Total head movement = 318 cylinders
   = (199 - 70) + (199 - 10) = 129 + 189 = 318
0  10    35    65 70   90   120   150   180  195 199
|---|-----|-----|--|----|-----|-----|-----|----|--|
                   70 → 90 → 120 → 150 → 180 → 195 → 199 (end)
    10 ← 35 ← 65 ←─────────────────────────────────────┘

Note the shortcut formula when SCAN goes up first: (end - start) + (end - lowest request).

The direction matters. If the head had been moving down instead:

Order:  70 → 65 → 35 → 10 → 0 → 90 → 120 → 150 → 180 → 195
Total head movement = 70 + 195 = 265 cylinders
  • No starvation: every request is reached within at most two sweeps.

  • Wasted travel: going to cylinder 199 when nothing there was requested.

  • Uneven waiting: just after the head passes a region and turns around, the requests at the far end have waited the longest, but the head visits the region it just served again first.

4. C-SCAN (Circular SCAN)

C-SCAN fixes SCAN's uneven waits. The head moves in one direction only, serving requests up to the end. Then it jumps straight back to cylinder 0 without serving anything on the return, and starts the next sweep. The disk is treated as a circle.

Order:  70 → 90 → 120 → 150 → 180 → 195 → 199 → 0 → 10 → 35 → 65
Moves:     20    30     30     30     15     4    199   10   25   30

Total head movement (counting the return jump) = 393 cylinders
Total without the return jump                   = 194 cylinders

Exam warning: textbooks and question papers differ on whether the return jump (199 → 0) counts as head movement. It is real arm movement, but it is fast and serves nothing. Always state your assumption. If the question says nothing, show the total including the jump and mention the other figure.

  • More uniform waiting time: every cylinder is visited once per cycle, at the same interval.

  • More total movement than SCAN in this example, but fairer.

5. LOOK

LOOK is SCAN without the pointless trip to the edge. The head reverses as soon as there are no more requests in the current direction. It "looks" ahead before continuing.

Order:  70 → 90 → 120 → 150 → 180 → 195 → 65 → 35 → 10
Moves:     20    30     30     30     15    130   30   25

Total head movement = 310 cylinders
   = (195 - 70) + (195 - 10) = 125 + 185 = 310

Same order as SCAN, but it turns at 195 instead of 199, saving 8 cylinders (4 up and 4 back).

6. C-LOOK

The circular version of LOOK: go up to the last request, then jump back to the lowest pending request (not to cylinder 0), and continue upward.

Order:  70 → 90 → 120 → 150 → 180 → 195 → 10 → 35 → 65
Moves:     20    30     30     30     15    185   25   30

Total head movement (counting the jump) = 365 cylinders
Total without the jump 195 → 10         = 180 cylinders

Results Side by Side

Algorithm

Service order (from 70)

Total head movement

FCFS

120, 35, 180, 90, 10, 150, 65, 195

805

SSTF

65, 90, 120, 150, 180, 195, 35, 10

320

SCAN (up)

90, 120, 150, 180, 195, (199), 65, 35, 10

318

C-SCAN

90, 120, 150, 180, 195, (199, 0), 10, 35, 65

393 (194 without jump)

LOOK (up)

90, 120, 150, 180, 195, 65, 35, 10

310

C-LOOK

90, 120, 150, 180, 195, 10, 35, 65

365 (180 without jump)

If moving one cylinder took 0.1 ms, FCFS would spend 80.5 ms seeking for these eight requests, and LOOK only 31.0 ms.

Comparing the Algorithms

Algorithm

Idea

Starvation?

Waiting time

Good for

FCFS

Arrival order

No

Fair but long

Light load, SSDs

SSTF

Nearest first

Yes

Low average, high variance

Moderate load

SCAN

Sweep to the end and back

No

Ends wait longer

Heavy load

C-SCAN

Sweep one way, jump back

No

Most uniform

Heavy load, fairness

LOOK

SCAN, turn at last request

No

Like SCAN

Heavy load

C-LOOK

C-SCAN, turn at last request

No

Uniform

Heavy load, fairness

Two observations that surprise students:

  • When the queue is short, the algorithm hardly matters. With only one pending request, every algorithm does the same thing. Scheduling pays off when many requests are waiting.

  • Total head movement is not the only goal. SSTF can give a small total and still starve one request. Real schedulers also enforce deadlines.


What Real Systems Do

Linux I/O Schedulers

Linux's block layer (the multi-queue "blk-mq" design used since kernel 5.0) offers these schedulers per device:

  • mq-deadline: keeps requests sorted by sector (an elevator, like C-LOOK) but also gives each request a deadline (by default 500 ms for reads, 5 s for writes). If a request's deadline expires, it is served next. This prevents SSTF-style starvation. A common default for hard disks.

  • bfq (Budget Fair Queueing): divides disk time fairly between processes, good for interactive desktops on slower drives.

  • kyber: a lightweight scheduler for fast devices that targets latency goals.

  • none: no reordering at all, basically FCFS. The usual choice for NVMe SSDs.

You can see and change the scheduler for each disk. Real output from a WSL Linux machine (kernel 6.18):

cat /sys/block/sdd/queue/scheduler
[none] mq-deadline kyber

The bracketed one is active. (Here the "disk" is a virtual disk provided by Windows, and Windows already schedules the real hardware, so none is sensible. bfq does not appear because its kernel module is not loaded on this machine.)

Solid-State Drives

An SSD stores data in flash memory chips. There is no arm and no spinning platter, so:

  • There is no seek time and no rotational latency. Reading block 10 after block 190 costs the same as reading block 11.

  • Seek-minimising algorithms like SSTF and SCAN bring no benefit, and the reordering itself costs CPU time. That is why Linux uses none (or a light scheduler) for SSDs.

  • NVMe SSDs talk to the CPU over PCIe and support up to 65,535 I/O queues with up to 65,536 commands each, so each CPU core can have its own queue. The drive's controller schedules work across its many flash chips internally.

SSDs have their own quirks that the OS must respect:

  • Flash cannot be overwritten in place. It must be erased first, in large erase blocks. The SSD's firmware (the Flash Translation Layer) writes new data to fresh pages and remaps addresses, similar to how page tables remap virtual addresses.

  • Each flash cell survives a limited number of erase cycles, so the firmware spreads writes evenly (wear leveling).

  • The OS helps by sending TRIM for deleted blocks (see File Allocation Methods).

HDD

SSD

Moving parts

Yes (platters, arm)

None

Random read latency

Milliseconds

Tens of microseconds

Sequential vs random

Huge difference

Much smaller difference

Disk scheduling for seeks

Very useful

Not useful

Overwrite in place

Yes

No (erase first)

Wear out from writes

Not a main concern

Yes, managed by wear leveling

Cost per GB

Lower

Higher

HDDs are still used where capacity per rupee matters: backup servers, cloud storage, surveillance recorders.


Preparing a Disk for Use

A brand-new disk goes through three steps before it holds files:

  1. Low-level (physical) formatting: divides the surfaces into sectors with headers and error-correcting codes (ECC). Done at the factory.

  2. Partitioning: divides the disk into one or more regions, each treated as a separate disk. The partition table is either the old MBR (at most 4 primary partitions; 32-bit sector numbers limit it to 2 TiB with 512-byte sectors) or the modern GPT (128 partitions by default, 64-bit addresses), used with UEFI firmware.

  3. Logical formatting: creates a file system in a partition, writing the superblock, free-space maps, inode table and root directory (see File Systems). On Linux this is mkfs; on Windows, "Format".

The disk also needs a boot block: the firmware loads a small bootstrap program from a known place (the MBR's first sector, or a file in the EFI system partition with GPT), which then loads the OS kernel.

Bad blocks are sectors that fail. Modern drives keep spare sectors and transparently remap a failing sector to a spare (sector sparing). The OS only sees errors when the spares run out, which is a sign to replace the drive.


RAID: Many Disks Working as One

One disk can fail and can only go so fast. RAID (Redundant Array of Independent Disks) combines several disks to improve reliability, performance, or both. Two basic tricks:

  • Striping: split data across disks so they work in parallel (speed).

  • Redundancy: keep mirror copies or parity so data survives a disk failure (reliability).

Level

How it works

Usable capacity (n disks)

Survives

Notes

RAID 0

Striping only

n

No failures

Fastest; one disk dies, all data is lost

RAID 1

Mirroring: same data on every disk

1 disk's worth

n - 1 failures

Simple, fast reads, expensive

RAID 5

Striping with one parity block per stripe, spread over all disks

n - 1

1 failure

Needs at least 3 disks; small writes are costly

RAID 6

Like RAID 5 with two independent parity blocks

n - 2

2 failures

Needs at least 4 disks

RAID 10 (1+0)

Mirrored pairs, striped together

n / 2

1 per mirrored pair

Fast and reliable, popular for databases

Example: four 2 TB disks give 8 TB usable with RAID 0, 6 TB with RAID 5, and 4 TB with RAID 6 or RAID 10.

How Parity Recovers Data

RAID 5 parity is just XOR. For one stripe across three data disks:

D1 = 1011
D2 = 0110
D3 = 1100
P  = D1 XOR D2 XOR D3 = 0001

Disk 2 fails. Rebuild D2 from the others:
D2 = D1 XOR D3 XOR P = 1011 XOR 1100 XOR 0001 = 0110   ✓

XOR works because x XOR x = 0: XOR-ing all the surviving pieces cancels everything except the missing one. The price: every small write must update the parity too (read old data and old parity, write new data and new parity).

RAID is not a backup. It protects against a disk dying, not against deleting a file by mistake, ransomware, or a fire. A deleted file is deleted on every disk at once.


Common Mistakes

  • Adding the initial head position as a request. The head's starting cylinder is where you begin measuring, not something to serve.

  • Going to the disk edge in LOOK, or not going to it in SCAN. SCAN goes to the end (0 or the last cylinder); LOOK turns at the last request.

  • Ignoring the direction. SCAN and LOOK answers depend on the direction the head is moving. Read the question carefully.

  • Not stating the C-SCAN/C-LOOK return-jump convention. Write both totals or state your assumption.

  • Thinking SSTF is optimal. It is greedy. In our example SCAN (318) and LOOK (310) both beat SSTF (320).

  • Using full rotation time for rotational latency. The average is half a rotation.

  • Applying HDD scheduling logic to SSDs. SSDs have no seek time.

  • Treating RAID as a backup.


Interview Questions

What are the components of disk access time?

Seek time (moving the arm to the cylinder), rotational latency (waiting for the sector to rotate under the head, on average half a rotation) and transfer time.

What is a cylinder?

The set of tracks at the same arm position across all surfaces. Data on one cylinder can be read without moving the arm.

What is the average rotational latency of a 7200 RPM disk?

One rotation takes 60/7200 s = 8.33 ms, so the average latency is half of that, about 4.17 ms.

Why can SSTF cause starvation?

It always chooses the nearest request, so if new requests keep arriving near the head, a request far away may never be chosen.

Difference between SCAN and LOOK?

SCAN travels to the end of the disk before reversing; LOOK reverses as soon as no requests remain in the current direction.

Why is C-SCAN fairer than SCAN?

It serves requests in one direction only and jumps back to the start, so every cylinder waits about the same time between visits; SCAN serves the middle more often than the ends.

Do SSDs need disk scheduling?

Not for seek reduction, since they have no moving parts. Linux usually uses the "none" scheduler for NVMe SSDs; schedulers may still be used for fairness or latency goals.

What does Linux's mq-deadline scheduler do?

It sorts requests by sector to reduce seeking but also assigns each request an expiry time, serving expired requests first so none starve.

RAID 5 vs RAID 10?

RAID 5 uses distributed parity: more usable space (n-1 disks) but slow small writes and long rebuilds. RAID 10 mirrors and stripes: only half the space but fast writes and rebuilds.


The Main Idea

HDD          → platters, surfaces, tracks, sectors, cylinders, one moving arm
Access time  → seek + rotational latency (half a turn) + transfer
FCFS         → arrival order; fair but long seeks
SSTF         → nearest first; short seeks, can starve
SCAN         → elevator to the end and back
C-SCAN       → one direction, jump back; uniform waits
LOOK/C-LOOK  → like SCAN/C-SCAN but turn at the last request
Linux        → mq-deadline, bfq, kyber, none (none for NVMe)
SSD          → no seeks; FTL, wear leveling, TRIM
RAID         → striping + mirroring/parity; not a backup

A hard disk spends almost all its time moving. Disk scheduling exists to make it move less, while making sure no request is forgotten.

Disks are just one kind of device. In the next chapter, I/O Systems, we zoom out to see how the OS talks to all hardware devices, using controllers, interrupts, DMA and device drivers.