source: doc/theses/thierry_delisle_PhD/thesis/text/intro.tex @ 749cf69

\chapter{Introduction}\label{intro}
\section{\CFA programming language}

The \CFA programming language~\cite{cfa:frontpage,cfa:typesystem} extends the C programming language by adding modern safety and productivity features, while maintaining backwards compatibility.
Among its productivity features, \CFA supports user-level threading~\cite{Delisle21} allowing programmers to write modern concurrent and parallel programs.
My previous master's thesis on concurrent in \CFA focused on features and interfaces.
This Ph.D.\ thesis focuses on performance, introducing \glsxtrshort{api} changes only when required by performance considerations.
Specifically, this work concentrates on scheduling and \glsxtrshort{io}.
Prior to this work, the \CFA runtime used a strict \glsxtrshort{fifo} \gls{rQ} and no \glsxtrshort{io} capabilities at the user-thread level\footnote{C supports \glsxtrshort{io} capabilities at the kernel level, which means blocking operations block kernel threads where blocking user-level threads whould be more appropriate for \CFA.}.

As a research project, this work builds exclusively on newer versions of the Linux operating-system and gcc/clang compilers.
While \CFA is released, supporting older versions of Linux ($<$~Ubuntu 16.04) and gcc/clang compilers ($<$~gcc 6.0) is not a goal of this work.

\section{Scheduling}
Computer systems share multiple resources across many threads of execution, even on single user computers like laptops or smartphones.
On a computer system with multiple processors and work units, there exists the problem of mapping work onto processors in an efficient manner, called \newterm{scheduling}.
These systems are normally \newterm{open}, meaning new work arrives from an external source or is spawned from an existing work unit.
On a computer system, the scheduler takes a sequence of work requests in the form of threads and attempts to complete the work, subject to performance objectives, such as resource utilization.
A general-purpose dynamic-scheduler for an open system cannot anticipate future work requests, so its performance is rarely optimal.
With complete knowledge of arrive order and work, creating an optimal solution still effectively needs solving the bin packing problem\cite{wiki:binpak}.
However, optimal solutions are often not required.
Schedulers do produce excellent solutions, whitout needing optimality, by taking advantage of regularities in work patterns.

Scheduling occurs at discreet points when there are transitions in a system.
For example, a thread cycles through the following transitions during its execution.
\begin{center}
\input{executionStates.pstex_t}
\end{center}
These \newterm{state transition}s are initiated in response to events (\Index{interrupt}s):
\begin{itemize}
\item
entering the system (new $\rightarrow$ ready)
\item
timer alarm for preemption (running $\rightarrow$ ready)
\item
long term delay versus spinning (running $\rightarrow$ blocked)
\item
blocking ends, \ie network or I/O completion (blocked $\rightarrow$ ready)
\item
normal completion or error, \ie segment fault (running $\rightarrow$ halted)
\item
scheduler assigns a thread to a resource (ready $\rightarrow$ running)
\end{itemize}
Key to scheduling is that a thread cannot bypass the ``ready'' state during a transition so the scheduler maintains complete control of the system.

When the workload exceeds the capacity of the processors, \ie work cannot be executed immediately, it is placed on a queue for subsequent service, called a \newterm{ready queue}.
Ready queues organize threads for scheduling, which indirectly organizes the work to be performed.
The structure of ready queues can take many different forms.
Where simple examples include single-queue multi-server (SQMS) and the multi-queue multi-server (MQMS).
\begin{center}
\begin{tabular}{l|l}
\multicolumn{1}{c|}{\textbf{SQMS}} & \multicolumn{1}{c}{\textbf{MQMS}} \\
\hline
\raisebox{0.5\totalheight}{\input{SQMS.pstex_t}} & \input{MQMSG.pstex_t}
\end{tabular}
\end{center}
Beyond these two schedulers are a host of options, \ie adding an optional global, shared queue to MQMS.

The three major optimization criteria for a scheduler are:
\begin{enumerate}[leftmargin=*]
\item
\newterm{load balancing}: available work is distributed so no processor is idle when work is available.

\noindent
Eventual progress for each work unit is often an important consideration, \ie no starvation.
\item
\newterm{affinity}: processors access state through a complex memory hierarchy, so it is advantageous to keep a work unit's state on a single or closely bound set of processors.

\noindent
Essentially, all multi-processor computers have non-uniform memory access (NUMA), with one or more quantized steps to access data at different levels in the memory hierarchy.
When a system has a large number of independently executing threads, affinity becomes difficult because of \newterm{thread churn}.
That is, threads must be scheduled on multiple processors to obtain high processors utilization because the number of threads $\ggg$ processors.

\item
\newterm{contention}: safe access of shared objects by multiple processors requires mutual exclusion in some form, generally locking\footnote{
Lock-free data-structures do not involve locking but incurr similar costs to achieve mutual exclusion.}

\noindent
Mutual exclusion cost and latency increases significantly with the number of processors accessing a shared object.
\end{enumerate}

Nevertheless, schedulers are a series of compromises, occasionally with some static or dynamic tuning parameters to enhance specific patterns.
Scheduling is a zero-sum game as computer processors normally have a fixed, maximum number of cycles per unit time\footnote{Frequency scaling and turbot boost add a degree of complexity that can be ignored in this discussion without loss of generality.}.
SQMS has perfect load-balancing but poor affinity and high contention by the processors, because of the single queue.
MQMS has poor load-balancing but perfect affinity and no contention, because each processor has its own queue.

Significant research effort has also looked at load sharing/stealing among queues, when a ready queue is too long or short, respectively.
These approaches attempt to perform better load-balancing at the cost of affinity and contention.
Load sharing/stealing schedulers attempt to push/pull work units to/from other ready queues

Note however that while any change comes at a cost, hence the zero-sum game, not all compromises are necessarily equivalent.
Some schedulers can perform very well only in very specific workload scenarios, others might offer acceptable performance but be applicable to a wider range of workloads.
Since \CFA attempts to improve the safety and productivity of C, the scheduler presented in this thesis attempts to achieve the same goals.
More specifically, safety and productivity for scheduling means supporting a wide range of workloads so that programmers can rely on progress guarantees (safety) and more easily achieve acceptable performance (productivity).


\section{Contributions}\label{s:Contributions}
This work provides the following contributions in the area of user-level scheduling in an advanced programming-language runtime-system:
\begin{enumerate}[leftmargin=*]
\item
A scalable scheduling algorithm that offers progress guarantees.
\item
An algorithm for load-balancing and idle sleep of processors, including NUMA awareness.
\item
Support for user-level \glsxtrshort{io} capabilities based on Linux's @io_uring@.
\end{enumerate}