%% This file: http://user.it.uu.se/~embe8573/hs-linux/docs/report/report.tex

\documentclass[a4paper, twoside, 12pt]{report}

\usepackage{enumerate}

%% \noindent\begin{minipage}{\textwidth}
%% \end{minipage}

\usepackage{longtable}

%% insert text file
% verbatim
\usepackage{verbatim}
\newlength\myverbindent
\setlength\myverbindent{1cm}
\makeatletter
\def\verbatim@processline{%
  \hspace{\myverbindent}\the\verbatim@line\par}
\makeatother
% alltt
\usepackage{alltt}

%% insert pdf
\usepackage{pdfpages}

%% url
\usepackage{hyperref}

%%% DEFINITIONS
%% index
\usepackage[font=footnotesize]{idxlayout}
\usepackage{makeidx}
\makeindex
%% boxes, captions, etc.
\usepackage[labelformat=empty,font=bf]{caption}
\usepackage{color}
\definecolor{light-gray}{gray}{0.95}
\setlength{\fboxsep}{0.67\baselineskip}
\newcommand\boxdef[2]{%
  \vspace{\baselineskip}%
  \begin{center}%
    \colorbox{light-gray}{\parbox{0.80\linewidth}{%
        \index{#1 \emph{def.}}\captionof{figure}{#1}#2}}%
  \end{center}%
  \vspace{\baselineskip}%
}

%% page and section refs
\newcommand\spref[1]{[section \ref{#1}, page \pageref{#1}]}

%% misc
\usepackage[T1]{fontenc}

%% equations
\newcounter{eqnumber}
\setcounter{eqnumber}{0}
\newcommand{\beq}[2]{
  \addtocounter{eqnumber}{1}
  \vspace{0.33cm}
  \begin{tabular}{p{0.7\linewidth}p{0.3\linewidth}}
    \index{#2@\texttt{#2} \emph{eq.} (\arabic{eqnumber})}
    \begin{center}$#1$\end{center}&
    \begin{center}\tiny\texttt{eq. (\arabic{eqnumber}), \textbf{#2}}\end{center}
  \end{tabular}
  \vspace{0.33cm}
}

\def\relate{0 < r < p < l}

\def\topscheduler{g = (l, p, r, S, a)}

\def\taskscheduler{S = \{s_{i}\} = \{(m_{i}, b_{i}, P_{i}, \alpha_{i})\}}
\def\sporadic{P_{i} = \{t_{j}\} = \{(C_{j}, D_{j}, T_{j})\}}
\def\sporadictask{t_{j} = (C_{j}, D_{j}, T_{j})}

\def\responsetime{r_{j} = Q_{j} + o_{j} + i_{j} + C_{j}}

\def\zperiods{z = \frac{r_{j}}{p}}

\def\schedulingoverhead{o_{j} = \left\lfloor\frac{r_{j}}{r}\right\rfloor o}
\def\interference{i_{j} = \lceil z\rceil m_{i}58.5\ ns}

\def\queuing{Q_{j} = Q^{g}_{j} + Q^{s}_{j}}

\def\groupqueuing{Q^{g}_{j} = \sum\limits_{\{t_{j}, t_{k}\}\subseteq P_{i}, t_{k} \in hp(t_{j})}\left\lceil\frac{r_{j}}{T_{k}}\right\rceil C_{k}}

\def\systemqueuing{Q^{s}_{j} = (\lceil z\rceil + 1)(p - b_{i})} % (\sum\limits_{s_{k} \in S, k\neq j}b_{k})

\def\interval{I = \Delta\theta = \theta_{2} - \theta_{1}}

\def\supplycompleteperiods{w = \left\lfloor\frac{I}{p}\right\rfloor - 1}
\def\supplytimecompleteperiods{B_{i} = wb_{i}}
\def\supplylengthincompleteperiods{R = I  -  wp}
\def\supplylengthincompleteoutside{U = p - \frac{R}{2}}
\def\supplyincompleteperiods{\beta_{i} = 2 max(0, b_{i} - U)}
\def\supplyreduction{\rho = (w + 2)m_{i}58.5\ ns}
\def\supply{sbf(s_{i}, I) = B_{i} + \beta_{i} - \rho}

\def\demandincompleteperiod{h = min(I - fT_{j},C_{j})}
\def\demandtask{dbf(t_{j}, I) = fC_{j} + h}
\def\demandgroup{dbf(P_{i}, I) = \sum\limits_{t_{j} \in P_{i}}dbf(t_{j}, I)}
\def\demandcompleteperiods{f = \left\lfloor\frac{I}{T_{j}}\right\rfloor}

%% to-be-boxed definitions
\def\hierarchicalscheduler{A hierarchical scheduler is
  a scheduler that consists of several schedulers that
  are organized hierarchically, in a tree structure.
  The leaf schedulers are not themselves hierarchical,
  but ordinary: they schedule processes (or tasks).
  All schedulers above them, however, are hierarchical
  schedulers: they do not schedule processes, but the
  schedulers at the level immediately below.}

\def\WCET{WCET (Worst Case Execution Time) is the
  wall-clock time, or response time, of a program:
  the amount of time that passes from invocation to
  completion, in the \emph{worst} possible case (i.e.,
  it is impossible that it could ever take any longer
  to successfully terminate the task). The WCET
  parameter is helpful in models, to do computation,
  and it can also steer software behavior.
  Nonetheless, it is most often not possible to derive
  the WCET, in spite of much Computer Science research
  devoted to methods to that end. \cite[p. 110]{rtss} \\

  There are several reasons WCET may be incomputable:
  task-execution conditions may vary -- externally
  (the physical context), but also internally (e.g.,
  system load); also, tasks may depend on other tasks
  to complete before them, or to release resources
  they have monopolized; and, the system may be a
  multicore, or even distributed with asynchronous
  message passing in between. \cite[p. 3]{rtssva} \\

  In this project, both in software and in analysis,
  it is assumed the WCET is correct, wherever it
  appears. Actually, WCETs are simply assigned by the
  user with no questions asked if it is realistic or
  not. Wherever available, indata verification is done
  in only terms of \emph{other} parameter indata: the
  associated software is not examined.}

\def\edf{EDF (Earliest Deadline First) is a real-time
  scheduling algorithm. It requires each task be
  annotated a deadline (typically an integer). This is
  a static, a-priori property; it should be
  interpreted as the time interval between the release
  of the task and when it must be completed, less it
  will be considered delayed (i.e., a failure for hard
  real-time systems). When scheduling, the
  EDF-scheduler will select for execution the task
  with the most immediate absolute deadline -- that
  is, the earliest deadline, first. Because the
  absolute deadline is a function not only of the
  deadline task parameter, but also of the run-time
  instant the task was released, EDF is a dynamic
  scheduling algorithm.}

\def\resources{The \emph{resources} of a computer can
  be either in hardware or software. Hardware
  resources are the memory, the CPU, the disk, etc.
  Such resources can be either static -- e.g., the
  disk size -- or dynamic -- e.g., the available
  memory at the time of a certain workload. Resources
  can also be in software. If a program has been
  assigned a certain number of memory accesses, this
  budget is a resource: if 0, it is a depleted
  resource until it gets resupplied.}

\def\responsetimedef{The \emph{response time} is the
  wall-clock time elapsed from when the user invoked a
  command up and until the completion of the program
  that is associated with that command. The user does
  not have to be a human: it can be another program,
  e.g., a real-time scheduler.}

\def\schedulability{For any task set (where the tasks
  adhere to a specific task model), and a particular
  scheduling algorithm, there is a test than can
  determine \emph{schedulability}. That test answers
  the question: ``Can the algorithm make a schedule,
  that involves all the tasks in the set, so that, if
  they are executed accordingly, all tasks will
  complete before their deadlines?'' If so, the task
  set has passed the schedulability test for that
  algorithm: the task set is \emph{schedulable}.}

\def\scheduler{Computers are capable of executing
  several programs concurrently -- or seemingly so.
  Actually, the CPU switches from program to program,
  executing each just so much as to create the
  illusion that everything happens in parallel.
  \cite[p. 117]{linux} This makes for responsiveness
  to the user, but also better use of hardware
  resources: for example, while one program waits for
  I/O, it yields the CPU to another,
  computation-intense program (as the
  program-put-on-hold cannot make use of the CPU
  anyway, lacking I/O data). A special program decides
  what program executes, and when: the
  \emph{scheduler}. This program is part of the kernel
  as it is needs memory and otherwise hardware access.
  There are several scheduling algorithms that the
  scheduler can employ to make its choise what program
  to run. Programs are associated a run-time data
  structure -- the process control block, or PCB --
  that will provide the scheduler with uniform
  metadata on the state of the program in execution.
  Contrary, on multicores, true concurrency do exist
  as programs are executed in parallel, on different
  CPUs (or cores).}

\def\rtos{The \emph{real-time operating system} (RTOS)
  is the software that makes sure that the real-time
  tasks are executed in such a way that they are all
  guaranteed to complete before their deadlines
  expire. In principle, there should be several ways
  to implement such a system. In practice, the most
  common solution is to have a real-time scheduler
  instead of the ordinary scheduler, and then to
  annotate each task with real-time metadata, such as
  worst-case execution time and deadline. The
  real-time scheduler will process the metadata, as
  well as the overall system state (including the
  time), so that tasks are enqueued and selected for
  execution in a manner that will ensure compliance
  with the real-time constraints.}

\def\realtimesystem{``An operating
  system capable of responding to an external event in
  a predictable and appropriate way every time the
  external event occurs.'' \cite[p. 374]{dyson}}

\def\deadline{In real-time computing, a task
  (typically a small program instance) must not only
  be implemented to produce a correct result (like any
  other piece of software), it must also complete its
  computation before a certain time limit. Such a
  limit can be expressed in different ways. The
  sporadic task model used for this implementation
  expresses time constraints in terms of a
  \emph{deadline} for each task. The deadline is
  relative to the task arrival time: it is thus a
  static parameter, attached to the task much like the
  source code that is to be executed. If the arrival
  of task $t_i$ is at time $c$, and $t_{i}$ has
  deadline $D_{i}$, that means in absolute time, $t_i$
  must be completed no later than $c + D_{i}$,
  otherwise $t_{i}$ is considered a faulty piece of
  software, no less so than was there a bug in its
  code, making it crash or produce an incorrect
  result. (In some settings, a correct result -- which
  is delivered late -- can have even worse
  consequences than an incorrect result, that was
  delivered in time. \cite[p. 9]{stigge})}

\def\predictable{Computer systems are deterministic by
  definition. If they are \emph{predictable}, that
  determinism is lifted to a human level: the user is
  able to make a statement -- that something
  particular will happen, and not later than at a
  certain time. The statement is then proved to hold
  by use of formal methods. If the statement holds in
  theory as well as practice, the system is
  predictable, at least with respect to that
  particular statement. A predictable system consists
  of a set of likewise predictable statements/behavior
  patterns.}

%% TOC
%%
%% does not work:
%% \usepackage[toc]{multitoc}
%% \renewcommand*{zlticolumntoc}{2}
%% \setlength{\columnseprule}{0.5pt}

%% \addtocontents{toc}{\protect\enlargethispage{6cm}}

%% does not work:
%% \def\contentsname{\empty}

\usepackage{tocloft}

%% \renewcommand\cftchapfont{\tiny}
%% \renewcommand\cftsecfont{\tiny}
%% \renewcommand\cftsubsecfont{\tiny}
\renewcommand\cftsubsubsecfont{\small}
%% \renewcommand\cftchappagefont{\tiny}
%% \renewcommand\cftsecpagefont{\tiny}
%% \renewcommand\cftsubsecpagefont{\tiny}
%% \renewcommand\cftsubsubsecpagefont{\tiny}

%% GFX
\usepackage{graphicx}
\graphicspath{{./pics/}}
\newcommand{\baimgspace}{\vspace{0.5cm}}

\usepackage{listings}
\usepackage{enumitem}

%% TOC
\renewcommand\thesection{\arabic{section}}

%% use \tt as the math font
\usepackage{mathastext}
\MTfamily{\ttdefault}\Mathastext

%% new page for each section
\usepackage{titlesec}
\newcommand{\sectionbreak}{\clearpage}

%% paragraph
\titleformat{\paragraph}
            {\normalfont\normalsize\bfseries}
            {\theparagraph}
            {1em}
            {}
\titlespacing*{\paragraph}
              {0pt}
              {3.25ex plus 1ex minus .2ex}
              {1.5ex plus .2ex}
\raggedbottom

\usepackage[english]{babel}

\usepackage{csquotes}

\usepackage[backend=biber]{biblatex}
\newbibmacro{in:}{}
\addbibresource{report.bib}
\defbibheading{mybibliography}[\bibname]{%
\section{#1}%
}

\DeclareFieldFormat{isbn}{\mkbibacro{ISBN}\addcolon\addnbspace\mbox{#1}}
\DeclareFieldFormat{volume}{\bibstring{volume}\addnbspace#1}
\DefineBibliographyStrings{english}{
  volume           = {Volume},
  volumes          = {Volumes},
}

\usepackage{scrextend}

%% footnotes
\newcommand{\fnw}{1.8em}
\deffootnote[\fnw]{0pt}{1.6em}{\makebox[\fnw][l]{\thefootnotemark.}}
\renewcommand{\footnoterule}{
  \kern -3pt
  \hrule width \textwidth height 1pt
  \kern 2pt
}
\interfootnotelinepenalty=10000

\usepackage[parfill]{parskip}

\setcounter{tocdepth}{4}
\setcounter{secnumdepth}{4}

\usepackage[no-math]{fontspec}

\makeatletter
\newcommand{\ttinput}[1]
           {{\begingroup\lccode`~32\lowercase{\endgroup\let~\@xobeysp}%
               \begingroup\lccode`~`\^^M\lowercase{\endgroup\def~{\\}}%
               \def\arraystretch{0}\offinterlineskip
               \ttfamily\catcode`\^^M\active\obeyspaces
               \begin{tabular}{l}\@@input#1\relax\end{tabular}}}
\makeatother

\begin{document}

\begingroup
\makeatletter
\def\@makeschapterhead#1{
  {\parindent \z@ \raggedright
    \normalfont
    \interlinepenalty\@M
    \Huge \bfseries  #1\par\nobreak
    \vskip 40\p@
}}
\makeatother
\endgroup

\tableofcontents

\section{Introduction}

Report update: \today

The purpose of this project is to implement a
\emph{hierarchical scheduler} that manages a
real-time, mixed-criticality task system.

A mixed-criticality task system is a system where
tasks of different criticality levels are executed on
the same physical platform. The tasks are divided into
groups according to their assigned criticality levels.

\boxdef{Real-time System}{\realtimesystem}

\boxdef{Hierarchical Scheduler}{\hierarchicalscheduler}

The hierarchical scheduler and the hard real-time
tasks all execute on a single, separate core: the
\emph{critical} core.

In parallel, best-effort software runs on a dedicated
core as well: the \emph{best-effort} core.

The cores share main memory, the DRAM, as well as the
memory bus.

The theoretic scope of the project is to give methods
to compute the response times for the critical tasks,
considering that the best-effort core software can
interfere because the hardware that is shared between
the two cores.

\boxdef{Response Time}{\responsetimedef}

The criticality groups must be isolated from each
other so that the groups can be separately executed
and analyzed. What is more, the critical core must be
isolated from the best-effort core less the
best-effort core monopolizes the memory, shutting out
the critical tasks from execution thus making them
miss their deadlines.

\boxdef{Deadline}{\deadline}

The solution is two resource servers. On the critical
core a CPU-time resource server monitors and limits
the CPU time of individual groups as to prevent
starvation. Likewise, a resource server limits the
allowed number of best-effort core memory accesses.

The purpose is to realize an architecture and
implement a memory throttling method that will make it
possible to construct modular real time computer
systems whose parts can be analyzed in isolation.

\subsection{goal}

The goal of the project is to be able to:

\begin{enumerate}

\item execute tasks of different criticality levels on
  the critical core; while

\item executing best-effort software on the
  best-effort core; so that

\item software from either core can access the shared
  DRAM; but

\item best-effort core memory interference still does
  not break critical-task schedulability analysis.

\end{enumerate}

\subsection{criticality groups}

A critical group is a subset of all the real-time
tasks in the system. The critical groups are mutually
exclusive: every task belongs to one (and only one)
critical group.

The reason to divide the critical tasks into groups is
to be able to express and employ a more flexible and
fine-grained real-time system. In this project, there
are other parameters apart from the criticality level
attached to each group.

The task classifications are to be used by the
real-time operating system to guide its actions.
Real-time analysis is to be applied to the groups as
isolated entities, and for an entire system one group
at a time, as if the other groups did not exist.

\boxdef{Real-time Operating System}{\rtos}

The reason to create a task-based system is that
real-time systems interact with the outside, physical
world. Because there are so many aspects of the
physical world that can be measured, and in so many
ways -- and all has to be done continuously, virtually
in parallel -- a powerful solution is to employ a set
of tasks, wherein each task is responsible for
collecting and processing data of one particular such
aspect. For example, one task reports temperature,
another volume, yet a third system proximity to other
objects, and so on. This model mimics the
general-purpose process-based computing model, which
in itself has many advantages.

There are several advantages to having several
criticality groups:

\begin{itemize}

\item The system is more \textbf{modular}: tasks can
  be brought in and out as groups, and each group can
  be analyzed for real-time schedulability
  independently of the other groups.

\item The system is more \textbf{well-defined}, and
  \textbf{ordered}. For example, by assigning
  different CPU-budgets to different groups, the
  respective importance of the groups as subsystems
  are made explicit: in turn, this will affect the
  behavior of the system in execution.

\item The system is more \textbf{flexible}: the
  different CPU-budgets assigned to different groups
  can be used to assign a budget that is adopted to
  the typical execution patterns of the tasks of that
  group.

\boxdef{Schedulability}{\schedulability}

\end{itemize}

\subsection{real-time isolation}

The critical groups must be isolated from each other
in real-time analysis. If any one group is deemed
schedulable, this must hold for any run-time scenario
which can involve the tasks of that group, as well as
those of all others. That is, in order to provide
guarantees for a predictable execution of the tasks of
any one critical group, it is necessary to process the
runtime behavior of the tasks of all other groups as
well.

\boxdef{Predictable}{\predictable}

In practice, the resource server solution is an
attempt to formalize and simplify such considerations
to the point where an individual group does not have
to be analyzed in a way that actively has to consider
the peculiarities of the other groups, their tasks,
and statuses.

Whenever needed, the system must intervene to prevent
unruly behavior, right before it happens. If the tasks
of a certain group collectively have depleted their
allocated resources, the group must be hindered from
further activity, less it will jeopardize the
predictability of tasks that belong to other groups.

\boxdef{Resources}{\resources}

\subsection{different kinds of computer systems}

The genealogy of computer systems -- from a desktop OS
to a fully-fledged real-time system in the physical
world -- can be sketched like this:

\begin{itemize}

\item \emph{interactive} non-timesharing -- This is a
  typical computer system for a user to use for
  various, mundane purposes. The software that runs on
  this system does not have any associated deadlines:
  everything is simply executed without any
  guarantees, but also without any cumbersome
  real-time layer or metadata attached to executing
  programs. Still, in some sense, even such systems
  are ``real-time'', because human-computer
  interaction would be unbearable if for example a
  keystroke sometimes had to process for several
  seconds before the character appeared on the screen.

\item \emph{timesharing} -- A timesharing system is an
  interactive system, but it is also a multiprogrammed
  and multitasked system that supports several active
  users to be logged in at the same time. The
  implementations of such systems often employs the
  process-based architecture, which is also what is
  found in many real-time systems. This shows the
  proximity between timesharing and real-time systems,
  the difference being the absence of deadlines in a
  timesharing system. In general, a timesharing system
  is oriented toward active \emph{humans}, who provide
  instructions what the computer should do, while a
  real-time system is oriented toward the outside
  \emph{physical} world, and whatever goes on there is
  sampled and processed as input to trigger various
  responses. \cite[p. 3]{unix_intro}

\item \emph{soft} real-time -- Here, software
  \emph{is} associated with deadlines. If a deadline
  cannot be held, however, that does not imply
  system-wide disfunction. Rather it is up to the
  system designers (and sometimes the user) to figure
  out what to do in such an event.

\item \emph{firm} real-time -- Here, deadlines are
  soft in the sense that breaches are not encouraged,
  but allowed; on the other hand, deadlines are hard
  in the sense that computation whose result arrives
  late has zero value, and is discarded. (In some
  settings, delayed-computation data can even be
  dangerous if used as if it had arrived in time.)

\item \emph{hard} real-time -- Here, a deadline breach
  implies a system fault.

\item \emph{critical} real-time -- Here, a deadline
  breach implies a hazard to people's health. Critical
  real-time obviously implies hard real-time. What is
  not as obvious is that hard real-time does not imply
  critical real-time. For example, consider a computer
  game: a fast-pace, interactive game is for all
  practical purposes hard real-time, even though the
  implementation probably lacks explicit deadlines --
  still, if the game does not react virtually
  instantly to inputs and in-game events, it is
  unplayable. However, an unplayable game is not a
  hazard to the health of any living thing, so for
  this reason it is not considered critical real-time.

\end{itemize}

\subsubsection{hybrids and gray zones}

The real-time system classifications are not cut in
stone. Many system consist of subsystems of different
natures. Actually, there can be combinations within a
subsystem itself: consider a real-time system where
software is associated with \emph{both} a soft and a
hard deadline. \cite[pp. 2-3]{rtspls} If the program
does not complete before the soft deadline, the system
reallocates resources so the program will be more
likely to complete, quicker. Only when the task still
has not completed at the time of the hard deadline,
system fault is flagged.

\subsubsection{where does this project fit in?}

The hierarchical scheduler schedules pieces of
software which all have parameter values -- the
real-time metadata. Thus, any system that runs on top
of \texttt{hs} will be at least a soft real-time
system. But it could also be a firm or hard real-time
system, or something in between, with none or minimal
changes to the code required. Ultimately, it is the
user who decides what software will run and how that
software will behave, and when. Those decisions will
shape the entire system, including its place in the
real-time ladder.

As for now, what is hard-coded is the sporadic task
model: software tasks are annotated with the
parameters WCET, deadline, and period.

\boxdef{WCET}{\WCET}

The criticality side to it is even more unrestrictive.
While the ``criticality'' groups indeed can be
arranged to express criticality (as in physical
hazard) they can just as well be thought of as labels
of task groups that belong to a certain local
scheduler, with no criticality implication whatsoever
-- in execution, the parameter values of the scheduler
are what counts, not any qualitative implication that
the human mind is fond of doing.

\boxdef{Scheduler}{\scheduler}

The hierarchical scheduler does not do anything by
itself, but in combination with different software
sets, it can schedule as many different kinds of
systems.

\subsection{why a real-time multicore?}

Multicore architectures is one way the CPU industry
brings faster computation to computers.

Also, with multicores, there is more computation out
of less power. This is important not the least to
embedded systems, which often have to operate on a
limited power supply. Embedded systems -- because they
apply to problems outside the world of computers --
are a huge implementation field for real-time systems.

Real-time systems on multicores are yet rare, in part
because of the increased unpredictability due to the
multiple sources of computation. This poses
difficulties both theoretically -- guaranteeing real
time analytically -- as well as to enforce it in
practice, because distributed computation implies
communication and synchronization delays that must be
bounded.

\subsection{meta}

The writer of this report as well as the programmer of
all new related software can be reached at
\texttt{embe8573@student.uu.se}.

This is a BibTeX entry for this report:
\tiny
\begin{verbatim}

@techreport{multicore-mixed-criticality-with-a,
 author      = {Emanuel Berg},
 title       = {Multicore mixed-criticality with a hierarchical real-time scheduler and resource servers},
 institution = {Department of Information Technology, Uppsala University, Sweden},
 type        = {\unskip\space},
 year        = 2015
}

\end{verbatim}

\normalsize

The report as well as the source code can be found at
the author's home page:
\texttt{http://user.it.uu.se/$\sim$embe8573}

\section{Related work}

The classical paper on hierarchical scheduling is
\cite{ieee_hs}. However, the scheduler implementation
of this project is not perfectly layered. Optimally,
any hierarchical outline relies on a one-way
communication data flow, where superior entities never
ask (but only tell) the lesser components what to do
(and, whenever necessary, provide them with what they
need to do it). For a hierarchical scheduler, that
translates to the root scheduler scheduling the
schedulers below solely based on their properties,
without looking any further below, and only after one
particular scheduler has been favored would that
scheduler decide what of its task to execute, without
the interference of the above scheduler. Instead,
because of practical considerations when implementing
the EDF algorithm, the root scheduler is not ignorant
to what happens at task level: contrary to just
barking orders, it must poll the below layers for
information that will determine its decision.

\boxdef{EDF}{\edf}

Previous work to a large extent consider only two
criticality levels: i.e., one crticial level and one
level which is best effort. \cite{heechul}
\cite[pp. 299-308]{heechul2} In this project, it is
possible to implement and analyze an arbitrary number
of critical groups, and have best-effort software run
in parallel.

In this project, unlike \cite{heechul}, there is not a
best-effort sphere of possible memory access once the
allocated budget has been depleted. And, unlike
\cite{heechul2}, this implementation is userspace
only.

In \cite{memory-architectures-for-noc-based}, the
unusual memory architecture of a network-on-a-chip
system (a NoC) is used to provide isolation between
criticality levels. Here, specialized hardware is
used, including a predictable multiprocessor, whereas
our project uses commodity components which are by
original design unpredictable.

In \cite{workload-aware-shaping-of-shared}, a monitor
is (in part) instructing a scheduler what process to
execute from the suggestions of four queues.
The queues are a division based on qualitative
properties of the processes, so that such properties
also influence what process to run. The algorithm is
``slack'': context switches are not always carried out
at times of priority inversion. Instead, to decrease
overhead and improve best-effort quality-of-service,
preemption occur only at the very moment it has to,
less a critical process will not be able to make its
deadline. Our project is similar to their but their
solution is more sophisticated (and complicated).
In our project, the critical groups (which can come in
any number) are holder of scheduling and real-time
metadata that is arbitrary and cannot be
computationally derived from properties of the
processes which make up the groups. Also, our monitor
serves only to freeze the best-effort core -- it
doesn't influence any scheduler on either core. And,
freezing \emph{always} happens when the maximum
allowed DRAM accesses have been accounted, so our
algorithm is not slack, either.

One of the most sensible suggestions to the problem
how to uphold predictability while sharing resources
is presented in
\cite{mapping-mixed-criticality-applications-on}.
Here, the shared memory is divided into banks.
However, the banks are not merely distributed over the
critical tasks -- while that would indeed provide
isolation between criticality levels, it would do so
at the price of no longer sharing the memory and thus
have the whole system constantly operate at the bottom
end of what it is capable of. Instead, the tasks are
dynamically mapped to the banks by means of the
scheduling algorithm. Consequently, the entire scope
of the capabilities of the system can be employed: at
the very least, there is the subdivision and
distribution of memory; at most, there is unrestricted
access. The challenge is to find or (re)design an
algorithm that maps the tasks to the banks in such a
way that the system can run on the most cylinders the
most of the time. In effect, the once contradictory
poles -- predictability vs. resource sharing -- are
transformed into an optimization problem.

Also, in
\cite{privatization-and-fixed-priority-scheduling} the
solution is a subdivision of the DRAM between the
critical tasks. Each critical task is assigned a DRAM
bank. There is one critical task for each bank. This
means the critical tasks do not share memory anymore:
instead, they use their designated ``virtual memory''
bank which is a fraction in size to the original DRAM.
Nonetheless, what is innovative about this project is
that for each bank, alongside the singular critical
task, there can be an arbitrary number of best-effort
tasks. Access to the bank memory is granted according
to a priority algorithm. Priorities are fixed with the
critical task in each bank having the highest
priority. This uncomplicated scheme has the benefit of
providing complete isolation for the critical tasks,
both from each other and from the best-effort tasks.
The drawback is that resource utilization is sensitive
to both the setup and the dynamic situation of every
execution.

Another impressive suggestion is
\cite{scheduling-of-mixed-criticality-applications}.
Here, there are no dedicated cores -- all critical
tasks, of any and all criticality levels, coexist
across the cores. Nor are there any budgets to be
distributed by resource servers. This makes for
minimal a-priori arrangements. Also, there is no
reliance on specialized hardware.

The solution is based on subdividing all cores as well
as the shared memory along the criticality levels. A
dynamic scheduling algorithm synchronizes the cores so
that only tasks from the same criticality level access
memory at the same time.

Interestingly, the authors comment on the type of
solution that is presented in our paper:

\begin{itemize}
\item Our solution is flexible in terms of managing
  processes -- e.g., to include arrivals. This is
  true, especially compared to monotonic scheduling.
  However, their solution is even more flexible as all
  cores share all work. The lack of a-priori metadata
  markup and budget assignments is a two-sided sword.
  On the one hand, there is no room for humans to
  screw up the algorithm. On the other hand, no expert
  human can tweak it to perfection. In general, we say
  their solution is better, assuming a time-tested
  dynamic algorithm to do the allocations.

\item Our solution requires ``a high design and
  implementation overhead''. Here, it is unclear if
  this aims at the scheduling and throttling software,
  or the a-priori setup of task systems and resource
  budgets. If it aims at the software, our project
  shows such software is not insurmountable to create.
  However, if it aims at the setup, we agree, and
  especially if compared to their project, which does
  not require any of that.

\item Our solution cannot be done with COTS
  components. COTS is ``commercial off the shelf''
  computer hardware. What truth there is to that of
  course depends on the definition of ``COTS''. In
  fact, a performance monitor counter (PMC) is all
  specialized hardware that is required, and such are
  found in many desktop PCs.

\end{itemize}

\section{System overview: two cores, shared DRAM}

The system consists of two cores: the \emph{critical}
core, and the \emph{best-effort} core: Those cores
share DRAM and memory bus.

\vspace{2\baselineskip}
\index{multicore architecture \emph{fig.}}
{\setmonofont{DejaVu Sans Mono}\centerline{\ttinput{figures/multicore.txt}}}
\vspace{\baselineskip}
\begin{center}\textbf{Multicore Architecture}\end{center}

\subsection{the critical core}

The critical core runs critical tasks. The
mixed-criticality scheduler, as well as all the
critical groups, reside on the critical core.

\subsection{isolation between the cores}

Whatever happens on the best-effort core cannot be
allowed to influence the execution of critical tasks
to the extent that even a single critical task cannot
complete before its deadline. To that end, the
interference from the best-effort core is bounded by a
parameter for each critical group. The value specifies
how many memory accesses the best-effort core is
allowed to do for a specific time span, while a task
of that group is executing.

\subsection{the best-effort core}

The best-effort core runs a media player.

To run a media player as the best-effort task is
interesting because a media player task does not lend
itself to static real-time analysis. A media player is
user-oriented software. Some downgrade in quality can
be tolerated. If the media content is streamed from a
network, data may be sketchy, and arrival spotty; and,
the service is most often designed to work on
different end-hardware platforms. \cite[pp. 4-13]{media} Also,
any substantial quality improvement can be detected by
inspection.

As the real-time system can block the best-effort
software from accessing memory, the performance of the
best-effort software can be much worse compared to if
it did not have to subject itself to the demands of
the real-time system. The extent of this performance
downgrade is evaluated by executing and measuring the
media player, when it runs in parallel with the
critical task system.

\section{The Linux implementation}

\subsection{the real-time system}

The hierarchical scheduler, or \texttt{hs}, that runs
the critical tasks is written in C++: C++ is fast,
which matters because it is desirable to reduce the
scheduling overhead. The object oriented support in by
C++ is also helpful to express the different
components of the hierarchical scheduler, which is
modular by concept. More generally, C++ is an
extension of C, which is the system programming
language of choice since the early-mid 70s. \cite[pp.
  v-vi, 6, 41-42]{cpp}

Programmers of real-time systems have discussed what
makes for a good implementation language for such
systems. \cite[pp. 20-22]{lang} provides a list which
in terms of technology amounts to:

\begin{itemize}

\item The language should come with debugging tools,
  including a compiler which provide compile-time
  warnings and error messages, in order to detect
  problems at the earliest stage possible.

\item The language offers features for modular design
  and development, e.g. user-defined datatypes (or
  classes).

\item The language is portable, fast, and vast with
  respect to what problems it can express and solve.

\end{itemize}

C++ does that, of course.

There is also a discussion whether such a programming
language should in itself include real-time
functionality, and provide it transparently on any
platforms for which it is ported, \emph{or} if
real-time functionality can be delegated the
underlying OS, and just be accessed through an API.
\cite[pp. 22, 131]{lang} (Bear in mind that those
approaches are not mutually exclusive.)

In this project no attempt is made to avoid using OS
functionality, and the C++ used is all vanilla.

Both critical and best-effort cores run on Debian
GNU/Linux. Linux is a good all-around platform for
programming; it comes with both general and specific
tools that were indispensible while developing the
hierarchical scheduler, and while setting up the
overall dedicated-core architecture as well as the
framework to carry out the experiments.

The Linux kernel and distribution used for this
project are:

\begin{verbatim}

$ uname -a
Linux debian 3.16-2-amd64 #1 SMP Debian 3.16.3-2 (2014-09-20) x86_64 GNU/Linux

\end{verbatim}

\subsection{the critical tasks}

The software of the critical tasks is written in C++.
The task software is hard-coded functions that are
compiled together with the hierarchical scheduler --
but, the task systems are independently defined, in
text files, that are read at run-time.

The tasks can run synthetic workloads or benchmarks to
collectively produce a behavior similar to a real
system.

\texttt{hs} can also run ordinary Linux processes. If
so, they are forked and controlled by signals. The
interface to define and later execute such systems is
the same as for the hard-coded task software, only, as
for now, task software and Linux processes cannot be
mixed in a single system.

\subsection{\texttt{perf\_event\_open(2)}}

\begin{sloppypar}
  At every global tick, the hierarchical scheduler
  invokes the Linux \texttt{perf\_event\_open} tools
  to poll the number of last level cache (LLC) misses
  that originates from the best-effort core. An LLC
  miss implies a DRAM fetch and use of the memory bus
  to communicate both the request and the data.
  (Details on the caches are in \spref{caches}.)
\end{sloppypar}

By booking the number of such requests, it is possible
to calculate the number of LLC misses since the
beginning of the global period.

The outcome is at every tick compared to the
maximum-allowed accesses for the executing critical
task. If the performed best-effort accesses exceed the
number allowed, the best-effort core is frozen: all
software there will be suspended, and only resume
whenever a task executes that belongs to a task
scheduler with a non-depleted memory budget.

\label{poll}
Because data is \emph{polled}, and polled
periodically, the best-effort core will be able to
exceed the number allowed often, as it can only be
frozen on a scheduling interrupt. This problem can be
minimized by increasing the frequency of the global
scheduling interrupts. However, there are other
problems associated with a high frequency:
\spref{high-frequency-problem}

The problem of periodic, non-immediate enforcement of
memory budgets could possibly be avoided if over-use
instead would trigger a kernel interrupt, that would
immediately freeze the best-effort core. In such an
implementation, the memory budgets could be
communicated to the kernel by means of a syscall.

\subsection{\texttt{cgroups}}

To freeze and thaw the best-effort core,
\texttt{cgroups} is used. This method stems from the
high-performance computing world (HPC) where it is
often desired to collectively suspend or activate
process groups.

\section{Real-time Linux and Unix}

Conventional wisdom has it that UNIX and Unix-like
systems like Linux cannot host real-time systems
without considerable changes to their kernels.

It is argued, because of the layered architecture -- a
kernel space, a userspace, and asynchronous syscalls
in between -- that any userspace-only application is
inherently unpredictable. \cite[pp. 17-18]{advunix}

Furthermore, many Unix-like systems do not have a
scheduler suitable for shuffling real-time processes.
(Linux has such features, but they need to be enabled
explicitly.)

While those arguments are true to form, whether they
are true in essence depends on the preferred
definition of a real-time system. The definition used
for this project -- \realtimesystem\ -- is very much
attainable on Unix-like systems, with or without
kernel surgery.

\subsection{Linux real-time schedulers}

As for kernel version 3.14, Linux provides four
schedulers that may be more fit for real-time purposes
than the default one, which for its part maximizes
average throughput to benefit a varied dose of
interactive computer use (e.g., editing).

The real-time schedulers are:

\begin{itemize}

\item \texttt{SCHED\_FIFO} is a fixed-priority
  scheduler, only real-time processes do not get
  preempted by common processes. If several real-time
  processes have equal priority, the one who has the
  CPU will not let it go until completed at what time
  another contender monopolizes the CPU.

\item \texttt{SCHED\_RR} is like \texttt{SCHED\_FIFO},
  only when several real-time processes have equal
  priority, they do Round Robin, still excluding every
  other process from the CPU.

\item \texttt{SCHED\_OTHER} is the round-robin,
  time-sharing algorithm where processes execute for
  certain timeslices.

\item \texttt{SCHED\_DEADLINE} is the EDF algorithm.
  This can likely be used to enhance this project,
  which employs a somewhat modified brand of EDF, and
  -- when dealing with real Linux processes --
  enforces it with userspace signals.

\end{itemize}

For this project, the ordinary Linux scheduler is
used. To use a real-time scheduling policy complicates
matters, especially when \texttt{hs} forks processes
and then attempts to control them through signals. But
in all fairness, Linux has many features that
ultimately can transform it to just about any system
-- including a hard real-time system. For example,
\texttt{mlock(2)} can be used to lock the virtual
address space of a process into the RAM. As nothing of
that has been touched upon, scheduling is left alone
as well.

\subsection{the Linux and C++ clocks}
\label{clocks}
\index{clocks}

To uphold an even rate of periodic scheduling, the C++
library function
\texttt{std::this\_thread::sleep\_until} is used,
which however may
``block for longer [than what has been specified] due
to scheduling or resource contention delays''.
\footnote{http://en.cppreference.com/w/cpp/thread/sleep\_until}

Actually, there can be widely diverging results due to
many factors. To illustrate the extent of imperfect
periodicity \texttt{-l} (or equivalently
\texttt{--log}) can be used to have the hierarchical
scheduler output the current time in nanoseconds, at
every tick. (Again, the same library functions are
used.)

It is likely that using a real-time scheduling policy
for \texttt{hs} would result in a more even tick rate,
especially if \texttt{hs} is intended to run among
many other processes that are not real-time.

Here is a sample output for a period of one
millisecond:

\begin{verbatim}

3594454136974
3594456742892
3594456842067
3594459262486
3594459326740
3594459349369
3594460102258
3594461102664
3594462098601
3594463098448
3594464103883
3594465098703
3594466102182
3594467103985
3594468097687
...

\end{verbatim}

Then, the following method is used to calculate the
offsets from the intended tick times:

\begin{verbatim}

offset_0 = time_1 - time_0 - DESIRED_TICK
offset_1 = time_2 - time_1 - DESIRED_TICK
...

\end{verbatim}

This produces, for the example trace:

\begin{verbatim}

 1524064
-958095
-488762
 323073
-289016
 1605918
-900825
 1420419
-935746
-977371
-247111
 406
-4063
-153
5435
...

\end{verbatim}

Last, for all offsets acquired, some statistical data
is computed:

\begin{verbatim}

readings:             9999
mean:                 7.000000      # drift size
variance:             1828079556
standard deviation:   42756.047011  # drift stability
min:                 -977371        # observed worst cases
max:                  1605918

\end{verbatim}

\textbf{Note:} It has been observed that the early
tick times of a run are much more inexact than those
of the rest of the trace. This is the case in the
above example as well. It is telling that the first
mere 15 readings contain both the minimum value
($-977371$), and the maximum value ($1605918$), of all
9999 readings, whose mean is only seven! (For a longer
trace, the mean would be even smaller.) As for now,
this behavior remains a mystery.

To exemplify, here are the offsets found at the
end-most part of another trace -- a trace that
likewise has a specified rate of a single millisecond.
As is typical, these offsets are much smaller than
their early brethren.

\begin{verbatim}

 10743
-431
-4902
 3480
-4622
-153
 6832
 2642
-7696
 3480
 127
-152
-4622
-153

\end{verbatim}

\subsection{hardware}

The hardware platform must be considered because the
real-time task superstructure and all the individual
tasks share hardware resources. Specifically, the
critical tasks -- including the hierarchical scheduler
and the task software, and all forked processes --
share the critical core for CPU-execution; and, they
share the DRAM and the memory bus with the best-effort
core. That has to be accounted for both in analysis,
\emph{and} in practice, where monitoring and
throttling is employed to hinder over-use of shared
resources.

The CPU is a dual core \texttt{x86\_64}:

\begin{verbatim}

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             AuthenticAMD
CPU family:            15
Model:                 35
Stepping:              2
CPU MHz:               1000.000
BogoMIPS:              1989.83
L1d cache:             64K
L1i cache:             64K
L2 cache:              512K
NUMA node0 CPU(s):     0,1

\end{verbatim}

DRAM and memory bus usage is monitored with a PMC,
which is accessed by means of the
\texttt{perf\_event\_open} Linux tools.

\index{caches}
\label{caches}
The \texttt{L1} and \texttt{L2} caches are not shared
between the cores but appear pair-wise, with one pair
for each core. Save for the CPU registers, \texttt{L1}
is the smallest memory storage unit, with $64K$ for
data, and the same amount for instructions. Below
\texttt{L1} is the $512K$ \texttt{L2}, which is the
last level cache, or LLC, right above the shared DRAM.
Thus, a failed memory lookup at the second level is
indicative of an imminent DRAM access. In this
project, LLC misses are counted as a way to count
fetches from the shared DRAM.

\begin{center}
  \index{memory architecture \emph{fig.}}
  \includegraphics[width=\textwidth]{figures/llc/llc.pdf}
\end{center}
\textbf{Memory Architecture. First a miss in the
  last-level-cache (LLC), then a DRAM fetch.}

\clearpage
\subsection{isolation}

All critical groups must be isolated from all other
critical groups, but they must also be isolated from
the best-effort software. Here, the intersection is not
the CPU, but the shared DRAM and the shared memory
bus.

\index{isolation \emph{fig.}}
\vspace{\baselineskip}
\begin{center}
  \includegraphics[width=\textwidth]{figures/isolation-figure.png}
  \textbf{Isolate us! Resource sharing interference.}
\end{center}

Isolation must be implemented in practice, as well as
digested into something that is formally computable,
so it can be used to determine task response times,
and, later on, overall system schedulability. In this,
software as well as hardware are considered.

It is important to note that the word ``isolation'' is
not used in the general sense, but in terms of real
time schedulability analysis and task response-time
computation. If $A$ is isolated from $B$ in terms of
$i$, that does not mean $A$ is physically separated
from $B$ so that $B$ cannot ever influence $A$. On the
contrary, it means that $A$ \emph{is} influenced by
$B$ precisely through $i$, only the designers and
implementors of the system has accounted for this, for
example by providing throttling mechanisms that in
practice will provide a bound for the worst-case
interference $B$ can have on $A$ (through $i$). This
bound is then used in the response-time calculations,
which is the theory mirror image of the real-time
implementation.

\subsubsection{starvation}

\label{starvation}
Because the best-effort core and the critical core
share the DRAM, and because the mechanism that
throttles the best-effort core resides on the critical
core, it is possible that the best-effort core can
overflow the memory, shutting out the critical core to
the extent that the critical core cannot throttle the
best-effort core, whose memory budget thus cannot be
enforced. In terms of real-time, that would
immediately break the system.

%% In practice, such a situation is highly unlikely. For
%% the purposes of this project, the assumption is that
%% the best-effort core will not ever starve the
%% critical-core from enforcing a budget.

\subsubsection{isolating the cores on Linux}

The cores on the project computer are originally
general-purpose: the Linux scheduler can execute any
process on either. In order to turn these cores into
one critical core and one best-effort core, a kernel
parameter is set that will stop the Linux scheduler
from using the best-effort core; then, a userspace
tool is used to start best-effort processes so they
will only execute on their designated core.

This turns the system into one where there are
dedicated cores for specific software: distribution of
processes over the cores can be a function of a-priori
policy decisions.

\label{grub}
\index{GRUB}

To isolate one of the cores from the Linux scheduler
until explicitely told otherwise, in:

\begin{verbatim}

/etc/default/grub

\end{verbatim}

put (or change) \texttt{GRUB\_CMDLINE\_LINUX\_DEFAULT}
into:

\begin{verbatim}

GRUB_CMDLINE_LINUX_DEFAULT="quiet isolcpus=1"

\end{verbatim}

Then, run

\begin{verbatim}

sudo update-grub

\end{verbatim}

and reboot.

After that, here is how to execute a program, say,
\texttt{forever}, exclusively on CPU 1:

\begin{verbatim}
taskset -c 1 forever
# to confirm:
ps -o psr,comm -p `pgrep forever` # psr = processor = core
\end{verbatim}

This method is used to invoke all best-effort
software.

\label{remaining-processes}
The method to isolate the best-effort core by setting
a kernel parameter in a GRUB initiation file does
isolate the core from most processes that are not
explicitly told otherwise. Still, a few system
processes remains on the best-effort core, unaffected
by the GRUB configuration. This is why, on the
critical core, the hierarchical scheduler and the
critical-task software co-exists with some modest
Linux system software:

\begin{verbatim}

watchdog/1
migration/1
ksoftirqd/1
kworker/1:0
kworker/1:0H
kworker/1:1
kworker/1:2
kworker/1:1H

\end{verbatim}

Fortunately, these processes are low-key: they demand
CPU or memory resources in quantities that are zero or
negligible in the face of userspace processes that are
intentionally and explicitly invoked to be executed
exclusively on the best-effort core.

To illustrate, one execution of a media player on the
best-effort core for 10 seconds booked $70464921$
memory accesses. During this execution, no activity
what so ever could be detected from the above
processes, which were monitored with \texttt{top(1)}.

A consecutive run of \texttt{hs} for another 10
seconds but with an idle best-effort core (i.e.,
without the media player) booked the number of memory
accesses as: $0$.

\section{Scheduling}

There is a single, top-scheduler, that schedules
task-schedulers at the level below. The
task-schedulers schedule tasks. At the down-most level
reside the individual tasks. The tasks are grouped and
assigned one unique task-scheduler: such a group of
tasks, along with its scheduler, is the
implementation of a criticality group.

Scheduling is done \emph{hierarchically}. The
top-scheduler is the highest entity. The
task-schedulers are at the level below, themselves at
the same level: they all belong to the top-scheduler.
Scheduling is carried out at two levels: at the level
of the top-scheduler, and at the level of the
task-schedulers.

Scheduling is also, conceptually, done in parallel,
or vertically: every task-scheduler schedules its task
set. The tasks are themselves at the same, down-most
level, below the task-schedulers to which they belong.
But, unlike the task-schedulers, the tasks do not all
belong to the same above scheduler: they are grouped,
together with their designated task-scheduler, into
criticality groups. There can be an arbitrary number
of task-schedulers and each can have a task set which
contains an arbitrary number of tasks.

The task system can be visualized as a tree: the root
(or top node) is the top-scheduler; the $n$ internal
nodes immediately below are the task-schedulers; and,
at the third and lowest level, the $k$ leafs (or
terminal nodes) are the individual tasks.

\vspace{2\baselineskip}
\index{hierarchical scheduler \emph{fig.}}
{\setmonofont{DejaVu Sans
    Mono}\centerline{\ttinput{figures/scheduler.txt}}}
\vspace{\baselineskip}
\begin{center}\textbf{Hierarchical Scheduler}\end{center}

\subsection{algorithm}

The scheduling algorithm is global, budgeted, and
preemptive EDF.

\begin{itemize}

\item It is \textbf{global} as it considers the critical
  tasks of \emph{all} task-schedulers, and compares
  them on a scheduler as well as task-by-task basis.

\item It is \textbf{budgeted} as all task-schedulers
  are assigned a CPU-budget. For each global period,
  the tasks of a particular task-scheduler can execute
  for a total time not exceeding that budget.

\item It is \textbf{preemptive} as a task, once assigned
  the CPU, can later be replaced, and put back
  into the ready queue, before it has completed. Here,
  the algorithm does not differ from the commonplace
  preemptive EDF of real-time scheduling,
  except for one implementation-derived detail:
  preemption can only be done at the time of a global
  scheduling interrupt. Those occur regularly and
  frequently according to a system parameter, which is
  set beforehand and thereafter does not change.
  Arrival of new tasks also takes place at those
  interrupts, so a task with the highest priority that
  just arrived will immediately preempt the CPU, as
  long as the task-scheduler it belongs to has not
  depleted its budget. So the algorithm is
  ``polled-preemptive EDF''.
\end{itemize}

\subsection{step-by-step description}

Scheduling is defined as follows:

\begin{enumerate}

\item Execution regularly comes to a halt in order to
  do scheduling.

\item Whenever so, the top-scheduler tells all
  task-schedulers to do scheduling of their respective
  task sets. In this implementation, all
  task-schedulers do the same, commonplace EDF. The
  task states are updated. The task-schedulers all
  propose a task to the top-scheduler.

\item Of the proposed tasks, the task with the most
  immediate deadline is favored, as long as its
  task-scheduler has a non-depleted CPU-budget.

\end{enumerate}

\subsection{task priority}

EDF is a priority scheduling algorithm where the
priority is a dynamic property.

For this project, \emph{locally}, at the level of an
individual task-scheduler, the highest-priority task is
the task with the most immediate absolute deadline,
just like commonplace EDF.

However, \emph{globally}, the highest-priority task
must also belong to a task-scheduler that has not
depleted its CPU-budget. If the task-scheduler has a
depleted budget, its proposal to the top-scheduler is
academic as no matter what deadline, no task of that
task-scheduler will ever be favored. If a task belongs
to a depleted task-scheduler, that is equivalent to
the task having the lowest possibly priority. (If all
schedulers are depleted the CPU will idle.)

Note that a depleted scheduler has a zero remaining
CPU-budget. If the budget is non-zero, it is not
depleted and its task will be considered,
even if that task requires more than the remaining
CPU-budget to terminate. (This is a possible window
for optimization that has not been explored.)

\section{The task finite state machine}

Each individual task belongs to one (and only one)
state, always.

\vspace{2\baselineskip}
\index{sporadic task implementation \emph{fig.}}
{\setmonofont{DejaVu Sans Mono}\centerline{\ttinput{figures/task-states.txt}}}
\vspace{\baselineskip}
\begin{center}\textbf{Sporadic Task Implementation}\end{center}

\subsection{transitions}

Transitions occur regularly, and at the same time for
all tasks, namely when the global scheduler interrupts
execution to re-asses the state of the system.

The transitions are:

\begin{enumerate}[label=(\alph*)]

\item The task arrives: it is employed. This happens
  after a semi-random delay: in practice, the task
  should arrive sooner rather than later. (The random
  delay can be disabled with the \texttt{-i} or
  \texttt{--immediate} option.)

\item The task has the most immediate deadline in the
  system of all tasks that belong to non-depleted
  schedulers and is thus passed to the CPU for
  execution.

\item The task is preempted by another task from a
  non-depleted task scheduler, a task with a more
  immediate deadline.

\item The task is completed and is released by the CPU.

\item The minimum inter-arrival time has passed, so a
  new task instance can be released.

\item Timeout -- the absolute deadline of the task is
  in the past, but the task still has not completed.

\end{enumerate}

\subsection{states}

\begin{longtable}{p{0.2\linewidth}p{0.7\linewidth}}
  \texttt{UNEMPLOYED} & Either of:
  \vspace{\baselineskip}
  \begin{itemize}

  \item The task has never executed, and has not yet
    been placed in the ready queue (where it would
    have state \texttt{READY}).

    \vspace{\baselineskip}

  \item The task has had at least one instance of
    itself executing (the \texttt{RUNNING} state); it
    completed its computation, and has been put on
    hold (the \texttt{HOLD} state). However, the time
    of necessary holding (due to the sporadic task
    model) has transpired, so another, new instance of
    the task can indeed be placed in the ready queue
    -- only this has not happened, yet.

  \end{itemize}

  \vspace{\baselineskip}

  Which one of these situations is at hand is not of
  practical or analytical importance, but they
  illustrate the cyclic nature of the life of a task
  in this system.

  \vspace{\baselineskip}

  The reason for this state is to get the sporadic,
  semi-random behavior of task arrivals.

  \vspace{\baselineskip}

  Note that an unemployed task has not arrived so it
  does not have a pending deadline, and it cannot be
  selected for execution. \\\\

  \texttt{READY} & The task is queuing. It has been
  deployed -- it has arrived -- and may in part have
  been executed, only, if so, it has been preempted --
  either way, it is not completed so it waits,
  queuing. All time spent in this state is added to
  the response time of the task. \\\\

  \texttt{RUNNING} & The task is executing: the
  scheduler that holds the task has not depleted its
  CPU-budget, and the task has the most immediate
  deadline for all tasks that run on non-depleted
  schedulers. When executing, the task is closing in
  on the absolute deadline as much as when it idles in
  the ready queue. However, contrary to when idling,
  the task is also closing in (at the same speed) on
  its own termination, at what point it has received
  enough CPU time to complete its computation and
  terminate successfully. \\\\

  \texttt{HOLD} & The previous task instance has
  completed, and before another instance of the same
  task can arrive, it must hold until its period is
  over, in accordance with the minimal-interarrival,
  one-instance-at-a-time policy of the sporadic task
  model. \\\\

  \texttt{DELAYED} & The task has missed its deadline:
  the absolute deadline is in the past, and the task
  has not been assigned the CPU (state \texttt{RUNNING})
  for a time that equals or exceeds the WCET of the
  task. In this system, a delayed task will not ever
  be completed, nor will any further instances of that
  task be released.

\end{longtable}

\section{System description}

\textbf{Terminology:} This section is a
\emph{description} of the hierarchical scheduler as a
piece of software. The parameters correspond directly
to C++ data types: in some cases classes, in some
cases primitives. Most parameters are part of the
interface and can thus be specified by the user
without any changes to the software required. Only the
parameter \emph{names} are simplified, most often to
single letters; and OO relationships are expressed as
parenthesized lists: this is to make the description
more accessible, and, later, to facilitate the use of
the parameters in formulas. Nonetheless this remains a
description of actual software and is not a model to
be verified by formal methods -- which, alas, at best
would verify only the model itself.

\subsection{the top-scheduler}
$g$ is the singular, or root, top-scheduler:

\beq{\topscheduler}{top\_scheduler}

\begin{longtable}{p{0.15\linewidth}p{0.15\linewidth}p{0.15\linewidth}p{0.50\linewidth}}

  parameter & name & (unit) & description \\ \hline \\

  $l$ & lifetime & ms & The system
  lifetime. This is the amount of time that the
  top-scheduler will execute, from the time of
  invocation. As the top-scheduler is the topmost body
  of the system, $l$ equals the system lifetime. \\\\

  $p$ & period & ms & The global period. At the
  beginning of each period the task-schedulers have
  their budgets (re)supplied to their individual,
  pre-assigned levels. \\\\

  $r$ & rate & ms & The scheduling rate by which
  $g$ will schedule $S$. At every $r$, execution comes
  to a halt: scheduling is done, and execution
  resumes. \\\\

  $S$ & schedulers & & The set of task schedulers that
  the top-scheduler schedules. \\\\

  $a$ & algorithm & & The scheduling algorithm that $g$
  applies to $S$, in order to select what task to
  execute (for all $s \in S$). The algorithm updates
  and maintains the statuses of all other tasks and
  schedulers as well.

\end{longtable}

\subsection{how the time parameters relate}

\beq{\relate}{relate}

If not $0 < r$ there will be constant preemption and
not any task execution at all.

If not $r < p$, then at each tick, the budgets of all
$s \in S$ will have been resupplied, and what happened
before the tick will not influence the selection of
the next $s'$, as then (and always), every $s' \in S$
(including $s$) is equally ready. If so, there will
not be any isolation between the critical groups as
that is expressed and implemented as the CPU-budgets
of the schedulers. If the budgets cannot be depleted,
they cannot play a role in this system.

If not $p < l$, there will not be any resupplies of
budgets.

\subsection{task scheduler}

$S$ is the set of task-schedulers.

The task-schedulers are the implementation of the
critical groups.

$S \neq \emptyset$ as, unless so, there is not any
$s \in S$ for $g$ to schedule (or any tasks to
execute).

The set of task schedulers is:

\beq{\taskscheduler}{task\_scheduler}

\textbf{Notation:} The subscripts are only given to
indicate that the properties belong to a certain task
scheduler. A single task-scheduler $s$ would be fully
described as $s = (m, b, P, \alpha)$.

\subsubsection{$m_{i}$, the maximum best-effort
  core memory accesses}

For each global period (of time $p$), the software
that runs on the best-effort core must not exceed a
certain number of memory accesses -- $m_{i}$ -- during
the execution of the critical tasks of $s_{i}$.

That way interference from the best-effort core
vis-a-vis a specific critical group can be quantified,
and thus bounded. The bound is used in response-time
analysis of the critical tasks on a task-scheduler
basis.

\subsubsection{$b_{i}$, the CPU-budget}

$b_{i}$ is the budget assigned to $s_{i}$. The time
the computer spends executing a $t \in P_{i}$ will
reduce the working budget of $s_{i}$ by the same
amount of time. When the working budget is depleted
for $s_{i}$, $g$ will not consider $s_{i}$; however,
$g$ will restore the working budget of $s_{i}$ to
$b_{i}$ at the transitions between global periods.

$b_{i} > 0$ as otherwise $g$ will never consider $s_{i}$.

The CPU-budget feature makes it possible to isolate
the critical groups from each other. For each global
period, the tasks of $s_i$ -- $P_i$ -- cannot delay
any task that belongs to another group by any more
than $b_i$, the budget of $s_i$.

\subsubsection{$\alpha_{i}$, the (task) scheduling algorithm}

$\alpha_{i}$ is the scheduling algorithm $s_{i}$ uses
to propose a $t \in P_{i}$ for execution.

In principle, $\alpha_{i}$ can be an altogether
different algorithm than the global scheduling
algorithm $a$. $\alpha_{i}$ can also be different from
one task-scheduler to another. In this project, all
task-schedulers do commonplace EDF, while the
top-scheduler do a slightly modified EDF, the most
notable addition being the ruling-out of schedulers
that have depleted budgets.

\subsection{$P_{i}$, the sporadic task set}

\beq{\sporadic}{sporadic\_task\_set}

$P_{i} \neq \emptyset$ as otherwise there are not any
tasks to schedule.

\subsection{the sporadic task model}
\label{sporadic-task-model}
\index{sporadic task model}

The sporadic task model is a small-but-important
extension to Liu and Layland's \emph{periodic} model
in which each task has only two parameters: WCET, and
period. \cite[pp. 46-61]{periodicmodel} The sporadic
model is different from the periodic model because it
decouples the deadline from the period \cite{mok}
whereas the period remains as an upper bound for the
deadline and also determines the frequency of task
instance releases.

The sporadic task model of this system does not differ
from the sporadic task model commonly used in real-time
scheduling:

\beq{\sporadictask}{sporadic\_task}

\subsubsection{task parameters}

\begin{itemize}
\item $C_{j}$ is the WCET.
\item $D_{j}$ is the deadline, relative to the  arrival time.
\item $T_{j}$ is the minimal inter-release time: i.e.,
  there can be at most one instance of $t_{j}$ for each
  $T_{j}$.
\item $0 < C_{j} \leq D_{j} \leq T_{j}$
\end{itemize}

\clearpage
\subsubsection{task properties}

\begin{itemize}

\item the tasks do not share any task-specific
  resources

\item there are not any task-precedence constraints

\item there is not any communication between tasks

\end{itemize}

\section{Schedulability method: response time}

One method to ensure schedulability is to assume the
worst-case scenario: i.e., that the best-effort core
software produces a maximum number of memory accesses,
at all times, and at the \emph{worst} times with
respect to the critical tasks completing before their
deadlines -- while, simultaneously, critical tasks are
released in the most unfavorable way -- the way that
causes maximum queuing.

\subsection{$r_{j}$, the worst-case response-time for $t_{j}$}

$r_{j}$ is the worst-case response-time for the task
$t_{j}$: it is the maximum-length time span from the
arrival of $t_{j}$, to its completion.

The following terms add to the delay of $t_{j}$. The
sum of those, plus $C_{j}$, the WCET of $t_{j}$, is
equal to the worst-case response time:

\beq{\responsetime}{response\_time}

\subsubsection{$Q_{j}$, queuing}

$Q_{j}$ is the worst-case time spent queuing for
$t_{j}$. When a task is queuing, it is in the
\texttt{READY} state. The definition of queuing is
whenever $t_{j}$ cannot execute, while some other task
not only can, but is. (As a consequence, it is not
considered queuing when \emph{all} tasks are inactive,
as is the case during a global scheduling interrupt.)
There are two (or three) situations when $t_{j}$ can
be queued, which makes up for a total queuing delay
formula of:

\beq{\queuing}{queuing}

\subsubsection{$z$, the response time in global periods}

The worst-case (largest) number of global periods that
can transpire during the existence of a task is,
without rounding:

\beq{\zperiods}{periods}

\subsubsection{$Q^{g}_{j}$, group deadline queuing}

Here, $t_{j}$ is queuing because it has a less
immediate deadline than another task in the same group
-- a task that belongs to the same scheduler as
$t_{j}$.

Note that just about any task can have $t_{j}$
preempted and/or queued at some point: a higher
priority is equivalent to a more immediate
\emph{absolute} deadline. This is a dynamic property
that does not imply $D_{i} \le D_{j}$ for a higher
priority task $t_{i}$: if $t_{i}$ was released before
$t_{j}$, the absolute deadline of $t_{i}$ may still be
more immediate than that of $t_{j}$. The set
$hp(t_{j})$ is all tasks that at some point can
have a higher priority than $t_{j}$.

The worst-case system queuing is:

\beq{\groupqueuing}{group\_queuing}

\textbf{Note: } $hp(t_{j})$ is effectually \emph{all}
tasks except for $t_{j}$ itself! Because of that, this
schedulability method is reduced to that of a
fixed-priority system, only worse, as here, all tasks
would have equal priority. While there exist methods
to compute the response time for individual tasks
under EDF, those are complicated and typically not
worth the effort as long as the purpose is to compute
general schedulability. Still, the formulas here are
included to illuminate the mechanics of this
implementation.

\subsubsection{$Q^{s}_{j}$, cross-group (system) deadline queuing}

The task $t_{j}$ of the scheduler $s_{i}$ can be
delayed by a higher-priority task that belongs to
another scheduler. In the worst case, \emph{all} other
schedulers will spend \emph{all} of their budgets
before $t_{j}$ can execute:

\beq{\systemqueuing}{system\_queuing}

\subsubsection{depletion queuing}

During depletion queuing, $t_{j}$ cannot execute
because its scheduler $s_{i}$ has depleted its
CPU-budget. Fortunately, the worst-case time $t_{j}$
can be delayed for this reason is already included in
$Q^{s}_{j}$.

\subsubsection{$o_{j}$, the scheduling overhead}

The worst-case time required to do a single execution
of global scheduling is denoted $o$ (just $o$, without
an index). It is the the scheduling overhead.

As the top-scheduler controls all of the
task-schedulers, $o$ includes task-scheduling overhead
as well.

$o_{j}$ is the worst-case scheduling overhead during a
single execution of any one instance of $t_{j}$.

Because scheduling occurs once every global tick ($r$),
the worst-case delay is:

\beq{\schedulingoverhead}{schedulability\_overhead}

\subsection{$i_{j}$, interference from the best-effort
  core}

Interference from the best-effort core is due to
best-effort core software contention for the shared
DRAM and the shared memory bus.

For each period $p$, with respect to the critical
tasks of scheduler $s_{i}$, the worst-case number of
memory accesses that can arise from the best-effort
core is bounded by $m_{i}$.

The worst-case interference for any task is a
situation in which the best-effort core makes
\emph{all} its allowed memory accesses during the
employment of that task, for \emph{all} global periods
during which that task instance exists.

The assumption is that during a best-effort memory
fetch, the critical core task cannot do anything, but
idles. (This assumption is probably very pessimistic.)

\label{timed-memory-access}
If the worst-case response time for a DRAM access (for
either core) is 58.5 nanoseconds \cite{hyoseung}, then
the worst-case memory interference from the
best-effort core is:

\beq{\interference}{interference}

\section{Schedulability method: resource server}

Another method to guarantee schedulability is to consider
an individual task-scheduler a
\emph{resource server}. The resource provided is
CPU-time; it is consumed by the tasks that belong to
that particular scheduler.

This method involves less advanced computation than
the response-time method, because here, there is not
any reliance on the dynamic set of tasks with higher
priorities than the task whose response time is
calculated. (Another implementation of this idea is
described in \cite[pp. 301-324]{baruah}. There, only
one processor is considered, and the notation is
different.)

This method relies on two functions: a \emph{supply}
bound function, \texttt{sbf}, and a \emph{demand}
bound function, \texttt{dbf}.

Both functions have two parameters. $\Delta\theta$ is
the same for both: it is the length of the time
interval for which supply or demand is computed. This
interval can occur anywhere in time, and during that
interval the system executing can be in any sound
state.

The other parameter, for \texttt{sbf} and
\texttt{dbf}, are the supplier and demander
themselves, respectively. If the functions are used to
compare supply and demand, they must be used
pair-wise: if $s_{i}$ is the argument to \texttt{sbf},
$P_{i}$ is the argument to \texttt{dbf}. Indeed, the
tasks of $P_{i}$ are the only tasks that can demand
CPU-time supplied by $s_{i}$.

$sbf(\Delta\theta, s_{i})$ is the \emph{minimum}
possible CPU-time supplied by $s_{i}$ during any time
period of length $\Delta\theta$.

Correspondingly, $sbf(\Delta\theta, s_{i})$ is the
\emph{maximum} possible CPU-time demanded.

The worst-case scenario is: the maximum possibly
demanded vs. the minimum possibly supplied.

For any task-scheduler, schedulability is guaranteed
if the maximum demand for any particular interval is
below or equal to the minimum supply for all interval
of the same length.

The system is schedulable if all task-schedulers are.

\clearpage
\subsection{interval length}

If the interval starts at $\theta_{1}$ and ends at
$\theta_{2}$ the length of the interval is:

\beq{\interval}{interval}

\subsection{\texttt{sbf}}

During each complete global period $p$, the
task-scheduler $s_{i}$ supplies exactly $b_{i}$ of
CPU-time for its tasks.

The number of complete periods is:

\beq{\supplycompleteperiods}{supply\_complete\_periods}

The CPU-time supplied by $s_{i}$ for those periods is:

\beq{\supplytimecompleteperiods}{supply\_time\_complete\_periods}

Moreover, there can be zero, one or two incomplete
periods that are part of the interval. If so, they
exist before and/or after the consecutive $w$ complete
periods.

The incomplete periods have the total length:

\beq{\supplylengthincompleteperiods}{supply\_length\_incomplete\_periods}

The worst case, when the task-scheduler supplies the
least, is when there are two incomplete periods of the
same length. Then, it is the most likely that the
task-scheduler supplies all of its CPU-budgets, both
times, during the stretches of the incomplete periods
that are outside the interval.

Both time spans that belong to incomplete periods
outside of the interval has length:

\beq{\supplylengthincompleteoutside}{supply\_length\_incomplete\_outside}

If $U$ is longer than $b_{i}$, the minimum supply case
for $s_{i}$ is when all of $b_{i}$ is supplied during
$U$. However, if $b_{i}$ exceeds $U$, the part of
$b_{i}$ that exceeds $U$ is supplied:

\beq{\supplyincompleteperiods}{supply\_incomplete\_periods}

However, because of the best-effort core interference,
the actual CPU-time supplied is less.

As seen, there are $w$ complete periods in each
interval. In addition, there can be two more periods
that are incomplete: one at each side of the
consecutive, complete periods. In all, there can be a
maximum of $(w + 2)$ periods. The task-scheduler
$s_{i}$ allows $m_{i}$ best-effort core LLC misses for
each period, and for the entire interval:
$(w + 2)m_{i}$. If the data and assumptions in
\spref{timed-memory-access} are reused, the total
supply reduction is:

\beq{\supplyreduction}{supply\_reduction}

All in all, the minimum supply from $s_{i}$ to all
tasks $t \in P_{i}$ is:

\beq{\supply}{supply}

\clearpage
\subsection{\texttt{dbf}}

The number of complete periods of $t_{j}$ that exists
within the interval is:

\beq{\demandcompleteperiods}{demand\_complete\_periods}

Once the complete periods have been accounted for, it
is possible that an incomplete period remains, during
which $t_{j}$ can demand CPU-time. However, it cannot
request more than either the computation time of the
task, or the entire incomplete period:

\beq{\demandincompleteperiod}{demand\_incomplete\_period}

Note that this is the opposite to the supply function.
There, what is desired is the minimum supply possible,
so the spill-over global period is divided into two.
Here, the aim is maximum demand so it is assumed the
spill-over task period is not spread over two periods.

The maximum demand made by the task is:

\beq{\demandtask}{demand\_task}

The maximum demand made by $P_{i}$ is the sum of the
demands made by all $t \in P_{i}$:

\beq{\demandgroup}{demand\_group}

\section{Experiments}

This project carries out several experiments. But
there can be many other experiments as well, that are
not necessarily less interesting. Because of a
building-block approach, it is quick to set up and
execute an experiment. Even most data is collected
automatically. Rather, the challenge is to grasp the
meaning of certain combinations, as well as to
correctly analyze the results.

\subsection{building blocks}

All experiments involve the same technology and the
same tools, but they are employed in different
combinations, and with different parameter values.

The building blocks are:

\begin{itemize}
  \item \texttt{hs} is the hierarchical scheduler. It
    is specifically developed for this project.
    \texttt{hs} can be invoked in different ways.
    Apart from executing task systems, \texttt{hs} can
    also output the global tick trace, which can be
    included in an experiment, if desired.

  \item \texttt{taskset(1)} is used to isolate a
    process to a specific hardware CPU, or core. How
    to isolate a core from most other processes is
    described in \spref{grub}.

  \item \texttt{stress(1)} is used to generate memory
    traffic. It can be used on any and all cores. For
    most experiments, \texttt{stress} is used to
    simulate interfering software: on the best-effort
    core, \texttt{stress} is used to simulate
    arbitrary non-critical software.

    On the critical core, \texttt{stress} is used
    simulate processor and memory usage of the
    software that would be executed by the tasks that
    are scheduled by \texttt{hs}. Unless \texttt{hs}
    is told to fork processes, the tasks that
    \texttt{hs} schedules do not utilize computer
    resources to the extent that real software would.

    \textbf{Note:} While \texttt{stress} can be made
    to behave virtually like any piece of software or
    software set -- and this makes it useful in
    simulations -- it is just as easy to run ordinary
    Linux software, on either core, to attain natural
    contention for computer resources. Simulation may
    be useful to create certain scenarios, that would
    otherwise require extensive setups of ordinary
    software, but most scenarios are just as easily
    attained without simulation. What to do depends on
    the nature of the experient: \texttt{stress} can
    be used to show that something actually can
    happen, under rare-but-possible conditions. On the
    other hand, ordinary software can be used to
    produce a realistic setting, say when the aim of
    the experiment is to illustrate every-day system
    use.

    \label{stress-warning}
    \textbf{Warning:} \texttt{stress} does not behave
    like a normal piece of software. Instead,
    \texttt{stress} can be made to congest the entire
    memory, at what point the computer is
    nonresponsive. After all memory has been
    congested, it is not enough to kill the
    \texttt{stress} processes to remedy the situation.
    While the memory is thus released, any running
    application still needs to reassert its footprint
    before it can resume proper work and respond to
    user IO. This usually takes a couple of seconds
    for the application immediately grasped for -- but
    for dormant processes, the effect can remain
    hidden, and appear unexpectedly. This makes
    \texttt{stress} even less reliable to use in
    experiments as the memory state of one experiment
    instance can linger on to affect other, where
    perhaps \texttt{stress} is not even used.

  \item \texttt{perf\_event\_open} is used to measure
    the memory usage. It does so by booking LLC
    misses, as they imply DRAM fetches and memory-bus
    traffic. \texttt{perf\_event\_open} can be used on
    a single process, on a set of processes, or on any
    and all cores, collectively. If need be, there can
    be parallel instances with different focus. Here,
    \texttt{perf\_event\_open} is used by \texttt{hs}
    so that at the end of its execution it outputs the
    total number of memory accesses that stem from the
    best-effort core.

  \item \texttt{perf\_event\_open} is also the way
    that \texttt{hs} monitors the best-effort core, to
    decide weather the software that runs there is
    supposed to be freezed, thawed, or left alone. If
    \texttt{hs} decides to change the status of the
    best-effort core, this is effectuated by means of
    a Linux \texttt{cgroup}: such a group must be
    initialized before \texttt{hs} is run.

  \item To measure the execution time of a process,
    \texttt{time(1)} is used. This tool can be used to
    measure performance downgrade by clocking the
    completion time of identical commands, only in
    different setups.

\end{itemize}

There is some material appended to this document --
\spref{code} -- to facilitate interaction with not
only \texttt{hs} but the associated tools and entities
(including the best-effort core) as well as the setup
and execution of experiments.

\subsection{design}

An experiment can be anything that employs \texttt{hs}
with a task system and any combination of the
mentioned tools. This checklist how to arrange and
execute an experiment should cover most cases:

\begin{enumerate}
\item the setup: what happens on the best-effort core,
  and what happens on the critical core (except for
  \texttt{hs}), while the experiment runs

\item the \texttt{hs} task system

\item a time-interval how long the experiment will run
  -- recall that a \texttt{hs} system has a lifetime
  parameter, which can fill this purpose

\item what processes are investigated with
  \texttt{time} and \texttt{perf\_event\_open}

\item the experiment should also have a verbalized
  rationale -- ``we do this because...''
  (implementation details of an experiment can
  contradict the purpose of the experiment: if deemed
  acceptable still, the problem should be mentioned as
  well as what is exciting about the experiment)

\item results (after the experiment is done)

\item a possible post-processing of the results by
  some number-crunching tool

\item conclusion
\end{enumerate}

\subsection{zsh wrappers}

To manage the experiments, and make sure they stay the
same for different input values (e.g., task systems),
zsh functions are used to wrap the specific commands
that make up the experiments.

This method is one of clearly defined functions which
are reproducible, highly automatized, and easily
re-executed after say a change to the involved
software.

There is one function for each experiment. Such a
function can, for example, execute several input task
systems, while booking their results, and later
comparing them.

The experiment functions: \spref{functions}

\section{Contention experiment}

\label{contention-experiment}
\index{contention experiment}

zsh function: \texttt{run-contention-experiment} \spref{functions}

This experiment attempts to show that processing, even
though separated on different cores, still affects,
and is affected by, simultaneous processing.

\subsection{setup}

The experiment consists of compiling some 50 Elisp
files on the critical core, in order to measure how
long it takes to complete compilation for different
setups. The changes involve the critical core as well
as the best-effort core.

In parallel with compilation, \texttt{hs} runs,
likewise exclusively on the critical core. The purpose
of the compilation is to simulate the memory accesses
and the CPU strain that the task software of
\texttt{hs} would produce, if indeed they carried real
software and not mock-offs.

On the best-effort core, for certain setups of this
experiment, \texttt{mplayer2(1)} runs: whenever so, it
displays a three gigabyte mp4 file. To display such a
file on the experiment computer is deemed expensive,
but not excessively or unrealistically so.

In addition, \texttt{stress(1)} sometimes run on the
critical core to simulate the resource demand and
consumption of would-be critical software.

The results are, in nanoseconds:

\verbatiminput{/home/incal/public_html/hs-linux/results/cr.log}

\subsection{conclusion}

Intuitively, the more contention, the more time is
needed to complete the compilation. Contrary to this,
in this experiment, neither \texttt{hs} nor the media
player influence the speed of the parallel compilation
process.

\section{Best-effort core memory experiment}

\label{memory-experiment}
\index{memory experiment}

zsh function: \texttt{run-memory-experiment} \spref{functions}

The contention experiment shows that the critical core
is affected by best-effort core activity:
\spref{contention-experiment} Now, the intention is
to show that influence goes both ways: in particular,
how the memory budgets of task systems affect the
best-effort core whenever \texttt{hs} is instructed
to, whenever appropriate, either freeze or thaw it.

The influence is quantified as the number of memory
accesses that originates from the best-effort core
during executions of task systems with different
memory budgets. The best-effort core executes the
media player.

Here, \texttt{hs} is invoked with
\texttt{--memory-budget-add}, which add its argument
to all memory budgets. Thus, the same system is is
executed repeatedly, only with different
memory-budgets. At termination, the number of
best-effort core memory accesses are output.

\subsection{the importance of this experiment: delays
  and overheads}

This project describes a problem, and looking at the
big picture, the implementation attempts to solve it
by controlling the number of best-effort core memory
accesses. The degree of success is possible to
quantify by executing this very experiment. Likewise,
later on, the experiment in \spref{audio-experiment}
will quantify the ``small picture'' success, which
directly relates to the real-time deadlines of the
involved tasks.

In this experiment, the interpretation of the result
is: if $x$ best-effort core memory accesses are
allowed for an execution of \texttt{hs}, and $y$ are
those actually performed, then the difference $y - x$
should be as close to zero as possible (and not less
than zero, for a busy system).

\label{black-list}
A perfect execution, where $x = y$, is unrealistic for
several reasons, some of which appear at every global
tick:

\begin{itemize}

\item the \texttt{hs} C++ scheduling and freeze/thaw
  overhead

\item the \texttt{hs} inexact tick, discussed in
  \spref{clocks}

\item the PMC data fetch overhead

\item the polled EDF, discussed in \spref{poll}, and
  otherwise the userspace implementation, notably the
  signal control of forked processes

\end{itemize}

In addition, some unpredictable factors appear at most
once for every task scheduler and global period:

\begin{itemize}

\item cgroup freezing and thawing overhead (an
  experiment indicates that this overhead is all but
  nonexistent)

\end{itemize}

While all those factors do reduce the quality of the
outcome, their respective weights are at this point
uncertain, as is weather they actually do influence
enough to qualify as scapegoats, should the experiment
outcome be unsatisfactory.

\subsection{systems}

The experiment includes two systems. One has a single
task scheduler; the other has two. The reason to do
the experiment twice is to see if the fallout is
responsive to setup details, in what case the
causality should be further explored. Both systems
have full budgets, with implicit deadlines ($D_{i} =
T_{i}$) for all tasks, and less than full utilization:

\begin{center}
  \vspace{1.5\baselineskip}
  $U_{T} = \sum\limits_{t_{i} \in T}\frac{C_{i}}{T_{i}} \leq 1$
\end{center}

The experiment results are showed below in two
figures; also, in \spref{memory-experiment-fallout}
are the complete tables of data from which the figures
are generated.

\subsubsection{one-scheduler system:
  \texttt{base-faculty-1}}

System:

\verbatiminput{/home/incal/public_html/hs-linux/sys/base-faculty-1}

Fallout:

\begin{center}
  \includegraphics[width=\textwidth]{pics/plot/1.png}
\end{center}

\subsubsection{two-scheduler system:
  \texttt{base-faculty-2}}

System:

\verbatiminput{/home/incal/public_html/hs-linux/sys/base-faculty-2}

Fallout:

\begin{center}
  \includegraphics[width=\textwidth]{pics/plot/2.png}
\end{center}

\clearpage
\subsection{conclusion}

The correspondence between memory budgets and
best-effort core memory accesses should be: the bigger
the budgets, the more accesses -- up and until where
budgets are not depleted because the best-effort core
software does not generate that much memory traffic.
(What is beyond that point is not included in the
above plots.) The linear tendency in both plots shows
that in general, memory throttling works as expected.
However, the high error percentages are discouraging.
In a real-time system, the specific, worst case has to
be considered, not the general tendency.

\section{\texttt{hs} task systems experiment}

\label{task-system-experiment}
\index{task system experiment}

zsh function: \texttt{run-task-system-experiment} \spref{functions}

All instances of this experiment are of the same form.
Only one input parameter differs: the \texttt{hs} task
system. Everything else is the same to facilitate
comparisons of the fallout data: if the setup does not
change, different results are a consequence of
different task systems.

\subsection{setup}

On the critical core, \texttt{hs} runs, as well as the
Elisp compilation, which is also timed. On the
best-effort core, the media player runs

What is different from the first experiment is the
behavior of \texttt{hs}: it will now freeze, and thaw,
the best-effort core. What happens is a function of
how many memory fetches the best-effort core produces,
as well as the dynamic state of the \texttt{hs} task
system.

The only way to affect the results is thus to change
the parameter values of the task system -- and those
of the scheduler itself (those parameters are in the
same task system file).

\begin{sloppypar}
  The method is to execute several task systems, with
  widely different parameter values at key points, and
  then examine if and how that affects the outcome. To
  this end, each system is given a personality name
  which describes what property is emphasized: e.g.,
  one system is called \texttt{short\_rate}, another
  \texttt{small\_memory\_budgets}, and so on. There
  can be many such personalities and combinations
  thereof: only a small subset is tested here.
\end{sloppypar}

Because there are so many parameters, it is a
challenge to assign neutral values that will not affect
the outcome and thus neither morph or hide the part of
the outcome that is a consequence of the spelled-out
personality. To circumvent this problem, the systems
have identical values except for their defining
traits.

\subsection{what is a task system?}

A task system contains parameter values for each task,
according to the sporadic task model: for each task
there is a WCET, a deadline, and a
minimum-interarrival time, or period, as described in
\spref{sporadic-task-model}. But there is more than
tasks to a task system. The system definition also
specifies the parameters values for each task
\emph{scheduler}, or critical group: e.g., the memory
budget that \texttt{hs} uses to freeze and thaw the
best-effort core. Also, a system definition contains
parameter values of the top-most scheduler: e.g., the
scheduling rate and the total system lifetime. So
technically, a more exact phrasing would be a
multicore task/scheduler system. Here, ``task system''
is used for simplicity.

An example task system can be found in
\spref{example-hs-task-system}.

\subsection{simulation issues}

This experiment is the first step toward an experiment
that is more realistic, and less simulated. Although
there is still heavy reliance on simulation,
simulation is implemented as well-defined puzzle
pieces with clear purposes. The thought is that they
can be easily replaced, one by one, further down the
line.

The issues are:

\begin{itemize}

  \item \texttt{hs} does real scheduling, only what
    it schedules is not real software in the sense
    that it actually does anything useful (it
    \emph{can} be hard-coded to do useful things, but
    as for now it is not).

  \item Although the compilation is an example of
    real, useful software in execution, it actually
    simulates all the instances of would-be
    critical-task software.

  \item The best-effort interference is measured in
    terms of how much it can delay the critical-core
    Elisp compilation, even though \texttt{hs} is in
    control of the best-effort software. That is,
    interference is not measured in terms of the
    real-time parameters -- the deadlines -- that
    belongs to the \texttt{hs} tasks.

\end{itemize}

\subsection{the result data}

After the completion of an instance of this
experiment, there are four newly created files which
contain all parts of the result. Those files are in a
directory that bears the same name as the executed
task system.

\begin{minipage}{\textwidth}

  The result is organized like this:

  \begin{longtable}{p{0.33\linewidth}p{0.67\linewidth}}
    file name & description \\ \hline \\

    \texttt{hs\_output.log} & The \texttt{hs} run: all
    the task state changes, as well as any task
    software output. It is the execution trace of the
    task system as scheduled, and executed, by
    \texttt{hs}. Also, this file contains the number
    of best-effort core memory accesses during the
    system run. \\\\

    \texttt{lisp.log} & The time required to compile
    the Elisp source files. \\\\

    \texttt{tick\_times.log} & The time readings in
    nanoseconds for every global tick. Details and
    examples are in \spref{clocks}. \\\\

    \texttt{stats.log} & This file contains the offset
    from the specified global tick rate, for every
    tick. It is computed of the
    \texttt{tick\_times.log} file; likewise, it is
    discussed elsewhere.
  \end{longtable}

  There are also the files \texttt{stats.txt} and
  \texttt{BE.txt} that are convenience parsings of
  data already available in the above files.

\end{minipage}

\subsection{systems and results}

The first system is \texttt{base}. It is a basic
system that the other systems model, save for some
characteristic trait changed. The purpose is to
examine how any step away from \texttt{base} makes --
or does not make -- its way into the result data, and
then analyze how this comes to happen.

\subsubsection{\texttt{base}}

\begin{itemize}

\item The system:

  \verbatiminput{/home/incal/public_html/hs-linux/sys/base}

\item Lisp compilation time, in nanoseconds:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base/lisp.log}

\item Tick stats:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base/stats.txt}

\item Best-effort core memory accesses:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base/BE.txt}

\end{itemize}

\subsubsection{\texttt{long-ticks}}

The \texttt{long-ticks} system has a much slower
global scheduling rate than the \texttt{base} system.
This affects presumably all aspects of any system
execution because it is only at the scheduling
interrupts that one task can be replaced by another as
the one executed by the CPU; moreover, it is only at
the scheduling interrupts that \texttt{hs} freezes or
thaws the best-effort core.

\begin{itemize}

\item The system:

  \verbatiminput{/home/incal/public_html/hs-linux/sys/long-ticks}

\item Lisp compilation time, in nanoseconds:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-ticks/lisp.log}

\item Tick stats:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-ticks/stats.txt}

\item Best-effort core memory accesses:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-ticks/BE.txt}

\end{itemize}

\subsubsection{\texttt{long-period}}

The \texttt{long-period} system has a much longer
global period than the \texttt{base} system.

\begin{itemize}

\item The system:

  \verbatiminput{/home/incal/public_html/hs-linux/sys/long-period}

\item Lisp compilation time, in nanoseconds:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-period/lisp.log}

\item Tick stats:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-period/stats.txt}

\item Best-effort core LLC misses:

  \verbatiminput{/home/incal/public_html/hs-linux/results/long-period/BE.txt}

\end{itemize}

\subsection{conclusion}

The different outcomes of this experiment show that
interference from the best-effort core can be
throttled as a function of the memory access profile
of the best-effort core software in combination with
what happens on the critical core, down to the
individual task that is currently executed.

\section{Linux processes experiment}

zsh function: \texttt{run-linux-process-experiment} \spref{functions}

This experiment is similar to the previous one --
\spref{task-system-experiment} -- with the huge
exception that \texttt{hs} does not run mock software
anymore, instead, it spawns and schedules ordinary
Linux processes.

The purpose of the experiment is to show that real
software is as much susceptible to interference as the
software measured in the previous simulation.

At best, the previously used hard-coded task software
provides a simulation of an actual system. Here, that
is replaced by Linux processes. The processes are
scheduled exactly like the task software, only -- were
it fits -- the processes are suspended and resumed
from \texttt{hs}, by means of \texttt{kill(2)}
signals. Those are sent on the basis of process group
IDs (PGIDs), so that processes spawned down the ladder
will be controlled by \texttt{hs} as well.

\subsection{advantages}

\begin{itemize}

\item Because real software is being executed it puts
  a definite end to everything simulated or artificial
  about this project.

\item Because the processes are now separated from
  \texttt{hs}, they can be monitored individually,
  isolated from each other as well as from
  \texttt{hs}. Recall that in the previous experiment,
  there was a compilation process that run in parallel
  with \texttt{hs}. The slowdown in compilation due to
  interference from the best-effort core was a measure
  of how, collectively, critical-core software was
  affected. Here, with real processes, the processes
  are not representing anything but themselves, so any
  slowdown detected (for whatever reason) is actual
  slowdown and no mere indication of such a tendency.

\item Because the processes are ordinary Linux
  processes, when they are resumed (after being
  suspended), they take on where they were preempted.
  That means total execution wall-clock time will not
  only be prolonged by the the best-effort core
  interference, it will to a much higher degree depend
  on the associated real-time parameters of the
  software, because those determine how \texttt{hs}
  will schedule the processes.

\end{itemize}

\subsection{disadvantages}

\begin{itemize}

\item If a system employs lengthy background
  processes, but still is desired to be highly
  responsive with frequent context switches, the task
  parameters of the sporadic task model must be
  reinterpreted. The $C$ parameter for WCET, as well
  as the other parameters, no longer express times for
  an entire process, but rather the burst patterns in
  which it will execute until completion. It can be
  thought of as a version of the multiframe model
  \cite[pp. 635-645]{multiframe}; however, it does not
  come with fixed frames in terms of exactly what part
  of the software is being executed. (Actually, a
  hard-framed model would be easy to implement with
  the hard-coded task software: a static C++ variable
  -- as in persistent, not class -- to hold the
  current frame, and then a branch is all it
  takes.)

\item Although slowdown is measured with actual
  software -- not some representation thereof --
  slowdown is not measured in terms of the real-time
  parameters associated with the software. This
  further contrasts with the sporadic task model, in
  which everything is fine as long as all tasks
  complete before their deadlines. Even if deadlines
  are reinterpreted as bounds of bursts of processes
  in execution, this experiment still does not examine
  how the context in which processes execute either
  fails to interfere enough, or actually breaks task
  deadlines.

\end{itemize}

\subsection{systems and results}

\subsubsection{\texttt{base-p}}

The \texttt{base-p} system consists of real Linux
processes. One is an infinite loop outputting a
string; the other compiles the by now familiar Elisp
files. However, compilation in this experiment is not
equivalent to what happened in the previous
experiment, with the \texttt{base} system -- then,
there was a compilation process that ran
interwovenly with \texttt{hs} on the critical
core; here, compilation is
critical software that \texttt{hs} schedules.
Thus, the compilation process is subject to its
sporadic task representation and the values it holds.
The by far biggest consequence of this is that the
result data cannot be interpreted in terms of
interference alone, although interference has not
decreased. Rather, a much bigger factor is competition
on \texttt{hs} from other critical tasks, and the task
parameter values of the process itself.

The result for \texttt{base-p}:

\begin{itemize}

\item The system:

  \verbatiminput{ /home/incal/public_html/hs-linux/sys/base-p }

\item Lisp compilation time, in nanoseconds:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p/lisp.log}

\item Tick stats:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p/stats.txt}

\item Best-effort core LLC misses:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p/BE.txt}

\end{itemize}

\subsubsection{\texttt{base-p-no-memory-budget}}

These are the results for an identical system, besides
having a virtually nonexistent memory budget.

\begin{itemize}

\item The system:

  \verbatiminput{/home/incal/public_html/hs-linux/sys/base-p-no-memory-budget}

\item Lisp compilation time, in nanoseconds:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p-no-memory-budget/lisp.log}

\item Tick stats:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p-no-memory-budget/stats.txt}

\item Best-effort core LLC misses:

  \verbatiminput{/home/incal/public_html/hs-linux/results/base-p-no-memory-budget/BE.txt}

\end{itemize}

\subsection{conclusion}

While the results of this experiment do enlighten the
inefficiency of the method, equally revealing was the
process of setting up the experiment.

The sporadic task model is not suited for continuous
processes. In order to have an interactive system, the
computation times (the WCET parameter values) must be
small. On the other hand, the deadlines cannot be too
tight less you risk having delayed processes (or
delayed parts of processes). Yet, on the third hand,
if deadlines are wide, so are periods, which means the
processes will not get back to action right away but
must idle until the period ends. This is sometimes
acceptable, even welcome, as long as other processes
can execute to fill the gap; if not, it is a waste of
resources.

Also, remember that the task model parameters are not
alone in defining a system: there are also the global
scheduler parameters, and those of every task
schedulers. All in all, it is a jungle just to execute
a program and have it complete within a reasonable
amount of time.

For this reason, there are only two systems included
in this experiment, to show the mechanics.

Of course, there is no ruling out that a system
implemented this way could be functional, but that
would have to involve experimentation and evaluation
as to what to assign each end every parameter. And
that is not a good idea: the parameters should reflect
reality, or at the least intuition, and pretty much
instantly so -- they are not to be tweaked just so a
simple program can be executed.

\section{Real real-time: audio experiment}

\label{audio-experiment}
\index{audio experiment}

zsh function: \texttt{run-audio-experiment} \spref{functions}

This experiments puts it all together. Just like the
previous experiment, it uses real software:
\texttt{hs} schedules Linux processes.

But unlike the previous experiment, all tasks are
expected to terminate within their deadline frames, as
expressed by their sporadic task representations.

This time, nothing is measured. Instead, everything is
done in terms of the real-time task system, and the
associated software.

Furthermore, the process that is examined executes
software that measures an external, physical property:
the sound level. This is measured with a microphone
plugged into the computer. (To make the system even
more interesting, it can be augmented with all sorts
of gadgets: an USB thermometer, for starters.)

The audio process executes a script that logs the
sound level by appending it to a file:

\verbatiminput{/home/incal/scripts/a-level}

As seen, that script is not optimized but uses a
combination of commonly-used utilities.

The script is a server: it idles until it receives an
\texttt{USR1} signal, which triggers the function that
reads and stores the sound level. This scheme makes it
unnecessary to create a new process for every instance
released.

The rationale of this experiment is that if realistic
real-time parameter values are assigned the sporadic
task representation of the process that executes the
audio script, then this system can be asserted not in
terms of increased memory/CPU contention, but instead:
failure is whenever the absolute deadline of the audio
task is in the past, while the task still has not
booked the audio level.

If such a failure is deducted to be the result of
best-effort core memory contention, it will be
attempted to nullify that influence in an execution
run where \texttt{hs} throttles the best-effort core.
If this changes the outcome, then it has been showed
that this project assesses a real problem that it is
able to solve as well.

\subsection{system}

The strategy is to create a system that for a
virtually unloaded computer will execute successfully:
it will not suffer a single deadline miss. However,
the margin of error should be the slimmest possible.

That way, if the same system thereafter executes in
parallel with best-effort core activity, the scale
will tip and interference will be detectable in the
form of missed deadlines.

The third step is to execute the system anew, again
along with interference, only this time with
throttling enabled, and examine if that counteracts
the interference, and has the system execute
successfully once again, just as if the interference
had not been there.

The system is:

\verbatiminput{/home/incal/public_html/hs-linux/sys/base-audio-2}

\subsection{execution}

In order to understand in what way a system is
executed and how it is influenced by activity on the
best-effort core, a framework of \texttt{tmux(1)}
panes is used. The screenshot below shows this -- only
the colors have been inverted, to facilitate reading
on paper.

In the comic-book reading-order -- left-to-right and
top-to-bottom -- the panes are:

\begin{itemize}

\item The IO of \texttt{hs}, and that which
  \texttt{hs} schedules (be it the hard-coded
  task-software or, as here, Linux processes).

\item The best-effort core policy: \texttt{no BE}
  means there is not any activity on the best-effort
  core; \texttt{tamed BE} means there is activity on
  the best-effort core but \texttt{hs} is instructed
  to throttle it; and, \texttt{wild BE} means that
  there is activity on the best-effort core, but it is
  never throttled.

  The parenthesis next to the best-effort core policy
  shows the system execution number. In order not to
  interpretate uncommon events as recurring, it is
  beneficial to execute the same system several times,
  under the same circumstances.

\item The next pane shows the state of the best-effort
  core: \texttt{FROZEN}, or \texttt{THAWED}. Here, a
  couple of PIDs are sometimes shown: those are the
  PIDs of the processes that are frozen, whenever the
  best-effort core is. There is only room to show
  three PIDs: if there are more processes on the
  best-effort core, they are treated the same as those
  of the PIDs mentioned.

\item The number of signals sent to the audio task
  during the \texttt{no BE} run(s). If there are
  several iterations this number is the sum of all
  signals sent during past executions plus the
  current, so far.

\item The number of outputted audio levels during the
  \texttt{no BE} phase, so far.

\item Ditto \texttt{tamed BE} (two consecutive panes).

\item Ditto \texttt{wild BE}.

\item The processes on the best-effort core: the data
  shown is core, PID, and command. ($1$ is the
  best-effort core.)

\end{itemize}

\baimgspace
\begin{center}
  \includegraphics[width=\textwidth]{audio_results_i.png}
\end{center}
\baimgspace

\label{high-frequency-problem}
\index{high-frequency-problem}
\textbf{Note:} In the course of carrying out this
experiment, it was discovered that the global
preemption rate cannot be set too low when scheduling
real processes. If so, presumably, the overhead
handling processes -- interrupting and otherwise
controlling them through signals -- will hinder actual
software execution. All but instantly, that will
result in missed deadlines. This situation can be
remedied without changing any other parameter value
save for the rate, which must be increased.

\subsection{ideal fallout}

A perfect fallout for this experiment would be:

\begin{itemize}

\item For a system that is schedulable, and executed
  without any best-effort core memory contention, the
  aim should be set that if there are $s$ signals
  sent, then there should be $o = s$ audio level
  outputs.

\item Keeping the same system, but adding contention
  at the time of execution (contention which
  nonetheless can be throttled), then if there are
  $s'$ signals, there should still be $o' = s'$
  outputs. The assumption is that the throttling
  mechanism is configured so it can, if necessary, put
  the best-effort core entirely out of business.

\item Keeping the same system and the same (severe)
  contention, only this time with throttling
  disenabled, then the number of outputted audio
  levels $o''$ should be considerable smaller than $o$
  and $o'$.

\end{itemize}

\subsection{conclusion}

This experiment shows that \texttt{hs} can control the
best-effort so that some critical tasks (though very
few) will complete before their deadlines in spite of
best-effort interference, which, without the
\texttt{hs} throttle, would not have been the case.

What is disappointing is the lack of precision. It
appears as though \texttt{hs} can barely remedy a
dysfunctional overall state, while not sophisticated
by far to tweak or improve a functional system with
any granularity to it.

It is telling that if \texttt{stress} is substituted
for a piece of normal software -- e.g., the media
player, which has a small footprint compared to the
entire memory space available -- there are not not any
deadlines misses due to memory contention, or, if
occurring, they are never remedied by throttling.

Another thing disappointing is the amount of deadline
misses even without any interference. A likely reason
is that the audio process has an execution time that
varies too much so that often the WCET do not reflect
reality.

However, it is clear that this experiment fails not
because of shortcomings in \texttt{hs} and/or the
wider architecture, but already due to the inability
to present the critical core with best-effort core
interference that in a realistic and sensible way
affects the performance of the critical-core software.

Nevertheless, it is even more clear that \texttt{hs}
is incapable of stopping \texttt{stress} from breaking
the entire system: because \texttt{hs} is itself
suspectible to best-effort core interference, the
throttling mechanism reverts to a dysfunctional state
along with the rest of the system as all memory
becomes unavailable.

\section{Conclusion}

The implementation process showed that a hierarchical
scheduler is suited to host a mixed criticality
system. Here, critical groups correspond one-to-one to
the task schedulers: because of its very composition,
the hierarchical scheduler provides isolation between
critical groups.

Because a hierarchical scheduler is modular by
definition, and here serves as a system host, it was
desired to use a fast, general-purpose, and
object-oriented langauge. C++ worked well: the
implementation process never ran into any obstacles
that were perceived as insurmountable.

Also, the many tools used in this project, all of them
available on a common Linux system, worked as
intended, and for the most part without complications.
Among the tools and technologies used were the GRUB
configuration to isolate the cores, then
\texttt{taskset} to steer processes to the best-effort
core; moreover, there was a cgroup to control the
best-effort core software; \texttt{perf\_event\_open}
to poll the number of best-effort core LLC misses;
and, \texttt{tmux} and zsh to make an interface to
automatize experiments.

Last, the idea to specify task systems in text files
that were parsed by \texttt{hs} at runtime proved
powerful, not the least in experiments that required
fast employment of different systems. It could all be
accounted for, and automatized.

Regretably, somewhere along the way, the sum of the
project became less than the sum of its parts. While
\texttt{hs} can reduce the number of best-effort core
memory accesses, it fails to do so with sufficient
precision, as is evident by the memory experiment.

At this point, there is not any theory as to what part
of the system is the weakest link of the chain. It is
not even clear if the lack of precision is the
consequence of one or a few such parts, or the overall
architecture, and, if so, at what level(s).

Moreover, there is a worse, even fatal system
exposure, which nonetheless is more satisfying because
the reason is known: because \texttt{hs} is itself
suspectible to best-effort core interference, in face
of massive (but possible) best-effort core memory
traffic, the throttling mechanism -- a part of
\texttt{hs} -- reverts to a dysfunctional state along
with \texttt{hs} and the rest of the system, as all
memory becomes unavailable.

Here, I should be noted that the relative success of
the memory experiment is achieved in the face of
\emph{moderate} best-effort contention -- most likely,
it would not work at all if exposed to the same
interference as the audio experiment.

\textbf{Note:} Some of the experiments that were
carried out in the course of this project are not
mentioned here. The reason is that those experiments,
while not exactly failing, did not offer any key
insights that are not conveyed by
subsequent experiments.

%% references
\renewcommand\bibname{References}
\printbibliography[heading=mybibliography]

\appendix

\renewcommand\thesection{\Alph{section}}
\renewcommand\thesubsection{\thesection.\alph{subsection}}
\renewcommand\thesubsubsection{\thesubsection.\alph{subsubsection}}

\section{Appendix A: Memory experiment fallout}

\label{memory-experiment-fallout}
\index{memory experiment fallout}

\textbf{Note:} If and whenever the tables above are
spotwise incomplete, that is because a failed hard
real-time task system has made \texttt{hs} exit
preemptly, without a result to output.
Correspondingly, the digits actually outputted are all
of systems whose tasks completed before or at their
deadlines, without fail.

\input{/home/incal/public_html/hs-linux/results/memory-experiment-tables.log}

\section{Appendix B: Formulas}

\subsection{system}

$\topscheduler$ where $\relate$

$\taskscheduler$

\subsection{sporadic task model}

$\sporadic$

$\sporadictask$

\subsection{response time}

$\responsetime$

$\zperiods$

$\schedulingoverhead$

$\interference$

\textbf{Queuing:}

$\queuing$

$\groupqueuing$

$\systemqueuing$

\subsection{resource server}

$\interval$

\subsubsection{supply}

$\supplycompleteperiods$

$\supplytimecompleteperiods$

$\supplylengthincompleteperiods$

$\supplylengthincompleteoutside$

$\supplyincompleteperiods$

$\supply$

\subsubsection{demand}

$\demandincompleteperiod$

$\demandtask$

$\demandgroup$

$\demandcompleteperiods$

\section{Appendix C: \texttt{hs} code}

This appendix contains the complete C++ source code
for \texttt{hs} as well as a groff man page which
describes the use of all command-line options.

%% man page for hs
\refstepcounter{subsection}
\addcontentsline{toc}{subsection}{%
  \protect\numberline{\thesubsection}%
  man page for \texttt{hs}}%
\texttt{\thesubsection\ man page for \texttt{hs}}
\lstset{
  basicstyle=\ttfamily,
  columns=fullflexible,
  keepspaces=true,
  showspaces=false,
  showstringspaces=false,
  commentstyle=\ttfamily
}
\lstinputlisting[language=bash]{../hs.txt}
\clearpage

\subsection{\texttt{ask}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/ask.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/ask.cc}

\subsection{\texttt{be}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/be.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/be.cc}

\subsection{\texttt{file\_io}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/file_io.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/file_io.cc}

\subsection{\texttt{global\_scheduler}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/global_scheduler.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/global_scheduler.cc}

\subsection{\texttt{llc}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/llc.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/llc.cc}

\subsection{\texttt{log}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/log.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/log.cc}

\subsection{\texttt{main}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/main.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/main.cc}

\subsection{\texttt{options}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/options.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/options.cc}

\subsection{\texttt{program}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/program.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/program.cc}

\subsection{\texttt{sporadic\_task}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/sporadic_task.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/sporadic_task.cc}

\subsection{\texttt{task\_scheduler}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/task_scheduler.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/task_scheduler.cc}

\subsection{\texttt{tcb}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/tcb.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/tcb.cc}

\subsection{\texttt{time\_io}}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/include/time_io.hh}
\lstinputlisting[language=c++]{/home/incal/public_html/hs-linux/src/time_io.cc}

\section{Appendix D: experiment code and example data}

\label{code}
\index{code}

%% example hs task system
\refstepcounter{subsection}
\addcontentsline{toc}{subsection}{%
  \protect\numberline{\thesubsection}%
  example \texttt{hs} system}%
\texttt{\thesubsection\ example hs task system}
\label{example-hs-task-system}
\index{example hs task system}
\verbatiminput{/home/incal/public_html/hs-linux/sys/base}
\clearpage

%% useful zsh commands
\refstepcounter{subsection}
\addcontentsline{toc}{subsection}{%
  \protect\numberline{\thesubsection}%
  useful zsh commands}%

\texttt{\thesubsection\ useful zsh commands}

\lstinputlisting[language=bash]{/home/incal/.zsh/be-task}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-monitor}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-paths}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-signals}
\clearpage

%% zsh wrapper to run experiments
\refstepcounter{subsection}
\addcontentsline{toc}{subsection}{%
  \protect\numberline{\thesubsection}%
  zsh wrapper to run experiments}%
\texttt{\thesubsection\ zsh wrapper to run experiments}
\label{functions}
\index{functions}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-experiment}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-experiment-setup}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-compile-elisp}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-contention-experiment}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-memory-experiment}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-system-experiment}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-process-experiment}
\lstinputlisting[language=bash]{/home/incal/.zsh/be-audio-experiment}
\clearpage

%% Elisp to crunch tick traces
\refstepcounter{subsection}
\addcontentsline{toc}{subsection}{%
  \protect\numberline{\thesubsection}%
  tick trace cruncher in Elisp}%
\texttt{\thesubsection\ tick trace cruncher in Elisp}
\lstinputlisting{/home/incal/public_html/hs-linux/src/times.el}

%% index
\refstepcounter{section}
\addcontentsline{toc}{section}{%
  \protect\numberline{$\rightarrow$}%
  \indexname}%

\renewcommand\indexname{Index}

\printindex

\end{document}
