Disk scheduling

1Seek, rotate, transfer

essay.txt's blocks sit on a spinning disk. Reaching one block costs three times added together. Seek time is how long the head takes to move to the right cylinder — usually the largest term, which is why the algorithms below minimise total head movement. Rotational latency is waiting for the right sector to rotate under the head. Transfer time is the reading itself.

A disk at 6000 RPM turns once in 60/6000 = 0.01 s = 10 ms. Average rotational latency is half a turn: 5 ms. Scheduling cannot change the spin; it can only shorten the seek sum.

Figure. Access time ≈ seek + rotational latency + transfer — seek usually dominates random I/O.

Three additive pieces

1. SeekMove the arm to the cylinder — often the largest cost.
2. RotateWait for the sector; average latency = half a rotation = (60/\mathrm{RPM})/2 seconds.
3. TransferCopy the bytes: time = bytes / transfer rate.

2FCFS disk scheduling

The head sits at cylinder 50. Requests for essay.txt's blocks arrive as 82, 170, 43, 140. FCFS serves them in that arrival order: 50→82→170→43→140.

Movement: |82−50| = 32, |170−82| = 88, |43−170| = 127, |140−43| = 97. Total 32+88+127+97 = 344 cylinders. Fair, simple, and the head zigzags.

Figure. Arrival order forces the long 170 → 43 jump. Positions on the line are schematic — the labelled distances are the teaching content, not pixel-proportional cylinder spacing.

How to compute FCFS movement

1. Fix the startBegin at the given head cylinder.
2. Follow arrivalsVisit each request in the order queued — no reordering.
3. Sum gapsTotal head movement = sum of |current − next| over the path.

Coding lab. FCFS head movement from 50 runs in the app, with checks on your output.

3SSTF and starvation

SSTF (Shortest Seek Time First) always serves the pending request closest to the current head. From 50 the nearest of 82, 170, 43, 140 is 43 (|43−50| = 7). Then 82 (39), then 140 (58), then 170 (30). Total 7+39+58+30 = 134 cylinders — much shorter than FCFS's 344.

The cost is fairness. A steady stream of requests near 80 can starve cylinder 170 forever. SCAN-family algorithms trade a little movement for a bound on that wait.

Figure. SSTF always serves the closest pending request — short local seeks, risk of starvation at the edges.

How SSTF picks the next request

1. MeasureFrom the current head, compute |head − r| for every pending request.
2. Take the nearestServe the minimum; ties need a stated rule (either side is fine if the problem specifies).
3. RepeatUpdate the head and repeat until the queue is empty — then sum the jumps.

4SCAN, LOOK, C-SCAN, C-LOOK

SCAN (the elevator) sweeps the head in one direction, serving every request it passes, then reverses. LOOK is SCAN without going to the physical end: reverse at the last pending request in that direction. C-SCAN services in one direction only, then jumps back to the start (or the opposite end) without serving on the return. C-LOOK is the same one-way idea, reversing at the last request rather than the disk end.

The jump back on C-SCAN / C-LOOK is idle — it does not pick up requests. That is the exam distinction from SCAN / LOOK, which serve on both the outbound and the return sweep.

Figure. SCAN/LOOK reverse and keep serving. C-SCAN's return is an idle jump (dashed) so the next sweep starts from the low end with more uniform waiting.

How the elevators differ

1. SCANSweep one way to the disk end (or until empty), then reverse and sweep the other way.
2. LOOKLike SCAN, but reverse at the last request in the current direction — no wasted trip to an empty end.
3. C-SCAN / C-LOOKService only while going one way; jump back to the start (C-SCAN) or to the farthest opposite request (C-LOOK) without serving on the jump.