SCHEDFAST : Understanding Linux scheduling bottlenecks

Context.

The process scheduler is the part of an operating system that decides what thread runs
on what core at what time. As such, it has a critical impact on application performance, particu-
larly for multithreaded applications. While some applications simply spread out across the available
cores, with each thread running continuously without disturbance on its preferred core, others involve
frequent synchronization, I/O, etc. In practice, whenever a thread gives up access to a core, another
thread can replace it, leading to migrations, loss of locality, and degraded performance. At the same
time, evolutions in the scheduler can introduce errors, that can also degrade performance on specific
workloads. Tools exist to trace scheduling behavior, that can help identify the presence of such pro-
blems, but the sheer volume of information available makes it difficult to map a scheduling trace to
a root cause.

Objectives.

The main aim of the PhD is to understand the behavior of the multicore Linux process
scheduler under heavy load. We will particularly focus on the diagnosis of scheduling anomalies, as
can occur in specific runs with a given scheduler implementation and as can be introduced over time
by bugs in the scheduler implementation. Our starting point is the observation that we can produce an
unlimited number of execution traces, including over multiple versions of the Linux kernel. Analogous
to the diagnosis of illnesses using image processing, we would like to develop a model of the expected
behavior of a scheduler on a given application through the use of statistical models such as for
instance Markov chain models, and then to detect as anomalous execution traces that deviate from
these models. The goal is to detect scheduling problems quickly, when bugs are introduced into the
source code, to detect scheduling problems from short-running examples where the problem may not
easily be visible to a person looking at a trace, and to connect scheduling problems reflected in a
trace to specific elements of the scheduler or the application source code. Based on the results, we
will consider how to improve the Linux scheduler to provide better performance.
Expected background : This PhD requires familiarity with the C language and operating systems
concepts, as well as a background in machine learning.