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