SCAN and CSCAN algorithm

operating-system computer-science disk disk-io
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.

Related questions

Implementing an N process barrier using semaphores

I'm currently training for an OS exam with previous iterations and I came across this: Implement a "N Process Barrier", that is, making sure that each process out of a group of them waits, at some point in its respective …

Read More
What is round-robin scheduling?

In a multitasking operating system context, sometimes you hear the term round-robin scheduling. What does it refer to? What other kind of scheduling is there?

Read More
How can I safely create a nested directory?

What is the most elegant way to check if the directory a file is going to be written to exists, and if not, create the directory using Python? Here is what I tried: import os file_path = "/my/directory/filename.…

Read More