Re: CFS review

[Ingo Molnar <mingo@elte.hu>]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> It would be better, I suspect, to make the scheduler clock totally 
> distinct from the other clock sources (many architectures have per-cpu 
> cycle counters), and *not* try to even necessarily force it to be a 
> "time-based" one.

yeah. Note that i largely detached sched_clock() from the GTOD 
clocksources already in CFS, so part of this is already implemented and 
the intention is clear. For example, when the following happens:

   Marking TSC unstable due to: possible TSC halt in C2.
   Clocksource tsc unstable (delta = -71630388 ns)

sched_clock() does _not_ stop using the TSC. It is very careful with the 
TSC value, it checks against wraps, jumping, etc. (the whole rq_clock() 
wrapper around sched_clock()), but still tries to use the highest 
resolution time source possible, even if that time source is not good 
enough for GTOD's purposes anymore. So the scheduler clock is already 
largely detached from other clocksources in the system.

> It would still be true that something that is purely based on timer 
> ticks will always be liable to have rounding errors that will 
> inevitably mean that you don't get good fairness - tuning threads to 
> run less than a timer tick at a time would effectively "hide" them 
> from the scheduler accounting. However, in the end, I think that's 
> pretty much unavoidable.

Note that there is a relatively easy way of reducing the effects of such 
intentional coupling: turn on CONFIG_HIGH_RES_TIMERS. That decouples the 
scheduler tick from the jiffy tick and works against such 'exploits' - 
_even_ if the scheduler clock is otherwise low resolution. Also enable 
CONFIG_NO_HZ and the whole thing (of when the scheduler tick kicks in) 
becomes very hard to predict.

[ So while in a low-res clock situation scheduling will always be less 
  precise, with hres-timers and dynticks we have a natural 'random 
  sampler' mechanism so that no task can couple to the scheduler tick - 
  accidentally or even intentionally.

  The only 'unavoidable coupling' scenario is when the hardware has only 
  a single, low-resolution time sampling method. (that is pretty rare 
  though, even in the ultra-embedded space. If a box has two independent 
  hw clocks, even if they are low resolution, the timer tick can be
  decoupled from the scheduler tick.) ]

> I have to say, it would be interesting to try to use 32-bit 
> arithmetic.

yeah. We tried to do as much of that as possible, please read on below 
for (many) more details. There's no short summary i'm afraid :-/

Most importantly, CFS _already_ includes a number of measures that act 
against too frequent math. So even though you can see 64-bit math code 
in it, it's only rarely called if your clock has a low resolution - and 
that happens all automatically! (see below the details of this buffered 
delta math)

I have not seen Roman notice and mention any of these important details 
(perhaps because he was concentrating on finding faults in CFS - which a 
reviewer should do), but those measures are still very important for a 
complete, balanced picture, especially if one focuses on overhead on 
small boxes where the clock is low-resolution.

As Peter has said it in his detailed review of Roman's suggested 
algorithm, our main focus is on keeping total complexity down - and we 
are (of course) fundamentally open to changing the math behind CFS, we 
ourselves tweaked it numerous times, it's not cast into stone in any 
way, shape or form.

> I also think it's likely a mistake to do a nanosecond resolution. 
> That's part of what forces us to 64 bits, and it's just not even an 
> *interesting* resolution.

yes, very much not interesting, and we did not pick nanoseconds because 
we find anything "interesting" in that timescale. Firstly, before i go 
into the thinking behind nanoseconds, microseconds indeed have 
advantages too, so the choice was not easy, see the arguments in favor 
of microseconds below at: [*].

There are two fundamental reasons for nanoseconds:

 1) they _automatically_ act as a 'carry-over' for fractional math and
    thus reduce rounding errors. As Roman has noticed we dont care much
    about math rounding errors in the algorithm: _exactly_ because we
    *dont have to* care about rounding errors: we've got extra 10
    "uninteresting" bits in the time variables to offset the effects of 
    rounding errors and to carry over fractionals.

    ( Sidenote: in fact we had some simple extra anti-rounding-error 
      code in CFS and removed it because it made no measurable 
      difference. So even in the current structure there's additional 
      design reserves that we could tap before having to go to another 
      math model. All we need is a testcase that demonstrates rounding 
      errors. Roman's testcase was _not_ a demonstration of math 
      rounding errors, it was about clock granularity! )

 2) i tried microseconds resolution once (it's easy) but on fast hw it 
    already showed visible accounting/rounding artifacts in 
    high-frequency scheduling workloads, which, if hw gets just a little 
    bit faster, will become pain.

    ( Sidenote: if a workload is rescheduling once every few 
      microseconds, then it very much matters to the balance of things 
      whether there's a fundamental +- 1 microsecond skew on who gets 
      accounted what. In fact the placement of sched_clock() call within 
      schedule() is already visible in practice in some testcases, 
      whether the runqueue-spinlock acquire spinning time is accounted 
      to the 'previous' or the 'next' task - despite that time being 
      sub-microsecond on average. Going to microseconds makes this too 
      coarse. )

I.e. microseconds are on the limit today on fast hardware, and 
nanoseconds give us an automatic buffer against rounding errors.

On _slow_ hardware, with a low-resolution clock, i very much agree that 
we should not do too frequent math, and there are already four 
independent measures that we did in CFS to keep the math overhead down:

Firstly, CFS fundamentally "buffers the math" via deltas, _everywhere_ 
in the fastpath:

        if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) {
                __update_curr(cfs_rq, curr, now);
                curr->delta_exec = 0;
        }

I.e. we only call the math routines if there was any delta. The beauty 
is that this "math buffering" works _automatically_ if there is a 
low-resolution sched_clock() present, because with a low-resolution 
clock a delta is only observed if a tick happens. I.e. in a 
high-frequency scheduling workload (the only place where scheduler 
overhead would be noticeable) all the CFS math is in a rare _slowpath_, 
that gets triggered only every 10 msecs or so! (if HZ=1000)

I.e. we didnt have to go down the (very painful) path of ktime_t 
split-model math and we didnt have to introduce a variable precision 
model for "scheduler time" either, because the delta math itself 
automatically buffers on slow boxes.

Secondly, note that all the key fastpath variables are already 32-bit 
(on 32-bit platforms):

        long                    wait_runtime;
        unsigned long           delta_fair_run;
        unsigned long           delta_fair_sleep;
        unsigned long           delta_exec;

The _timestamps_ are still 64-bit, but most of the actual math goes on 
in 32-bit delta variables. That's one of the advantages of doing deltas 
instead of absolute values.

Thirdly, if even this amount of buffering is not enough for an 
architecture, CFS also includes the sched_stat_granularity_ns tunable 
that allows the further reduction of the sampling frequency (and the 
frequency of us having to do the math) - so if the math overhead is a 
problem an architecture can set it.

Fourthly, in CFS there is a _single_ 64-bit division, and even for that 
division, the actual values passed to it are typically in a 32-bit 
range. Hence we've introduced the following optimization:

  static u64 div64_likely32(u64 divident, unsigned long divisor)
  {
  #if BITS_PER_LONG == 32
          if (likely(divident <= 0xffffffffULL))
                  return (u32)divident / divisor;
          do_div(divident, divisor);

          return divident;
  #else
          return divident / divisor;
  #endif
  }

Which, if the divident is in 32-bit range, does a 32-bit division.

About math related rounding errors mentioned by Roman (not to be 
confused with clock granularity rounding), in our analysis and in our 
experience rounding errors of the math were never an issue in CFS, due 
to the extra buffering that nanosecs gives - i tweaked it a bit around 
CFSv10 but it was unprovable to have any effect. That's one of the 
advantages of working with nanoseconds: the fundamental time unit 
includes about 10 "low bits" that can carry over much of the error and 
reduce rounding artifacts. And even that math rounding errors we believe 
centers around 0.

In Roman's variant of CFS's algorithm the variables are 32-bit, but the 
error is rolled forward in separate fract_* (fractional) 32-bit 
variables, so we still have 32+32==64 bit of stuff to handle. So we 
think that in the end such a 32+32 scheme would be more complex (and 
anyone who took a look at fs2.c would i think agree - it took Peter a 
day to decypher the math!) - but we'll be happy to be surprised with 
patches of course :-)

	Ingo

[*] the main advantage of microseconds would be that we could use "u32"
    throughout to carry around the "now" variable (timestamp). That 
    property of microseconds _is_ tempting and would reduce the 
    task_struct footprint as well. But if we did that it would have
    ripple effects: we'd have to resort to (pretty complex and 
    non-obvious) math to act against rounding errors. We'd either have 
    to carry the rounding error with us in separate 32-bit variables (in 
    essence creating 32+32 bit 64-bit variable), or we'd have to shift 
    up the microseconds by say ... 10 binary positions ... in essence 
    bringing us back into the same nanoseconds range. And then the 
    wraparound problem of microseconds - 72 hours is not _that_ 
    unrealistic to trigger intentionally, so we have to do _something_
    about it to inhibit infinite starvation. We experimented
    around with all this and the overwhelming conclusion (so far) was 
    that trying to reduce timestamps back to 32 bits is just not worth 
    it. _Deltas_ should, can and _are_ 32-bit values already, even in 
    the nanosecond model. So all the buffering and delta logic gives us
    most of the 32-bit advantages already, without the disadvantages of
    microseconds.