Introduction

POSIX, that stands for Portable Operating System Interface, is a standard that is being jointly developed by the IEEE and The Open Group. It defines a standard operating system interface and environment, including a command interpreter (or "shell"), and common utility programs to support applications portability at the source code level. The current revision of POSIX is The Open Group Base Specifications Issue 6 and also the IEEE Std 1003.1-2001.

This standard is composed by four major components:

• Base Definitions: This include general terms, concepts and interfaces common to entire standard.

• System Interfaces: This comprises the definitions for system service functions for the C programming language, function and portability issues, error handling and recovery.

• Shell and Utilities: It contains the definitions for a standard source code-level interface to command interpretation services.

• Rationale: It contains information that does not fit well into the rest of the document structure.

The IEEE Std 1003.1-2001 standard is a single common revision to IEEE Std 1003.1-1996, IEEE Std 1003.2-1992, and the Base Specifications of The Open Group Single UNIX Specification, Version 2. In order to develope the current revision several base documents has been used. The base documents that are involved in the definition of system interfaces are:

• IEEE Std 1003.1-1996 (POSIX-1) (incorporating IEEE Stds 1003.1-1990, 1003.1b-1993, 1003.1c-1995, and 1003.1i-1995)

• The following amendments to the POSIX.1-1990 standard:

  • IEEE P1003.1a draft standard (Additional System Services)

  • IEEE Std 1003.1d-1999 (Additional Realtime Extensions)

  • IEEE Std 1003.1g-2000 (Protocol-Independent Interfaces (PII))

  • IEEE Std 1003.1j-2000 (Advanced Realtime Extensions)

  • IEEE Std 1003.1q-2000 (Tracing)

• Open Group Technical Standard, February 1997, System Interface Definitions, Issue 5 (XBD5)

• Open Group Technical Standard, February 1997, System Interfaces and Headers, Issue 5 (XSH5)

• Open Group Technical Standard, January 2000, Networking Services, Issue 5.2 (XNS5.2)

• ISO/IEC 9899:1999, Programming Languages - C.

As it can be observed this standard includes support for source portability of applications with realtime requirements, but this support is maintly optional for POSIX-conforming implementations. The specific functional areas included for realtime support and their definitions[1] are basically the following:

• Semaphores.

  A minimum synchronization primitive to serve as a basis for more complex synchronization mechanisms to be defined by the application program.

• Process Memory Locking.

  A performance improvement facility to bind application programs into the high-performance random access memory of a computer system. This avoids potential latencies introduced by the operating system in storing parts of a program that were not recently referenced on secondary memory devices.

• Memory Mapped Files.

  A facility to allow applications to access files as part of the address space.

• Shared Memory Objects

  An object that represents memory that can be mapped concurrently into the address space of more than one process.

• Priority Scheduling.

  A performance and determinism improvement facility to allow applications to determine the order in which threads that are ready to run are granted access to processor resources.

• Realtime Signal Extension.

  A determinism improvement facility to enable asynchronous signal notifications to an application to be queued without impacting compatibility with the existing signal functions.

• Timers.

  A mechanism that can notify a thread when the time as measured by a particular clock has reached or passed a specified value, or when a specified amount of time has passed.

• Interprocess Communication.

  A functionality enhancement to add a high-performance, deterministic interprocess communication facility for local communication.

• Synchronized Input and Output.

  A determinism and robustness improvement mechanism to enhance the data input and output mechanisms, so that an application can ensure that the data being manipulated is physically present on secondary mass storage devices.

• Asynchronous Input and Output.

  A functionality enhancement to allow an application process to queue data input and output commands with asynchronous notification of completion.

Another optional support that can be interesting for the developemnt of embedded applications is the Threads support. This extension to POSIX defines functionality to support multiple flows of control within a process. These flows of control are called threads and they share their address space and most of the resources and attributes defined in the operating system for the owner process.

The specific functional areas included in threads support are:

• Thread management: the creation, control, and termination of multiple flows of control that share a common address space.

• Synchronization primitives optimized for tightly coupled operation of multiple control flows in a common, shared address space.

Finally, the IEEE Std 1003.1-2001 standard also proposes a set of tracing facilities that can be quite useful at the development stage of a embedded real-time application. The tracing facilities defined in the standard allow a process to select a set of trace event types, to activate a trace stream of the selected trace events as they occur in the flow of execution, and to retrieve the recorded trace events. A trace event is a data object that represents an action executed by the system, and that is recorded in a trace stream. The trace events can be retrieved later from the trace stream, allowing the system behaviour analysis.

All these functionalities are not mandotory in a POSIX-conforming implementation, but defined as a set of options that may be supported by that system. In this line, the IEEE Std 1003.1-2001 standard defines several XSI extensions that groups together several of these options in so-called XSI Option Groups. The option groups that can be of interest for embedded real-time applications are described in the next section.

XSI System Interfaces and Extensions

The X/Open System Interface is the core application programming interface for systems conforming to the Single UNIX Specification. This is a superset of the mandatory requirements for conformance to IEEE Std 1003.1-2001.

A system that wants to be a XSI-conforming implementation shall meet the criteria for POSIX conformance and support all functions and headers defined in IEEE Std 1003.1-2001 as part of the XSI extension. Additionally, it shall support the following options defined in the standard: File Synchronization, Memory Mapped Files, Memory Protection, Threads, Thread Process-Shared Synchronization, Thread Stack Address Attribute and Thread Stack Address Size.

Despite of these options that are mandatory to be a XSI-conforming system, the system may also support one or more of the following XSI Option Groups: Encryption, Realtime, Advanced Realtime, Realtime Threads, Advanced Realtime Threads, Tracing, XSI STREAMS and Legacy. All the realtime option groups jointly with the tracing option group are clearly of great interest for developing embedded real-time applications. The options each option groups requires are detailed next:

Introduction

OSEK/VDX [2] is a joint project of the automotive industry that aims to the definition of an industry standard for an open-ended architecture for distributed control units in vehicles.

The objective of the standard is to describe an environment which supports efficient utilization of resources for automotive control unit application software. This standard can be viewed as a set of API for real-time operating system (OSEK) integrated on a network management system (VDX) that together describes the characteristics of a distributed environment that can be used for developing automotive applications.

The typical applications that have to be implemented have tight real-time constraints and an high criticality (for example, a power-train application). Moreover, these applications have to be made in a huge number of unit, therefore there is a need to reduce the memory footprint to a minimum enhancing as possible the OS performance.

Here are some keywords that helps to better characterize the philosophy that drove the main architectural choices of the OSEK Operating System:

In the following sections the main features of the OSEK/VDX standard will be analyzed in detail.

Architecture of the OSEK/VDX operating system

The architecture on which an OSEK Operating System is based can be viewed as a traditional fixed priority approach.

Each task in the system can be a basic task (BT) or an extended task (ET) (extended tasks are basic tasks that can react to external asynchronous events).

Every task in the system has assigned a fixed priority (statically assigned at compile time), and the scheduler always selects the higher priority task from the ready task queue. Interrupt service routines typically preempt the running task (except in case the running task uses resources).

To provide support for different features in the Operating system, the various requirements of the application in terms of number of tasks, memory consumption and like are listed in four conformance classes. The compliance of an OSEK OS is always stated with respect to one conformance class. Basically, conformance classes exist to allow partial implementations of the standard along pre-defined lines, creating an upgrade path from classes of lesser functionality to classes of higher functionality with no change to the application tasks.

The conformance classes specifies different requirements for the following attributes:

• Multiple requesting task activations (only one activation or more than one)

• Task types (basic tasks only or basic and extended tasks)

• Number of tasks per priority (one or more than one)

The following conformance classes are defined by the standard :

Task Management

In the OSEK OS, a task provides the framework for the concurrent and asynchronous execution of functions. The Scheduler is then responsible for scheduling tasks following a well defined scheduling algorithm.

The OSEK operating system provides two kind of tasks: basic tasks and extended tasks. The only difference between the two concepts is that extended tasks are allowed to use the operating system call WaitEvent(). Basically that call allow an extended task to release the CPU waiting for an asynchronous event without terminating the current instance.

Each task in the system has assigned a fixed priority (statically assigned at compile time; the value 0 is defined as the lowest priority of a task), and it can be preemptive or non-preemptive. If the running task is preemptive the scheduler always made a preemption when needed, otherwise it reschedules the system at the end of the running task instance. A preemptive task can disable preemption for a while locking a resource called RES_SCHEDULER.

In any moment of its life a task is characterized by its state. The OSEK standard defines four task states:

Note that basic tasks have no waiting state: a basic task can only represent a synchronization point at the beginning and at the end of the task. Application parts with internal synchronization points have to be implemented by more than one basic task. An advantage of extended tasks is that they can handle a coherent job in a single task, no matter which synchronization requests are active. Whenever current information for further processing is missing, the extended task switches over into the waiting state. It exits this state whenever corresponding events signal the receipt or the update of the desired data or events.

Depending on the conformance class a basic task can be activated once or multiple times. The latter means that an activation issued when a task is not in the suspended state will be recorded and then executed when the task will finish the current instance.

The termination of a task instance only happen when a task terminates itself (to simplify the OS, no explicit task kill primitives are provided).

Application modes and system startup

The OSEK Operating system gives a support for Application Modes. In real applications, an embedded system may execute different applications in a mutually exclusive way (for example, the normal operation, a factory test, and like). The application mode is a means to structure the software running in the system according to those different conditions and are a clean mechanism for development of totally separate systems. Once the operating system has been started, it is not allowed to change the application mode. Typically each application mode uses its own subset of tasks, ISRs, alarms and timing conditions, although if some kind of sharing between modes is possible.

The start up performance is another safety critical issue for embedded system in automotive applications since reset conditions may occur during normal operation (for example, a power-train application should be capable of rebooting the whole system in a few microseconds, because the system must safely control the spark on the engine cylinders). The system startup is completely left to the particular implementation, although if some hint is given on how design the boot-up sequence. In any case the standard suggest the avoidance of lengthy or complicated starting procedures.

Interrupt processing

Since the standard must be suitable for different microcontrollers, the specification of interrupt handling routines only cover the general approach that a compliant OS should follow, without coping with any hardware related issues.

In particular, the standard provides two kind of ISR handlers:

Inside any ISR no rescheduling will take place. Rescheduling takes place on termination of the ISR category 2 if a preemptable task has been interrupted and if no other interrupt is active. At the end of the ISR category 1 no rescheduling takes place too, and this is the reason because ISR category 1 should have the highest priority in a correct design.

Events

The event mechanism is only provided for extended tasks and can be used to communicate binary information that synchronize these tasks on asynchronous events. Each extended task owns a set of events, that can be triggered by other (basic and extended) tasks or by ISR of category 2.

The typical behavior of an extended task is to wait for asynchronous events calling the OS service WaitEvent(). This service usually blocks the task until an event arrives. After servicing the event, the task calls again WaitEvent() to wait other events.

Events can be set only if the task is not in the suspended state. This seems to suggest that an extended task should never be in the suspended state.

Scheduling

The scheduler decides on the basis of the task priority which is the next of the ready tasks to be transferred into the running state (dynamic priority management is not supported). Tasks on the same priority level are started depending on their order of activation.

The OSEK standard provides four flavors of fixed priority scheduling, outlined below:

Resource Management

The standard provides support for binary resources that can be used to implement critical sections. Priority inversion and deadlock are avoided using a variant of the SRP called OSEK Priority Ceiling.

The protocol in fact is a version of SRP adapted to fixed priority:

• every resource as assigned a ceiling that is the maximum priority of the tasks (and ISRs) that use the resource;

• when a task requires a resource, its current priority is raised to the ceiling of the resource;

• when a task releases a resource, the priority of this task is reset to the priority which was dynamically assigned before requiring that resource.

The normal properties of SRP applies to the protocol. In particular, Priority inversion, chained blocking and deadlocks are avoided. Moreover, there is no need for waiting queues, since a task can be scheduled only when all the resources it needs are free.

Resources are typically used by task only. In the OSEK standard, resources can be used either by a task or by an ISR of category 2. An ISR that use a resource can be thought as an high priority task: its execution can be delayed due to lower ISRs or tasks accessing resources with ceiling greater or equal than the IRS priority. This is the natural behavior in those systems where tasks activations and priorities are mapped on interrupts, and the raising of task's priorities is done with a proper programming of the interrupt controller.

The OSEK standard also provides a support for Preemption Thresholds through the use of internal resources. An internal resource is simply a resource that is locked when a task instance starts, and is unlocked when the task instance ends. The ceiling of the internal resources can be thought as the Preemption Threshold of the tasks.

In the same way the standard provides a special resource called RES_SCHEDULER that can be used to disable preemption. In practice, the RES_SCHEDULER is a resource with ceiling equal to the maximum priority in the system. In the same way a non preemptive task can be thought as a task that use an internal resource with the same ceiling of RES_SCHEDULER.

Finally note that, although a technique similar to Preemption Threshold is used, stack sharing between tasks of a same Non Preemption Group can not be exploited due of the OS calls WaitEvent() and Schedule() [3]. In fact, these calls releases the internal resource taken by a task, letting execution to more than one task in the same Non Preemption Group.

Miscellaneous

The OSEK operating system provides services for processing recurring events (for example, timers that provide an interrupt at regular intervals, or encoders at axles that generate an interrupt in case of a constant change of an angle). These events are recorded into implementation dependent counters, then used by software alarms. When an alarm (that can be one-shot or periodic) fires, a task can be activated, or an event can be set, or finally an alarm-callback routine can be called. Alarms and counters are statically defined at compile time. The only dynamic parameters that can be set are when an alarm has to expire and the period of a cyclic alarm.

To ease the tracing and the debugging of the system the OSEK standard provides system specific hook routines to allow user-defined actions within the OS internal processing. These hook routines are called by the operating system and they are composed by user code that is executed into an OS primitive, usually with ISR of category 2 disabled. These routines are only allowed to use a subset of API functions (mainly they can use functions for get internal OS states, to ease the tracing of the application). They are called at system startup, at system shutdown, before and after a preemption, and in case of an error. In particular, two different kinds of errors are distinguished:

The standard gives two ways of handling errors: a centralized way (using an Error Hook that is called every time an error occurs in a system primitive), and a decentralized way (where the application code must check itself for the correctness of the return value of every primitive).

OSEK COM

The OSEK standard comprises also an agreement on interfaces and protocols for in-vehicle communication called OSEK COM. The term in-vehicle communication means both communication between nodes and internal communication in a node of the whole vehicle. The basic idea is to provide a standardized API for software communication that is independed from the particular communication media used in a way to ease porting of applications between different hardwares.

The OSEK COM standard is composed by:

• An Interaction layer which provides communication services for the transfer of application messages.

• A Network layer which provides services for the unacknowledged and segmented transfer of application messages. The network layer provides flow control mechanisms to enable interfacing of communication peers featuring different level of performance and capabilities.

• A Data link layer interface which provides services for the unacknowledged transfer of individual data packets over a network to the layers above.

OSEK COM provides a rich set of communication facilities but it is likely that many applications will only require a subset of this functionality. For that reason, the standard defines a set of conformance classes to enable the integration of OSEK COM in systems featuring various levels of capabilities in a scalable way, enabling the car producer to integrate software parts produced by different suppliers.

OSEK COM defines these levels as Communication Conformance Classes (CCCs). The main purpose of the conformance classes is to ensure that applications which have been for a particular conformance class are portable across different OSEK implementations and ECUs featuring that same or higher level of communication functionality. OSEK COM defines five communication conformance classes to provide support from ECU internal communication only (CCCA) up to inter-ECU external communication (CCC2).

For an OSEK implementation to be compliant, message handling for intra processor communication has to be offered. The minimum functionality required is CCCA as described in the OSEK COM specification.

OSEK NM

The OSEK standard also cover a standardization of basic and non-competitive infrastructure between the various embedded systems that can be present in a vehicle. In fact, very often electronic control units made by different manufacturers are networked within vehicles by serial data communication links.

For that reason the standard propose a Network Management system (OSEK NM) that provides standardised features which ensure the functionality of inter-networking by standardised interfaces.

The essential task of NM is to ensure the safety and the reliability of a communication network. This is obtained implementing access restriction to each node (access must be restricted only from authorized entities), keeping the whole network tolerant to faults, and implementing diagnostic features capable of monitoring the status of the network in an indirect (monitoring application messages) or in a direct way (monitoring by dedicated NM communication using token principle).

Moreover, the network management also cover the initialization of network resources, network configuration the co-ordination of global operation modes (e.g. network wide sleep mode), and a support for diagnosis.

OSEKTime

The OSEK Standard produced a specification for a Time Triggered Operating System (OSEKtime OS) that aims to represent a uniform functioning environment for single processor distributed embedded control units with a fault-tolerant communication layer.

The OSEKtime operating system supports static scheduling and offers all basic services for real-time applications, i.e., interrupt handling, dispatching, system time and clock synchronization, local message handling, and error detection mechanisms.

The OSEKtime operating system serves as a basis for application programs which are independent of each other, and provides their environment on a processor. The are two types of entities: interrupt services routines managed by the operating system and time triggered tasks.

The Osek Operating system can coexist with a OSEKTime OS, for handling both time triggered and event-driven computations on the same Embedded Control Unit. Basically, the interface of the OSEK OS remains the same (apart from some small changes in the startup/shutdown procedures). The main concept is that the OSEKTime OS assigns its idle time to the OSEK OS.

The OSEK OS, its tasks and its interrupts have always a lower priority than the similar entities in the OSEKTime OS. Non-preemptive tasks remains non-preemptive only in the OSEK/VDX domain, and they can be preempted bt the Time Triggered dispatcher and by the Time Triggered Tasks.

Scheduling

From the very first versions of Linux, the scheduler was realtime POSIX compatible. It supports, among others, the fixed priority (SCHED_FIFO) policy, which is the base feature to build a realtime systems. It also provides the POSIX required: SCHED_RR and SCHED_OTHER. The range of priorities is [0..99].

A lot of work has been done to improve the performance of the scheduler through a careful design which yield to a new scheduler code and structure. Next stable Linux kernel (2.4.19), as well as unstable kernel development (2.5.x), will replace the old scheduler code with an improved "O(1) scheduler" developed by Ingo Molnar . This new scheduler is able to manage a large number of processes with no overhead degradation.

Virtual Memory

It is not possible to build realtime applications on a system with virtual memory. The random and long delays introduced when RAM is exhausted and swapping is required is intolerable in a realtime system. Linux provides the mlock() and mlockall() functions that disables paging for the specified range of memory, or for the whole process respectively. Therefore, all the "locked" memory will stay in RAM until the process exits or unlocks the memory.

mlock() and mlockall() are included in the POSIX realtime extensions.

Shared Memory

One of the main communications paradigms used in realtime applications is shared memory.

Linux processes can share memory with each other and with drivers the POSIX.1b call mmap(). This function can be used both, to map into main memory a regular file and to map shared memory objects. When multiple processes map the same memory object (or file), they share access to the underlying data, which is a efficient way to communicate large amounts of data between processed.

Since version 2.4.x and glibc 2.2 (GNU "C" library), Linux provides open shared memory objects, which is part of the POSIX realtime extensions. This API has the following functions: shm_open() and shm_unlink().

High Resolution POSIX Timers (HRT)

Current POSIX API defines two different timer facilities:

• BSD timers: setitimer() and getitimer() functions.

• IEEE 1003.1b REALTIME timers: timer_create(), timer_settime(), timer_getoverrun(), etc.

This patch can provide high resolution timers with very low overhead because of two main design issues: the use of several timing and interrupt hardware sources (the old 8254, the Pentiun internal instruction TSC, and the ACPI[4] timers when available), and a clever data structure to maintain the timers.

The patch provides high resolution clocks: CLOCK_REALTIME_HR and CLOCK_MONOTONIC_HR. And the accompanying functions: clock_settime(), clock_gettime(), clock_getres(). Also the POSIX timers functions are implemented: timer_create(), timer_delete(), timer_settime(), timer_gettime() and timer_getoverrun().

Realtime Signals

POSIX extended the signals generation and delivery to improve the realtime capabilities. Signals take an important role in realtime as the way to inform the processes of the occurrence of asynchronous events like high-resolution timer expiration, fast inter-process message arrival, asynchronous I/O completion and explicit signal delivery.

The main characteristics of this type of signals are:

• The range of realtime signals supported by Linux is form 32 (SIGRTMIN) to 63 (SIGRTMAX).

• Signals can deliver a small piece of data (an integer or a pointer) to the signal handler (signal-catching function).

• Signals that carry information are delivered in chronological FIFO order.

• It is possible to automatically create a thread in response to a signal.

Linux fully supports the POSIX realtime signals standard.

POSIX Asynchronous I/O

Asynchronous I/O (AIO) is the POSIX interface to provide high efficiency asynchronous I/O access. The standard way to access I/O devices (files, drivers, sockets, fifos, etc.) defined by UNIX the read() write() blocking sequence, where a next file access is performed only when the previous request has been completed. AIO mechanism provides the ability to overlap application processing and I/O operations initiated by the application.

A process can start one or more IO requests to a single file or multiples files and continue its execution. Also, a single system call can start a sequence of I/O operation on one or several files, which reduces the overhead due to context switches.

There are two implementations available in Linux: the one provided at the library level by using non-aio system calls (included in the glibc/librt since version 2.1); and the kernel implementation first developed by SGI™ called KAIO (till linux kernel 2.4.0), and now the Linux-AIO which provides this functionality to newer kernels.

POSIX Threads

Current Linux implementation of POSIX threads (POSIX 1003.1c) is based on the work done by Xavier Leroy, known as LinuxThreads. LinuxThreads is now integrated in the glibc, and distributed as a part of the it. It provides kernel-level threads: threads are created with the clone() system call and all scheduling is done in the kernel. This kind of threading is defined as 1:1, i.e. each thread is mapped to a Linux process.

LinuxThreads implements most of the POSIX API: mutex, condition variables, cancellation, signals, timed calls, etc. The library also provides POSIX semaphores. Mutex do not implement any protocol to prevent priority inversion. Since threads are scheduled by the Linux scheduler, the scheduling policies are the same as in Linux: SCHED_FIFO, SCHED_RR and SCHED_OTHER.

Quality of Service

Nowadays, linux offers a sophisticated component for bandwidth management called Traffic Control. This component supports method for classifying, prioritising, and limiting both incoming and out-coming traffic. Therefore, linux can do the following list of things: limit bandwidth for certain computers, help to fairly share bandwidth, protect the Internet from abuses, restrict access, do routing based on user id, MAC address, source IP address ... and so on.

For working with this subsystem, the kernel versions 2.2.x has to be patched, but the versions 2.4.x and uppers implement directly this functioning.

Compatibility

Linux was developed around UNIX and POSIX standards. Therefore, its native API is mostly POSIX compatible.

Also MontaVista™ developed Wind River pSOS® and Wind River VxWorks® two emulation environments. These emulators are designed to ease the port of legacy RTOS code Linux. The emulation libraries are available at Sourceforge.

Kernel Latency

When scheduling a real-time user-level Linux process, the real-time performance can be affected by bottom halves (BHs) execution, kernel non-preemptable sections, and so on. The kernel latency is a quantity used to measure the difference between the theoretical schedule and the actual one.

The kernel latency is defined as follows: Let T be a real-time process that requires execution at time t, and let t' be the time at which T is actually scheduled; we define the kernel latency experienced by T as L = t' - t.

The biggest source of kernel latency are kernel non-preemptable sections (including BHs and Interrupt Service Routines - ISRs). In fact, non-preemptable sections in the kernel can prevent a high priority task from being scheduled for a very long time (up to 100ms). For example, if interrupts are disabled at time t, task T can only enter the ready queue later when interrupts are re-enabled. In addition, even if T enters the ready queue at the correct time t and has the highest real-time priority in the system, it may still not be scheduled if another task is running in the kernel in a non-preemptable section. In this case, T will be scheduled when the kernel exits the non-preemptable section at time t'.

The length of a kernel non-preemptable section depends on the strategy that the kernel uses to guarantee the consistency of its internal structures, and on the internal organization of the kernel. The standard Linux kernel is based on the classical monolithic structure, in which the consistency of kernel structures is enforced by allowing at most one execution flow in the kernel at any given time. This is achieved by disabling preemption when an execution flow enters the kernel, i.e., when a system call is invoked or when an interrupt fires. When a system call is invoked, the thread that invokes it enters in the kernel and becomes non-preemptable, returning preemptable when the execution exits from the kernel. When an interrupt fires, a short ISR is invoked with interrupts disabled: the ISR acknowledges the hardware interrupt and schedules a BH for execution. The BH will be executed in a non-preemptive way immediately before returning to user mode; hence, if the ISR interrupts a system call, the BH will be executed only after that the system call is completed (system calls can synchronize with ISRs by explicitly disabling interrupts). Summing up, in a standard Linux kernel, the maximum latency is equal to the maximum length of a system call plus the processing time of all the interrupts that fire before returning to user mode. Unfortunately, this value can be as large as 100ms.

Possible Solutions

Two different approaches can be used to reduce the size of kernel non-preemptable sections: the one used by the Low-Latency patches (Ingo Molnar and Andrew Morton)[LowLat], and the one used by the kernel preemptability patch (MontaVista, TimeSys)[kpreem, TimeSys].

Evaluation

We measured the latency for the standard, Low-Latency, preemptable and preemptable with lock-breaking kernels while running different loads in background. All the experiments were performed using the Latency Benchmark tool downloadable from [FT]. The results are shown in the following figures:

From the first figure, it is possible to see that standard Linux exhibits high latencies at the end of the memory stress (a program that reads and writes a large array in memory), during the I/O stress (a program that reads and writes large amount of data on a file), when accessing the /proc file system, and when switching the caps/lock led. The large latency at the end of the memory stress is due to the munmap() system call. Comparing the figures it is possible to see that the low latency kernel solves all the problems except the /proc file system access and the caps/lock switch. On the other hand, the preemptable kernel eliminates the large latency in the /proc fs access, but does not solve the problem with the memory stress, and is not as effective as the low latency kernel in reducing the latency during the I/O stress. Finally, the lock-breaking preemptable kernel seems to provide good real-time performance, but still has some problem during the I/O stress.

By repeating similar experiments for longer amounts of time, we verified that the low-latency kernel is characterized by larger average latencies respect to the preemptable and lock-breaking preemptable kernels, but reduces the worst case latencies. In other words, the tail of the probability distribution function is shorter for a low-latency kernel. As an example, the PDFs of the latency during the I/O stress are reported in the following figures (note that this new experiments were performed on a computer that is faster than the one used for the previous experiments).

According to the previous figures, it seems that the low-latency patch provides better real-time performance. This is probably due to the fact that the Linux kernel still contains ``big spinlocks'' that are held for long amounts of time, and that the lock-breaking patch does not ``break'' properly. A classical example is the spinlock used to serialize BHs. However, in the future Linux developers will likely decrease the size of kernel critical sections (to improve SMP performance), hence it seems to be reasonable to think that the latency of the preemptable and lock-breaking preemptable kernel will decrease.

Architecture overview

There are two approaches to provide real-time performance in a Linux system:

1. Improving the Linux kernel preemption.

2. Adding a new software layer beneath Linux kernel with full control of interrupts and processor key features.

RTLinux is a small, fast operating system, following the POSIX 1003.13 "minimal realtime operating system" standard.

RTLinux adds a layer of virtual hardware between the standard Linux kernel and the computer hardware (see Figure 8-1). As far as the standard Linux kernel is concerned, this new layer appears to be the actual hardware. RTLinux implements a complete and predictable RTOS with no interference from the non-real-time Linux. The RTLinux threads are executed directly by a fixed-priority scheduler. The whole Linux kernel, and all the normal Linux processes, are managed by the RTLinux scheduler as the background task. This way, it is possible to have a complete general purpose operating system running on top of a small predictable RTOS.

There are three main modifications done to the Linux kernel in order to virtualize the hardware so that RTLinux can take full control of the machine: The RTLinux layer takes direct control of all the hardware interrupts, interrupts that are not controlled by real-time threads are forwarded to the Linux upper level; RTLinux also takes the control of the timer hardware (8254 and APIC when available) and implements a virtual timer to Linux; and the last modification done to Linux to remove the basic control of the hardware from Linux is to replace all the cli and sti (disable and enable interrupt flag) functions calls from the Linux kernel so that Linux can no make a real disable but a virtual interrupt disable. These modifications are quiet complex and tricky, but do not require large code (Linux) modifications.

RTLinux provides an execution environment "below" the Linux kernel. One consequence of this, is that realtime threads can not use Linux services because deadlock or system inconsistencies may happen. To overcome this problem, the realtime system has to be divided into two separated layers: the hard realtime layer, executed on top of RTLinux, and the soft realtime, executed as normal Linux processes. Several mechanisms (FIFO, shared memory) can be used to communicate threads in both layers.

The two layer approach is a useful method to provide hard realtime while having all the features of a desktop operating system. It decouples the mechanism of the realtime kernel from the mechanism of the general purpose Linux kernel so that each system can be optimized independently.

Hardware characteristics

Process management

Memory management