
\chapter{Implementation}
\label{chap:implementation}

This chapter describes implementations of the algorithms introduced in the previous parts
of the thesis.

In the first section tools used for scheduler implementation are introduced, as well as
some basic overview of the implementation is provided.

The second section contains the description of the interpreter and static analyzer
implementation. Used tools and libraries are listed, an overview of the implementation is
provided, and some further implementation optimizations are discussed.

\section{Scheduler}

The whole scheduler is implemented in the \textit{C++ programming language} \cite{cppSpec} using the
standard library that is part of the \textit{C++14 specification} \cite{cppSpec}. Thanks to this,
the implementation is portable and can be used on every platform supported by the
\textit{C++14 standard} - including Unix and Windows.

Because scheduling algorithm is inherently parallel, some parallelization construct has
to be used. For this purpose, system threads feature \cite{syncConstructs}, e.g., Unix
POSIX threads, is used. One thread is used for the main scheduler procedure, and one
additional thread is used for each scheduler's worker.

As many parallel threads are used during algorithm's execution, some synchronization of
threads has to be involved. Consumer-producer queues showed up to be an appropriate data
structure for such synchronization. These queues are implemented to be thread-safe by using
standard \textit{semaphores} and \textit{conditional variables} \cite{syncConstructs}.

Various control messages are being sent to the queues. These messages are then received and
processed by the queue's owner thread. Every sent message has an assigned priority, which alters
the order of the message processing - messages with the higher priority are processed earlier.

Following \textit{control messages} are exchanged by the worker threads, the main scheduler
thread and the \textit{outside world}, which is generating the \textit{messages} that should be
scheduled and processed by the scheduler:
\begin{enumerate}
  \item Main scheduler thread receives the \textit{control message} from the outside world that carries
  the \textit{message} that should be scheduled and processed.

  \item Main scheduler thread receives the \textit{control message} from itself that carries the \textit{message},
  previously received from the outside world, that should be rescheduled. This \textit{control message}
  has lower priority than schedule \textit{control message} above.

  \item Main scheduler thread receives a \textit{control message} from the worker that informs the scheduler
  about finished processing and entering the idle state. This \textit{control message} has the highest priority.

  \item Main scheduler thread sends a \textit{control message} to the worker that carries the \textit{message}
  that worker should immediately start processing.
\end{enumerate}

In addition to exchanging these messages, the main scheduler thread keeps track of idle workers and
locked variables by different workers, i.e., information needed to determine which \textit{outside world messages}
are schedulable at any given time. Also, there are some extra \textit{control messages} related to
the terminating of the main scheduler thread, as well as worker threads. These are not essential for
scheduler functionality, so there are not described here.

\section{Interpreter}

An interpreter is a program which takes a source code of the particular programming
language as an input and performs semantic actions based on the source code, that should
be performed according to the programming language specification.

Every interpreter generally consists of several parts:
\begin{enumerate}
  \item \textit{Lexer} which transforms the source code into a stream of tokens.
  \item \textit{Parser} which converts the stream of the tokens into an abstract syntax tree (AST).
  \item \textit{Executor} which traverses the AST and performs corresponding semantic actions.
\end{enumerate}

The interpreter implemented as part of this diploma thesis is using the \textit{ANTLR} \cite{antlr}
library to create the \textit{lexer} and the \textit{parser}. This library takes lexer and parser
definition files and generates set of C++ classes that handle tokenization and parsing of the
input source code into the AST. This AST is then executed by the \textit{executor} which is also
implemented in the C++ programming language. The parser generated by the \textit{ANTLR} tool
performs the parsing using the \textit{LL(*)} algorithm \cite{llParsing}. This algorithm is
based on \textit{formal language} and \textit{finite-state automata} abstraction and formalism
\cite{formalLanguages}.

The interpreter is also designed to run in an analysis mode. In this mode, special program static
analysis is performed, as described in the \hyperref[chap:compiler]{Interpreter chapter}.
This analysis is also performed on the AST, and its result is set of boolean expressions that
are used to determine read and written variables during the particular message processing.

For the experiments presented in the \hyperref[chap:results]{Results chapter}, it was important
to merge the interpreter implementation with the scheduler implementation. Both were implemented
in the C++ programming language, and the scheduler implementation was designed to be as modular
as possible. Thanks to this, merging both components was smooth and efficient.

The implementation was done to allow comparing performance impact of the different workers count.
Therefore, it was not necessary to optimize every single part of the interpreter. Several aspects
were not optimized and should be if the interpreter will be used in the real service:
\begin{enumerate}
  \item \textit{Object copying} is performed on each assign. This is a required semantic restriction
  of the programming language which makes the code analysis possible. However, this is very inefficient
  because many assignments create an object that is just read-only. To mitigate this inefficiency,
  the copy-on-write algorithm \cite{copyOnWrite} might be implemented for object assignments.

  \item \textit{Boolean expressions evaluation} is performed to determine variables that are read or
  written by each messages processing. The boolean expressions are created by the analyzer and are
  always side-effect free. However, there might not be optimal and often can be simplified. The aim of
  this simplification is a decrease of the evaluation time. To achieve this improvement boolean
  minimization procedures \cite{booleanMinimization} might be applied.

  \item \textit{Boolean expressions caching and reusing} can lead to improved performance. Generated
  boolean expressions often share some parts whose evaluation might be cached and reused instead of
  evaluating it again when it is needed. Whole expressions result might be cached for the messages
  that will be rescheduled in the future.
\end{enumerate}
