lkml.org 
[lkml]   [2000]   [Feb]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: elevator-starvation-4 (2.2.14 && 2.3.42)
From
Date
> 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/

\
 
 \ /
  Last update: 2005-03-22 13:56    [W:0.801 / U:0.040 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site