Changeset 9d67a6d for doc/theses/thierry_delisle_PhD

Timestamp:

Aug 31, 2022, 3:02:53 PM (2 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, ast-experimental, master, pthread-emulation

Children:

7e5da64

Parents:

38e4c5c (diff), 67a1c67 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

doc/theses/thierry_delisle_PhD/thesis

Files:

• local.bib (modified) (1 diff)
• text/conclusion.tex (modified) (1 diff)
• text/eval_macro.tex (modified) (1 diff)

doc/theses/thierry_delisle_PhD/thesis/local.bib

@@ -555 +555 @@
   title = {Mach Scheduling and Thread Interfaces - Kernel Programming Guide},
   organization = {Apple Inc.},
-  note = {\href{https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html}{https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html}}
+  note = {\href{https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html}{https://\-developer.apple.com/\-library/archive/\-documentation/\-Darwin/\-Conceptual/\-KernelProgramming/\-scheduler/\-scheduler.html}}
 }
 

doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex

@@ -1 +1 @@
 \chapter{Conclusion}\label{conclusion}
 
-\Gls{uthrding} is popular.
-It makes sense for \CFA to use it.
+Building the \CFA runtime has been an extremely 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.
 
-\todo{Obivously fix the above}
+I believed my Masters work would provide the background to make the Ph.D work reasonably straightforward.
+What I discovered is that interacting with kernel locking, threading, and I/O in the UNIX (Linux) operating system is extremely difficult.
+There are multiple concurrency aspects in UNIX that are poorly designed, not only for user-level threading but also for kernel-level threading.
+Basically, UNIX-based OSs are not very concurrency friendly.
+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.
+It is unfortunately so little has changed in the intervening years.
 
-An important aspect of this approach to threading is how threads are scheduled.
-As \CFA aims to increase productivity and safety of C while maintaining its performance, so to should the threading runtime achieve these goals.
-For scheduling, productivity and safety manifest in removing pitfalls in the efficient usage of the threading runtime.
-This thesis contributes to this goal by presenting a low-latency scheduler that offers improved starvation prevention compared to other state-of-the-art schedulers.
-It presents a core algorithm (Chapter~\ref{core}) that provides increased fairness through helping (Section~\ref{heling}) as well as optimizations which virtually remove the cost of this fairness (Section~\ref{relaxedtimes}).
-Building upon the fundamental scheduling algorithm, an implementation of user-level \io blocking is presented (Chapter~\ref{io}) which achieves the same performance and fairness balance as the scheduler itself.
-From these core algorithms, and a low-latency idle-sleep mechanism is presented (Chapter~\ref{practice}) which allows the \CFA runtime to stay viable for workloads that do not consistently saturate the system.
+Also, my decision to use @io_uring@ was both a positive and negative.
+The positive is that @io_uring@ supports the panoply of I/O mechanisms in UNIX;
+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 some unknown to handle disk I/O.
+It is unclear to me how I would have merged all these different I/O mechanisms into a coherent scheduling implementation.
+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.
+Specifically, spinning up internal kernel threads to handle blocking scenarios is what developers already do outside of the kernel.
+Nonblocking I/O should not be handled in this way.
+
+% While \gls{uthrding} is an old idea, going back to the first multi-processor computers, it was largely set aside in the 1990s because of the complexity in making it work well between applications and the operating system.
+% Unfortunately,, a large amount of that complexity still exists, making \gls{uthrding} a difficult task for library and programming-language implementers.
+% For example, the introduction of thread-local storage and its usage in many C libraries causes the serially reusable problem~\cite{SeriallyReusable} for all \gls{uthrding} implementers.
+% Specifically, if a \gls{kthrd} is preempted, it always restarts with the same thread-local storage;
+% when a user thread is preempted, it can be restarted on another \gls{kthrd}, accessing the new thread-local storage, or worse, the previous thread-local storage.
+% The latter case causes failures when an operation using the thread-local storage is assumed to be atomic at the kernel-threading level.
+% If library implementers always used the pthreads interface to access threads, locks, and thread-local storage, language runtimes can interpose a \gls{uthrding} version of pthreads, switching the kind of threads, locks, and storage, and hence, make it safe.
+% However, C libraries are currently filled with direct declarations of thread-local storage and low-level atomic instructions.
+% In essence, every library developer is inventing their own threading mechanisms to solve their unique problem, independent from any standardize approaches.
+% This state of affairs explains why concurrency is such a mess.
+% 
+% To address the concurrency mess, new programming languages integrate threading into the language rather than using the operating-system supplied interface.
+% The reason is that many sequential code-optimizations invalid correctly written concurrent programs.
+% While providing safe concurrent-code generation is essential, the underlying language runtime is still free to implement threading using kernel or user/kernel threading, \eg Java versus Go.
+% In either case, the language/runtime manages all the details to simplify concurrency and increase safety.
+
+\section{Goals}
+
+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 complex set of OS interfaces that indirectly manipulate the hardware components.
+Couple that with the OS running multiple applications with its own goals for scheduling among them.
+Hence, my goal became the battle of two schedulers.
+
+This work focusses 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 is the enemy of the scheduler.
+Fundamentally, scheduling needs to understand all the mechanisms used by threads that affect their state changes.
+
+Interestingly, there is another major hardware component that affects threading: memory.
+How memory is organized, and when it is acquired and released, has a significant affect on thread scheduling.
+To this end, I worked closely with another graduate student, Mubeen Zulfiqar, in the development of a new memory allocator for \CFA.
+(See Mubeen's thesis~\cite{Zulfiqar22} for a discussion of how threading is managed in the \CFA memory-allocator.)
+
+% An important aspect of this approach to threading is how threads are scheduled.
+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 in 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 contributes 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 in term of performance and fairness than other schedulers, I do believe that further improvements could be made to reduce even further the number of cases where performance deteriorates.
-Furthermore, I believe that achieve performance and starvation freedom simultaneously is generally a challenge even outside of scheduling algorithms.
+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.
+Fundamentally, achieving performance and starvation freedom will always be opposing goals even outside of scheduling algorithms.
 
 \subsection{Idle Sleep}
-A difficult challenge that was not fully address in this thesis is idle-sleep.
-While a correct and somewhat low-cost idle-sleep mechanism was presented, several of the benchmarks show notable performance degradation when too few \ats are present in the system.
+A difficult challenge, not fully address 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.
-It is especially worth noting that relaxed timestamps and topology aware helping lead to notable improvements in performance.
-Neither of these techniques were used for the idle sleep mechanism.
+While relaxed timestamps and topology awareness made a notable improvements in performance, neither of these techniques are used for the idle-sleep mechanism.
 
-There are opportunities where these techniques could be use:
+Here are opportunities where these techniques could be use:
+\begin{itemize}
+\item
 The mechanism uses a hand-shake between notification and sleep to ensure that no \at is missed.
-The correctness of that hand-shake is cirtical when the last \proc goes to sleep but could be relaxed when several \procs are awake.
+\item
+The correctness of that hand-shake 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 LIDO 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.
-
-However, using these techniques could require significant investigation.
-For example, keeping a CPU socket cold might be appropriate for power consumption reasons but can affect overall memory bandwith.
-The balance between these is not necessarily obvious.
+\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.
 
 \subsection{Hardware}
-One challenge that needed to be overcome for this thesis was that the modern x86-64 has very few tools to implement fairness.
-\Glspl{proc} attempting to help eachother inherently cause cache-coherence traffic.
+One challenge that needed to be overcome for this thesis is that the modern x86-64 processors has 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 would be suitable here.
-For example, when attempting to read remote timestamps when deciding to whether or not to help, it could be useful to allow cancelling the remote read if it will lead to significant latency.
-If the latency is due to a recent cache invalidation, it is unlikely that the timestamp is old and that helping will be needed.
+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 would be to attempt to read multiple memory addresses and only wait for \emph{one of} these reads to retire.
-This would have a similar effect, where cache-lines with more traffic would be waited on less often.
-In both of these examples, some care would probably be needed to make sure that the reads to an address \emph{sometimes} retire.
+Another option would be 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 would be waited on less often.
+In both of these examples, some care is needed to ensure that reads to an address \emph{sometime} retire.
 
-Note that this is similar to the feature \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.
+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.
 However, I believe this feature is generally aimed at large groups of instructions.
-A more fine-grained approach may be more amenable to carefully picking which aspects of an algorithm require exact correctness and which do not.
+A more fine-grained approach may be more amenable by carefully picking which aspects of an algorithm require exact correctness and which do not.

doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex

@@ -373 +373 @@
 
 Supporting this case in the webserver would require creating more \procs or creating a dedicated thread-pool.
-However, I felt this kind of modification moves to far away from my goal of evaluating the \CFA runtime, \ie it begins writing another runtime system;
+However, I felt this kind of modification moves too far away from my goal of evaluating the \CFA runtime, \ie it begins writing another runtime system;
 hence, I decided to forgo experiments on low-memory performance.