Studying Linux Schedulers, and Why Metrics Matter

Studying Linux Schedulers, and Why Metrics Matter

A cruel reminder that measuring stuff is hard

Last semester, I took Parallel Computer Architectures at UIUC. For a term project, I (with the help of smart friends) set out to investigate exactly how much scheduling decisions mattered in the Linux Scheduler, specifically as it related to picking between different cores available in a CPU (or multiple sockets).

Background

The classical advice goes that you prefer to keep processes on the same core for as long as possible (without inducing unfairness) so that you can keep their data warm in the caches, and Linux's EEVDF scheduler does a pretty good job of that. What isn't taken into account is making sure processes are arranged across the CPU(s) in such a way that you minimize the number of levels in the cache hierarchy you have to traverse to service accesses to shared memory.

As an illustrative example – consider a dual-socket Xeon system (which was our testing configuration). If a process makes an access to shared memory, let's be pessimistic and suppose that another process has recently accessed this memory as well, has performed a write, and that the dirty data is still in the cache hierarchy. What are the possible coherence actions that could occur? It depends on where the process was scheduled:

If the process was running on the same core (in a separate scheduling quantum), nothing! We have the data! Yippee! We will find it somewhere in our L1/L2 private cache hierarchy, and require no coherence actions.

If the process ran on another core, then on modern Xeon systems there are two ways this can pan out.

The process was scheduled onto another core in our socket. This means that we will force a write-back from the other core's private cache hierarchy into the fully-shared L3, and either pull data from DRAM or directly from the other core's private cache hierarchy via the coherency fabric.

The process was scheduled on the other socket. This is the worst-case, as the other socket's L3 will need to transfer data across the chipset (or we go to DRAM), at which point we can pull the data all the way through our own cache hierarchy to use it… yikes!

As we can see, there is a fairly asymmetric penalty here to service a cache miss when dealing with multi-threaded programs. So really, our goal is to minimize the number of times we have to deal with case 2.2. If we were only read-sharing across cores, everything would be hunky-dory since data is much more likely to stay cache-resident. It's really this pessimistic write-sharing behavior that starts to be annoying. Ideally, we generally prefer to trigger case 2.1 in this situation, since it balances cache miss penalties with scheduling flexibility and maximizing available compute.

The granularity of this decision tree will inevitably change depending on the CPU/configuration we are using. Zen 1 and 2, for example, would have a third branch here, as some SKUs contained separated L3 caches per CCX, so you could get away with faster access times if you managed to schedule your data-sharing processes on the same CCX.

So with some fairly strict caveats – no sub-NUMA clustering, ignoring memory residency, etc. – we set out to answer three questions:

How much of a benefit is there from successfully scheduling multi-threaded processes fully within one LLC domain?

Do current schedulers do a good job of ensuring that this happens?

How can they be improved to actually make this happen?

Our study mostly focused on points 1 and 2, with 3 being a "we hope this can happen", until we realized that CAS was starting to address point 3. So at this point we thought, "what if we just test CAS and EEVDF and find the gaps?". Okay, fair enough. But then we realized that we couldn't actually do that on shared lab resources and instead pivoted to profiling LAVD. It obviously exhibits very different behaviors and priorities, but the hope was that the second-order effects of LAVD would emulate that of CAS. I'm not totally sure how accurate that hypothesis ended up being, but EOTD we needed some testing methodology so this would have to do.

There's a lot more background about the internals of these schedulers about how various Linux schedulers work and our evaluation methods, but I'll fast forward to the mishaps in the next section for (relative) brevity. More fine-grained details can be found in our final report, either in PDF or web format.

A Cascade of Mistakes

So at this point, our study is clear! We want to characterize how performance is impacted by scheduling threads auto-magically with the default Linux scheduler, with a "cache-optimized" scheduler, and with manual restriction of thread positions.

As many school projects go, we started a little close to the deadline, and followed a fairly linear train of thought to start testing right away. Our experimental setup was to track coherence actions (via read-for-ownership...