Disk Scheduling

The Elevator Algorithm

A building elevator serves floors in requests that arrive in random order: 3, 12, 1, 8, 15, 5. If the elevator goes floor 3, then 12, then back to 1, then 8, then 15, then 5 — it wasses enormous time traveling up and down. An intelligent elevator instead sweeps upward, stopping at every requested floor on the way up, then sweeps back down. Fewer total floors traveled, same requests served.

Hard disk drives work on the same principle. The read/write head must physically move to the requested track before data can be read or written. This movement — called a seek — takes time. Disk scheduling algorithms minimize the total seek distance, which directly reduces disk latency and improves throughput.

HDD Structure: Why Head Movement Matters

A traditional Hard Disk Drive (HDD) consists of:

• Platters: Spinning magnetic disks (typically 7,200 RPM)
• Tracks: Concentric circles on each platter surface
• Sectors: Fixed-size units within a track (typically 512 bytes or 4 KB)
• Read/Write Head: Moves radially across the platter surface to reach different tracks
• Cylinder: The set of tracks at the same radial position across all platters

Seek time is the time to move the head to the target track. It is the dominant latency in HDD operations — typically 3–15 ms per seek. Rotational latency (waiting for the sector to spin under the head) adds another 0–8 ms at 7,200 RPM.

Total access time = Seek time + Rotational latency + Transfer time

Scheduling algorithms focus on minimizing seek time by ordering the request sequence intelligently.

The Test Queue

All algorithms demonstrated on:

Request queue (track numbers): [98, 183, 37, 122, 14, 124, 65, 67]

Initial head position: 53

Track range: 0–199

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

Policy: Service requests in arrival order. Simple, no reordering.

Order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Movement: |53-98|+|98-183|+|183-37|+|37-122|+|122-14|+|14-124|+|124-65|+|65-67|
        =   45  +   85   +   146  +   85   +   108  +   110  +   59   +  2
        = 640 tracks

Total head movement: 640 tracks

Problem: The head jumps back and forth across the disk wildly. Request at 37 is served after 183, requiring a 146-track backtrack. This is grossly inefficient.

2. SSTF (Shortest Seek Time First)

Policy: Always service the request closest to the current head position. Greedy algorithm.

Trace (head starts at 53):

• 53 → 65 (distance 12)
• 65 → 67 (distance 2)
• 67 → 37 (distance 30)
• 37 → 14 (distance 23)
• 14 → 98 (distance 84)
• 98 → 122 (distance 24)
• 122 → 124 (distance 2)
• 124 → 183 (distance 59)

Total: 12+2+30+23+84+24+2+59 = 236 tracks

Starvation problem: Requests far from the current head may wait indefinitely if nearby requests keep arriving. Track 183 is served last; if new requests near track 50–100 kept arriving, track 183 could starve.

3. SCAN (Elevator Algorithm)

Policy: The head moves in one direction, servicing all requests along the way, until it reaches the end of the disk (or the last request in that direction), then reverses direction.

Trace (head at 53, moving toward higher tracks):

• 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (end) → reverses
• 199 → 37 → 14

Movement: |53→199| + |199→14|
         = 146 + 185 = 331 tracks

Wait — only service requests, not traverse the full disk if no request exists at the end. Let's recalculate properly:

• 53 → 65 → 67 → 98 → 122 → 124 → 183 (highest request, reverse here)
• 183 → 37 → 14

Movement: (183-53) + (183-14) = 130 + 169 = 299 tracks

SCAN eliminates starvation — every request is eventually reached as the head sweeps back. No request waits longer than two full sweeps.

4. C-SCAN (Circular SCAN)

Policy: Head moves in one direction, services requests, reaches the end, then jumps back to the beginning without servicing and sweeps again. Provides more uniform waiting times.

Trace (head at 53, moving toward higher tracks):

• 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (jump to 0) → 14 → 37

Movement: (199-53) + (199-0) + (37-0) = 146 + 199 + 37 = 382 tracks

More total movement than SCAN, but requests at the low end never wait for the head to service the entire upper half before reaching them.

5. LOOK

Policy: Like SCAN, but the head only goes as far as the last request in each direction, not to the physical end of the disk.

Trace (head at 53, moving toward higher tracks):

• 53 → 65 → 67 → 98 → 122 → 124 → 183 (last request, reverse)
• 183 → 37 → 14

Movement: (183-53) + (183-14) = 130 + 169 = 299 tracks

LOOK is typically the same as SCAN when the last request does not happen to be at track 0 or 199.

6. C-LOOK

Policy: Like C-SCAN, but jumps only to the lowest-numbered pending request, not to track 0.

Trace (head at 53, moving toward higher tracks):

• 53 → 65 → 67 → 98 → 122 → 124 → 183 (jump to lowest pending: 14) → 14 → 37

Movement: (183-53) + (183-14) + (37-14) = 130 + 169 + 23 = 322 tracks

Algorithm Summary on [98,183,37,122,14,124,65,67], Head=53

SSDs: Why Disk Scheduling Matters Less

Solid State Drives (SSDs) have no moving parts. There is no read/write head, no spinning platter, no seek time. Any location is accessed in approximately the same time (50–100 microseconds for NVMe SSDs vs 5–15 ms for HDDs).

For SSDs, disk scheduling algorithms provide little benefit. The OS still queues requests, but ordering them for seek minimization is irrelevant. Modern Linux uses the mq-deadline or none schedulers for SSDs and reserves SCAN-based algorithms (CFQ, BFQ) for HDDs.

The scheduling algorithm matters enormously for HDDs (still common in data centers, NAS, and budget PCs) and is a classic topic in OS design.

Summary

Disk scheduling reduces HDD access time by minimizing total head movement:

• FCFS: Simple, fair, inefficient — wild head movement
• SSTF: Greedy minimum seek — risk of starvation
• SCAN/LOOK: Elevator sweep — good balance of efficiency and fairness
• C-SCAN/C-LOOK: Uniform waiting times — best for equal-priority workloads

As SSDs replace HDDs, the practical importance of disk scheduling shrinks — but the concepts remain foundational to understanding storage I/O performance and system design.