Disk Scheduling Algorithms

OS uses List of Disk Scheduling Algorithms, i.e. (FCFS, SSTF, SCAN) for fast access time and High throughput. Before explaining disk scheduling, we must know the following,

As we know, every process requires two types of time for its execution.

i. CPU time: Execution of process on CPU
ii. I/O time: Time to access the input or output device

A hard disk is an Input and output device because the CPU can read and write the data. So, Process the request to OS to access the hard disk. This time to access the hard disk is called I/O time.

The method through which an OS decides which request will be executed next is called disk scheduling.

Let’s explain some essential points related to disk scheduling.

i. Seek time

The time at which the disk arm arrives at the specific track where the read/write request will be satisfied is known as the seek time.

ii. Rotational Latency

The time at which the desired sector comes under the R/W head by rotating itself is called rotational latency. Then, read/write heads can read or write the data for that specific sector.

iii. Transfer time

After accessing the required data from a specific sector, it is necessary to transfer it to the CPU for execution. So, the time needed to move the data from the hard disk to the CPU is called transfer time.

iv. Disk Access Time

We can calculate Disk access time through the following equation,

Total Disk_Access_Time = Seek_Time + Rotational_Latency + Transfer_Time

v. Disk Response Time

It is the average time each request spends waiting for the I/O operation.

Goals of Disk Scheduling Algorithms

  • Fairness
  • High throughput
  • Minimal traveling R/W head time

List of Disk Scheduling Algorithms

There are several disk scheduling algorithms, each with advantages and disadvantages. We will explain all of the following

  • FCFS scheduling algorithm
  • SSTF (shortest seek time first) algorithm
  • SCAN scheduling
  • C-SCAN scheduling
  • LOOK Scheduling
  • C-LOOK scheduling

i. FCFS Scheduling Algorithm

In the FCFS scheduling algorithm, the R/W head of the disk executes the requests in the same order as they arrive by moving inward and outward of the disk.

Advantages:

  • Most straightforward algorithm and easy to implement
  • There is no starvation in FCFS because every request is serviced as it arrives.

Disadvantages

  • The scheme does not focus on the seek time.
  • Due to the appropriate movement of the head, seek time may be very high.

Example

Suppose the request queue sequence is 82, 170, 43, 140, 24, 16, 190 respectively, for a disk with 200 tracks.

Consider the position of R/W Head pointer is 50. Calculate the number of R/W head movements in cylinders, using FCFS scheduling.

Solution

FCFS Scheduling algorithm in Disk SchedulingTotal Number of tracks/cylinders moved by the R/W head is

= (82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16)
= 32 + 88 + 127 + 97 + 116 + 8 + 174
= 642

ii. SSTF Scheduling Algorithms

According to this algorithm, select a request from the queue that has the least movement of R/W Head from its current position. This movement of the R/W head has no concern with either clockwise or anti-clockwise direction.

Advantages

  • Seek time is reduced
  • Highly responsive

Disadvantages

  • Starvation for some requests may happen.
  • The overhead of OS is increased because each Time, OS has to find the nearest value from the disk arm.

Example

Request queue sequence = 82, 170, 43, 140, 24, 16, 190
Disk Tracks =200
R/W Head pointer is at 50.
Calculate the number of R/W head movements in cylinders, using SSTF scheduling?

Solution

SSTF Scheduling algorithm in Disk Scheduling

Total Number of tracks/cylinders moved by the R/W head is
= (50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170)
= 7 + 9 + 8 + 66 + 58 + 30 + 20
= 208

iii. SCAN Algorithm

In this algorithm, the R/W head moves in a particular direction till the end by executing all the disk requests coming in this direction. Then, it turns back and moves backward by executing the requests coming in that path.

It is also known as the Elevator Algorithm because in working, an elevator moves in a particular direction entirely (till the last floor) and then moves back.

The logic behind moving the disk arm in a particular direction until the end is that any disk request can happen at run-time.

Example

Request queue sequence = 82, 170, 43, 140, 24, 16, 190
Disk Tracks =200
R/W Head pointer is at 50.
Calculate the number of R/W head movements in cylinders, using SCAN scheduling?
Total Number of tracks/cylinders moved by the R/W head is

Solution

SCAN Scheduling algorithm in Disk Scheduling

Total Number of tracks/cylinders moved by the R/W head is
= (82-50)+(140-82)+(170-140)+(190-170)+(199-190)+(199-43)+(43-24)+(24-16)
= 32 + 58 + 30 + 20 + 9 + 156 +19 +8
= 332

iv. C-SCAN algorithm

In the C-SCAN algorithm, the R/W head of the disk arm moves toward a particular direction by executing the receiving disk requests until it reaches the last track. It jumps back to the start of the sector of the opposite direction without completing any disk request. It again starts moving in that direction by executing the remaining requests.

Example

Request queue sequence = 82, 170, 43, 140, 24, 16, 190
Disk Tracks =200
R/W Head pointer is at 50.
Calculate the number of R/W head movements in cylinders, using SSTF scheduling?
By considering Direction is toward large value
Solution
C-SCAN Scheduling algorithm in Disk Scheduling
Total Number of tracks/cylinders moved by the R/W head is
= (82-50)+(140-82)+(170-140)+(190-170)+(199-190) + (199-0) +(16-0) +(24-16) +(43-24)
= 32 + 58 + 30 + 20 + 9 + 199 +16 +8 + 19
= 391

v. Look Scheduling

It is just like the SCAN Algorithm, but the main difference is, In LOOK scheduling algorithm,  the disk arm stops moving inwards or outwards when there is no more disk accessing request in that direction.

Example

Request queue sequence = 82, 170, 43, 140, 24, 16, 190
Disk Tracks =200
R/W Head pointer is at 50.
Calculate the number of R/W head movements in cylinders, using SSTF scheduling?
By considering Direction is toward large value
Solution
LOOK Scheduling algorithm in Disk Scheduling
Total Number of tracks/cylinders moved by the R/W head is
= (82-50)+(140-82)+(170-140)+(190-170) +(190-43)+(43-24)+(24-16)
= 32 + 58 + 30 + 20 + 147 +19 +8
= 314

vi. C Look Scheduling

According to the C-LOOK algorithm, the arm of the disk moves outwards of the disk by servicing disk accessing requests until it reaches the highest disk-request track, then it jumps back to the lowest request track without executing any disk-request then again disk-arm starts moving outwards by executing the remaining disk-requests.

Example

Request queue sequence = 82, 170, 43, 140, 24, 16, 190
Disk Tracks =200
R/W Head pointer is at 50.
Calculate the number of R/W head movements in cylinders, using SSTF scheduling?
By considering Direction is toward large value
Solution
C-LOOK Scheduling algorithm 
Total Number of tracks/cylinders moved by the R/W head is
= (82-50) + (140-82) + (170-140) + (190-170) + (190-16) + (24-16) + (43-24)
= 32 + 58 + 30 + 20 + 174 +8 + 19
= 341

Note: If the B part of this question is

B). If R/W head takes 1ns to move from 1 track to another, then total time is taken…….?

Solution

Total time taken by R/W head to move from one sector to another = time for 1 sector * total sectors moved                                                                                                                      = 1ns*642 642ns. (For FCFS)