Part 5 of 7 · 2 min read
LOOK, C-LOOK and the choice
Think of the same lift that learns that nobody waits above floor 14, so it turns at floor 14 and not at the roof. The analogy stops in one place: a lift knows the waiting people, and a disk only knows the requests that have already reached the queue.
In plain words: LOOK is SCAN that turns at the last waiting request in each direction and does not go to the end of the disk. C-LOOK is C-SCAN with the same shortcut. They never move farther than SCAN or C-SCAN and they keep the same freedom from starvation. Most real systems that schedule by position use a LOOK variant for this reason.
A worked example. On the same queue, LOOK moving up first serves 62 to 180 in 130 cylinders and returns to 11 in 169, so 299 in total. C-LOOK goes up in 130, jumps back to 11 in 169, and goes up to 34 in 23, so 322 in total. The table lists all six results. The last column costs each at 0.05 ms per cylinder.
| Algorithm | Cylinders moved | Cost at 0.05 ms per cylinder |
|---|---|---|
| FCFS | 644 | 32.20 ms |
| SSTF | 236 | 11.80 ms |
| SCAN (up first) | 337 | 16.85 ms |
| LOOK (up first) | 299 | 14.95 ms |
| C-SCAN (up) | 382 | 19.10 ms |
| C-LOOK (up) | 322 | 16.10 ms |
SSTF is the best on this queue, and SCAN and LOOK are close. Their gap to SSTF is the price of a bounded wait. On a busy disk with many requests, SCAN and LOOK serve a request on almost every cylinder they pass, and their advantage over FCFS becomes large.
Common mistake
SCAN and LOOK are not the same. SCAN goes all the way to the last cylinder of the disk, and LOOK turns at the last request. Textbooks often draw LOOK and call it SCAN. In an exam, state which end the arm goes to.
LOOK
The LOOK algorithm is the SCAN algorithm that reverses at the farthest waiting request in the current direction and not at the end of the disk. C-LOOK is the same shortcut applied to C-SCAN.
Example: from cylinder 50 moving up with 180 as the farthest request, LOOK reverses at 180 and not at 199, which saves 19 cylinders each way.
Check yourself: 1. From the table, what is the difference between SCAN and LOOK, and why? 2. Which two algorithms in the table can starve a request? 3. Why do book authors call SSTF "not optimal"?