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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
