The
elevator algorithm (also
SCAN) is a
diskA hard disk drive is a non-volatile storage device that stores digitally encoded data on rapidly rotating platters with magnetic surfaces. Strictly speaking, "drive" refers to the motorized mechanical aspect that is distinct from its medium, such as a tape drive and its tape, or a floppy disk...
schedulingInput / Output Scheduling or I/O Scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...
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
elevatorAn elevator or lift is a vertical transport vehicle that efficiently moves people or goods between floors of a building...
, 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
driveDrive may refer to:* Driving, the act of controlling a vehicle* Disk drive, a computer storage device* Prey drive, the instinctive behavior of a carnivore to pursue and capture prey* Drive theory, a diverse set of motivational theories in psychology...
maintains a
bufferIn computing, a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device . However, a buffer may be used when moving...
of pending read/write requests, along with the associated
cylinderA disk drive cylinder is a division of data in a disk drive, as used in the CHS addressing mode of a hard disk . It is also used in the Cylinder-Head-Record addressing mode of CKD disk...
number of the request.
The
elevator algorithm (also
SCAN) is a
diskA hard disk drive is a non-volatile storage device that stores digitally encoded data on rapidly rotating platters with magnetic surfaces. Strictly speaking, "drive" refers to the motorized mechanical aspect that is distinct from its medium, such as a tape drive and its tape, or a floppy disk...
schedulingInput / Output Scheduling or I/O Scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...
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
elevatorAn elevator or lift is a vertical transport vehicle that efficiently moves people or goods between floors of a building...
, 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
driveDrive may refer to:* Driving, the act of controlling a vehicle* Disk drive, a computer storage device* Prey drive, the instinctive behavior of a carnivore to pursue and capture prey* Drive theory, a diverse set of motivational theories in psychology...
maintains a
bufferIn computing, a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device . However, a buffer may be used when moving...
of pending read/write requests, along with the associated
cylinderA disk drive cylinder is a division of data in a disk drive, as used in the CHS addressing mode of a hard disk . It is also used in the Cylinder-Head-Record addressing mode of CKD disk...
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.
Description
When a new request arrives while the drive is idle, the initial arm/head movement will be in the direction of the cylinder where the data is stored, either
in or
out. As additional requests arrive, requests are serviced only in the current direction of arm movement until the arm reaches the edge of the disk. When this happens, the direction of the arm reverses, and the requests that were remaining in the opposite direction are serviced, and so on.
Variations
One variation of this method ensures all requests are serviced in only 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 this one direction only (or vice versa). This is known as the "Circular Elevator Algorithm" or C-SCAN. This results in more equal performance for all head positions, as the expected distance from the head is always half the maximum distance, unlike in the standard elevator algorithm where cylinders in the middle will be serviced as much as twice as often as the innermost or outermost cylinders.
Other variations include:
- FSCAN
FScan is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.It uses two subqueues. During the scan, all of the requests are in the first queue and all new requests are put into the second queue. Thus, service of new requests is...
- LOOK
LOOK is a disk scheduling algorithm used to determine the order in which new disk read and write requests are processed.-Description:LOOK is similar to SCAN in that the heads sweep across the disk surface in both directions performing reads and writes...
(and C-LOOK)
- N-Step-SCAN
N-Step-SCAN is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests....
Example
The following is an example of how to calculate average disk seek times for both the SCAN and C-SCAN algorithms.
- Example list of pending disk requests (listed by track number): 100, 50, 10, 20, 75.
- The starting track number for the examples will be 35.
- The list will need to be sorted in ascending order: 10, 20, 50, 75, 100.
Both SCAN and C-SCAN behave in the same manner until they reach the last track queued. For the sake of this example let us assume that the SCAN algorithm is currently going from a lower track number to a higher track number (like the C-SCAN is doing). For both methods, one takes the difference in magnitude (i.e. absolute value) between the next track request and the current track.
- 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 = 100 // 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) : 185
- Average (C-SCAN) : 185 / 5 = 37
Note: Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done.
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 firstShortest seek first is a secondary storage scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.- Description :...
, which is slightly closer to optimal, but can result in high variance in response time and even in
starvationIn computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task ....
when new requests continually get serviced prior to existing requests.
Anti-starvation techniques can be applied to the shortest seek time first algorithm to guarantee an optimum response time.
See also
- FCFS
FIFO is an acronym for First In, First Out, an abstraction in ways of organizing and manipulation of data relative to time and prioritization...
- FSCAN
FScan is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.It uses two subqueues. During the scan, all of the requests are in the first queue and all new requests are put into the second queue. Thus, service of new requests is...
- LOOK
LOOK is a disk scheduling algorithm used to determine the order in which new disk read and write requests are processed.-Description:LOOK is similar to SCAN in that the heads sweep across the disk surface in both directions performing reads and writes...
- N-Step-SCAN
N-Step-SCAN is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests....
- Shortest seek time first
Shortest seek first is a secondary storage scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.- Description :...