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 offairness> 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 aweight, which, for example, can be specified by the user, or sth. mappedfrom thread priorities, nice values, etc. A scheduler achieves idealproportional fairness if (1) it is work-conserving, i.e., it neverleaves a processor idle if there are runnable threads, and (2) for anytwo threads, i and j, in any time interval, the ratio of their CPU timeis greater than or equal to the ratio of their weights, assuming thatthread i is continuously runnable in the entire interval and boththreads have fixed weights throughout the interval. A corollary of thisis that if both threads i and j are continuously runnable with fixedweights in the time interval, then the ratio of their CPU time should beequal to the ratio of their weights. This definition is prettyrestrictive since it requires the properties to hold for any thread inany interval, which is not feasible. In practice, all algorithms try toapproximate this ideal scheduler (often referred to as GeneralizedProcessor 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 threadwould receive in the interval [t1, t] under the ideal scheduler and S isthe actual CPU time it receives under the scheduler being evaluated.(2) The second metric doesn't really have an agreed-upon name. Some callit fairness measure and some call it sth else. Anyway, different fromlag, which is kind of an absolute measure for one thread, this metric(call it F) defines a relative measure between two threads over any timeinterval: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 theinterval [t1, t2] and w_i and w_j are their weights, assuming bothweights don't change throughout the interval.The goal of a proportional-share scheduling algorithm is to minimize theabove metrics. If the lag function is bounded by a constant for anythread in any time interval, then the algorithm is considered to befair. You may notice that the second metric is actually weaker thanfirst. In fact, if an algorithm achieves a constant lag bound, it mustalso achieve a constant bound for the second metric, but the reverse isnot necessarily true. But in some settings, people have focused on thesecond metric and still consider an algorithm to be fair as long as thesecond 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, andthis> > 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? Whathappens> > if a large number of threads dynamically join and leave thesystem?).> > 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 theanalysis. An example is the deficit round-robin (DRR) algorithm innetworking. Its analysis utilizes the fact that the round each flow (inthis case, it'd be thread) goes through in any time interval differs byat most one.Hope you didn't get bored by all of this. :)  tong-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/

Last update: 2007-04-25 03:27    [W:0.144 / U:8.440 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site