source: doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex @ b797d978

\chapter{Conclusion}\label{conclusion}

Building the \CFA runtime has been a challenging project.
The work was divided between high-level concurrency design and a user-level threading runtime (Masters' thesis), and low-level support of the user-level runtime using OS kernel threading and its (multiple) I/O subsystems (Ph.D. thesis).
Because I am the main developer for both components of this project, there is strong continuity across the design and implementation.
This continuity provides a consistent approach to advanced control flow and concurrency, with easier development, management and maintenance of the runtime in the future.

I believed my Masters' work would provide the background to make the Ph.D. work reasonably straightforward.
However, I discovered two significant challenges.

First, modern symmetric multiprocessing CPUs have significant performance penalties for communication, often cache-related.
An SQMS scheduler (see Section~\ref{sched}), with its \proc-shared ready-queue, has perfect load-balancing but poor affinity resulting in high communication across \procs.
An MQMS scheduler, with its \proc-specific ready-queues, has poor load-balancing but perfect affinity often resulting in significantly reduced communication.
However, implementing fairness for an MQMS scheduler is difficult, since fairness requires \procs to be aware of each other's ready-queue progress, \ie communicated knowledge.
For balanced workloads with little or no data sharing, \ie embarrassingly parallel, an MQMS scheduler is near optimal, \eg a state-of-the-art work-stealing scheduler.
For these kinds of fair workloads, adding fairness must be low-cost to hide the communication costs needed for global ready-queue progress or performance suffers.
While I was aware of these realities, I underestimated how little performance margin there is for communication.
Several of my attempts at building a fair scheduler compared poorly to work-stealing schedulers because of the thin communication margin.

Second, the kernel locking, threading, and I/O in the Linux operating system offer very little flexibility and are not designed to facilitate user-level threading.
There are multiple concurrency aspects in Linux that require carefully following a strict procedure to achieve acceptable performance.
To be fair, many of these concurrency aspects were designed 30-40 years ago, when there were few multiprocessor computers and concurrency knowledge was just developing.
Unfortunately, little has changed in the intervening years.

Also, my decision to use @io_uring@ was both positive and negative.
The positive is that @io_uring@ supports the panoply of I/O mechanisms in Linux;
hence, the \CFA runtime uses one I/O mechanism to provide non-blocking I/O, rather than using @select@ to handle TTY I/O, @epoll@ to handle network I/O, and managing a thread pool to handle disk I/O.
Merging all these different \io mechanisms into a coherent scheduling implementation would require much more work than what is present in this thesis, as well as detailed knowledge of multiple I/O mechanisms.
The negative is that @io_uring@ is new and developing.
As a result, there is limited documentation, few places to find usage examples, and multiple errors that required workarounds.

Given what I now know about @io_uring@, I would say it is insufficiently coupled with the Linux kernel to properly handle non-blocking I/O.
It does not seem to reach deep into the kernel's handling of \io, and as such it must contend with the same realities that users of @epoll@ must contend with.
Specifically, in cases where @O_NONBLOCK@ behaves as desired, operations must still be retried.
Preserving the illusion of asynchronicity requires delegating these operations to kernel threads.
This requirement is also true of cases where @O_NONBLOCK@ does not prevent blocking.
Spinning up internal kernel threads to handle blocking scenarios is what developers already do outside of the kernel, and managing these threads adds a significant burden to the system.
Nonblocking I/O should not be handled in this way.
Presumably, this is better handled by Windows's ``overlapped I/O'', however porting \CFA to Windows is far beyond the scope of this work.

\section{Goals}
This work focuses on efficient and fair scheduling of the multiple CPUs, which are ubiquitous on all modern computers.
The levels of indirection to the CPUs are:
\begin{itemize}
\item
The \CFA presentation of concurrency through multiple high-level language constructs.
\item
The OS presentation of concurrency through multiple kernel threads within an application.
\item
The OS and library presentation of disk and network I/O, and many secondary library routines that directly and indirectly use these mechanisms.
\end{itemize}
The key aspect of all of these mechanisms is that control flow can block, which immediately hinders any level above from making scheduling decisions as a result.
Fundamentally, scheduling needs to understand all the mechanisms used by threads that affect their state changes.

The underlying goal of this thesis is scheduling the complex hardware components that make up a computer to provide good utilization and fairness.
However, direct hardware scheduling is only possible in the OS.
Instead, this thesis is performing arms-length application scheduling of the hardware components through a set of OS interfaces that indirectly manipulate the hardware components.
This can quickly lead to tensions when the OS interface has different use cases in mind.

As \CFA aims to increase productivity and safety of C, while maintaining its performance, this places a huge burden on the \CFA runtime to achieve these goals.
Productivity and safety manifest in removing scheduling pitfalls from the efficient usage of the threading runtime.
Performance manifests in making efficient use of the underlying kernel threads that provide indirect access to the CPUs.

This thesis achieves its stated contributions by presenting:
\begin{enumerate}[leftmargin=*]
\item
A scalable low-latency scheduler that offers improved starvation prevention (progress guarantee) compared to other state-of-the-art schedulers, including NUMA awareness.
\item
The scheduler demonstrates a core algorithm that provides increased fairness through helping, as well as optimizations which virtually remove the cost of this fairness.
\item
An implementation of user-level \io blocking is incorporated into the scheduler, which achieves the same performance and fairness balance as the scheduler itself.
\item
These core algorithms are further extended with a low-latency idle-sleep mechanism, which allows the \CFA runtime to stay viable for workloads that do not consistently saturate the system.
\end{enumerate}
Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state changes is low.

\section{Future Work}
While the \CFA runtime achieves a better compromise than other schedulers, in terms of performance and fairness, I believe further improvements can be made to reduce or eliminate the few cases where performance does deteriorate.
Fundamentally, achieving performance and starvation freedom will always be goals with opposing needs even outside of scheduling algorithms.

\subsection{Idle Sleep}
A difficult challenge, not fully addressed in this thesis, is idle sleep.
While a correct and somewhat low-cost idle-sleep mechanism is presented, several of the benchmarks show notable performance degradation when too few \ats are present in the system.
The idle sleep mechanism could therefore benefit from a reduction of spurious cases of sleeping.
Furthermore, this thesis did not present any heuristic for when \procs should be put to sleep and when \procs should be woken up.
While relaxed timestamps and topology awareness made notable performance improvements, neither of these techniques are used for the idle-sleep mechanism.

Here are opportunities where these techniques could be used:
\begin{itemize}
\item
The mechanism uses a handshake between notification and sleep to ensure that no \at is missed.
\item
The handshake correctness is critical when the last \proc goes to sleep but could be relaxed when several \procs are awake.
\item
Furthermore, organizing the sleeping \procs as a LIFO stack makes sense to keep cold \procs as cold as possible, but it might be more appropriate to attempt to keep cold CPU sockets instead.
\end{itemize}
However, using these techniques would require significant investigation.
For example, keeping a CPU socket cold might be appropriate for power consumption reasons but can affect overall memory bandwidth.
The balance between these approaches is not obvious.
I am aware there is a host of low-power research that could be tapped here.

\subsection{CPU Workloads}
A performance consideration related to idle sleep is cpu utilization, \ie, how easy is it
CPU utilization generally becomes an issue for workloads that are compute bound but where the dependencies among \ats can prevent the scheduler from easily.
Examining such workloads in the context of scheduling would be interesting.
However, such workloads are inherently more complex than applications examined in this thesis, and as such warrant it's own work.

\subsection{Hardware}
One challenge that needed to be overcome for this thesis is that the modern x86-64 processors have very few tools to implement fairness.
\Glspl{proc} attempting to help each other inherently cause cache-coherence traffic.
However, as mentioned in Section~\ref{helping}, relaxed requirements mean this traffic is not necessarily productive.
In cases like this one, there is an opportunity to improve performance by extending the hardware.

Many different extensions are suitable here.
For example, when attempting to read remote timestamps for helping, it would be useful to allow cancelling the remote read if it leads to significant latency.
If the latency is due to a recent cache invalidation, it is unlikely the timestamp is old and that helping is needed.
As such, simply moving on without the result is likely to be acceptable.
Another option is to read multiple memory addresses and only wait for \emph{one of} these reads to retire.
This approach has a similar effect, where cache lines with more traffic are waited on less often.
In both of these examples, some care is needed to ensure that reads to an address \emph{sometimes} retire.

Note that this idea is similar to \newterm{Hardware Transactional Memory}~\cite{wiki:htm}, which allows groups of instructions to be aborted and rolled back if they encounter memory conflicts when being retired.
However, I believe this feature is generally aimed at large groups of instructions.
A more fine-grained approach may be more amenable by carefully picking which aspects of an algorithm require exact correctness and which do not.