Subversion Repositories shark

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

\chapter{Kernel Internals}

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

Since the Generic Kernel does not implement any memory protection,

all the Modules have access to the internal data structures used

for scheduling. Although the Modules could modify these data

structures, typically they do not need to do so.

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

\section{Kernel types}

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

The Generic Kernel defines a set of primitive data types, that are

briefly described below:

\begin{description}

\item [PID]This type is used to contain a task index. It is an

integer pointing to an entry of the task descriptor table. This

type can have values in the range {[}0...MAXPROC-1{]}, plus an

invalid value, NIL (that is, -1).

\item [IQUEUE]This type is used to implement the task queues typically used in

scheduling operations. For more information see Section \ref{KernSupport_Code}.

\item [TASK]This type is simply a

redefinition of the \texttt{void {*}} type and it can be used for

readiness ad the returned value in the task function declaration.

\item [LEVEL,~RLEVEL]They are used to index the Module descriptor

Tables. They are integers and they point to a particular entry.

The values of these types are

{[}0...\texttt{MAX\_SCHED\_LEVEL-1}{]} for the \texttt{LEVEL} type

and {[}0...\texttt{MAX\_RES\_LEVEL}{]} for the \texttt{RLEVEL}

type.

\item [bandwidth\_t]This type is used to store a real number

in the range {[}0,1{]}. It is a 32 bit unsigned integer and its

value is interpreted as $\frac{x}{MAX\_ BANDWIDTH}$.

\item

[task\_key\_t]This is an integer type and it is used as an index

for task specific data (similar to POSIX's Thread Specific Data).

\end{description}

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

\section{Descriptors}

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

In this section we present all the descriptors defined in the

Generic Kernel. If not specified, these data structures are

defined in the \texttt{include/kernel/descr.h} file and they are

used (usually as arrays) in the \texttt{kernel/kern.c} file.

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

\subsection{Task Descriptor}

\label{KernSupport_Task_descriptor}

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

The \texttt{proc\_des} structures used to define task control blocks

\footnote{The name of this structure is derived from the previous versions of

Hartik. However, it is a \textit{task} descriptor and not a \textit{process}

descriptor.}. In the following paragraphs the fields of the task descriptor are

described \footnote{The following fields have been removed from the structure in

the last releases: request\_time, priority, timespec\_priority, prev, next.}.

\begin{description}

\item [DWORD~task\_ID]Progressive number assigned to a task at its

creation.

\item [LEVEL~task\_level]This field points to the Module

that owns the task. The Generic kernel uses this field to redirect

the calls to the Module owning the task.

\item

[CONTEXT~context]This field contains an index in the OS Lib

context array that handles the context of a task.

\item

[BYTE~{*}stack]This field is a pointer to the memory used as a

task stack.

\item [TASK~(*body)()]This field is the pointer to

the first instruction of a task body, and it is used at

initialization time.

\item [char~name[MAX\_TASKNAME]]This is a

symbolic name, whose length is defined by the

\texttt{MAX\_TASKNAME} constant.

\item [WORD~status]This is the

task status.

\item [WORD~pclass]This field is the Class code of

the Task Model used during task creation. It can be used by

Modules to know the typology of the task (useful if the task

supports many types of Models; see

%

% Tool: such section does not exists.

%

%Section

%\ref{SchedModules_LevelCalls},

\texttt{level\_accept\_task\_model}

%function)

.

\item [WORD~group]This is the task group. The value 0

is used to index a single task. This field is not used as a GID in

classical Unix systems but is used to kill or activate a group of

tasks in an atomic way.

\item [WORD~stacksize]Stack dimension (in

bytes).

\item [DWORD~control]Task Status flags. A description of

the bits in this field is reported in

Section\ref{Modelli_TASK_MODEL}.

\item

[int~frozen\_activations]Number of frozen activations. Useful only

if the \texttt{FREEZE\_ACTIVATION} flag of the \texttt{control}

field is active (see Section \ref{Kernel_Attivazione}).

\item

[int~sigmask]This is the blocked signal task mask (see

\texttt{kernel/signal.c} and also \cite{POSIX1003.1}).

\item

[int~sigpending]This is the pending signal task mask (see

\texttt{kernel/signal.c} and also \cite{POSIX1003.1}).

\item

[int~sigwaiting]This is the mask of the signals on which a task is

waiting, blocked on a \texttt{sigwait} primitive (or similar).

\item [int~avail\_time]This field contains the remaining

computation time of a task (see Section

\ref{KernSupport_Capacita}).

\item [PID~shadow]This is the shadow

pointer (see Section \ref{oview_Shadows}).

\item

[struct~\_task\_handler\_rec~{*}cleanup\_stack]Pointer to the

first element of the cleanup stack.

\item [int~errnumber]This is

an error number local to the running task. The symbol

\texttt{errno} defined into the C standard is implemented as a

macro that refers to this field of the running task.

\item

[TIME~jet\_table{[}JET\_TABLE\_DIM{]}]This table contains the

computation times consumed by the last JET\_TABLE\_DIM instances

of the task. The table is handled as a circular buffer.

\item

[int~jet\_tvalid]This is the number of valid items in the

\texttt{jet\_table} table.

\item [int~jet\_curr]This is the

current element in the \texttt{jet\_table} table.

\item

[TIME~jet\_max]This field contains the maximum time (in

microseconds) consumed by a task, among all its instances.

\item

[TIME~jet\_sum]This field accumulates the execution times (in

microseconds) of all task instances from the start of the task (or

from the last call to \texttt{jet\_delstat}). This field, together

with the \texttt{jet\_n} field, is used to compute the mean

execution time of a task instance.

\item [TIME~jet\_n]This field contains the number of instances involved in the

computation of \texttt{jet\_sum}.

\item [PID~waiting\_for\_me]This field contains

the identifier of the task which is currently blocked for a

\texttt{task\_join} on the current task. The field value is NIL if

no task is blocked for a join on it.

\item

[void~{*}return\_value]This is the value returned by a task when

it dies. This value is memorized if the task is joinable, waiting

for someone to synchronize on it with a join.

\item

[void~{*}keys{[}PTHREAD\_KEYS\_MAX{]}]This array contains the task

specific data.

\item

[struct~condition\_struct~{*}cond\_waiting]This field is NULL or

it points to the condition variable on which the task is

blocked \footnote{This field is present because if a task is killed during

a block on a condition wait, the POSIX standard requires that the

task reacquires the mutex linked to that condition before it

dies.}.

\item [int~delay\_timer]This field is used in the

implementation of the blocking primitives with timeout. Usually

this field contains the OS Lib index of the event created for the

wake-up.

\item [int~wcet]This field can be used by Modules to

store some temporal information. It is generally used in

conjunction with the \texttt{avail\_time} field.

\end{description}

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

\subsection{Level descriptor}

\label{KernSupport_Level_Descriptor}

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

In this Section we describe the fields contained in the

\texttt{level\_des} structure, that implements the Scheduling

Module Descriptor. These Modules will fill the proposed interface,

defining also all the interface functions. If a Module does not

implement an interface function, it redefines that function in a

way that it will raise an exception if called. The fields defined

for the \texttt{level\_des} structure are the following:

\begin{description}

\item [Private~Functions,~Public~Functions]The rest of the interface is made of

a set of function pointers that implements the \emph{virtual} functions of the

Scheduling Modules. That functions are described in the Chapter

\ref{CapSchedulingModules}. All that functions have as first parameter a LEVEL

field that can be used to find the Module Descriptor and then the private

structures of that Modules \footnote{The behaviour of the LEVEL parameter passed

to that function is the same of the hidden paramether \emph{this} of many Object

Oriented languages.}.

\end{description}

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

\subsection{Resource module descriptor}

\label{KernSupport_Descrittore_GestioneRisorse}

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

In this Section we describe the fields contained in the

\texttt{resource\_des} structure, which implements the Resource

Module Descriptor. These Modules will fill the proposed interface,

defining all the required functions. If a Module does not

implement an interface function, it redefines that function in a

way that it will raise an exception if it is called. The fields

defined for the \texttt{resource\_des} structure are the

following:

\begin{description}

\item [char~res\_name{[}MAX\_MODULENAME{]}]This filed contains a

symbolic Name of the Module, for statistical purposes. The file

\texttt{include/modules/codes.h} contains the name of the Modules

distributed with the Kernel. \item [WORD~res\_code]This field

contains a numeric identifier that identifies a Module in an

unique way. The codes of the Modules distributed with the kernel

are written in the file \texttt{include/modules/codes.h}. \item

[BYTE~res\_version]This is a version number for the Module. The

version numbers of the Modules distributed with the Kernel are

reported in the file \texttt{include/modules/codes.h}. \item

[int~rtype]This field is used to identify the extended interface

implemented by a Resource Module. This field is necessary to

implement some primitives that use a particular extended

interface, that need to know which of the resource modules

registered in the kernel have a particular extension. \item

[Resource~Calls]The rest of the interface is made of a set of

function pointers that implement the \emph{virtual} functions of

the Resource Modules. These functions are described in Chapter

\ref{CapModuliRisorsa}. All these functions have as first

parameter a RLEVEL field that can be used as the similar parameter

of the Scheduling Module virtual functions.

\end{description}

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

\section{System states}

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

As mentioned in Section \ref{oview_Status} the concept of task

state has a local meaning, and it is stored in the \texttt{status}

field of its task descriptor.

The values that the status field can have are divided in four

intervals, described in Table \ref{KernSupport_Tab_StatusCodes}.

\begin{table}

\begin{center}

\begin{tabular}{|p{4cm}|p{9cm}|}

\hline

Interval reserved to & Codes\\ \hline \hline

Generic Kernel & {[}0...\texttt{MODULE\_STATUS\_BASE}-1{]} \\ \hline

Scheduling Algorithm \foreignlanguage{english}{} & {[}\texttt{MODULE\_STATUS\_BASE}

...\texttt{APER\_STATUS\_BASE}-1{]}\\ \hline

Aperiodic Servers \foreignlanguage{english}{} & {[}\texttt{APER\_STATUS\_BASE}

...\texttt{LIB\_STATUS\_BASE}-1{]}\\ \hline

Others (Resource Handling, libraries, etc.) \foreignlanguage{english}{} &

\texttt{>= LIB\_STATUS\_BASE}\\ \hline

\end{tabular}

\end{center}

\caption{Partitioning of the codes for the status field of the task descriptor.}

\label{KernSupport_Tab_StatusCodes}

\end{table}

Each Module Should use the codes in the correct range of values.

This approach allows to handle many Module configurations. The

fact that two Scheduling Modules use the same status code for

different meanings is not a problem, because the codes are used

internally to the Modules.

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

\section{Kernel Global Variables}

\label{KernSupport_Variabili}

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

The following global variables are defined in the Generic Kernel

and can be used by the Modules.

\begin{description}

\item [proc\_des~proc\_table{[}{]}]This variable is the task descriptor array.

Not all the entries of this array are used. The descriptor really allocated are

handled by the \texttt{task\_create} primitive.

\item [level\_des~{*}level\_table{[}{]}]This variable is the array that

memorizes a set of \emph{pointers} to the Scheduling Modules

Descriptors. When a Module registers itself into the Kernel, an

entry of this array is allocated, and it points to an

\emph{extension} of the \texttt{level\_des} descriptor type. In an

object oriented interpretation it can be thought as a polymorphic

Module array (see Section \ref{Modelli_MetodologiaOOP}).

\item [resource\_des~{*}resource\_table{[}{]}]This variable memorizes an

array of pointers to extension of the resource\_des structure. For

this variable the same comments for the level\_table apply.

\item [PID~exec]This variable contains the task returned by the

Scheduling Module scheduling operation. Typically this variable is

used only into the \texttt{scheduler()} function of the Generic

Kernel. This variable cannot be modified, it can only be read and

checked with the field \texttt{exec\_shadow}. This variable has

the value \texttt{NIL} (-1) when a primitive blocks the running

task, and the scheduler is not yet called. This variable

\emph{does not} point to the running task. Use

\texttt{exec\_shadow} instead!

\item [PID~exec\_shadow]This variable points to the running task. It can be

different from the value contained into \texttt{exec} because of the Shadow

mechanism (see Section \ref{oview_Shadows}). This variable cannot be modified,

it can only be read and check with the field \texttt{exec}. This variable has

the value \texttt{NIL} (-1) when a primitive blocks the running task, and the

scheduler is not yet called. When a reference to the running task is needed,

this variable has to be used.

\item [int~cap\_timer]This variable is different from -1 only if the Generic

Kernel or a Module created a capacity event. This variable can be used by the

Scheduling Modules that do not utilize the \texttt{CONTROL\_CAP flag} for their

tasks (see Section \ref{KernSupport_Capacita}).

\item [struct~timespec~schedule\_time]This variable contains the system time in

which the scheduler was called the last time. The first thing the Kernel

function \texttt{scheduler()} does is the setting of that variable. This

variable is also used as finish time for an execution time interval.

\item [struct~timespec~cap\_lasttime]This variable is a copy of the

\texttt{schedule\_time} variable, done at each call of the \texttt{scheduler()}

function. The value of that variable is used as the start time of the last

interval executed by a task. It is used to implement the time accounting.

\item [DWORD~res\_levels]This variable is the number of resource

module level descriptors allocated. It is modified only by the

\texttt{resource\_alloc\_descriptor} function

%

% Tool: such section does not exists.

%

% (see Section \ref{SchedModules_RegFunctions})

.

\item [int~task\_counter]This variable is a variable that counts the number of

User tasks actually present into the system (see Section

\ref{Kernel_Inizializzazione}).

\item [int~system\_counter]This

variable is a variable that counts the number of System tasks

actually present into the system (see Section

\ref{Kernel_Inizializzazione}).

%

% Tool: no more sys_end nor sys_abort. Check this in the code!

%

% \item [int~mustexit]This variable

% is used by the system primitives \texttt{sys\_end} and

% \texttt{sys\_abort} to block the context changes into the event

% handlers.

\item [int~calling\_runlevel\_func]This variable is a

flag. It is set to 1 when the system executes some system

functions (registered through the \texttt{sys\_atrunlevel()}

function). This flag influence the \texttt{task\_activate}

primitive, because that primitive has to do different stuffs

depending on the value of that variable (see the code of the

primitive in the file \texttt{kernel/activate.c}).

\item

[IQUEUE~freedesc]This variable is the free task descriptor queue.

It is handled by the Kernel and must be used by a Scheduling

Module into the call \texttt{task\_end} call to free a task

descriptor of a task terminated correctly.

\item

[TIME~sys\_tick]If the OS Lib is initialized with the \textit{one

shot timer} the variable contains the system tick (in

microseconds). Otherwise, the one-shot timer is used, and this

variable has a value of \texttt{0}.

\end{description}

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

\section{Temporal protection}

\label{KernSupport_Capacita}

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

The Generic Kernel supports task temporal protection through a set

of procedures and data structures that may be used by the

Scheduling Modules. The generic Kernel does force to use its own

functions, so a Module can define itself a policy to ensure

temporal protection. In this Section the proposed functions to

implement the temporal protection are described.

The Generic Kernel handles the time capacity of the tasks in the

system using the creation and the deletion of a specific OS Lib

event that simply reschedules the system. The end of the capacity

is seen by the Modules as a normal epilogue done in the case of a

preemption.

The timer event is created when a task is dispatched, and it is

deleted by all the primitives that may cause preemption. In an

instant there is at least one capacity event pending, that is the

event of the running task.

The Generic Kernel defines for each task the bit

\texttt{CONTROL\_CAP} that is memorized into the field

\texttt{control} of the task descriptor. That bit is set by the

Scheduling Modules to require for a task the creation of the

capacity event at dispatch time.

The Scheduling Modules have also to check the capacity exhaustion

each time a task is descheduled.

Capacities are handled using the following variables provided by

the Kernel:

\begin{itemize}

\item The \texttt{wcet} field of the task descriptor usually memorizes a

characteristic time for a task (i.e., it is used to store a worst-case execution

time or a mean execution time). It is included in the task descriptor to avoid

the allocation of such an information for all the modules. It is \emph{not} used

by the Generic Kernel.

\item The \texttt{avail\_time} field of the task descriptor is used to handle

the available execution time for a task. The capacity event generated by the

Generic Kernel at dispatch time has an activation time that is equal to

\texttt{schedule\_time + avail\_time}. The field is updated by the generic

kernel each time a task is descheduled, decrementing the slice just executed by

the task.

\item The \texttt{cap\_timer} field is used by the Generic Kernel to know

whether a capacity event is or not pending. If the field is equal to -1, there

are no events, otherwise the value is the index of the capacity event. If the

field is not equal to -1 the Generic kernel will delete automatically the event

each time the system is rescheduled. The Generic Kernel does not check who has

created the event pointed by \texttt{cap\_timer}, so a Scheduling Module that

not use the flag \texttt{CONTROL\_CAP} can create a capacity event and put his

index into \texttt{cap\_timer}, avoiding the removal of the event directly in

the code of the Module.

\item The \texttt{cap\_lasttime} field contains the time of the previous

reschedule of the system. The accounting of the computation times is done from

the difference between \texttt{schedule\_time} and \texttt{cap\_lasttime}. The

time used by the Kernel primitives is accounted in the running task.

\end{itemize}

The functions called by the capacity event have only to reschedule

the system. The Scheduling Modules that have to generate

themselves the capacity event can store their events in the

\texttt{cap\_timer} filed if they want an event to be removed at

each preemption. The events can call the Generic Kernel Function

called \texttt{capacity\_timer} (it does not accept any

parameter).

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

\subsection{Negative capacities}

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

The contents of the \texttt{avail\_time} field can be negative.

This fact, theoretically impossible, can happen for two reasons:

\begin{itemize}

\item first, the OS LIb event handler can not guarantee the

delivery of a capacity event at exact time (a small delay of some

microseconds may occur). So, a capacity event may be delivered

after the capacity is exhausted, so that the task capacity becomes

negative. We can suppose that negatives values are smaller than

the usual time for the tasks; \item second, because the shadow

mechanism can execute a task that has finished his budget; that

task will not be descheduled until the shadow of the higher

priority task points to it. This behavior is correct because we

want that the blocking task will ends its critical section to

limit the blocking time of the higher priority tasks. This

approach is supported by some theoretical results (see

\cite{Gha95}).

\end{itemize}

Scheduling modules can use two strategies to cope with the problem

given by negative capacities.

The first solution is to recharges the capacity with an amount

equal to $Q_{s}$; if the capacity is still negative, the task will

{}``loose a turn''. This solution is good for algorithms that

provide a periodic replenishment (like for example Round Robin,

Polling Server or Deferrable Server) but not for algorithms like

Sporadic Server or Constant Bandwidth Server, where the

replenishment is due to the capacity usage (in these algorithms

the server would not become active).

The second solution is to replenish the budget up to $Q_{s}$; this

solution is good for all types of algorithms, but we have to

consider that the server utilization factor becomes

$\frac{Q_{s}+\Delta}{T_{s}}$.

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

\section{Utility functions}

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

This section contains a set of utility functions that can be used

to simplify the writing of the Modules. Often these functions are

simple redefinitions of the OS Lib functions. Use these functions

instead of those provided by the OS Lib.

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

\subsection{Event Handling}

\label{KernSupport_GestioneEventi}

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

The Generic Kernel uses the Generic kernel event handling provided

by the OS Lib. The following functions should be used (see

\texttt{include/kernel/func.h}):

\begin{itemize}

\item \texttt{kern\_event\_post} can be used to post an event. The

redefinition adds a check on the index, raising an exception if

the OS Lib event queue is full. \item \texttt{kern\_event\_delete}

can be used to remove an OSLIB event. The unique parameter of the

funcion is the eveni ID returned by the kern\_event\_post

function. \item \texttt{event\_need\_reschedule}, with no

parameters. It has to be called into the event handlers that have

to reschedule the system. The Modules never have to call the

schedule function into event handlers.

\end{itemize}

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

\subsection{Exception Handling}

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

The Generic Kernel exception handling is based on the real-time

signal interface of the POSIX standard. In particular, the

exceptions are implemented with the signal number 9, SIGHEXC, that

typically writes a message to the console and ends the system.

The function to use to raise an exception is: \begin{center}

\fbox{\tt{ void kern\_raise(int n, PID p); }} \end{center}

As a result of this function call, a real-time signal is enqueued

into the system and the n parameter is passed into the field

\texttt{si\_value} of the structure \texttt{siginfo\_t} passed as

a parameter to the signal handler.

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

\subsection{Memory Management}

\label{KernSupport_GestioneMemoria}

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

The Generic kernel provides a memory allocator based on Flux

OS-Kit LMM\cite{Bry97}. The LMM is in the \texttt{kernel/mem}

directory; the functions defined in this subsection are in the

file \texttt{kernel/mem.c}. These functions must be called with

interrupt disabled.

The allocator divides the memory into three regions that can be

specified with some \#defines into the flag parameter of some

functions:

\begin{itemize}

\item Memory addresses below 1 Mb (flag field set to

\texttt{MEMORY\_UNDER\_1M}) \item Memory addresses from 1 Mb to 16

Mb (flag field set to \texttt{MEMORY\_FROM\_1M\_TO\_16M}) \item

Memory addresses below 16 Mb (flag field set to

\texttt{MEMORY\_UNDER\_16M}) \item Memory addresses over 16 Mb

(flag field set to \texttt{0})

\end{itemize}

Memory management functions are described below (see also Figure

\ref{KernSupport_mem_functions}):

\begin{figure}

\begin{center}

\begin{minipage}{6cm}

\begin{verbatim}

void *kern_alloc(DWORD s);

void *kern_alloc_aligned(size_t size, lmm_flags_t flags,

      int align_bits, DWORD align_ofs);

void *kern_alloc_gen(size_t size, lmm_flags_t flags,

      int align_bits, DWORD align_ofs,

      DWORD bounds_min, DWORD bounds_max);

void kern_free(void *block, size_t size);

void *kern_alloc_page(lmm_flags_t flags);

void kern_free_page(void *block);

void *DOS_alloc(DWORD size);

void DOS_free(void *ptr, DWORD size);

\end{verbatim}

\end{minipage}

\end{center}

\label{KernSupport_mem_functions}

\caption{Memory allocation functions.}

\end{figure}

\begin{description}

\item [\texttt{kern\_alloc}]This function allocates a memory block

of s bytes returning a \texttt{void~{*}}. All the addresses given

are supposed to be good for the block. The function returns

\texttt{NULL} if there is not a free memory block with the

required size. \item [\texttt{kern\_alloc\_aligned}]This functions

allocates an aligned memory block. The first \texttt{align\_bits}

of the block must be equal to the lowest \texttt{align\_bits} of

\texttt{align\_ofs}. In other words, \texttt{align\_bits}

specifies an alignment as a power of 2, whereas

\texttt{align\_ofs} is a natural offset. The function returns

\texttt{NULL} if there is not a block with the required

characteristics. \item [\texttt{kern\_alloc\_gen}]This function

allocates an aligned memory block in a way similar to

\texttt{kern\_alloc\_aligned}, with the additional condition that

the block must be found within the addresses \texttt{bounds\_min}

and \texttt{bounds\_max}. \item [\texttt{kern\_free}]This function

will free a block allocated with one of the previous functions.

Note that this function requires the dimension of the block to

allocate. \item [\texttt{kern\_alloc\_page}]This function

allocates an aligned page of memory (4 Kb). \item

[\texttt{kern\_free\_page}]This function frees a page allocated

with the \texttt{kern\_alloc\_page} function. \item

[\texttt{DOS\_alloc,~DOS\_free}]These functions allocate memory

under the first Mb.

\end{description}

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

\subsection{Context switch}

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

The creation and the deletion of a context in the Generic Kernel

is made using the OS Lib functions, properly renamed into

\texttt{kern\_context\_create} and \texttt{kern\_context\_delete}.

To change context, the Generic Kernel provides two functions,

\texttt{kern\_context\_save} and \texttt{kern\_context\_load}.

First function can be used to start a kernel primitive (disabling

interrupts, whereas the second can be used to enable the

interrupts, change the context using the OS Lib functions,

dispatch pending signals and test for asynchronous cancellation.

Note that currently the kernel primitives run on the same stack of

the caller thread, and the primitives are simply called disabling

the interrupts.

These functions must never be called into the standard interface

of the scheduling modules. When a OS Lib event need to reschedule

the system because there is a preemption, the function

\texttt{event\_need\_reschedule} must be called instead.

The functions described in this paragraph are into the

\texttt{include/kernel/func.h} file.

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

\subsection{Queues, arrays and pointers}

\label{KernSupport_Code}

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

To simplify the use of the internal Kernel references, the

following approach is used:

\begin{itemize}

\item Whenever possible, the descriptor arrays are statically

allocated. \item Each descriptor is identified by an integer which

represents the index in the descriptor array (e.g. PID, LEVEL,

RLEVEL).

\end{itemize}

To handle task queues, the Generic Kernel provides some utility

functions which can speed up the Module writing; however a module

can use its own functions to enqueue tasks.

The implemented functions do not use any fields of the task

descriptor; they are implemented with a double linked list. The

prototypes of the functions for queue management are shown in

Figure \ref{KernSupport_queue_functions}. They are into the file

\texttt{kernel/iqueue.c}, and \texttt{include/kernel/iqueue.h},

described below.

\begin{figure}

\texttt{\#define IQUEUE\_NO\_PRIORITY 1}

\texttt{\#define IQUEUE\_NO\_TIMESPEC 2}

\texttt{struct IQUEUE\_shared \{ }

\texttt{~~PID prev{[}MAX\_PROC{]}; }

\texttt{~~PID next{[}MAX\_PROC{]}; }

\texttt{~~struct timespec {*}timespec\_priority; }

\texttt{~~DWORD {*}priority; }

\texttt{\};}

\texttt{typedef struct \{ }

\texttt{~~PID first; }

\texttt{~~PID last; }

\texttt{~~struct IQUEUE\_shared {*}s; }

\texttt{\} IQUEUE; }

\texttt{~}

\texttt{void iq\_init (IQUEUE {*}q, IQUEUE {*}share, int flags);}

\texttt{void iq\_priority\_insert (PID p, IQUEUE {*}q); }

\texttt{void iq\_timespec\_insert (PID p, IQUEUE {*}q); }

\texttt{void iq\_insertfirst (PID p, IQUEUE {*}q); }

\texttt{void iq\_insertlast (PID p, IQUEUE {*}q);}

\texttt{void iq\_extract (PID p, IQUEUE {*}q); }

\texttt{PID iq\_getfirst ( IQUEUE {*}q); }

\texttt{PID iq\_getlast ( IQUEUE {*}q); }

\texttt{PID iq\_query\_first(IQUEUE {*}q);}

\texttt{PID iq\_query\_last(IQUEUE {*}q);}

\texttt{struct timespec {*}iq\_query\_timespec(PID p, IQUEUE

{*}q);}

\texttt{DWORD {*}iq\_query\_priority (PID p, IQUEUE {*}q);}

\texttt{PID iq\_query\_next (PID p, IQUEUE {*}q);}

\texttt{PID iq\_query\_prev (PID p, IQUEUE {*}q);}

\texttt{int iq\_isempty (IQUEUE {*}q);}

\caption{Prototypes of the task queue handling functions.}

\label{KernSupport_queue_functions}

\end{figure}

Basically, an IQUEUE has an \char`\"{}I\char`\"{}nternal prev/next

structure, that may be shared between one or more queue. Of

course, the user MUST guarantee that the same task will not be

inserted in two IQUEUEs that share the same prev/next buffer.

Internal queue initialization:

\begin{description}

\item [share~=~\&x]the internal data structure of the IQUEUE x is

used to enqueue the tasks. \item [\texttt{share~=~NULL}]an

internal data structure to handle prev/next pairs is dynamically

allocated (The amount of memory that is allocated can be reduced

using the flags). \item [flags]can be used to reduce the memory

usage of an IQUEUE when \texttt{share=NULL}:

\begin{description}

\item [\texttt{IQUEUE\_NO\_PRIORITY}]the iqueue do not provide

internally a priority field \item

[\texttt{IQUEUE\_NO\_TIMESPEC}]the iqueue do not provide

internally a timespec field

\end{description}

note that, if these flags are used, the corresponding insert

functions will not work!. The default value for the flags is, of

course, 0.