Subversion Repositories shark

%----------------------------------------------------------------------------

\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}.