Re: [REPORT] cfs-v4 vs sd-0.44

[William Lee Irwin III <wli@holomorphy.com>]

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