* Li, Tong N <[EMAIL PROTECTED]> wrote: >> [...] 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. [...]
On Wed, Apr 25, 2007 at 11:44:03AM +0200, Ingo Molnar wrote: > yes, it's a pretty strong definition, but also note that while it is > definitely not easy to implement, the solution is nevertheless feasible > in my opinion and there exists a scheduler that implements it: CFS. The feasibility comment refers to the unimplementability of schedulers with infinitesimal timeslices/quanta/sched_granularity_ns. It's no failing of cfs (or any other scheduler) if, say, the ratios are not exact within a time interval of one nanosecond or one picosecond. One of the reasons you get the results you do is that what you use for ->fair_key is very close to the definition of lag, which is used as a metric of fairness. It differs is in a couple of ways, but how it's computed and used for queueing can be altered to more precisely match. The basic concept you appear to be trying to implement is a greedy algorithm: run the task with the largest lag first. As far as I can tell, this is sound enough, though I have no formal proof. So with the lag computation and queueing adjusted appropriately, it should work out. 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. There are no mysteries. -- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/