Figure 5.7 Tracks and Sectors on Floppy Disks and Hard Disks

Operating System Fundamentals
73
The Elevator Algorithm
Now that we know how magnetic disks are physically structured, we can turn our attention to how the interrupt handler actually handles requests to retrieve information from disk resources. This is typically done using the elevator algorithm. For this discussion, we will concentrate on requests for data from a hard disk. However, it should be noted that the elevator algorithm can be used by the interrupt handler to handle requests for data from other storage devices, as well. The elevator algorithm is a strategy used by the interrupt handler to find data on a storage device when it is requested by a process. Using a first come first serve strategy to fill requests for data that have accumulated in the shared request folder is not an effective strategy, because it would actually take too long to constantly change the direction of travel of a disks read/write head. This strategy would also increase wear and tear on a disk. Instead, the elevator algorithm organizes data requests based on the data‘s cylinder location on a disk. Using the elevator algorithm, the read/write head will only move in one direction at a time, and will pickup requested data as it moves from cylinder to cylinder. The actual decision making process used by the interrupt handler is
1. If the request queue is empty, exit interrupt handler
2. If read/write arms direction is UP, move from the current cylinder (just completed request) to the next higher cylinder to perform that request.
3. If direction is DOWN, move the arm from the current cylinder (just completed request) to next lower cylinder to perform that request.
4. If no request lies in current direction, reverse direction. Using this algorithm, we can examine the handling of requests for data from cylinders on a hard disk. Assume that the original request order in the shared request folder is for data from the following cylinders

Download 2.34 Mb.

Share with your friends: