Disk Scheduling Algorithms

A hard drive is a magnetic storage device consisting of several disks (a.k.a. platters) where data is stored.

Each disk is divided into many concentric circular tracks. Each track contains several sectors where data is stored. When the Operating System stores a file on a hard drive, this file is split into several clusters. Each cluster will be stored across a few sectors. The typical size of a cluster on a Windows computer is 4KB.

When loading a file into memory, it is necessary to access all the sectors used by this file. This involves physical movement of the Hard Drive arm used to position the Read/Write head on the right track. Once the head is positioned on the right track, the sectors of this track can easily be reached as the disk is constantly rotating. Moving the arm from one track to another takes time which increases the overall seek time: the time taken to locate a specific piece of data stored on a hard disk.

Disk scheduling

Disk scheduling is done by the operating system to schedule Read/Write requests (a.k.a I/O requests) arriving for the disk.

When a file is loaded into memory, several sectors (and tracks) will need to be accessed. The operating system can use different disk scheduling algorithms to do so. In this post we will compare four main algorithms:

• The FCFS Disk Scheduling Algorithm (First Come First Serve)
• The SCAN Disk Scheduling Algorithm
• The LOOK Disk Scheduling Algorithm
• The SSTF Disk Scheduling Algorithm (Shortest Seek Time First)

FCFS Disk Scheduling Algorithm

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 algorithm, 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:

So in this case, we can calculate the number of tracks crossed as follows:

SCAN Disk Scheduling Algorithm

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:

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

LOOK Disk Scheduling Algorithm

The LOOK disk scheduling algorithm is an improved version of the SCAN disk scheduling algorithm. In this algorithm, instead of reaching the last track (e.g. track 99) before changing direction, this algorithms changes direction when it reaches highest (or lowest) track from the list of track to access.

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:

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

SSTF Disk Scheduling Algorithm

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:

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

You Task

Estimate the Seek Time for all 4 scheduling algorithms for the given track lists: