The elevator algorithm: SCAN and LOOK with a worked example
SCAN goes to the end before turning, LOOK turns at the last request. One example compares them with FCFS and shortest-seek-first.
In computer science the “elevator algorithm” usually means SCAN, a way to schedule a disk’s read head. Move in one direction and handle every request on the way, then turn around. LOOK is the same thing, except it turns at the last request instead of the end of the disk. Real lifts do LOOK.
Here is one example. A lift is on floor 5 of a building with floors 0 to 10, going up. Requests came in for floors 9, 2, 7, 1 and 8, in that order.
| Strategy | Stops | Floors travelled |
|---|---|---|
| First come, first served | 9, 2, 7, 1, 8 | 29 |
| Shortest seek first (SSTF) | 7, 8, 9, 2, 1 | 12 |
| SCAN | 7, 8, 9, (10), 2, 1 | 14 |
| LOOK | 7, 8, 9, 2, 1 | 12 |
| C-SCAN | 7, 8, 9, (10, 0), 1, 2 | 17 |
| C-LOOK | 7, 8, 9, 1, 2 | 13 |
First come, first served crosses the building five times. Shortest seek first looks as good as LOOK here, but it can starve a far-away request forever if closer ones keep arriving. SCAN wastes a trip to the top floor. LOOK skips that trip and nobody waits more than two sweeps.
The circular versions (C-SCAN, C-LOOK) only serve requests going one way and jump back to the start. That evens out waiting times on a disk. It makes less sense for lifts, where people go down as often as up.
Lifts also have problems a disk doesn’t: a full car can’t pick anyone up, people care about waiting as well as riding, and with two or more cars you have to decide which one answers. That is where Elevator gets interesting.