Disk Scheduling Algorithms in Operating System

Disk scheduling algorithm

Disk Scheduling Algorithms in Operating System

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.

There are more advanced Disk Scheduling Algorithms in Operating System 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

Types of Disk Scheduling Algorithms

First Come First Serve  (FCFS)

Now, this algorithm is fairly simple. In the order the request would come, in the same order visit the address on the disk.

Example –

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 then9518034119111236264

Total Head Movement Computation: (THM)

(95 – 50) + (180 – 95) + (180-34) + (119-34) + (119-11) + (123-11) + (123-62) + (64-62)

Trick

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

Disk Scheduling Algorithm FCFS

 

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 50, nearest to 50 -> 62 : nearest to 62 ->64 :
Nearest to 64-> 34 : nearest to 34->11 : nearest to 11 : 95. Similarly,
95->119, 119->123, 123->180
In this case total movement is – (64-50) + (64 – 11) + (180 – 11) = 236

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.

 

Elevator (SCAN)

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 – If in the question the initial direction of movement is given then, Follow that, if the direction is not given then, the which ever is the nearest end that direction is chosen.

For example : In this question the Read-write head initially is at 50. The nearest b/w 0 or 199 is 0.

So direction of movement will be that.

Example –
Track Range from 0 to 199 and head initially is rested on 50
95, 180, 34, 119, 11, 123, 62, 64

(THM) = (50 – 0) + (180 – 0) = 230
Seek Time = THM * Seek rate = 230 * 5ms
Seek Time = 1150 ms

 

Circular SCAN (C- SCAN)

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 0 we changed the direction.

Wouldn’t it be a little better if we could start from 199 instead and start servicing in that 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:

Its an improvement over elevator

Note – In CSCAN a new variable alpha(α) is there which is basically adjustment time to shift from end to start(in this case from 199 to 0).

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 = 207 * 5ms

Seek Time = 1035 ms

 

LOOK

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 = 208

(THM) = 208 tracks

Seek Time = THM * Seek rate = 208 * 5ms

Seek Time = 1040 ms

New OS - Disk Scheduling Algorithm LOOK

 

C – LOOK

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 = 177 * 5ms

Seek Time = 885 ms

Facts For MCQ

  • 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.