Changes in / [f7e4f8e8:4ae78c1]


Ignore:
Location:
doc/theses/thierry_delisle_PhD
Files:
2 deleted
12 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/comp_II/presentation.tex

    rf7e4f8e8 r4ae78c1  
    3636        \miniframeson
    3737}
    38 \section{Concurrency and \CFA}
    39 \begin{frame}{Project}
    40         \begin{center}
    41                 {\large Produce a scheduler for \CFA that is simple for programmers to understand and offers good general performance.}
    42         \end{center}
    43 \end{frame}
    44 %------------------------------
     38\section{\CFA and Concurrency}
    4539\begin{frame}{\CFA}
    46         \CFA is a modern extension of C.
    47         It adds to C : overloading, constructors/destructors, polymorphism, and much more.
    48 
    49         ~\newline
    50         For this project, the relevant aspects are:
    51         \begin{itemize}
    52                 \item Fast and safe system language.
    53                 \item Threading.
    54                 \item Manual memory management.
    55         \end{itemize}
    5640
    5741\end{frame}
    … …  
    120104\begin{frame}{Priority Scheduling}
    121105        \begin{center}
    122                 {\large
     106        {\large
    123107                        Runs all ready threads in group \textit{A} before any ready threads in group \textit{B}.
    124108                }
    … …  
    152136
    153137        Processors begin busy for long periods can mean starvation.
    154 \end{frame}
    155 %------------------------------
    156 \begin{frame}{Scheduling in Practice: Summary}
    157         \begin{columns}
    158                 \begin{column}{0.5\textwidth}
    159                         \textbf{Feedback Scheduling}
    160                         \newline
    161 
    162                         \begin{itemize}
    163                                 \item Inappropriate for short lived threads.
    164                                 \item Overkill for cooperating threads.\newline
    165                         \end{itemize}
    166                 \end{column}
    167                 \begin{column}{0.5\textwidth}
    168                         \textbf{Priority Scheduling}
    169                         \newline
    170 
    171                         \begin{itemize}
    172                                 \item Allows lasting starvation.\newline
    173                                 \item Hard to reason about.\newline~\newline
    174                         \end{itemize}
    175                 \end{column}
    176         \end{columns}
    177 
    178         ~\newline
    179         ~\newline
    180         \CFA would benefit from something different.
    181138\end{frame}
    182139%==============================
    … …  
    233190        \begin{itemize}
    234191                \item Acquire for reading for normal scheduling operations.
    235                 \item Acquire for writing when resizing the array and creating/deleting internal queues.
     192                \item Acquire for right when resizing the array and creating/deleting internal queues.
    236193        \end{itemize}
    237194\end{frame}
    … …  
    357314        Runtime system and scheduling are still open topics.
    358315        \newline
    359         \newline
    360316
    361317        This work offers a novel runtime and scheduling package.
    362         \newline
    363318        \newline
    364319
    … …  
    381336
    382337%------------------------------
    383 \begin{frame}{}
     338\begin{frame}{Timeline}
    384339        \begin{center}
    385340                {\large Questions?}

  • doc/theses/thierry_delisle_PhD/comp_II/presentationstyle.sty

    rf7e4f8e8 r4ae78c1  
    2020\setbeamertemplate{blocks}[rounded][shadow=false]
    2121\newcommand\xrowht[2][0]{\addstackgap[.5\dimexpr#2\relax]{\vphantom{#1}}}
    22 \setbeamertemplate{sections/subsections in toc}{\inserttocsectionnumber.~\inserttocsection}
    2322
    2423%==============================
    … …  
    3736\setbeamercolor{palette primary}{bg=colbg}
    3837\setbeamercolor{palette tertiary}{fg=red}
    39 \setbeamercolor{section in toc}{fg=white}
    40 \setbeamercolor{subsection in toc}{fg=gray}
    4138
    4239%==============================

  • doc/theses/thierry_delisle_PhD/thesis/Makefile

    rf7e4f8e8 r4ae78c1  
    1515        front \
    1616        intro \
    17         existing \
    1817        runtime \
    1918        core \
    … …  
    2827        base \
    2928        empty \
    30         system \
    3129}
    3230
    … …  
    3937## Define the documents that need to be made.
    4038all: thesis.pdf
    41 thesis.pdf: ${TEXTS} ${FIGURES} ${PICTURES} glossary.tex local.bib
     39thesis.pdf: ${TEXTS} ${FIGURES} ${PICTURES} glossary.tex
    4240
    4341DOCUMENT = thesis.pdf

  • doc/theses/thierry_delisle_PhD/thesis/fig/system.fig

    rf7e4f8e8 r4ae78c1  
    1 #FIG 3.2  Produced by xfig version 3.2.7b
     1#FIG 3.2  Produced by xfig version 3.2.5c
    22Landscape
    33Center
    … …  
    36361 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 3600 15 15 4500 3600 4515 3615
    3737-6
     386 3225 4125 4650 4425
     396 4350 4200 4650 4350
     401 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 4275 15 15 4425 4275 4440 4290
     411 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 4275 15 15 4500 4275 4515 4290
     421 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4575 4275 15 15 4575 4275 4590 4290
     43-6
     441 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3450 4275 225 150 3450 4275 3675 4425
     451 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 4275 225 150 4050 4275 4275 4425
     46-6
     476 6675 4125 7500 4425
     486 7200 4200 7500 4350
     491 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7275 4275 15 15 7275 4275 7290 4290
     501 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7350 4275 15 15 7350 4275 7365 4290
     511 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7425 4275 15 15 7425 4275 7440 4290
     52-6
     531 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 4275 225 150 6900 4275 7125 4425
     54-6
    38556 6675 3525 8025 3975
    39562 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2
    … …  
    62791 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 2850 150 150 3975 2850 4125 2850
    63801 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 7200 2775 150 150 7200 2775 7350 2775
    64 1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4830
     811 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4860
    65821 3 0 1 0 0 0 0 0 0.000 1 0.0000 7200 2775 30 30 7200 2775 7230 2805
    66831 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 3600 150 150 3525 3600 3675 3600
    67 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4625 4838 100 100 4625 4838 4725 4838
     841 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3875 4800 100 100 3875 4800 3975 4800
     851 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 4800 150 75 4650 4800 4800 4875
    68862 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5
    6987         2400 4200 2400 3750 1950 3750 1950 4200 2400 4200
    … …  
    135153        1 1 1.00 45.00 90.00
    136154         7875 3750 7875 2325 7200 2325 7200 2550
     1552 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5
     156         5850 4950 5850 4725 5625 4725 5625 4950 5850 4950
    1371572 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5
    138158         6975 4950 6750 4950 6750 4725 6975 4725 6975 4950
    139 2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5
    140          5850 4950 5850 4725 5625 4725 5625 4950 5850 4950
    141 4 1 -1 0 0 0 10 0.0000 2 135 900 5550 4425 Processors\001
    142 4 1 -1 0 0 0 10 0.0000 2 165 1170 4200 3975 Ready Threads\001
    143 4 1 -1 0 0 0 10 0.0000 2 165 1440 7350 1725 Other Cluster(s)\001
    144 4 1 -1 0 0 0 10 0.0000 2 135 1080 4650 1725 User Cluster\001
    145 4 1 -1 0 0 0 10 0.0000 2 165 630 2175 3675 Manager\001
    146 4 1 -1 0 0 0 10 0.0000 2 135 1260 2175 3525 Discrete-event\001
    147 4 1 -1 0 0 0 10 0.0000 2 150 900 2175 4350 preemption\001
    148 4 0 -1 0 0 0 10 0.0000 2 135 630 7050 4875 cluster\001
    149 4 1 -1 0 0 0 10 0.0000 2 135 1350 4200 3225 Blocked Threads\001
    150 4 0 -1 0 0 0 10 0.0000 2 135 540 4800 4875 thread\001
    151 4 0 -1 0 0 0 10 0.0000 2 120 810 5925 4875 processor\001
    152 4 0 -1 0 0 0 10 0.0000 2 165 1710 2325 4875 generator/coroutine\001
     1594 1 -1 0 0 0 10 0.0000 2 105 720 5550 4425 Processors\001
     1604 1 -1 0 0 0 10 0.0000 2 120 1005 4200 3225 Blocked Tasks\001
     1614 1 -1 0 0 0 10 0.0000 2 150 870 4200 3975 Ready Tasks\001
     1624 1 -1 0 0 0 10 0.0000 2 135 1095 7350 1725 Other Cluster(s)\001
     1634 1 -1 0 0 0 10 0.0000 2 105 840 4650 1725 User Cluster\001
     1644 1 -1 0 0 0 10 0.0000 2 150 615 2175 3675 Manager\001
     1654 1 -1 0 0 0 10 0.0000 2 105 990 2175 3525 Discrete-event\001
     1664 1 -1 0 0 0 10 0.0000 2 135 795 2175 4350 preemption\001
     1674 0 -1 0 0 0 10 0.0000 2 150 1290 2325 4875 generator/coroutine\001
     1684 0 -1 0 0 0 10 0.0000 2 120 270 4050 4875 task\001
     1694 0 -1 0 0 0 10 0.0000 2 105 450 7050 4875 cluster\001
     1704 0 -1 0 0 0 10 0.0000 2 105 660 5925 4875 processor\001
     1714 0 -1 0 0 0 10 0.0000 2 105 555 4875 4875 monitor\001

  • doc/theses/thierry_delisle_PhD/thesis/glossary.tex

    rf7e4f8e8 r4ae78c1  
    11\makeglossaries
    22
    3 % ----------------------------------
    4 % Acronyms
    5 \newacronym{api}{API}{Application Programming Interface}
    6 \newacronym{fifo}{FIFO}{First-In, First-Out}
    7 \newacronym{io}{I/O}{Input and Output}
    8 \newacronym{numa}{NUMA}{Non-Uniform Memory Access}
    9 \newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
    10 \newacronym{tls}{TLS}{Thread Local Storage}
     3\longnewglossaryentry{hthrd}
     4{name={hardware thread}}
     5{
     6Threads representing the underlying hardware directly.
    117
    12 % ----------------------------------
    13 % Definitions
     8\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
     9}
    1410
    1511\longnewglossaryentry{thrd}
    16 {name={thread}}
     12{name={threads}}
    1713{
    1814Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system.
    1915
    2016\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
    21 }
    22 
    23 \longnewglossaryentry{proc}
    24 {name={processor}}
    25 {
    26 
    27 }
    28 
    29 \longnewglossaryentry{rQ}
    30 {name={ready-queue}}
    31 {
    32 
    33 }
    34 
    35 \longnewglossaryentry{uthrding}
    36 {name={user-level threading}}
    37 {
    38 
    39 
    40 \textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
    41 }
    42 
    43 % ----------------------------------
    44 
    45 \longnewglossaryentry{hthrd}
    46 {name={hardware thread}}
    47 {
    48 Threads representing the underlying hardware directly, \eg the CPU core, or hyper-thread if the hardware supports multiple threads of execution per core. The number of hardware threads is considered to be always fixed to a specific number determined by the hardware.
    49 
    50 \textit{Synonyms : }
    5117}
    5218
    … …  
    9157}
    9258
     59\longnewglossaryentry{proc}
     60{name={virtual processor}}
     61{
    9362
     63}
     64
     65\longnewglossaryentry{Q}
     66{name={work-queue}}
     67{
     68
     69}
    9470
    9571\longnewglossaryentry{at}
    … …  
    155131}
    156132
     133
     134\newacronym{tls}{TLS}{Thread Local Storage}
     135\newacronym{api}{API}{Application Program Interface}
     136\newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
     137\newacronym{numa}{NUMA}{Non-Uniform Memory Access}

  • doc/theses/thierry_delisle_PhD/thesis/text/core.tex

    rf7e4f8e8 r4ae78c1  
    11\chapter{Scheduling Core}\label{core}
    22
    3 Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenerio, where the system has reached a steady state. For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and but the system has the ressources necessary to accomplish the work. In short, the system is neither overloaded or underloaded.
     3This chapter addresses the need of scheduling on a somewhat ideal scenario
    44
    5 I believe it is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to the new load and return to the steady state. Flaws in the scheduling in the steady state tend therefore to be pervasive in all states.
     5\section{Existing Schedulers}
     6\subsection{Feedback Scheduling}
    67
    7 \section{Design Goals}
    8 As with most of the design decisions behind \CFA, the main goal is to match the expectation of the programmer, according to their probable mental model. To match these expectations, the design must offer the programmers sufficient guarantees so that, as long as the programmer respects the mental model, the system will also respect this model.
     8\subsection{Priority Scheduling}\label{priority}
    99
    10 For threading, a simple and common mental model is the ``Ideal multi-tasking CPU'' :
    11 
    12 \begin{displayquote}[Linux CFS\cit{https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt}]
    13         {[The]} ``Ideal multi-tasking CPU'' is a (non-existent  :-)) CPU that has 100\% physical power and which can run each task at precise equal speed, in parallel, each at [an equal fraction of the] speed.  For example: if there are 2 tasks running, then it runs each at 50\% physical power --- i.e., actually in parallel.
    14 \end{displayquote}
    15 
    16 Applied to threads, this model states that every ready \gls{thrd} immediately runs in parallel with all other ready \glspl{thrd}. While a strict implementation of this model is not feasible, programmers still have expectations about scheduling that come from this model.
    17 
    18 In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with eachother but simply share the hardware. This makes it easier to reason about threading because ready \glspl{thrd} can be taken in isolation and the effect of the scheduler can be virtually ignored. This expectation of \gls{thrd} independence means the scheduler is expected to offer 2 guarantees:
    19 \begin{enumerate}
    20         \item A fairness guarantee: a \gls{thrd} that is ready to run will not be prevented to do so by another thread.
    21         \item A performance guarantee: a \gls{thrd} that wants to start or stop running will not be slowed down by other threads wanting to do the same.
    22 \end{enumerate}
    23 
    24 It is important to note that these guarantees are expected only up to a point. \Glspl{thrd} that are ready to run should not be prevented to do so, but they still need to share a limited amount of hardware. Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware, even if that share is very small.
    25 
    26 Similarly the performance guarantee, the lack of interferance between threads is only relevant op to a point. Ideally the cost of running and blocking would be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. How much is an acceptable cost is obviously highly variable. For this document the performance experimentation will attempt to show that the cost of scheduling is not a major factor in application performance. This demonstration can be made by comparing application built in \CFA to applications built with other languages or other models. If the performance of an application built in \CFA is not meaningfully different than one built with a different runtime, then the scheduler has a negigeable impact on performance, \ie its impact can be ignored. Recall from a few paragraphs ago that the expectation of programmers is that the impact of the scheduler can be ignored. Therefore, if the cost of scheduling is not a significant portion of the runtime of several different application, I will consider the guarantee achieved.
    27 
    28 \todo{This paragraph should be moved later}
    29 % The next step is then to decide what is considered a \emph{fair share}, \ie what metric is used to measure fairness. Since \CFA is intended to allow numerous short lived threads, I decided to avoid total CPU time as the measure of fairness. Total CPU time inherently favors new \glspl{thrd} over older ones which isn't necessarily a good thing. Instead, fairness is measured in terms of opportunities to run. This metric is more appropriate for a mix of short and long lived \glspl{thrd}.
     10\subsection{Work Stealing}
    3011
    3112\section{Design}
    32 While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}. A strictly \glsxtrshort{fifo} rea
     13While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}.
    3314
    3415\subsection{Sharding}
    … …  
    3819                \input{base.pstex_t}
    3920        \end{center}
    40         \caption{Relaxed FIFO list}
     21        \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists.
     22        The timestamp is in all nodes and cell arrays.}
    4123        \label{fig:base}
    42         List at the base of the scheduler: an array of strictly FIFO lists.
    43         The timestamp is in all nodes and cell arrays.
    4424\end{figure}
    4525
    … …  
    4828Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty.
    4929Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time.
     30This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
     31
     32Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.
     33
     34\paragraph{Dense Information}
     35
     36
     37
    5038
    5139
    … …  
    5442                \input{empty.pstex_t}
    5543        \end{center}
    56         \caption{``More empty'' Relaxed FIFO list}
     44        \caption{``More empty'' state of the queue: the array contains many empty cells.}
    5745        \label{fig:empty}
    58         Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.
    5946\end{figure}
    60 
    61 This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
    62 
    63 Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.
    64 
    65 \paragraph{Dense Information}

  • doc/theses/thierry_delisle_PhD/thesis/text/front.tex

    rf7e4f8e8 r4ae78c1  
    184184\phantomsection         % allows hyperref to link to the correct page
    185185
    186 % TODOs and missing citations
    187 % -----------------------------
    188186\listofcits
    189187\listoftodos
    190 \cleardoublepage
    191 \phantomsection         % allows hyperref to link to the correct page
    192188
    193189

  • doc/theses/thierry_delisle_PhD/thesis/text/intro.tex

    rf7e4f8e8 r4ae78c1  
    1 \chapter*{Introduction}\label{intro}
    2 \todo{A proper intro}
    3 
    4 The C programming language\cit{C}
    5 
    6 The \CFA programming language\cite{cfa:frontpage,cfa:typesystem} which extends the C programming language to add modern safety and productiviy features while maintaining backwards compatibility. Among it's productiviy features, \CFA introduces support for threading\cit{CFA Concurrency}, to allow programmers to write modern concurrent and parallel programming.
    7 While previous work on the concurrent package of \CFA focused on features and interfaces, this thesis focuses on performance, introducing \glsxtrshort{api} changes only when required by performance considerations. More specifically, this thesis concentrates on scheduling and \glsxtrshort{io}. Prior to this work, the \CFA runtime used a strictly \glsxtrshort{fifo} \gls{rQ}.
    8 
    9 This work exclusively concentrates on Linux as it's operating system since the existing \CFA runtime and compiler does not already support other operating systems. Furthermore, as \CFA is yet to be released, supporting version of Linux older that the latest version is not a goal of this work.
     1\chapter{Introduction}

  • doc/theses/thierry_delisle_PhD/thesis/text/io.tex

    rf7e4f8e8 r4ae78c1  
    1 \chapter{User Level \glsxtrshort{io}}
    2 As mentionned in Section~\ref{prev:io}, User-Level \glsxtrshort{io} requires multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \glsxtrshort{io} operations. Various operating systems offer various forms of asynchronous operations and as mentioned in Chapter~\ref{intro}, this work is exclusively focuesd on Linux.
     1\chapter{I/O}
    32
    43\section{Existing options}
    5 Since \glsxtrshort{io} operations are generally handled by the
    64
    75\subsection{\texttt{epoll}, \texttt{poll} and \texttt{select}}
    … …  
    97\subsection{Linux's AIO}
    108
     9\subsection{\texttt{io\_uring}}
    1110
    12 
    13 \begin{displayquote}
    14         AIO is a horrible ad-hoc design, with the main excuse being "other,
    15         less gifted people, made that design, and we are implementing it for
    16         compatibility because database people - who seldom have any shred of
    17         taste - actually use it".
    18 
    19         But AIO was always really really ugly.
    20 
    21         \begin{flushright}
    22                 -- Linus Torvalds\cit{https://lwn.net/Articles/671657/}
    23         \end{flushright}
    24 \end{displayquote}
    25 
    26 Interestingly, in this e-mail answer, Linus goes on to describe
    27 ``a true \textit{asynchronous system call} interface''
    28 that does
    29 ``[an] arbitrary system call X with arguments A, B, C, D asynchronously using a kernel thread''
    30 in
    31 ``some kind of arbitrary \textit{queue up asynchronous system call} model''.
    32 This description is actually quite close to the interface of the interface described in the next section.
    33 
    34 \subsection{\texttt{io\_uring}}
    35 A very recent addition to Linux, \texttt{io\_uring}\cit{io\_uring} is a framework that aims to solve many of the problems listed with the above mentioned solutions.
    36 
    37 \subsection{Extra Kernel Threads}\label{io:morethreads}
    38 Finally, if the operating system does not offer any satisfying forms of asynchronous \glsxtrshort{io} operations, a solution is to fake it by creating a pool of \glspl{kthrd} and delegating operations to them in order to avoid blocking \glspl{proc}.
     11\subsection{Extra Kernel Threads}
    3912
    4013\subsection{Discussion}

  • doc/theses/thierry_delisle_PhD/thesis/text/practice.tex

    rf7e4f8e8 r4ae78c1  
    22The scheduling algorithm discribed in Chapter~\ref{core} addresses scheduling in a stable state.
    33However, it does not address problems that occur when the system changes state.
    4 Indeed the \CFA runtime, supports expanding and shrinking the number of KTHREAD\_place \todo{add kthrd to glossary}, both manually and, to some extent automatically.
     4Indeed the \CFA runtime, supports expanding and shrinking
     5
     6the number of KTHREAD\_place
     7
     8, both manually and, to some extent automatically.
    59This entails that the scheduling algorithm must support these transitions.
    610

  • doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex

    rf7e4f8e8 r4ae78c1  
    11\chapter{\CFA Runtime}
    2 This chapter offers an overview of the capabilities of the \CFA runtime prior to this work.
    32
    4 Threading in \CFA offers is based on \Gls{uthrding}, where \glspl{thrd} are the representation of a unit of work. As such, \CFA programmers should expect these units to be fairly inexpensive, that is: programmers should be able to create a large number of \glspl{thrd} and switch between \glspl{thrd} liberally without many concerns for performance.
    5 
    6 \section{M:N Threading}\label{prev:model}
    7 
    8 C traditionnally uses a 1:1 threading model. This model uses \glspl{kthrd} to achive parallelism and concurrency. In this model, every thread of computation maps to an object in the kernel. The kernel then has the responsibility of managing these threads, \eg creating, scheduling, blocking. This also entails that the kernel has a perfect view of every thread executing in the system\footnote{This is not completly true due to primitives like \texttt{futex}es, which have a significant portion of their logic in user space.}.
    9 
    10 By contrast \CFA uses an M:N threading models, where concurrency is achieved using many user-level threads mapped onto fewer \glspl{kthrd}. The user-level threads have the same semantic meaning as a \glspl{kthrd} in the 1:1 model, they represent an independant thread of execution with it's on stack. The difference is that user-level threads do not have a corresponding object in the kernel, they are handled by the runtime in user space and scheduled onto \glspl{kthrd}, referred to as \glspl{proc} in this document. \Glspl{proc} run a \gls{thrd} until it context switches out, it then choses a different \gls{thrd} to run.
     3\section{M:N Threading}
    114
    125\section{Clusters}
    13 \begin{figure}
    14         \begin{center}
    15                 \input{system.pstex_t}
    16         \end{center}
    17         \caption{Overview of the \CFA runtime}
    18         \label{fig:system}
    19         \Glspl{thrd} are scheduled inside a particular cluster, where it only runs on the \glspl{proc} which belong to the cluster. The discrete-event manager, which handles preemption and timeout, is a \gls{kthrd} which lives outside any cluster and does not run \glspl{thrd}.
    20 \end{figure}
    21 \CFA allows the option to group user-level threading, in the form of clusters. Both \glspl{thrd} and \glspl{proc} belong to a specific cluster. \Glspl{thrd} will only be scheduled onto \glspl{proc} in the same cluster and scheduling is done independantly of other clusters. Figure~\ref{fig:system} shows an overview if this system. This allows programmers to control more tightly parallelism. It also opens the door to handling effects like NUMA, by pining clusters to specific NUMA node\footnote{This is not currently implemented in \CFA, but the only hurdle left is creating a generic interface for cpu masks.}.
    22 
    23 \section{Scheduling}
    24 The \CFA runtime was previously using a strictly \glsxtrshort{fifo} ready queue with a single lock. This setup offers perfect fairness in terms of opportunities to run/ However, it offers poor scalability, since the performance of the ready queue can never be improved by adding more \glspl{hthrd}, but the contention can cause significant performance degradation.
    25 
    26 \section{\glsxtrshort{io}}\label{prev:io}
    27 Prior to this work, the \CFA runtime did not add any particular support for \glsxtrshort{io} operations. \CFA being built on C, this means that, while all the operations available in C are available in \CFA, \glsxtrshort{io} operations are designed for the POSIX threading model\cit{pthreads}. Using these operations in a M:N threading model, when they are built for 1:1 threading, means that operations block \glspl{proc} instead of \glspl{thrd}. While this can work in certain cases, it limits the number of concurrent operations to the number of \glspl{proc} rather than \glspl{thrd}. This also means that deadlocks can occur because all \glspl{proc} are blocked even if at least one \gls{thrd} is ready to run. A simple example of this type of deadlock would be as follows:
    28 
    29 Given a simple network program with 2 \glspl{thrd} and a single \gls{proc}, one \gls{thrd} sends network requests to a server and the other \gls{thrd} waits for response from the server. If the second \gls{thrd} races ahead, it may wait for responses to requests that have not been sent yet. In theory, this should not be a problem, even if the second \gls{thrd} waits, the first \gls{thrd} is still ready to run and should just be able to get CPU time and send the request. In practice with M:N threading, while the first \gls{thrd} is ready, the lone \gls{proc} in this example will \emph{not} try to run the first \gls{thrd} if it is blocked in the \glsxtrshort{io} operation of the second \gls{thrd}. If this happen, the system is effectively deadlocked\footnote{In this example, the deadlocked could be resolved if the server sends unprompted messages to the client. However, this solution is not general and may not be appropriate even in this simple case.}.
    30 
    31 One of the objective of this work, is to introduce \emph{User-Level \glsxtrshort{io}} which, as a parallel to \glslink{uthrding}{User-Level \emph{Threading}}, blocks \glspl{thrd} rather than \glspl{proc} when doing \glsxtrshort{io} operations. This entails multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc}. This multiplexing requires that a single \gls{proc} be able to execute multiple operations in parallel. This cannot be done with operations that block \glspl{proc}, \ie \glspl{kthrd}, since the first operation would prevent starting new operations for its duration. Executing operations in parallel requires \emph{asynchronous} \glsxtrshort{io}, sometimes referred to as \emph{non-blocking}, since the \gls{kthrd} is not blocked.
    326
    337\section{Interoperating with \texttt{C}}
    34 While \glsxtrshort{io} operations are the classical example of operations that block \glspl{kthrd}, the challenges mentioned in the previous section do not require \glsxtrshort{io} to be involved. These challenges are a product of blocking system calls rather than \glsxtrshort{io}. C offers no tools to identify whether or not a librairy function will lead to a blocking system call. This fact means interoperatability with C becomes a challenge in a M:N threading model.
    35 
    36 Languages like Go and Java, which have strict interoperatability with C\cit{JNI, GoLang with C}, can control operations in C by ``sandboxing'' them. They can, for example, delegate C operations to \glspl{kthrd} that are not \glspl{proc}. Sandboxing may help towards guaranteeing that the deadlocks mentioned in the previous section do not occur.
    37 
    38 As mentioned in Section~\cit{\CFA intro}, \CFA is binary compatible with C and, as such, trivially supports calls to and from C librairies. Furthermore, interoperatability can happen within a single library, through inline code or simply C and \CFA translation units archived together. The fine-grained interoperatability between C and \CFA has two consequences:
    39 \begin{enumerate}
    40         \item Precisely identifying C calls that could block is difficult.
    41         \item Introducing code where interoperatability occurs could have a significant impact on general performance.
    42 \end{enumerate}
    43 
    44 Because of these consequences, this work does not attempt to ``sandbox'' calls to C. It is possible that conflicting calls to C could lead to deadlocks on \CFA's M:N threading model where they would not in the traditionnal 1:1 threading model. However, I judge that solving this problem in general, in a way that is composable and flexible, is too complex in itself and would add too much work to this thesis. Therefore it is outside the scope of this thesis.

  • doc/theses/thierry_delisle_PhD/thesis/thesis.tex

    rf7e4f8e8 r4ae78c1  
    121121% installation instructions there.
    122122
    123 \usepackage{csquotes}
    124 \usepackage{indentfirst} % as any self-respecting frenchman would
    125 
    126123% Setting up the page margins...
    127124% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the
    … …  
    221218% separate documents, they would each start with the \chapter command, i.e,
    222219% do not contain \documentclass or \begin{document} and \end{document} commands.
    223 \part{Introduction}
    224220\input{text/intro.tex}
    225 \input{text/existing.tex}
    226221\input{text/runtime.tex}
    227 \part{Design}
    228222\input{text/core.tex}
    229223\input{text/practice.tex}
    230224\input{text/io.tex}
    231 \part{Evaluation}
    232 \chapter{Theoretical and Existance Proofs}
    233 \chapter{Micro-Benchmarks}
    234 \chapter{Larger-Scale applications}
    235 \part{Conclusion \& Annexes}
    236225
    237226%----------------------------------------------------------------------
    … …  
    256245\addcontentsline{toc}{chapter}{\textbf{References}}
    257246
    258 \bibliography{local}
     247\bibliography{uw-ethesis}
    259248% Tip 5: You can create multiple .bib files to organize your references.
    260249% Just list them all in the \bibliogaphy command, separated by commas (no spaces).
    261250
    262 % % The following statement causes the specified references to be added to the bibliography% even if they were not
    263 % % cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional).
    264 % \nocite{*}
     251% The following statement causes the specified references to be added to the bibliography% even if they were not
     252% cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional).
     253\nocite{*}
    265254
    266255% The \appendix statement indicates the beginning of the appendices.
Note: See TracChangeset for help on using the changeset viewer.