Messages in this thread | | | Subject | RE: [REPORT] cfs-v4 vs sd-0.44 | Date | Tue, 24 Apr 2007 18:22:53 -0700 | From | "Li, Tong N" <> |
| |
> 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.
The definition for proportional fairness assumes that each thread has a weight, which, for example, can be specified by the user, or sth. mapped from thread priorities, nice values, etc. A scheduler achieves ideal proportional fairness if (1) it is work-conserving, i.e., it never leaves a processor idle if there are runnable threads, and (2) for any two threads, i and j, in any time interval, the ratio of their CPU time is greater than or equal to the ratio of their weights, assuming that thread i is continuously runnable in the entire interval and both threads have fixed weights throughout the interval. A corollary of this is that if both threads i and j are continuously runnable with fixed weights in the time interval, then the ratio of their CPU time should be equal to the ratio of their weights. This definition is pretty restrictive since it requires the properties to hold for any thread in any interval, which is not feasible. In practice, all algorithms try to approximate this ideal scheduler (often referred to as Generalized Processor Scheduling or GPS). Two error metrics are often used:
(1) lag(t): for any interval [t1, t2], the lag of a thread at time t \in [t1, t2] is S'(t1, t) - S(t1, t), where S' is the CPU time the thread would receive in the interval [t1, t] under the ideal scheduler and S is the actual CPU time it receives under the scheduler being evaluated.
(2) The second metric doesn't really have an agreed-upon name. Some call it fairness measure and some call it sth else. Anyway, different from lag, which is kind of an absolute measure for one thread, this metric (call it F) defines a relative measure between two threads over any time interval:
F(t1, t2) = S_i(t1, t2) / w_i - S_j(t1, t2) / w_j,
where S_i and S_j are the CPU time the two threads receive in the interval [t1, t2] and w_i and w_j are their weights, assuming both weights don't change throughout the interval.
The goal of a proportional-share scheduling algorithm is to minimize the above metrics. If the lag function is bounded by a constant for any thread in any time interval, then the algorithm is considered to be fair. You may notice that the second metric is actually weaker than first. In fact, if an algorithm achieves a constant lag bound, it must also achieve a constant bound for the second metric, but the reverse is not necessarily true. But in some settings, people have focused on the second metric and still consider an algorithm to be fair as long as the second metric is bounded by a constant.
> > 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. >
If we can derive some invariants from the algorithm, it'd help the analysis. An example is the deficit round-robin (DRR) algorithm in networking. Its analysis utilizes the fact that the round each flow (in this case, it'd be thread) goes through in any time interval differs by at most one.
Hope you didn't get bored by all of this. :)
tong - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |