Re: [patch] CFS scheduler, -v8

Ingo Molnar
2007-05-03T08:50:24Z

* Ting Yang <tingy@cs.umass.edu> wrote:

> Authors of this paper proposed a scheduler: Earlist Eligible Virtual
> Deadline First (EEVDF). EEVDF uses exactly the same method as CFS to
> track the execution of each running task. The only difference between
> EEVDF and CFS is that EEVDF tries to _deadline_ fair while CFS is
> _start-time_ fair. [...]

Well, this is a difference but note that it's far from being the 'only
difference' between CFS and EEVDF:

- in CFS you have to "earn" your right to be on the CPU, while EEVDF
gives out timeslices (quanta)

- EEVDF concentrates on real-time (SCHED_RR-alike) workloads where they
know the length of work units - while CFS does not need any knowledge
about 'future work', it measures 'past behavior' and makes its
decisions based on that. So CFS is purely 'history-based'.

- thus in CFS there's no concept of "deadline" either (the 'D' from
EEVDF).

- EEVDF seems to be calculating timeslices in units of milliseconds,
while CFS follows a very strict 'precise' accounting scheme on the
nanoseconds scale.

- the EEVDF paper is also silent on SMP issues.

- it seems EEVDF never existed as a kernel scheduler, it was a
user-space prototype under FreeBSD with simulated workloads. (have
they released that code at all?).

The main common ground seems to be that both CFS and EEVDF share the
view that the central metric is 'virtual time' proportional to the load
of the CPU (called the 'fair clock' in CFS) - but even for this the
details of the actual mechanism differ: EEVDF uses 1/N while CFS (since
-v8) uses a precise, smoothed and weighted load average that is close to
(and reuses portions of) Peter Williams's load metric used in smp-nice.

The EEVDF mechanism could perhaps be more appropriate for real-time
systems (the main target of their paper), while the CFS one i believe is
more appropriate for general purpose workloads.

So i'd say there's more in common between SD and CFS than between EEVDF
and CFS.

So ... it would certainly be interesting to try the EEVDF paper based on
CFS (or whatever way you'd like to try it) and turn the EEVDF paper into
a real kernel scheduler - the two mechanisms are quite dissimilar and
they could behave wildly differently on various workloads. Depending on
test results we could use bits of EEVDF's approaches in CFS too, if it
manages to out-schedule CFS :-)

(your observation about CFS's fork handling is correct nevertheless!)

Ingo