Messages in this thread | | | Subject | Re: elevator-starvation-4 (2.2.14 && 2.3.42) | From | Zachary Amsden <> | Date | Fri, 11 Feb 2000 13:48:46 -0800 |
| |
> 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/
| |