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

[Zachary Amsden]

> 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  [e-mail]  [phone]  09U-510  Core Protocols