
\chapter{Parallel scheduler for message-driven system}
\label{chap:scheduler}

A scheduler is a component, often implemented as essential part of the operating system,
which distributes processes' computations on the available computation hardware \cite{scheduler}.
In case of this diploma thesis, distribution is restricted by usage of some shared resources -
reading and writing global variables.

Before implementing such scheduler, it is beneficial to formally describe message-driven system
on which this scheduler will operate. Such formal definition will make it straightforward to define
a scheduling algorithm, as well as propose methods for measuring scheduler's performance and potential.

This chapter describes this formal model and whole scheduling algorithm. The provided formal model abstracts
away all unnecessary parts of the message-driven system, so explaining the algorithm is as simple as possible.

\section{Formal model}

For the scheduling algorithm description, describing a message-driven system with the following mathematical
structures is beneficial:
\begin{enumerate}
  \item The finite set of all state variables identified for the system:
  \begin{equation}
    \label{vars_def}
    Vars = \{ v_1, v_2, v_3, \dots \}
  \end{equation}
  These are the variables that can be potentially used (read or written) by the message processing procedure.

  \item The domain \( M \) of all possible messages:
  \begin{equation}
    M = \{ (V_r, V_w) \ |\ V_r, V_w \in \{0, 1\}^{|Vars|}  \}
  \end{equation}
  Therefore, each message is represented by two binary vectors of the length \( |Vars| \). The first vector
  is for the variables read during message processing, second is for the written variables. If \textit{i-th}
  element of these vectors equals \( 1 \), it means that \textit{i-th} variable from the \( Vars \) set will be
  read or, in case of the second vector, written during message processing.

  \item The duration function \( t \):
  \begin{equation}
    \label{duration_func}
    t : M \rightarrow \mathcal N
  \end{equation}
  This function assigns a number of time units that processing of the given message takes. This function is
  used for the simulation to measure scheduler's performance.

  \item The possibly infinite sequence of messages:
  \begin{equation}
    Msgs = m_1, m_2, m_3, \dots \ ;\ m_i \in M
  \end{equation}
  Where the \( M \) is the domain of all possible messages, as described above.
\end{enumerate}

Because, during studying scheduling algorithm behavior and performance, we do not need any information
about internal structure of the system state, neither about the message processing procedure, we omitted
this information from the formal model definition. For our purpose, simulation of the processing, by utilizing
the result of the \hyperref[duration_func]{duration function}, is enough.

\section{Scheduling algorithm}

With the introduced formal model, it is possible to describe several scheduling algorithms:
\begin{enumerate}
  \item \textit{Sequential scheduling algorithm} - all messages are processed sequentially.
  Useful as a reference for performance comparison.

  \item \textit{Parallel scheduling algorithm \textbf{with} read variables locking} - messages
  processing is spread across multiple workers if possible. When the message is scheduled, all
  variables modified by its processing are \textbf{locked for reading and writing}. Useful when
  read-only copies of variables cannot be created or are expensive to create.

  \item \textit{Parallel scheduling algorithm \textbf{without} read variables locking} - messages
  processing is spread across multiple workers if possible. When the message is scheduled all variables
  modified by its processing are \textbf{locked only for writing}. Useful when read-only copies of
  variables are easy and cheap to create.
\end{enumerate}

\subsection{Sequential scheduler}

Sequential scheduling algorithm is straightforward - as soon as message \( m \) arrives, process it.
During simulation, this processing takes \( t(m) \) time units. No variables locking has to be considered
because no parallel execution is performed. This scheduler type is used in this diploma thesis as
a reference for comparing the performance of the parallel schedulers.

\subsection{Parallel schedulers}

The main problem that scheduler has to solve is to determine if a received message can be processed.
Based on the way how is this issue solved, there are two scheduling strategies:
\begin{enumerate}
  \item When the message \( m \) is scheduled for processing, all state variables that will be modified by
  processing message \( m \) will be locked for reading and writing. The message \( m \) can be scheduled only
  if its processing doesn't read any already read-locked variables and if its processing doesn't write any
  already write-locked variables.

  \item When the message \( m \) is scheduled for processing, all state variables that will be modified by
  processing the message \( m \) will be locked for writing. The message \( m \) can be scheduled only if its
  processing doesn't write any already write-locked variables. This requires that there is a read-only private
  copy of each variable for every parallel execution of the message processing.
\end{enumerate}
These two strategies describe two variations of parallel scheduling algorithm - one \textbf{with} and another
\textbf{without} read variables locking.

However, when using the scheduler \textbf{without} read variables locking, there is another issue that
an algorithm has to be aware of - need of the system state cloning. Without read variable locking it is not
guaranteed that write operations, for the same variable, do not happen in the parallel. This issue can be
overcome by maintaining another read-only copy of the whole system state. This copy will be altered only by
the main scheduler procedure. For workers, this copy will be read-only, i.e., no parallel writes will be performed.

The scheduling algorithm, which uses \( N \) parallel workers for message processing, needs to maintain following
data structures to function properly:
\begin{enumerate}
  \item The queue \( Q \) for messages that wait for rescheduling. Initially empty.

  \item The binary vector \( LR_{i} \) of the length \( |Vars| \) for each worker \( i \in [0, N) \) that indicates
  which variables are currently read-locked by the worker \( i \). Initially contains \( |Vars| \) zeros.

  \item The binary vector \( LW_{i} \) of the length \( |Vars| \) for each worker \( i \in [0, N) \) that indicates
  which variables are currently write-locked by the worker \( i \). Initially contains \( |Vars| \) zeros.

  \item The binary vector \( W \) of the length \( N \) that indicates which workers are currently
  available for processing new messages. Initially contains \( N \) ones.
\end{enumerate}

The whole scheduling algorithm can be split into several procedures that are periodically executed to exhibit
the expected behavior of the scheduler.

The first procedure is the \textit{IS\_SCHEDULABLE(m)} which finds out whether the message \( m \) can be
processed by any worker in the current scheduler state. It can be summarized in the following steps:
\begin{enumerate}
  \item Make boolean-or product \( LW \) of all \( LW_{i} \) vectors:
  \begin{equation}
    LW = LW_{1} \ | \ LW_{2} \ | \ ... \ | \ LW_{N}
  \end{equation}

  \item Read vectors \( V_r \) and \( V_w \) of the messsage \( m \).

  \item Make boolean product \( L \):
  \begin{enumerate}
    \item If running scheduler \textbf{with} read variables locking:
    \begin{equation}
      L = LW \ \& \ (V_{r} \ | \ V_{w})
    \end{equation}

    \item If running scheduler \textbf{without} read variables locking:
    \begin{equation}
      L = LW \ \& \ V_{w}
    \end{equation}
  \end{enumerate}

  \item Return \textbf{true} only if vector \( L \) \textbf{does not} contain any bit set to one.
  Or in other words, return \textbf{true} only if vector \( L \) is all-zero vector.
\end{enumerate}

The second procedure is the \textit{SCHEDULE(m)} which does the following:
\begin{enumerate}
  \item Execute \textit{IS\_SCHEDULABLE(m)} to check if the message \( m \) is currently schedulable.
  \begin{enumerate}
    \item If the message \( m \) is schedulable continue with next steps.
    \item Otherwise, add the message \( m \) to the waiting queue \( Q \) and
    terminate execution of this procedure.
  \end{enumerate}

  \item Try to find the \( i \) such that \textit{i-th} bit of the vector \( W \) is one.
  \begin{enumerate}
    \item If such \( i \) exists:
    \begin{enumerate}
      \item Set \textit{i-th} bit of the vector \( W \) to zero.

      \item Send message \( m \) to the worker \( i \) to be processed.
    \end{enumerate}
    \item Otherwise:
    \begin{enumerate}
      \item Add the message \( m \) to the waiting queue \( Q \).
    \end{enumerate}
  \end{enumerate}
\end{enumerate}

The last procedure merges the previous ones and communicates with the workers to provide
the desired functionality:
\begin{enumerate}
  \item Whenever the new message \( m \) arrives into the system:
  \begin{enumerate}
    \item Execute \textit{SCHEDULE(m)} for the arrived message.
  \end{enumerate}

  \item Whenever the worker \( i \) finishes its processing:
  \begin{enumerate}
    \item If running scheduler \textbf{without} read variables locking -
    update the read-only copy of the state to be used by the workers.

    \item Set the \( LR_{i} \) vector to all zeros.

    \item Set the \( LW_{i} \) vector to all zeros.

    \item Set the \textit{i-th} bit of the \( W \) vector to zero.

    \item For each message \( m \) in the waiting queue \( Q \):
    \begin{enumerate}
      \item Remove the message \( m \) from the queue \( Q \).
      \item Execute \textit{SCHEDULE(m)} for the message.
    \end{enumerate}
  \end{enumerate}
\end{enumerate}

\section{Measuring scheduler performance}

To measure performance of the schedulers, it is the best to perform simulation which executes described
scheduling algorithm and simulate time-intensive message processing by busy-waiting for the amount of time
specified by the \hyperref[duration_func]{duration function}.

To perform the measuring simulation, it is essential to define generation process of the messages sequence \( Msgs \).

Every message \( m \) can be viewed as binary vector of length \( 2 \cdot |Vars| \). Therefore, generating a message
can be done by creating a binary vector of length \( 2 \cdot |Vars| \) and setting some its components to \( 0 \) and
some to \( 1 \). The number of components set to \( 1 \) can be determined by specific probability distribution \( P_1 \).
After that, the chosen number of \( 1 \) components, can be randomly distributed in the vector according to probability
distribution \( P_2 \).

The probability distribution function \( P_1(x) \) returns a probability of generating a binary vector with the \( x \)
components set to \( 1 \). Many options for this function are possible, e.g.:
\begin{enumerate}
  \item \textit{Uniform distribution}:
  \begin{equation}
    P_1(x) = \frac{1}{2 \cdot |Vars|}
  \end{equation}

  \item \textit{Exponential distribution}:
  \begin{equation}
    P_1(x) = \lambda e^{-\lambda x}
  \end{equation}
  Where \( \lambda \) is a parameter carefully chosen based on \( |Vars| \). Adjusting this parameter can
  lead to more precise real-world simulation.

  \item \textit{Normal distribution}:
  \begin{equation}
    P_1(x) = \frac{1}{\sqrt{2 \pi \sigma^{2}}}e^{-\frac{(x - \mu)^2}{2 \sigma^2}}
  \end{equation}
  Where \( \sigma \) and \( \mu \) is parameters carefully chosen based on \( |Vars| \). Adjusting
  these parameters can lead to more precise real-world simulation. This distribution was used for
  simulation in this diploma thesis. It is discussed more deeply in the next section.
\end{enumerate}

The probability distribution function \( P_2(x) \) returns a probability of the fact that \( x-th \)
component of the binary vector is set to \( 1 \). Note that the total number of \( 1 \) components
in the binary vector is bounded by the first probability distribution \( P_1 \).

\subsection*{Using the normal distribution}

The normal distribution is often used in the natural and social sciences to represent random variables
whose distributions are unknown. \cite{normalDist} It actually, seems like this distribution (also
sometimes called Gaussian distribution) represents many real-world social phenomena. \cite{normalDist2}

Therefore, it is natural to use this distribution for generating random messages to simulate the scheduler.
In the real-world, messages are created by the actions of the people, so using the Gaussian distribution might
lead to the simulation that mimics the real-world more or less precisely.

For the message generation in the system with \( |Vars| \) variables following version of the distribution
function can be used:
\begin{equation}
  P_1(x) = \frac{1}{\sqrt{2 \pi |Vars|}}e^{-\frac{(x - \frac{|Vars|}{2})^2}{2 |Vars|}}
\end{equation}

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=12cm]{images/normal_graph.png}
  \end{center}
  \caption{Graph of the \( P_1(x) \) function for the \( |Vars| = 20 \)}
\end{figure}

\subsection*{Rate limited message generation}

To believably simulate real-world message-driven systems, it is necessary to choose the right
time for the message generation. This problem was previously solved for the performance benchmarking
of HTTP servers  \cite{httpPerf1} \cite{httpPerf2}. One of the techniques used in those benchmarks is
defining the message rate.  The message rate is the real number that denotes the probability of
generating given message.

Assume that the generation process has access to the rate \( r_i \) for each possible message \( m_i \).
The producing of new messages is performed at ticks once per time unit (e.g., one millisecond).
The message \( m_i \) is produced with the probability of \( r_i \) at each tick.

This generation process, when accompanied by appropriately chosen rates \( r_i \), can precisely
simulate the real-world behavior.
