* 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 -- dm-devel mailing list dm-devel@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/dm-devel
