Re: fair clock use in CFS

[Ting Yang <tingy@cs.umass.edu>]

William Lee Irwin III wrote:
> On Mon, May 14, 2007 at 04:52:59PM +0530, Srivatsa Vaddagiri wrote:
>   
>> Doesn't EEVDF have the same issue? From the paper:
>> 	V(t) = 1/(w1 + w2 + ...wn)
>>     
>
> Who knows what I was smoking, then. I misremembered the scale factor
> as being on the other side of comparisons with the queue's clock. I'm
> suspicious of EEVDF's timekeeping now as well.
>
>   
Both CFS and EEVDF uses the queue virtual time (VT) to measure the total 
amount of work done so far, VT maps to different real time scale as the 
workload in the system varies. It provides a measure for task to check 
if it goes ahead or falls behind.

Suppose, each task p maintain its own  virtual time, which  is advance 
reverse proportional to its weight
    VT_p(t + 1)  = VT_p(t) + 1/w_p
(in fact, CFS uses this to calculate p->delta_mine, EEVDF uses this to 
decide the deadline for a given slice of work by adding l_p/w_p to 
virtual start time.)
At the time when VT_p(t) = VT(t), i.e. at time t, the virtual time of a 
task equals the virtual time of the queue, this task has received its 
entitled share in interval [0, t]. If VT_p(t) < VT(p), it falls behind 
than it should, otherwise it goes ahead than it should.

Both CFS and EEVDF uses this measure implicitly to decide when a task 
should be executed. The difference is that CFS allows the amount of 
carried out by a task of weight w_i to be continuously executed until it 
goes ahead what it should by a certain amount (tuned and scaled 
accordingly). While EEVDF has to give out a slice (since it is deadline 
driven), and forces a potential long work to be done in smaller slices 
and interleaved with other tasks. Combined with eligibility check, EEVDF 
provides better "fairness" (only in the sense that work spread out more 
evenly in relative short window, since nobody can continuously do more 
than l_i amount of work) with the overhead of _more_ context switches.

It is really difficult for me to say which one is better.  In 
particular, the current CFS implementation favors  higher weight tasks. 
The granularity used by higher weight task is scaled up, which allows it 
to go ahead more (as it is possibly more important and should make it 
finish as early as possible.), while lower weight task has no such 
ability. This makes a lot sense to me.


Ting