Disk Scheduling Algorithms

OS use List of Disk Scheduling Algorithms i.e. (FCFS, SSTF, SCAN) for fast access time and Highly throughput. Before to explain disk scheduling, we must know the followings,

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

As Hard disk is Input and output device because CPU can read and write the data on it. So, Process 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 decide, which request will be execute next is called disk scheduling.

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

i. Seek Time

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

ii. Rotational Latency

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 at that specific sector.

iii. Transfer Time

After accessing the required data from specific sector, it is required to transfer it to CPU for execution. So, the time require to transfer the data from hard disk to 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, spends by each request, waiting for the I/O operation.

Goals of Disk Scheduling Algorithms

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

List of Disk Scheduling Algorithms

There are several disks scheduling algorithm where each algorithm has some 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 FCFS scheduling algorithm, R/W head of disk, executes the requests  in the same order as they arrive by moving inward and outward of of the disk.

Advantages:

• Simplest 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 inappropriate 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

Total 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 queue which has the least movement of R/W Head from its current position. This movement of R/W head has no concern with direction, either clockwise or anti clockwise.

Advantages

• Seek time is reduced
• Highly responsive

Disadvantages

• Starvation for some requests may happen.
• Overhead of OS is increased because each time OS has to find the nearest value from 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

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, and then it turns back and moves in the backward direction by executing the requests coming in that path.

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

Logic behind the moving of disk arm in a particular direction till the end is, at run time any disk request can happen.

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

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 C-SCAN algorithm, the R/W head of disk arm moves toward the particular direction by executing the receiving disk requests until it reaches the last track, then it jumps back to the start of sector of the opposite direction without executing any disk request then it  again start 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

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 exists 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

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 C-LOOK algorithm, the arm of the disk moves to 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

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 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)