CONCEPT - Elevator SCAN or SCAN Algorithm

Algorithm


Elevator SCAN Algorithm

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

In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works as an elevator and hence also known as elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

Advantages:

  • This algorithm is simple and easy to understand.

    • DisAdvantages:

  • More complex algorithm to implement.
  • This algorithm is not fair because it cause long waiting time for the cylinders just visited by the head.
  • It causes the head to move till the end of the disk in this way the requests arriving ahead of the arm position would get immediate service but some other requests that arrive behind the arm position will have to wait for the request to complete.

Algorithm

1. Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of disk head.
2. Let direction represents whether the head is moving towards left or right.
3. In the direction in which head is moving service all tracks one by one.
4. Calculate the absolute distance of the track from the head.
5. Increment the total seek count with this distance.
6. Currently serviced track position now becomes the new head position.
7. Go to step 3 until we reach at one of the ends of the disk.
8. If we reach at the end of the disk reverse the direction and go to step 2 until all tracks in request array have not been serviced.

>> Example :

Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = left (We are moving from right to left)

Output:
Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176

The following chart shows the sequence in which requested tracks are serviced using SCAN.



Therefore, the total seek count is calculated as:

= (50-41)+(41-34)+(34-11)
+(11-0)+(60-0)+(79-60)
+(92-79)+(114-92)+(176-114)
= 226