`* Fabio Checconi <fchecconi@gmail.com> [2009-06-23 06:10:52]:> > From: Vivek Goyal <vgoyal@redhat.com>> > 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`