Ignore:
Timestamp:
Jun 29, 2022, 4:15:33 PM (3 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
master, pthread-emulation, qualifiedEnum
Children:
06bdba4, 1ed3fe7c
Parents:
d7af839
Message:

Updated intro

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/text/existing.tex

    rd7af839 radf03a6  
    1414
    1515\section{Naming Convention}
    16 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. 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 \glspl{at}.
     16Scheduling 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. 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.
    1717
    1818\section{Static Scheduling}
    19 \newterm{Static schedulers} require \gls{at} dependencies and costs be explicitly and exhaustively specified prior to scheduling.
     19\newterm{Static schedulers} require \ats dependencies and costs be explicitly and exhaustively specified prior to scheduling.
    2020The scheduler then processes this input ahead of time and produces a \newterm{schedule} the system follows during execution.
    2121This approach is popular in real-time systems since the need for strong guarantees justifies the cost of determining and supplying this information.
     
    2525
    2626\section{Dynamic Scheduling}
    27 \newterm{Dynamic schedulers} determine \gls{at} dependencies and costs during scheduling, if at all.
    28 Hence, unlike static scheduling, \gls{at} dependencies are conditional and detected at runtime. This detection takes the form of observing new \gls{at}(s) in the system and determining dependencies from their behaviour, including suspending or halting a \gls{at} that dynamically detects unfulfilled dependencies.
    29 Furthermore, each \gls{at} has the responsibility of adding dependent \glspl{at} back into the system once dependencies are fulfilled.
    30 As a consequence, the scheduler often has an incomplete view of the system, seeing only \glspl{at} with no pending dependencies.
     27\newterm{Dynamic schedulers} determine \ats dependencies and costs during scheduling, if at all.
     28Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime. This detection takes the form of observing new \ats(s) in the system and determining dependencies from their behaviour, including suspending or halting a \ats that dynamically detects unfulfilled dependencies.
     29Furthermore, each \ats has the responsibility of adding dependent \ats back into the system once dependencies are fulfilled.
     30As a consequence, the scheduler often has an incomplete view of the system, seeing only \ats with no pending dependencies.
    3131
    3232\subsection{Explicitly Informed Dynamic Schedulers}
    33 While dynamic schedulers may not have an exhaustive list of dependencies for a \gls{at}, some information may be available about each \gls{at}, \eg expected duration, required resources, relative importance, \etc.
    34 When available, a scheduler can then use this information to direct the scheduling decisions. \cit{Examples of schedulers with more information} 
     33While dynamic schedulers may not have an exhaustive list of dependencies for a \ats, some information may be available about each \ats, \eg expected duration, required resources, relative importance, \etc.
     34When available, a scheduler can then use this information to direct the scheduling decisions. \cit{Examples of schedulers with more information}
    3535However, most programmers do not determine or even \emph{predict} this information;
    36 at best, the scheduler has only some imprecise information provided by the programmer, \eg, indicating a \glspl{at} takes approximately 3--7 seconds to complete, rather than exactly 5 seconds.
    37 Providing this kind of information is a significant programmer burden especially if the information does not scale with the number of \glspl{at} and their complexity.
    38 For example, providing an exhaustive list of files read by 5 \glspl{at} is an easier requirement then providing an exhaustive list of memory addresses accessed by 10,000 independent \glspl{at}.
     36at best, the scheduler has only some imprecise information provided by the programmer, \eg, indicating a \ats takes approximately 3--7 seconds to complete, rather than exactly 5 seconds.
     37Providing this kind of information is a significant programmer burden especially if the information does not scale with the number of \ats and their complexity.
     38For 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.
    3939
    4040Since 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.
    4141
    4242\subsubsection{Priority Scheduling}
    43 Common information used by schedulers to direct their algorithm is priorities. 
    44 Each \gls{at} is given a priority and higher-priority \glspl{at} are preferred to lower-priority ones.
    45 The simplest priority scheduling algorithm is to require that every \gls{at} have a distinct pre-established priority and always run the available \gls{at} with the highest priority.
    46 Asking programmers to provide an exhaustive set of unique priorities can be prohibitive when the system has a large number of \glspl{at}.
    47 It can therefore be desirable for schedulers to support \glspl{at} with identical priorities and/or automatically setting and adjusting priorities for \glspl{at}.
    48 Most common operating systems use some variant on priorities with overlaps and dynamic priority adjustments. 
     43Common information used by schedulers to direct their algorithm is priorities.
     44Each \ats is given a priority and higher-priority \ats are preferred to lower-priority ones.
     45The simplest priority scheduling algorithm is to require that every \ats have a distinct pre-established priority and always run the available \ats with the highest priority.
     46Asking programmers to provide an exhaustive set of unique priorities can be prohibitive when the system has a large number of \ats.
     47It can therefore be desirable for schedulers to support \ats with identical priorities and/or automatically setting and adjusting priorities for \ats.
     48Most common operating systems use some variant on priorities with overlaps and dynamic priority adjustments.
    4949For example, Microsoft Windows uses a pair of priorities
    5050\cit{https://docs.microsoft.com/en-us/windows/win32/procthread/scheduling-priorities,https://docs.microsoft.com/en-us/windows/win32/taskschd/taskschedulerschema-priority-settingstype-element}, one specified by users out of ten possible options and one adjusted by the system.
    5151
    5252\subsection{Uninformed and Self-Informed Dynamic Schedulers}
    53 Several scheduling algorithms do not require programmers to provide additional information on each \gls{at}, and instead make scheduling decisions based solely on internal state and/or information implicitly gathered by the scheduler.
     53Several scheduling algorithms do not require programmers to provide additional information on each \ats, and instead make scheduling decisions based solely on internal state and/or information implicitly gathered by the scheduler.
    5454
    5555
    5656\subsubsection{Feedback Scheduling}
    57 As mentioned, schedulers may also gather information about each \glspl{at} to direct their decisions.
    58 This design effectively moves the scheduler into the realm of \newterm{Control Theory}~\cite{wiki:controltheory}. 
    59 This information gathering does not generally involve programmers, and as such, does not increase programmer burden the same way explicitly provided information may. 
    60 However, some feedback schedulers do allow programmers to offer additional information on certain \glspl{at}, in order to direct scheduling decisions.
     57As mentioned, schedulers may also gather information about each \ats to direct their decisions.
     58This design effectively moves the scheduler into the realm of \newterm{Control Theory}~\cite{wiki:controltheory}.
     59This information gathering does not generally involve programmers, and as such, does not increase programmer burden the same way explicitly provided information may.
     60However, some feedback schedulers do allow programmers to offer additional information on certain \ats, in order to direct scheduling decisions.
    6161The important distinction being whether or not the scheduler can function without this additional information.
    6262
    6363
    6464\section{Work Stealing}\label{existing:workstealing}
    65 One of the most popular scheduling algorithm in practice (see~\ref{existing:prod}) is work stealing. 
    66 This idea, introduce by \cite{DBLP:conf/fpca/BurtonS81}, effectively has each worker process its local \glspl{at} first, but allows the possibility for other workers to steal local \glspl{at} if they run out of \glspl{at}.
    67 \cite{DBLP:conf/focs/Blumofe94} introduced the more familiar incarnation of this, where each workers has a queue of \glspl{at} and workers without \glspl{at} steal \glspl{at} from random workers\footnote{The Burton and Sleep algorithm had trees of \glspl{at} and steal only among neighbours.}.
     65One of the most popular scheduling algorithm in practice (see~\ref{existing:prod}) is work stealing.
     66This idea, introduce 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.
     67\cite{DBLP:conf/focs/Blumofe94} introduced the more familiar incarnation of this, where each workers has a queue of \ats and workers without \ats steal \ats from random workers\footnote{The Burton and Sleep algorithm had trees of \ats and steal only among neighbours.}.
    6868Blumofe and Leiserson also prove worst case space and time requirements for well-structured computations.
    6969
    7070Many 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.
    7171
    72 \paragraph{Granularity} A significant portion of early work-stealing research concentrated on \newterm{Implicit Parallelism}~\cite{wiki:implicitpar}. 
     72\paragraph{Granularity} A significant portion of early work-stealing research concentrated on \newterm{Implicit Parallelism}~\cite{wiki:implicitpar}.
    7373Since the system is responsible for splitting the work, granularity is a challenge that cannot be left to programmers, as opposed to \newterm{Explicit Parallelism}\cite{wiki:explicitpar} where the burden can be left to programmers.
    74 In general, fine granularity is better for load balancing and coarse granularity reduces communication overhead. 
    75 The best performance generally means finding a middle ground between the two. 
     74In general, fine granularity is better for load balancing and coarse granularity reduces communication overhead.
     75The best performance generally means finding a middle ground between the two.
    7676Several methods can be employed, but I believe these are less relevant for threads, which are generally explicit and more coarse grained.
    7777
    78 \paragraph{Task Placement} Since modern computers rely heavily on cache hierarchies\cit{Do I need a citation for this}, migrating \glspl{at} from one core to another can be .  \cite{DBLP:journals/tpds/SquillanteL93}
     78\paragraph{Task Placement} Since modern computers rely heavily on cache hierarchies\cit{Do I need a citation for this}, migrating \ats from one core to another can be .  \cite{DBLP:journals/tpds/SquillanteL93}
    7979
    8080\todo{The survey is not great on this subject}
     
    8383
    8484\subsection{Theoretical Results}
    85 There is also a large body of research on the theoretical aspects of work stealing. These evaluate, for example, the cost of 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}. 
    86 \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}. 
    87 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}. 
    88 \cite{DBLP:conf/ipps/ColeR13} also studied how randomized work-stealing affects false sharing among \glspl{at}.
    89 
    90 However, as \cite{DBLP:journals/ijpp/YangH18} highlights, it is worth mentioning that this theoretical research has mainly focused on ``fully-strict'' computations, \ie workloads that can be fully represented with a direct acyclic graph. 
     85There is also a large body of research on the theoretical aspects of work stealing. These evaluate, for example, the cost of 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}.
     86\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}.
     87Others 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}.
     88\cite{DBLP:conf/ipps/ColeR13} also studied how randomized work-stealing affects false sharing among \ats.
     89
     90However, as \cite{DBLP:journals/ijpp/YangH18} highlights, it is worth mentioning that this theoretical research has mainly focused on ``fully-strict'' computations, \ie workloads that can be fully represented with a direct acyclic graph.
    9191It is unclear how well these distributions represent workloads in real world scenarios.
    9292
    9393\section{Preemption}
    94 One last aspect of scheduling is preemption since many schedulers rely on it for some of their guarantees. 
    95 Preemption is the idea of interrupting \glspl{at} that have been running too long, effectively injecting suspend points into the application.
    96 There are multiple techniques to achieve this effect but they all aim to guarantee that the suspend points in a \gls{at} are never further apart than some fixed duration.
    97 While this helps schedulers guarantee that no \glspl{at} unfairly monopolizes a worker, preemption can effectively be added to any scheduler.
     94One last aspect of scheduling is preemption since many schedulers rely on it for some of their guarantees.
     95Preemption is the idea of interrupting \ats that have been running too long, effectively injecting suspend points into the application.
     96There 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.
     97While this helps schedulers guarantee that no \ats unfairly monopolizes a worker, preemption can effectively be added to any scheduler.
    9898Therefore, the only interesting aspect of preemption for the design of scheduling is whether or not to require it.
    9999
     
    106106
    107107\subsection{Operating System Schedulers}
    108 Operating System Schedulers tend to be fairly complex as they generally support some amount of real-time, aim to balance interactive and non-interactive \glspl{at} and support multiple users sharing hardware without requiring these users to cooperate.
    109 Here are more details on a few schedulers used in the common operating systems: Linux, FreeBSD, Microsoft Windows and Apple's OS X. 
     108Operating 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.
     109Here are more details on a few schedulers used in the common operating systems: Linux, FreeBSD, Microsoft Windows and Apple's OS X.
    110110The information is less complete for operating systems with closed source.
    111111
    112112\paragraph{Linux's CFS}
    113 The default scheduler used by Linux, the Completely Fair Scheduler~\cite{MAN:linux/cfs,MAN:linux/cfs2}, is a feedback scheduler based on CPU time. 
    114 For each processor, it constructs a Red-Black tree of \glspl{at} waiting to run, ordering them by the amount of CPU time used.
    115 The \gls{at} that has used the least CPU time is scheduled.
     113The default scheduler used by Linux, the Completely Fair Scheduler~\cite{MAN:linux/cfs,MAN:linux/cfs2}, is a feedback scheduler based on CPU time.
     114For each processor, it constructs a Red-Black tree of \ats waiting to run, ordering them by the amount of CPU time used.
     115The \ats that has used the least CPU time is scheduled.
    116116It also supports the concept of \newterm{Nice values}, which are effectively multiplicative factors on the CPU time used.
    117 The ordering of \glspl{at} is also affected by a group based notion of fairness, where \glspl{at} belonging to groups having used less CPU time are preferred to \glspl{at} belonging to groups having used more CPU time.
     117The 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.
    118118Linux achieves load-balancing by regularly monitoring the system state~\cite{MAN:linux/cfs/balancing} and using some heuristic on the load, currently CPU time used in the last millisecond plus a decayed version of the previous time slots~\cite{MAN:linux/cfs/pelt}.
    119119
    120120\cite{DBLP:conf/eurosys/LoziLFGQF16} shows that Linux's CFS also does work stealing to balance the workload of each processors, but the paper argues this aspect can be improved significantly.
    121 The issues highlighted stem from Linux's need to support fairness across \glspl{at} \emph{and} across users\footnote{Enforcing fairness across users means that given two users, one with a single \gls{at} and the other with one thousand \glspl{at}, the user with a single \gls{at} does not receive one thousandth of the CPU time.}, increasing the complexity.
    122 
    123 Linux also offers a FIFO scheduler, a real-time scheduler, which runs the highest-priority \gls{at}, and a round-robin scheduler, which is an extension of the FIFO-scheduler that adds fixed time slices. \cite{MAN:linux/sched}
     121The 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 \ats and the other with one thousand \ats, the user with a single \ats does not receive one thousandth of the CPU time.}, increasing the complexity.
     122
     123Linux 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}
    124124
    125125\paragraph{FreeBSD}
     
    131131Microsoft's Operating System's Scheduler~\cite{MAN:windows/scheduler} is a feedback scheduler with priorities.
    132132It supports 32 levels of priorities, some of which are reserved for real-time and privileged applications.
    133 It schedules \glspl{at} based on the highest priorities (lowest number) and how much CPU time each \gls{at} has used.
     133It schedules \ats based on the highest priorities (lowest number) and how much CPU time each \ats has used.
    134134The scheduler may also temporarily adjust priorities after certain effects like the completion of I/O requests.
    135135
     
    149149
    150150\subsection{User-Level Schedulers}
    151 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 \glspl{at} have the same user, and therefore cooperation is both feasible and probable.
     151By 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.
    152152
    153153\paragraph{Go}\label{GoSafePoint}
     
    167167
    168168\paragraph{Erlang}
    169 Erlang is a functional language that supports concurrency in the form of processes: threads that share no data. 
     169Erlang is a functional language that supports concurrency in the form of processes: threads that share no data.
    170170It 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.
    171171This migration logic is directed by monitoring logic that evaluates the load a few times per seconds.
     
    173173\paragraph{Intel\textregistered ~Threading Building Blocks}
    174174\newterm{Thread Building Blocks} (TBB) is Intel's task parallelism \cite{wiki:taskparallel} framework.
    175 It runs \newterm{jobs}, which are uninterruptable \glspl{at} that must always run to completion, on a pool of worker threads.
     175It runs \newterm{jobs}, which are uninterruptable \ats that must always run to completion, on a pool of worker threads.
    176176TBB's scheduler is a variation of randomized work-stealing that also supports higher-priority graph-like dependencies~\cite{MAN:tbb/scheduler}.
    177 It schedules \glspl{at} as follows (where \textit{t} is the last \gls{at} completed):
     177It schedules \ats as follows (where \textit{t} is the last \ats completed):
    178178\begin{displayquote}
    179179        \begin{enumerate}
     
    196196
    197197\paragraph{Grand Central Dispatch}
    198 An Apple\cit{Official GCD source} API that offers task parallelism~\cite{wiki:taskparallel}. 
     198An Apple\cit{Official GCD source} API that offers task parallelism~\cite{wiki:taskparallel}.
    199199Its distinctive aspect is multiple ``Dispatch Queues'', some of which are created by programmers.
    200 Each queue has its own local ordering guarantees, \eg \glspl{at} on queue $A$ are executed in \emph{FIFO} order.
     200Each queue has its own local ordering guarantees, \eg \ats on queue $A$ are executed in \emph{FIFO} order.
    201201
    202202\todo{load balancing and scheduling}
     
    207207
    208208\paragraph{LibFibre}
    209 LibFibre~\cite{DBLP:journals/pomacs/KarstenB20} is a light-weight user-level threading framework developed at the University of Waterloo. 
    210 Similarly to Go, it uses a variation of work stealing with a global queue that is higher priority than stealing. 
     209LibFibre~\cite{DBLP:journals/pomacs/KarstenB20} is a light-weight user-level threading framework developed at the University of Waterloo.
     210Similarly to Go, it uses a variation of work stealing with a global queue that is higher priority than stealing.
    211211Unlike Go, it does not have the high-priority next ``chair'' and does not use randomized work-stealing.
Note: See TracChangeset for help on using the changeset viewer.