Current ULE state and plans (was Re: HMP scheduling on FreeBSD)

Hi,

This is a mail intended to spread the news.  I must also admit to getting a bit tired to see the same misconceptions and falsities on ULE, and even on schedulers in general, repeated over long periods of time by several people.

> IMHO, ULE doesn't do great job for fairness. There was a freebsd-hackers thread [1] back in 2023 that criticized ULE's fairness, and I believe this is ULE's limitation by design.

This assumption and a significant number of those that appeared in that earlier thread are mostly wrong.

There's nothing in ULE's design that rules out fairness.  On the contrary, it was (of course) designed to be fair, for threads that are in the same situation (same kind of execution pattern, same nice values, etc.).

Rather than point out every mistake, it seems best to do some synthesis about ULE, which isn't the exact truth but with that number of words is hopefully the closest description to reality.

Creation of ULE was done in preparation for multi- and many-core machines.  Its main purpose, and huge advantage over 4BSD, is scalability over an arbitrary number of cores and threads (it is O(1) for both for the most frequent operations) and knowledge of cores topology.  Not only 4BSD has a single, shared global runqueue (the usual case), but it also periodically needs to scan all threads to adjust their priorities (each time statclock() is called; ~128Hz).  ULE most of the time operates on the local CPU runqueue, without contention, and does not need to "update" thread priorities at all, thanks to a clever mechanism of circular runqueues (I think Kirk McKusick has been calling them "calendar runqueues"; we are talking about the same thing, regardless of the term).  A load-balancer, which runs much less frequently (once to twice per second), balances the per-CPU queues (taking into account the topology).

Despite the different mechanisms, Jeff Roberson (ULE's creator) took care to ensure that priority decaying in ULE would be similar to that of 4BSD, that is, priority depends on an estimate of CPU time over elapsed time when not waiting for an event (i.e., being in a runqueue or on a CPU; being in a runqueue waiting for execution is usually called "involuntary sleep").

That said, the current implementation has a number of problems.  I'm listing the two I consider the most important later in this mail.

> Someone in the thread said the interactivity score is "bogus": although I wouldn't go that far, interactivity score sacrifices fairness and we definitely need patches to handle edge cases (similar to what CFS experienced on linux side).

Not sure what you had in mind exactly but, as is, this statement about CFS makes no sense.  CFS works by maintaining an execution time which it uses to ensure fairness as it allows to check whether some thread has been less executed than another.  There's no interactivity score at all in CFS, so there certainly aren't any patches to fix problems with that.

IIRC, CFS has been trying to be "too" fair, as wanting to execute threads behind in terms of CPU time received too early, which can cause important efficiency problems and, perhaps counter-intuitively, have adverse effects on latency.  ULE does not have this problem at all for non-interactive threads; and obviously we are ready to accept such a loss of overall efficiency for the benefit of interactive ones (although the extent of which could be debated).

> ULE's interactivity score mechanism also pollutes priorities provided by nice value.

It's a feature that we both take into account priorities computed from runtime and sleeptime (actually, wait time, i.e., involuntary sleep) and nice values.  Any sane scheduler does that.

There can be discussion on how interactivity is measured, or why there's such a measure at all, see below.

> Someone in the thread said nice isn't relevant anymore these days, but I think it should be respected as nice value is crucial to UNIX scheduling and many softwares still depend on it.

I agree with this, and have been intending to fix the nice values problem (see below).

That said, the advice of using idle priorities to launch background jobs is more relevant than ever, as it works very well.  You have now at your disposal 32 really distinct such priority levels, and given current ULE's tuning no deadlock/starvation should ever occur, contrary to what is stated in some places, e.g., `rtprio(8)`.

> Interactivity scores and nice value can be messed up together pretty easily compared to CFS/EEVDF, which can cause performance degradation that users didn't expect. It also makes harder to predict how the system would behave under certain circumstance while many of the "interactivity" assumptions in early 2000s aren't true anymore (e.g. graphical applications).

I don't think the performance problems described in the thread you quoted are due to "interactivity scores" and "nice values" being "messed up" (see list of problems below).

Interactive patterns have shifted, yes, but human perception has stayed the same.  ULE evaluates interactivity over the last ~10s of thread execution or involuntary sleep, and this is more than enough even for modern use where interactivity processing time has risen.

ULE does have a sysctl knob to tune detection of interactivity, `kern.sched.interact`, which is a value between 0 and 100 (30 is the default).  It is possible to turn off right now the interactive detection and favoring by just setting this knob to 0.

If anyone suspects some behavior is linked to interactive detection and handling, the first thing to try is to re-run the scenario with `kern.sched.interact` set to 0.

I'll take the opportunity to remind everyone that, when running benchmarks, you must follow a thorough procedure in order to avoid as many sources of bias as possible.  We have a useful wiki write-up to this end: https://wiki.freebsd.org/BenchmarkAdvice.  We need more experiments and hard numbers, rather than not-that-well-informed opinions.

I actually already discussed the interactivity detection with Jeff, and he was considering the idea of perhaps leaving out interactivity detection.  Personally, I think more experiments are warranted, and suspect the current interactivity score formula could be revised (and some balancing mechanism), if it is shown that the interactivity indeed impacts fairness too badly, which again remains to be seen.
 
> It would be nice to introduce fairness scheduler like CFS/EEVDF[2] in FreeBSD, even though that might require cleaning up existing sched.h interfaces. FreeBSD kernel has been too dependent on 4BSD/ULE since early 2000s, and introducing new scheduler will break many things. By establishing a better sched interface, this gives opportunities for others to implement their own scheduler on FreeBSD.

I already did one step in this direction, in the form of almost entirely separating the runqueue code with scheduler code.  There is still some room to improvement but we are not faring that bad.  I don't think introducing a new scheduler would "break many things".  The scheduler interface must stay as simple as possible to the rest of the kernel.

> These days I'm leaning towards fairness schedulers over multilevel feedback queue. (snip)

I've been toying with this idea too, as schedulers making decisions based directly on CPU/sleep time instead of priorities are easier to reason about with respect to fairness in terms of CPU time (but not latency).  However, they are not necessarily simpler (virtual runtime needs care, and policies in some parts), and direct accounting of runtime is in fact only part of the story in a lot of circumstances, the rest being agnostic to the chosen scheduler type.

Moreover, we already have a good basis in the form of ULE, and its problems can be fixed.  So my current goal is first to fix ULE before starting the much bigger task of an entirely new scheduler design, especially since a lot of mechanisms in ULE are actually more flexible than they appear.
 
> (snip) I believe on Unix world window manager developers should handle this through nice not by asking OS to expose scheduling APIs like XNU does.

We indeed want to avoid that.

Now, turning to ULE's well-known main problems (which I've analyzed not only with merely running examples, but actually hacking the scheduler and support programs that produce statistics):
1. The effect of nice values is too low, to the point of insignificance.  As a striking example, a thread with an offset nice value of -20 competing with one with a value of 20 will get the CPU only 66% of the time.  A nice value of 0 against 20 only gives a +4% CPU time advantage compared to total fairness (nice values been equal).  See https://reviews.freebsd.org/D46566 for details.
2. There is a fairness issue for threads in-between interactive ones and CPU hogs, i.e., doing a non-trivial amount of computation so that they are not considered interactive, but at the same which frequently do not use the full quantum.  In this situation, with the current code, the amount of not-used quantum is simply lost.

There were earlier attempts to fix point 2 but they were not satisfactory enough.  I have been having a solution for it, which I ran by Jeff who agreed it was worth testing.  I also have a solution for point 1 as well which is relatively simple and most probably will turn out to be sufficient to give much more weight to nice values, and change the scale to be an exponential one (so that the effect of a shift in nice values is, from a relative point of view, the same whatever your current nice value is).   In terms of coding, each of them shouldn't take me more than a week or two.  What really takes time with scheduling matters is rarely coding per se, but, beyond high-level analysis and design (already mostly done in these cases), tests and actual measurements, as well as comparing the behavior of a variety of workloads before and after the changes.

These have been in my TODO list for a relatively long time now, without ever reaching the top for various reasons.  They still probably won't in the immediate (as I'm mostly working on Power matters at the moment) but since there seems to be some interest, hopefully I'll be doing them in a month or two.  Once these problems are fixed, it's likely that, experiments confirming, there won't be any more reason to keep 4BSD around.  One of my personal goals is to deprecate 4BSD in 16 if possible, as it is more and more irrelevant on modern machines and seems too lightly tested.

Thanks and regards.

-- 
Olivier Certner