Session 16: Disk scheduling

Textbook: Section 3.7.2

First come, first serve
Shortest seek time first
Elevator algorithm
Single-direction elevator algorithm
Fancier alternatives

Disk scheduling is a very interesting topic. Here's the basic scenario: We have a disk arm that moves quite slowly. In fact, it takes longer to move the arm farther. We also have an erratic stream of disk requests. How should we decide where to move the arm next?

For the following, we're going to think of the disk having 100 cylinders, numbered 0 through 99. And we'll think of the time the disk arm takes to be proportional to the distance it moves.

First come, first served

The simplest technique - and the one that Minix uses - always selects the oldest request. This can be very bad. For example, say the requests come in the order 0, 99, 0, 99, 0, 99 in rapid succession. Then the disk is moving across the entire disk repeatedly, and as a result the OS slows down processes a lot more for accessing the disk than it must.

First come, first served has the virtue of being simple, but it has the dire disadvantage of having a horrible worst case.

Shortest seek time first

Another technique says that the OS should always choose the cylinder that is closest to the arm's current position. For the above example, the OS would choose to service the three requests on sector 0 first, and then it would service the three requests on sector 99. As a result, it would traverse the disk only once, and there'd be no seek time penalty at all for the rest of the time.

So this can do very well. Unfortunately, it tends to get in a rut, leaving some requests to wait a very long time. If you think of requests coming quickly at random, the OS will generally stay near where it began, since it is basically doing a random walk. It won't move across the disk.

Say, for example, it happens that there are three processes that simply generate random disk requests. Thus, at any time, there are three requests in the pool. Also, say the arm begins at cylinder 30.

                 current   next
p1 p2 p3 p4 p5  location location
93 35 69 22 78     30       35
93 10 69 22 78     35       22
93 10 69 34 78     22       10
93 89 69 34 78     10       34
93 89 69 26 78     34       26
93 89 69 42 78     26       42
In this example, p2 successfully read from three cylinders, and p4 read from three. But p1, p3, and p5 got nothing done. This algorithm has not treated the processes fairly.

Elevator algorithm

A more sophisticated approach takes its inspiration from the world of elevators. Here, the OS attributes a ``direction'' to the arm - it's either moving inward or outward. When the OS needs to choose the next request to service, it takes the next cylinder in the current direction of the arm. If there aren't any such requests, it reverses the direction of the arm and goes the other way.

For example, let's say our arm in our previous example is currently going downward, and we have the same sequence of requests.

                 current   next
p1 p2 p3 p4 p5  location location
93 35 69 22 78     30       22
93 35 69 10 78     22       10
93 35 69 34 78     10       34     arm switched direction
93 35 69 89 78     34       35
93 26 69 89 78     35       69
93 26 42 89 78     35       42
In this example, p2 was serviced twice, p3 was services once, and p4 was services three times. Both p1 and p5 are still waiting, but we can tell that their turn is coming soon.

Though the elevator algorithm takes longer for the average request, it won't starve a process for the sake of others.

C-SEEK

This is just a slight modification on the elevator algorithm that works very well also. It only allows the arm to travel in one direction. For example, if the arm can travel only outward, it will always move to the next cylinder outward. If there are no blocks that way, it will move to the innermost requested cylinder and start working itself outward again. (You can think of this as a ``wraparound'' algorithm.)

                 current   next
p1 p2 p3 p4 p5  location location
93 35 69 22 78     30       22
93 35 69 10 78     22       10
93 35 69 34 78     10       93     arm went to innermost cylinder
89 35 69 34 78     93       89
26 35 69 34 78     89       78
26 35 69 34 42     78       69
In this example, the disk managed to serve every process at least once, except p2.

Alternatives

Fancier disks can tell the CPU where the platter has currently rotated. This can enable scheduling on the current cylinder. Moreover, it can potentially affect the arm scheduling, as it may be advantageous to go slightly farther.

Mirrored disks add a bigger complication to the mix, as now you essentially have two arms moving over the disk.