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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What do you think? Have you tried executing the algorithms step by step? $\endgroup$– RaphaelCommented Nov 25, 2014 at 13:38
-
$\begingroup$ The wikipedia article on the Elevator Algorithm (also known as SCAN) has a nice worked example: en.wikipedia.org/wiki/Elevator_algorithm $\endgroup$– Wandering LogicCommented Nov 26, 2014 at 12:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In the SCAN algorithm (also called Elevator algorithm) the disk head, when servicing requests, will move in one direction until it reaches the edge of the disk.
For example consider a disk with 5000 sectors. If we assume the head begins at sector 0 it will move the head over every sector from 0 to 4999, servicing any requests on sectors as it moves. When the head reaches sector 4999 it will reverse the movement direction and repeat the process, servicing any requests as it progresses back to sector 0.
The C-SCAN modification is very similar. If we, again, assume the disk head is at sector 0 it will begin moving from 0 to 4999. Upon reaching sector 4999 the disk head immediately returns to sector 0, no requests are serviced during this movement.
For the example you've given [10 22 20 2 40 6 38], and the head at sector 20. The arm begins moving, I will assume that it is moving in the positive direction as that is what the answer seems to indicate.
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20, 22 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20, 22, 38 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20, 22, 38, 40 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20, 22, 38, 40 ]
As 40 is the largest sector in the queue we would now expect the arm to seek to the edge of the disk. Since it's not given I assumed 40 was the last block. Thus the arm reverses seek direction.
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20 22 38 40 10 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20 22 38 40 10 6 ]
REQUESTS: [10 22 20 2 40 6 38]; READ: [ 20 22 38 40 10 6 2 ]
In the case of C-SCAN the order of the last three requests is reversed. The arm would seek to 0 and then begin producing [ ... 2 6 10 ]
$\begingroup$
$\endgroup$
SCAN works like an elevator does. 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 from 20,22 is the closest so it starts moving in that direction.
Continuing 20,22,38,40,end now reversing head and moving in the opposite direction
i.e. from end to 10,6,2.
So the order should be 20,22,38,40,end,10,6,2 for SCAN and 20,22,38,40,10,6,2 for LOOK.
