- Timestamp:
- Sep 13, 2022, 3:07:25 PM (22 months ago)
- Branches:
- ADT, ast-experimental, master, pthread-emulation
- Children:
- 3606fe4
- Parents:
- 1c334d1
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/thesis/text/existing.tex
r1c334d1 rfc96890 5 5 6 6 In general, \emph{selecting} a scheduling algorithm depends on how much information is available to the scheduler. 7 Workloads that are well -known, consistent, and homogeneous can benefit from a scheduler that is optimized to use this information, while ill-defined, inconsistent, heterogeneous workloads require general non-optimal algorithms.7 Workloads that are well known, consistent, and homogeneous can benefit from a scheduler that is optimized to use this information, while ill-defined, inconsistent, heterogeneous workloads require general non-optimal algorithms. 8 8 A secondary aspect is how much information can be gathered versus how much information must be given as part of the scheduler input. 9 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.9 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. 10 10 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. 11 11 … … 77 77 In general, fine granularity is better for load balancing and coarse granularity reduces communication overhead. 78 78 The best performance generally means finding a middle ground between the two. 79 Several methods can be employed, but I believe these are less relevant for threads, which are generally explicit and more coarse 79 Several methods can be employed, but I believe these are less relevant for threads, which are generally explicit and more coarse-grained. 80 80 81 81 \paragraph{Task Placement} Another aspect of work stealing that has been studied extensively is the mapping between \at and \proc. … … 97 97 \cite{DBLP:conf/ipps/ColeR13} also studied how randomized work-stealing affects false sharing among \ats. 98 98 99 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.100 It is unclear how well these distributions represent workloads in real 99 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. 100 It is unclear how well these distributions represent workloads in real-world scenarios. 101 101 102 102 \section{Preemption} … … 115 115 116 116 \subsection{Operating System Schedulers} 117 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.117 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. 118 118 Here are more details on a few schedulers used in the common operating systems: Linux, FreeBSD, Microsoft Windows and Apple's OS X. 119 119 The information is less complete for closed source operating systems. … … 130 130 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. 131 131 132 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}132 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} 133 133 134 134 \paragraph{FreeBSD} … … 144 144 145 145 In~\cite{russinovich2009windows}, Chapter 1 section 2.3 ``Processes, Threads, and Jobs'' discusses the scheduling policy more in-depth. 146 Multicore scheduling is based on a combination of priorities and \proc prefer ance.146 Multicore scheduling is based on a combination of priorities and \proc preference. 147 147 Each \at is assigned an initial processor using a round-robin policy, called the \at's \newterm{ideal} \proc. 148 148 \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. … … 195 195 \item The task returned by \textit{t}@.execute()@ 196 196 \item The successor of t if \textit{t} was its last completed predecessor. 197 \item A task popped from the end of the thread's own deque.197 \item A task popped from the end of the thread's own queue. 198 198 \item A task with an affinity for the thread. 199 199 \item A task popped from approximately the beginning of the shared queue. 200 \item A task popped from the beginning of another randomly chosen thread's deque.200 \item A task popped from the beginning of another randomly chosen thread's queue. 201 201 \end{enumerate} 202 202
Note: See TracChangeset
for help on using the changeset viewer.