Ignore:
Timestamp:
Sep 19, 2022, 8:11:02 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, ast-experimental, master, pthread-emulation, stuck-waitfor-destruct
Children:
aa9f215
Parents:
ebf8ca5 (diff), ae1d151 (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:

fix merge conflict

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rebf8ca5 r23a08aa0  
    3939                \vspace*{2.0cm}
    4040
    41                 Waterloo, Ontario, Canada, 2021 \\
    42 
    43                 \vspace*{1.0cm}
    44 
    45                 \copyright\ Thierry Delisle 2021 \\
     41                Waterloo, Ontario, Canada, 2022 \\
     42
     43                \vspace*{1.0cm}
     44
     45                \copyright\ Thierry Delisle 2022 \\
    4646        \end{center}
    4747\end{titlepage}
    … …  
    6060\noindent
    6161        The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote.
    62         \todo{External Examiners}
    63 \bigskip
    64 
    65 \noindent
    66 \begin{tabbing}
    67         Internal-External Member: \=  \kill % using longest text to define tab length
    68         External Examiner: \>  TBD \\
    69         \> TBD \\
     62\bigskip
     63
     64\noindent
     65\begin{tabbing}
     66        Internal-External Member: \=  \kill % using longest text to define tab length
     67        External Examiner: \>  Doug Lea \\
     68        \> Professor, Computer Science Department \\
     69        \> State University of New York at Oswego \\
    7070\end{tabbing}
    7171\bigskip
    … …  
    9696\begin{tabbing}
    9797        Internal-External Member: \=  \kill % using longest text to define tab length
    98         Internal-External Member: \> TBD \\
    99         \> TBD \\
     98        Internal-External Member: \> Patrick Lam \\
     99        \> Associate Professor, Department of Electrical and Computer Engineering \\
    100100        \> University of Waterloo \\
    101101\end{tabbing}
    … …  
    124124
    125125User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages.
    126 The user threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multi-core systems.
     126The user threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multicore systems.
    127127Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities.
    128128To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads;
    129 which begs of the question of how many kernel threads are needed and should the number be dynamically reevaluated.
     129which begs the question of how many kernel threads are needed and should the number be dynamically reevaluated.
    130130Furthermore, scheduling must prevent kernel threads from blocking, otherwise user-thread parallelism drops.
    131 When user-threading parallelism does drop, how and when should idle kernel-threads be put to sleep to avoid wasting CPU resources.
     131When user-threading parallelism does drop, how and when should idle \glspl{kthrd} be put to sleep to avoid wasting CPU resources.
    132132Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread;
    133 otherwise other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur on busy kernel threads.
    134 
    135 This thesis analyses multiple scheduler systems, where each system attempts to fulfill the necessary requirements for user-level threading.
    136 The predominant technique for managing high levels of concurrency is sharding the ready-queue with one queue per kernel-thread and using some form of work stealing/sharing to dynamically rebalance workload shifts.
    137 Preventing kernel blocking is accomplish by transforming kernel locks and I/O operations into user-level operations that do not block the kernel thread or spin up new kernel threads to manage the blocking.
     133otherwise, other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur on busy kernel threads.
     134
     135This thesis analyses multiple scheduler systems, where each system attempts to fulfill the requirements for user-level threading.
     136The predominant technique for managing high levels of concurrency is sharding the ready queue with one queue per \gls{kthrd} and using some form of work stealing/sharing to dynamically rebalance workload shifts.
     137Preventing kernel blocking is accomplished by transforming kernel locks and I/O operations into user-level operations that do not block the kernel thread or spin up new kernel threads to manage the blocking.
    138138Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases.
    139139
    … …  
    146146The new scheduler also includes support for implicit nonblocking \io, allowing applications to have more user-threads blocking on \io operations than there are \glspl{kthrd}.
    147147The implementation is based on @io_uring@, a recent addition to the Linux kernel, and achieves the same performance and fairness as systems using @select@, @epoll@, \etc.
    148 To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside of the application.
     148To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside the application.
    149149
    150150\cleardoublepage
    … …  
    179179\phantomsection    % allows hyperref to link to the correct page
    180180
     181% L I S T   O F   F I G U R E S
     182% -----------------------------
     183\addcontentsline{toc}{chapter}{List of Figures}
     184\listoffigures
     185\cleardoublepage
     186\phantomsection         % allows hyperref to link to the correct page
     187
    181188% L I S T   O F   T A B L E S
    182189% ---------------------------
    … …  
    186193\phantomsection         % allows hyperref to link to the correct page
    187194
    188 % L I S T   O F   F I G U R E S
    189 % -----------------------------
    190 \addcontentsline{toc}{chapter}{List of Figures}
    191 \listoffigures
    192 \cleardoublepage
    193 \phantomsection         % allows hyperref to link to the correct page
    194 
    195195% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
    196196% -----------------------------
    … …  
    199199\phantomsection         % allows hyperref to link to the correct page
    200200
    201 % TODOs and missing citations
    202 % -----------------------------
    203 \listofcits
    204 \listoftodos
    205 \cleardoublepage
    206 \phantomsection         % allows hyperref to link to the correct page
    207 
    208 
    209201% Change page numbering back to Arabic numerals
    210202\pagenumbering{arabic}
Note: See TracChangeset for help on using the changeset viewer.