When a
disk head is searching for a particular spot on a disk, the movement of the head is the slowest part. Where to go next is a question that
programmers ask. If you always go to the closest request on the disk after servicing the current request, you will
inevitably starve the outer edges of the disk, because it is rare that that is ever the closest point on the disk.
The solution to this is to have the disk head emulate an elevator.
- Start heading in one direction (up).
- Service all requests that can be done as you are heading up to the highest requested spot.
- If a request for a spot that is just down of your current position occurs, ignore it until the down pass.
- Once servicing the top request, turn around and start going back down.
- Continue handling requests until the lowest request is reached.
- Repeat
This is the same
methodology that an elevator uses - when it is going up, it continues going up until there are no
request for higher
floors than it is on. Then it stars going down handling requests until there are no requests for floors lower than the one it is on.
As mentioned, this does present itself in some sort of radial traveling salesman problem. However, this is a very special case of the traveling salesman problem that is not typically dealt with - not all the stops are known at start up.
In the classic traveling salesman problem, there are several cities with distances between them and the goal is to find the shortest route touching each one in turn. This has been proven to be NP-Hard.
/\ /\ /\
/ \ / \/ \ ...
\ /\ / \ /
\/ \/ \/
-- Time -->
The head on a disk can be thought of as traveling in constant loops about the
surface of the disk (see above). The head moves up and down, though through time. Though another way to look at even a simpler request would be to assume that the two ends of the disk are constantly being requested, thus making it look like this:
/\ /\
/ \ / \
/ \ / ...
/ \/
If this was the case, it would be possible to think of it as a very simple loop, starting at the bottom, going to the top, turning around, and going to the bottom again.
* *
* *
* *
* *
* *
* *
The nature of this actual makes it unnecessary for more
complex approaches to be taken. Given a circle with points on it to travel to, the shortest route for a disk head or traveling salesman to take is that of a
circle itself. It is thus unnecessary to run through thousands of
iterations to see if there is a better
route.
One of the critical parts of the elevator algorithm is its simplicity and the speed at which decisions are made. The logic for this must be handled in the drive itself. Within the confines of embedded systems, simplicity is king. The simpler the logic, the better.
Because of the constantly changing landscape for the disk head (or salesman), a consistent rule must be applied in all cases that is as fair as possible to all destinations. Even the most powerful processors (costing several times more than the largest disk drives) would take far too long to work out a new plan of where to go when and would thus be even slower than the simplistic model that exists now. It is quite possible that a faster algorithm can be made that is equally fair to all requests - though the sacrifice in speed with the components available today is much greater than any possible gain.
Storage space on a single drive has reached 137 GB with seek times around 4.5 milliseconds and transferring over 600 megabits per second. While the largest and fastest drives approach $800 or more, even the speed of gigahertz processors ($400) is not enough even for the 2 gigabyte drives available and would increase the price by 50%.