Sorry, but I must respectfully disagree. The time to service the
request specifically is _not_ unbounded, it's bounded by the size of
the disk.
In general I would assert that the probability of the user process
swamping the driver in this manner is extremely low, or else the
relative priority between the driver and the user process is mixed
up. I would further argue that before sending the block up to the
user process you really ought to kick-off servicing block 11 since
that's going to take a long time and the user process should be able
to proceed in the mean time.
Cheers,
Bruce.
At 15:38 +0000 02/10/2000, Matthew Kirkwood wrote:
>On Thu, 10 Feb 2000, Bruce Thompson wrote:
>
>> Maybe I'm missing something massive, but I'd always been under
>> the impression that an elevator algorithm made starvation impossible?
>
>It does make complete starvation impossible. However, consider
>a 10000000 block device.
>
>Your queue looks like [5, 10, 11, 12], and you are currently
>servicing block 10, and going uphill. Block 10 appears, and
>you copy it to userspace and wake up the process that requested
>it.
>
>While waiting for block 11, the process finishes its processing
>of block 10 and requests block 13.
>
>So your queue now looks like [5, 11, 12, 13] and you're dealing
>with block 11.
>
>Repeat.
>
>Eventually, you /will/ get to the end of the disk, and start
>again at block 5 but to all practical intents, the time to get
>that request serviced is unbounded, hence starvation.
>
>"cp /dev/zero ." tends to exhibit exactly this behaviour on some
>filesystems (though writing rather than reading), and doing this
>on reiserfs is exactly what prompted the patch.
>
>Matthew.
--
--
------------------------------------------------------------------------
Bruce Thompson | "Pinky! Are you pondering what I'm
Palm Computing, Inc. | pondering?"
| "Uh, I think so Brain, but where will
| we find a duck and a hose at this
bruce@otherother.com | hour?"
My opinions are strictly my own.
PGP Fingerprint: 8F48 7FEF EE22 14FB 1F2E 3BF2 0D40 9628 53E8 72EB
-
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/
This archive was generated by hypermail 2b29 : Tue Feb 15 2000 - 21:00:19 EST