Subversion Repositories shark

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

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