source: doc/theses/thierry_delisle_PhD/thesis/text/core.tex @ 86c1f1c3

\chapter{Scheduling Core}\label{core}

This chapter addresses the need of scheduling on a somewhat ideal scenario

\section{Existing Schedulers}
\subsection{Feedback Scheduling}

\subsection{Priority Scheduling}\label{priority}

\subsection{Work Stealing}

\section{Design}
While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}.

\subsection{Sharding}

\begin{figure}
        \begin{center}
                \input{base.pstex_t}
        \end{center}
        \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists.
        The timestamp is in all nodes and cell arrays.}
        \label{fig:base}
\end{figure}

\subsection{Finding threads}
Once threads have been distributed onto multiple queues, indentifying which queues are empty and which aren't can become a problem.
Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty.
Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time.
This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.

Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.

\paragraph{Dense Information}





\begin{figure}
        \begin{center}
                \input{empty.pstex_t}
        \end{center}
        \caption{``More empty'' state of the queue: the array contains many empty cells.}
        \label{fig:empty}
\end{figure}