Operating Systems

(KCS-401)
Disk Scheduling

By

Puneet Kumar Goyal

Assistant Professor
Department of Information Technology
Ajay Kumar Garg Engineering College, Ghaziabad
 Magnetic Disk in Computer
Architecture-
Magnetic disk is a storage device that is used to write, rewrite and access data.
It uses a magnetization process.

Architecture-

✓ The entire disk is divided into platters.

✓ Each platter consists of concentric circles called as tracks.
✓ These tracks are further divided into sectors which are the smallest divisions
in the disk.
✓ A cylinder is formed by combining the tracks at a given radius of a disk pack.
Magnetic Disk in Computer Architecture-
 Magnetic Disk in Computer
Architecture-
✓ There exists a mechanical arm called as Read / Write head.
✓ It is used to read from and write to the disk.
✓ Head has to reach at a particular track and then wait for the rotation of the
platter.
✓ The rotation causes the required sector of the track to come under the head.
✓ Each platter has 2 surfaces- top and bottom and both the surfaces are used to
store the data.
✓ Each surface has its own read / write head.
Magnetic Disk in Computer
Architecture-
Disk Scheduling-
Disk scheduling is a technique used by the operating system to schedule multiple
requests for accessing the disk.

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.
Disk Performance Parameters-

The time taken by the disk to complete an I/O request is called as disk service time or disk
access time.
1. Seek Time-

✓ The time taken by the read / write head to reach the desired track is called as seek time.
✓ It is the component which contributes the largest percentage of the disk service time.
✓ The lower the seek time, the faster the I/O operation.

2. Rotational Latency-
✓ The time taken by the desired sector to come under the read / write head is called
as rotational latency.
✓ It depends on the rotation speed of the spindle.

3. Data Transfer Rate-

✓ The amount of data that passes under the read / write head in a given amount of time is
called as data transfer rate.
✓ The time taken to transfer the data is called as transfer time.
Seek Time-

✓ The time taken by the read / write head to reach the desired track is called as seek time.
✓ It is the component which contributes the largest percentage of the disk service time.
✓ The lower the seek time, the faster the I/O operation.

2. Rotational Latency-
The time taken by the desired sector to come under the read / write head is called
as rotational latency.
•It depends on the rotation speed of the spindle.

3. Data Transfer Rate-

The amount of data that passes under the read / write head in a given amount of time is
called as data transfer rate.
•The time taken to transfer the data is called as transfer time.
 Disk Scheduling-
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.
 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 _______.
 FCFS Disk Scheduling Algorithm-

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
 FCFS Disk Scheduling Algorithm-

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
FCFS Disk Scheduling Algorithm-
 Disk Scheduling-
SSTF Disk Scheduling Algorithm(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.
 Problem-01: SSTF
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 _______.

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: SSTF

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

Ans is 119ms
SSTF
SSTF

Ans is 236
 SCAN Disk Scheduling Algorithm-
✓ 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. SCAN Algorithm is also called as Elevator Algorithm.
Advantages-
✓ It is simple, easy to understand and implement.
✓ It does not lead to starvation.

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.
 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 _______.

Total head movements incurred while servicing these

requests = (199 – 53) + (199 – 14)
= 146 + 185
= 331
 SCAN Disk Scheduling Algorithm-

Illustration shows total head movement of

236 cylinders.
 LOOK Disk Scheduling Algorithm-
✓ LOOK Algorithm is an improved version of the SCAN Algorithm.
✓ Head starts from the first request at one end of the disk and moves towards the last
request at the other end servicing all the requests in between.
✓ After reaching the last request at the other end, head reverses its direction.
✓ It then returns to the first request at the starting end servicing all the requests in
between. The same process repeats.
Advantages- It does not causes the head to move till the ends of the disk when there are
no requests to be serviced.
✓ It provides better performance as compared to SCAN Algorithm.
✓ It does not lead to starvation.
 LOOK Disk Scheduling Algorithm-
Disadvantages-
✓ There is an overhead of finding the end requests.
✓ It causes long waiting time for the cylinders just visited by the head.

Problem-

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14,
124, 65, 67. The LOOK 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 _______.
LOOK Disk Scheduling Algorithm-

Total head movements incurred while servicing these

requests = (183 – 53) + (183 – 14)
= 130 + 169
= 299
 CSCAN Disk Scheduling Algorithm-
✓ Circular-SCAN Algorithm is an improved version of the SCAN Algorithm.
✓ 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.
✓ It then returns to the starting end without servicing any request in between.
✓ The same process repeats.
Advantages-
✓ The waiting time for the cylinders just visited by the head is reduced as compared to
the SCAN Algorithm.
 CSCAN Disk Scheduling Algorithm-
✓ It provides uniform waiting time.
✓ It provides better response time.
Disadvantages-
It causes more seek movements as compared to SCAN Algorithm.
It causes the head to move till the end of the disk even if there are no requests to be
serviced.
 Problem-
Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124,
65, 67. The C-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 _______.

Total head movements incurred

while servicing these requests
= (199 – 53) + (199 – 0) + (41 – 0)
= 146 + 199 + 41
= 386
 CLOOK Disk Scheduling Algorithm-
C-LOOK Disk Scheduling Algorithm-
✓ Circular-LOOK Algorithm is an improved version of the LOOK Algorithm.
✓ Head starts from the first request at one end of the disk and moves towards the last
request at the other end servicing all the requests in between.
✓ After reaching the last request at the other end, head reverses its direction.
✓ It then returns to the first request at the starting end without servicing any request in
between.
✓ The same process repeats.
 CLOOK Disk Scheduling Algorithm-
Advantages-
✓ It does not causes the head to move till the ends of the disk when there are no requests
to be serviced.
✓ It reduces the waiting time for the cylinders just visited by the head.
✓ It provides better performance as compared to LOOK Algorithm.
✓ It does not lead to starvation.
Disadvantages-

There is an overhead of finding the end requests.

Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14,
124, 65, 67. The C-LOOK 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 _______.

Total head movements incurred while

servicing these requests
= (183 – 53) + (183 – 14) + (41 – 14)
= 130 + 169 + 27
= 326