Disk
Scheduling
As we know, a process
needs two type of time, CPU time and IO time. For I/O, it requests the
Operating system to access the disk.However, the operating system must be fare
enough to satisfy each request and at the same time, operating system must
maintain the efficiency and speed of process execution.The technique that
operating system uses to determine the request which is to be satisfied next is
called disk scheduling.
Seek Time
Seek time is the time
taken in locating the disk arm to a specified track where the read/write
request will be satisfied.
Rotational Latency
It is the time taken
by the desired sector to rotate itself to the position from where it can access
the R/W heads.
Transfer Time
It is the time taken
to transfer the data.
Disk Access Time
Disk access time is
given as,
Disk Access Time =
Rotational Latency + Seek Time + Transfer Time
Disk Response Time
It is the average of
time spent by each request waiting for the IO operation.
Purpose of Disk Scheduling
The main purpose of
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.
Goal of Disk Scheduling
Algorithm
- Fairness
- High
throughout
- Minimal
traveling head time
Disk Scheduling Algorithms
The list of various
disks scheduling algorithm is given below. Each algorithm is carrying some
advantages and disadvantages. The limitation of each algorithm leads to the
evolution of a new algorithm.
- FCFS
scheduling algorithm
- SSTF
(shortest seek time first) algorithm
- SCAN
scheduling
- C-SCAN
scheduling
- LOOK
Scheduling
- C-LOOK
scheduling
It is the simplest
Disk Scheduling algorithm. It services the IO requests in the order in which
they arrive. There is no starvation in this algorithm, every request is
serviced.
Disadvantages
The scheme does not
optimize the seek time.
The request may come
from different processes therefore there is the possibility of inappropriate
movement of the head.
Example
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 _______.
Number of cylinders
moved by the head
= (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 Scheduling Algorithm
Shortest seek time first (SSTF)
algorithm selects the disk I/O request which requires the least disk arm
movement from its current position regardless of the direction. It reduces the
total seek time as compared to FCFS.
It allows the head to move to the closest
track in the service queue.
Disadvantages
It may cause
starvation for some requests.
Switching direction
on the frequent basis slows the working of algorithm.
It is not the most
optimal algorithm.
Example
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
SCAN and C-SCAN algorithm
Scan Algorithm
It is also called as Elevator
Algorithm. In this algorithm, the disk arm moves into a particular direction
till the end, satisfying all the requests coming in its path,and then it turns
back and moves in the reverse direction satisfying requests coming in its path.
It works in the way an elevator works,
elevator moves in a direction completely till the last floor of that direction
and then turns back.
Example
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
= (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
= 331
C-SCAN algorithm
In C-SCAN algorithm, the arm of the
disk moves in a particular direction servicing requests until it reaches the
last cylinder, then it jumps to the last cylinder of the opposite direction
without servicing any request then it turns back and start moving in that
direction servicing the remaining requests.
Example
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
= (65 – 53) + (67 – 65) + (98 – 67) +
(122 – 98) + (124 – 122) + (183 – 124) + (199 – 183) + (199 – 0) + (14 – 0) +
(41 – 14)
= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 27
= 386
Alternatively,
Total head movements incurred while
servicing these requests
= (199 – 53) + (199 – 0) + (41 – 0)
= 146 + 199 + 41
= 386
Look Scheduling
It is like SCAN scheduling Algorithm to
some extant except the difference that, in this scheduling algorithm, the arm
of the disk stops moving inwards (or outwards) when no more request in that
direction exists. This algorithm tries to overcome the overhead of SCAN
algorithm which forces disk arm to move in one direction till the end
regardless of knowing if any request exists in the direction or not.
Example
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
_______.
Total head movements incurred while servicing these
requests
= (65 – 53) + (67 – 65) + (98 – 67) +
(122 – 98) + (124 – 122) + (183 – 124) + (183 – 41) + (41 – 14)
12 + 2 + 31 + 24 + 2 + 59 + 142 + 27
= 299
Alternatively,
Total head movements incurred while
servicing these requests
= (183 – 53) + (183 – 14)
= 130 + 169
= 299
C Look Scheduling
C Look Algorithm is similar to C-SCAN
algorithm to some extent. In this algorithm, the arm of the disk moves outwards
servicing requests until it reaches the highest request cylinder, then it jumps
to the lowest request cylinder without servicing any request then it again
start moving outwards servicing the remaining requests.
It is different from C SCAN algorithm
in the sense that, C SCAN force the disk arm to move till the last cylinder
regardless of knowing whether any request is to be serviced on that cylinder or
not.
Example
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
_______.
= 12 + 2 + 31 + 24 + 2 + 59 + 169 + 27
= 326
Alternatively,
Total head movements incurred while
servicing these requests
= (183 – 53) + (183 – 14) + (41 – 14)
= 130 + 169 + 27
= 326
Try to solve the above methods with 200 cylinders i.e initial track =0 and final track = 199
Disk queue track nos : 23 89 132 42 187
initial head position is at position 100
Total seek time in FCFS = 421
Total seek time in SSTF = 273
Try to solve the above methods with 200 cylinders i.e initial track =0 and final track = 199
Disk queue track nos : 23 89 132 42 187
initial head position is at position 100
Total seek time in FCFS = 421
Total seek time in SSTF = 273
Total seek time in SCAN = 275
Total seek time in C-SCAN = 387
Total seek time in LOOK = 255
Total seek time in C-LOOK = 317
