On Tue, Sep 19 2000, Peter Osterlund wrote:
> > 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 */
> }
But there may be several p points in the queue, how are you going
to keep track of all of them?
> 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.
See QUEUE_NR_REQUESTS in blkdev.h -- the standard size is 256 requests
per queue.
-- * Jens Axboe <axboe@suse.de> * SuSE Labs - 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