# Re: [PATCH 02/20] io-controller: Common flat fair queuing code inelevaotor layer

**From: **Balbir Singh

**Date: ** Tue Jun 23 2009 - 03:33:52 EST

* Fabio Checconi <fchecconi@xxxxxxxxx> [2009-06-23 06:10:52]:

>* > From: Vivek Goyal <vgoyal@xxxxxxxxxx>*

>* > Date: Mon, Jun 22, 2009 10:43:37PM -0400*

>* >*

>* > On Mon, Jun 22, 2009 at 02:43:13PM +0200, Fabio Checconi wrote:*

>* > *

>* ...*

>* > > > Please help me understand this, we sort the tree by finish time, but*

>* > > > search by vtime, start_time. The worst case could easily be O(N),*

>* > > > right?*

>* > > > *

>* > > *

>* > > no, (again, the full answer is in the paper); the nice property of*

>* > > min_start is that it partitions the tree in two regions, one with*

>* > > eligible entities and one without any of them. once we know that*

>* > > there is one eligible entity (checking the min_start at the root)*

>* > > we can find the node i with min(F_i) subject to S_i < V walking down*

>* > > a single path from the root to the leftmost eligible entity. (we*

>* > > need to go to the right only if the subtree on the left contains *

>* > > no eligible entities at all.) since the RB tree is balanced this*

>* > > can be done in O(log N).*

>* > > *

>* > *

>* > Hi Fabio,*

>* > *

>* > When I go thorough the paper you mentioned above, they seem to have*

>* > sorted the tree based on eligible time (looks like equivalent of start*

>* > time) and then keep track of minimum deadline on each node (equivalnet of*

>* > finish time).*

>* > *

>* > We seem to be doing reverse in BFQ where we sort tree on finish time*

>* > and keep track of minimum start time on each node. Is there any specific*

>* > reason behind that?*

>* > *

>* *

>* Well... no specific reasons... I think that our implementation is easier*

>* to understand than the one of the paper, because it actually uses finish*

>* times as the ordering key, and min_start to quickly locate eligible*

>* subtrees, following the definition of the algorithm.*

>* *

Is it still O(log N)?

>* Moreover, if you look at the get_req() code in the paper, it needs a*

>* couple of loops to get to the result, while with our implementation*

>* we save the second loop.*

>* *

>* Our version is still correct, because it always moves to the left*

>* (towards smaller finish times), except when moving to the left would*

>* mean entering a non feasible subtree, in which case it moves to the*

>* right.*

>* *

>* Unfortunately I'm not aware of any paper describing a version of the*

>* algorithm more similar to the one we've implemented. Sorry for not*

>* having mentioned that difference in the comments nor anywhere else,*

>* it has been a long long time since I read the paper, and I must have*

>* forgotten about that.*

/me needs to go read the paper in full.

--

Balbir

--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

the body of a message to majordomo@xxxxxxxxxxxxxxx

More majordomo info at http://vger.kernel.org/majordomo-info.html

Please read the FAQ at http://www.tux.org/lkml/