[585d910] | 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. |
---|
[86c1f1c3] | 11 | \begin{titlepage} |
---|
[d835116] | 12 | \begin{center} |
---|
| 13 | \vspace*{1.0cm} |
---|
[585d910] | 14 | |
---|
[d835116] | 15 | \Huge |
---|
| 16 | {\bf The \CFA Scheduler} |
---|
[585d910] | 17 | |
---|
[d835116] | 18 | \vspace*{1.0cm} |
---|
[585d910] | 19 | |
---|
[d835116] | 20 | \normalsize |
---|
| 21 | by \\ |
---|
[585d910] | 22 | |
---|
[d835116] | 23 | \vspace*{1.0cm} |
---|
[585d910] | 24 | |
---|
[d835116] | 25 | \Large |
---|
| 26 | Thierry Delisle \\ |
---|
[585d910] | 27 | |
---|
[d835116] | 28 | \vspace*{3.0cm} |
---|
[585d910] | 29 | |
---|
[d835116] | 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 \\ |
---|
[585d910] | 38 | |
---|
[d835116] | 39 | \vspace*{2.0cm} |
---|
[585d910] | 40 | |
---|
[d835116] | 41 | Waterloo, Ontario, Canada, 2021 \\ |
---|
[86c1f1c3] | 42 | |
---|
[d835116] | 43 | \vspace*{1.0cm} |
---|
[86c1f1c3] | 44 | |
---|
[d835116] | 45 | \copyright\ Thierry Delisle 2021 \\ |
---|
| 46 | \end{center} |
---|
[585d910] | 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} |
---|
[d835116] | 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 |
---|
[585d910] | 64 | |
---|
[d835116] | 65 | \noindent |
---|
[585d910] | 66 | \begin{tabbing} |
---|
[d835116] | 67 | Internal-External Member: \= \kill % using longest text to define tab length |
---|
| 68 | External Examiner: \> TBD \\ |
---|
| 69 | \> TBD \\ |
---|
[585d910] | 70 | \end{tabbing} |
---|
[d835116] | 71 | \bigskip |
---|
[585d910] | 72 | |
---|
[d835116] | 73 | \noindent |
---|
[585d910] | 74 | \begin{tabbing} |
---|
[d835116] | 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 \\ |
---|
[585d910] | 79 | \end{tabbing} |
---|
[d835116] | 80 | \bigskip |
---|
[585d910] | 81 | |
---|
[d835116] | 82 | \noindent |
---|
[585d910] | 83 | \begin{tabbing} |
---|
[d835116] | 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 \\ |
---|
[585d910] | 92 | \end{tabbing} |
---|
[d835116] | 93 | \bigskip |
---|
[585d910] | 94 | |
---|
[d835116] | 95 | \noindent |
---|
[585d910] | 96 | \begin{tabbing} |
---|
[d835116] | 97 | Internal-External Member: \= \kill % using longest text to define tab length |
---|
| 98 | Internal-External Member: \> TBD \\ |
---|
| 99 | \> TBD \\ |
---|
| 100 | \> University of Waterloo \\ |
---|
[585d910] | 101 | \end{tabbing} |
---|
[d835116] | 102 | \bigskip |
---|
[585d910] | 103 | |
---|
| 104 | \cleardoublepage |
---|
| 105 | |
---|
| 106 | % D E C L A R A T I O N P A G E |
---|
| 107 | % ------------------------------- |
---|
[d835116] | 108 | % The following is a sample Delaration Page as provided by the GSO |
---|
| 109 | % December 13th, 2006. It is designed for an electronic thesis. |
---|
| 110 | \noindent |
---|
[86c1f1c3] | 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 | |
---|
[d835116] | 113 | \bigskip |
---|
[86c1f1c3] | 114 | |
---|
[d835116] | 115 | \noindent |
---|
[585d910] | 116 | I understand that my thesis may be made electronically available to the public. |
---|
[86c1f1c3] | 117 | |
---|
[585d910] | 118 | \cleardoublepage |
---|
[86c1f1c3] | 119 | |
---|
[585d910] | 120 | % A B S T R A C T |
---|
| 121 | % --------------- |
---|
[86c1f1c3] | 122 | |
---|
| 123 | \begin{center}\textbf{Abstract}\end{center} |
---|
| 124 | |
---|
[d0fcc82] | 125 | User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages. |
---|
| 126 | The user-level 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 significantly eases load balancing while providing user threads for each unit of work offers greater freedom to the programmer. |
---|
| 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 when should the need be re-evaliated. |
---|
| 130 | Furthermore, the scheduler must prevent kernel threads from blocking, otherwise user-thread parallelism drops, and put idle kernel-threads to sleep to avoid wasted resources. |
---|
| 131 | Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread; |
---|
| 132 | otherwise other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur. |
---|
| 133 | |
---|
| 134 | This thesis analyses multiple scheduler systems, where each system attempts to fulfill the necessary requirements for user-level threading. |
---|
| 135 | The predominant technique for manage high levels of concurrency is sharding the ready-queue with one queue per kernel-threads and using some form of work stealing/sharing to dynamically rebalance workload shifts. |
---|
| 136 | Fairness can be handled through preemption or ad-hoc solutions, which leads to coarse-grained fairness and pathological cases. |
---|
| 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 | |
---|
| 139 | After selecting specific approaches to these scheduling issues, a complete implementation was created and tested in the \CFA (C-for-all) runtime system. |
---|
| 140 | \CFA is a modern extension of C using user-level threading as its fundamental threading model. |
---|
| 141 | As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance. |
---|
| 142 | The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness. |
---|
| 143 | This is achieved through several optimization that successfully eliminate the cost of the additional fairness, some of these optimization relying on interesting hardware optimizations present on most modern cpus. |
---|
| 144 | This work also includes support for user-level \io, allowing programmers to have many more user-threads blocking on \io operations than there are \glspl{kthrd}. |
---|
| 145 | The implementation is based on @io_uring@, a recent addition to the Linux kernel, and achieves the same performance and fairness. |
---|
| 146 | To complete the picture, the idle sleep mechanism that goes along is presented. |
---|
[86c1f1c3] | 147 | |
---|
| 148 | |
---|
| 149 | |
---|
[585d910] | 150 | \cleardoublepage |
---|
[86c1f1c3] | 151 | |
---|
[585d910] | 152 | % A C K N O W L E D G E M E N T S |
---|
| 153 | % ------------------------------- |
---|
[86c1f1c3] | 154 | |
---|
[585d910] | 155 | \begin{center}\textbf{Acknowledgements}\end{center} |
---|
| 156 | |
---|
[d835116] | 157 | \todo{Acknowledgements} |
---|
[585d910] | 158 | \cleardoublepage |
---|
| 159 | |
---|
| 160 | % D E D I C A T I O N |
---|
| 161 | % ------------------- |
---|
[86c1f1c3] | 162 | |
---|
[d835116] | 163 | % \begin{center}\textbf{Dedication}\end{center} |
---|
[86c1f1c3] | 164 | |
---|
[d835116] | 165 | % This is dedicated to the one I love. |
---|
| 166 | % \cleardoublepage |
---|
[585d910] | 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 | % ----------------------------- |
---|
[d835116] | 191 | \printglossary[type=\acronymtype] |
---|
[585d910] | 192 | \cleardoublepage |
---|
| 193 | \phantomsection % allows hyperref to link to the correct page |
---|
| 194 | |
---|
[b9537e6] | 195 | % TODOs and missing citations |
---|
| 196 | % ----------------------------- |
---|
[d835116] | 197 | \listofcits |
---|
| 198 | \listoftodos |
---|
[b9537e6] | 199 | \cleardoublepage |
---|
| 200 | \phantomsection % allows hyperref to link to the correct page |
---|
[d835116] | 201 | |
---|
| 202 | |
---|
[585d910] | 203 | % Change page numbering back to Arabic numerals |
---|
| 204 | \pagenumbering{arabic} |
---|
[86c1f1c3] | 205 | |
---|