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

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

On Mon, Apr 23, 2007 at 05:59:06PM -0700, Li, Tong N wrote:
> I don't know if we've discussed this or not. Since both CFS and SD claim
> to be fair, I'd like to hear more opinions on the fairness aspect of
> these designs. In areas such as OS, networking, and real-time, fairness,
> and its more general form, proportional fairness, are well-defined
> terms. In fact, perfect fairness is not feasible since it requires all
> runnable threads to be running simultaneously and scheduled with
> infinitesimally small quanta (like a fluid system). So to evaluate if a
> new scheduling algorithm is fair, the common approach is to take the
> ideal fair algorithm (often referred to as Generalized Processor
> Scheduling or GPS) as a reference model and analyze if the new algorithm
> can achieve a constant error bound (different error metrics also exist).

Could you explain for the audience the technical definition of fairness
and what sorts of error metrics are commonly used? There seems to be
some disagreement, and you're neutral enough of an observer that your
statement would help.


On Mon, Apr 23, 2007 at 05:59:06PM -0700, Li, Tong N wrote:
> I understand that via experiments we can show a design is reasonably
> fair in the common case, but IMHO, to claim that a design is fair, there
> needs to be some kind of formal analysis on the fairness bound, and this
> bound should be proven to be constant. Even if the bound is not
> constant, at least this analysis can help us better understand and
> predict the degree of fairness that users would experience (e.g., would
> the system be less fair if the number of threads increases? What happens
> if a large number of threads dynamically join and leave the system?).

Carrying out this sort of analysis on various policies would help, but
I'd expect most of them to be difficult to analyze. cfs' current
->fair_key computation should be simple enough to analyze, at least
ignoring nice numbers, though I've done nothing rigorous in this area.


-- wli