Disk
Scheduling
Algorithms
Disk Scheduling
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.
Types Of Disk Scheduling
algorithms
1.FCFS (First Come First Serve)
2.SSTF (Shortest Seek Time First)
3.SCAN (Elevator Algorithm)
4.C-SCAN (CIrcular SCAN)
FCFS (First Come First Serve)
FCFS is the simplest of all Disk Scheduling Algorithms. In
FCFS, the requests are addressed in the order they arrive in
the disk queue.
Ex:-
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is: 50
So, total overhead movement is
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-
16)+(190-16) = 642
Advantages of FCFS :-
1.Every request gets a fair
chance
2.No indefinite
postponement
Disadvantages of FCFS
1.Does not try to optimize seek
time
2.May not provide the best
possible service
SSTF (Shortest Seek Time First)
In SSTF (Shortest Seek Time First), requests having the shortest seek
time are executed first. So, the seek time of every request is calculated
in advance in the 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
the system.
EX:-
Suppose the order of request is- (82,170,43,140,24,16,190) And current
position of Read/Write head is: 50
So, total overhead movement is
(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-
140)+(190-170) =208
Advantages of Shortest Seek Time First
1.The average Response Time decreases
2.Throughput increases
Disadvantages of Shortest Seek Time
First
1.Overhead to calculate seek time in
advance Can cause Starvation for a request
if it has a higher seek time as compared to
incoming requests.
2.The high variance of response time as SSTF
favors only some requests.
S C A N ( El ev a t o r A l g o r i t h m )
In the SCAN Algorithm the disk arm moves in a particular direction and
services the requests coming in its path and after reaching the end of the
disk, it reverses its direction and again services the request arriving in its
path. So, this algorithm works as an elevator and is hence also known as
an elevator algorithm. As a result, the requests at the midrange are
serviced more and those arriving behind the disk arm will have to wait.
Ex:-
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the
Read/Write arm is at 50, and it is also given that the disk arm should
move “towards the larger value”.
So, total overhead movement is
(199-50) + (199-16) = 332
Advantages of SCAN
1.High throughput.
2.Low variance of response.
3.time Average response time.
Disadvantages of SCAN
1.Long waiting time for requests for locations
just visited by disk arm.
C-SCAN (CIrcular SCAN)
In the 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.
These situations are avoided in the CSCAN algorithm in which the
disk arm instead of reversing its direction goes to the other end of
the disk and starts servicing the requests from there. So, the disk
arm moves in a circular fashion and this algorithm is also similar to
the SCAN algorithm hence it is known as C-SCAN (Circular SCAN).
Ex:-
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50,
and it is also given that the disk arm should move “towards the larger value”.
So, the total overhead movement (total distance covered by the disk arm)
is calculated as:
(199-50) + (199-0) + (43-0) = 391
