Thursday, July 10, 2008

Hard disks and Elevators

Now, that's a weird title. What follows may sound absurd to some people. But having studied computer science, it makes sense to me.

Many of us work in high rise buildings and more often than not, we take elevators to get to our places of work. My office building has 6 elevators, and 2 control switches - each switch, when pressed, sends request to 3 elevators and one of them eventually services the request.

Recalling from the operating systems course in engineering, the disk request scheduling algorithm heavily borrows from the algorithm used by elevators to service requests. Most of us computer literate people should know that the disk request scheduling algorithm tries to minimize the number of seeks and the distance per seek. The elevator behaves somewhat similarly. For any request, among many elevators receiving the request, the one closest to the origin-place of request services it. Also, if an elevator is already moving in the direction of the origin-place of the request, it handles the request instead of an idle elevator at the same level.

Now, if there was only one elevator in question, then its guaranteed that it would handle requests optimally. But with many elevators and more than one control switch to summon the elevators, the usage could become non-optimal, depending on how people use them. Some of the common things that people do that results in non-optimal usage are:

1) Summoning more than one elevator (activating more than one control switch) for one request
2) Summoning a elevator(s) which are farther away from the origin-place of the request

Think of the elevators in your building as disks, all of them having the same data in them. The amount of distance the elevators need to travel before servicing a request as the seek of a disk. Since there is more than one elevator to choose from, we could choose one (and only one, not more than one! Refer point 1 above) which is closest to the place from which the request is being made.

1) Avoids non-optimal usage - saves power! (GO GREEN!)
2) Provides quicker service!

1) You could lose 5 seconds in looking at positions of all elevators before making a decision to summon a particular elevator - This could be offset by point 2 in advantages. Also, is 5 seconds too much, considering the slightly more weighed advantages?

There are many places like these where we can apply knowledge of computer science, in our daily lives. Its surprising that most of us do not.

1 comment:

Shantanu said...

Digging further...

The it really a disadvantage?

I assume the calculation is a CPU and memory intensive task vis-a-vis a mechanical device movement(the head of the disk).

With power of machines increasing on CPU and memory its worth the processing.

Starting a tangential line of thought:
Reiser FS which is respected highly for its efficient algorithms makes extensive use of elevator algorithm. The creator of this FS Hans Reiser talks very extensively of Elevator algorithm.

PS: Hans Reiser's life is a weird story, true nonetheless.