LOOK algorithm
 | This article possibly contains original research. (April 2014) |
 | This article needs additional citations for verification. (April 2014) |
LOOK is a disk scheduling algorithm used to determine the order in which new disk read and write requests are processed.
Description
The LOOK algorithm is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write read is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.[1]
LOOK behaves almost identically to SSTF, but avoids the starvation problem of SSTF. This is because LOOK is biased against the area recently traversed, and heavily favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).
Variants
One variant of LOOK is C-LOOK. C-LOOK (circular LOOK) is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if you’re moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than you’d expect and usually considerably less than the time it would take to seek there one track at a time).
Performance
LOOK has slightly better average seek times than SCAN. C-LOOK has a slightly lower variance in seek time than LOOK since the worst case seek time is nearly cut in half.
See also
Other variations include:
- SCAN - Elevator algorithm
- FSCAN
- N-Step-SCAN