Subversion Repositories shark

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

\subsection{Introduction}

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

Low-level support of peripheral devices is one of the most

demanding activities in a real-time system for control

applications. In fact, the rapid development of new interface

boards and the continuous upgrade of hardware platforms causes a

tremendous effort at the operating system level for writing and

testing low-level drivers for supporting the new hardware. The

possibility of reusing legacy drivers in real-time systems would

offer the great advantage of keeping the rate of changes with a

small programming effort. Since typical legacy drivers are written

to execute in a non-preemptive fashion, a suitable operating

system mechanism is needed to protect real-time application tasks

from unpredictable bursty interrupt requests.

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

\subsection{Why do we need a new server technology ?}

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

The rapid development of new interface boards and the continuous

upgrade of hardware platforms causes a tremendous effort at the

operating system level for writing and testing the low-level

software to support new peripheral devices. The problem of device

management is particularly significant in those embedded systems

dedicated to control applications, where the number of I/O

peripherals is usually large. In these systems, the code layer

dedicated to device drivers is one of the most delicate

components. The possibility of reusing legacy drivers in real-time

systems would offer the great advantage of keeping the pace of

changes with a small programming effort.

One of the main problems of reusing legacy drivers in a real-time

system, however, is that most interrupt handlers disable the

interruption capability of the processor, executing long portions

of code at the highest priority in a non-preemptive fashion. As a

consequence, a bursty sequence of interrupts may introduce long

blocking delays in application tasks, which would cause hard tasks

to miss their deadlines and soft tasks to increase their response

time. Under such an execution model for the interrupts, an

off-line guarantee of real-time constraints could require the

system to run with a very low utilization.

Inside S.Ha.R.K. this is possible. The modules stack is instrinsically

hierarchical and the idle time of the first kernel module becomes the

execution time for the next one (\ref{f:intserver3}).

\begin{figure}

\centering

\includegraphics[width=0.5\columnwidth]{images/int-server3}

\caption{\small S.Ha.R.K. module stack}

\label{f:intserver3}

\end{figure}

Splitting the scheduler, the server algorithm becomes system independent and,

therefore, it makes it possible to transparently use FP and EDF scheduling

algorithms.

This approach also keeps the server algorithm simple, just to fit our

requirements for the IRQ and timers handling, leaving the main scheduler out

from this specific problem.

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

\subsection{Server features}

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

The server features are

\begin{itemize}

\item

The handler is always executed in a non preemptive fashion, but

the server limits its bandwidth consumption through a suitable

budget management that allows guaranteeing the other real-time

activities.

\item

A hierarchical scheduling approach \cite{Lip03} is employed

to make the interrupt service mechanism independent of the

scheduling policy, so that either fixed or dynamic priority

assignments can be used for the application tasks.

\item

The server can be tuned to balance its responsiveness versus its

bandwidth consumption.

\item

The mechanism can be efficiently implemented to reduce the extra

overhead typically required in capacity-based servers to set the

timers for the budget management.

\item

Finally, the context-switch overhead introduced by the interrupt

requests can be easily taken into account in the guarantee test

for the application tasks.

\end{itemize}

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

\subsection{Server description}

\label{s:desc}

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

The novel server mechanism proposed in this paper aims at

executing interrupt requests coming from complex legacy drivers

imported into a real-time kernel from widely available open source

operating systems. Since a device driver may be imported as it is,

with very few or even without modifications, it is important to

provide a method to safely schedule the requests without

jeopardizing the internal driver temporization, keeping the

developer away from the low-level details of the driver

implementation and saving a lot of programming efforts. To achieve

this goal, the interrupt service routines are always executed in a

non preemptive fashion, but a budget management mechanism is used

in the server to protect the application tasks from unbounded

interference, in the case of long bursty interrupt requests.

As a consequence of such a budget management mechanism, an ISR can

experience a bounded activation delay, which can be tuned through

the server parameters to balance application predictability vs.

interrupt responsiveness.

The server is defined by 3 parameters: a maximum budget $Q_{max}$,

a bandwidth $U$, and a budget threshold $Q_\theta$. The server

also keeps two state variables: its current budget $Q(t) \leq

Q_{max}$ and an activity state $\Phi(t)$, which can have three

values:

\begin{itemize}

\item

$exe$. The server is in this state when it executes an ISR;

\item

$ready$. The server is ready when there are no pending interrupt

requests and a new incoming request can be executed immediately

without any activation delay;

\item

$idle$. The server is idle when a new request cannot be immediately

executed because the previous requests consumed the available budget

below the threshold $Q_\theta$. In this state, the budget is

recharged

according to a given replenishment rule, until the maximum level

$Q_{max}$ is reached or a new request arrives.

\end{itemize}

The maximum budget ($Q_{max}$) is the upper bound for the current

budget and limits the number of ISRs that can be consecutively

executed by the server. The budget $Q(t)$ is decreased while an

ISR is executing to keep track of the remaining budget that can be

allocated to other requests. To prevent any preemption of the

server, the budget is allowed to be negative. When no request is

executing, $Q(t)$ is recharged at a constant rate.

The $U$ parameter specifies the percentage of processor allocated

to the server, which leaves a bandwidth $1-U$ to the application

tasks. The value of $U$ directly influences the server budget

$Q(t)$, which increases at rate $U$ when the server is ready or

idle, and decreases at rate $1-U$ when the server is executing.

A higher value of $U$ makes the budget to decrease more slowly (see

Section \ref{s:rules} for the detailed budget variation rules),

thus allowing the execution of a higher number of ISRs before

starting the recharge. On the contrary, decreasing the value of

$U$ makes the budget to increase more slowly, thus letting more

space for the application tasks.

The budget threshold $Q_\theta$ ($0 \leq Q_\theta \leq Q_{max}$)

defines the budget level above which the server can start

executing pending requests after an idle period. In other words,

when the budget is exhausted ($Q < 0$) a new request can only be

started when the budget is replenished up to $Q_\theta$. However,

if $Q > 0$ and the server is ready, an ISR can be executed even

though $Q \leq Q_\theta$.

Decreasing the value of $Q_\theta$ decreases the latency of the

ISR, while increasing $Q_\theta$ decreases the overhead introduced

by the server during IRQ bursts.

While the server is $idle$, the ISRs that cannot be executed due to

the bandwidth limitations are sent to a ready queue, which can be

handled by an arbitrary discipline.

Then, they are fetched from the queue when the processor can be

safely assigned to the server, meaning that the execution of an

interrupt service does not jeopardize the temporal requirements of

the application tasks.

Two examples of server execution are reported in Figure

\ref{f:budget} to better illustrate the budget management

mechanism and the server state transitions.

\begin{figure}

\centering

\includegraphics[width=\columnwidth]{images/budget1}

\includegraphics[width=\columnwidth]{images/budget2}

\caption{Examples of server budget behavior.}

\label{f:budget}

\end{figure}

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

\subsection{Server rules}

\label{s:rules}

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

This section presents the rules that regulate the variation of the

budget and the state transitions.

Budget consumption and recharging is regulated by the following

rules:

\begin{enumerate}

\item

At the system start-up $\Phi(0) = idle$ and the initial budget is

set to $0$, i.e., $Q(0) = 0$.

\item

While $\Phi=idle$ or $\Phi=ready$, the budget increases at a

constant rate $U$ up to its maximum value. If $Q(t_1)$ is the

budget at time $t_1 < t_2$, then

\begin{equation}

\label{equ:inc}

Q(t_2) = \min \{Q_{max}, \; Q(t_1) + (t_2 - t_1)U\}.

\end{equation}

\item

While $\Phi=exe$, the budget decreases at a constant rate equals

to $1-U$. If $Q(t_1)$ is the budget at time $t_1 < t_2$, then

\begin{equation}

\label{equ:dec}

Q(t_2) = Q(t_1) - (t_2 - t_1)(1 - U).

\end{equation}

\end{enumerate}

The activity status of the server is determined by the current

available budget, by the previous server status and by the presence

or absence of pending ISRs into the ready queue. The status

switches accordingly with the following rules:

\begin{itemize}

\item

The initial state of the server is $idle$;

\item

When an IRQ arrives, if $\Phi$ is $exe$ or $idle$ the ISR is sent to

the ready queue and the server maintains its current state;

\item

When an IRQ arrives, if $\Phi=ready$ the server starts executing the

handler and $\Phi=exe$;

\item

When an interrupt handler terminates the execution, if $Q(t) < 0$

$\Phi$ switches from $exe$ to $idle$; if $Q(t) \geq 0$ and the

ready queue is empty, the server switches to $ready$, otherwise,

if an ISR is waiting in the queue, the server keeps the $exe$ state

and starts executing the next ISR;

\item

When $Q(t)$ increases $\Phi$ can only be $idle$ or $ready$. If $\Phi

= idle$, when $Q(t)$ reaches $Q_\theta$ and the ready queue is

empty,

the server switches to $ready$; if the queue is not

empty it switches to $exe$ and starts executing the first pending

request. If $\Phi = ready$, when $Q(t)$ reaches $Q_\theta$

the server keeps its current status and keeps recharging up to

$Q_{max}$ if there are no IRQs to execute.

\end{itemize}

\begin{figure}

\centering

\includegraphics[width=\columnwidth]{images/fsm}

\caption{Server finite-states machine.}

\label{f:fsm}

\end{figure}

These rules are illustrated in Figure~\ref{f:fsm} as a finite-state

machine.

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

\subsection{Server Properties}

\label{s:prop}

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

The proposed interrupt server is characterized by the following

interesting properties:

\begin{itemize}

\item

the response time of every single ISR can be predicted in order to

perform an online guarantee of incoming requests;

\item

the implementation overhead can be traded for the ISR latency by

acting on the budget threshold $Q_\theta$;

\item

the server parameters can be directly used to specify the bandwidth

allocation within a hierarchical framework.

\end{itemize}