%----------------------------------------------------------------------------
\chapter{Models}
%----------------------------------------------------------------------------
In this chapter we will described in detail the Models used in the
Generic Kernel. For a general description of the Models see
Section
\ref{oview_Models}.
%----------------------------------------------------------------------------
\section{Data structures}
\label{Modelli_MetodologiaOOP}
%----------------------------------------------------------------------------
The approach used in the definition of the kernel data structures
is similar to that used in Object Oriented Languages.
In fact, there are many situations in which the kernel needs to
define data structures that can be thought as a
\emph{base class},
which will be extended by the Modules that use it. For example,
the Kernel has to manage Task Models to know the stack size of a
task, but it does not have to know fields like priorities,
deadlines, and so on. Such data have to be stored into the task
model, because they represent a QoS specification for the Module
that will handle the task.
For this reason, the Generic Kernel only defines a C
\texttt{struct} that contains only the information that it needs
(and that is common to all the derived structures). If a Module
needs to extend that base class, it creates another
\texttt{struct} whose first field specifies the base class
type
%
\footnote{In this way the derived struct will inherit the fields
from the base
class.
%
}, whereas the other fields extend the base class.
In this way, both the Generic Kernel and the Modules can accept a
pointer to the base class to access the required information.
When the Kernel primitives are used, a pointer to a derived class
is passed instead of a pointer to the base class. Because the
first field of a derived class is of the base class type, the
pointer passed addresses the correct memory structure (the C
structures are stored using the declaration order), and the
Generic Kernel can safely handle the generic part of the
structure.
Viceversa, when a Module interface function receives from the
Generic Kernel a pointer to a base class, it will cast explicitly
the struct to the correct derived type, getting the extensions of
the derived class.
As it can be seen, this approach is a way to implement single
inheritance and polymorphism in the C language.
%----------------------------------------------------------------------------
\section{Task Models }
%----------------------------------------------------------------------------
The Task Models are implemented, as described in the previous
paragraph, through extensions to a base class. In the following
paragraph base class is described with the main extensions to it.
The Task Models that are included in the official distribution of
the Kernel are declared into the file
\texttt{include/kernel/model.h}.
%----------------------------------------------------------------------------
\subsection{\texttt{TASK\_MODEL}}
\label{Modelli_TASK_MODEL}
%----------------------------------------------------------------------------
This is the base structure for the Task Models. Its definition is
showed in Figure
\ref{Modelli_struct_TASK_MODEL}.
\begin{figure}
\begin{center}
\begin{minipage}{6cm}
\begin{verbatim}
typedef struct {
WORD pclass;
LEVEL level;
size_t stacksize;
void *stackaddr;
WORD group;
void *arg;
DWORD control;
} TASK_MODEL;
\end{verbatim}
\end{minipage}
\end{center}
\label{Modelli_struct_TASK_MODEL}
\caption{the \texttt{struct TASK\_MODEL}.}
\end{figure}
In the following paragraph each field of that structure is described.
\begin{description}
\item [\texttt{pclass}]this field contains an identifier that represents the
real (derived) type of the structure. The \texttt{pclass} fields of the derived
class that are included into the official distribution are included into the
file \texttt{include/kernel/model.h}. The \texttt{pclass} field is a 16 bit
integer \item [\texttt{level}]this field identifies a particular level to which
the task must be inserted in preference. 0 means ``all levels'' \footnote{We
recall that the Scheduling Modules are organized in levels. The Task Models are
used when a task is created and they are passed to the Modules to find a Module
that can handle the Model. All the Modules accepts Models in which the
\texttt{level} field are 0 or the level number in which the Module is
registered. In this way it is possible to distinguish Task Models that are
related to different Modules when there are many Modules that can accept the
same Model.}.
\item [\texttt{stacksize}]this is the dimension (in bytes)
required for the stack of the task to be created. The Generic
Kernel provides allocation and deallocation of the stack of the
tasks (only if the parameter \texttt{stackaddr} is not specified).
\item [\texttt{stackaddr}]this is a memory pointer that can be used as stack for
the task to be created. If this parameter is specified, the \texttt{stacksize}
field is ignored when a task is created. The memory pointed by
\texttt{stackaddr} is not deallocated at the termination of the task
(deallocation must be done by the creating task. There is no check on the
dimension of the memory area pointed by \texttt{stackaddr}.
\item [\texttt{group}]the tasks in the Generic
Kernel are divided into groups. The group of a task is specified
when a task is created, using this field. A group is a number that
is common to a set of tasks in the system. This identifier is used
by the primitives \texttt{group\_activate} and
\texttt{group\_kill} to activate or kill a set of tasks in an
atomic way.
\item [\texttt{arg}]the body of a task created into
the system is a function that accepts a \texttt{void~*}
parameter. That parameter is passed at the first activation of a
task and it is specified in this field.
\item [\texttt{control}]this field contains a set of flags that represents
features of the task to be created and represents also some particular states of
a running task. Flags are set by the user at creation time or they can be set by
some primitives. The defined flags are:
\begin{description}
\item [\texttt{USE\_FPU}]This flag is used by the OS Lib to notify
the system that the task uses in its code some floating point
operation. This information is used by the OS Lib to guarantee
that the FPU state is saved at each context switch. \item
[\texttt{NO\_KILL}]If this flag is set the task cannot be killed
through a \texttt{task\_kill} primitive. This flag is also used at
the shutdown of the kernel (see Section \ref{Kernel_TaskUtente}),
and it can be specified only at the task creation. \item
[\texttt{NO\_PREEMPT}]If this flag is set, the running task cannot
be preempted by another task, but it can be interrupted by a
device handler. In other words, the scheduler is disabled. This
flag is modified by the primitives \texttt{task\_preempt} and
\texttt{task\_nopreempt}. \item [\texttt{SYSTEM\_TASK}]If set this
flag marks the task as a system task. It can be specified only at
creation time. The fact that a task is or not a system task
affects the system shutdown (see Section \ref{Kernel_TaskUtente}).
\item [\texttt{JET\_ENABLED}]This flag can be set only at task
creation time and when set specifies that the Generic Kernel must
register the Job Execution Time statistics. \item
[\texttt{TASK\_JOINABLE}]This flag is set if another task can wait
for the task termination through the \texttt{task\_join} primitive
(see Section \ref{Kernel_Join}). \item
[\texttt{STACKADDR\_SPECIFIED}]This flag is set by the creation
primitive if the \texttt{stackaddr} field was specified. At
termination time, if this flag is not set, the stack space is
deallocated by the Kernel; otherwise, the stack space is left
according to the POSIX standard. \item [\texttt{TRACE\_TASK}]This
flag is set if the tracer has to monitor the task events. \item
[\texttt{KILLED\_ON\_CONDITION}]This flag is used in the
implementation of the condition variables. This flag is set by the
Generic Kernel if a task is killed while it is blocked on a
condition variable. In this case the task must be rescheduled to
reaquire the mutex linked to the condition variable. \item
[\texttt{KILL\_ENABLED}]This flag is set if the cancellation (in a
POSIX meaning) is or not enabled. \item
[\texttt{KILL\_DEFERRED}]This flag is set if the cancellation (in
a POSIX meaning) is deferred (the cancellation is asynchronous if
not). \item [\texttt{KILL\_REQUEST}]This flag registers a
cancellation request made with one of these primitives:
\texttt{task\_kill}, \texttt{group\_kill},
\texttt{pthread\_testcancel}. \item [\texttt{CONTROL\_CAP}]This
flag is used in the Scheduling Modules to tell Generic Kernel to
generate an OS Lib event when the running task terminates its
capacity. \item [\texttt{TASK\_DOING\_SIGNALS}]This flag is set by
the Generic Kernel when the task is executing a signal handler.
This flag is used only in the function
\texttt{kern\_deliver\_pending\_signals}, contained in the file
\texttt{kernel/signal.c}. \item [\texttt{FREEZE\_ACTIVATION}]This
flag blocks the task activations done through the primitives
\texttt{task\_activate} and \texttt{group\_activate}.
The flag is modified by the primitives \texttt{task\_block\_activation} and
\texttt{task\_unblock\_activation}.
\item [\texttt{WAIT\_FOR\_JOIN}]This flag is set when a task
terminates, but only if a task is joinable. The flag is used to
register that the task is terminated and it is waiting for someone
to do a join on it to die. \item
[\texttt{DESCRIPTOR\_DISCARDED}]This flag is used in the
implementation of the join primitive, and it is set by the
primitive \texttt{task\_create} to notify that a task descriptor,
whose task is terminated and is waiting for a join, has been
chosen and discarded for the creation of a new task. \item
[\texttt{SIGTIMEOUT\_EXPIRED}]This flag is set for the task
blocked on a \texttt{sigtimedwait} primitive, when the timeout
event fires.
\end{description}
\end{description}
The internal data structures of a \texttt{TASK\_MODEL} should be
used only into the Generic Kernel and into the Modules. For this
reason the system provides a set of macros that can be used to set
the required values in a base class object. In all the described
macros the parameter \texttt{m} is a \texttt{TASK\_MODEL}. The
macro are described below:
\begin{description}
\item [\texttt{task\_default\_model(m,p)}]This macro initializes
the Model \texttt{m} to a default value. The \texttt{pclass} of
\texttt{m} becomes equal to the \texttt{p} parameter. \item
[\texttt{task\_def\_level(m,l)}]This macro specifies the
scheduling level \texttt{l} of Model \texttt{m}. \item
[\texttt{task\_def\_arg(m,a)}]This macro specifies the parameter
passed to the first activation of the task initialized with Model
\texttt{m}. \item [\texttt{task\_def\_stack(m,s)}]This macro is
used to specify the stack dimension of the task initialized with
Model \texttt{m}. \item [\texttt{task\_def\_stackaddr(m,s)}]This
macro is used to specify a memory address pointer to be used as a
stack for the task initialized with Model \texttt{m}. \item
[\texttt{task\_def\_group(m,g)}]This macro is used to specify the
group of tasks initialized with Model \texttt{m}. \item
[\texttt{task\_def\_usemath(m)}]This macro is used to specify that
the task initialized with Model \texttt{m} uses the mathematical
coprocessor. \item [\texttt{task\_def\_system(m)}]This macro is
used to specify that the task that is initialized with Model
\texttt{m} is a system task. \item
[\texttt{task\_def\_nokill(m)}]This macro is used to specify that
the task initialized with Model \texttt{m} cannot be killed. \item
[\texttt{task\_def\_ctrl\_jet(m)}]This macro is used to specify
that the task initialized with Model \texttt{m} requires the
monitoring of the job execution time. \item
[\texttt{task\_def\_joinable(m)}]This macro is used to specify
that the task initialized with Model \texttt{m} can be passed as a
parameter into the join primitive. \item
[\texttt{task\_def\_unjoinable(m)}]This macro is used to specify
that the task initialized with Model \texttt{m} cannot be passed
as parameter into the join primitive. \item
[\texttt{task\_def\_trace(m)}]This macro is used to specify that
the task initialized with Model \texttt{m} is a task for which the
system tracer will register some information about the events
related to it. \item [\texttt{task\_def\_notrace(m)}]This macro is
used to specify that the task initialized with Model \texttt{m} is
a task for which the system tracer will not register any
information.
\end{description}
%----------------------------------------------------------------------------
\subsection{Used conventions}
%----------------------------------------------------------------------------
In normal situations the final user never needs to instantiate an
object of type
\texttt{TASK\_MODEL}, but objects of a type derived
from it. Also the macro described in the previous paragraph cannot
be used directly; instead, there are similar macros redefined for
the derived types.
The standard used in the inheritance of a Model from the base
model are the following:
\begin{enumerate}
\item The name of the derived class is obtained from the name of the base class
by adding a prefix. For example, the task Model for the Soft task is called
\texttt{SOFT\_TASK\_MODEL}.
\item The first field of a derived structure is a structure with name \texttt{t}
and type \texttt{TASK\_MODEL}.
\item The specific parameters added to the models (e.g., period, wcet, etc.) are
inserted as normal fields after the first field. These fields represent a
specification of the Quality of Service required by a task to the system at
creation time. The Scheduling Modules can be structured in a way that they may
use only a subset of the fields of a Model \footnote{For example, to create a
Soft Task Model it is useful to insert two parameters like period and mean
execution time; these parameters are mandarory for the Scheduling Module that
implements CBS, whereas they are ignored by a Scheduling Module that implements
a Polling Server.}. This approach limits the growth of the number of Models and
achieves better independence of the applications from the task models
\footnote{For example, an Application can use a Soft Task Model specifying all
the Model parameters, without knowing which Scheduling Module is really used,
e.g. CBS or Polling Server).}.
\item The macros defined for the \texttt{TASK\_MODEL} struct and described in
the previous paragraph must also be defined for the new model. They should be
rewritten with a name derived from the old name, like the example below:
\begin{center}
\fbox{\tt{
\#define soft\_task\_def\_level(m,l) task\_def\_level((m).t,l)
}}
\end{center}
\item The new model should provide a set of private macros similar to those
provided with the \texttt{TASK\_MODEL} to handle the new fields of the derived
structure. For example, if the new model has a field called \texttt{period}
(that contains for example a reactivation period), the new macro should be
similar to the one shown below:
\begin{center} \fbox{\tt{
\#define soft\_task\_def\_period(m,p) (m).period = (p)
}}
\end{center}
\end{enumerate}
The five rules described above simplify the definition of new
models allowing the user to cut and paste the code of a similar
model and to modify some prefixes.
%----------------------------------------------------------------------------
\subsection{Examples of Models currently integrated into the Kernel}
%----------------------------------------------------------------------------
Currently the Kernel defines a set of Task Models directly derived
from the base TASK
\_MODEL class. In the following paragraphs they
are briefly described (for their definition look in the file
\texttt{include/kernel/model.h}).
\begin{description}
\item [\texttt{HARD\_TASK\_MODEL}]~
This Task Model can be used to model Hard Periodic and Sporadic tasks. A Hard
Periodic Task \footnote{The \texttt{periodicity} field of the model must be set
to \texttt{PERIODIC}.} is a task guaranteed using an activation period and a
wcet \footnote{Worst Case Execution Time.}, whereas a Hard Sporadic Task
\footnote{The \texttt{periodicity} field of the model must be set to
\texttt{APERIODIC}.} is an aperiodic task guaranteed on a minimum interarrival
time and a wcet.
The Model allows the specification of a relative deadline. If not
specified, the deadline is assumed to be equal to the next
reactivation time (as in the classical task model proposed by Liu
and Layland \cite{Liu73}).
The Model also allows a release offset to be specified. This means
that any activation should be delayed by the given offset.
\end{description}
A Module that accepts tasks with this Model can raise the
following exceptions:
\begin{description}
\item [\texttt{XDEADLINE\_MISS}]This exception is raised if the
task misses a deadline.
\begin{description}
\item [\texttt{XWCET\_VIOLATION}]This exception is raised if the
task tries to use more CPU time than declared.
\item [\texttt{XACTIVATION}]This exception is raised if a sporadic task is
activated with a frequency greater than that declared.
\end{description}
\item [\texttt{SOFT\_TASK\_MODEL}]
This Task Model is used to specify the QoS required by a soft
task. A soft task is a periodic or aperiodic task, which is
handled by a server with a given (guaranteed) bandwidth (i.e.,
which allocates a budget Qs every interval Ts).
A soft task can specify, using a specific field, if it wants to save or skip
pending activations. A pending activation occurs when a task is activated before
the end of its current instance \footnote{It may happen when the reserved
bandwidth is less than the maximum task's utilization.}. The Scheduling Modules
can choose whether to handle or not this situation. Pending activations
influence the behavior of the \texttt{task\_sleep} and \texttt{task\_endcycle}
primitives.
The Soft Task Model has also a field which contains a wcet. This
field can be required by some algorithm that requires this
information (for example, the TBS algorithm.
Usually, the Modules that accept the soft task model do not raise
any exception.
\item [\texttt{NRT\_TASK\_MODEL}]
This Task Model is typically used to support non real-time
computations performed by tasks without temporal requirements.
Typical Modules that use these Models are Modules that implement
scheduling algorithms like Round Robin, Proportional Share,
priority scheduling, and POSIX scheduling.
The model has also a field to specify whether a Task have to save
or skip pending activations.
Finally, the Model has two other fields (\texttt{inherit} and \texttt{policy})
used in the implementation of the POSIX scheduling algorithm \footnote{This is
one of the (rare) cases in which the Task Model depends on a specific Scheduling
Module.}.
\item [\texttt{JOB\_TASK\_MODEL}]
This Task Model is normally used by an Aperiodic Server to pass a
task to a Master Module. It is not explicitly used in the
Application code.
This Model extends the Base Model with a deadline and a period. A
Job is a single a task instance which starts and stops without
synchronization points in between.
Typically, an aperiodic server inserts a Job in the Master Module
to ask for service. When that task ends its instance or it blocks
on a synchronization variable, the Job dies and it is newly
recreated when the task is reactivated or when it resumes from
blocking.
There are no fields that specify computation times (i.e., wcet,
met) because the Aperiodic Servers that use that Model generally
handle a budget.
The Model contains another field that specifies whether a Master
Module should raise a deadline exception when a deadline is
reached and the Job is still alive.
\end{description}
%----------------------------------------------------------------------------
\section{Resource Models}
\label{Modelli_RES_MODEL}
%----------------------------------------------------------------------------
The resource Models are implemented in a way similar to the Task
Models. The difference between Task Models and Resource Models is
that it is not possible to group a set of fields common to all
Resource Handlers. For this reason, the C structure that
represents the base class of a Resource Model contains only a
field that provides information about the real type of a Resource
Model. As done for the Task Models, that field is called
\texttt{rclass}.
The Resource Models available in the kernel are used in the
implementation of the Priority Ceiling Protocol and the Stack
Resource Policy.
In the case of Priority Ceiling, the Resource Model only adds a
static priority of the task to be created.
In the case of SRP, the Resource Model only adds the definition of
the Preemption Level of the task.
The Resource Models contained into the official distribution of
the Kernel are included into the file
\texttt{include/kernel/model.h}.
%----------------------------------------------------------------------------
\section{Mutex attributes}
%----------------------------------------------------------------------------
The protocol used by a mutex is decided when the mutex is
initialized (at run time).
To implement the mutex initialization in a modular fashion we
derived a structure, called
\texttt{mutexattr\_t}, from a base
structure similar to that used in the Resource Models
We derived a set of mutex attributes to be used in the
initialization of a mutex (a mutex is contained in a
\texttt{mutex\_t} type, which is similar to the POSIX's
\texttt{pthread\_mutex\_t}).
The Mutex Attributes are declared into the file
\texttt{include/kernel/model.h}.