Disk arm scheduling (section 5.3.1)

We've looked at the device independant parts of an operating system's I/O code. For example, the filesystem code, which works in terms of blocks, and ignores the sectors, tracks and cylinders of the physical disk; that code is device independant: a block may not even correspond to a physical sector (it may be composed of several physical sectors). Also, the block, caching code, and the naming system; these do not care about the mechanical nicities of disk drives or laser printers.

Give a thought though to the poor device driver of a hard disk drive. It is responsible for creating this illusion of a block device to the device-independant parts of the OS. It is constantly bombarded by requests to read and write blocks. It must then translate these block requests into decisions to read or write sectors (or whole tracks), moving the read/write head of the disk as necessary.

The high-level software just wants blocks moved as fast as possible. The device driver knows that this will involve the slow process of seeking the heads to the correct cylinder, then issuing a read or a write request. If it has received several block requests, the device driver is free to satisfy them in any order. To minimise the amount of head movement, or to increase throughput, it may decide to satisfy them in a different order than that in which they were issued.

Remember that there may be several tracks in a single cylinder, and many sectors per track, so many requests may be satisfied at each cylinder.

FCFS

With First-Come-First-Served disk arm scheduling, we simply fulfil the requests in the order in which they were received from the device-independent software. This is the simplest approach, and in a single-tasking system it may well be the best. The problems occur when several tasks are accessing different files, and the disk arm must move back and forth between several locations on the disk. This makes nasty grinding noises.
Shortest seek first

SSF

Shortest-seek first. Since it takes some time to satisfy requests, several requests may arrive while we are busy satisfying the last one. In principle, therefore, the device driver may choose which request---of those waiting in the request queue---to satisfy first. Instead of simply taking the first one from the queue, one approach is to go for the request which is for the closest cylinder to that at which the read/write head is currently located.

This is shortest-seek first. It cuts down total arm motion dramatically (by about half). Unfortunately this algorithm falls prey to one flaw: when there are many requests pending, the head will tend to hang around the middle of the disk, going for the nearest cylinders, and avoiding far off ones. This means that some requests, those for cylinders to the edges of the disk, may have to wait a long time for service.

Elevator algorithm

So if the lifts in the Livvy tower used the same algorithm, at busy times, they'd all head for the nearest floor to be visited, and end up mostly hovering around floors 5 and 6, with the occasional forray to higher and lower floors. Although total lift movement would be greatly decreased, over a first-come-first-served algorithm, fairness would decrease (and average journey time would probably increase dramatically).

For this reason, lifts and many device drivers use the so-called elevator algorithm. In this scheme, the disk head (or lift car) moves across the disk (or building), satisfying all the requests in one direction, before turning around, and satisfying the requests in the other direction... and so on.

Sometimes known as the SCAN algorithm---'SCAN' doesn't stand for anything.

One variation on the elevator algorithm is to only scan the disk in one direction: when the read/write head gets to one end of the disk, it moves straight back to the other end of the disk, without servicing any requests on the way, and starts again. This algorithm, sometimes known as the C-SCAN (circular scan) algorithm, provides for a smaller variance in response time.

Hardware

Actual disk controller hardware is getting increasingly sophisticated, in terms of caching blocks and tracks, and scheduling disk head movement. If the disk controller is doing all this work, the operating system device driver does not.

last updated 23 April 1998