Disk Scheduling Algorithms in Operating System
Disk Scheduling Algorithm in OS
PreRequisite before Reading this – Magnetic Disks Structure
As we all know a hard disk(typically found in a computer) is a collection of disks placed on the top of one another. A typical hard disk may have 100-200 such disks stacked.
Now to have the best seek time or reduce seek time of an hard disk, we have different types of algorithms. Most common are mentioned below.
There are more advanced disk scheduling algorithm which are trade secrets of companies like – HP, Sandisks, etc. You have to work in those companies ;), to know them.
Before reading further we definitely suggest you please check out this page first as its PreRequisite before Reading – Magnetic Disks Structure
First Come First Serve
Now, this algorithm is fairly simple. In the order the request would come, in the same order visit the address on the disk.
Track Range from 0 to 199 and head initially is rested on 50
95, 180, 34, 119, 11, 123, 62, 64
First the head from 50 goes to 95 then→95→180→34→119→11→123→62→64
Total Head Movement Computation: (THM)
(95 – 50) + (180 – 95) + (180-34) + (119-34) + (119-11) + (123-11) + (123-62) + (64-62)
Now rather than doing (95 – 50) + (180 – 95) since direction doesnt change we can do (180 – 50).
The above step will save a lot of your time.
= (180 – 50) + (180-34) + (119-34) + (119-11) + (123-11) + (123-62) + (64-62) = 130 + 146 + 85 + 108 + 112 + 61 + 2 (THM) = 644 tracks
Assuming a seek rate of 5 milliseconds is given, we compute for the seek time using the formula:
Seek Time = THM * Seek rate = 644 * 5 ms
Seek Time = 3,220 ms
Shortest Seek Time First (SSTF) –
To save seek time, it would be better to visit the closest address first right.
Image if we start from 60 and 199 and 58 are FCFS order so first it will go from 60 to 199 and then from 199 to 58.
In this case total movement is – (199-60) + (199 – 58) = 280
However, if we visit closest from current r/w head, which is 60 then first we will visit 58 and then 199.
Total movement – (60-58) + (199 – 58) = 143.
Which is considerably lower than 280.
(THM) = (64-50) + (64-11) + (180-11)
= 14 + 53 + 169
(THM) = 236 tracks
Seek Time = THM * Seek rate = 236 * 5ms
Seek Time = 1,180 ms
In this algorithm, request is serviced according to the next shortest distance. Starting at 50, the next shortest distance would be 62 instead of 34 since it is only 12 tracks away from 62 and 16 tracks away from 34.
The process would continue up to the last track request. There are a total of 236 tracks and a seek time of 1,180 ms, which seems to be a better service compared with FCFS which there is a chance that starvation would take place.
The reason for this is if there were lots of requests closed to each other, the other requests will never be handled since the distance will always be greater.
Now, even in SSTF to and fro movement is there a lot.
Wouldn’t it be better if we just moved in one direction and once all requests in that direction are complete changed the direction and moved to 2nd direction.
Note – No other website tells you this in Scan the first request or direction decision is based on the nearest request. Example –
In Case below, from 50 it goes to 34 as its closer.
In Scan it will scan till the whole limit for our case its 0 and 199 to both will be scanned.
(THM) = (50-0) + (180-0) = 50 + 180 (THM) = 230
Seek Time = THM * Seek rate = 230 * 5ms
Seek Time = 1,150 ms
The idea comes from a disk, this is a modified version of scan, in which we changed the direction once we reached the end address for that scan.
Like in previous example, once we reached 199 we changed the direction.
In case of disks, which are circular 199 and 0 will be side by side. Correct?
If you still don’t understand – imagine a circle on the disk, now divide that circle in 200 equal parts starting from 0 till 199. Now imagine !!! 😛 its easy really.
This algorithm is a modified version of the SCAN algorithm. C-SCAN sweeps the disk from end-to-end, but as soon it reaches one of the end tracks it then moves to the other end track without servicing any requesting location.
As soon as it reaches the other end track it then starts servicing and grants requests headed to its direction.
This algorithm improves the unfair situation of the end tracks against the middle tracks. Using the same sets of example in FCFS the solution are as follows:
Note – In CSCAN a new variable alpha(α) is there which is basically adjustment time to shift from end to start(in this case from 0 to 199).
In ideal cases alpha(α) is 0. But, in real time cases alpha is some mili seconds.
Assume α = 20ms
(THM) = (50-0) + (199-62) + α = 50 + 137 + 20 (THM) = 207 tracks
Seek Time = THM * Seek rate = 187 * 5ms
Seek Time = 935 ms
Look is exactly like SCAN, but rather than going end to end like going to 0 and 199 both depending on the direction of the movement.
It looks for the last service required in either direction, hence called look.
In our case 11 and 180 are the last services.
(THM) = (50-11) + (180-11) = 39 + 169
(THM) = 208 tracks
Seek Time = THM * Seek rate = 208 * 5ms
Seek Time = 1,040 ms
C look again is modified version of looks. It is knows the last services in the either direction and also has alpha value(α) as, shift adjustment value.
Take alpha value as 20ms again.
(THM) = (50-11) + (180-62) + α = 39 + 118 + 20 (THM) = 177 tracks
Seek Time = THM * Seek rate = 157 * 5ms
Seek Time = 785 ms
Facts for MCQ’s
- SSTF is better than FCFS always.
- Scan in most cases or in average cases is better than SSTF and FCFS
Most operating Systems work on a advanced(can’t tell even we don’t know, they are trade secrets of big companies) version of SCAN and CLOOK.