On Fri, Jun 21, 2002 at 03:31:19PM +0200, Olaf Seibert wrote:
> 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...

Your textbook may very well have been the "Design and Implementation of 
the 4.4BSD Operating System" as that algorithm is described on page 199.
It's a decent algorithm, and does guarantee eventual completion of all
queued I/O requests, but here's the problem we're running into:

The requests queued in (c) of your example are coming in faster than the
disk can service them, and because they're all read/write-block-n+1,
they're all in front of the current position.  None of them are eligible
to be serviced in (e).  So, the request in (b) is starved until the very
large write in (c) is completed.

This would be fine if some process (say, an ls) wasn't blocking on (b).
(b) AIUI is a swap I/O that's blocking the entire system.

The solution we seek is to elevate the priority of (b) so the system
isn't blocked.

jf
-- 
John Franklin
franklin@elfie.org
ICBM: 35°43'56"N 78°53'27"W