Elevator algorithm

The elevator algorithm, or SCAN, is a disk-scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction. From an implementation perspective, the drive maintains a buffer of pending read/write requests, along with the associated cylinder number of the request, in which lower cylinder numbers generally indicate that the cylinder is closer to the spindle, and higher numbers indicate the cylinder is farther away. The algorithm is largely obsolete for data storage. With the current generation of magnetic disks it is not possible to know the location of specific data on the disk and solid state memory devices have a constant seek time independent of location.

The elevator algorithm, or SCAN, is a disk-scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction. From an implementation perspective, the drive maintains a buffer of pending read/write requests, along with the associated cylinder number of the request, in which lower cylinder numbers generally indicate that the cylinder is closer to the spindle, and higher numbers indicate the cylinder is farther away. The algorithm is largely obsolete for data storage. With the current generation of magnetic disks it is not possible to know the location of specific data on the disk and solid state memory devices have a constant seek time independent of location. ==History== The earliest published treatment of the algorithm is in Donald Knuth's classic book The Art of Computer Programming Volume 1 where he describes a theoretical simulation of a single elevator in the Mathematics building at the California Institute of Technology in order to discuss coroutines and doubly linked lists. By the 1980s the problem had been extended to n elevators. It is now considered to be a classic problem of Software Engineering and the formal specification of programming languages. Seek 1: 50 − 35 = 15 Seek 2: 75 − 50 = 25 Seek 3: 100 − 75 = 25 At this point both have reached the highest (end) track request. SCAN will just reverse direction and service the next closest disk request (in this example, 20) and C-SCAN will always go back to track 0 and start going to higher track requests. Seek 4 (SCAN): 20 − 100 = 80 Seek 5 (SCAN): 10 − 20 = 10 Total (SCAN): 155 Average (SCAN): 155 ÷ 5 = 31 Seek 4 (C-SCAN): 0 − 100 = 0 head movement as cylinders are treated as a circular list (C-SCAN always goes back to the first track) Seek 5 (C-SCAN): 10 − 0 = 10 Seek 6 (C-SCAN): 20 − 10 = 10 Total (C-SCAN): 85 Average (C-SCAN): 85 ÷ 5 = 17 Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done. ==See also== FIFO (computing and electronics) Shortest seek first

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367061946 under CC BY-SA 4.0; modifications have been made.