Disk Scheduling Algorithms

'Disk Scheduling Algorithm' is an algorithm that keeps and manages input and output requests
arriving for the disk in a system. As we know, for executing any process memory is required.

Key Terms Associated with Disk Scheduling

There are many terms that we need to know for a better understanding of Disk Scheduling. We
are going to have a brief look at each of them one by one:

1. Seek Time: the disk arm moves and finds the required block. The time taken by the arm
in doing this search is known as "Seek Time".

2. Rotational Latency: The required data block needs to move at a particular position from
where the read/write head can fetch the data. So, the time taken in this movement is
known as "Rotational Latency".

3. Transfer Time: When a request is made from the user side, it takes some time to fetch
these data and provide them as output. This taken time is known as "Transfer Time".

4. Disk Access Time: It is defined as the total time taken by all the above processes. Disk
access time = (seek time + rotational latency time + transfer time)

Types of Disk Scheduling Algorithm in OS

We have various types of Disk Scheduling Algorithms available in our system. Each one has its
own capabilities and weak points.

1. FCFS disk scheduling algorithm-

It stands for 'first-come-first-serve'. As the name suggests, the request that comes first will be
processed first and so on. The requests coming to the disk are arranged in a proper sequence as
they arrive. Since every request is processed in this algorithm, so there is no chance of
'starvation'.

Example: Suppose a disk having 200 tracks (0-199). The request

sequence(82,170,43,140,24,16,190) of the disk is shown as in the given figure and the head
start is at request 50.

Explanation: In the above image, we can see the head starts at position 50 and moves to
request 82. After serving them the disk arm moves towards the second request which is 170
and then to the request 43 and so on. In this algorithm,, the disk arm will serve the requests in
arriving order. In this way, all the requests are served in arriving order until the process
executes.

"Seek time" will be calculated by adding the head movement differences of all the requests:

Seek time= "(82-50) + (170-82) + (170-43) + (140-43) + (140-24) + (24-16) + (190-16) = 642

 Advantages:

1. Implementation is easy.

2. No chance of starvation.

 Disadvantages:

1. 'Seek time' increases.

2. Not so efficient.

2. SSTF disk scheduling algorithm-

It stands for 'Shortest seek time first'. As the name suggests, it searches for the request having
the least 'seek time' and executes them first. This algorithm has less 'seek time' as compared to
the FCFS Algorithm.

Example: Suppose a disk has 200 tracks (0-199). The request

sequence(82,170,43,140,24,16,190) are shown in the given figure and the head position is at
50.

Explanation: The disk arm searches for the request which will have the least difference in head
movement. So, the least difference is (50-43). Here the difference is not about the shortest
value but it is about the shortest time the head will take to reach the nearest next request. So,
after 43, the head will be nearest to 24, and from here the head will be nearest to request 16,
After 16, the nearest request is 82, so the disk arm will move to serve to request 82 and so on.

Hence, Calculation of Seek Time = (50-43) + (43-24) + (24-16) + (82-16) + (140-82) + (170-140) +
(190-170) = 208

 Advantages:

1. In this algorithm, disk response time is less.

2. More efficient than FCFS.

 Disadvantages:

1. Less speed of algorithm execution.

2. Starvation can be seen.

3. SCAN disk scheduling algorithm:

In this algorithm, the head starts to scan all the requests in a direction and reaches the end of
the disk. After that, it reverses its direction and starts to scan again the requests in its path and
serves them. Due to this feature, this algorithm is also known as the "Elevator Algorithm".
Example: Suppose a disk has 200 tracks (0-199). The request
sequence(82,170,43,140,24,16,190) is shown in the given figure and the head position is at 50.
The 'disk arm' will first move to the larger values.

Explanation: In the above image, we can see that the disk arm starts from position 50 and goes
in a single direction until it reaches the end of the disk i.e.- request position 199. After that, it
reverses and starts servicing in the opposite direction until reaches the other end of the disk.
This process keeps going on until the process is executed. Hence, the Calculation of 'Seek Time'
will be like: (199-50) + (199-16) =332

 Advantages:

1. Implementation is easy.

2. Requests do not have to wait in a queue.

 Disadvantage:

1. The head keeps going on to the end even if there are no requests in that
direction.

4. C-SCAN disk scheduling algorithm:

It stands for "Circular-Scan". This algorithm is almost the same as the Scan disk algorithm but
one thing that makes it different is that 'after reaching the one end and reversing the head
direction, it starts to come back. The disk arm moves toward the end of the disk and serves the
requests coming into its path.

After reaching the end of the disk it reverses its direction and again starts to move to the other
end of the disk but while going back it does not serve any requests.
Example: Suppose a disk having 200 tracks (0-199). The request
sequence(82,170,43,140,24,16,190) are shown in the given figure and the head position is at
50.

Explanation: In the above figure, the disk arm starts from position 50 and reached the end(199),
and serves all the requests in the path. Then it reverses the direction and moves to the other
end of the disk i.e.- 0 without serving any task in the path.

After reaching 0, it will again go move towards the largest remaining value which is 43. So, the
head will start from 0 and moves to request 43 serving all the requests coming in the path. And
this process keeps going.

Hence, Seek Time will be =(199−50)+(199−0)+(43−0)=391=(199−50)+(199−0)+(43−0)=391

 Advantages:

1. The waiting time is uniformly distributed among the requests.

2. Response time is good in it.

 Disadvantages:

1. The time taken by the disk arm to locate a spot is increased here.

2. The head keeps going to the end of the disk.

5. LOOK the disk scheduling algorithm:

In this algorithm, the disk arm moves to the 'last request' present and services them. After
reaching the last requests, it reverses its direction and again comes back to the starting point. It
does not go to the end of the disk, in spite, it goes to the end of requests.

Example a disk having 200 tracks (0-199). The request sequence(82,170,43,140,24,16,190) are
shown in the given figure and the head position is at 50.

Explanation: The disk arm is starting from 50 and starts to serve requests in one direction only
but in spite of going to the end of the disk, it goes to the end of requests i.e.-190. Then comes
back to the last request of other ends of the disk and serves them. And again starts from here
and serves till the last request of the first side. Hence, Seek time =(190-50) + (190-16) =314

 Advantages:

1. Starvation does not occur.

2. Since the head does not go to the end of the disk, the time is not wasted here.

 Disadvantage:

1. The arm has to be conscious to find the last request.

6. C-LOOK disk scheduling algorithm:

The C-Look algorithm is almost the same as the Look algorithm. The only difference is that after
reaching the end requests, it reverses the direction of the head and starts moving to the initial
position. But in moving back, it does not serve any requests.

Example: Suppose a disk having 200 tracks (0-199). The request

sequence(82,170,43,140,24,16,190) are shown in the given figure and the head position is at
50.
Explanation: The disk arm starts from 50 and starts to serve requests in one direction only but
in spite of going to the end of the disk, it goes to the end of requests i.e.-190. Then comes back
to the last request of other ends of a disk without serving them. And again starts from the other
end of the disk and serves requests of its path. Hence, Seek
Time =(190−50)+(190−16)+(43−16)=341=(190−50)+(190−16)+(43−16)=341

 Advantages:

1. The waiting time is decreased.

2. If there are no requests till the end, it reverses the head direction immediately.

3. Starvation does not occur.

4. The time taken by the disk arm to find the desired spot is less.

Disadvantage:

1. The arm has to be conscious about finding the last request.