SCAN and CSCAN algorithm

 Khan picture Khan · Nov 25, 2014 · Viewed 21.2k times · Source

I am having hard time understanding the working of SCAN and CSCAN algorithm of disk scheduling.I understood FCFS,Closest Cylinder Next but heard that SCAN resembles elevator mechanism and got confused. My book says that for the incoming order :[10 22 20 2 40 6 38] (while the disk currently at 20) the SCAN moving at the start serves [(20) 20 22 38 40 10 6 2]; this requires moves of [0 2 16 2 30 4 4] cylinders, a total of 58 cylinders. How does the pattern [(20) 20 22 38 40 10 6 2] came?

Answer

Am_I_Helpful picture Am_I_Helpful · Nov 25, 2014

Let's know what the SCAN(Elevator) disk-scheduling algorithm says:-

It scans down towards the nearest end and then when it hits the bottom it scans up servicing the requests that it didn't get going down. If a request comes in after it has been scanned it will not be serviced until the process comes back down or moves back up.

So, in your case, the current position of disk is at 20. So, as per the SCAN algorithm, it'll scan towards the nearest end, and just after hitting bottom, it scans up servicing the requests back up.

The order is :-

|                                                     |


| * current position                                  | * move back up to upside
|---> nearest disk is this one                        |
|     so it'll move down and so on.                   |
|         as it hit the bottom                     _______

____

                   Fig :- Demonstration of SCAN algorithm  

So, as per the given data, the order will be [(20) 20 22 38 40 10 6 2];


EDIT :-

The only difference between SCAN and CSCAN is that in CSCAN,

it begins its scan toward the nearest end and works it way all the way to the end of the system. Once it hits the bottom or top it jumps to the other end and moves in the same direction,unlike the SCAN which moves back to upside using the same path.

As per CSCAN,the direction of movement would be same uptil bottom and then it'll reverse the path.

So, as per the given data, the order will be [(20) 20 22 38 40 2 6 10]; Notice the change in last three disk positions.

I hope it is clear. Feel free to ask remaining doubts.