On Fri, Jun 21, 2002 at 03:31:19PM +0200, Olaf Seibert wrote:
> In Operating Systems lectures at the university they taught me about the
> "elevator algorithm". Basically it just means that during one pass
> through the queue you seek in the "up" direction only, and during the
> next pass in the "down" direction only. So your scenario becomes
> something like this:
> 
> - a) a bunch of sequential I/O requests in the middle of the disk are queued
>   I/O to disk are started, and we go do something else while it complete.
>   Assume we go in the "up" direction.
> - b) while waiting for a) we queue a single I/O for the end of the disk.
>   With write ordering it's appenned to the queue (we're still in the
>   middle of the disk).
> - c) another bunch of sequential I/O for the middle of the disk are queued.
>   Some of them are queued in front of the "current" position in the

Almost all of them, it's a sequential write, remember.

>   queue and will be serviced before we get to request b).
> - d) The request from b) is serviced, and now we start going through the
>   queue backwards,

No, because while we a servicing a+c, some more requests come in, which
are queued before b)

The problem is that there can be an arbitrary amount of request inserted
before b), so we can't make any assuption about how many time will be needed
for b) to be handled.

> 
> I cannot imagine why this basic textbook stuff would not already be
> implemented...

It is implemented, the problem is, precisely, that it's a bit too basic :)

--
Manuel Bouyer, LIP6, Universite Paris VI.           Manuel.Bouyer@lip6.fr
--