linux-kernel - Re: fair clock use in CFS

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4648C49D.3070909@cs.umass.edu>
Date:	Mon, 14 May 2007 16:20:45 -0400
From:	Ting Yang <tingy@...umass.edu>
To:	William Lee Irwin III <wli@...omorphy.com>
CC:	Srivatsa Vaddagiri <vatsa@...ibm.com>, Ingo Molnar <mingo@...e.hu>,
	efault@....de, linux-kernel@...r.kernel.org
Subject: Re: fair clock use in CFS

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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/