Disk Structure and Disk Scheduling

A hard disk stores data on spinning platters. To read a block, the arm first moves the head to the right track (cylinder), then waits for the right sector to rotate under it, then transfers the data.

Access time = seek time + rotational latency + transfer time. At r revolutions per minute, one rotation takes 60 / r seconds, so the average rotational latency is 30 / r seconds.

Since seeks dominate, the OS reorders pending requests to reduce total head movement. (SSDs have no moving parts, so these algorithms matter much less for them.)

The algorithms

Example

Disk cylinders 0 to 199. The head is at 50 and moving towards larger numbers. Pending requests: 82, 170, 43, 140, 24, 16, 190.

head, low, high = 50, 0, 199
requests = [82, 170, 43, 140, 24, 16, 190]

def movement(path):
    return sum(abs(a - b) for a, b in zip(path, path[1:]))

up = sorted(r for r in requests if r >= head)
down = sorted((r for r in requests if r < head), reverse=True)

sstf_path, pos, left = [head], head, requests[:]
while left:
    nxt = min(left, key=lambda r: (abs(r - pos), r))
    sstf_path.append(nxt)
    left.remove(nxt)
    pos = nxt

paths = {
    "FCFS":   [head] + requests,
    "SSTF":   sstf_path,
    "SCAN":   [head] + up + [high] + down,
    "C-SCAN": [head] + up + [high, low] + sorted(down),
    "LOOK":   [head] + up + down,
    "C-LOOK": [head] + up + sorted(down),
}
for name, path in paths.items():
    print(f"{name:6} total movement {movement(path):3}   order {path[1:]}")

FCFS   total movement 642   order [82, 170, 43, 140, 24, 16, 190]
SSTF   total movement 208   order [43, 24, 16, 82, 140, 170, 190]
SCAN   total movement 332   order [82, 140, 170, 190, 199, 43, 24, 16]
C-SCAN total movement 391   order [82, 140, 170, 190, 199, 0, 16, 24, 43]
LOOK   total movement 314   order [82, 140, 170, 190, 43, 24, 16]
C-LOOK total movement 341   order [82, 140, 170, 190, 16, 24, 43]

SSTF looks best here, but it can starve requests at the far end if new nearby requests keep arriving. SCAN and LOOK bound the waiting time; C-SCAN and C-LOOK make it more uniform across cylinders.

GATE-style practice questions