lkml.org 
[lkml]   [2000]   [Sep]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: (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/

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