In multiprogramming systems several different processes may want to
use the system's resources simultaneously. For example, processes
will contend to access an auxiliary storage device such as a disk.
The disk drive needs some mechanism to resolve this contention,
sharing the resource between the processes fairly and efficiently.
A magnetic disk consists of a collection of platters which rotate on
about a central spindle. These platters are metal disks covered with
magnetic recording material on both sides. Each disk surface is
divided into concentric circles called tracks. Each track is
divided into sectors where information is stored. The
reading and writing device, called the head moves over the
surface of the platters until it finds the track and sector it
requires. This is like finding someone's home by first finding the
street (track) and then the particular house number (sector). There
is one head for each surface on which information is stored each on
its own arm. In most systems the arms are connected together
so that the heads move in unison, so that each head is over the same
track on each surface. The term cylinder refers to the
collection of all tracks which are under the heads at any time.
In order to satisfy an I/O request the disk controller must first move
the head to the correct track and sector. Moving the head between
cylinders takes a relatively long time so in order to maximise the
number of I/O requests which can be satisfied the scheduling policy
should try to minimise the movement of the head. On the other hand,
minimising head movement by always satisfying the request of the
closest location may mean that some requests have to wait a long time.
Thus, there is a trade-off between throughput (the average
number of requests satisfied in unit time) and response time
(the average time between a request arriving and it being satisfied).
Various different disk scheduling policies are used:
First Come First Served (FCFS)
The disk controller processes the I/O requests in the order in which
they arrive, thus moving backwards and forwards across the surface of
the disk to get to the next requested location each time. Since no
reordering of request takes place the head may move almost randomly
across the surface of the disk. This policy aims to minimise response
time with little regard for throughput.
Shortest Seek Time First (SSTF)
Each time an I/O request has been completed the disk controller
selects the waiting request whose sector location is closest to the
current position of the head. The movement across the surface of the
disk is still apparently random but the time spent in movement is
minimised. This policy will have better throughput than FCFS but a
request may be delayed for a long period if many closely located
requests arrive just after it.
The drive head sweeps across the entire surface of the disk, visiting
the outermost cylinders before changing direction and sweeping back to
the innermost cylinders. It selects the next waiting requests whose
location it will reach on its path backwards and forwards across the
disk. Thus, the movement time should be less than FCFS but the policy
is clearly fairer than SSTF.
Circular SCAN (C-SCAN)
C-SCAN is similar to SCAN but I/O requests are only satisfied when the
drive head is travelling in one direction across the surface of the
disk. The head sweeps from the innermost cylinder to the outermost
cylinder satisfying the waiting requests in order of their locations.
When it reaches the outermost cylinder it sweeps back to the innermost
cylinder without satisfying any requests and then starts again.
Similarly to SCAN, the drive sweeps across the surface of the disk,
satisfying requests, in alternating directions. However the drive now
makes use of the information it has about the locations requested by
the waiting requests. For example, a sweep out towards the outer edge
of the disk will be reversed when there are no waiting requests for
locations beyond the current cylinder.
Circular LOOK (C-LOOK)
Based on C-SCAN, C-LOOK involves the drive head sweeping across the
disk satisfying requests in one direction only. As in LOOK the drive
makes use of the location of waiting requests in order to determine
how far to continue a sweep, and where to commence the next sweep.
Thus it may curtail a sweep towards the outer edge when there are
locations requested in cylinders beyond the current position, and
commence its next sweep at a cylinder which is not the innermost one,
if that is the most central one for which a sector is currently