% T I T L E P A G E % ------------------- % Last updated June 14, 2017, by Stephen Carr, IST-Client Services % The title page is counted as page `i' but we need to suppress the % page number. Also, we don't want any headers or footers. \pagestyle{empty} \pagenumbering{roman} % The contents of the title page are specified in the "titlepage" % environment. \begin{titlepage} \begin{center} \vspace*{1.0cm} \Huge {\bf The \CFA Scheduler} \vspace*{1.0cm} \normalsize by \\ \vspace*{1.0cm} \Large Thierry Delisle \\ \vspace*{3.0cm} \normalsize A thesis \\ presented to the University of Waterloo \\ in fulfillment of the \\ thesis requirement for the degree of \\ Doctor of Philosophy \\ in \\ Computer Science \\ \vspace*{2.0cm} Waterloo, Ontario, Canada, 2021 \\ \vspace*{1.0cm} \copyright\ Thierry Delisle 2021 \\ \end{center} \end{titlepage} % The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii' \pagestyle{plain} \setcounter{page}{2} \cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed. % In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary. % E X A M I N I N G C O M M I T T E E (Required for Ph.D. theses only) % Remove or comment out the lines below to remove this page \begin{center}\textbf{Examining Committee Membership}\end{center} \noindent The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote. \todo{External Examiners} \bigskip \noindent \begin{tabbing} Internal-External Member: \= \kill % using longest text to define tab length External Examiner: \> TBD \\ \> TBD \\ \end{tabbing} \bigskip \noindent \begin{tabbing} Internal-External Member: \= \kill % using longest text to define tab length Supervisor(s): \> Peter Buhr \\ \> Associate Professor, School of Computer Science \\ \> University of Waterloo \\ \end{tabbing} \bigskip \noindent \begin{tabbing} Internal-External Member: \= \kill % using longest text to define tab length Internal Member: \> Trevor Brown \\ \> Assistant Professor, School of Computer Science \\ \> University of Waterloo \\ \\ Internal Member: \> Martin Karsten \\ \> Associate Professor, School of Computer Science \\ \> University of Waterloo \\ \end{tabbing} \bigskip \noindent \begin{tabbing} Internal-External Member: \= \kill % using longest text to define tab length Internal-External Member: \> TBD \\ \> TBD \\ \> University of Waterloo \\ \end{tabbing} \bigskip \cleardoublepage % D E C L A R A T I O N P A G E % ------------------------------- % The following is a sample Delaration Page as provided by the GSO % December 13th, 2006. It is designed for an electronic thesis. \noindent 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. \bigskip \noindent I understand that my thesis may be made electronically available to the public. \cleardoublepage % A B S T R A C T % --------------- \begin{center}\textbf{Abstract}\end{center} User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages. The user-level approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multi-core systems. 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. To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads; which begs of the question of how many kernel threads are needed and when should the need be re-evaliated. 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. Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread; otherwise other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur. This thesis analyses multiple scheduler systems, where each system attempts to fulfill the necessary requirements for user-level threading. 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. Fairness can be handled through preemption or ad-hoc solutions, which leads to coarse-grained fairness and pathological cases. 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. After selecting specific approaches to these scheduling issues, a complete implementation was created and tested in the \CFA (C-for-all) runtime system. \CFA is a modern extension of C using user-level threading as its fundamental threading model. As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance. The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness. 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. 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}. The implementation is based on @io_uring@, a recent addition to the Linux kernel, and achieves the same performance and fairness. To complete the picture, the idle sleep mechanism that goes along is presented. \cleardoublepage % A C K N O W L E D G E M E N T S % ------------------------------- \begin{center}\textbf{Acknowledgements}\end{center} \todo{Acknowledgements} \cleardoublepage % D E D I C A T I O N % ------------------- % \begin{center}\textbf{Dedication}\end{center} % This is dedicated to the one I love. % \cleardoublepage % T A B L E O F C O N T E N T S % --------------------------------- \renewcommand\contentsname{Table of Contents} \tableofcontents \cleardoublepage \phantomsection % allows hyperref to link to the correct page % L I S T O F T A B L E S % --------------------------- \addcontentsline{toc}{chapter}{List of Tables} \listoftables \cleardoublepage \phantomsection % allows hyperref to link to the correct page % L I S T O F F I G U R E S % ----------------------------- \addcontentsline{toc}{chapter}{List of Figures} \listoffigures \cleardoublepage \phantomsection % allows hyperref to link to the correct page % GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) % ----------------------------- \printglossary[type=\acronymtype] \cleardoublepage \phantomsection % allows hyperref to link to the correct page % TODOs and missing citations % ----------------------------- \listofcits \listoftodos \cleardoublepage \phantomsection % allows hyperref to link to the correct page % Change page numbering back to Arabic numerals \pagenumbering{arabic}