Subversion Repositories shark

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

\chapter{Kernel Overview}

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

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

\section{Scheduling Architecture}

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

S.Ha.R.K. is a research kernel expressly designed to help the

implementation and testing of new scheduling algorithms, both for

the CPU and for shared resources. In order to achieve independence

between applications and scheduling algorithms (and between the

schedulers and the kernel), S.Ha.R.K. is based on a \emph{Generic

Kernel}, which does not implement any particular scheduling

algorithm, but postpones scheduling decisions to external

entities, the \emph{scheduling modules}. In a similar fashion, the

access to shared resources is coordinated by \emph{resource

modules}. External modules can implement periodic scheduling

algorithms, soft task management through real-time servers,

semaphore protocols, and resource management policies. The modules

implementing the most common algorithms (such as RM, EDF, Round

Robin, and so on) are already provided, and it is easy to develop

new modules. A scheme of the kernel architecture is depicted in

Figure \ref{oview_Fig_KernelArchitecture}.

\begin{figure}

\begin{center}

\includegraphics[width=8cm]{images/oview_Architecture.eps}

\end{center}

\label{oview_Fig_KernelArchitecture}

\caption{The S.Ha.R.K. Architecture}

\end{figure}

The OS Lib layer implements an abstraction of a generic machine

capable of exporting some services, as for example context

switching, time management, interrupts handling, and a subset of

the run-time C library. For detailed information about the OS Lib,

see \cite{Abe00-1}\cite{Abe00-2}.

The Generic Kernel provides the mechanisms used by the modules to

perform scheduling and resource management thus allowing the

system to abstract from the specific algorithms that can be

implemented. The Generic Kernel simply provides the primitives

without specifying any algorithm, whose implementation resides in

external modules, configured at run-time with the support of the

\emph{Model Mapper} (see Section \ref{oview_Models}).

Another important component of the Generic Kernel is the Job

Execution Time (JET) estimator, which monitors the computation

time actually consumed by each job. This is a generic mechanism,

independent from the scheduling algorithms, that can be used for

statistical measurements, for enforcing temporal protection, or

for resource accounting (see Section \ref{Kernel_Jet}).

The API is exported through the \emph{Libraries}, which use the

Generic Kernel to support some common hardware devices (i.e.,

keyboard, sound cards, network cards, graphic cards) and provide a

compatibility layer with the POSIX Real-time Controller System

Profile \cite{POSIX1003.13}.

An Application can be considered as a set of cooperating tasks \footnote{In this

document, a process is a set of computations performed in a private address

space. A thread is a single execution flow in a process. Each thread is

identified by an unique ID, plus some specific parameters. The term Task is used

as a synonymous of the term thread.} that share a common address space. There is

no memory protection implemented into the Kernel. Intertask communication is

performed using shared memory buffers accessed through some synchronization

mechanisms (as mutexes, condition variables, semaphores, CAB, message queues).

Each task is characterized by a Task Model, some optional Resource Models, and a

body. The body of a task is simply a C function with the prototype \texttt{void

*body(void *arg)}.

An Application can use the following sets of functions:

\begin{itemize}

\item The functions exported by the OS Lib;

\item The Generic Kernel primitives;

\item Some Module-dependent functions;

\item Some functions exported by libraries, device drivers, or the standard C

library;

\item The library implementing of the POSIX standard interface.

\end{itemize}

Each Module consists of a set of data and functions used for

implementing a specific algorithm, whose implementation is

independent from the other modules in the system, thus realizing a

trade-off between user-level and in-kernel schedulers. In this

way, many different module configurations are possible. For

example, a Polling Server can either work with a RM or an EDF

scheduling Module without any modification.

Currently, S.Ha.R.K. provides two basic modules:

\begin{itemize}

\item modules that implement scheduling algorithms and aperiodic service

policies (Scheduling Modules);

\item modules that manage shared (hardware or software) resources (Resource

Modules);

\end{itemize}

All resource access protocols, such as Priority Inheritance, are

implemented as a mutex module whose interface is derived from the

resource module interface. A POSIX mutex interface is also

provided on top of the implemented protocols.

Each type of Module provides a well defined interface to

communicate with the Generic Kernel (user programs do not directly

interact with the modules). The interface functions are called by

the Generic Kernel to implement the kernel primitives. When

modules need to interact with the hardware (for example, the

timer), they can use the service calls provided by the Generic

Kernel.

Finally, each Module has some unique identifiers to allow the

implementation of some consistency checks (for example, a module

that implements a Total Bandwidth Server cannot work with Rate

Monotonic).

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

\section{QoS Specification}

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

\label{oview_Models} One of the goals of S.Ha.R.K. is to allow the

user to easily implement and test novel scheduling algorithms. In

particular, the kernel has been designed with the following

objectives:

\begin{itemize}

\item achieve independence between the kernel mechanisms and the

scheduling policies for tasks and resource management; \item

configure the system at run-time by specifying the algorithms to

be used for task scheduling and resource access; \item achieve

independence between applications and scheduling algorithms.

\end{itemize}

These requirements are particularly useful for comparing the

performance of similar algorithms on the same application. In

fact, module independence allows the user to configure and test

applications without recompile them, only relinking them.

Independence between applications and scheduling algorithms is

achieved by introducing the concept of \emph{model}. Each task

asks the system to be scheduled according to a given Quality of

Service (QoS) specified by a model. In other words, a model is the

entity used by S.Ha.R.K. to separate the scheduling parameters

from the QoS parameters required by each task. In this way, the

kernel provides a common interface to isolate the task QoS

requirements from the real scheduler implementation.

Models are descriptions of the scheduling requirements expressed

by tasks. S.Ha.R.K. provides three different kinds of models:

\begin{description}

\item [Task~Models.]A task model expresses the QoS requirements of

a task for the CPU scheduling. Requirements are specified through

a set of parameters at task creation time. Some of the task

requirements are mandatory (e.g., the stack size of a task), while

others depend on the specific task model (e.g., a deadline). For

this reason, all task models are characterized by a general common

part, which can be extended by a model-dependent part. Usually,

the model-dependent part abstracts from a specific scheduling

algorithm (for instance, the concept of period or deadline is

independent from a specific algorithm like EDF or RM). The task

models have a function similar to the \texttt{pthread\_attr\_t}

structure defined in the POSIX standard. \item [Resource~Models.]A

resource model is used to define the QoS parameters relative to a

set of shared resources used by a task. For example, the resource

model can be used to specify the semaphore protocol to be used for

protecting critical sections (e.g., Priority Inheritance, Priority

Ceiling, or SRP). In other cases, the resource model can be used

to specify a hardware resource scheduling algorithm (e.g. a File

System Scheduling Algorithm). \item [Mutex~Models.]When a mutex

semaphore is created, these Models are used to specify the

resource access protocol to be used, in a way similar to that done

with Task Models. The mutex models have a function similar to the

\texttt{pthread\_mutexattr\_t} structure defined in the POSIX

standard.

\end{description}

Each task is characterized by a single mandatory QoS parameter,

the \emph{task criticality} (hard, soft, firm, non real-time, and

so on). This parameter belongs the common part of the task model,

together with a \emph{model identifier} and some other parameters,

such as the stack size.

Each task model is implemented as a C structure, in which the

first field is the model identifier, the next fields are the

mandatory parameters and the last field is a sequence of bytes

containing the model-dependent parameters, that only the specific

module can interpret. Resource models are completely generic, and

depend on the resource they describe: the only mandatory parameter

is the model identifier.

Models are required to make the generic kernel independent from

the implemented scheduling algorithms: since the generic kernel

does not implement any algorithm, it does not know how to serve a

task but invokes a service request to scheduling entities realized

as external \emph{modules}. Hence, the generic kernel does not

interpret the models, but just passes them to the modules; each

module, by reading the common part of the model, can verify

whether the task can be served or not.

Using models an application is able to specify the requested QoS,

independently from the modules used into the system. For example,

an application that creates a task using an Hard Task Model can be

executed on an EDF, a RM, or a Deadline Monotonic

Module.

\begin{figure}

\begin{center}

\includegraphics[width=11cm]{images/oview_QOSMapper.eps}

\end{center}

\label{oview_Fig_QOSMapper}

\caption{The interaction between the Model Mapper and the QOS Mapper.}

\end{figure}

Task creation works as follows (see Figure

\ref{oview_Fig_QOSMapper}): when an application issues a request

to the kernel for creating a new task, it also sends the model

describing the requested QoS. A kernel component, namely the

\emph{model mapper}, passes the model to a module, selected

according to an internal policy, and the module checks whether it

can provide the requested QoS; if the selected module cannot serve

the task, the model mapper selects a different module. When a

module accepts to manage the task described by the specified

model, it converts the model's QOS parameters into the appropriate

scheduling parameters. Such a conversion is performed by a module

component, called the \emph{QoS Mapper}. For example, a hard

periodic task may have a model consisting of a period and a

worst-case execution time (WCET); when a task is created with that

model, the EDF module will convert such parameters into deadlines,

reactivation times, and so on. In general, a module can manage

only a subset of the models, and the set of models is not limited

by the kernel. This is possible because the kernel does not handle

the models, but it simply passes them to the Model Mapper, that

selects a module and passes the model to that module. Currently,

the Model Mapper uses a simple strategy, according to which

modules are selected based on fixed priorities (see Section

\ref{oview_Module_Organization} for more details).

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

\section{Scheduling Modules}

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

Scheduling Modules are used by the Generic Kernel to schedule

tasks, or serve aperiodic requests using an aperiodic server. In

general, the implementation of a scheduling algorithm should

possibly be independent on resource access protocols, and handle

only the scheduling behavior. Nevertheless, the implementation of

an aperiodic server relies on the presence of another scheduling

module, called the Master Module

\begin{figure}

\begin{center}

\includegraphics[width=4cm]{images/oview_Server_e_Master.eps}

\end{center}

\label{oview_Fig_MasterModule}

\caption{An aperiodic Server that inserts its tasks into a master module.}

\end{figure}

(for example, a Deferrable Server can be used if the base

scheduling algorithm is RM or EDF, but not Round Robin; see Figure

\ref{oview_Fig_MasterModule}). Such a design choice reflects the

traditional approach followed in the literature, where most

aperiodic servers insert their tasks directly into the scheduling

queues of the base scheduling algorithm. Again, our modular

approach masks this mechanism with the task models: an aperiodic

server must use a task model to insert his tasks into the Master

Module.

The Model Mapper distributes the tasks to the registered modules

according to the task models the set of modules can handle. For

this reason, the task descriptor includes an additional field

(\texttt{task\_level}), which points to the module that is

handling the task.

When the Generic Kernel has to perform a scheduling decision, it

asks the modules for the task to schedule, according to fixed

priorities: first, it invokes a scheduling decision to the highest

priority module, then (if the module does not manage any task

ready to run), it asks the next high priority module, and so on.

In this way, each module manages its private ready task list, and

the Generic Kernel schedules the first task of the highest

priority non empty module's queue.

A Scheduling Module must include all the data structures needed.

It can be thought as an object in an Object oriented language;

this implies that many instances of a module can be created (for

example, many TBS servers with different bandwidth).

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

\subsection{Module Organization}

\label{oview_Module_Organization}

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

The Scheduling Modules are organized into levels, one Module for

each level. These levels can be thought as priority scheduling

levels (index 0 has the maximum priority).

Modules are selected for scheduling by the Model Mapper by a fixed

priority strategy. When a task is given to a module, the module

\emph{owns} the task. The \texttt{task\_level} field of the

generic task descriptor is used to save the level index of the

Module that handles the task (see Section

\ref{KernSupport_Task_descriptor}).

Each Scheduling Module handles all the events that belong to its

owned tasks. A task owned by a module is scheduled in background

with respect to the tasks owned by a Module with higher level

index. For example, in Figure \ref{oview_Levels}, the tasks

\emph{scheduled}%

\footnote{Note that the word \emph{scheduled} is emphasized: the

tasks \emph{scheduled} by a Module are the tasks owned by the

Module itself and the tasks that other modules have inserted in

it.%

} by the XXX Scheduling Module are run in foreground; the tasks

scheduled by the WWW Module run in background with respect to

those of the XXX and YYY Modules, and in foreground with respect

to the tasks scheduled by the ZZZ Module.

\begin{figure}

\begin{center}

\includegraphics[width=6cm]{images/oview_Levels.eps}

\end{center}

\label{oview_Levels}

\caption{Kernel Level Organization.}

\end{figure}

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

\subsection{Sample scheduling architectures}

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

The approach followed in the organization of the Scheduling

Modules is very versatile and allows to implement different Kernel

configurations. In the following, some typical scheduling

architectures are described.

\begin{description}

\item [Fixed~Priority~Scheme.]This is the most typical approach

used in the real-time systems (see Figure

\ref{oview_Power_FixedPriority}). In this example, hard tasks

(periodic and sporadic) are served at the highest priority,

whereas aperiodic tasks are handled by a Sporadic Server. At the

lowest priority level non-realtime tasks can be handled by a Round

Robin scheduling

policy.

\begin{figure}

\begin{center}

\includegraphics[width=7cm]{images/oview_Power_FixedPriority.eps}

\end{center}

\label{oview_Power_FixedPriority}

\caption{A fixed priority Module configuration\textit{.}}

\end{figure}

\item [Dual~Priority~Scheme.]This configuration (described in

Figure \ref{oview_Power_DualPriority}) proposes a combination of

modules which were not developed to work together at

implementation time. In this example, the highest priority tasks

are scheduled by the RM with a Deferrable Server linked to it.

Other tasks are scheduled at medium priority using EDF with a

Total Bandwidth Server. At the lowest priority level, non-realtime

tasks can be handled by a Round Robin scheduling scheme.. This

configuration can be used to reduce the jitter of some important

tasks \cite{Dav95}.

\begin{figure}

\begin{center}

\includegraphics[width=7cm]{images/oview_Power_DualPriority.eps}

\end{center}

\label{oview_Power_DualPriority}

\caption{A Dual Priority Module configuration. Note that the TBS Module is put

at the lowest priority level to prevent the TBS algorithm from using the

background time left by other modules.}

\end{figure}

\item [Dynamic~Multiserver.]This example (described in Figure

\ref{oview_Power_Dynamic}) shows how to create a complex

scheduling architecture. In the example, some Hard tasks are

scheduled with a set of aperiodic tasks, each one handled by a

different server. Note that the EDF Module is designed to accept

tasks from a generic Module, independently from the algorithm

implemented by that Module. Note also that in the system there are

many instances of a single module, and each instance can only

manage the tasks that it

owns.

\begin{figure}

\begin{center}

\includegraphics[width=8cm]{images/oview_Power_Dynamic.eps}

\end{center}

\label{oview_Power_Dynamic}

\caption{Dynamic Module Configuration.}

\end{figure}

\item [Timeline~Scheduling.]The example illustrated in Figure

\ref{oview_Power_Timeline} shows a Timeline scheduler integrated

with a fixed priority algorithm, such as RM. Note that S.Ha.R.K.

does not force the developer to use classic approaches, like

prioritary task queues. The Generic Kernel does not impose any

restrictions to developers.

\begin{figure}

\begin{center}

\includegraphics[width=7cm]{images/oview_Power_Timeline.eps}

\end{center}

\label{oview_Power_Timeline}

\caption{A hybrid Timeline-RM approach.}

\end{figure}

\end{description}

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

\subsection{Module Interface}

\label{oview_Module_Interface}

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

The interface functions provided by a scheduling module can be

grouped in two classes: public and private functions. In general,

a scheduling module has an interface that implements a specific

behavior for each event in the system generated by a task.

In the following paragraph the various classes of functions are

explained in a general way. Each function will be then described

in detail in Chapter \ref{CapSchedulingModules}.

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

\subsection{Public Functions}

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

The public functions are those fuctions that are directly called

by the Generic Kernel to implement the behavior of the primitives.

Some of the functions are directly related to the life of a single

task (e.g. task creation, task end), whereas other functions are

related to the module as a whole (the scheduler, and the

acceptance test).

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

\subsection{Private Functions}

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

On the other side, a module can export an interface to the public

part of the same or of another module. For example, an EDF Module

can export an interface (smaller than the Public Functions) that

allows a generic aperiodic server to insert tasks in the EDF reqdy

queue.

That is, Private Functions are called ONLY by other Public and

Private Functions. They are NEVER called by the Generic Kernel.

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

\subsection{An Example}

\label{oview_Example}

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

In this paragraph an useful example is explained to show the use

of the various functions of a Scheduling Module Interface. The

interface will be described in detail in Chapter

\ref{CapSchedulingModules}.

\begin{figure}

\begin{center}

\includegraphics[width=8cm]{images/oview_LevelExample.eps}

\end{center}

\label{oview_Fig_Example}

\caption{Configuration of the example in Section \ref{oview_Example}.}

\end{figure}

The example (see Figure \ref{oview_Fig_Example}) considers a

configuration made using two scheduling modules, registered in the

first two levels:

\begin{itemize}

\item at Level 0 there is a Module that implements a generic

Scheduling Algorithm; \item at Level 1 there is a Module that

implements a generic Aperiodic Server (that inserts his tasks into

the first Module).

\end{itemize}

Then, we consider two tasks in the system:

\begin{itemize}

\item Task A is a task created into the Module that implements the

scheduling algorithm (registered at level 0); therefore its

\texttt{task\_level} = 0. \item Task B is a task created into the

Module that implements the aperiodic server (registered at level

1); therefore its \texttt{task\_level} = 1. Moreover, the task B

is inserted into the level 0 using level-0's private functions.

\end{itemize}

Both the tasks are scheduled by the level 0 public\_scheduler:

task A because it was created in that level; task B because it was

inserted into the level 0 through the level-0's private functions.

When the scheduling procedure is called, the Generic Kernel

scheduler will call the public\_scheduler, stating from that of

the Module Registered at level 0. In this case, the level 0

public\_scheduler will choose which task really schedule between A

and B. If task A is selected, the Generic Kernel will call the

public\_dispatch of the level 0 (because Task A's

\texttt{task\_level} is 0). If task B is selected, the Generic

Kernel will call the public\_dispatch of the level 1 (because Task

A's \texttt{task\_level} is 1). To handle the public\_dispatch

event that function will call the level-0 private\_dispatch of

Level 0.

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

\section{Resource Modules}

\label{oview_Moduli_GestioneRisorse}

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

Resource Modules are normally used to implement some parts that do

not directly interact with task scheduling, but need some

information that has to be provided at task creation and

termination time.

Such Modules are, for example, those that implement shared

resource access protocols (they require some parameters like

system ceiling, the set of mutexes used by a task, etc.), or the

Modules that implements a file system that supports the

specification of a disk bandwidth to be guaranteed to each task.

Like Scheduling Modules, also Resource Modules are organized into

levels, one module for each level. The level number influences

only the order in which events are notified to modules.

The only events that can be notified to a Resource Module are the

creation and the termination of a task. At creation time an

application can specify one or more Resource Models, which will be

handled by the modules registered in the Kernel.

Note that the Resource Module interface is not complete, because

in general a Module will need a larger interface which depends on

the resource that the module itself handles. Usually, the Modules

extends the interface used by the Generic Kernel, by adding a set

of new functions, in a way similar to that used in an Object

Oriented Language when a class is inherited from another base

class.

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

\section{Shared Resource Access Protocols}

\label{oview_Shadows}

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

S.Ha.R.K. is based on a shared memory programming paradigm, so

communication among tasks is performed by accessing shared

buffers. In this case, tasks that concurrently access the same

shared resource must be synchronized through \emph{mutual

exclusion}: real-time theory \cite{Sha90} teaches that mutual

exclusion through classical semaphores is prone to \emph{priority

inversion}. In order to avoid or limit priority inversion,

suitable shared resource access protocols must be used.

As for scheduling, S.Ha.R.K. achieves modularity also in the

implementation of shared resource access protocols. Resource

modules are used to make resource protocols modular and almost

independent from the scheduling policy and from the others

resource protocols. Each resource module exports a common

interface, similar to the one provided by POSIX for mutexes, and

implements a specific resource access protocol. A task may also

require to use a specified protocol through a resource model.

Some protocols (like Priority Inheritance or Priority Ceiling)

directly interact with the scheduler (since a low-priority task

can inherit the priority from a high-priority task), making the

protocol dependent on the particular scheduling algorithm (see

Figure \ref{oview_Fig_Idea1}).

\begin{figure}

\begin{center}

\includegraphics[width=5cm]{images/oview_Fig_Idea1.eps}

\end{center}

\label{oview_Fig_Idea1}

\caption{Priority inheritance implemented with an out of order queue insertion:

(1) Ta blocks when it tries to access a resource; (2) Ta goes in the blocked

queue; (3) Tb replaces the position of the high priority task.}

\end{figure}

Although a solution based on a direct interaction between the

scheduler and the resource protocol is efficient in terms of

runtime overhead, it limits the full modularity of the kernel,

preventing the substitution of a scheduling algorithm with another

one handling the same task models (for example, Rate Monotonic

could be replaced by the more general Deadline Monotonic

algorithm).

To achieve full modularity, the S.Ha.R.K. Generic Kernel supports

a generic priority inheritance mechanism independent from the

scheduling modules. Such a mechanism is based on the concept of

\emph{shadow tasks}. A shadow task is a task that is scheduled in

place of the task selected by the scheduler. When a task is

blocked by the protocol, it is kept in the ready queue, and a

shadow task is binded to it; when the blocked task becomes the

first task in the ready queue, its binded shadow task is scheduled

instead. In this way, the shadow task executes as if it

{}``inherited'' the priority of the blocked tasks, but no

inheritance takes place, thus decoupling the implementation of the

scheduling algorithm from that of the shared resource access

protocol (see Figure \ref{oview_Fig_Idea2}).

\begin{figure}

\begin{center}

\includegraphics[width=5cm]{images/oview_Fig_Idea2.eps}

\end{center}

\label{oview_Fig_Idea2}

\caption{Priority Inheritance implemented through shadows: (1) Ta blocks when it

tries to access a resource; (2) Ta indicates a shadow task and remains into the

ready queue; (3) Tb is scheduled in place of Ta.}

\end{figure}

To implement this solution, a new field \texttt{shadow} is added

to the generic part of the task descriptor. This field points to

the shadow task (see Figure \ref{oview_Fig_Shadow_Significato}).

\begin{figure}

\begin{center}

\includegraphics[width=5cm]{images/oview_Fig_Shadow1.eps}

\end{center}

\label{oview_Fig_Shadow_Significato}

\caption{Meaning of the Task Descriptor's \texttt{shadow} field.}

\end{figure}

Initially, the shadow field is equal to the task ID (no

substitution; see Figure \ref{oview_Fig_Shadow_Typical}).

\begin{figure}

\begin{center}

\includegraphics[width=2cm]{images/oview_Fig_Shadow2.eps}

\end{center}

\label{oview_Fig_Shadow_Typical}

\caption{Typical scenario with no substitution.}

\end{figure}

When a task blocks on a shared resource, its shadow field is set

to the task ID of the task holding that resource (see Figure

\ref{oview_Fig Shadow_Blocking}).

\begin{figure}

\begin{center}

\includegraphics[width=5cm]{images/oview_Fig_Shadow3.eps}

\end{center}

\label{oview_Fig Shadow_Blocking}

\caption{In this scenario a blocked task waits for a resource; the blocking task

inherits its priority.}

\end{figure}

In general, a graph can grow from a blocking task (see Figure

\ref{oview_Fig_Shadow_DAG}).

\begin{figure}

\begin{center}

\includegraphics[width=5cm]{images/oview_Fig_Shadow4.eps}

\end{center}

\label{oview_Fig_Shadow_DAG}

\caption{Using the shadow mechanism a graph can grow...}

\end{figure}

In this way, when the blocked task is scheduled, the blocking

(shadow) task is scheduled, thus allowing the scheduler to

abstract from the resource protocol. This approach has also the

benefit of allowing a classical deadlock detection strategy:

cycles have to be searched in the shadow graph when a

\texttt{shadow} field is set.

Using this approach, a large number of shared resources protocols

can be implemented in a way independent from the scheduling

implementation. The classical approach, however, can also be

pursued. In addition to this method, a classical synchronization

mechanism is available (see the User Manual for informations about

semaphores interfaces).

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

\section{The Generic Kernel}

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

The \textit{Generic Kernel} implements the primitives which form

the interface if with the Libraries and the User Applications.

The term Generic is used because the kernel is developed

abstracting from the implementation of a particular scheduling

algorithm. This means that it does not provide the concept of

priority, deadline, task queues, and so on. All the peculiarities

of an algorithm are encapsulated in the Modules, interacting with

the Kernel.

In general Applications use the Kernel through the generic

primitives, asking the Kernel to handle a task set. The Kernel

tries to handle the tasks passing them to the modules according to

the Task Models specified for the tasks. Any module modification

that does not affect the Model interface, does not require any

modification to the Kernel and the Applications.

The generic kernel divides the task set in two parts: the system

tasks and the user tasks. System tasks are used to manage external

devices (like keyboard, mouse, file system, etc.). User tasks are

tasks that belong to the Application.

Moreover, it distinguishes between scheduling and dispatching:

\begin{description}

\item [scheduling]is the activity by which the Generic Kernel asks

a module the indication of the task to be executed; \item

[dispatching]is the activity by which the Generic Kernel orders a

module the execution of a task.

\end{description}

The following section describes some new additions implemented in

the kernel to achieve modularity. They mainly concern the task

descriptor and the task states.

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

\subsection{Task descriptor}

\label{oview_task_descriptor}

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

To have full modularity, the Generic Kernel should not be modified

when implementing a new algorithm.

For this reason the task descriptor is split in several parts: one

generic part, common to all the modules, and a set of parts that

are dependent from the used Modules and are local to the modules.

The generic descriptor part contains all the data used by the

Generic Kernel to implement the generic primitives, like context,

stack address and size, error codes, statistical information, etc.

The generic part does not contain any information like deadlines,

priorities, time slices, reactivation times, etc. These data are

used by specific scheduling algorithms and must be contained in

the corresponding scheduling modules. In particular:

\begin{itemize}

\item The Generic Kernel does not implement a specific scheduling

policy. \item Each instance of a module has a private memory where

it can store information about the owned tasks. \item Each Module

uses the information stored in the generic task descriptor plus

his private information, but not the information of other modules.

\item Typically, an Aperiodic Server does not use the internal

structures of the Master Module, but interacts with it using the

available interface functions.

\end{itemize}

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

\subsection{Task States}

\label{oview_Status}

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

One of the consequences of the modular approach is that many task

states are local to the modules. The Generic Kernel defines only a

subset of the states in which a task can be, giving freedom to the

Modules to create their private subsystem.

In particular, the Generic Kernel defines only the states

described in Table \ref{oview_Table_Kernel_States}.

\begin{table}

\begin{center}\begin{tabular}{|p{2cm}|p{10cm}|}

\hline

\multicolumn{1}{|c|}{State} & Description\\ \hline \hline

\multicolumn{1}{|c|}{FREE} & Descriptor not used\\ \hline

\multicolumn{1}{|c|}{SLEEP \foreignlanguage{english}{  }} & Default state in

which a task go after creation; this is the state in whichthe task returns after

a call to thetask\_sleep primitive\\ \hline

\multicolumn{1}{|c|}{EXE} & State of the task currently being

executed\\ \hline

\multicolumn{1}{|c|}{WAIT\_* \foreignlanguage{english}{ }} & State in which a

task is put after blocking on a synchronizationprimitive\\ \hline

\end{tabular}\end{center}

\label{oview_Table_Kernel_States}

\caption{Task states defined by the Generic Kernel.}

\end{table}

These states must be integrated with other internal states defined

into the Modules. Some typical states implemented in modules are

reported in Table \ref{oview_Table_Modules_States}.

\begin{table}

\begin{center}\begin{tabular}{|p{3cm}|p{10cm}|}

\hline \multicolumn{1}{|c|}{State name}&

Description\\ \hline \hline

\multicolumn{1}{|c|}{READY \foreignlanguage{english}{}}& This is

the classical ready state in which a task waits to be

executed.\\ \hline \multicolumn{1}{|c|}{BLOCKED}&

This is the state of a task blocked on a semaphore.\\

\hline \multicolumn{1}{|c|}{ZOMBIE \foreignlanguage{english}{ }}&

This is the state of a Hard Periodic Task afterhis termination,

when it waits the end of the period tofree his used

bandwidth.\\ \hline \multicolumn{1}{|c|}{LOBBY

\foreignlanguage{english}{  }}& In some implementation of the SRP

protocolthis state is used to postpone the activation of atask

while the system waits that for system ceiling to become

zero.\\ \hline \multicolumn{1}{|c|}{IDLE

\foreignlanguage{english}{}}& This is the typical state in which a

periodic task is putat the end of an instance, to wait for

reactivation at the beginning of the next period.\\

\cline{2-2}

\end{tabular}\end{center}

\caption{\label{oview_Table_Modules_States}Examples of states

defined in the Modules.}

\end{table}

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

\section{Initialization and termination of the system}

\label{oview_Initialization}

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

Before an Application can be executed, the user has to tell the

Generic Kernel the modules used by the system. This is done

through an initialization function in which the specified modules

are registered and initialized.

Normally, the registration creates a non-realtime task, that

initializes some devices and calls the standard C startup function

\texttt{main()}.

When the system ends (because a function like \texttt{sys\_end()}

or \texttt{sys\_abort()} is called) or when the last user task

terminates, all the devices are closed and all the system tasks

are terminated in a clean way.