Subversion Repositories shark

\documentclass[english]{report}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\geometry{verbose,a4paper}
\usepackage{array}
\usepackage{makeidx}
\makeindex
\usepackage{graphicx}

\makeatletter

\usepackage{babel}

\newenvironment{intest}{\noindent\large\bf\hspace*{1pt}}
{\vspace*{-5pt}\\\line(1,0){433}}

\makeatother

\begin{document}

\thispagestyle{empty}

\begin{center}{\LARGE S.Ha.R.K. User Manual}\end{center}{\LARGE \par} \vfill{}

\begin{center}{\large Volume III}\end{center}

\begin{center}
S.Ha.R.K. Modules
\end{center}
\vfill{}

\begin{center}Written by\end{center}

\begin{center}Giorgio Buttazzo (giorgio at sssup.it)\end{center}
\begin{center}Paolo Gai (pj at sssup.it)\end{center}
\begin{center}Luigi Palopoli (luigi at hartik.sssup.it)\end{center}
\begin{center}Marco Caccamo (caccamo at sssup.it)\end{center}
\begin{center}Giuseppe Lipari (lipari at sssup.it) \end{center}
\begin{center}Tullio Facchinetti (tullio.facchinetti at unipv.it) \end{center}
\vfill{}

\begin{center}\includegraphics[width=2cm]{../common/sssup.ps}\end{center}

\begin{center}
Scuola Superiore di Studi e Perfezionamento S. Anna
\end{center}

\begin{center}RETIS Lab\end{center}
\begin{center}Via Carducci, 40 - 56100 Pisa\end{center}
\pagebreak

\tableofcontents{}

\begin{abstract}
The S.Ha.R.K. kernel provides a way to implement in a simple
way a lot of scheduling algorithms that have been proposed by the
Real-Time literature. This Volume simply contains a simple
description on which modules are available and how these modules
can be used. Moreover, to help the implementation of new modules,
a small description of the tricks used in the implementation is
also given.
\end{abstract}

%----------------------------------------------------------------------------
\chapter{Models}
%----------------------------------------------------------------------------

Task Models and Resource Models are the structures used by the
S.Ha.R.K. Kernel to isolate the scheduling parameter needed by the
various Scheduling Modules and Resource Modules.

To simplify the use of the Models, the Kernel provides a set of
macros that can be used to fill their various fields. In the
following paragraphs, the various models are described in detail.
All the Model definitions of this chapter can be found in the file
\texttt{include/kernel/model.h}.

Examples of Models initializations can be found in various
examples through this Volume.

%----------------------------------------------------------------------------
\section{HARD\_TASK\_MODEL}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    TASK_MODEL t;
    TIME mit;
    TIME drel;
    TIME wcet;
    int periodicity;
} HARD_TASK_MODEL;
\end{verbatim}
\end{tt}

A Hard Task model can be used to model periodic and sporadic
tasks. These tasks are usually guaranteed basing on their minimum
interarrival time (mit) and wcet, and may have a relative
deadline.

Table \ref{tab:HARD_TASK_MODEL_Macros} shows the macros that
applies to a \texttt{HARD\_TASK\_MODEL}.

\begin{table}
\begin{tabular}{|l|p{8cm}|}
\hline Macro name & Behaviour \\ \hline

hard\_task\_default\_model(m) & Default values for the Model
(periodic task, others = 0) \\ \hline

hard\_task\_def\_level(m,l) & Set the Model level to l. A Module
registered at level x can accept a Model only if it has level 0 or
x. The default value is 0. \\ \hline

hard\_task\_def\_arg(m,a) & Set the void * argument passed to
the task the first time it is activated. The default value is
NULL.\\ \hline

hard\_task\_def\_stack(m,s) & Set the task stack size. The default
value is 4096.\\ \hline

hard\_task\_def\_stackaddr(m,s) & If the stack is statically
allocated you can tell its address here. The default is NULL (no
pre-allocated stack).\\ \hline

hard\_task\_def\_group(m,g) & Set the task group to g. Task
grouping influences primitives like group\_activate() or
group\_kill()\\ \hline

hard\_task\_def\_usemath(m) & Declare that the task uses floating
point arithmetic.\\ \hline

hard\_task\_def\_system(m) & Declare that the task is a system
task. System tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

hard\_task\_def\_nokill(m) & Declare that the task can not be
killed. These tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

hard\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
JET informations for the task.\\ \hline

hard\_task\_def\_mit(m,p) & Set the Minimum Interarrival Time
(MIT) of the Model to p.\\ \hline

hard\_task\_def\_drel(m,d) & Set the relative deadline to
d.\\ \hline

hard\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
w.\\ \hline

hard\_task\_def\_periodic(m) & Declare that the task is
Periodic.\\ \hline

hard\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
(Aperiodic).\\ \hline

hard\_task\_def\_joinable(m) & Declare that the task is joinable
with task\_join()/pthread\_join().\\ \hline

hard\_task\_def\_unjoinable(m) & Declare that the task is not
joinable (is detached) with
task\_join()/pthread\_join().\\ \hline

hard\_task\_def\_trace(m) & Declare that the task has to be traced
by the Tracer.\\ \hline

hard\_task\_def\_notrace(m) & Declare that the task has not to be
traced by the Tracer.\\ \hline
\end{tabular}
\caption{HARD\_TASK\_MODEL Macros}
\label{tab:HARD_TASK_MODEL_Macros}
\end{table}

%----------------------------------------------------------------------------
\section{SOFT\_TASK\_MODEL}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    TASK_MODEL t;
    TIME period;
    TIME met;
    TIME wcet;
    int periodicity;
    int arrivals;
} SOFT_TASK_MODEL;
\end{verbatim}
\end{tt}

A Soft Task model can be used to model periodic and aperiodic
tasks usually not guaranteed or guaranteed basing on their period
and mean execution time (met). A Soft task can also record pending
activations if the arrivals are set to SAVE\_ACTIVATIONS. A wcet
field is also present for those servers that need it (i.e., TBS).

Table \ref{tab:SOFT_TASK_MODEL_Macros} shows the macros that
applies to a \texttt{SOFT\_TASK\_MODEL}.

\begin{table}
\begin{tabular}{|l|p{8cm}|}
\hline Macro name & Behaviour\\ \hline

soft\_task\_default\_model(m) & Default values for the Model
(periodic task, save arrivals, others = 0).\\ \hline

soft\_task\_def\_level(m,l) & Set the Model level to l. A Module
registered at level x can accept a Model only if it has level 0 or
x. The default value is 0.\\ \hline

soft\_task\_def\_arg(m,a) & Set the void * argument passed to
the task the first time it is activated. The default value is
NULL.\\ \hline

soft\_task\_def\_stack(m,s) & Set the task stack size. The default
value is 4096.\\ \hline

soft\_task\_def\_stackaddr(m,s) & If the stack is statically
allocated you can tell its address here. The default is NULL (no
pre-allocated stack).\\ \hline

soft\_task\_def\_group(m,g) & Set the task group to g. Task
grouping influences primitives like group\_activate() or
group\_kill()\\ \hline

soft\_task\_def\_usemath(m) & Declare that the task uses floating
point arithmetic.\\ \hline

soft\_task\_def\_system(m) & Declare that the task is a system
task. System tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

soft\_task\_def\_nokill(m) & Declare that the task can not be
killed. These tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

soft\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
JET informations for the task.\\ \hline

soft\_task\_def\_period(m,p) & Set the task period to
p.\\ \hline

soft\_task\_def\_met(m,d) & Set the task Mean Execution Time (MET)
to d.\\ \hline

soft\_task\_def\_wcet(m,w) & Set the Worst Case Execution Time to
w.\\ \hline

soft\_task\_def\_periodic(m) & Declare that the task is
Periodic.\\ \hline

soft\_task\_def\_aperiodic(m) & Declare that the task is Sporadic
(Aperiodic).\\ \hline

soft\_task\_def\_joinable(m) & Declare that the task is joinable
with task\_join()/pthread\_join().\\ \hline

soft\_task\_def\_unjoinable(m) & Declare that the task is not
joinable (is detached) with
task\_join()/pthread\_join().\\ \hline

soft\_task\_def\_trace(m) & Declare that the task has to be traced
by the Tracer.\\ \hline

soft\_task\_def\_notrace(m) & Declare that the task has not to be
traced by the Tracer.\\ \hline

soft\_task\_def\_save\_arrivals(m) & The task will save a pending
activation if it arrives when the task is already
active.\\ \hline

soft\_task\_def\_skip\_arrivals(m) & The task will ignore a
pending activation if it arrives when the task is already
active.\\ \hline
\end{tabular}
\caption{SOFT\_TASK\_MODEL Macros}
\label{tab:SOFT_TASK_MODEL_Macros}
\end{table}

\pagebreak

%----------------------------------------------------------------------------
\section{NRT\_TASK\_MODEL}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    TASK_MODEL t;
    int weight;
    TIME slice;
    int arrivals;
    int policy;
    int inherit;
} NRT_TASK_MODEL;
\end{verbatim}
\end{tt}

A NRT task has a weight and a time slice, plus a policy attribute.
It can be used to model Round Robin, Proportional Share, POSIX,
and Priority tasks.

Note that policy and inherit are inserted in the model to support
POSIX compliant scheduling without adding another Task Model;
weight can be used to contain the fixed priority of a task; slice
can be used to contain the RR slice of the task.

Table \ref{tab:NRT_TASK_MODEL_Macros} shows the macros that
applies to a \texttt{NRT\_TASK\_MODEL}.

\begin{table}
\begin{tabular}{|c|p{8cm}|}
\hline Macro name & Behaviour\\ \hline

nrt\_task\_default\_model(m) & Default values for the Model (save
arrivals, NRT\_RR\_POLICY, NRT\_EXPLICIT\_SCHED, others =
0).\\ \hline

nrt\_task\_def\_level(m,l) & Set the Model level to l. A Module
registered at level x can accept a Model only if it has level 0 or
x. The default value is 0.\\ \hline

nrt\_task\_def\_arg(m,a) & Set the void * argument passed to the
task the first time it is activated. The default value is
NULL.\\ \hline

nrt\_task\_def\_stack(m,s) & Set the task stack size. The default
value is 4096.\\ \hline

nrt\_task\_def\_stackaddr(m,s) & If the stack is statically
allocated you can tell its address here. The default is NULL (no
pre-allocated stack).\\ \hline

nrt\_task\_def\_group(m,g) & Set the task group to g. Task
grouping influences primitives like group\_activate() or
group\_kill()\\ \hline

nrt\_task\_def\_usemath(m) & Declare that the task uses floating
point arithmetic.\\ \hline

nrt\_task\_def\_system(m) & Declare that the task is a system
task. System tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

nrt\_task\_def\_nokill(m) & Declare that the task can not be
killed. These tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

nrt\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
JET informations for the task.\\ \hline

nrt\_task\_def\_weight(m,w) & Set the task weight to
w.\\ \hline

nrt\_task\_def\_slice(m,d) & Set the timeslice to
d.\\ \hline

nrt\_task\_def\_policy(m,p) & Set the policy of the task. p can be
NRT\_RR\_POLICY or NRT\_FIFO\_POLICY. (used for POSIX
scheduling)\\ \hline

nrt\_task\_def\_inherit(m,i) & Tell if the task should inherit the
same properties of the father. i can be NRT\_INHERIT\_SCHED or
NRT\_EXPLICIT\_SCHED. (used for POSIX scheduling)\\
\hline

nrt\_task\_def\_joinable(m) & Declare that the task is joinable
with task\_join()/pthread\_join().\\ \hline

nrt\_task\_def\_unjoinable(m) & Declare that the task is not
joinable (is detached) with
task\_join()/pthread\_join().\\ \hline

nrt\_task\_def\_trace(m) & Declare that the task has to be traced
by the Tracer.\\ \hline

nrt\_task\_def\_notrace(m) & Declare that the task has not to be
traced by the Tracer.\\ \hline

nrt\_task\_def\_save\_arrivals(m) & The task will save a pending
activation if it arrives when the task is already
active.\\ \hline

nrt\_task\_def\_skip\_arrivals(m) & The task will ignore a pending
activation if it arrives when the task is already
active.\\ \hline
\end{tabular}
\caption{NRT\_TASK\_MODEL Macros}
\label{tab:NRT_TASK_MODEL_Macros}
\end{table}

%----------------------------------------------------------------------------
\section{JOB\_TASK\_MODEL}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    TASK_MODEL t;
    TIME period;
    struct timespec deadline;
    int noraiseexc;
} JOB_TASK_MODEL;
\end{verbatim}
\end{tt}

This model implements a Job with an optional period and a starting
deadline (for the first activation). A Job task can raise a
XDEADLINE\_MISS exception; if the flag noraiseexc is != 0, the
exception is not raised.

This model is normally used with aperiodic servers: the aperiodic
server insert a guest task in another level with that model
calling \texttt{guest\_create} and \texttt{guest\_activate}. When
the task has to be removed, \texttt{guest\_end} is called.

Note that there is no capacity control on this model. Note that
the task that accept this task DOESN'T reactivate the task after a
period... There is NOT a guest\_endcycle defined for this model...

Table \ref{tab:JOB_TASK_MODEL_Macros} shows the macros that
applies to a \texttt{JOB\_TASK\_MODEL}.

\begin{table}
\begin{tabular}{|l|p{8cm}|}
\hline Macro name& Behaviour\\ \hline

job\_task\_default\_model(m,dl) & Default values for the Model
(period = 0, deadline = dl, noraiseexc = 0)\\ \hline

job\_task\_def\_level(m,l) & Set the Model level to l. A Module
registered at level x can accept a Model only if it has level 0 or
x. The default value is 0.\\ \hline

job\_task\_def\_arg(m,a) & Set the void * argument passed to the
task the first time it is activated. The default value is
NULL.\\ \hline

job\_task\_def\_stack(m,s) & Set the task stack size. The default
value is 4096.\\ \hline

job\_task\_def\_stackaddr(m,s) & If the stack is statically
allocated you can tell its address here. The default is NULL (no
pre-allocated stack).\\ \hline

job\_task\_def\_group(m,g) & Set the task group to g. Task
grouping influences primitives like group\_activate() or
group\_kill()\\ \hline

job\_task\_def\_usemath(m) & Declare that the task uses floating
point arithmetic.\\ \hline

job\_task\_def\_system(m) & Declare that the task is a system
task. System tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

job\_task\_def\_nokill(m) & Declare that the task can not be
killed. These tasks behaves differently at shutdown. See the
Architecture manual for details.\\ \hline

job\_task\_def\_ctrl\_jet(m) & If called, the Kernel must store
JET informations for the task.\\ \hline

job\_task\_def\_period(m,p) & Set the period to p.\\ \hline

job\_task\_def\_deadline(m,dl) & Set the deadline to
dl.\\ \hline

job\_task\_def\_noexc(m) & Set noraiseexc = 1.\\ \hline

job\_task\_def\_yesexc(m) & Set noraiseexc = 1.\\ \hline

job\_task\_def\_joinable(m) & Declare that the task is joinable
with task\_join()/pthread\_join().\\ \hline

job\_task\_def\_unjoinable(m) & Declare that the task is not joinable (is
detached) with task\_join()/pthread\_join().\\ \hline

job\_task\_def\_trace(m) & Declare that the task has to be traced
by the Tracer.\\ \hline

job\_task\_def\_notrace(m) & Declare that the task has not to be
traced by the Tracer.\\ \hline
\end{tabular}
\caption{HARD\_TASK\_MODEL Macros}
\label{tab:JOB_TASK_MODEL_Macros}
\end{table}

%----------------------------------------------------------------------------
\section{BDEDF\_RES\_MODEL (BlockDevice EDF resource model)}
%----------------------------------------------------------------------------

TBD

%----------------------------------------------------------------------------
\section{BDPSCAN\_RES\_MODEL (Block Device PSCAN resource model)}
%----------------------------------------------------------------------------

TBD

%----------------------------------------------------------------------------
\section{PC\_RES\_MODEL (Priority Ceiling Resource Model)}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    RES_MODEL r;
    DWORD priority;
} PC_RES_MODEL;
\end{verbatim}
\end{tt}

This Resource Model signal to the Priority Ceiling (PC) Module
that the task may use the PC protocol for some mutexes.

Note that the PC Module consider the tasks created without using
this resource models to have priority = MAX\_DWORD (the lowest).

The macro that can be used to setup the Resource Model are the
following:

\texttt{PC\_res\_default\_model(res, prio) }

Initializes a PC\_RES\_MODEL with a priority equal to prio.

\texttt{PC\_res\_def\_level(res,l)}

Set the Model level to l (in a way similar to what happens to task
models).

%----------------------------------------------------------------------------
\section{SRP\_RES\_MODEL (Stack Resource Policy resource model)}
%----------------------------------------------------------------------------

\begin{tt}
\begin{verbatim}
typedef struct {
    RES_MODEL r;
    DWORD preempt;
} SRP_RES_MODEL;
\end{verbatim}
\end{tt}

This Resource Model signal to the Stack Resource Policy (PC)
Module that the task will use the SRP protocol.

Note that the SRP Module does not influence the schedule of any
task that did not pass a SRP\_RES\_MODEL at its creation. The SRP
Module uses another resource model that is embedded into the mutex
structure. See \texttt{modules/srp/srp.c} for details.

The macro that can be used to setup the Resource Model are the
following:

\texttt{SRP\_res\_default\_model(res, pre) }

Initializes a SRP\_RES\_MODEL with a preemption level equal to
prio.

\texttt{SRP\_res\_def\_level(res,l)}

Set the Model level to l (in a way similar to what happens to task
models).

%----------------------------------------------------------------------------
\chapter{Mutex attributes}
%----------------------------------------------------------------------------

Every mutex attribute encode a particular mutex protocol, and one
of them must be passed to the mutex\_init() primitive to specify
the protocol used by a particular mutex. The following paragraphs
describe in detail the mutex attributes. Their definitions can be
found in \texttt{include/kernel/model.h}. Examples of use of mutex
attributes can be found later in this document.

%----------------------------------------------------------------------------
\section{PI\_mutexattr\_t (Priority Inheritance Mutex Attribute)}
%----------------------------------------------------------------------------

\texttt{typedef mutexattr\_t PI\_mutexattr\_t;}

The Priority Ceiling Mutex Attribute.

You can initialize that attribute using the static initializer
\texttt{PI\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{PI\_mutexattr\_default(a)}

where a is the mutex attribute.

%----------------------------------------------------------------------------
\section{NPP\_mutexattr\_t (Non Preemptive Protocol Mutex Attribute)}
%----------------------------------------------------------------------------

\texttt{typedef mutexattr\_t NPP\_mutexattr\_t;}

The Non Preemptive Protocol Mutex Attribute. You can initialize
that attribute using the static initializer
\texttt{NPP\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{NPP\_mutexattr\_default(a)}

where a is the mutex attribute.

%----------------------------------------------------------------------------
\section{PC\_mutexattr\_t (Priority Ceiling Mutex Attribute)}
%----------------------------------------------------------------------------

\texttt{typedef struct \{ mutexattr\_t a; DWORD ceiling; \}
PC\_mutexattr\_t;}

The Priority Ceiling Mutex Attribute.

You can initialize that attribute using the static initializer
\texttt{PC\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{PC\_mutexattr\_default(at,c) }

where at is the mutex attribute, and c is the ceiling of the
mutex.

%----------------------------------------------------------------------------
\section{SRP\_mutexattr\_t (Stack Resource Policy Mutex Attribute)}
%----------------------------------------------------------------------------

\texttt{typedef mutexattr\_t SRP\_mutexattr\_t;}

The Stack Resource Policy Mutex Attribute. You can initialize that
attribute using the static initializer
\texttt{SRP\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{SRP\_mutexattr\_default(a) }

where at is the mutex attribute.

%----------------------------------------------------------------------------
\section{NOP\_mutexattr\_t (No Protocol Mutex Attribute)}
%----------------------------------------------------------------------------

\texttt{typedef mutexattr\_t NOP\_mutexattr\_t;}

The No Protocol Mutex Attribute.

You can initialize that attribute using the static initializer
\texttt{NOP\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{NOP\_mutexattr\_default(a) }

where at is the mutex attribute.

%----------------------------------------------------------------------------
\section{NOPM\_mutexattr\_t (No Protocol Multiple lock Mutex Attribute)}
%----------------------------------------------------------------------------

typedef mutexattr\_t NOPM\_mutexattr\_t;

The No Protocol Multiple lock Mutex Attribute. You can initialize
that attribute using the static initializer
\texttt{NOPM\_MUTEXATTR\_INITIALIZER} or calling the macro

\texttt{NOPM\_mutexattr\_default(a) }

where at is the mutex attribute.

%----------------------------------------------------------------------------
\chapter{Scheduling algorithms}
%----------------------------------------------------------------------------

%----------------------------------------------------------------------------
\section{DUMMY}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [DUMMY\_TASK\_MODEL]- This Model is used only at system
startup to register the dummy task. It cannot be used by the other
modules.
\end{description}

\paragraph{Description:}

This Module implements a \texttt{dummy} task. A dummy task is a
task like all the other task that simply does an infinite loop,
does nothing inside.

Why we need such a Module? Look at the Scheduling Module
Architecture: when the Kernel needs to schedule a task, it asks to
all the registered modules if they have a task to schedule. The
hyphotesis is that there must be ALWAYS a task to schedule. The
dummy Scheduling Modules is used to register a module that have
always a task to schedule (the dummy task).

The dummy Module is not needed if you can ensure that there will
always be a task to schedule.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised. \item
[XUNVALID\_DUMMY\_OP]The dummy task can't be created, or
activated, or another (strange) problem occurred.
\end{description}

\paragraph{Usage:}

Usually the Dummy Module is the LAST scheduling module registered
in the function

\texttt{\_\_kernel\_register\_levels\_\_}.

Just insert the following line into
\texttt{\_\_kernel\_register\_levels\_\_} to register the Module:

\texttt{dummy\_register\_level();}

If you have a CPU where the HLT instruction works, you can use the
define \texttt{\_\_HLT\_WORKS\_\_}. If that \texttt{\#define} is
defined, the idle loop of the \texttt{dummy} task will use
\texttt{HLT}, maybe saving power.

\paragraph{Files:}

\texttt{modules/dummy/*}

\paragraph{Implementation hints:}

You can look at the code to learn how to create a new task at
startup using a \texttt{RUNLEVEL\_INIT} function.

%----------------------------------------------------------------------------
\section{IntDrive Interrupt Server}
%----------------------------------------------------------------------------

\input{intserver.tex}

\paragraph{Files:}

\texttt{modules/intdrive/*}

%----------------------------------------------------------------------------
\subsection{Implementation}
%----------------------------------------------------------------------------

\begin{intest}
INTDRIVE\_register\_level \index{INTDRIVE\_register\_level}
\end{intest}

\begin{description}
\item [\textbf{LEVEL INTDRIVE\_register\_level(TIME capacity, TIME q\_theta, int
U, int flags);}]
\item [\textbf{Description:}]This function registers the IntDrive module at
initialization time. This model should be usually registered as the first module
in the \texttt{\_\_kernel\_register\_levels\_\_} function.
\item [\textbf{Parameters:}]~

\begin{itemize}
\item \textbf{capacity}: the server capacity;
\item \textbf{q\_theta}: the server threshold;
\item \textbf{U}: the maximum bandwidth consumed by the server;
\item \textbf{flags}: a set of configuration options. Supported values are:

\begin{itemize}
\item \textbf{INTDRIVE\_CHECK\_WCET}: when a WCET overrun occurs, an exception
is raised.
\end{itemize}

\end{itemize}

\end{description}

\begin{intest}
INTDRIVE\_usedbandwidth \index{INTDRIVE\_usedbandwidth}
\end{intest}

\begin{description}
\item [\textbf{bandwidth\_t INTDRIVE\_usedbandwidth(LEVEL l);}]
\item [\textbf{Description:}]returns the bandwidth used by the IntDrive.
\end{description}

\begin{intest}
INTDRIVE\_set\_q\_theta \index{INTDRIVE\_set\_q\_theta}
\end{intest}

\begin{description}
\item [\textbf{TIME INTDRIVE\_set\_q\_theta(LEVEL l, TIME new\_q\_theta);}]
\item [\textbf{Description:}]changes the \texttt{q\_theta} value. Notice that
changing \texttt{q\_theta} does not affect the bandwidth used by the server, nor
the schedulability conditions for the application tasks.
\end{description}

\textbf{ATTENTION:} notice that IntDrive is based on the Lipari-Bini
hierarchical framework proposed in \cite{Lip03}. Therefore, the schedulability
tests used by the current scheduling modules are no more sufficient to guarantee
the schedulability. See \cite{Lip03} and \cite{Fac05} for more details.

%----------------------------------------------------------------------------
\section{EDF (Earliest Deadline First) }
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
be used to set the Worst Case Execution Time (WCET) and Period of
the tasks. The \texttt{periodicity} can be either
\texttt{PERIODIC} or \texttt{APERIODIC}. drel field must be <=
mit.

\begin{description}
\item [NOTE:]A Relative Deadline of 0 is interpreted as MIT. \item
[NOTE:]The utilization of the task is computed as wcet/drel. \item
[NOTE:]\textbf{offset} field specifies a release offset relative
to task\_activate or group\_activate.
\end{description}

\end{description}

\paragraph{Guest Models Accepted:}

\begin{description}
\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
be identified by an absolute deadline and a period. The
\texttt{period} field is ignored. \item [Description:]This module
schedules periodic and sporadic tasks based on their absolute
deadlines. The task guarantee is based on a simple utilization
approach. The utilization factor of a task is computed as
wcet/drel. (By default, drel = mit.) A periodic task must only be
activated once; subsequent activations are triggered by an
internal timer. By contrast, an sporadic task must be explicitely
activated for each instance. NO GUARANTEE is performed on guest
tasks. The guarantee must be performed by the level that inserts
guest tasks in the EDF level.
\end{description}

\paragraph{Exceptions raised:}

\begin{description}
\item [XDEADLINE\_MISS]If a task misses its deadline and the
\texttt{EDF\_ENABLE\_DL\_EXCEPTION} flag is set, this exception is
raised. Note that after raising that exception, the task can't be
put in execution again. The safest thing to do is to Shut Down the
system! This exception is also raised if a guest task miss its
deadline. \item [XWCET\_VIOLATION]If a task executes longer than
its declared wcet and the \texttt{EDF\_ENABLE\_WCET\_EXCEPTION}
flag is set, this exception is raised and the task is put in the
\texttt{EDF\_WCET\_VIOLATED} state. To reactivate it, use
\texttt{EDF\_task\_activate} via task\_activate or manage directly
the EDF data structure. Note that the exception is not handled
properly, an \texttt{XDEADLINE\_MISS} exception will also be
raised at the period end. \item [XACTIVATION]If a sporadic task is
activated with a rate that is greather than the rate declared in
the model, this exception is raised and the task is NOT activated.
This exception is also raised if we are trying to activate a
periodic task stopped with \texttt{task\_delay}. \item
[XUNVALID\_GUEST]This exception is raised if a
\texttt{guest\_endcycle} or \texttt{guest\_sleep} guest calls are
called.
\end{description}

\paragraph{Usage:}

Usually this model is registered as one of the first Modules in
the \texttt{\_\_kernel\_register\_levels\_\_} function. To
register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{EDF\_register\_level(flag);}

where \texttt{flag} can be:

\begin{description}
\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
ignored. Pending periodic jobs are queued and are eventually
scheduled with correct deadlines according to their original
arrival times. Sporadic tasks that arrive to often aresimply
dropped. \item [EDF\_ENABLE\_DL\_CHECK]- When a deadline overrun
occurs, the dl\_miss counter of the task is increased. Same
behavior for pending jobs as above. \item
[EDF\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
wcet\_miss counter of the task is increased. Same behavior for
pending jobs as above. \item [EDF\_ENABLE\_DL\_EXCEPTION]- When a
deadline overrun occurs, an exception is raised. \item
[EDF\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
exception is raised. \item [EDF\_ENABLE\_ACT\_EXCEPTION]When a
periodic or sporadic task is activated too often, an exception is
raised.
\end{description}

The functions \texttt{EDF\_get\_dl\_miss},
\texttt{EDF\_get\_wcet\_miss}, \texttt{EDF\_get\_act\_miss}, and
EDF\_get\_nact can be used to find out the number of missed
deadlines, the number of wcet overruns, the number of skipped
activations, and the number of currently queued periodic
activations.

\begin{description}
\item [EDF\_DISABLE\_ALL]- All checks disabled \item
[EDF\_ENABLE\_GUARANTEE]- Guarantee test enabled.

When enabled, an acceptance test
($\sum\frac{WCET_{i}}{Period_{i}}<1$) is performed; Deadline miss
exceptions are raised in any case.

\item [EDF\_ENABLE\_ALL]- All checks enabled
\end{description}

The EDF Module provides also addictional functions:

\begin{description}
\item [\textbf{bandwidth\_t EDF\_usedbandwidth(LEVEL l);}]
It returns the used bandwidth, where l is the level at which the
EDF Module is registered.
\item [\textbf{int EDF\_get\_dl\_miss(PID p);}]
It returns the deadline miss counter.
\item [\textbf{int EDF\_get\_wcet\_miss(PID p);}]
It returns the wcet miss counter.
\item [\textbf{int EDF\_get\_act\_miss(PID p);}]
It returns the activation miss counter.
\end{description}

\paragraph{Files:}

\texttt{modules/edf/*}

\paragraph{Implementation hints:}

It uses the CONTROL\_CAP field to keep track of the task execution
time. It implements a ZOMBIE state for ended tasks. It post a
single OSLib event for each task for deadline/reactivation/zombie
detection. The \texttt{guest\_endcycle} and \texttt{guest\_sleep}
guest calls are not implemented.

\begin{description}
\item [NOTES:]~
\end{description}

\begin{enumerate}
\item Relative deadlines \textbf{drel <= mit} may be specified.
\item An offset
>
0 will delay the activation of the task by the same amount of
time. To synchronize a group of tasks, assign suitable offsets and
then use the group\_activate function. \item This level doesn't
manage the main task. \item The level uses the priority and
timespec\_priority fields. \item The guest tasks don't provide the
guest\_endcycle function.
\end{enumerate}

%----------------------------------------------------------------------------
\section{POSIX (fixed priority FIFO/RR scheduler)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. If the
\texttt{inherit} field is set to \texttt{NRT\_INHERIT\_SCHED}, the
scheduling properties of the running task are inherited (as
required by the POSIX standard). Else, the \texttt{slice} field is
used to set the time slice of the task (if \texttt{slice} is set
to 0, the default value is used); the \texttt{weight} field is
used to set the task priority; the \texttt{policy} field is used
to set the policy of the task (\texttt{NRT\_RR\_POLICY} for
Round-Robin or \texttt{NRT\_FIFO\_POLICY} for FIFO); the
\texttt{arrivals} field can be set to \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}.
\end{description}

\paragraph{Description:}

This module schedule his tasks following the POSIX scheduler as
described by the standard IEEE 1003.1c. This Module is typically
used by the POSIX primitives for their scheduling pourposes. For
example, the pthread\_create function calls the task\_createn
function passing a NRT\_TASK\_MODEL filled with the correct
parameters.

The Module can create the \texttt{\_\_init\_\_} task, that is
typically used to call the Standard C \texttt{main()} function.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{POSIX\_register\_level(slice, createmain, mb,
prioritylevels);}

where \texttt{slice} is the default timeslice for the POSIX tasks scheduled
using the Round-Robin policy, \texttt{createmain} is \texttt{POSIX\_MAIN\_YES}
or \texttt{POSIX\_MAIN\_NO} if you want that the POSIX Module creates or not the
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct multiboot\_info
*} the Kernel passed to the \texttt{\_\_kernel\_register\_levels\_\_}
function, and prioritylevels are the number of different priority levels
supported by the Module \footnote{The POSIX standard requires a minimum of 32
priority levels}.

The POSIX Module provides also some addictional function, that are
used to implement the behaviour of various POSIX primitives:

\texttt{int POSIX\_sched\_yield(LEVEL l);}

This function forces the running task to go to his queue tail,
then calls the scheduler and changes the context. It is used by
the \texttt{sched\_yield()} primitive.

\texttt{int POSIX\_get\_priority\_max(LEVEL l);}

This function returns the maximum level allowed for the POSIX
level. It is used by the \texttt{sched\_get\_priority()}
primitive.

\texttt{int POSIX\_rr\_get\_interval(LEVEL l);}

This function returns the default timeslice for the POSIX level.
It is used by the \texttt{sched\_rr\_get\_interval()} primitive.

\texttt{int POSIX\_getschedparam(LEVEL l, PID p, int *policy,
int *priority);}

This functions returns some paramaters of a task; \texttt{policy}
is set to \texttt{NRT\_RR\_POLICY} or \texttt{NRT\_FIFO\_POLICY};
priority is set in the range \texttt{{[}0..prioritylevels{]}}. The
function returns \texttt{ENOSYS} or \texttt{ESRCH} if there are
problems. The function must be called with interrupts disabled and
is used by the \texttt{pthread\_getschedparam()} primitive.

\texttt{int POSIX\_setschedparam(LEVEL l, PID p, int policy, int
priority);}

This functions sets some paramaters of a task; \texttt{policy}
must be set to \texttt{NRT\_RR\_POLICY} or
\texttt{NRT\_FIFO\_POLICY}; priority must be set in the range
\texttt{{[}0..prioritylevels{]}}. The function returns
\texttt{ENOSYS}, \texttt{EINVAL} or \texttt{ESRCH} if there are
problems. The function must be called with interrupts disabled and
is used by the \texttt{pthread\_setschedparam() primitive}.

\paragraph{Files:}

\texttt{modules/posix/*}

\paragraph{Implementation hints:}

The implementation of this module is directly derived from the RR
scheme.

%----------------------------------------------------------------------------
\section{RM (Rate Monotonic)}
%----------------------------------------------------------------------------

\paragraph{Task
Models Accepted:}

\begin{description}
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic). The
\texttt{wcet} and \texttt{mit} must be != 0. These parameters will
be used to set the Worst Case Execution Time (WCET) and Period of
the tasks. The \texttt{periodicity} can be either
\texttt{PERIODIC} or \texttt{APERIODIC}. The Relative Deadline is
ignored (deadlines are equal to periods).
\end{description}

\paragraph{Guest Models Accepted:}

\begin{description}
\item [JOB\_TASK\_MODEL]- A single guest task activation. It must
be identified by an absolute deadline and a period.
\end{description}

\paragraph{Description:}

This module schedule his tasks following the classic RM scheme as
described by Liu and Layland. The task guarantee is based on the
factor utilization approach. The tasks scheduled are periodic and
sporadic. The sporadic tasks are like hard task with periodicity
set to \texttt{APERIODIC}; they are guaranteed as a periodic task
with period equal to the minimum interarrival time. All the task
are put in a queue and the scheduling is based on the period
value.

No Guarantee is performed on guest tasks. The guarantee must be
performed by the level that inserts guest tasks in the RM level.

If a RM task does not respect its WCET and deadline constraints,
then the Module will raise an exception. Note that the deadline
exception is not recoverable, so the Module will be in an
inconsistent state after a Deadline Miss. Deadline Miss in this
Module are treated as unrecoverable errors.

If you try to activate a Periodic task that is not sleeping,
nothing happens.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XDEADLINE\_MISS]If a task miss his deadline, the exception
is raised. Note that after raising that exception, the task can't
be put in execution again. The safest thing to do is to Shut Down
the system! This exception is also raised if a guest task miss its
deadline. \item [XWCET\_VIOLATION]If a task doesn't end the
current cycle before if consume the \texttt{wcet}, an exception is
raised, and the task is put in the \texttt{RM\_WCET\_VIOLATED}
state. To reactivate it, use \texttt{RM\_task\_activate} via
task\_activate or manage directly the RM data structure. Note that
the exception is not handled properly, an \texttt{XDEADLINE\_MISS}
exception will also be raised at the period end. \item
[XACTIVATION]If a sporadic task is activated with a rate that is
greather than the rate declared in the model, this exception is
raised and the task is NOT activated. This exception is also
raised if we are trying to activate a periodic task stopped with
\texttt{task\_sleep} before the deadline in which the
\texttt{task\_sleep} is called. \item [XUNVALID\_GUEST]This
exception is raised if a \texttt{guest\_endcycle} or
\texttt{guest\_sleep} guest calls are called.
\end{description}

\paragraph{Usage:}

Usually this model is registered as one of the first Modules in
the \texttt{\_\_kernel\_register\_levels\_\_} function. To
register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{RM\_register\_level(flag);}

where \texttt{flag} can be:

Restrictions and special features:

\begin{description}
\item [(No\_flags\_enabled)]- Deadline and wcet overruns are
ignored. Pending periodic jobs are queued and are eventually
scheduled with correct deadlines according to their original
arrival times. Sporadic tasks that arrive to often are simply
dropped. \item [RM\_ENABLE\_DL\_CHECK]- When a deadline overrun
occurs, the dl\_miss counter of the task is increased. Same
behavior for pending jobs as above. \item
[RM\_ENABLE\_WCET\_CHECK]- When a wcet overrun occurs, the
wcet\_miss counter of the task is increased. Same behavior for
pending jobs as above. \item [RM\_ENABLE\_DL\_EXCEPTION]- When a
deadline overrun occurs, an exception is raised. \item
[RM\_ENABLE\_WCET\_EXCEPTION]- When a wcet overrun occurs, an
exception is raised. \item [RM\_ENABLE\_ACT\_EXCEPTION]When a
periodic or sporadic task is activated too often, an exception is
raised. \item [RM\_DISABLE\_ALL]- Wcet and Guarantee test disabled
\item [RM\_ENABLE\_GUARANTEE]- Guarantee test enabled (when
enabled, an acceptance test ($\sum\frac{WCET_{i}}{Period_{i}}<1$)
is performed; Deadline miss exceptions are raised in any case.
Note that, for reasons of semplicity, the test that has been
implemented IS NOT the test for RM, but only a simple acceptance
test. \item [RM\_ENABLE\_ALL]- Wcet and Guarantee test enabled
\end{description}
The RM Module provides also addictional functions:

\begin{description}
\item [\textbf{bandwidth\_t RM\_usedbandwidth(LEVEL l);}]
It returns the used bandwidth, where l is the level at which the
RM Module is registered.
\item [\textbf{int RM\_get\_dl\_miss(PID p);}]
It returns the deadline miss counter.
\item [\textbf{int RM\_get\_wcet\_miss(PID p);}]
It returns the wcet miss counter.
\item [\textbf{int RM\_get\_act\_miss(PID p);}]
It returns the activation miss counter.
\end{description}

\paragraph{Files:}

\texttt{modules/rm/*}

\paragraph{Implementation hints:}

The implementation of this module is very similar to the
implementation of the EDF Module.

\paragraph{NOTE}

\begin{enumerate}
\item Relative deadlines drel <= mit may be specified. \item An offset > 0 will
delay the activation of the task by the same amount of time. To synchronize a
group of tasks, assign suitable \item offsets and then use the group\_activate
function. \item This level doesn't manage the main task. \item The level uses
the priority and timespec\_priority fields. \item The guest tasks don't provide
the guest\_endcycle function. \item At init time, the user can specify the
behavior in case ofdeadline and wcet overruns. The following flags are
available:
\end{enumerate}

%----------------------------------------------------------------------------
\section{RR (Round Robin)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
field is used to set the time slice of the task. If \texttt{slice}
is set to 0, the default value is used. The \texttt{weight},
\texttt{arrivals}, \texttt{policy} and \texttt{inherit} fields are
ignored.
\end{description}

\paragraph{Description:}

This module schedule his tasks following the classic round-robin
scheme. The default timeslice is given at registration time and is
a a per-task specification. The default timeslice is used if the
\texttt{slice} field in the \texttt{NRT\_TASK\_MODEL} is 0.

If a task is activated when it is already active (its instance is
not yet finished on a \texttt{task\_endcycle} or
\texttt{task\_sleep}), nothing happens.

If you need to remember the pending activations you can use the
\texttt{RR2} scheduling module.

The Module can create the \texttt{\_\_init\_\_} task, that is
typically used to call the Standard C \texttt{main()} function.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{RR\_register\_level(slice, createmain, mb);}

where \texttt{slice} is the default timeslice for the RR tasks,
\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
multiboot\_info *} the Kernel passed to the
\texttt{\_\_kernel\_register\_levels\_\_} function.

You can use more than one RR Scheduling Module to simulate a
Multilevel scheduling policy. The RR Module does not add any
addictional function.

\paragraph{Files:}

\texttt{modules/rr/*}

\paragraph{Implementation hints:}

This is one of the simplest scheduling module. It can be useful to
learn how to create the \_\_init\_\_ task at startup time. It uses
the CONTROL\_CAP field. It supports negative task capacities (that
can happen when using shadows; for that reason, the scheduler has
a while inside, and the timeslices ar added and not assigned). No
Guarantee is performed at task creation.

%----------------------------------------------------------------------------
\section{RR2 (Round Robin with pending activations)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [NRT\_TASK\_MODEL]- Non-Realtime Tasks. The \texttt{slice}
field is used to set the time slice of the task. If \texttt{slice}
is set to 0, the default value is used. The \texttt{arrivals}
field is used to say if the activations have to be saved
(\texttt{SAVE\_ARRIVALS}) or skipped (\texttt{SKIP\_ARRIVALS}).
The \texttt{weight}, \texttt{policy} and \texttt{inherit} fields
are ignored.
\end{description}

\paragraph{Description:}

The Module is identical to the RR Scheduling Module, except that
task activations can be saved if a task was created with the
arrivals field equal to SAVE\_ARRIVALS.

\paragraph{Exceptions Raised:}

See the RR Scheduling Module.

\paragraph{Usage:}

See the RR Scheduling Module, changing every occurrence of RR with
RR2.

\paragraph{Files:}

\texttt{modules/rr2/*}

\paragraph{Implementation hints:}

With respect to the RR Scheduling Module, it adds a pending
activation counter (nact) for each task.

%----------------------------------------------------------------------------
\section{RRSOFT (hard/SOFT Round Robin)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [HARD\_TASK\_MODEL]- Hard Tasks (Periodic and Sporadic).
Only the periodicity and the mit parameters are used to know if
the task is periodic/sporadic and to set the task period. The task
timeslice is set to the default value. \item [SOFT\_TASK\_MODEL]-
Soft Tasks (Periodic and Sporadic). Only the periodicity, arrivals
and period parameters are used to know if the task is
periodic/sporadic, to set the task period and to know if the
pending activations should be saved. The task timeslice is set to
the default value. \item [NRT\_TASK\_MODEL]- Non-Realtime Tasks.
The \texttt{slice} field is used to set the time slice of the
task. If \texttt{slice} is set to 0, the default value is used.
The \texttt{arrivals} field is used to say if the activations have
to be saved (\texttt{SAVE\_ARRIVALS}) or skipped
(\texttt{SKIP\_ARRIVALS}). The \texttt{weight}, \texttt{policy}
and \texttt{inherit} fields are ignored.
\end{description}

\paragraph{Description:}

This module can be used as a polymorphic module that can accept
Hard, Soft or NRT Task Models. The policy used to schedule the
tasks is the same of RR2, plus the fact that SOFT and HARD tasks
can be periodic, so they can be automatically activated at each
instance.

This Module is very useful if you want to replace another Module
that accept Hard of Soft tasks with a round-robin scheduler, for
example to compare a scheduling algorithm with the plain round
robin.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{RRSOFT\_register\_level(slice, createmain, mb, models);}

where \texttt{slice} is the default timeslice for the RR tasks,
\texttt{createmain} is \texttt{RR\_MAIN\_YES} or
\texttt{RR\_MAIN\_NO} if you want that RR creates or not the
\texttt{\_\_init\_\_} task, \texttt{mb} is the \texttt{struct
multiboot\_info *} the Kernel passed to the
\texttt{\_\_kernel\_register\_levels\_\_} function, and
\texttt{models} specifies the kind of Models accepted by the
Module. The \texttt{models} value can be an or of the values of
the following constants: \texttt{RRSOFT\_ONLY\_HARD},
\texttt{RRSOFT\_ONLY\_HARD}, \texttt{RRSOFT\_ONLY\_HARD}.

You can use more than one RR Scheduling Module to simulate a
Multilevel scheduling policy. The RR Module does not add any
addictional function.

\paragraph{Files:}

\texttt{modules/rrsoft/*}

\paragraph{Implementation hints:}

The implementation of the Module is similar to RR2 plus the
implementation of the reactivation for periodic tasks.

%----------------------------------------------------------------------------
\chapter{Aperiodic servers}
%----------------------------------------------------------------------------

%----------------------------------------------------------------------------
\section{CBS (Constant Bandwidth Server)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [SOFT\_TASK\_MODEL]- Soft Tasks (Periodic and Sporadic). The
\texttt{met} and \texttt{period} must be != 0. These parameters
will be used to set the Mean Execution Time (MET) and the Period
of the tasks. The \texttt{periodicity} can be either
\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
field can be either \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}. The \texttt{wcet} field is ignored (Worst
case execution times are not used by CBS).
\end{description}

\paragraph{Description:}

This module schedule his tasks following the CBS algorithm. The
task guarantee is based on the factor utilization approach. The
tasks scheduled are periodic and sporadic. The sporadic tasks are
like hard task with periodicity set to \texttt{APERIODIC}. All the
task are put as guest task in the scheduling queue of another
Module (typically that Module is an EDF Module).

A CBS server is attached to each task, with the parameters passed
in the \texttt{SOFT\_TASK\_MODEL}.

If you try to activate a Periodic task that is not sleeping, a pending
activation is recorded \footnote{If the task was created with the
\texttt{SAVE\_ARRIVALS} option... }.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{CBS\_register\_level(flag, master);}

where \texttt{flag} can be:

\begin{description}
\item [CBS\_DISABLE\_ALL]- Guarantee test disabled. \item
[CBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled, an
acceptance test ($\sum\frac{met_{i}}{period_{i}}<1$) is performed;
Deadline miss exceptions are raised in any case. \item
[CBS\_ENABLE\_ALL]- Guarantee test enabled.
\end{description}
and \texttt{master} is the level to that the CBS is attached. At
the moment, you can attach a CBS Module either to an \texttt{EDF}
or an \texttt{EDFACT} Module. The CBS Module can be registered as
the last scheduling Module after the \texttt{DUMMY} Module (this
because the CBS Module does not use background time, and because
when a CBS task is ready it is inserted in another queue!).

The CBS Module provides also an addictional function, that can be
used to get the used bandwidth by the Module and the pending
activations of a task. The prototypes of these function are:

\texttt{bandwidth\_t CBS\_usedbandwidth(LEVEL l);}

where l is the level at which the CBS Module is registered.

\texttt{int CBS\_get\_nact(LEVEL l, PID p);}

Returns the number of pending activations of a task. No control is
done if the task is not a CBS task! (l is the level at which the
CBS Module is registered, p is the PID of the task).

\paragraph{Files:}

\texttt{modules/cbs/*}

\paragraph{Implementation hints:}

CBS implementation is similar to the EDF implementation except
that a capacity exaustion postpones a deadline, and that the
deadline event is simply a reactivation. This is one of the only
Modules where the \texttt{task\_eligible} task calls is defined
non-void.

%----------------------------------------------------------------------------
\section{HARD\_CBS}
%----------------------------------------------------------------------------

This Module is very similar to the standard CBS, but it implements
the Hard Reservation algorithm.

\begin{description}
\item [Files:]\texttt{modules/hardcbs/*}
\end{description}

%----------------------------------------------------------------------------
\section{DS (Deferrable Server)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
\texttt{periodicity} can be only \texttt{APERIODIC}. The
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
\end{description}

\paragraph{Description:}

This module schedule its tasks following the Deferrable Server
Algorithm. All the aperiodic requests are served on a FCFS basis.
The Module can be configured to use only its budget or to also use
the idle time left by the higher level Modules. The Module can be
configured to save or skip task activations. The Module can be
attached to either a RM or an EDF Module.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{DS\_register\_level(flag, master, Cs, per);}

where \texttt{flag} can be:

\begin{description}
\item [DS\_DISABLE\_ALL]- Guarantee test disabled; Background
scheduling disabled. \item [DS\_ENABLE\_BACKGROUND]- Background
scheduling enabled. \item [DS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
is performed. This flag have to be used if the Module is attached
to an EDF Module. \item [DS\_ENABLE\_ALL\_EDF]- EDF guarantee test
enabled, Background scheduling disabled. \item
[DS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
have to be used if the Module is attached to a RM Module. \item
[DS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
scheduling disabled.
\end{description}
\texttt{master} is the level to that the DS Module is attached. At
the moment, you can attach a DS Module either to an \texttt{EDF},
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
\texttt{per} are the budget and the period of the deferrable
server. If it is configured to do not use background time, the DS
Module can be registered as the last scheduling Module after the
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
of the list to catck the idle time left by higher level Modules.

The DS Module provides also an addictional function, that can be
used to get the used bandwidth by the Module. The prototype of the
function is:

\texttt{bandwidth\_t DS\_usedbandwidth(LEVEL l);}

where l is the level at which the DS Module is registered.

\paragraph{Files:}

\texttt{modules/ds/*}

\paragraph{Implementation hints:}

The DS Module uses a FIFO queue to enqueue the ready tasks. Only
the first task is inserted into the queue of the Master Level. The
Module does not use the CONTROL\_CAP field, but it handles its
capacity event by itself. The budget of the module is recharged
every DS period, and is kept into an internal data structure of
the module, and not in the wcet and avail\_time fields of every
task. Note that the idle time is recognized when the DS scheduler
is called. In that case, no capacity event is posted. The
implementation is very similar to the PS Module implementation.

%----------------------------------------------------------------------------
\section{PS (Polling Server)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
\texttt{periodicity} can be only \texttt{APERIODIC}. The
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
\end{description}

\paragraph{Description:}

This module schedule its tasks following the Polling Server
Algorithm. All the aperiodic requests are served on a FCFS basis.
The Module can be configured to use only its budget or to also use
the idle time left by the higher level Modules. The Module can be
configured to save or skip task activations. The Module can be
attached to either a RM or an EDF Module.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{PS\_register\_level(flag, master, Cs, per);}

where \texttt{flag} can be:

\begin{description}
\item [PS\_DISABLE\_ALL]- Guarantee test disabled; Background
scheduling disabled. \item [PS\_ENABLE\_BACKGROUND]- Background
scheduling enabled. \item [PS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
is performed. This flag have to be used if the Module is attached
to an EDF Module. \item [PS\_ENABLE\_ALL\_EDF]- EDF guarantee test
enabled, Background scheduling disabled. \item
[PS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
have to be used if the Module is attached to a RM Module. \item
[PS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
scheduling disabled.
\end{description}
\texttt{master} is the level to that the DS Module is attached. At
the moment, you can attach a PS Module either to an \texttt{EDF},
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
\texttt{per} are the budget and the period of the deferrable
server. If it is configured to do not use background time, the PS
Module can be registered as the last scheduling Module after the
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
of the list to catck the idle time left by higher level Modules.

The PS Module provides also an addictional function, that can be
used to get the used bandwidth by the Module. The prototype of the
function is:

\texttt{bandwidth\_t PS\_usedbandwidth(LEVEL l);}

where l is the level at which the PS Module is registered.

\paragraph{Files:}

\texttt{modules/ps/*}

\paragraph{Implementation hints:}

The PS Module uses a FIFO queue to enqueue the ready tasks. Only
the first task is inserted into the queue of the Master Level. The
Module does not use the CONTROL\_CAP field, but it handles its
capacity event by itself. The budget of the module is recharged
every PS period, and is kept into an internal data structure of
the module, and not in the wcet and avail\_time fields of every
task. Note that the idle time is recognized when the PS scheduler
is called. In that case, no capacity event is posted. The
implementation is very similar to the DS Module implementation.

%----------------------------------------------------------------------------
\section{SS (Sporadic Server)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
\texttt{periodicity} can be only \texttt{APERIODIC}. The
\texttt{arrivals} field can be either \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
\end{description}

\paragraph{Description:}

This module schedule its tasks following the Sporadic Server
Algorithm. The Module can be configured to save or skip task
activations. The Module can be attached to either a RM or an EDF
Module. The module has been written by Marco Gigante. Please
contact the author for more informations.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{SS\_register\_level(flag, master, Cs, per);}

where \texttt{flag} can be:

\begin{description}
\item [SS\_DISABLE\_ALL]- Guarantee test disabled; Background
scheduling disabled. \item [SS\_ENABLE\_BACKGROUND]- Background
scheduling enabled. \item [SS\_ENABLE\_GUARANTEE\_EDF]- Guarantee
test enabled (when enabled, an acceptance test ($U_{p}+U_{s}<1$)
is performed. This flag have to be used if the Module is attached
to an EDF Module. \item [SS\_ENABLE\_ALL\_EDF]- EDF guarantee test
enabled, Background scheduling disabled. \item
[SS\_ENABLE\_GUARANTEE\_RM]- Guarantee test enabled (when enabled,
an acceptance test ($U_{p}+U_{s}<ln\,2$) is performed. This flag
have to be used if the Module is attached to a RM Module. \item
[SS\_ENABLE\_ALL\_RM]- RM guarantee test enabled, Background
scheduling disabled.
\end{description}

\texttt{master} is the level to that the SS Module is attached. At
the moment, you can attach a SS Module either to an \texttt{EDF},
\texttt{EDFACT} or \texttt{RM} Module. \texttt{Cs} and
\texttt{per} are the budget and the period of the deferrable
server. If it is configured to do not use background time, the SS
Module can be registered as the last scheduling Module after the
\texttt{DUMMY} Module. Otherwise, it should be put in the middle
of the list to catck the idle time left by higher level Modules.

The SS Module provides also some addictional function, that can be
used to get the used bandwidth by the Module and its available
capacity. The prototypes of the functions are:

\texttt{bandwidth\_t SS\_usedbandwidth(LEVEL l);}

where l is the level at which the SS Module is registered.

\texttt{int SS\_availCs(LEVEL l);}

Returns tha available capacity of the Module

\paragraph{Files:}

\texttt{modules/ss/*}

\paragraph{Implementation hints:}

The implementation of the Module is quite complex. Please refer to
the comments in the source code.

%----------------------------------------------------------------------------
\section{TBS (Total Bandwidth Server)}
%----------------------------------------------------------------------------

\paragraph{Task Models Accepted:}

\begin{description}
\item [SOFT\_TASK\_MODEL]- Soft Tasks (only Sporadic). The
\texttt{wcet} must be != 0. The \texttt{periodicity} can be either
\texttt{PERIODIC} or \texttt{APERIODIC}. The \texttt{arrivals}
field can be either \texttt{SAVE\_ARRIVALS} or
\texttt{SKIP\_ARRIVALS}. The other fields are ignored.
\end{description}

\paragraph{Description:}

This module schedule his tasks following the TBS algorithm. The
task guarantee is based on the factor utilization approach. The
tasks scheduled are only sporadic. Each task has a deadline
assigned with the TBS scheme,
$d_{k}=\max(r_{k},d_{k-1})+\frac{wcet}{U_{s}}$

The tasks are inserted in an EDF level (or similar), and the TBS
level expects that the task is scheduled with the absolute
deadline passed in the guest model.

The acceptance test is based on the factor utilization approach.
The theory guarantees that the task set is schedulable if
$U_{p}+U_{s}\leq1$ so it is sufficient to add the Us to the
bandwidth used by the upper levels.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XUNVALID\_GUEST]This level doesn't support guests. When a
guest operation is called, the exception is raised. \item
[XDEADLINE\_MISS]If a task miss his deadline, the exception is
raised. Normally, a TBS task can't cause the raise of such
exception because if it really use more time than declared a
\texttt{XWCET\_VIOLATION} is raised instead. \item
[XWCET\_VIOLATION]If a task doesn't end the current cycle before
if consume the wcet, an exception is raised, and the task is put
in the \texttt{TBS\_WCET\_VIOLATED} state. To reactivate it, call
\texttt{TBS\_task\_activate} using \texttt{task\_activate} or
manage directly the TBS data structure. Note that if the exception
is not handled properly, an \texttt{XDEADLINE\_MISS} exception
will also be raised at the absolute deadline...
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{TBS\_register\_level(flag, master, num, den);}

where \texttt{flag} can be:

\begin{description}
\item [TBS\_DISABLE\_ALL]- Guarantee test disabled. \item
[TBS\_ENABLE\_GUARANTEE]- Guarantee test enabled (when enabled,
the acceptance test is performed); Deadline miss exceptions are
raised in any case. \item [TBS\_ENABLE\_WCET\_CHECK]- WCET check
enabled. \item [TBS\_ENABLE\_ALL]- Guarantee test and WCET check
enabled.
\end{description}
and \texttt{master} is the level to that the TBS is attached. num
and den are the reserved bandwidth ($U_{s}=\frac{num}{den}$) for
the TBS server. At the moment, you can attach a TBS Module either
to an \texttt{EDF} or an \texttt{EDFACT} Module. The TBS Module
can be registered as the last scheduling Module after the
\texttt{DUMMY} Module (this because the TBS Module does not use
background time, and because when a TBS task is ready it is
inserted in another queue!).

The TBS Module provides also some addictional functions, that can
be used to get the used bandwidth by the Module and the pending
activations of a task. The prototypes of these function are:

\texttt{bandwidth\_t TBS\_usedbandwidth(LEVEL l);}

where l is the level at which the TBS Module is registered.

\texttt{int TBS\_get\_nact(LEVEL l, PID p);}

Returns the number of pending activations of a task. No control is
done if the task is not a TBS task! (l is the level at which the
TBS Module is registered, p is the PID of the task).

\paragraph{Files:}

\texttt{modules/tbs/*}

\paragraph{Implementation hints:}

The TBS implementation uses a FIFO queue for serving the aperiodic
requests of the Module's tasks. Only the first task is put in the
ready queue of the master module.

%----------------------------------------------------------------------------
\chapter{Sharing resource access protocols}
%----------------------------------------------------------------------------

%----------------------------------------------------------------------------
\section{CABS}
%----------------------------------------------------------------------------

\paragraph{Description:}

This module implements the Cyclical Asynchronous Buffers as
described in the Volume I of the User Manual.

Note that the Maximum number of CABs that can be created is
MAX\_CAB (defined in include/modules/cabs.h).

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{CABS\_register\_module();}

\paragraph{Files:}

\texttt{modules/cabs/*}

%----------------------------------------------------------------------------
\section{HARTPORT}
%----------------------------------------------------------------------------

\paragraph{Description:}

This module implements the Communication Ports as described in the
Volume I of the User Manual.

\paragraph{Usage:}

To register this module, just put this line into the \texttt{\_\_init\_\_} task
\footnote{or in any other task; in any case this function has to be called
before using the port primitives}:

\texttt{HARTPORT\_init();}

\paragraph{IMPORTANT: }

Remember that to get the ports running, you need to register also
the SEM module!

\paragraph{Files:}

\texttt{modules/hartport/*}

%----------------------------------------------------------------------------
\section{NOP (NO Protocol)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

None.

\paragraph{Description:}

The NOP Module implements a binary semaphore using the mutex
interface. If a task owns a mutex, it can not lock that mutex
again until it has unlocked it. This protocol can produce priority
inversions and chained blocking.

\paragraph{Exceptions Raised:}

None

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{NOP\_register\_module();}

The NOP protocol uses the default mutex mechanism provided by the
Kernel. In that way, the NOP behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a NOP mutex, you need to call \texttt{mutex\_init()}
passing a previously initialized \texttt{NOP\_mutexattr\_t}.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
\begin{verbatim}
#include <modules/nop.h>
...

mutex_t m1,m2;
...

void *demo(void *arg) {
    ...
   
    mutex_lock(&m1);

    /* critical section of m1 */
    ...

    mutex_unlock(&m1);
    ...

    mutex_lock(&m1);

    /* only m1 locked */
    ...
   
    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...
   
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...
   
    return 0;
}

...

int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;

    NOP_mutexattr_t a;

    /* Initialize the NOP mutexes */
    NOP_mutexattr_default(a);
    mutex_init(&m1, &a);
    mutex_init(&m2, &a);
    ...

    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    p0 = task_create("DEMO", demo, &m, NULL);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

\paragraph{Note:}

NOP Mutexes can be statically allocated. See
\texttt{include/modules/nop.h} for details.

\paragraph{Note:}

A task can use NOP mutexes with other mutexes with different
protocol (for example, PI, PC, SRP mutexes). We don't know the
behaviour of that choice, but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/nop/*}

\paragraph{Implementation hints:}

The implementation of the NOP mutexes is similar to the internal
semaphores.

%----------------------------------------------------------------------------
\section{NOPM (NO Protocol Multiple lock)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

None.

\paragraph{Description:}

The NOP Module implements a binary semaphore using the mutex
interface. If a task owns a mutex, it can lock that mutex again.
It is like the NOP Module, but the owner of the mutex can issue
multiple lock/unlock on mutex. This protocol can produce priority
inversions and chained blocking.

\paragraph{Exceptions Raised:}

None

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{NOPM\_register\_module();}

The NOPM protocol uses the default mutex mechanism provided by the
Kernel. In that way, the NOPM behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a NOPM mutex, you need to call
\texttt{mutex\_init()} passing a previously initialized
\texttt{NOPM\_mutexattr\_t}.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
\begin{verbatim}
#include <modules/nopm.h>
...

mutex_t m1, m2;
...
 
void *demo(void *arg) {
    ...

    mutex_lock(&m1);

    /* critical section of m1 */
    ...

    mutex_unlock(&m1);
    ...

    mutex_lock(&m1);

    /* only m1 locked */
    ...

    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...
   
    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...
   
    return 0;
}

...

int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;
   
    NOPM_mutexattr_t a;

    /* Initialize the NOP mutexes */
    NOPM_mutexattr_default(a);
    mutex_init(&m1, &a);
    mutex_init(&m2, &a);
    ...
   
    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    p0 = task_create("DEMO", demo, &m, NULL);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

\paragraph{Note:}

A task can use NOPM mutexes with other mutexes with different
protocol (for example, PI, PC, SRP mutexes). We don't know the
behaviour of that choice, but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/nopm/*}

\paragraph{Implementation hints:}

The implementation of the NOPM mutexes is similar to the NOP
implementation, except that it counts the numer of times a task
locked a mutex.

%----------------------------------------------------------------------------
\section{NPP (Non Preemptive Protocol)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

None.

\paragraph{Description:}

The NPP Module implements a binary semaphore using the mutex
interface. The difference with the NOP Module is that when a task
lock a NPP mutex, it became non-preemptive as it called the
\texttt{task\_nopreempt()} primitive. Critical section can be
nested.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
ends and it owns one or more mutexes.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{NPP\_register\_module();}

The NPP protocol uses the default mutex mechanism provided by the
Kernel. In that way, the NPP behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a NPP mutex, you need to call \texttt{mutex\_init()}
passing a previously initialized \texttt{NPP\_mutexattr\_t}.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
\begin{verbatim}
#include <modules/npp.h>
...

mutex_t m1,m2;
...

void *demo(void *arg) {
    ...

    mutex_lock(&m1);

    /* critical section of m1 */
    ...
   
    mutex_unlock(&m1);
    ...
       
    mutex_lock(&m1);

    /* only m1 locked */
    ...

    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...

    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...

    return 0;
}

...
   
int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;
    NPP_mutexattr_t a;

    /* Initialize the NOP mutexes */
    NPP_mutexattr_default(a);
    mutex_init(&m1,&a);
    mutex_init(&m2,&a);
    ...
   
    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    p0 = task_create("DEMO", demo, &m, NULL);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

\paragraph{Note:}

A task can use NPP mutexes with other mutexes with different
protocol (for example, PI, PC, SRP mutexes; except for nested
critical sections). We don't know the behaviour of that choice,
but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/npp/*}

\paragraph{Implementation hints:}

The implementation of the NPP Module counts the number of locks a
task issued and uses
\texttt{task\_preempt()}/\texttt{task\_nopreempt()} to implement
the protocol.

%----------------------------------------------------------------------------
\section{PC (Priority Ceiling)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

\begin{description}
\item [PC\_RES\_MODEL]- Task priority. This model have to be used
to tell to the PC Module that a task have to be scheduled
following the PC rules. The model can be passed at creation time
to more than one task, and it only contains the priority
information.
\end{description}

\paragraph{Description:}

This Module implements the Priority Ceiling (PC) Protocol. This
mechanism can be easily applied to Fixed Priority Scheduling to
bound blocking times and to eliminate chained blocking and
deadlocks.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
ends and it owns one or more PC mutexes.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{PC\_register\_module();}

The PC protocol uses the default mutex mechanism provided by the
Kernel. In that way, the PC behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a PC mutex, you need to call \texttt{mutex\_init()}
passing a previously initialized \texttt{PC\_mutexattr\_t}, that
contains the ceiling of the mutex.

To apply the Priority Ceiling protocol to a task, you need to tell the Module
what is the priority of that task \footnote{Also a task that have to be
scheduled using the PC rules but without using any PC mutex must declare its
priority!}. That information is given ti the Module using a Resource Model of
type \texttt{PC\_RES\_MODEL} at task creation time (in other words, to the
\texttt{task\_createn} primitive). That model have to be previously initialized
with the priority of the task.

Note that the priority value used by the PC Module may differ from
the priority of the scheduling algorithm that really schedule the
tasks. Typically, priorities are set to the same (or equipollent)
values.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
\begin{verbatim}
#include <modules/pc.h>
...

mutex_t m1,m2;
...

void *demo(void *arg)  {
    ...

    mutex_lock(&m1);

    /* critical section of m1 */
    ...

    mutex_unlock(&m1);
    ...

    mutex_lock(&m1);

    /* only m1 locked */
    ...

    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...

    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...

    return 0;
}
...

int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;

    PC_mutexattr_t a;
    PC_RES_MODEL r;

    /* Initialize the SRP mutexes */
    PC_mutexattr_default(a,1); /* 1 is the pr. level */
    mutex_init(&m1,&a);
    mutex_init(&m2,&a);
    ...

    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    PC_res_default_model(r, 1); /* set the task Priority */

    p0 = task_create("DEMO", demo, &m, &r);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

The Module also provides three functions that are used to
implement similar POSIX functions. Typically the user does not
need to call them.

\texttt{int PC\_get\_mutex\_ceiling(const mutex\_t *mutex, DWORD
*ceiling);}

This function gets the ceiling of a PC mutex, and it have to be
called only by a task that owns the mutex. Returns -1 if the mutex
is not a PC mutex, 0 otherwise.

\texttt{int PC\_set\_mutex\_ceiling(mutex\_t *mutex, DWORD
ceiling, DWORD *old\_ceiling);}

This function sets the ceiling of a PC mutex, and it have to be
called only by a task that owns the mutex. Returns -1 if the mutex
is not a PC mutex, 0 otherwise.

\texttt{void PC\_set\_task\_ceiling(RLEVEL r, PID p, DWORD
priority);}

This function sets the priority of a task.

\paragraph{Note:}

The Real-Time Literature typically found a feasibility test for
the scheduling only in the case that all hard tasks use the PC
protocol. Note that the Module is written in a way that only the
tasks that declared their Priority will use the PC protocol. If a
task that does not have a Priority, it is not scheduled using the
PC protocol, also if it is inserted in the same scheduling queue
of PC tasks.

\paragraph{Note:}

A task can use PC mutexes with other mutexes with different
protocol (for example, PI, SRP, NOP mutexes). We don't know the
behaviour of that choice, but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/pc/*}

\paragraph{Implementation hints:}

The PC Module uses the shadow mechanism to implement its
behaviour. It keeps track of all the locked mutexes to block
(setting the shadow field to the mutex owner) a task that requires
a lock on a mutex with ceiling less than the system ceiling. When
unlocking, all the shadows are reset. At that point they will try
again to reaquire the mutex, that time starting from the highest
priority task in the scheduling queue.

%----------------------------------------------------------------------------
\section{PI (Priority Inheritance)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

None.

\paragraph{Description:}

This Module implements the Priority Inheritance mechanism. This
mechanism can be easily applied to Fixed Priority Scheduling to
bound blocking times.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
ends and it owns one or more PI mutexes.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{PI\_register\_module();}

The PI protocol uses the default mutex mechanism provided by the
Kernel. In that way, the PI behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a PI mutex, you need to call \texttt{mutex\_init()}
passing a previously initialized \texttt{PI\_mutexattr\_t}.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
\begin{verbatim}
#include <modules/pi.h>
...

mutex_t m1,m2;
...

void *demo(void *arg) {
    ...

    mutex_lock(&m1);

    /* critical section of m1 */
    ...

    mutex_unlock(&m1);
    ...

    mutex_lock(&m1);

    /* only m1 locked */
    ...

    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...

    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...

    return 0;
}
...

int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;

    PI_mutexattr_t a;

    /* Initialize the SRP mutexes */
    PI_mutexattr_default(a);
    mutex_init(&m1,&a);
    mutex_init(&m2,&a);
    ...

    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    p0 = task_createn("DEMO", demo, &m, NULL);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

\paragraph{Note:}

A task can use PI mutexes with other mutexes with different
protocol (for example, SRP, PC, NOP mutexes). We don't know the
behaviour of that choice, but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/pi/*}

\paragraph{Implementation hints:}

This is the simplest protocol that can be implemented using the
shadows mechanism. The implementation set the shadow field when a
task blocks, and reset it when the mutex is unlocked. At that
point, the highest priority free task will lock the mutex.

%----------------------------------------------------------------------------
\section{SEM (POSIX Semaphores)}
%----------------------------------------------------------------------------

\paragraph{Description:}

This module implements the POSIX Semaphores as described in the
Volume I of the User Manual.

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{SEM\_register\_module();}

\paragraph{Files:}

\texttt{modules/sem/*}

\paragraph{Implementation hints:}

The implementation uses a fixed number of semaphores (note that
Internal Semaphores does not!). Note the use of
\texttt{task\_testcancel()} to implement the cancellation points.

%----------------------------------------------------------------------------
\section{SRP (Stack Resource Policy)}
%----------------------------------------------------------------------------

\paragraph{Resource Models Accepted:}

\begin{description}
\item [SRP\_RES\_MODEL]- Preemption levels. This model have to be
used to tell to the SRP Module that a task have to be scheduled
following the SRP rules. The model can be passed at creation time
to more than one task, and it only contains the preemption level
information.
\end{description}

\paragraph{Description:}

\emph{Stack Resource Policy} (SRP) is a mutual exclusion mechanism
suitable for hard real-time tasks, that can be used with static or
dynamic scheduling algorithms. Its main feature is the property
that a task is blocked not when it tries to use the resource, but
when it tries to preempt another task owning the shared resource.
This early blocking simplifies the protocol implementation and
reduces the number of context switches, increasing the system
efficiency.

This SRP implementation provides a simplified version of the protocol, suitable
only for single-unit resources, that defines a particular behaviour for the
\texttt{mutex\_XXX} primitives. Moreover, it is implemented using the shadows
mechanism (described in the S.Ha.R.K. architecture manual), so there is no
restriction on the Task Models of the tasks that will use SRP \footnote{However,
note that a schedulability test is only available for EDF and RM schedulers.}.

SRP is implemented associating a dynamic priority $p(\tau)$ and a
preemption level $\pi(\tau)$ to each task $\tau$. If an EDF
scheduler is used to schedule the tasks that use SRP, we can say
that the priority $p(\tau)$ of task $\tau$ is proportional to
$1/d$, where $d$ is the task's absolute deadline, while the
preemption level $\pi(\tau)$ is proportional to $1/D$, where $D$
is the tasks's relative deadline.

Each resource is assigned a dynamic \emph{priority ceiling}
$C_{R}$, defined as:
\[
C_{R}=max\{0\},\;\{\pi(\tau):R\in R(\tau)\, and\, Rsbusy\}
\]

\noindent where $R(\tau)$ is the set of all resources used by task
$\tau$. According to this definition, if a resource is free, its
ceiling is 0; if a resource is busy, its ceiling is the maximum
among the preemption levels of tasks using it. A \emph{System
Ceiling} $\Pi_{S}$ is also defined as the maximum ceiling among
all the resources:
\[
\Pi_{S}\;=\; max_{r}\{ C_{r}\;:\; r=1,\ldots,m\}.
\]

Starting from these definitions, the SRP works according to the
following rule:

\begin{quote}
\emph{The execution of a task is delayed until it becomes the task
having the highest priority and its preemption level is strictly
greater than the system ceiling.}
\end{quote}

Two tests are needed to allow a task to execute: a test on its
priority (i.e., the deadline, which is dynamically assigned) and a
test on the preemption level (which is statically determined).

The SRP protocol ensures that a task $\tau$, once started, cannot
be blocked on any resource until it terminates. Consequently, SRP
avoids unbounded priority inversion, blocking chains, and
deadlocks. It also reduces the number of context switches and
simplifies the implementation of the mechanism.

Since the SRP may be applied on various Scheduling Modules with
different scheduling policies, no guarantee or blocking time
calculations are performed by the Kernel.

The tasks that use SRP mutexes must declare the use of a shared
resource, using the provided resource modules.

Finally, note that this implementation of SRP is NOT compatible
with the join primitive. If a task that uses SRP mutexes calls
\texttt{task\_join} or \texttt{pthread\_join}, the result is
undefined.

\paragraph{Exceptions Raised:}

\begin{description}
\item [XMUTEX\_OWNER\_KILLED]This exception is raised when a task
ends and it owns one or more SRP mutexes. \item
[XSRP\_UNVALID\_LOCK]This exception is raised when a task try to
lock a srp mutex but it don't have the privilege.
\end{description}

\paragraph{Usage:}

To register this module, just put this line into the
\texttt{\_\_kernel\_register\_levels\_\_} function:

\texttt{SRP\_register\_module();}

The SRP protocol uses the default mutex mechanism provided by the
Kernel. In that way, the SRP behaviour for a mutex can be set at
run-time, and the applications can choose the protocol of their
mutexes without changing the task source code.

To initialize a SRP mutex, you need to call \texttt{mutex\_init()}
passing a previously initialized \texttt{SRP\_mutexattr\_t}.

To use a SRP mutex, you need to tell the Module two kind of
informations:

\begin{itemize}
\item First, every task that have to be scheduled following the SRP rules must
have a (fixed) preemption level \footnote{Also a task that have to be scheduled
using the SRP rules but without using any SRP mutex must declare its preemption
level!}.
\item Second, every task must declare the mutexes that it will use during its
life.
\end{itemize}

All the two informations have to be given to the Module using
Resource Models.

To set a task preemption level you need to pass an
\texttt{SRP\_RES\_MODEL} at task creation time (in other words, to
the \texttt{task\_createn} primitive). That model have to be
previously initialized with the preemption level of the task.

To declare that a task will use a particular mutex, you have to
pass another Resource Model at task creation time. The Model you
need to pass is returned by the following function:

\texttt{RES\_MODEL *SRP\_usemutex(mutex\_t *m);}

where \texttt{m} is the SRP mutex the task will use.

In the following example, the demo task uses two resources,
labeled with \texttt{m1} and \texttt{m2}, and accesses three
different critical sections:

\begin{tt}
 
\begin{verbatim}
 #include <modules/srp.h>
...

mutex_t m1,m2;
...

void *demo(void *arg) {
    ...

    mutex_lock(&m1);

    /* critical section of m1 */
    ...

    mutex_unlock(&m1);
    ...

    mutex_lock(&m1);
    /* only m1 locked */
    ...

    mutex_lock(&m2);

    /* m1 and m2 locked */
    ...

    mutex_unlock(&m2); /* NOTE: first m2, then m1! */
    mutex_unlock(&m1);
    ...

    return 0;
}
...

int main(int argc, char **argv) {
    HARD_TASK_MODEL m;
    PID p0, p1, p2;

    SRP_mutexattr_t a;
    SRP_RES_MODEL r;

    /* Initialize the SRP mutexes */

    SRP_mutexattr_default(a);
    mutex_init(&m1,&a);
    mutex_init(&m2,&a);
    ...

    /* Create the task */
    hard_task_default_model(m);
    hard_task_def_mit(m, 1000000);
    hard_task_def_wcet(m, 80000);
    SRP_res_default_model(r, 3); /* set the task Preemption level */
    p0 = task_createn("DEMO", demo, &m, &r, SRP_usemutex(&m1),
SRP_usemutex(&m2), NULL);
    ...
}
\end{verbatim}
\end{tt}

Critical sections must be properly nested (like Chinese boxes):
hence the order of the \texttt{mutex\_unlock(m1)} and
\texttt{mutex\_unlock(m2)} primitives cannot be changed without
modifying the corresponding \texttt{mutex\_lock()}.

\paragraph{Note:}

The Real-Time Literature typically found a feasibility test for the scheduling
only in the case that all hard tasks use the SRP protocol. Note that the Module
is written in a way that only the tasks that declared their Preemption Level
will use the SRP protocol. If a task that does not have a Preemption Level
\footnote{i.e., it was created without passing a \texttt{SRP\_RES\_MODEL} to the
\texttt{task\_createn} primitive.}, it is not scheduled using the SRP protocol,
also if it is inserted in the same scheduling queue of SRP tasks.

\paragraph{Note:}

A task can use SRP mutexes with other mutexes with different
protocol (for example, PI, PC, NOP mutexes). We don't know the
behaviour of that choice, but, if you want to try, it works!

\paragraph{Files:}

\texttt{modules/srp/*}

\paragraph{Implementation hints:}

Notes about the implementation of SRP are inserted in the heading
the source file \texttt{modules/srp/srp.c}.

%----------------------------------------------------------------------------
\chapter{File system Modules}
%----------------------------------------------------------------------------

%----------------------------------------------------------------------------
\section{BD\_EDF}
%----------------------------------------------------------------------------

TBD

%----------------------------------------------------------------------------
\section{BD\_PSCAN}
%----------------------------------------------------------------------------

TBD

\printindex{}

\bibliographystyle{alpha}
\bibliography{../common/biblio}

\end{document}