-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What do you think? Have you tried executing the algorithms step by step? $\endgroup$ – Raphael Nov 25 '14 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 Logic Nov 26 '14 at 12:20
1
$\begingroup$

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 ]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.