Rik van Riel <riel@conectiva.com.br> 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: peter.osterlund@mailbox.swipnet.se Sköndalsvägen 35 f90-pos@nada.kth.se 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 majordomo@vger.kernel.org Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sat Sep 23 2000 - 21:00:21 EST