Disk Scheduling

A disk is a magnetic storage device which has a number of platters (or surfaces). The entire assembly of platters rotates as a unit at high speeds (typically 5000-10000 RPM for a fixed disk.) The surface of each platter is organised as a concentric group of magnetic tracks on which data can be stored. Each track is divided into a number of blocks of fixed size (typically 1024 bytes) in which the data is stored. A block is the smallest amount of data that can be read from or written to the disk in a single I/O operation.

Each disk surface has a read/write head which can move linearly across the surface. Data from the disk is requested by block number. The disk controller moves the head to the correct track and then waits for the correct block to pass underneath it for access.

The slowest part of accessing a disk block is physically moving the head to the correct track This is called the seek time. In a multitasking system, requests to access different parts of the disk arrive from different processes. Correct scheduling of these requests can reduce the average seek time by reducing the average distance the head has to travel.

Note: In contrast to CPU scheduling, the track request is known in advance, whereas the CPU burst time is not. Also, the servicing of a track/block request is not preemptable, without restarting the service request.

To demonstrate some of the algorithms which may be applied to servicing a disk request queue, consider the following example:-


Example
Say the following set of requests to different tracks on the disk are waiting for service:-

98, 183, 37, 122, 14, 124, 65, 67

and say the read/write head is initially at track 53. How might we order these requests?

We must consider fairness and performance. We don't want to starve any requests for particular areas of the disk, but at the same time we want to reduce the average seek time.

First Come First Served (FCFS)
With this algorithm we would get the following head movements:-

Shortest Seek Time First (SSTF)
Choose the request which is closest to the current head position. With this algorithm we would get the following head movements:-

Note that on average, the head will be somewhere around the middle of the disk and that this algorithm therefore favours requests in this area. The outer and inner tracks of the disk may therefore be starved.


SCAN Algorithm
The head moves in one direction, either to the center or to the outermost track, servicing requests as it passes the corresponding tracks. It then turns around and repeats this in the other direction. With this algorithm, assuming the head is moving in the direction of increasing track numbers and track numbers are from 0..200, we would get the following head movements:-

Note that this results in an uneven distribution of service across the disk surface. For example, when the head services tracks at the centre it is unlikely that new requests will have arrived for these tracks in the short time it takes the head to turn around and service these tracks again in the other direction. Likewise if the head has just serviced the outermost track and is moving inwards, requests which arrive just behind the current head position take almost two disk scans to receive service.

C-SCAN Algorithm
This algorithm attempts to regularise the distribution of service offered by SCAN. When the head has completed movement in one direction, it flys back quickly to the start, without scaning the surface, and begins the scan again in the same direction. Each track then has the same time between consecutive visits by the head.
With this algorithm, we get the following head movements:-


LOOK Algorithm (Elevator Algorithm)
The LOOK algorithm is the same as SCAN except that where SCAN always continues to the last track in a particular direction before turning around, the LOOK algorithm simply checks to see if there are anymore requests in that direction before turning around.
With this algorithm we get the following head movements:-

C-LOOK Algorithm
The C-LOOK algorithm is the same as C-SCAN except that where C-SCAN always continues to the last track in a particular direction before flying back, the C-LOOK algorithm simply checks to see if there are anymore requests in that direction before flying back.
With this algorithm we get the following head movements:-