%----------------------------------------------------------------------------
\chapter{Introduction}
%----------------------------------------------------------------------------
Real-time computing is required in many application domains, ranging
from embedded process control to multimedia systems. Each application
has peculiar characteristics in terms of timing constraints and computational
requirements (such as periodicity, criticality of the deadlines, tolerance
to jitter, and so on). For this reason, a lot of different scheduling
algorithms and resource allocation protocols have been proposed to
conform to such different application demands, from the classical
fixed or dynamic priority allocation schemes to adaptive or feedback-based
systems.
However, most of the new approaches have been only theoretically analyzed,
and sometimes evaluated using a scheduling simulator. In this case,
the algorithm performance is not evaluated on real examples, but only
on a synthetic workload. This choice is often dictated from the fact
that writing a kernel from scratch every time a new scheduling algorithm
is proposed would be unrealistic and would not offer the availability
of meaningful applications. A more effective approach is to modify
an existing kernel (such as Linux), since most of the existing applications
and device drivers written for the host OS can be used in a straightforward
fashion. On the other hand, a general purpose kernel is designed aiming
at specific goals and generally its architecture is not modular enough
for replacing or modifying the scheduling policy. Moreover, classical
OSs do not allow to easily define a scheduling policy for resources
other than the CPU and this poses a further limitation for testing
novel research solutions. This is mainly due to the fact that the
classical OS structure does not permit a precise
\emph{device scheduling}
(due to problems involving resource contention, priority inversion,
interrupt accounting, long non-preemptive sections, and so on). A
small kernel providing short non-preemptable sections, aperiodic real-time
threads for handling interrupts, and a distinction between \emph{device
drivers} accessing the hardware and \emph{device managers} implementing
the \emph{device scheduling} algorithms would help the progress in
this research field. The problems explained above emerge both in the
educational and research environments, when the focus is oriented
in developing and testing new scheduling algorithms rather than hacking
the code of a complex system.
S.Ha.R.K. (Soft and Hard Real-time Kernel), is a research kernel purposely
designed to help the implementation and testing of new scheduling
algorithms, both for the CPU and for other resources. The kernel can
be used to perform early validation of the scheduling algorithms produced
in the research labs, and to show the application of real-time scheduling
in real-time systems courses. These goals are fulfilled by making
a trade off between simplicity and flexibility of the programming
interface on one hand and efficiency on the other. This approach allows
a developer to focus his/her attention on the real algorithmic issues,
thus saving significant time in the implementation of new solutions.
Another important design guideline is the use of standard naming conventions
for the support libraries in order to ease the porting of meaningful
applications written for other platforms. The results have been satisfactory
for applications such as an MPEG player, a set of network drivers
and a FFT library.
The kernel provides the basic mechanisms for queue management and
dispatching and uses one or more external configurable modules to
perform scheduling decisions. These external modules can implement
periodic scheduling algorithms, soft task management through real-time
servers, semaphore protocols, and resource management policies. The
modules implementing the most common algorithms (such as RM, EDF,
Round Robin, and so on) are already provided, and it is easy to develop
new modules. Each new module can be created as a set of functions
that \emph{abstract} from the implementation of the other scheduling
modules and from the resource handling functions. Also the applications
can be developed independently from a particular system configuration,
so that new modules can be added or replaced to evaluate the effects
of specific scheduling policies in terms of predictability, overhead,
and performance. Low-level drivers for the most typical hardware resources
(like network cards, graphic cards, and hard disks) are also provided,
without imposing any form of device scheduling. In this way, device
scheduling can be implemented by the user to test new solutions. To
avoid the implementation of a new non-standard programming interface,
which would discourage people from using the kernel, S.Ha.R.K. implements
the standard POSIX 1003.13 PSE52 interface
%
% Tool: no such reference!
%
% \cite{POSIX1003.1,POSIX1003.13}
.
This manual was derived from the Hartik User Manual release 3.3.1.
%----------------------------------------------------------------------------
\section{General Description}
%----------------------------------------------------------------------------
S.Ha.R.K. has been designed as a library of functions which extends
the classical C library, by providing a multiprogramming environment
with an explicit management of time. From a logical point of view,
the system is based on a
\emph{Host} computer where the application
is developed and on a \emph{Target} computer where the application
executes. Development tools are located on the host system, where
a general purpose operating system is used. After its compilation,
the application is loaded on the target system using the appropriate
\emph{loader}. This separation, typical of many hard real-time development
systems, enables the final application to run on a variety of target
systems, ranging from typical PC to embedded micro-controllers. From
a practical point of view, host and target may be the same computer
and in the rest of this manual we will not further distinguish between
them.
S.Ha.R.K. has been developed focusing on modularity of the kernel
source code. S.Ha.R.K. is fundamentally a set of routines that runs
on top of a library for OS development called OSLib (see http://oslib.sourceforge.net)
that has these requirements:
\begin{description}
\item [Operating~System~(OS)]You can compile OSLib/S.Ha.R.K. programs
using some different host OS. In theory, any OS supporting gcc can
be used; in practice, we successfully compiled OSLib/S.Ha.R.K. from
Linux, DOS and Cygwin.
\item [Compiler]The used compiler is gcc. You can use the gcc version that
you prefer (we tested gcc 3.3.3 and older version), the important
thing is that the linker must produce ELF binaries (in order to be
MultiBoot compliant and to avoid problems with the Linux source code
inside S.Ha.R.K.). An ELF cross-compile version of gcc is included
inside the DJGPP distribution on the S.Ha.R.K. website, so you can
easily compile OSLib/S.Ha.R.K. programs inside a standard DOS environment.
To compile under Cygwin, it is required to build an ELF cross-compile
gcc/linker couple.
\item [Other~utilities]GNU Make \index{Make}, uname, pwd, cp, rm, X (these
utilities can be found in the utility package on the S.Ha.R.K. web
site).
\item [Target~Requirements]The target have to be at least a PC based on
Intel 80486 (or compatible) - SMP is not supported - with at least
4Mb of RAM. In order to load OSLib/S.Ha.R.K. programs (MultiBoot compliant),
the target must have GRUB installed, or it must run a real mode operating
system (such as MS-DOS or FreeDOS). If you intend to boot OSLib/S.Ha.R.K.
programs from DOS, you also have to download our DOS eXtender X.
\end{description}
Compilation and application linking can be done using the \emph{make}\index{make}
utility, available in any of the development environments mentioned
above. In this case, a {}``makefile''\index{makefile} containing
the names of all of the .C files composing the application and the
directives to link the needed libraries have to be written. For more
information, you can look at the installation txt file from the website
download page.
%----------------------------------------------------------------------------
\section{SHARK.CFG}
%----------------------------------------------------------------------------
Inside
\texttt{shark.cfg} you can find the main parameters for S.Ha.R.K.
configuration. All the stettings inside this file will be crucial
to run correctly S.Ha.R.K. and to get the maximum performaces on a
x86 machines. The most important options related to the Real-Time
behaviour are:
\begin{description}
\item MEM\_START = [number]
\end{description}
\begin{itemize}
\item Kernel image start point. The kernel image file will be loaded starting
from this physical memory address. Default value is 0x220000, but DOS users,
should set an high address (like 0x1720000) if Smartdrive or other tools which
require Extended Memory are used.
\end{itemize}
\begin{description}
\item TSC = [TRUE,FLASE]
\end{description}
\begin{itemize}
\item This option enables the Time Step Counter inside the CPU (Pentium
or higher). Kern\_gettime function will use the TSC register which
is faster and more precise than the external PIT. The default value
is TRUE. If the system cannot find the TSC, this feature will be disabled
and PIT will be used to get the system time.
\end{itemize}
\begin{description}
\item APIC = [TRUE,FALSE]
\end{description}
\begin{itemize}
\item This option enables the APIC (Pentium Pro or higher). As TSC, APIC
is faster and more precise than the standard PIT. It will be used
to generate the timer interrupts. The default value is TRUE. If the
system cannot find the APIC, the feature will be disabled. On some
embedded systems or old PC, the APIC check could hang the system,
so you must disable it manually. APIC requires the TSC.
\end{itemize}
\begin{description}
\item TIMER\_OPT = [1000,2000,4000,8000]
\end{description}
\begin{itemize}
\item Enable TSC read timer optimization. The 4 values are suggested for
different CPU speeds, allowing different wraparound performance: TIMER\_OPT =
1000 for CPU < 1 GHz, wraparound of 585 years; TIMER\_OPT = 2000 for 1 GHz <
CPU < 2 GHz, wraparound of 146 years; TIMER\_OPT = 4000 for 2 GHz < CPU < 4 GHz,
wraparound of36 years; TIMER\_OPT = 8000 for CPU < 8 GHz, wraparound of 292
years.
\end{itemize}
\begin{description}
\item TRACER = [NO,OLD,NEW]
\end{description}
\begin{itemize}
\item Select the tracer to be used for tracing events. While TRACER = OLD is for
backward compatibility, TRACER = NEW should be the preferred option when event
tracing is required. The event tracer can be disabled by selecting TRACER = NO.
\end{itemize}
\begin{description}
\item BIOS = [X,VM86]
\end{description}
\begin{itemize}
\item Select the BIOS interrupt access mode. BIOS = X means that you must use
x.exe as shark loader if shark needs to call BIOS interrupt (Ex. to enable
graphics); BIOS = VM86 means that shark call the BIOS interrupts as Virtual
Machine 86, and you can load a graphical demo also through GRUB.
\item Notice that VM86 MODE IS NOT COMPATIBLE WITH SOME VGA CARDS (like MATROX).
\end{itemize}
\begin{description}
\item FB = [VESA,FINDPCI,VGA16]
\end{description}
\begin{itemize}
\item Select the FrameBuffer configuration. It can use the VBE interrupts to
enable the selected video mode (VESA), or enable the VGA16 (4 bit per plane)
video mode (VGA16). Using FINDPCI, the FrameBuffer driver will try to find a
PCI/AGP graphical card. If a card is found, FB will use a specific driver to
enable it; however, few graphic adapters are currently supported with specific
drivers. Since almost all adapters support the VESA standard, FB = VESA is
usually the best choice.
\end{itemize}
\begin{description}
\item FG = [NORMAL,FORCE\_PXC]
\end{description}
\begin{itemize}
\item Select the FrameGrabber configuration. FORCE\_PXC forces the frame grabber to init a PXC200 card, and should be used carefully.
\end{itemize}
\begin{description}
\item SHARK\_FS = [YES,NO]
\end{description}
\begin{itemize}
\item Select the S.Ha.R.K. file system support. SHARK\_FS = YES makes the kernel
to include the File System library, which supports the FAT16 filesystem only. If
you don't have a FAT16 filesystem, set SHARK\_FS = NO.
\end{itemize}
\begin{description}
\item [{\Large NOTE:}]{\Large You must recompile S.Ha.R.K. if you modify}
\texttt{\Large shark.cfg}{\Large \par}
\end{description}
%----------------------------------------------------------------------------
\section{Predefined Types and Constants}
%----------------------------------------------------------------------------
Tables~
\ref{t:types}, \ref{t:task}, \ref{t:stati}, \ref{t:limits}
show a subset of the predefined data types in S.Ha.R.K., a subset
of the possible task states and Models and the system basic constants.
\begin{table}
\begin{center}\begin{tabular}{|l|l|}
\hline
\emph{Type} & \emph{Description} \\
\hline
BYTE & unsigned char, {[}0, 255{]} \\
WORD & unsigned int, {[}0, 65535{]} \\
DWORD & unsigned long, {[}0, 0xFFFFFFFF{]} \\
TIME & unsigned long, {[}0, 0xFFFFFFFF{]} \\
PID & Task identifier \\
TASK & task \\
PORT & communication endpoints \\
CAB & cyclic asynchronous buffers \\
\hline
\end{tabular}\end{center}
\caption{\label{t:types}Predefined types.}
\end{table}
\begin{table}
\begin{center}\begin{tabular}{|l|c|}
\hline
\emph{Identifier} & \emph{Value}\\
\hline
FREE & 0 \\
EXE & 1 \\
SLEEP & 2 \\
WAIT\_JOIN & 3 \\
WAIT\_COND & 4 \\
WAIT\_SIG & 5 \\
WAIT\_SEM & 6 \\
WAIT\_NANOSLEEP & 7\\
WAIT\_SIGSUSPEND & 8 \\
WAIT\_MQSEND & 9\\
WAIT\_MQRECEIVE & 10 \\
\hline
\end{tabular}\end{center}
\caption{\label{t:stati}Task states. (Note that a scheduling module can add
its private task states.)}
\end{table}
\begin{table}
\begin{center}\begin{tabular}{|l|c|}
\hline
\emph{Identifier} & Class \\
\hline
HARD\_TASK\_MODEL & Periodic and sporadic hard tasks \\
SOFT\_TASK\_MODEL & Periodic and aperiodic soft tasks\\
NRT\_TASK\_MODEL & Non-real-time tasks \\
JOB\_TASK\_MODEL & A task instance (job) that can be inserted into another module \\
DUMMY\_TASK\_MODEL & Model used for the Dummy Task \\
ELASTIC\_TASK\_MODEL & Elastic task, used with the Elastic Module \\
\hline
\end{tabular}\end{center}
\caption{\label{t:task}Basic Task Models included with the default distribution
(see include/kernel/model.h).}
\end{table}
\begin{table}
\begin{center}\begin{tabular}{|l|c|}
\hline
\emph{Identifier} & \emph{Value} \\
\hline
MAX\_PROC & 66 \\
MAX\_RUNLEVEL\_FUNC & 40 \\
JET\_TABLE\_DIM & 20 \\
MAX\_CANCPOINTS & 20 \\
MAX\_SIGINTPOINTS & 20 \\
MAX\_SCHED\_LEVEL & 16 \\
MAX\_RES\_LEVEL & 8 \\
MAX\_LEVELNAME & 20 \\
MAX\_MODULENAME & 20 \\
MAX\_TASKNAME & 20 \\
NIL & -1 \\
RUNLEVEL\_STARTUP & 0 \\
RUNLEVEL\_INIT & 1 \\
RUNLEVEL\_RUNNING & 3 \\
RUNLEVEL\_SHUTDOWN & 2 \\
RUNLEVEL\_BEFORE\_EXIT & 4 \\
RUNLEVEL\_AFTER\_EXIT & 5 \\
NO\_AT\_ABORT & 8 \\
\hline
\end{tabular}\end{center}
\caption{\label{t:limits}System constants (see include/kernel/const.h).}
\end{table}