Disk Scheduling Algorithms

By the end of this lesson you will be able to calculate total head movement for the six classic disk scheduling algorithms, explain the trade-offs between them, and say what Linux does for SSDs today.

Hard disks are mechanical. Before reading any data, an arm must move the read/write head to the right track. That movement is slow compared with everything else in a computer, so the order in which the OS sends read and write requests to the disk can change performance a lot.

How a hard disk reads data

A hard disk drive (HDD) has spinning platters covered in circular tracks. The set of tracks at the same position on every platter is a cylinder. One arm assembly moves all the heads together.

Reading a block takes three parts:

1. Seek time: moving the arm to the right cylinder. Usually the biggest part, several milliseconds.
2. Rotational latency: waiting for the right sector to spin under the head. On average, half a rotation.
3. Transfer time: actually reading the bits, which is quick.

Disk scheduling tries to reduce total seek time by choosing a good order for pending requests. Exam questions measure this as the total head movement in cylinders.

A good everyday picture is a lift in a tall office building in Gurugram. People on many floors press buttons. A lift that serves calls strictly in the order they were pressed would race up and down wastefully. Real lifts sweep in one direction, picking people up on the way. Most disk algorithms copy that idea.

The example

The disk has cylinders 0 to 199. The head is at cylinder 96, and it was last moving towards higher numbers. The queue of requests, in arrival order, is:

140, 30, 172, 85, 12, 110, 63, 190

Step 1: run all six algorithms. The function total adds up the distance between each pair of positions in the path.

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

def fcfs(head, reqs):
    return [head] + reqs

def sstf(head, reqs):
    path, left = [head], list(reqs)
    while left:
        nxt = min(left, key=lambda r: (abs(r - path[-1]), r))   # closest; ties -> lower
        left.remove(nxt); path.append(nxt)
    return path

def scan(head, reqs, max_cyl):          # moving towards higher numbers first
    up = sorted(r for r in reqs if r >= head)
    down = sorted((r for r in reqs if r < head), reverse=True)
    return [head] + up + [max_cyl] + down

def cscan(head, reqs, max_cyl):
    up = sorted(r for r in reqs if r >= head)
    low = sorted(r for r in reqs if r < head)
    return [head] + up + [max_cyl, 0] + low

def look(head, reqs):
    up = sorted(r for r in reqs if r >= head)
    down = sorted((r for r in reqs if r < head), reverse=True)
    return [head] + up + down

def clook(head, reqs):
    up = sorted(r for r in reqs if r >= head)
    low = sorted(r for r in reqs if r < head)
    return [head] + up + low

head, queue, MAX = 96, [140, 30, 172, 85, 12, 110, 63, 190], 199
for name, path in [("FCFS", fcfs(head, queue)), ("SSTF", sstf(head, queue)),
                   ("SCAN", scan(head, queue, MAX)), ("C-SCAN", cscan(head, queue, MAX)),
                   ("LOOK", look(head, queue)), ("C-LOOK", clook(head, queue))]:
    print(f"{name:6} {total(path):4} cylinders  {path}")

FCFS    728 cylinders  [96, 140, 30, 172, 85, 12, 110, 63, 190]
SSTF    262 cylinders  [96, 85, 63, 30, 12, 110, 140, 172, 190]
SCAN    290 cylinders  [96, 110, 140, 172, 190, 199, 85, 63, 30, 12]
C-SCAN  387 cylinders  [96, 110, 140, 172, 190, 199, 0, 12, 30, 63, 85]
LOOK    272 cylinders  [96, 110, 140, 172, 190, 85, 63, 30, 12]
C-LOOK  345 cylinders  [96, 110, 140, 172, 190, 12, 30, 63, 85]

Now go through each algorithm and check the numbers yourself.

FCFS

Serve requests in arrival order. Fair and simple, but the head swings wildly: 96 to 140 (44), to 30 (110), to 172 (142), and so on, for a total of 728.

SSTF: shortest seek time first

Always go to the pending request closest to the current head position. From 96, the nearest is 85 (11 away), then 63, 30, 12, and then all the way up. Total 262, the lowest here.

SSTF is like SJF scheduling for the disk, and it has the same weakness: starvation. If new requests keep arriving near the head, a far request can wait for ever.

head, pending = 50, [190]                       # one far-away request is waiting
arrivals = [48, 53, 47, 52, 49, 54, 46, 51]     # new nearby requests keep coming

for step, new in enumerate(arrivals, 1):
    pending.append(new)
    nxt = min(pending, key=lambda r: abs(r - head))   # SSTF choice
    pending.remove(nxt)
    head = nxt
    print(f"step {step}: serve {nxt:3}   still waiting: {sorted(pending)}")

step 1: serve  48   still waiting: [190]
step 2: serve  53   still waiting: [190]
step 3: serve  47   still waiting: [190]
step 4: serve  52   still waiting: [190]
step 5: serve  49   still waiting: [190]
step 6: serve  54   still waiting: [190]
step 7: serve  46   still waiting: [190]
step 8: serve  51   still waiting: [190]

The request for cylinder 190 never gets served while the nearby stream continues.

SCAN (the elevator algorithm)

The head moves in one direction, serving every request it passes, until it reaches the end of the disk, then reverses. From 96 going up: 110, 140, 172, 190, on to 199 (the end), then back down to 85, 63, 30, 12. Total 290.

SCAN never starves anyone, because the sweep always comes back. But requests just behind the head must wait for a full round trip.

C-SCAN: circular SCAN

The head serves requests only while moving in one direction. At the end it jumps straight back to cylinder 0 without serving anything on the return, then sweeps up again. This gives more uniform waiting times: every cylinder is visited once per cycle, like a circular bus route that always runs clockwise.

In the output above the return jump from 199 to 0 is counted (199 cylinders), giving 387. Some exam questions do not count the return movement; then the answer would be 387 - 199 = 188. Always check which convention the question uses.

LOOK and C-LOOK

LOOK is SCAN that turns around at the last request in each direction instead of going all the way to the end of the disk. Here it turns at 190 instead of 199, saving 18 cylinders: 272 instead of 290.

C-LOOK is C-SCAN that goes only as far as the last request (190), then jumps to the lowest pending request (12) instead of to cylinder 0. Total 345 with the jump counted.

What happens with SSDs and in Linux today

Solid-state drives (SSDs) have no moving arm, so there is no seek time. The cost of reading block 10 or block 10,000,000 is about the same. Reordering requests by position is pointless; what matters is keeping the drive's many internal queues busy and treating processes fairly.

Linux uses a multi-queue block layer with these I/O schedulers:

• none: pass requests straight through; common for fast NVMe SSDs.
• mq-deadline: sorts requests but also gives each one a deadline so none waits too long, a good default for hard disks.
• bfq: shares disk time fairly between processes, good for desktop responsiveness.
• kyber: designed for fast devices, aiming at target latencies.

You can see and change the scheduler per device. The one in square brackets is active:

cat /sys/block/nvme0n1/queue/scheduler

[none] mq-deadline kyber bfq

Your device names and the list may differ. Windows manages disk queues inside its storage drivers and does not expose a choice of algorithm in the same way. The ideas in this lesson still apply to hard disks, which are widely used for large, cheap storage, and they are a classic exam topic.

Common mistakes

• Forgetting the trip to the end in SCAN. SCAN goes to cylinder 199 (or 0) before turning; LOOK does not.
• Ignoring the direction. SCAN and LOOK results depend on which way the head was moving; the question must say.
• Counting or not counting the C-SCAN return without checking. State your convention or follow the question's.

Key points

• Disk access time is seek time plus rotational latency plus transfer time; seek time dominates on HDDs.
• FCFS is fair but slow; SSTF picks the closest request and can starve far ones.
• SCAN sweeps to the end and back; C-SCAN sweeps one way and jumps back for uniform waits.
• LOOK and C-LOOK turn around at the last request instead of the disk edge.
• SSDs have no seek time; Linux often uses none or mq-deadline for them, and bfq for fairness.

queue = [140, 30, 172, 85, 12, 110, 63, 190]
head = 50
down = sorted((r for r in queue if r < head), reverse=True)
up = sorted(r for r in queue if r >= head)
path = [head] + down + [0] + up
print(path, total(path))

[50, 30, 12, 0, 63, 85, 110, 140, 172, 190] 240