Disk scheduling

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.

SCAN

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.

LOOK

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 requested.

Distributed Computing

In distributed computing, there are several, geographically remote autonomous computers that have to act in concert to complete a task. The network and the computers are unreliable, but the system has to struggle on regardless.

In distributed computing, everything gets trickier!

• The algorithms are harder to design because the work has to be spread out and synchronised. The computing `agents' have a degree of autonomy and must agree to act in concert.
• The algorithms' performance and complexity are harder to analyse because communication costs come into play.
• Problems such as deadlock afflict centralised computer systems, but in distributed systems, deadlock is harder to detect and harder to break.
• Most importantly, distributed systems are unreliable. A centralised computer system is either working OK or completely failed, whereas a distributed system is hardly ever in either of these two states. At any one time, parts of the network and some of the computers will be working, whilst other components will be broken.

If it's that hard, why bother? Well, put cynically, it keeps us in a job. But there are other good reasons.

• Some applications are inherently distributed. Consider, for example, automated transactions between different companies' computer systems.
• Some applications are distributed for performance reasons. In a client/server computing environment, it may be more convenient to have some computing power on the end-users' desktop machines and some in the server host machines.

Distributed computing concepts such as distributed agreement protocols and distributed deadlock detection, are in widespread use in industry, but very few people in industry understand the limitations of these techniques. The others get nasty shocks when their systems collapse around their ears!