On a disk with 1000 cylinders (0 to 999), find the number of tracks the disk…

Concept

SCAN — the elevator algorithm — keeps the disk arm moving in the direction it is already travelling, serving every pending request it passes, until it reaches the end cylinder on that side of the disk. Only then does the arm reverse and serve the requests waiting in the opposite direction.

Two turning points therefore fix the total head movement: the disk end in the initial direction of travel, and, on the return sweep, the farthest pending request, since the arm has nothing left to travel toward once the queue is empty. Total movement is the sum of the leg lengths, and the FIFO arrival order changes nothing.

Application

1. The arm starts at track 345 and is moving inward, toward track 0, on a disk spanning cylinders 0 to 999.

2. Travelling inward, the arm passes and serves the pending requests that lie below 345: first 123, then 105.

3. It does not turn at 105; SCAN carries the arm to the end cylinder in that direction, cylinder 0. Inward leg = 345 − 0 = 345 tracks.

4. The arm reverses at cylinder 0 and travels outward, serving 376, 475, 692 and 874 in that order.

5. 874 is the farthest pending request, so the outward sweep ends there. Outward leg = 874 − 0 = 874 tracks.

6. Total head movement = 345 + 874 = 1219 tracks.

Cross-check

The same result follows from the closed form for an inward-first SCAN: total = (start − lower end) + (highest request − lower end) = (345 − 0) + (874 − 0) = 1219 tracks. Re-shuffling the queue leaves this unchanged, because the turning points are set by the algorithm and the extreme request values, not by arrival order.

Contrast with other traversals