Part 2 of 7 · 2 min read
Why order matters
Think of a lift with people waiting on many floors. If it serves them in the order they pressed the button, it runs up and down all day. If it serves the floors on its way, it carries everyone with much less travel. The analogy stops in one place: a lift can refuse to stop, while an OS must serve every disk request eventually.
In plain words: While the drive serves one request, more arrive. The OS keeps them in a queue and picks the next one. A disk is organised in cylinders, which are the set of tracks that are under all the heads at one arm position. Moving the arm one cylinder costs a little time, and moving it far costs more. A good order keeps the total movement small, and this lowers the average wait of every request.
A worked example (made up to show the idea). The disk has 200 cylinders, numbered 0 to 199. The head is at cylinder 50. Eight requests wait, in the order they arrived: 95, 180, 34, 119, 11, 123, 62, 64. A fixed cost of 0.05 ms per cylinder moved is assumed, so 100 cylinders of movement cost 5 ms.
The key lines. The cost of an order is the sum of the distances between consecutive stops. Section 2 computes it for two simple orders and sections 3 and 4 for the elevator orders.
Disk scheduling
Disk scheduling is the choice, made by the OS or the drive, of the order in which waiting I/O requests are sent to a disk. For a hard disk the aim is to reduce the arm movement and the rotational wait, and to keep the wait of every request bounded.
Example: with requests for cylinders 95 and 62 waiting and the head at 50, serving 62 first moves the arm 12 cylinders and then 33, and serving 95 first moves it 45 and then 33.
Check yourself: 1. What is a cylinder? 2. Why does the order of the queue change the total cost, although the set of requests is the same? 3. What would be the total movement of the worked example if the head served only 95 and 62, in that order?