Disk geometry and disk scheduling

Aisha backs up her project to the external 1 TB hard disk. It has 200 tracks. The read head is sitting at track 53.

The backup queues eight block requests: tracks 98, 183, 37, 122, 14, 124, 65, 67.

Serve them in the order they arrived and the head travels 640 tracks. Serve them in a smarter order and it travels 236.

Same eight blocks. Same data. Less than half the movement, and on this disk movement is nearly all of the time.

Why & what

Why order matters on a spinning disk. Three things happen for each access:

• Seek time — moving the head to the right track. This is mechanical and by far the largest.
• Rotational latency — waiting for the right sector to spin under the head.
• Transfer time — actually reading the bits. Almost free by comparison.

Seek dominates, so reordering requests to reduce head travel is a genuine win.

Four algorithms, all on our queue with the head at 53:

• FCFS — serve in arrival order. 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67. The head crosses the disk repeatedly. 640 tracks. Perfectly fair, and it never gets faster than this.
• SSTF — shortest seek time first. Always go to the nearest pending request. 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183. 236 tracks. It is the fastest here, and it can starve. If requests keep arriving near the head, a request at track 190 waits forever. That is Module 3's starvation, in a different place.
• SCAN — the elevator. Move in one direction serving everything on the way, reach the end, reverse. 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14. 331 tracks. It cannot starve: the head is always coming back for you.
• C-SCAN — circular SCAN. Sweep one way only. At the end, jump straight back to track 0 without serving anything, and sweep again. 382 tracks. It costs more, and it buys uniform waiting. Under SCAN, a track in the middle gets visited twice per sweep while a track at the edge gets visited once. C-SCAN makes everybody wait about the same.

A note on counting. These totals include the full sweep to track 199 and, for C-SCAN, the jump back to 0. Some textbooks do not count the return jump. If a question gives a total you cannot reproduce, check that convention first — the method is right even when the number differs.

LOOK and C-LOOK are the obvious improvement: go only as far as the furthest pending request instead of all the way to the end. LOOK on our queue gives 299 instead of SCAN's 331. Real systems use these rather than SCAN.

HDD versus SSD. All of this assumes a moving head.

• A hard disk has platters and an arm. Position matters enormously.
• An SSD has no moving parts. Any block costs about the same, so reordering by track number saves nothing.

This is why Aisha's internal SSD does not need a scheduler in the same way, and her backup disk does. SSDs have their own problem instead: a block must be erased before it can be rewritten, and each cell tolerates a limited number of erases, so the drive spreads writes around internally to make them wear evenly.

How it works

Working a disk scheduling question by hand:

1. Write down the head position and the queue in arrival order.
2. Apply the rule to pick the next track, and note the distance from the current position.
3. Move the head and remove that request.
4. Repeat until the queue is empty, adding the end-of-disk stop for SCAN or C-SCAN if the direction requires it.
5. Add up the distances. Only the total head movement is being scored.

Common confusion

"SSTF is the best because it has the lowest total." It has the lowest total for this queue, and it can starve requests indefinitely. SCAN costs 95 more tracks and guarantees everyone is served. That is the same trade as SJF versus Round Robin in Module 3, and it is worth saying so out loud in an interview.

"C-SCAN is better than SCAN because it is more advanced." It moves the head further. What it buys is fairness, not speed. If a question asks which is faster, the answer is SCAN.

"Disk scheduling is obsolete because everything is SSD now." Spinning disks still hold most of the world's bulk storage, and the algorithms are asked about constantly. The comparison itself is the interesting part: knowing why it stops mattering on an SSD proves you understand what it was solving.

Interview angle

"Given this queue and head position, compute the total head movement for FCFS, SSTF, SCAN and C-SCAN." This is one of the most reliably asked numerical questions in the whole subject. Practise it until it is mechanical, and state your direction and counting convention before you start.

"Which algorithm would you choose?" Do not just name one. Say SSTF for throughput when starvation is not a concern, SCAN or LOOK for a general-purpose system because they bound the waiting time, and note that on an SSD the question mostly stops applying.