Disk Scheduling Algorithms

Disk Scheduling:

•  The operating system is responsible for using hardware efficiently, for the disk drives, this means having a fast access time and disk bandwidth.
•       Access time has three major components: -

Ø  Seek time: it is the average time taken by the head to move from one track to another.

Ø  Rotational latency: it is the additional time waiting for the disk to rotate the desired sector to the disk head. It is not fixed so we take the average value.

Ø  Transfer time: it is time taken to transfer the data

Disk Access Time = Rotational Latency + Seek Time + Transfer Time

Disk Response Time= Delay Time (spent for IO operation) + Disk Access Time

Purpose of Disk Scheduling:

The main purpose of the disk scheduling algorithm is to select a disk request from the queue of IO requests and decide the schedule when this request will be processed.

The goal of Disk Scheduling:

Ø  Fairness

Ø  High throughout

Ø  Minimal traveling head time

Disk Scheduling Algorithms

1.      FCFS: 

FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.

2.      SSTF:

 In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of system.

3.      SCAN:

In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction and again services the request arriving in its path. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

4.      CSCAN:

 In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.

         it is known as Circular SCAN.

            5. LOOK:

              It is similar to the SCAN disk scheduling algorithm except the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.          

6.      CLOOK: 

CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm inspite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Example:

On a disk with 1000 cylinders, number 0 to 999, compute the number of tracks the disk arm must move to satisfy all the requests in the disk queue. Assume the last request serviced was at track 345 and the head is moving toward track 0. The queue in FIFO order contains requests for the following tracks,

123, 874, 692, 475, 105, 376.

Perform the computation for the above scheduling algorithms.

FCFS:

 Total R/W head Movement: 222+751+182+217+370+271 =2013 tracks 

SSTF:

Total R/W head Movement: 31+99+182+217+182+751+18=1298 tracks

  
SCAN:

Total R/W head Movement: 222+18+105+376+99+217+182=1219 tracks

LOOK:

Total R/W head Movement: 222+18+271+99+217+182=1009 tracks

CSCAN:

Total R/W head Movement: 222+18+105+999+125+182+217+99= 1967 tracks

CLOOK:

Total R/W head Movement: 222+18+769+182+217+99= 1507 tracks