When a process wants to do disk I/O, it makes a call to the operating system. Since the operation may take some time, the process is put into a blocked state, and the I/O request is sent to a part of the OS called a device driver. If the disk is idle, the operation can be started right away, but if the disk is busy servicing another request, it must be added to a queue of requests and wait its turn. Thus the total delay seen by the process has several components:

• The overhead of getting into and out of the OS, and the time the OS spends fiddling with queues, etc.
• The queuing time spent waiting for the disk to become available.
• The latency spent waiting for the disk to get the right track and sector.
• The transfer time spent actually reading or writing the data.

Although I mentioned a “queue'’ of requests, there is no reason why the requests have to be satisfied first-come first-served. In fact, that is a very bad way to schedule disk requests. Since requests from different processes may be scattered all over the disk, satisfying them in the order they arrive would entail an awful lot of jumping around on the disk, resulting in excessive rotational latency and seek time — both for individual requests and for the system as a whole. Fortunately, better algorithms are not hard to devise.

Shortest Seek Time First (SSTF)

When a disk operation finishes, choose the request that is closest to the current head position (the one that minimizes rotational latency and seek time). This algorithm minimizes latency and thus gives the best overall performance, but suffers from poor fairness. Requests will get widely varying response depending on how lucky they are in being close the current location of the heads. In the worst case, requests can be starved (be delayed arbitrarily long).

The Elevator Algorithm

The disk head progresses in a single direction (from the center of the disk to the edge, or vice versa) serving the closest request in that direction. When it runs out of requests in the direction it is currently moving, it switches to the opposite direction. This algorithm usually gives more equitable service to all requests, but in the worst case, it can still lead to starvation. While it is satisfying requests on one cylinder, other requests for the same cylinder could arrive. If enough requests for the same cylinder keep coming, the heads would stay at that cylinder forever, starving all other requests. This problem is easily avoided by limiting how long the heads will stay at any one cylinder. One simple scheme is only to serve the requests for the cylinder that are already there when the heads gets there. New requests for that cylinder that arrive while existing requests are being served will have to wait for the next pass.

One-way Elevator Algorithm

The simple (two-way) elevator algorithm gives poorer service to requests near the center and edges of the disk than to requests in between. Suppose it takes time T for a pass (from the center to the edge or vice versa). A request at either end of a pass (near the hub or the edge of the disk) may have to wait up to time 2T for the heads to travel to the other end and back, and on average the delay will be T. A request near the “middle'’ (half way between the hub and the edge) will get twice as good service: The worse-case delay is T and the average is T/2. If this bias is a problem, it can be solved by making the elevator run in one direction only (say from hub to edge). When it finishes the request closest to the edge, it seeks all the way back to the first request (the one closes to the hub) and starts another pass from hub to edge. In general, this approach will increase the total amount of seek time because of the long seek from the edge back to the hub, but on a heavily loaded disk, that seek will be so infrequent as not to make much difference.