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.
-
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:17 EST