1 | \chapter{Conclusion}\label{conclusion} |
---|
2 | |
---|
3 | Building the \CFA runtime has been a challenging project. |
---|
4 | 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). |
---|
5 | Because I am the main developer for both components of this project, there is strong continuity across the design and implementation. |
---|
6 | This continuity provides a consistent approach to advanced control-flow and concurrency, with easier development, management and maintenance of the runtime in the future. |
---|
7 | |
---|
8 | I believed my Masters work would provide the background to make the Ph.D work reasonably straightforward. |
---|
9 | However, in doing so I discovered two expected challenges. |
---|
10 | First, while modern symmetric multiprocessing CPU have significant performance penalties for communicating across cores. |
---|
11 | This makes implementing algorithm notably more difficult, since fairness generally requires \procs to be aware of each other's progress. |
---|
12 | This challenge is made even harder when comparing against MQMS schedulers (see Section\ref{sched}) which have very little inter-\proc communication. |
---|
13 | This is particularly true of state-of-the-art work-stealing schedulers, which can have virtually no inter-\proc communication in some common workloads. |
---|
14 | This means that when adding fairness to work-stealing schedulers, extreme care must be taken to hide the communication costs so performance does not suffer. |
---|
15 | Second, the kernel locking, threading, and I/O in the Linux operating system offers very little flexibility of use. |
---|
16 | There are multiple concurrency aspects in Linux that require carefully following a strict procedure in order to achieve acceptable performance. |
---|
17 | To be fair, many of these concurrency aspects were designed 30-40 years ago, when there were few multi-processor computers and concurrency knowledge was just developing. |
---|
18 | It is unfortunate that little has changed in the intervening years. |
---|
19 | |
---|
20 | Also, my decision to use @io_uring@ was both a positive and negative. |
---|
21 | The positive is that @io_uring@ supports the panoply of I/O mechanisms in Linux; |
---|
22 | 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. |
---|
23 | Merging all these different I/O mechanisms into a coherent scheduling implementation would require a much more work than what is present in this thesis, as well as detailed knowledge of the I/O mechanisms in Linux. |
---|
24 | The negative is that @io_uring@ is new and developing. |
---|
25 | As a result, there is limited documentation, few places to find usage examples, and multiple errors that required workarounds. |
---|
26 | 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. |
---|
27 | 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. |
---|
28 | Specifically, in cases where @O_NONBLOCK@ behaves as desired, operations must still be retried. |
---|
29 | To preserve the illusion of asynchronicity, this requires delegating operations to kernel threads. |
---|
30 | This is also true of cases where @O_NONBLOCK@ does not prevent blocking. |
---|
31 | Spinning up internal kernel threads to handle blocking scenarios is what developers already do outside of the kernel, and managing these threads adds significant burden to the system. |
---|
32 | Nonblocking I/O should not be handled in this way. |
---|
33 | |
---|
34 | \section{Goals} |
---|
35 | This work focusses on efficient and fair scheduling of the multiple CPUs, which are ubiquitous on all modern computers. |
---|
36 | The levels of indirection to the CPUs are: |
---|
37 | \begin{itemize} |
---|
38 | \item |
---|
39 | The \CFA presentation of concurrency through multiple high-level language constructs. |
---|
40 | \item |
---|
41 | The OS presentation of concurrency through multiple kernel threads within an application. |
---|
42 | \item |
---|
43 | The OS and library presentation of disk and network I/O, and many secondary library routines that directly and indirectly use these mechanisms. |
---|
44 | \end{itemize} |
---|
45 | The key aspect of all of these mechanisms is that control flow can block, which immidiately hinders any level above from making scheduling decision as a result. |
---|
46 | Fundamentally, scheduling needs to understand all the mechanisms used by threads that affect their state changes. |
---|
47 | |
---|
48 | The underlying goal of this thesis is scheduling the complex hardware components that make up a computer to provide good utilization and fairness. |
---|
49 | However, direct hardware scheduling is only possible in the OS. |
---|
50 | 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. |
---|
51 | This can quickly lead to tensions if the OS interface was built with different use cases in mind. |
---|
52 | |
---|
53 | 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. |
---|
54 | Productivity and safety manifest in removing scheduling pitfalls in the efficient usage of the threading runtime. |
---|
55 | Performance manifests in making efficient use of the underlying kernel threads that provide indirect access to the CPUs. |
---|
56 | |
---|
57 | This thesis achieves its stated contributes by presenting: |
---|
58 | \begin{enumerate}[leftmargin=*] |
---|
59 | \item |
---|
60 | A scalable low-latency scheduler that offers improved starvation prevention (progress guarantee) compared to other state-of-the-art schedulers, including NUMA awareness. |
---|
61 | \item |
---|
62 | The scheduler demonstrates a core algorithm that provides increased fairness through helping, as well as optimizations which virtually remove the cost of this fairness. |
---|
63 | \item |
---|
64 | An implementation of user-level \io blocking is incorporated into the scheduler, which achieves the same performance and fairness balance as the scheduler itself. |
---|
65 | \item |
---|
66 | 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. |
---|
67 | \end{enumerate} |
---|
68 | Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state changes is low. |
---|
69 | |
---|
70 | \section{Future Work} |
---|
71 | While the \CFA runtime achieves a better compromise, in term of performance and fairness, than other schedulers, I believe further improvements can be made to reduce or eliminate the few cases where performance does deteriorate. |
---|
72 | Fundamentally, achieving performance and starvation freedom will always be goals with opposing needs even outside of scheduling algorithms. |
---|
73 | |
---|
74 | \subsection{Idle Sleep} |
---|
75 | A difficult challenge, not fully address in this thesis, is idle-sleep. |
---|
76 | 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. |
---|
77 | The idle sleep mechanism could therefore benefit from a reduction of spurious cases of sleeping. |
---|
78 | Furthermore, this thesis did not present any heuristic for when \procs should be put to sleep and when \procs should be woken up. |
---|
79 | While relaxed timestamps and topology awareness made a notable improvements in performance, neither of these techniques are used for the idle-sleep mechanism. |
---|
80 | |
---|
81 | Here are opportunities where these techniques could be use: |
---|
82 | \begin{itemize} |
---|
83 | \item |
---|
84 | The mechanism uses a hand-shake between notification and sleep to ensure that no \at is missed. |
---|
85 | \item |
---|
86 | The correctness of that hand-shake is critical when the last \proc goes to sleep but could be relaxed when several \procs are awake. |
---|
87 | \item |
---|
88 | 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. |
---|
89 | \end{itemize} |
---|
90 | However, using these techniques would require significant investigation. |
---|
91 | For example, keeping a CPU socket cold might be appropriate for power consumption reasons but can affect overall memory bandwidth. |
---|
92 | The balance between these approaches is not obvious. |
---|
93 | |
---|
94 | \subsection{Hardware} |
---|
95 | One challenge that needed to be overcome for this thesis is that the modern x86-64 processors has very few tools to implement fairness. |
---|
96 | \Glspl{proc} attempting to help each other inherently cause cache-coherence traffic. |
---|
97 | However, as mentioned in Section~\ref{helping}, relaxed requirements mean this traffic is not necessarily productive. |
---|
98 | In cases like this one, there is an opportunity to improve performance by extending the hardware. |
---|
99 | |
---|
100 | Many different extensions are suitable here. |
---|
101 | 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. |
---|
102 | If the latency is due to a recent cache invalidation, it is unlikely the timestamp is old and that helping is needed. |
---|
103 | As such, simply moving on without the result is likely to be acceptable. |
---|
104 | Another option would be to read multiple memory addresses and only wait for \emph{one of} these reads to retire. |
---|
105 | This approach has a similar effect, where cache-lines with more traffic would be waited on less often. |
---|
106 | In both of these examples, some care is needed to ensure that reads to an address \emph{sometime} retire. |
---|
107 | |
---|
108 | Note, this idea is similar to \newterm{Hardware Transactional Memory}~\cite{HTM}, which allows groups of instructions to be aborted and rolled-back if they encounter memory conflicts when being retired. |
---|
109 | However, I believe this feature is generally aimed at large groups of instructions. |
---|
110 | A more fine-grained approach may be more amenable by carefully picking which aspects of an algorithm require exact correctness and which do not. |
---|