Part 4 of 7 · 2 min read
SCAN and C-SCAN
Think of a lift that goes up to the top floor, stopping wherever someone waits, and then goes down in the same way. Nobody waits for more than two sweeps. The analogy stops in one place: a real lift turns at the top and bottom floors, and some disk variants turn at the last request.
In plain words: SCAN moves the arm from one end of the disk to the other and serves every request on the way, then reverses and does the same in the other direction. A request waits at most for one full sweep and a half, so nothing starves. C-SCAN (circular SCAN) serves requests in one direction only. When the arm reaches the end, it returns to the other end without serving anything, and then sweeps again. This gives each cylinder a more even wait.
A worked example. On the queue of section 1, with the head at 50 moving up, SCAN serves 62, 64, 95, 119, 123 and 180 on the way to cylinder 199. It then reverses and goes down to 34 and 11. The movement is 149 up and 188 down, so 337 in total. C-SCAN goes up to 199 in 149, returns to 0 in 199 (counted here, though some books leave it out), then goes up to 34 in 34, so 382 in total.
The key lines. The totals come from the program of section 2. Read the three terms of each line as: distance up to the end, distance of the turn or the return, and distance of the last stretch.
SCAN (elevator algorithm)
The SCAN algorithm moves the disk arm in one direction across the whole disk and serves each waiting request that it reaches, then reverses and sweeps back the same way. C-SCAN treats the disk as a circle: it serves in one direction only and returns the arm to the start without serving requests on the way back.
Example: from cylinder 50 moving up, SCAN serves 62, 64, 95, 119, 123 and 180, then comes back down for 34 and 11.
Check yourself: 1. Why can SCAN not starve a request? 2. Which cylinders get the longest average wait under SCAN, the middle or the edges? 3. What does C-SCAN pay for a more even wait?