display | more...
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.

  1. Start heading in one direction (up).
  2. Service all requests that can be done as you are heading up to the highest requested spot.
  3. If a request for a spot that is just down of your current position occurs, ignore it until the down pass.
  4. Once servicing the top request, turn around and start going back down.
  5. Continue handling requests until the lowest request is reached.
  6. 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%.

I always wonder if these sort of problems are best solved via genetic algorithms.

Take for example m_turner's excellent description of a possible algorithm above. It seems efficient in it's simplicity, which is easy for us humans to follow, but it is probably missing a lot of potential for improvment. It doesn't adapt to discover which parts of the disk are accessed most often, what is the fastest way to get to points A, B, C, and D (sort of a radial travelling salesman problem), and where errors are likely to occur least/most often, probability guesstimates for the next access. A genetic algorithm would eventually find all of these (and other things you probably would never think of) if it were run long enough on the model.

Elevators themselves also present some interesting problems. An efficient elevator system is actually very complicated, and was the basis of the game Sim Tower by Maxis (the manual mentions some of this). There are special considerations with elevator systems that go beyond the simple elevator algorithm, such as the arrangment of express elevators, number of elevators present, peak usage and off-peak usage patterns, etc.

Log in or register to write something here or to contact authors.