source: doc/theses/thierry_delisle_PhD/thesis/text/front.tex

pthread-emulation
Last change on this file was 80d16f8, checked in by Peter A. Buhr <pabuhr@…>, 8 days ago

small wording changes to abstract

  • Property mode set to 100644
File size: 7.7 KB
Line 
1% T I T L E   P A G E
2% -------------------
3% Last updated June 14, 2017, by Stephen Carr, IST-Client Services
4% The title page is counted as page `i' but we need to suppress the
5% page number. Also, we don't want any headers or footers.
6\pagestyle{empty}
7\pagenumbering{roman}
8
9% The contents of the title page are specified in the "titlepage"
10% environment.
11\begin{titlepage}
12        \begin{center}
13                \vspace*{1.0cm}
14
15                \Huge
16                {\bf The \CFA Scheduler}
17
18                \vspace*{1.0cm}
19
20                \normalsize
21                by \\
22
23                \vspace*{1.0cm}
24
25                \Large
26                Thierry Delisle \\
27
28                \vspace*{3.0cm}
29
30                \normalsize
31                A thesis \\
32                presented to the University of Waterloo \\
33                in fulfillment of the \\
34                thesis requirement for the degree of \\
35                Doctor of Philosophy \\
36                in \\
37                Computer Science \\
38
39                \vspace*{2.0cm}
40
41                Waterloo, Ontario, Canada, 2021 \\
42
43                \vspace*{1.0cm}
44
45                \copyright\ Thierry Delisle 2021 \\
46        \end{center}
47\end{titlepage}
48
49% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii'
50\pagestyle{plain}
51\setcounter{page}{2}
52
53\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
54% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.
55
56
57% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
58% Remove or comment out the lines below to remove this page
59\begin{center}\textbf{Examining Committee Membership}\end{center}
60\noindent
61        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 \\
70\end{tabbing}
71\bigskip
72
73\noindent
74\begin{tabbing}
75        Internal-External Member: \=  \kill % using longest text to define tab length
76        Supervisor(s): \> Peter Buhr \\
77        \> Associate Professor, School of Computer Science \\
78        \> University of Waterloo \\
79\end{tabbing}
80\bigskip
81
82\noindent
83\begin{tabbing}
84        Internal-External Member: \=  \kill % using longest text to define tab length
85        Internal Member: \> Trevor Brown \\
86        \> Assistant Professor, School of Computer Science \\
87        \> University of Waterloo \\
88        \\
89        Internal Member: \> Martin Karsten \\
90        \> Associate Professor, School of Computer Science \\
91        \> University of Waterloo \\
92\end{tabbing}
93\bigskip
94
95\noindent
96\begin{tabbing}
97        Internal-External Member: \=  \kill % using longest text to define tab length
98        Internal-External Member: \> TBD \\
99        \> TBD \\
100        \> University of Waterloo \\
101\end{tabbing}
102\bigskip
103
104\cleardoublepage
105
106% D E C L A R A T I O N   P A G E
107% -------------------------------
108% The following is a sample Declaration Page as provided by the GSO
109% December 13th, 2006.  It is designed for an electronic thesis.
110\noindent
111I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
112
113\bigskip
114
115\noindent
116I understand that my thesis may be made electronically available to the public.
117
118\cleardoublepage
119
120% A B S T R A C T
121% ---------------
122
123\begin{center}\textbf{Abstract}\end{center}
124
125User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages.
126The user threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multi-core systems.
127Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities.
128To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads;
129which begs of the question of how many kernel threads are needed and should the number be dynamically reevaluated.
130Furthermore, scheduling must prevent kernel threads from blocking, otherwise user-thread parallelism drops.
131When user-threading parallelism does drop, how and when should idle kernel-threads be put to sleep to avoid wasted CPU resources.
132Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread;
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 necessary requirements for user-level threading.
136The 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.
137Preventing 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.
138Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases.
139
140After testing and selecting specific approaches to these scheduling issues, a complete implementation was created and tested in the \CFA (C-for-all) runtime system.
141\CFA is a modern extension of C using user-level threading as its fundamental threading model.
142As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance.
143The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness.
144The implementation uses several optimizations that successfully balance the cost of fairness against performance;
145some of these optimizations rely on interesting hardware optimizations present on modern CPUs.
146The 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}.
147The 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.
148To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside of the application.
149
150\cleardoublepage
151
152% A C K N O W L E D G E M E N T S
153% -------------------------------
154
155\begin{center}\textbf{Acknowledgements}\end{center}
156
157\todo{Acknowledgements}
158\cleardoublepage
159
160% D E D I C A T I O N
161% -------------------
162
163% \begin{center}\textbf{Dedication}\end{center}
164
165% This is dedicated to the one I love.
166% \cleardoublepage
167
168% T A B L E   O F   C O N T E N T S
169% ---------------------------------
170\renewcommand\contentsname{Table of Contents}
171\tableofcontents
172\cleardoublepage
173\phantomsection    % allows hyperref to link to the correct page
174
175% L I S T   O F   T A B L E S
176% ---------------------------
177\addcontentsline{toc}{chapter}{List of Tables}
178\listoftables
179\cleardoublepage
180\phantomsection         % allows hyperref to link to the correct page
181
182% L I S T   O F   F I G U R E S
183% -----------------------------
184\addcontentsline{toc}{chapter}{List of Figures}
185\listoffigures
186\cleardoublepage
187\phantomsection         % allows hyperref to link to the correct page
188
189% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
190% -----------------------------
191\printglossary[type=\acronymtype]
192\cleardoublepage
193\phantomsection         % allows hyperref to link to the correct page
194
195% TODOs and missing citations
196% -----------------------------
197\listofcits
198\listoftodos
199\cleardoublepage
200\phantomsection         % allows hyperref to link to the correct page
201
202
203% Change page numbering back to Arabic numerals
204\pagenumbering{arabic}
205
Note: See TracBrowser for help on using the repository browser.