Different Disc Scheduling Algorithms

Let’s consider a disk consisting of 100 concentric tracks (0-99) and let’s assume the Operating System needs to access sectors on the following tracks: [43,52,24,65,70,48,16,61]. And let’s assume the head is, to start with at track 20.

With a First Come First Served scheduling algorithms the tracks will be accessed in the order they were requested. So the read/write head will be moving from its current position to track 43, then track 52 then track 24 and so on…

Looking at the above pattern we can estimate the seek time of this approach:

Seek Time = (Number of tracks crossed) x (Time to cross one track)

Number of tracks crossed = |20-43| + |43-52| + |52-24| + |24-65| + |65-70| + |70-48| + |48-16| + |16-61| = 205

Seek Time = 205 x (Time to cross one track)

With the Shortest Seek Time First algorithm, we once again do not necessary process the requests in order they arrived. Instead we all always process the request which is the closest to the current position (track number) of the head.

In this case, using the same example as above: Starting Position: Track 20, list of tracks to access [43,52,24,65,70,48,16,61] we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-24| + |24-16| + |16-70| = 66

Seek Time = 66 x (Time to cross one track)

On average this algorithm will reduce the overall seek time (compared to all the other 3 algorithms we investigated in this blog post).

With a SCAN Disk Scheduling algorithm the disk arm will not access the tracks in the order they were requested. Instead it will move in one direction and service the requests coming in its path. After reaching the end of disk (e.g. track 99), it will reverse its direction and again services the request arriving in its path. Due to the movement of the arm going all the way up and down the number of tracks, the algorithm is also known as elevator algorithm. The aim of this approach is to reduce the average seek time when accessing a list of sectors.

In this case, using the same example as above: Starting Position: Track 20, list of tracks to access [43,52,24,65,70,48,16,61] we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-99| + |99-16| = 162

Seek Time = 162 x (Time to cross one track)

On average this algorithm will reduce the overall seek time (compared to a FCFS Disk Scheduling algorithm.