[lkml]   [2007]   [Apr]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [REPORT] cfs-v4 vs sd-0.44
    On Wed, Apr 25, 2007 at 04:58:40AM -0700, William Lee Irwin III wrote:
    >>> Adjustments to the lag computation for for arrivals and departures
    >>> during execution are among the missing pieces. Some algorithmic devices
    >>> are also needed to account for the varying growth rates of lags of tasks
    >>> waiting to run, which arise from differing priorities/weights.

    On Wed, 2007-04-25 at 22:13 +0200, Willy Tarreau wrote:
    >> that was the principle of my proposal of sorting tasks by expected completion
    >> time and using +/- credit to compensate for too large/too short slice used.

    On Thu, Apr 26, 2007 at 10:57:48AM -0700, Li, Tong N wrote:
    > Yeah, it's a good algorithm. It's a variant of earliest deadline first
    > (EDF). There are also similar ones in the literature such as earliest
    > eligible virtual deadline first (EEVDF) and biased virtual finishing
    > time (BVFT). Based on wli's explanation, I think Ingo's approach would
    > also fall into this category. With careful design, all such algorithms
    > that order tasks based on some notion of time can achieve good fairness.
    > There are some subtle differences. Some algorithms of this type can
    > achieve a constant lag bound, but some only have a constant positive lag
    > bound, but O(N) negative lag bound, meaning some tasks could receive
    > much more CPU time than it would under ideal fairness when the number of
    > tasks is high.

    The algorithm is in a bit of flux, but the virtual deadline computation
    is rather readable. You may be able to tell whether cfs is affected by
    the negative lag issue better than I. For the most part all I can smoke
    out is that it's not apparent to me whether load balancing is done the
    way it needs to be.

    On Thu, Apr 26, 2007 at 10:57:48AM -0700, Li, Tong N wrote:
    > On the other hand, the log(N) complexity of this type of algorithms has
    > been a concern in the research community. This motivated O(1)
    > round-robin based algorithms such as deficit round-robin (DRR) and
    > smoothed round-robin (SRR) in networking, and virtual-time round-robin
    > (VTRR), group ratio round-robin (GP3) and grouped distributed queues
    > (GDQ) in OS scheduling, as well as the distributed weighted round-robin
    > (DWRR) one I posted earlier.

    I'm going to make a bold statement: I don't think O(lg(n)) is bad at
    all. In real systems there are constraints related to per-task memory
    footprints that severely restrict the domain of the performance metric,
    rendering O(lg(n)) bounded by a rather reasonable constant.

    A larger concern to me is whether this affair actually achieves its
    design goals and, to a lesser extent, in what contexts those design
    goals are truly crucial or dominant as opposed to others, such as,
    say, interactivity. It is clear, regardless of general applicability,
    that the predictability of behavior with regard to strict fairness
    is going to be useful in certain contexts.

    Another concern which is in favor of the virtual deadline design is
    that virtual deadlines can very effectively emulate a broad spectrum
    of algorithms. For instance, the mainline "O(1) scheduler" can be
    emulated using such a queueing mechanism. Even if the particular
    policy cfs now implemented is dumped, radically different policies
    can be expressed with its queueing mechanism. This has maintainence
    implications which are quite beneficial. That said, it's far from
    an unqualified endorsement. I'd still like to see much done differently.

    -- wli
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2007-04-27 01:31    [W:0.023 / U:17.412 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site