Disk Scheduling (FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK)

Why the order of requests matters

A hard disk stores data on spinning platters. To read a block, the read/write head must first move to the right cylinder (track). This movement is the seek, and it is by far the slowest part of a disk access: milliseconds, while everything else in the computer works in nanoseconds.

Many programs send requests at once, so the operating system keeps a queue of cylinders to visit. The disk scheduler decides the order. A good order means a short total head movement, which means faster programs.

Think of a courier with eight parcels for houses along one long road. Delivering them in the order they were ordered sends the van back and forth along the road. Delivering them in the order of the houses saves a lot of driving.

The textbook example

The classic exam question uses a disk with cylinders 0–199, the head at 53 moving towards higher cylinders, and this queue:

98, 183, 37, 122, 14, 124, 65, 67

If the head were moving towards lower cylinders, SCAN would be 236 and LOOK only 208. The direction matters, which is why exam questions always state it. Try both in the 3D model with Compare all.

The six algorithms

FCFS (First Come, First Served): serve requests in arrival order. It is simple and fair, but the head zig-zags wildly.

SSTF (Shortest Seek Time First): always go to the closest pending request. It is greedy and usually gives a short path. The danger is starvation: a request at the far end can wait forever if new requests keep arriving near the head.

SCAN (the elevator algorithm): move in one direction serving every request on the way, go all the way to the edge of the disk, then reverse. Like a lift that goes to the top floor and then comes down. No request starves.

C-SCAN (Circular SCAN): like SCAN, but after reaching the edge the head jumps back to the other edge and serves only in one direction. Waiting times become more uniform, because the disk is treated like a circle.

LOOK: SCAN without the wasted trip. The head reverses at the last request in the current direction instead of at the edge of the disk.

C-LOOK: C-SCAN without the wasted trip. After the last request it jumps straight to the farthest request on the other side.

Comparison

In practice, LOOK and C-LOOK are the usual choices: they are almost as efficient as SSTF but never starve a request.

Code

def fcfs(reqs, head):
    total = 0
    for r in reqs:
        total += abs(r - head)
        head = r
    return total

def sstf(reqs, head):
    pending, total = list(reqs), 0
    while pending:
        nxt = min(pending, key=lambda r: abs(r - head))   # closest request
        total += abs(nxt - head)
        head = nxt
        pending.remove(nxt)
    return total

# The sweeping algorithms, with the head moving towards higher cylinders.
def scan(reqs, head, max_cyl=199):
    up = sorted(r for r in reqs if r >= head)
    down = sorted((r for r in reqs if r < head), reverse=True)
    return fcfs(up + ([max_cyl] if down else []) + down, head)

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

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

def c_look(reqs, head):
    up = sorted(r for r in reqs if r >= head)
    low = sorted(r for r in reqs if r < head)
    return fcfs(up + low, head)

queue, head = [98, 183, 37, 122, 14, 124, 65, 67], 53
for f in (fcfs, sstf, scan, c_scan, look, c_look):
    print(f.__name__, f(queue, head))
# fcfs 640, sstf 236, scan 331, c_scan 382, look 299, c_look 322

What about SSDs?

Solid-state drives have no moving head, so every block is equally fast to reach and seek order hardly matters. Operating systems still schedule SSD requests, but for other reasons: merging neighbouring requests and keeping things fair between programs. Linux, for example, often uses the simple none or mq-deadline schedulers for SSDs. Disk scheduling algorithms remain important for hard disks, which still store most of the world’s data in data centres.

Common mistakes

• Forgetting the trip to the edge in SCAN. SCAN goes to cylinder 199 (or 0) before reversing. LOOK does not.
• Ignoring the direction. SCAN and LOOK give different totals depending on which way the head is moving.
• Counting (or not counting) C-SCAN’s return jump without saying so. Textbooks differ, so state which one you use.
• Starting the sum from the first request instead of from the head’s starting position.