Disk
Scheduling
Disk requests include
the disk address, memory address, number of sectors to transfer, and whether
the request is for reading or writing. When one request is completed, the
operating system chooses which pending request to service next. Any one of the
several disk scheduling algorithms can be used to make this choice.
1. FCFS Scheduling
This algorithm is fair,
but it generally does not provide the fastest service. Consider, a disk queue
with requests for I/O to blocks on cylinders.
A total of head
movement of 640 cylinders. There are wild swings of the head movement.
2. SSTF Scheduling
Shortest Seek Time
First scheduling is more efficient, but may lead to
starvation if a constant stream of requests arrives for the same general area
of the disk. The SSTF algorithm selects the requests with the least seek time
from the current head position.
SSTF reduces the total
head movement to 236 cylinders, down from 640 required for the same set of
requests under FCFS. However that the distance could be reduced still further
to 208 by starting with 37 and then 14 first before processing the rest of the
requests.
3. SCAN Scheduling
This algorithm is
sometimes called the elevator algorithm. In this algorithm, the disk arm starts
at one end of the disk and moves towards the other end. The direction of head
movement has to be known in addition to the head’s current position.
Under the SCAN
algorithm, If a request arrives just ahead of the moving head then it will be
processed right away, but if it arrives just after the head has passed, then it
will have to wait for the head to pass going the other way on the return trip.
This leads to a fairly wide variation in access times which can be improved
upon.
4. C-SCAN Scheduling
The Circular-SCAN algorithm
improves upon SCAN by treating all requests in a circular queue fashion - Once
the head reaches the end of the disk, it returns to the other end without
processing any requests, and then starts again from the beginning of the disk.
5. LOOK
Scheduling
LOOK scheduling
improves upon SCAN by looking ahead at the queue of pending requests, and not
moving the heads any farther towards the end of the disk than is
necessary.
6. Selection of a
Disk-Scheduling Algorithm
With very low loads all
algorithms are equal, since there will normally only be one request to process
at a time.
For slightly larger
loads, SSTF offers better performance than FCFS, but may lead to starvation
when loads become heavy enough.
For busier systems,
SCAN and LOOK algorithms eliminate starvation problems.
Requests for disk
service can be greatly influenced by the file-allocation method. The location
of directories and index blocks are also important.
