On Thu 20 Jun 2002 at 21:26:51 +0200, Manuel Bouyer wrote:
> This is exacly what we have now: ordered per devices. And this is in part
> responsible of the behavior whe have now (I tried disabling completely
> write ordering, handling requests in the order they come: this helps a bit
> for the problem we're talking about). Here's an example of what happens:
> - a) a bunch of sequencial 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.
> - 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).
> - another bunch of sequential I/O for the middle of the disk are queued.
>   Because of write ordering, they're inserrted between a) and b).

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
  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,
- e) eventually reaching the remaining requests from c).

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

-Olaf.
-- 
___ Olaf 'Rhialto' Seibert - rhialto@       -- Woe betide the one who feels
\X/ polderland.nl  -- remorse without sin - Tom Poes, "Het boze oog", 4444.