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

% 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.
\bigskip

\noindent
\begin{tabbing}
        Internal-External Member: \=  \kill % using longest text to define tab length
        External Examiner: \>  Doug Lea \\
        \> Professor and Department Chair, Computer Science Department \\
        \> State University of New York at Oswego \\
\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: \> Patrick Lam \\
        \> Associate Professor, Department of Electrical and Computer Engineering \\
        \> 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 Declaration 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 threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multicore systems.
Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities.
To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads;
which begs the question of how many kernel threads are needed and should the number be dynamically reevaluated.
Furthermore, scheduling must prevent kernel threads from blocking, otherwise user-thread parallelism drops.
When user-threading parallelism does drop, how and when should idle \glspl{kthrd} be put to sleep to avoid wasting CPU 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 on busy kernel threads.

This thesis analyses multiple scheduler systems, where each system attempts to fulfill the requirements for user-level threading.
The 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.
Preventing 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.
Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases.

After examining, selecting and testing 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.
The implementation uses several optimizations that successfully balance the cost of fairness against performance;
some of these optimizations rely on interesting hardware optimizations present on modern CPUs.
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}.
The 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.
To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside the application.

\cleardoublepage

% A C K N O W L E D G E M E N T S
% -------------------------------

\begin{center}\textbf{Acknowledgements}\end{center}

I would like to thank my supervisor, Professor Peter Buhr, for his guidance through my degree as well as the editing of this document.

I would like to thank Professors Martin Karsten and Trevor Brown, for reading my thesis and providing helpful feedback.

Thanks to Andrew Beach, Michael Brooks, Colby Parsons, Mubeen Zulfiqar, Fangren Yu and Jiada Liang for their work on the \CFA project as well as all the discussions which have helped me concretize the ideas in this thesis.

Finally, I acknowledge that this has been possible thanks to the financial help offered by the David R. Cheriton School of Computer Science and the corporate partnership with Huawei Ltd.
\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}