Elevator algorithm

The elevator algorithm' (also SCAN/C-SCAN) is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.

Description

The algorithm is so named since the behaviour is akin to an elevator. The drive maintains an incoming buffer of requests, and tied with each request is a cylinder number of the request. Lower cylinder numbers indicate that the cylinder is closest to the spindle, and higher numbers indicate the cylinder is further away.

From some initial arm/head starting position with incoming requests, we also have a current indication of the arm movement, either in or out. As requests arrive, the requests are serviced in the direction of the arm movement until there are no further requests in the current direction. When this happens, the direction of the arm reverses, and the requests that were remaining in the opposite direction are serviced, and so on.

One variation of this method ensures all requests are serviced in the one direction, that is, once the head has arrived at the outer edge of the disk, it returns to the beginning and services the new requests in the one direction only (or vice versa).

Analysis

The arm movement is thus always less than twice the number of total cylinders then, for both versions of the elevator algorithm. The variation has the advantage to have a smaller variance in response time. The algorithm is also relatively simple.

However, the elevator algorithm is not always better than Shortest seek first, which is slightly more optimal, but can result in statistical performance issues.