[lkml]   [2000]   [Sep]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: An elevator algorithm (patch)
Rik van Riel <> writes:

> This is a bug in Andrea's idea. The request should only
> be inserted at the end of the list if:
> 1) the block numbre is bigger than head->prev (which you
> already have)
> 2) the block number is smaller than head (or head->next
> if the current request is unplugged)

The second condition is not so simple in the case of latency control.
Consider the following queue:

sector: 100 200 300 400 10 20 30
sequence: 1 1 1 1 0 1 1

In this case it would be correct to insert 150 at the end even though
it is >100, because no more requests are allowed to pass the "10"

It is however possible to decide in O(1) time if the correct insertion
point is at the end of the queue. We have to keep track of the point,
p, where no more requests may pass. (10 in the example above.) The logic
would then be:

int insert_at_tail = 0;
if (IN_ORDER(p, last)) {
if (IN_ORDER(last, req) || IN_ORDER(req, p))
insert_at_tail = 1;
} else {
if (IN_ORDER(last, req) && IN_ORDER(req, p))
insert_at_tail = 1;
if (insert_at_tail) {
/* Do it in O(1) */
} else {
/* Do normal O(n) scan and update latencies */

The question is if this is worth the extra code complexity. How long
can the request queue be? Does it have a fixed upper size, or is it
limited only by available memory? If the request queue is always
short, the O(n) complexity shouldn't matter. Note that the worst case
complexity is still O(n) for all algorithms discussed so far.

Peter Österlund Email:
Sköndalsvägen 35
S-128 66 Sköndal Home page:
Sweden Phone: +46 8 942647

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

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