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

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

Zachary Amsden (zamsden@cthulhu.engr.sgi.com)
Fri, 11 Feb 2000 13:48:46 -0800

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Jean-Luc Pedneault: "Re: sg.c/IrDA in 2.3.43: compile fails"
- Previous message: pramodh mallipatna: "kiovec"

> On Thu, 10 Feb 2000, Bruce Thompson wrote:
>
> > Lemme sort of restate the question I have then: Is the goal to
> > ensure that the elevator algorithm does not result in indefinite
> > postponement? If so then I assert that a correct implementation of
> > the elevator algorithm is guaranteed to prevent indefinite
> > postponement. Or, is the goal to ensure that any given request is
> > not delayed for an unreasonable length of time
>
> The latter. We want to maximise request latency to something
> relatively small because we don't want one flood of requests
> to stall something else in the system.

Divide the disk into N buckets. When queuing requeusts, queue them into the
appropriate bucket. When running the disk scheduling algorithm, do a linear
scan of all items in the current bucket. Weight the scheduling factor used to
service a bucket using a heuristic based on three factors:

1) absolute distance from current bucket
2) maximal age of request in the bucket
3) number of requests in the bucket.

This gives you a balance between global fairness and local optimization which
is tweakable by choosing N. In a spread access pattern, this would behave
better than a simple age/distance heuristic, as you get a nice optimization
from scanning an entire bucket at a time. In a localized access pattern, any
"outside" requests get serviced as timely as possible when their age
contributes to their heuristic function.

Just a suggestion, I'm not aware of whether this has already been tried.

    --
    Zachary Amsden  zamsden@engr.sgi.com  (650) 933-6919  09U-510  Core Protocols

    -
    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: Jean-Luc Pedneault: "Re: sg.c/IrDA in 2.3.43: compile fails"
- Previous message: pramodh mallipatna: "kiovec"