Circular SCAN Algorithm
In the SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.
These situations are avoided in the CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to the SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).
What is C-SCAN (Circular Elevator) Disk Scheduling Algorithm?
Circular SCAN (C-SCAN) scheduling algorithm is a modified version of SCAN disk scheduling algorithm that deals with the inefficiency of SCAN algorithm by servicing the requests more uniformly. Like SCAN (Elevator Algorithm) C-SCAN moves the head from one end servicing all the requests to the other end. However, as soon as the head reaches the other end, it immediately returns to the beginning of the disk without servicing any requests on the return trip (see chart below) and starts servicing again once reaches the beginning. This is also known as the “Circular Elevator Algorithm” as it essentially treats the cylinders as a circular list that wraps around from the final cylinder to the first one.
Algorithm:
- 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.
- The head services only in the right direction from 0 to size of the disk.
- While moving in the left direction do not service any of the tracks.
- When we reach at the beginning(left end) reverse the direction.
- While moving in right direction it services all tracks one by one.
- While moving in right direction calculate the absolute distance of the track from the head.
- Increment the total seek count with this distance.
- Currently serviced track position now becomes the new head position.
- Go to step 6 until we reach at right end of the disk.
- If we reach at the right end of the disk reverse the direction and go to step 3 until all tracks in request array have not been serviced.
Algorithm
>> Example :
Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Output:
Initial position of head: 50
Total number of seek operations = 190
Seek Sequence is
60
79
92
114
176
199
0
11
34
41
The following chart shows the sequence in which requested tracks are serviced using SCAN.
= (60-50)+(79-60)+(92-79)
+(114-92)+(176-114)+(199-176)+(199-0)
+(11-0)+(34-11)+(41-34)