Re: elevator algorithm bug in ll_rw_blk.c

kwrohrer@ce.mediaone.net
Mon, 16 Nov 1998 16:32:53 -0600 (EST)

And lo, Stephen C. Tweedie saith unto me:
>
> On Sun, 15 Nov 1998 11:17:19 -0600 (EST), kwrohrer@ce.mediaone.net said:
>
> > And lo, Chip Salzenberg saith unto me:
> >>
> >> But that's a *one-way* elevator. Ideal elevators are two-way, aren't they?
> > Depends on what you call "ideal". Bottom-up elevators are fairer to the
> > first and last parts of the disk than back-and-forth elevators are. But I
> > haven't seen any papers on how fair is "fair enough" in the general case.
> > I'd think not allowing processes to add more requests to the current pass
> > would be more important, and more likely necessary, than choosing one-way
> > over back-and-forth, for "typical" tasks. But I freely admit that my sense
> > of "typical" is intuitive, not concrete or even anecdotal...
>
> Allowing processes to add new tasks to the queue is essential for good
> performance. As long as the elevator is uni-directional, it doesn't
> make things any less fair: over the long term, every request gets served
> within the space of exactly one pass and no individual requests get
> priority.

But the duration of a "pass" is not fixed. One user doing "cat bigfile >
/dev/null" can monopolize the whole disk until it's done catting
bigfile; a database process (or three) generating many random accesses to
the database file would produce a similar mess, perhaps of greater
duration relative to their size because of all the time spent seeking and
waiting for the disk to spin. Meanwhile, the rest of the requests sit and
wait, and who cares if they're guaranteed to be handled "this pass" when
that's 10+ seconds from now...

It's clear that you do have to impose some sort of cutoff at some point.
What that is, I can't say for sure. But how come ls -R and du don't hang
the system nowadays?

Keith

-- 
"The avalanche has already started; |Linux: http://www.linuxhq.com     |"Zooty,
it is too late for the pebbles to   |KDE:   http://www.kde.org         | zoot
vote." Kosh, "Believers", Babylon 5 |Keith: kwrohrer@enteract.com      | zoot!"
 www.midwinter.com/lurk/lurker.html |http://www.enteract.com/~kwrohrer | --Rebo


-
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/