Disk scheduling 

is done by operating systems to schedule I/O requests arriving for the

disk. Disk scheduling is also known as I/O scheduling.

Disk scheduling is important because:

 Multiple I/O requests may arrive by different processes and only one I/O request
can be served at a time by the disk controller. Thus other I/O requests need to wait
in the waiting queue and need to be scheduled.
 Two or more request may be far from each other so can result in greater disk
arm movement.
 Hard drives are one of the slowest parts of the computer system and thus need
to be accessed in an efficient manner.

There are many Disk Scheduling Algorithms but before discussing them let’s have a
quick look at some of the important terms:
 Seek Time: Seek time is the time taken to locate the disk arm to a specified track
where the data is to be read or write. So the disk scheduling algorithm that gives
minimum average seek time is better.
 Rotational Latency: Rotational Latency is the time taken by the desired sector
of disk to rotate into a position so that it can access the read/write heads. So the
disk scheduling algorithm that gives minimum rotational latency is better.
 Transfer Time: Transfer time is the time to transfer the data. It depends on the
rotating speed of the disk and number of bytes to be transferred.
 Disk Access Time: Disk Access Time is:
 Disk Access Time = Seek Time +
 Rotational Latency +
 Transfer Time

Disk Response Time: Response Time is the average of time spent by a request waiting to
perform its I/O operation. Average Response time is the response time of the all
requests. Variance Response Time is measure of how individual request are serviced with
respect to average response time. So the disk scheduling algorithm that gives minimum
variance response time is better.
 Disk Scheduling Algorithms-
 

 The algorithms used for disk scheduling are called as disk scheduling algorithms.
 The purpose of disk scheduling algorithms is to reduce the total seek time.
 
Various disk scheduling algorithms are-
 

 
1. FCFS Algorithm
2. SSTF Algorithm
3. SCAN Algorithm
4. C-SCAN Algorithm
5. LOOK Algorithm
6. C-LOOK Algorithm

FCFS Disk Scheduling Algorithm-

 
 As the name suggests, this algorithm entertains requests in the order they arrive in
the disk queue.
 It is the simplest disk scheduling algorithm.
 

Advantages-
 

 It is simple, easy to understand and implement.

 It does not cause starvation to any request.
 

Disadvantages-
 

 It results in increased total seek time.

 It is inefficient.
 

PRACTICE PROBLEM BASED ON FCFS DISK

SCHEDULING ALGORITHM-
 

Problem-
 
Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124,
65, 67. The FCFS scheduling algorithm is used. The head is initially at cylinder number 53.
The cylinders are numbered from 0 to 199. The total head movement (in number of
cylinders) incurred while servicing these requests is _______.
 

Solution-
 
  
Total head movements incurred while servicing these requests
= (98 – 53) + (183 – 98) + (183 – 41) + (122 – 41) + (122 – 14) + (124 – 14) + (124 – 65) +
(67 – 65)
= 45 + 85 + 142 + 81 + 108 + 110 + 59 + 2
=632

SSTF Disk Scheduling Algorithm-

 

 SSTF stands for Shortest Seek Time First.

 This algorithm services that request next which requires least number of head
movements from its current position regardless of the direction.
 It breaks the tie in the direction of head movement.
 

Advantages-
 

 It reduces the total seek time as compared to FCFS.

 It provides increased throughput.
 It provides less average response time and waiting time.
 

Disadvantages-
 

 There is an overhead of finding out the closest request.

 The requests which are far from the head might starve for the CPU.
 It provides high variance in response time and waiting time.
 Switching the direction of head frequently slows down the algorithm.
 

PRACTICE PROBLEMS BASED ON SSTF DISK

SCHEDULING ALGORITHM-
 

Problem-01:
 
Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124,
65, 67. The SSTF scheduling algorithm is used. The head is initially at cylinder number 53
moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered
from 0 to 199. The total head movement (in number of cylinders) incurred while servicing
these requests is _______.
 

Solution-
 
  
Total head movements incurred while servicing these requests
= (65 – 53) + (67 – 65) + (67 – 41) + (41 – 14) + (98 – 14) + (122 – 98) + (124 – 122) + (183
– 124)
= 12 + 2 + 26 + 27 + 84 + 24 + 2 + 59
= 236

Problem-02:
 
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in
following sequence-
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all
requests if it takes 1 ms to move from one cylinder to adjacent one and shortest seek time
first policy is used?
1. 95 ms
2. 119 ms
3. 233 ms
4. 276 ms
 

Solution-
 

 
Total head movements incurred while servicing these requests
= (50 – 34) + (34 – 20) + (20 – 19) + (19 – 15) + (15 – 10) + (10 – 7) + (7 – 6) + (6 – 4) + (4
– 2) + (73 – 2)
= 16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71
= 119
 
Time taken for one head movement = 1 msec. So,
Time taken for 119 head movements
 = 119 x 1 msec
= 119 msec

SCAN Disk Scheduling Algorithm-

 

 As the name suggests, this algorithm scans all the cylinders of the disk back and
forth.
 Head starts from one end of the disk and move towards the other end servicing all
the requests in between.
 After reaching the other end, head reverses its direction and move towards the
starting end servicing all the requests in between.
 The same process repeats.
 

NOTE-
 

 SCAN Algorithm is also called as Elevator Algorithm.

 This is because its working resembles the working of an elevator.
 
Also Read- FCFS Disk Scheduling Algorithm
 

Advantages-
 

 It is simple, easy to understand and implement.

 It does not lead to starvation.
 It provides low variance in response time and waiting time.
 

Disadvantages-
 

 It causes long waiting time for the cylinders just visited by the head.
 It causes the head to move till the end of the disk even if there are no requests to be
serviced.
PRACTICE PROBLEM BASED ON SCAN DISK
SCHEDULING ALGORITHM-
 

Problem-
 
Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124,
65, 67. The SCAN scheduling algorithm is used. The head is initially at cylinder number 53
moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered
from 0 to 199. The total head movement (in number of cylinders) incurred while servicing
these requests is _______.
 

Solution-
 

 
Total head movements incurred while servicing these requests
= (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) + (183 – 124) + (199 – 183) +
(199 – 41) + (41 – 14)
= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 158 + 27
= 331
 
Alternatively,
Total head movements incurred while servicing these requests
= (199 – 53) + (199 – 14)
= 146 + 185
Consider a disk with 200 tracks and the queue has random
requests from different processes in the order:
Q1. 55, 58, 39, 18, 90, 160, 150, 38, 184

Initially arm is at 100. Find the Average Seek length using FIFO, SSTF, SCAN 

Q2. Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is : 50

Q3. Suppose the R/W head is at track 63, moving towards track number 175. The disk queue
contains request for 100,175,51,133,8,140,73,77. Find the total number of head movements to
satisfy the request using algorithms

Q4. A disk queue with requests for I/O to blocks on cylinders 23, 89, 132, 42, 187 With disk
head initially at 100