Re: elevator algorithm bug in ll_rw_blk.c

Michael O'Reilly (michael@metal.iinet.net.au)
13 Nov 1998 15:03:13 +0800


Chris Wedgwood <chris@cybernet.co.nz> writes:
> > The request *should* be optimally ordered within the current
> > request queue state. I.e. if the queue has request for the blocks
> > [4, 10000, 10005] and the 'elevator' is going 'up', you issue 4,
> > then 10000. If you then get a new request for block 5, your're out
> > of luck. This is the classical elevator alg. from OS course, I
> > assume that's what Linux uses.
>
> Somehow, its wasn't or isn't.
>

Yup. I think the problem here is that sorting only goes on inside the
request queue (at least, it did last time I looked).

With a sync, it'll start at the beginning of the dirty block list, and
start adding things to the request queue. It'll collese and sorts
where possible.

When there are 64 items queued up, it will _stop_ adding until the
disk hardware has cleared a request. This means if you have..

1, 10001, 11000, ..... 64000, 2, 65000, ...., 128000, 3, ...

in the dirty block list, the 1, 2, 3 won't be collesed together
because they're spaced too fair apart.

The 'obvious' solution is to sort the dirty block list, but you'll
need to do it carefully to avoid starvation.

Michael.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/