Subversion Repositories shark

Rev

Blame | Last modification | View Log | RSS feed

%----------------------------------------------------------------------------
\chapter{The Scheduling Modules\label{CapSchedulingModules}}
%----------------------------------------------------------------------------

This chapter describes the interface of a generic Scheduling
Module, the semantic of the functions that compose the interface,
and a set of conventions used to write the Modules.
%
% Tool: such section does not exists.
%
% For more
% information on the Scheduling Module Architecture see Section
% \ref{ArchDetail_Scheduling_Modules}.

%----------------------------------------------------------------------------
\section{Task Lifecycle\label{SchedModules_Lifecycle}}
%----------------------------------------------------------------------------

To understand the interface of a Scheduling Module, we present a
simple view of the events that refer the life of a task, from its
creation to its end. The Module Interface reflects these events.

Figure \ref{SchedModules_Lifecycle_Base} illustrates a simple
case, in which a task is created, activated, and then preempted by
another task that dies after a while. The following events are
generated:

\begin{figure}
\begin{center}
\includegraphics[width=8cm]{images/schedmodules_lifecycle1.eps}
\end{center}
\label{SchedModules_Lifecycle_Base}
\caption{A simple scenario: tasks i and j are created and activated. Task i is
executed, and, after a while, it is preempted by task j. The numbers in
parenthesis denote the event sequence.}
\end{figure}

\begin{description}
\item [create]This event is generated at task creation. The
Scheduling Module initializes the data structures for the task
activation.

\item [activate]This event is generated when a task is
explicitly activated by a call to a user primitive. That event
authorizes the Scheduling Module to insert the task in the set of
the schedulable tasks.

\item [dispatch]This event is generated when a task, after it has been scheduled
\footnote{The scheduling event is not showed in the figure.}, is actually
executed. The Scheduling Module updates the data structures to register the
execution of the task.

\item [epilogue]This event is generated all the times a task is preempted by
another task \footnote{This event is also raised if the task finishes its time
capacity allocated on its server (for soft tasks).}. The Scheduling Module
usually reinserts the task in the set of the schedulable tasks.

\item [end]this event is generated when a
task ends its execution. The Scheduling Module is authorized to
free the task descriptor and any data allocated for the task.
\end{description}

Note that the POSIX standard does not differentiate between task
creation and task activation; in fact, the
\texttt{pthread\_create} primitive creates and activates directly
a task.

Figure \ref{SchedModules_Lifecycle_endcycle} shows a sample sequence of events
produced by a periodic task.

\begin{figure}
\begin{center}
\includegraphics[width=1.0\columnwidth]{images/schedmodules_lifecycle2.eps}
\end{center}
\label{SchedModules_Lifecycle_endcycle}
\caption{Activation handling: a periodic task is activated once, and it executes
for three activations .}
\end{figure}

A task is activated, it executes for three instances and then it
falls asleep waiting for another explicit activation. The new
events introduced in this scenario are:

\begin{description}
\item [endcycle]The endcycle event is the termination of the
current task instance. It is generated by a primitive inserted
into the task code. If the task is a periodic task, it will be
reactivated by the Scheduling Module at the beginning of the next
period. If the task is an aperiodic task, this event implies that
the task will wait for an explicit activation (through an activate
event).

\item [(reactivation)]This event is not created directly
by the user with a primitive, but it is handled internally by the
Scheduling Module that handles the task. This event reactivates
the task, and it is usually delivered at the end of a period.
\end{description}

Although the event \textit{endcycle} terminates an aperiodic or a
periodic job, and it can differ in the way they handle pending
activations. A \emph{pending activation} is an \emph{activate}
event which is delivered when the task has not ended the previous
instance. The handling of pending activations is left to the
Scheduling Modules.

Figure \ref{SchedModules_Lifecycle_extract} shows the
\textit{block} ed \textit{unblock} events. These events are
generated to handle the behavior of a synchronization primitives,
which generally blocks a task (\emph{block} event) and then
activate again the task after a while (\emph{unblock} event). The
events behave as
follows:

\begin{figure}
\begin{center}
\includegraphics[width=8cm]{images/schedmodules_lifecycle3.eps}
\end{center}
\label{SchedModules_Lifecycle_extract}
\caption{Task synchronization. A task calls a synchronization primitive, which
blocks the task using an extract event. When the task will be able to continue,
an insert event will be called.}
\end{figure}


\begin{description}
\item [block]It disables the task scheduling because the task is
arrived at a synchronization point.

\item [unblock]This event is
used to notify to the task that the synchronization is occurred,
so the task scheduling must be enabled.
\end{description}

The Generic Kernel guarantees that an \textit{unblock} event will
never be called before a corresponding \textit{block
} event. That
is, these two events are coupled.


%----------------------------------------------------------------------------
\section{Assumptions on Task Queues}
%----------------------------------------------------------------------------

The modules distributed with the Kernel use the following
assumptions when managing task queues:

\begin{itemize}
\item The variables of type \texttt{IQUEUE} are allocated into the extensions of
the level descriptor and \emph{not} outside;

\item The running task is extracted
from the ready queue (if there is one in the Module) at dispatch time
\footnote{A policy that leaves the running task at the head of the ready queue
is also suitable.};

\item A Module can handle queue and other data structures
than those provided by the Generic Kernel. In this case all the data structures
shall be inserted in the level descriptor extension and the functions that use
them shall be visible only in that Module (for example look at the file
\texttt{kernel/modules/srp.c}).
\end{itemize
}

%----------------------------------------------------------------------------
\section{Scheduling Module Interface\label{SchedModules_Interface}}
%----------------------------------------------------------------------------

This section describes the interface of the functions that have to be
implemented to develop a Scheduling Module. The functions described in this
Section are those represented by the dashed rectangles named \emph{Public
Functions and Private Functions} introduced early in this chapter. They are
\emph{not} user primitives, but they are called to implement the scheduling
behavior of a primitive. The function names reported in this section are the
name of the function pointers contained into the \texttt{level\_des} structure
(defined into \texttt{include/kernel/descr.h}). When a designer implements a new
Scheduling Module, he writes the correspondent functions and then he sets the
correct values into the correct \texttt{level\_des
} structure (as an example, a
template application is provided on the website). The user primitives are
listed into the S.Ha.R.K. User Manual (it can be found, together with the
template application, on the proper section of S.Ha.R.K. website).
%
% Tool: such section does not exists.
%
% For more information see also at Sections \ref{ArchDetail_Module_Interface} and
% \ref{KernSupport_Level_Descriptor}.

All the interface functions have as first parameter a variable of
\texttt{LEVEL} type, used to obtain a pointer to the level
descriptor of the current Scheduling Module; some functions may
also have additional parameters.

We recommend that the functions listed in Table
\ref{SchedModules_Tab_schedule_time} should use the global
variable \texttt{schedule\_time} to get the system time, and
should not use the \texttt{kern\_gettime} function provided with
the OS
Lib.
\begin{table}
\begin{center}\begin{tabular}{|c|c|}
\hline Type& Function\\ \hline \hline Public
Functions& \texttt{public\_scheduler}\\ &
\texttt{public\_dispatch}\\ &
\texttt{public\_epilogue}\\ &
\texttt{public\_message}\\ &
\texttt{public\_block}\\ \hline Private Functions&
\texttt{private\_dispatch}\\ &
\texttt{private\_epilogue}\\ \hline
\end{tabular}\end{center}

\caption{\label{SchedModules_Tab_schedule_time}These functions
should use the variable \texttt{schedule\_time} to read the
current time.}
\end{table}

\textbf{WARNING}: All the Scheduling Modules functions are called
with \emph{interrupts disabled
}. They should never consume more
than a few microseconds!!!

%----------------------------------------------------------------------------
\subsection{Public Functions\label{SchedModules_PublicFunctions}}
%----------------------------------------------------------------------------

These functions are directly called by the Generic Kernel to
implement the behavior of a scheduling algorithm.

%----------------------------------------------------------------------------
\subsubsection{\texttt{PID (*public\_scheduler)(LEVEL l);}}
%----------------------------------------------------------------------------

This function is the scheduler of the current Scheduling Module.

It must return the scheduled task among those handled by the
Module \footnote{That is, the tasks owned by the Module plus the tasks
that other Modules inserted in it using the private
functions.}.

The scheduled task must be selected only using the private data structures of
the Module, \emph{prescinding from the other Modules registered in the system
}.
The fact that a task is returned by this function to be scheduled does not imply
that that task will be executed (dispatched) immediately
%
% Tool: such section does not exists.
%
% \footnote{Look at section \ref{ArchDetail_Shadows}}
.

So, the level scheduler shall not:

\begin{itemize}
\item Modify the pointer to the running task (in other words, the
variables \texttt{exec} and \texttt{exec\_shadow});

\item Handle
timers for deadline, capacity exhaustion, and things like that;

\item Set the data structures preparing the execution of the task (for example,
if the Module uses a ready queue, the task must not be extracted from the queue
\footnote{This will be done at dispatch time!}).
\end{itemize}

If the level does not implement a scheduler (because, for example, it is an
Aperiodic server that inserts all its tasks in another Module \footnote{look at
\texttt{kernel/modules/cbs.c}}), or if the Module currently does not have any
ready task, the returned value must be \texttt{NIL
}.

%----------------------------------------------------------------------------
\subsubsection{\texttt{int (*public\_guarantee)(LEVEL l, bandwidth\_t *freebandwidth);}}
%----------------------------------------------------------------------------

This function implements the on-line acceptance test. This
function should only consider the tasks directly inserted in the
module, and it does not consider the tasks inserted in the module
through private functions (their guarantee is made by the Module
that owns them).

The function is called with an additional parameter that is the
free bandwidth left by the Modules with level number less than
\texttt{l}. The acceptance tests that can be implemented are those
based on the Utilization Factor.

The function returns 1 if the current task set can be guaranteed
using the free bandwidth available, 0 otherwise. The
\texttt{freebandwidth} parameter must be decreased by the function
by the amount of bandwidth used by the task being guaranteed.

If the pointer to this function is registered in the
\texttt{level\_des} descriptor of the Module with a NULL value,
the acceptance test procedure will stop and the whole task set is
considered guaranteed (see Section \ref{Kernel_Garanzia}).

This function is called by the Generic Kernel each time a task is
created in the system. The call is issued after the task is
created using the task call \texttt{public\_create
} and after the
Resource Models of the new task have been registered. The
public\_guarantee functions are called starting from level 0 until
a NULL pointer is reached or the task set cannot be guaranteed.

%----------------------------------------------------------------------------
\subsubsection{\texttt{int (*public\_create)(LEVEL l, PID p, TASK\_MODEL *m);}}
%----------------------------------------------------------------------------

This function is called by the Generic Kernel into the
\texttt{task\_create} primitive to create a task into a Module.
The function has two additional parameters: the first is the task
descriptor allocated by the Generic Kernel for the new Task, and
the second is the Task Model passed at creation time.

The function returns 0 if the Module can handle the TASK\_MODEL
passed as parameter (that is, if the Module can handle the pclass
of the TASK\_MODEL, and if the level field is 0 or l), -1
otherwise.

The functions must set the Module internal data structures with
the QoS parameters passed with the Task Model. The function does
not enable the task to be scheduled in the system (i.e., if a
ready queue is implemented, the new task should not be inserted in
it).

The \texttt{task\_create} primitive sets the task state to the
default \texttt{SLEEP} value, and sets the flags of the
\texttt{control} field of the task descriptor to the values given
into the \texttt{control} field of the \texttt{TASK\_MODEL
}
structure. These settings can be modified by the public\_create
function.

The acceptance test on a new task is called after this function.

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_detach)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function is called into the Generic Kernel
\texttt{task\_create} primitive when an error is occurred during
the creation of a new task.

The function receives as an additional parameter the task
identifier passed to the \texttt{public\_create
} function. This
function is called only after public\_create, and it must reset
the data structures allocated internally by the current Module
during public\_create.

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_end)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function implements task termination. When this function is
called the task has been killed by someone (e.g., task\_kill() or
pthread\_cancel()), or it is ended. All the references to task p
have to be removed from the internal data structures of the
Module.

The \texttt{public\_end} function is called after the POSIX's
cleanup functions, after the POSIX's thread-specific data
destructors, and before the destructors of the Resource Modules.

When the function is called the task is in the EXE state. The
typical actions done by this function are the following:

\begin{itemize}
\item The task is extracted from some internal queue. \item All
the pending events for the task (e.g., deadline and capacity
timers) are removed. \item The task is inserted into the
\texttt{freedesc} queue. When the task is inserted in this queue
the task descriptor of the task may be reused by the Generic
Kernel.


If the Module implements some form of guarantee on the task set,
the insertion of the descriptor p into the \texttt{freedesc} queue
may be postponed until the bandwidth used by the task will be
totally released. This may occur after task's termination (for
example, in the EDF Module a guarantee is implemented, and the
bandwidth is decreased at the end of the current period. Hence,
the task descriptor will be inserted into the \texttt{freedesc}
queue at the end of the period.

\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{int (*public\_eligible)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function is called by the Generic Kernel into the global
scheduling function (see Section \ref{Kernel_Scheduler}) and is
used to ensure the Kernel of the correctness of the value returned
by the public\_scheduler.

The function receives as an additional parameter that is the task
returned by the \texttt{public\_scheduler} call. It must return 0
if the task can be scheduled, -1 otherwise. If a -1 is returned,
the system will call the level scheduler function again to choose
another (may be the same) task.

This function is used when implementing aperiodic servers and the
Module needs to know when its tasks will be scheduled by a
level\_scheduler of the Master Module, to update some old out-of
date parameters.

This function is useful in pathological or unplanned situations.
For example (see Figure \ref{SchedModules_Fig_eligible}), we have
implemented a CBS module in a way that it uses another Scheduling
Module. The CBS Module inserts its tasks in that module using the
guest calls; after that, it waits for its tasks to be scheduled.
In general, it may happen that, because of some overload
condition, the CBS task will be scheduled after its deadline.
Through the \texttt{public\_eligible} function the CBS Module can
postpone the task deadline, so causing the scheduler to be called
again to manage the new situation.

\begin{figure}
\begin{center}
\includegraphics[width=7cm]{images/schedmodules_eligible.eps}
\end{center}
\label{SchedModules_Fig_eligible}
\caption{Use of the \texttt{public\_eligible} function. Consider a CBS Module
that inserts its task j into an EDF-NP (EDF non-preemptive) Module. EDF-NP will
schedule task i first. When task i ends, task j (CBS) is scheduled. However,
this task has an obsolete deadline. The \texttt{public\_eligible} function
called on the CBS Module when the EDF-NP Module tries to schedule task j allows
the CBS Module to postpone the deadline.}
\end{figure
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_dispatch)(LEVEL l, PID p, int nostop);}}
%----------------------------------------------------------------------------

This function is called by the Generic Kernel to notify a Module
(registered at level l) that his task p is going to be the running
task.

When this function is called it is not possible to change the task
selected for execution. It is not possible to avoid the execution
of a task that is on the tail of a shadow chain
%
% Tool: such section does not exists.
%
% (see Section\ref{ArchDetail_Shadows})
. The \texttt{public\_eligible}
function should be used instead whenever a task cannot be
scheduled but it is chosen by a level scheduler.

The function receives two additional parameters: the task
\texttt{l} that will be executed and a \texttt{nostop} parameter.
The value of the latter parameter is the result of the logic
expression \texttt{exec == exec\_shadow}, where the value of
\texttt{exec\_shadow} is computed by the \texttt{scheduler()}
function (see Section \ref{Kernel_Scheduler}) after following the
shadow chain. If the value nostop is 0, no capacity event should
be generated by the Module.

In practice, the \texttt{public\_dispatch} can be thought as a
prologue in which the Scheduling Modules set the internal data
structures to allow a task to be executed. The state of the task
is set to EXE before the function call. The function shall not
modify the task state, as well as the \texttt{exec} and
\texttt{exec\_shadow} variables.

A few typical actions for this function are described below:

\begin{itemize}
\item the task is removed from the ready queue, if there is one;

\item if the Module does not use the \texttt{CONTROL\_CAP} flag (see
\ref{KernSupport_Capacita}, and kernel/modules/ps.c) but it needs capacity
control it is necessary to create a capacity event with the
\texttt{kern\_event\_post} function. Remember that a capacity event should not
be created if the \texttt{nostop} is not equal \texttt{0} \footnote{In this case
the task is going to be the running task because it locks a resource needed by a
high priority task, so usually the task must execute until the release of the
blocking resource.};

\item If the Scheduling Module is {}``coupled'' with a Resource
Handling Module, this function must update the ceiling (for
example as done with the SRP protocol).
\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_epilogue)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function is called by the Generic Kernel when:

\begin{itemize}
\item the running task p is preempted by another task in the
system;

\item a function that may generate a preemption is called
(these functions usually call the generic scheduler that, as a
first operation, simply call this function);

\item the capacity of
the running task p is exhausted (the capacity exhaustion is
handled as a preemption request!).
\end{itemize}

In general, this function receives as an additional parameter the
running task index. The effect of the call may also disable the
schedulability of the task. When this function is called the task
p has a state equal to EXE.

The typical actions done by this function are:

\begin{itemize}
\item if the schedulability of the task is still active, the task
is reinserted into the ready queue, if there exists one into the
Module; \item the state of the task is modified and it is set to
an internal Module state (for example, a READY state); \item the
capacity of the task is checked: if it is exhausted some
operations will be done, for example an exception is raised, a
deadline is postponed, and so on; \item If the Module created a
capacity event without using the \texttt{CONTROL\_CAP} field and
without using the \texttt{cap\_timer} variable, that capacity
event must be removed.
\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_activate)(LEVEL l, PID p, struct timespec *t);}}
%----------------------------------------------------------------------------

This function is called by the Generic Kernel when an explicit
activation for the task is called using the
\texttt{task\_activate} primitive or the \texttt{group\_activate}
primitive.

The PID parameter is the task that has to be activated. Also, the
activation time is given as an parameter (this will be the
time-base of the task). The effect of the function is to activate
the schedulability of the task.

The typical actions done by this function are listed below:

\begin{itemize}
\item First, a check is done to verify if the task is in a state
compatible with the activation (for example, a sporadic task
cannot be activated too frequently);

\item The state of the task,
usually equal to SLEEP, is modified (for example it becomes
READY);

\item If the Module has a ready queue, the task is
inserted in it;

\item If the Module counts the task's pending
activations, and the task does not have finished his current
activation yet, the activation should be saved for the task;

\item
If the Module handles periodic tasks or tasks with temporal
deadlines, some events should be created to check these
conditions.
\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_block)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

The function implements the blocking of the task p (p is the
running task) in a generic synchronization primitive that does not
use the shadow mechanism.

The function must disable the schedulability for the task until it
is ``freed'' by a call to the \texttt{public\_unblock} function.

The typical actions done by this function are:

\begin{itemize}
\item The task should be extracted from the ready queue if the
\texttt{task\_dispatch} didn't do this;

\item The events posted
with the dispatch should be removed (for example, the capacity
events should be removed, but not the deadline ones);

\item The
function shall not modify the state of the task; the state of the
task is modified by the primitive that calls the function;
\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*public\_unblock)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

The function accepts a parameter p that is the task that has
terminated the synchronization started with a call to the
\texttt{public\_block} function. After this call, the awaken task
can be scheduled in the system.

Usually the function inserts the task into some internal queues,
and the state of the task is modified (for example it is set to
READY). Usually the function does not post any event.

The function is called into the code of the Generic Kernel
primitives that implement synchronization without using the shadow
mechanism. The Generic Kernel guarantees that this function is not
called before the corresponding call to \texttt{public\_block
}.

%----------------------------------------------------------------------------
\subsubsection{\texttt{int (*public\_message)(LEVEL l, PID p, void *m);}}
%----------------------------------------------------------------------------

This function is called when the task\_message() primitive is
called by a task to send a message to the scheduler. Typical
messages are, for example, the end of an instance, or some kind of
signaling the task must do to a scheduling module, like a
checkpint mechanism.

The parameter p is the running task (that is, exec\_shadow). A
parameter m is passed, and it can be used to pass arbitrary
parameters to the scheduler. The value NULL is typically used by
the Kernel to signal the task\_endcycle primitive. An integer is
also returned to return a kind of status value to the calling
task.

%----------------------------------------------------------------------------
\subsubsection{The task\_endcycle primitive}
%----------------------------------------------------------------------------

A typical message that a task sends to a scheduling module is the
end of an instance, signaled using a task\_endcycle() primitive.
The implementation of that primitive is simply a
``task\_message(NULL,1)''. The task\_message should implement a
behavior similar to the one descried in the following paragraphs.

If the task does not have pending activations (or if the Module does not manage
them) the effect of the function is to disable the schedulability of the task
until an explicit activation is done by the user \footnote{using a
\texttt{task\_activate} call.} or an automatic reactivation done by the Module
(if the task is periodic).

If the task has some pending activations the function will
reactivate the task in a way similar to \texttt{public\_epilogue}.

The typical actions done by this function are listed below:

\begin{itemize}
\item If the task must be suspended, the task state is modified to
a ``parking'' state (\texttt{IDLE} or \texttt{SLEEP});

\item The
task may be removed from the ready queue (if it was not removed by
the \texttt{public\_dispatch});

\item Some resource reclaiming
algorithm may be implemented, because a task instance is finished;

\item Timer events related to the budget exhaustion and deadlines
are handled (for example events can be deleted, or postponed).
\end{itemize
}

%----------------------------------------------------------------------------
\subsection{Private Functions}
%----------------------------------------------------------------------------

This section describes the private functions provided by a
scheduling module. Private functions are called only by other
scheduling modules, and never by the generic kernel, and they
represent the interface extorted by a scheduling module towards
other modules. Typical example of use of the private functions
are:

\begin{itemize}

\item an EDF module have to implement task activation and
unblocking simply inserting a task into the ready queue. For that
purpose, the functions public\_activate and public\_unblock
internally calls the private function private\_insert. Moreover,
the two functions can have some peculiarities. For example, the
implementer would like that public\_activate adds a deadline check
posting an OSLib event at the deadline time, whereas this is not
the case of public\_unblock, because the deadline used before have
to be used again. Deadline posting can be done into
public\_activate. private\_insert will simply insert the task into
its \char`\"{}private\char`\"{} queue.

\item an aperiodic server
wants to insert a task into the EDF queue. Again, the
public\_activate and the public\_unblock of the aperiodic server
will call the private\_insert of the EDF queue, that will insert
the task into its queue.
\end{itemize
}

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*private\_insert )(LEVEL l, PID p, TASK\_MODEL *m);}}
%----------------------------------------------------------------------------

This function is used to insert a task into the Module. The
inserted task must have been already created through a call to the
\texttt{task\_create} primitive. When inserted, the behavior of
the function is as the task has been activated into the module
(e.g., the task goes into the ready queue). All the useful
informations passed to the task Model must be registered
internally to the Module.

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*private\_extract )(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function terminates a chunk of a task previously inserted in the Module
using private\_insert. The typical effect of this function is to extract the
task from the internal queues and to delete the events generated for the task
(deadline, capacity, and so on). The function shall not insert the task
descriptor in the \texttt{freedesc} queue \footnote{public\_end() is responsible
for that\ldots{}
}.

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*private\_dispatch)(LEVEL l, PID p, int nostop);}}
%----------------------------------------------------------------------------

This function is usually called by \texttt{public\_dispatch} to
inform the Master Module that a task inserted in it as a guest is
being dispatched. The semantic of the function is similar to that
of \texttt{public\_dispatch
}.

%----------------------------------------------------------------------------
\subsubsection{\texttt{void (*private\_epilogue)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function is called by a Module to inform the Master Module
that a task inserted in it using private\_insert() is being
preempted or its budget has been exhausted.

%----------------------------------------------------------------------------
\subsubsection{\texttt{int (*private\_eligible)(LEVEL l, PID p);}}
%----------------------------------------------------------------------------

This function is usually called by public\_eligible to inform the
Master Module that a task inserted in it as a guest has been
chosen for scheduling. The semantic of the function is similar to
that of \texttt{public\_eligible}.

%----------------------------------------------------------------------------
\section{Registration Function}
%----------------------------------------------------------------------------

The code contained in a Module is composed by the function calls
(Level, Task and Guest Calls), and by a Registration Function that
must be called when the system starts to properly initialize the
kernel data structures. This registration function can be thought
as a C++ constructor for the Module.

A Module initialization typically consists of four parts:

\begin{itemize}
\item The first part allocates a level descriptor that will be
used to initialize the Module; To alloc a level descriptor, the
functions

\texttt{LEVEL~level\_alloc\_descriptor(void)} and

\texttt{RLEVEL~resource\_alloc\_descriptor(void)}

must be used. These functions take no arguments and return a free
descriptor to be used; \item The second part initializes the
function pointer of the level descriptor of a scheduling module;
\item The third part initializes the private data structures of
the Module, and possibly posts a function that has to be called
just after the system has gone in multitasking mode; \item The
fourth part executes the function posted in the third part.
\end{itemize}
The first three parts are written in the Registration Function,
which is called by the \texttt{\_\_kernel\_init\_\_} function
before the Kernel goes in multitasking mode.

In the \texttt{\_\_kernel\_init\_\_} function no Generic Kernel
primitives can be called. If there is a need to do that, a
registered function has to be called instead. For example, the
dummy task is created by the Dummy Module
(\texttt{kernel/modules/dummy.c}) through a registration function.
The main task is created in the same way by the Round Robin Module
(\texttt{kernel/modules/rr.c
}).

%----------------------------------------------------------------------------
\subsection{Default values}
%----------------------------------------------------------------------------

In general, the scheduling modules needs only to register the
functions they want to redefine. For that reason, the public and
private functions have a default value, set by
\texttt{level\_alloc\_descriptor()}. Here is a list of these
default values:

\begin{description}
\item [private\_insert]Kernel Exception.

\item
[private\_extract]Kernel Exception.

\item
[private\_eligible]Returns 0 (that is, the task can be accepted
for scheduling).

\item [private\_dispatch]Kernel Exception.

\item
[private\_epilogue]Kernel Exception.

\item
[public\_scheduler]Returns -1 (that is, no task are ready to be
scheduled).

\item [public\_guarantee]Returns 1 (that is, the
system can be scheduled).

\item [public\_create]Returns -1 (that
is, the model can not be handled by the module).

\item
[public\_detach]Does nothing.

\item [public\_end]Kernel Exception.

\item [public\_eligible]Returns 0 (that is, the task can be
accepted for scheduling).

\item [public\_dispatch]Kernel
Exception.

\item [public\_epilogue]Kernel Exception.

\item
[public\_activate]Kernel Exception.

\item [public\_unblock]Kernel
Exception.

\item [public\_block]Kernel Exception.

\item
[public\_message]Kernel Exception.
\end{description
}

%----------------------------------------------------------------------------
\section{Writing Conventions\label{SchedModules_Convenzioni}}
%----------------------------------------------------------------------------

This Section explains some conventions followed in writing the
Modules. They are useful to understand how to write new Modules
using the same style adopted in the Modules distributed with the
Kernel. They can be summarized as follows.

\begin{itemize}
\item Each Module is composed of two files, one file \texttt{.h}
and one file \texttt{.c}. The \texttt{.h} files are stored in the
\texttt{include/modules} directory; the \texttt{.c} files are
stored in the \texttt{kernel/modules} directory. \item Each
Registration Function registers only ONE level descriptor. In this
way the level at which a Module is registered can be found
inspecting the initialization file. The level descriptor number is
usually returned by the register function. \item The Task Models
used by the Modules are listed in the
\texttt{include/kernel/model.h} file. \item The names of the
internal functions are defined as \texttt{static} and are in the
form \texttt{MODULENAME\_FUNCTIONNAME}, where \texttt{MODULENAME}
is the name of the \texttt{.c} file where the Module code is
written. \item A Module can export some functions to implement a
specific behavior; these functions have a first parameter of type
\texttt{LEVEL}, in order to retrieve the Module data structures.
An application that relies on a specific Module configuration can
use the functions under the assumption that the Application knows
the level at which the Module is registered. \item The prototypes
of the functions exported by a Module (registration function plus
other functions if present) have to be included in the \texttt{.h}
file. \item The Modules should not use global data, because
different instances of a Module can be registered at the same time
in the system.
\end{itemize}
In general writing a new Scheduling Module requires the creation
of new files. To simplify the distribution and the integration of
new modules in the Generic Kernel no modifications have to be made
to the standard distribution of the Kernel. Beside that, a few
rules of common sense have to be followed:

\begin{itemize}
\item A new Scheduling Module should consist of only one
\texttt{.h} file and only one \texttt{.c} file. Modules composed
of many files should contain an explanation in their
documentation. \item Together with the Scheduling Module a system
designer should provide:

\begin{itemize}
\item an initialization file (similar to those present in the
\texttt{kernel/init} directory) that shows how the new Module must
be initialized; \item at least one test program showing the
functionality of the Module;
\end{itemize}
\item New data definitions (for example new Task Models, new
\texttt{pclass}, version and exception values) used by the new
Modules should be inserted into the \texttt{.h} file of the
Module. New constants should be different from the others
contained into the default distribution.
\end{itemize
}
A template example of a Scheduling Module can be found on the
S.Ha.R.K. web site. Examples of third-party scheduling modules can
be dound into the demos directory (e.g., demos/static,
demos/edfact, demos/cash).