lkml.org 
[lkml]   [2000]   [Sep]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: An elevator algorithm (patch)
On 18 Sep 2000, Peter Osterlund wrote:
> Andrea Arcangeli <andrea@suse.de> writes:
>
> > > The only disadvantage I can see is that the new patch doesn't handle
> > > consecutive insertions in O(1) time, but then again, the pre-latency
> >
> > We can still do that by trivially fixing a bit your code. You should first
> > check if the new inserted request is over the last in the current queue before
> > entering the tmp1/tmp2 logic.
>
> Yes this can be done, but it will affect where requests are inserted.
> Suppose the queue currently contains:
>
> 100 200 300 400 10 20 30
>
> If request 150 is to be inserted, then with my previous patch it
> will be inserted between 100 and 200, but with the proposed
> change it will instead be inserted at the end.

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)

regards,

Rik
--
"What you're running that piece of shit Gnome?!?!"
-- Miguel de Icaza, UKUUG 2000

http://www.conectiva.com/ http://www.surriel.com/

-
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    [from the cache]
©2003-2011 Jasper Spaans. Advertise on this site