lkml.org 
[lkml]   [2009]   [Jun]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 02/20] io-controller: Common flat fair queuing code in elevaotor layer
    * 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


    \
     
     \ /
      Last update: 2009-06-23 09:37    [W:0.023 / U:92.232 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site