Rik van Riel <[EMAIL PROTECTED]> 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)
>
> AND
>
> 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"
request.
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: [EMAIL PROTECTED]
Sköndalsvägen 35 [EMAIL PROTECTED]
S-128 66 Sköndal Home page: http://home1.swipnet.se/~w-15919
Sweden Phone: +46 8 942647
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
Please read the FAQ at http://www.tux.org/lkml/
