> 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/
This archive was generated by hypermail 2b29 : Tue Feb 15 2000 - 21:00:21 EST