Index: doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex (revision e4855f684383f7bd8f4a3a1ad28663c2f6d307c7) +++ doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex (revision 918e013764524a1728c269d95056f4b9dff17a6d) @@ -9,9 +9,9 @@ However, I discovered two significant challenges. -First, modern symmetric multiprocessing CPU have significant performance penalties for communication (often cache related). +First, modern symmetric multiprocessing CPU have significant performance penalties for communicationm, often cache related. A SQMS scheduler (see Section~\ref{sched}), with its \proc-shared ready-queue, has perfect load-balancing but poor affinity resulting in high communication across \procs. A MQMS scheduler, with its \proc-specific ready-queues, has poor load-balancing but perfect affinity often resulting in significantly reduced communication. However, implementing fairness for an MQMS scheduler is difficult, since fairness requires \procs to be aware of each other's ready-queue progress, \ie communicated knowledge. -For balanced workloads with little or no data sharing (embarrassingly parallel), an MQMS scheduler, \eg a state-of-the-art work-stealing scheduler, is near optimal. +For balanced workloads with little or no data sharing, \ie embarrassingly parallel, an MQMS scheduler is near optimal, \eg a state-of-the-art work-stealing scheduler. For these kinds of fair workloads, adding fairness must be low-cost to hide the communication costs needed for global ready-queue progress or performance suffers. While I was aware of these realities, I underestimated how little performance margin there is for communication. Index: doc/theses/thierry_delisle_PhD/thesis/text/existing.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/existing.tex (revision e4855f684383f7bd8f4a3a1ad28663c2f6d307c7) +++ doc/theses/thierry_delisle_PhD/thesis/text/existing.tex (revision 918e013764524a1728c269d95056f4b9dff17a6d) @@ -8,25 +8,25 @@ A secondary aspect is how much information can be gathered versus how much information must be given as part of the scheduler input. This information adds to the spectrum of scheduling algorithms, going from static schedulers that are well-informed from the start, to schedulers that gather most of the information needed, to schedulers that can only rely on very limited information. -Note, this description includes both information about each request, \eg time to complete or resources needed, and information about the relationships among request, \eg whether some request must be completed before another request starts. - -Scheduling physical resources, \eg in an assembly line, is generally amenable to using well-informed scheduling, since information can be gathered much faster than the physical resources can be assigned and workloads are likely to stay stable for long periods of time. +Note, this description includes both information about each request, \eg time to complete or resources needed, and information about the relationships among requests, \eg whether some requests must be completed before another request starts. + +Scheduling physical resources, \eg in an assembly line, is generally amenable to using well-informed scheduling since information can be gathered much faster than the physical resources can be assigned and workloads are likely to stay stable for long periods. When a faster pace is needed and changes are much more frequent gathering information on workloads, up-front or live, can become much more limiting and more general schedulers are needed. \section{Naming Convention} -Scheduling has been studied by various communities concentrating on different incarnation of the same problems. -As a result, there are no standard naming conventions for scheduling that is respected across these communities. +Scheduling has been studied by various communities concentrating on different incarnations of the same problems. +As a result, there are no standard naming conventions for scheduling that are respected across these communities. This document uses the term \newterm{\Gls{at}} to refer to the abstract objects being scheduled and the term \newterm{\Gls{proc}} to refer to the concrete objects executing these \ats. \section{Static Scheduling} -\newterm{Static schedulers} require \ats dependencies and costs be explicitly and exhaustively specified prior to scheduling. +\newterm{Static schedulers} require \ats dependencies and costs to be explicitly and exhaustively specified prior to scheduling. The scheduler then processes this input ahead of time and produces a \newterm{schedule} the system follows during execution. This approach is popular in real-time systems since the need for strong guarantees justifies the cost of determining and supplying this information. -In general, static schedulers are less relevant to this project because they require input from the programmers that the programming language does not have as part of its concurrency semantic. +In general, static schedulers are less relevant to this project because they require input from the programmers that the programming language does not have as part of its concurrency semantics. Specifying this information explicitly adds a significant burden to the programmer and reduces flexibility. For this reason, the \CFA scheduler does not require this information. \section{Dynamic Scheduling} -\newterm{Dynamic schedulers} determine \ats dependencies and costs during scheduling, if at all. -Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime. +\newterm{Dynamic schedulers} determine \at dependencies and costs during scheduling, if at all. +Hence, unlike static scheduling, \at dependencies are conditional and detected at runtime. This detection takes the form of observing new \ats in the system and determining dependencies from their behaviour, including suspending or halting a \at that dynamically detects unfulfilled dependencies. Furthermore, each \at has the responsibility of adding dependent \ats back into the system once dependencies are fulfilled. @@ -40,5 +40,5 @@ at best, the scheduler has only some imprecise information provided by the programmer, \eg, indicating a \at takes approximately 3--7 seconds to complete, rather than exactly 5 seconds. Providing this kind of information is a significant programmer burden, especially if the information does not scale with the number of \ats and their complexity. -For example, providing an exhaustive list of files read by 5 \ats is an easier requirement then providing an exhaustive list of memory addresses accessed by 10,000 independent \ats. +For example, providing an exhaustive list of files read by 5 \ats is an easier requirement than providing an exhaustive list of memory addresses accessed by 10,000 independent \ats. Since the goal of this thesis is to provide a scheduler as a replacement for \CFA's existing \emph{uninformed} scheduler, explicitly informed schedulers are less relevant to this project. Nevertheless, some strategies are worth mentioning. @@ -49,10 +49,10 @@ The simplest priority scheduling algorithm is to require that every \at have a distinct pre-established priority and always run the available \ats with the highest priority. Asking programmers to provide an exhaustive set of unique priorities can be prohibitive when the system has a large number of \ats. -It can therefore be desirable for schedulers to support \ats with identical priorities and/or automatically setting and adjusting priorities for \ats. +It can therefore be desirable for schedulers to support \ats with identical priorities and/or automatically set and adjust priorities for \ats. Most common operating systems use some variant on priorities with overlaps and dynamic priority adjustments. For example, Microsoft Windows uses a pair of priorities~\cite{win:priority}, one specified by users out of ten possible options and one adjusted by the system. \subsection{Uninformed and Self-Informed Dynamic Schedulers} -Several scheduling algorithms do not require programmers to provide additional information on each \at, and instead make scheduling decisions based solely on internal state and/or information implicitly gathered by the scheduler. +Several scheduling algorithms do not require programmers to provide additional information on each \at, and instead, make scheduling decisions based solely on internal state and/or information implicitly gathered by the scheduler. @@ -61,13 +61,13 @@ This design effectively moves the scheduler into the realm of \newterm{Control Theory}~\cite{wiki:controltheory}. This information gathering does not generally involve programmers, and as such, does not increase programmer burden the same way explicitly provided information may. -However, some feedback schedulers do allow programmers to offer additional information on certain \ats, in order to direct scheduling decisions. -The important distinction being whether the scheduler can function without this additional information. +However, some feedback schedulers do allow programmers to offer additional information on certain \ats, to direct scheduling decisions. +The important distinction is whether the scheduler can function without this additional information. \section{Work Stealing}\label{existing:workstealing} -One of the most popular scheduling algorithm in practice (see~\ref{existing:prod}) is work stealing. -This idea, introduced by \cite{DBLP:conf/fpca/BurtonS81}, effectively has each worker process its local \ats first, but allows the possibility for other workers to steal local \ats if they run out of \ats. +One of the most popular scheduling algorithms in practice (see~\ref{existing:prod}) is work stealing. +This idea, introduced by \cite{DBLP:conf/fpca/BurtonS81}, effectively has each worker process its local \ats first but allows the possibility for other workers to steal local \ats if they run out of \ats. \cite{DBLP:conf/focs/Blumofe94} introduced the more familiar incarnation of this, where each worker has a queue of \ats and workers without \ats steal \ats from random workers\footnote{The Burton and Sleep algorithm has trees of \ats and steals only among neighbours.}. -Blumofe and Leiserson also prove worst case space and time requirements for well-structured computations. +Blumofe and Leiserson also prove worst-case space and time requirements for well-structured computations. Many variations of this algorithm have been proposed over the years~\cite{DBLP:journals/ijpp/YangH18}, both optimizations of existing implementations and approaches that account for new metrics. @@ -86,6 +86,6 @@ Another example is energy usage, where the scheduler is modified to optimize for energy efficiency in addition/instead of performance~\cite{ribic2014energy,torng2016asymmetry}. -\paragraph{Complex Machine Architecture} Another aspect that has been examined is how well work stealing is applicable to different machine architectures. -This is arguably strongly related to Task Placement, but extends into more heterogeneous architectures. +\paragraph{Complex Machine Architecture} Another aspect that has been examined is how applicable work stealing is to different machine architectures. +This is arguably strongly related to Task Placement but extends into more heterogeneous architectures. As \CFA offers no particular support for heterogeneous architecture, this is also an area that is less relevant to this thesis. Although it could be an interesting avenue for future work. @@ -94,5 +94,5 @@ There is also a large body of research on the theoretical aspects of work stealing. These evaluate, for example, the cost of \glslink{atmig}{migration}~\cite{DBLP:conf/sigmetrics/SquillanteN91,DBLP:journals/pe/EagerLZ86}, how affinity affects performance~\cite{DBLP:journals/tpds/SquillanteL93,DBLP:journals/mst/AcarBB02,DBLP:journals/ipl/SuksompongLS16} and theoretical models for heterogeneous systems~\cite{DBLP:journals/jpdc/MirchandaneyTS90,DBLP:journals/mst/BenderR02,DBLP:conf/sigmetrics/GastG10}. \cite{DBLP:journals/jacm/BlellochGM99} examines the space bounds of work stealing and \cite{DBLP:journals/siamcomp/BerenbrinkFG03} shows that for under-loaded systems, the scheduler completes its computations in finite time, \ie is \newterm{stable}. -Others show that work stealing is applicable to various scheduling contexts~\cite{DBLP:journals/mst/AroraBP01,DBLP:journals/anor/TchiboukdjianGT13,DBLP:conf/isaac/TchiboukdjianGTRB10,DBLP:conf/ppopp/AgrawalLS10,DBLP:conf/spaa/AgrawalFLSSU14}. +Others show that work stealing applies to various scheduling contexts~\cite{DBLP:journals/mst/AroraBP01,DBLP:journals/anor/TchiboukdjianGT13,DBLP:conf/isaac/TchiboukdjianGTRB10,DBLP:conf/ppopp/AgrawalLS10,DBLP:conf/spaa/AgrawalFLSSU14}. \cite{DBLP:conf/ipps/ColeR13} also studied how randomized work-stealing affects false sharing among \ats. @@ -101,8 +101,8 @@ \section{Preemption} -One last aspect of scheduling is preemption, since many schedulers rely on it for some of their guarantees. +One last aspect of scheduling is preemption since many schedulers rely on it for some of their guarantees. Preemption is the idea of interrupting \ats that have been running too long, effectively injecting suspend points into the application. -There are multiple techniques to achieve this effect, but they all aim to guarantee that the suspend points in a \ats are never further apart than some fixed duration. -While this helps schedulers guarantee that no \ats unfairly monopolizes a worker, preemption can effectively be added to any scheduler. +There are multiple techniques to achieve this effect, but they all aim to guarantee that the suspend points in a \at are never further apart than some fixed duration. +While this helps schedulers guarantee that no \ats unfairly monopolize a worker, preemption can effectively be added to any scheduler. Therefore, the only interesting aspect of preemption for the design of scheduling is whether to require it. @@ -111,5 +111,5 @@ While these schedulers do not necessarily represent the most recent advances in scheduling, they are what is generally accessible to programmers. As such, I believe these schedulers are at least as relevant as those presented in published work. -Schedulers that operate in kernel space and in user space are considered, as both can offer relevant insight for this project. +Both Schedulers that operate in kernel space and user space are considered, as both can offer relevant insight for this project. However, real-time schedulers are not considered, as these have constraints that are much stricter than what is needed for this project. @@ -117,5 +117,5 @@ Operating System Schedulers tend to be fairly complex as they generally support some amount of real-time, aim to balance interactive and non-interactive \ats and support multiple users sharing hardware without requiring these users to cooperate. Here are more details on a few schedulers used in the common operating systems: Linux, FreeBSD, Microsoft Windows and Apple's OS X. -The information is less complete for operating systems with closed source. +The information is less complete for closed source operating systems. \paragraph{Linux's CFS} @@ -124,9 +124,9 @@ The \at that has used the least CPU time is scheduled. It also supports the concept of \newterm{Nice values}, which are effectively multiplicative factors on the CPU time used. -The ordering of \ats is also affected by a group based notion of fairness, where \ats belonging to groups having used less CPU time are preferred to \ats belonging to groups having used more CPU time. +The ordering of \ats is also affected by a group-based notion of fairness, where \ats belonging to groups having used less CPU time are preferred to \ats belonging to groups having used more CPU time. Linux achieves load-balancing by regularly monitoring the system state~\cite{MAN:linux/cfs/balancing} and using some heuristic on the \gls{load}, currently CPU time used in the last millisecond plus a decayed version of the previous time slots~\cite{MAN:linux/cfs/pelt}. \cite{DBLP:conf/eurosys/LoziLFGQF16} shows that Linux's CFS also does work stealing to balance the workload of each \proc, but the paper argues this aspect can be improved significantly. -The issues highlighted stem from Linux's need to support fairness across \ats \emph{and} across users\footnote{Enforcing fairness across users means that given two users, one with a single \at and the other with one thousand \ats, the user with a single \at does not receive one thousandth of the CPU time.}, increasing the complexity. +The issues highlighted stem from Linux's need to support fairness across \ats \emph{and} across users\footnote{Enforcing fairness across users means that given two users, one with a single \at and the other with one thousand \ats, the user with a single \at does not receive one-thousandth of the CPU time.}, increasing the complexity. Linux also offers a FIFO scheduler, a real-time scheduler, which runs the highest-priority \ats, and a round-robin scheduler, which is an extension of the FIFO-scheduler that adds fixed time slices. \cite{MAN:linux/sched} @@ -135,5 +135,5 @@ The ULE scheduler used in FreeBSD\cite{DBLP:conf/bsdcon/Roberson03} is a feedback scheduler similar to Linux's CFS. It uses different data structures and heuristics but also schedules according to some combination of CPU time used and niceness values. -It also periodically balances the load of the system (according to a different heuristic), but uses a simpler work stealing approach. +It also periodically balances the load of the system (according to a different heuristic) but uses a simpler work stealing approach. \paragraph{Windows(OS)} @@ -143,9 +143,9 @@ The scheduler may also temporarily adjust priorities after certain effects like the completion of I/O requests. -In~\cite{russinovich2009windows}, Chapter 1 section 2.3 ``Processes, Threads, and Jobs'' discusses the scheduling policy more in depth. -Multicore scheduling is based on a combination of priorities and preferred \proc. +In~\cite{russinovich2009windows}, Chapter 1 section 2.3 ``Processes, Threads, and Jobs'' discusses the scheduling policy more in-depth. +Multicore scheduling is based on a combination of priorities and \proc preferance. Each \at is assigned an initial processor using a round-robin policy, called the \at's \newterm{ideal} \proc. \Glspl{at} are distributed among the \procs according to their priority, preferring to match \ats to their ideal \proc and then to the last \proc they ran on. -This approach is a variation of work stealing, where the stealing \proc restore the \at to its original \proc after running it, but mixed with priorities. +This approach is a variation of work stealing, where the stealing \proc restores the \at to its original \proc after running it, but mixed with priorities. \paragraph{Apple OS X} @@ -160,13 +160,13 @@ There is very little documentation on the internals of this scheduler. -However, the documentation do describe a feature set that is very similar to the Windows and Linux OS schedulers. +However, the documentation does describe a feature set that is very similar to the Windows and Linux OS schedulers. Presumably, this means that the internals are also fairly similar overall. \subsection{User-Level Schedulers} -By comparison, user level schedulers tend to be simpler, gathering fewer metrics and avoid complex notions of fairness. Part of the simplicity is due to the fact that all \ats have the same user, and therefore cooperation is both feasible and probable. +By comparison, user-level schedulers tend to be simpler, gather fewer metrics and avoid complex notions of fairness. Part of the simplicity is due to the fact that all \ats have the same user, and therefore cooperation is both feasible and probable. \paragraph{Go}\label{GoSafePoint} Go's scheduler uses a randomized work-stealing algorithm that has a global run-queue (\emph{GRQ}) and each processor (\emph{P}) has both a fixed-size run-queue (\emph{LRQ}) and a high-priority next ``chair'' holding a single element~\cite{GITHUB:go,YTUBE:go}. -Preemption is present, but only at safe-points,~\cite{go:safepoints} which are inserted detection code at various frequent access boundaries. +Preemption is present, but only at safe points,~\cite{go:safepoints} which are detection code inserted at various frequent access boundaries. The algorithm is as follows : @@ -184,5 +184,5 @@ Erlang is a functional language that supports concurrency in the form of processes: threads that share no data. It uses a kind of round-robin scheduler, with a mix of work sharing and stealing to achieve load balancing~\cite{:erlang}, where under-loaded workers steal from other workers, but overloaded workers also push work to other workers. -This \glslink{atmig}{migration} logic is directed by monitoring logic that evaluates the load a few times per seconds. +This \glslink{atmig}{migration} logic is directed by monitoring logic that evaluates the load a few times per second. \paragraph{Intel\textregistered ~Threading Building Blocks} @@ -196,5 +196,5 @@ \item The successor of t if \textit{t} was its last completed predecessor. \item A task popped from the end of the thread's own deque. - \item A task with affinity for the thread. + \item A task with an affinity for the thread. \item A task popped from approximately the beginning of the shared queue. \item A task popped from the beginning of another randomly chosen thread's deque. @@ -217,5 +217,5 @@ While the documentation only gives limited insight into the scheduling and load balancing approach, \cite{apple:gcd2} suggests a fairly classic approach. Each \proc has a queue of \ats to run, called \newterm{blocks}, which are drained in \glsxtrshort{fifo}. -GCD also has secondary queues, called \newterm{Dispatch Queues} with clear ordering, where executing a block ends-up scheduling more blocks. +GCD also has secondary queues, called \newterm{Dispatch Queues} with clear ordering, where executing a block ends up scheduling more blocks. In terms of semantics, these Dispatch Queues seem to be very similar to Intel\textregistered ~TBB \lstinline{execute()} and predecessor semantics. @@ -223,5 +223,5 @@ \paragraph{LibFibre} -LibFibre~\cite{DBLP:journals/pomacs/KarstenB20} is a light-weight user-level threading framework developed at the University of Waterloo. -Similarly to Go, it uses a variation of work stealing with a global queue that is higher priority than stealing. +LibFibre~\cite{DBLP:journals/pomacs/KarstenB20} is a lightweight user-level threading framework developed at the University of Waterloo. +Similarly to Go, it uses a variation of work stealing with a global queue that has a higher priority than stealing. Unlike Go, it does not have the high-priority next ``chair'' and does not use randomized work-stealing. Index: doc/theses/thierry_delisle_PhD/thesis/text/front.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/front.tex (revision e4855f684383f7bd8f4a3a1ad28663c2f6d307c7) +++ doc/theses/thierry_delisle_PhD/thesis/text/front.tex (revision 918e013764524a1728c269d95056f4b9dff17a6d) @@ -127,12 +127,12 @@ 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 of the question of how many kernel threads are needed and should the number be dynamically reevaluated. +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 kernel-threads be put to sleep to avoid wasting CPU resources. +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 necessary requirements for user-level threading. -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. +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. Index: doc/theses/thierry_delisle_PhD/thesis/text/intro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/intro.tex (revision e4855f684383f7bd8f4a3a1ad28663c2f6d307c7) +++ doc/theses/thierry_delisle_PhD/thesis/text/intro.tex (revision 918e013764524a1728c269d95056f4b9dff17a6d) @@ -9,7 +9,7 @@ When user-threading parallelism does drop, how and when should idle kernel-threads 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. +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 necessary requirements for \gls{uthrding}. +This thesis analyses multiple scheduler systems, where each system attempts to fulfill the requirements for \gls{uthrding}. 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. 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. @@ -23,5 +23,5 @@ Chapter~\ref{existing} discusses how scheduler implementations attempt to achieve these goals, but all implementations optimize some workloads better than others. Chapter~\ref{cfaruntime} presents the relevant aspects of the \CFA runtime system that have a significant effect on the new scheduler design and implementation. -Chapter~\ref{core} analyses different scheduler approaches, while looking for scheduler mechanisms that provide both performance and fairness. +Chapter~\ref{core} analyses different scheduler approaches while looking for scheduler mechanisms that provide both performance and fairness. Chapter~\ref{userio} covers the complex mechanisms that must be used to achieve nonblocking I/O to prevent the blocking of \glspl{kthrd}. Chapter~\ref{practice} presents the mechanisms needed to adjust the amount of parallelism, both manually and automatically. @@ -36,5 +36,5 @@ For scheduled work-units, a scheduler takes a sequence of threads and attempts to run them to completion, subject to shared resource restrictions and utilization. A general-purpose dynamic-scheduler for an open system cannot anticipate work requests, so its performance is rarely optimal. -Even with complete knowledge of arrive order and work, creating an optimal solution is a bin packing problem~\cite{wiki:binpak}. +Even with complete knowledge of arrival order and work, creating an optimal solution is a bin packing problem~\cite{wiki:binpak}. However, optimal solutions are often not required: schedulers often produce excellent solutions, without needing optimality, by taking advantage of regularities in work patterns. @@ -91,5 +91,5 @@ \newterm{contention}: safe access of shared objects by multiple processors requires mutual exclusion in some form, generally locking.\footnote{ Lock-free data-structures do not involve locking but incur similar costs to achieve mutual exclusion.} -Mutual exclusion cost and latency increases significantly with the number of processors access\-ing a shared object. +Mutual exclusion cost and latency increase significantly with the number of processors access\-ing a shared object. \end{enumerate} @@ -116,5 +116,5 @@ Since \CFA attempts to improve the safety and productivity of C, the new scheduler presented in this thesis attempts to achieve the same goals. -More specifically, safety and productivity for scheduling means supporting a wide range of workloads so that programmers can rely on progress guarantees (safety) and more easily achieve acceptable performance (productivity). +More specifically, safety and productivity for scheduling mean supporting a wide range of workloads so that programmers can rely on progress guarantees (safety) and more easily achieve acceptable performance (productivity). 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}. To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside the application.