Messages in this thread | | | Date | Tue, 19 Sep 2000 21:17:51 +0200 | From | Jens Axboe <> | Subject | Re: (reiserfs) Re: An elevator algorithm (patch) |
| |
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/
| |