Messages in this thread
 Subject Re: An elevator algorithm (patch) From Peter Osterlund <> Date 19 Sep 2000 20:30:05 +0200
`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 30sequence: 1   1   1   1   0  1  1In this case it would be correct to insert 150 at the end even thoughit 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 insertionpoint 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 logicwould 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 longcan the request queue be? Does it have a fixed upper size, or is itlimited only by available memory? If the request queue is alwaysshort, the O(n) complexity shouldn't matter. Note that the worst casecomplexity is still O(n) for all algorithms discussed so far.-- Peter Österlund          Email:     peter.osterlund@mailbox.swipnet.seSköndalsvägen 35                    f90-pos@nada.kth.seS-128 66 Sköndal         Home page: http://home1.swipnet.se/~w-15919Sweden                   Phone:     +46 8 942647-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgPlease read the FAQ at http://www.tux.org/lkml/`

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