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 |
---|
111 | I 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 |
---|
116 | I 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 | |
---|
125 | User-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. |
---|
127 | Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities. |
---|
128 | To 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. |
---|
130 | Furthermore, 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 wasted CPU resources. |
---|
132 | Finally, 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. |
---|
138 | Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases. |
---|
139 | |
---|
140 | After 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. |
---|
142 | As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance. |
---|
143 | The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness. |
---|
144 | The implementation uses several optimizations that successfully balance the cost of fairness against performance; |
---|
145 | some of these optimization rely on interesting hardware optimizations present on modern CPUs. |
---|
146 | The 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}. |
---|
147 | The implementation is based on @io_uring@, a recent addition to the Linux kernel, and achieves the same performance and fairness. |
---|
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. |
---|
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 | |
---|