the linux scheduler: a decade of wasted cores

Paper: The Linux Scheduler: a Decade of Wasted Cores by Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quema, and Alexandra Fedorova (EuroSys 2016).

What is TPC-H? An org that audits benchmarks for DB, storage engines. Frequently mentioned in research papers. DBT-3 (open source version) helps you run the same tests. TPC-H gives you QphH (queries per hour via geometric mean of power and throughput). Useful in capacity planning.

They built their own tools for identifying these bugs while scheduling.

What is Dennard Scaling? Because of increasing complexity of the surrounding systems (hardware, cache), the implementation of the scheduler is becoming more complex and maybe more bloaty.

It fails in a very basic function: runnable threads use idle cores.

This paper discusses 4 performance bugs. A common symptom: the scheduler unintentionally and for a long time leaves cores idle while there are runnable threads waiting in runqueues.

Tools built: sanity checker (detects invariant violations).

the Linux scheduler #

CFS on single CPU #

CFS (Completely Fair Scheduling) is based on Weighted Fair Queueing (WFQ) scheduling algorithms. It time-slices the CPU among the running threads.

Decisions made in the scheduler:

• How to determine a thread’s timeslice?
• How to pick the next thread to run?

The scheduler defines a fixed time interval in which every thread should run at least once. The interval is divided among threads with respect to weight. The resulting interval is the timeslice for that thread.

Thread’s weight is based on priority/niceness. When a thread runs, it accumulates vruntime (runtime/weight).

The thread gets pre-empted:

• When vruntime exceeds the timeslice
• Another smaller vruntime thread is awoken
• If there are other threads available on the CPU

Threads are organized as a runqueue (red-black tree), sorted in increasing order of their vruntime. The CPU chooses the leftmost node in the tree, which contains the smallest vruntime.

How do I see the vruntime or the runqueue?

CFS on multi-core #

CFS becomes quite complex. Per-core runqueue. Context switches will be expensive if we go away from local runqueue to global shared runqueue across cores.

Runqueues should be balanced across cores. If there are 2 cores and one has N high priority threads and the other core has 1 low priority thread, the high priority threads will have less CPU time than the low priority thread if each core only sees their local runqueue. To solve this problem, they introduced the load balancer.

Load balancing is expensive in communication and compute. When runqueues are unbalanced, cores go idle. Scheduler tries not to run the load balancer and goes to great lengths to avoid it. Goal is to have lower overhead and save power.

load balancer algorithm #

It will be bad to load balance based on weights and numbers alone. We need a metric to balance so that we balance the CPU time.

Load balancing with respect to weights would make CPU idle when high priority threads sleep and get more CPU time, which might lead to work stealing. Or if each runqueue has the same number of threads, one is low priority and another high priority. Looking at it this way, we see that this is not what we want. We don’t want the same CPU time for low and high priority threads.

CFS balances runqueues based on a load metric: thread weight and average CPU utilization. This thereby helps us balance threads based on load. If the thread is not on CPU a lot, then it would have less load.

In multithreading in different processes, say one process with a lot of threads and another with few threads. This will make it such that the first process with lots of threads will starve the other process. To make sure there is fairness, there is a feature for this: scheduling groups.

Scheduling groups, scheduling domains.

bugs #

group imbalance bug #

This happens because of the problem of taking load average of the scheduling group to assign or steal work. This makes the lowest thread in that group free and thus it is not fully utilized, causing inefficiencies among the group.

It is caused because the load metric of the group is the average. The simple solution is to take the lowest load in the group. Finding this would be in the same time as finding the average. So in terms of complexity, it is the same. But we get the performance improvement.

When the NAS Benchmark was run, lu ran 13x faster after the fix.

scheduling group construction bug #

This happens because of the way scheduling groups are constructed and load balanced.

In the default cases of group construction with respect to node 0, there will be nodes that are two hops apart in some NUMA systems, which can be used for binding the application using tasksets. Now because they might also be in both groups, this will make the average probing of load to balance not effective for more work as the load averages will be the same in both groups. Making it a bug.

The fix is so that each node can form these groups with overlap in mind and not have the nodes in different groups, making this bug obsolete from the root cause.

overload-wakeup bug #

Because of cache optimizations, a short-term sleep thread may be woken up on a core other than a long-term idle core. Which makes the system non-optimal in performance.

The wakeup might not be power efficient as the long-term idle cores may be in a low power state and waking up means going on full throttle.

Fix: add this as a factor to choose and schedule work. Choose long-idle cores before short-term idle cores when needed.

missing scheduler domain bug #

This bug occurs when a core gets deactivated and the number of cores gets updated but the scheduler still schedules in the past groups. Meaning it schedules on the old cores for new work. Significantly overloading the single core or group.

Fix: add the function that updates the group on deactivation, which was missed in the code refactor.

should we change the design of the Linux scheduler? #

No, it has had immense engineering throughout the years. The high algorithmic complexity made it slower. CFS is useful for multithreaded workloads with changing hardware and software. Now, they are changing the load metric calculation to be made simpler in terms of code complexity.

Measurement of these bugs is not possible or a pain with traditional performance monitoring tools as these are not panic problems that the system shows but slow performance-eating bugs.

tools #

sanity checker #

It checks for idle cores and waiting threads in the runqueue. It does not assert because it allows short-term discrepancy as the scheduler will fix it. So the tool runs to check in S interval and after a violation it profiles the events for M time. Systemtap can also be used to profile but it has performance implications compared to the in-house tool.

This tool gives us the bugs that eat away at performance.

scheduler visualization tool #

Helps us see the events visually throughout the paper to see the bug. The overload-wakeup bug!

It gets the runqueue, load and core usage events and stores them in a global array for further visuals. Each event is 20 bytes and it has no performance implications.

lessons learned #

There were a lot of changes and new ideas proposed for the scheduler by a lot of researchers and community. But they couldn’t be included in the scheduler safely. We need to think about a scheduler design that allows it to add more things safely as the hardware grows/changes. The proposed way is to have modules like main and optimization modules that help the main module schedule when possible. The optimization module may be cache-based, power-based, memory-based.

Another lesson is visualization should be more adopted and standardized to find more of these bugs.

related work #

performance bugs #

• The Linux kernel performance project
• LITMUS

kernel correctness #

RacerX, Eraser. Like these tools that detect system crashes, we need these tools to extend and detect performance bugs. The big issue in this arena is to know that the short invariant violation is acceptable in our system. But long-term violation isn’t. So we need tools that should keep track of that.

Model checking is used to detect bugs in kernels. Useful to find bugs before they happen. It can detect crash bugs but not subtle performance bugs.

Formal verification: proving software correctness by analyzing source code. They work by describing the system with states, pre and post conditions. It works in single-threaded. And it does not work yet with the long-term invariant violation detection. Having Linux developers write formal specs will also be a hurdle.

tracing #

Tracing can be helpful in finding these bugs, but the sheer volume of data is overwhelming.

• Event Tracing in Windows
• DTrace (Solaris, FreeBSD, macOS)
• SystemTap, Ftrace, KernelShark (Linux)

The online sanity checker used SystemTap to find the traces and events to build the bug cases with their visualization tool.

conclusion #

Scheduler (dividing CPU cycles among threads) is not a solved problem. And the bugs that arise from these implementations are hard to detect because of the subtlety of them. We see the problem of runnable threads stuck in the runqueue while there are idle cores. The Linux scheduler also violates the basic work-conserving invariant. They mention that more tools and fixes will be available.