Linux-kernel mailing list archive 2000-06,: Re: elevator-starvation-4 (2.2.14 && 2.3.42) [was Re: 2.3.42 elevator

# Re: elevator-starvation-4 (2.2.14 && 2.3.42) [was Re: 2.3.42 elevator

Linus Torvalds (torvalds@transmeta.com)
Wed, 9 Feb 2000 12:19:06 -0800 (PST)

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Trond Myklebust: "Again: Process stuck in D state while locking in NFS"
- Previous message: Theodore Y. Ts'o: "Re: 2.4 Features"

On Wed, 9 Feb 2000, Andrea Arcangeli wrote:
>
> Linus I suggest you to give a try to the below patch. Do you remeber that
> linux always stalled during heavy write I/O? If not try a `cp /dev/zero .`
> and see that all accesses to the fs where you are writing to stalls
> sometime until you kill `cp` on the other terminal.

I'd MUCH rather have something like:
- each IO queue has a sequence number
- each incoming request increments the sequence number, and sets req->seq
to be the new sequence number allocated.
- re-do the request queue to be a regular "struct list_head" thing, so
that we can go both forwards and backwards.
- start adding requests from the BACK instead of the front like we do
now. That's usually the right thing to do anyway, so it makes us use
less CPU to find the right position. It also makes the next rule
trivial to implement:
- refuse to move a new request forward past a request that has a sequence
number that is too much in the past. Here "too much" depends on what
kinds of requests we're talking about.

I don't like the "writebomb" logic - rather than have a separate writebomb
thing, it should be much easier to make the "too much in the past" check
do this particular logic. So the logic may be something like

- writes may occur earlier than reads, but we will do that ONLY if
- the read is really recent (ie the distance between the "current
sequence number" and the "read request sequence number" is
short)
- the write is closer to the proper elevator sequence than the
read was.

Reads work the same way, except the "distance" requirement can be much
less strict - let's say that writes can pass reads only if the read is
within the last 10 requests handled, while reads can pass other reads as
long as there have been less than 100 other reads in between (made-up
numbers, you get the idea).

Passing old writes is even easier, so there the distance could be
something like "it's ok to pass an old write as long as the old writes
sequence number is within 1000 of the current one". This is also where we
could easily have "generation of write" logic for sorting between two
writes - to force a partial ordering on the queue level.

So I think the sequence numbers should be able to handle =both= the
latency issue and the write bomb issue. With some simple rules like the
above, you KNOW that you'll never starve a readfrom writes, in fact you'll
be guaranteed to do the read with no more than X (in above example 10)
writes coming between it and execution.

Comments? It doesn't seem to be too hard to do, and I'd hate to apply your
current patch that does something similar but has other things I disagree
with.

Linus

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

- Next message: Trond Myklebust: "Again: Process stuck in D state while locking in NFS"
- Previous message: Theodore Y. Ts'o: "Re: 2.4 Features"