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

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

* Li, Tong N <tong.n.li@intel.com> 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 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/