An open source software library to enhance Linux/RTAI
Feb 4, 2005 — by LinuxDevices Staff — from the LinuxDevices Archive — 5 viewsForeword — This paper presents Cleopatre, a library of GPL'd components that enhance scheduling, synchronization, aperiodic task servicing, and fault tolerance in RTAI or “any other RTOS,” according to the authors. The components were developed as part of a publicly funded research project in France. Enjoy . . . !
1. Introduction
General-purpose operating systems are not designed to meet the timing constraints of real-time processes. Since its birth, Linux has undergone extensive growth that has made it one of the most robust and efficient operating systems and besides a very good candidate for a potential RTOS.
Recently, we have been working on a RTOS project, namely Cleopatre (work supported by the French research office, grant number 01 K 0742) based on Linux. One of the most important reasons for us choosing Linux as the foundation of our project is due to the open source policy behind it that allows it to grow constantly. Several projects have pursued the same goal such as RT-Linux and RTAI which both implement a small real-time kernel underneath but outside of the Linux kernel. Our approach is to add new real-time capabilities to Linux, yet keep all existing Linux and RTAI capabilities. Cleopatre can be viewed as a library of components that provides selectable real-time facilities and in addition a specific module which makes it possible to use the components with Linux through RTAI.
The Cleopatre components are contained in dynamic modules of Linux and provide an external interface for the application. These components have been tested in the integration phase of the project and the demonstrator has been a mobile robotic platform. To facilitate the integration of the application software or additional components, we have developed several features from the last year, which will be detailed below [1].
Cleopatre proposes four categories of components respectively dedicated to scheduling, synchronization, fault tolerance and aperiodic servicing. Only the first one is necessary. The other ones are optional and selectable by the application user. The main problem encountered during the implementation of these components was their separation in different Linux dynamic modules.
Stand alone RTAI is not able to support Cleopatre components. To make that possible, RTAI must be patched with a software module called Task Control Layer (TCL). TCL provides an “internal interface” for the components, low level mechanisms and data structures such as the following:
- Creation and destruction of tasks adapted to Linux/RTAI
- Switching to real time mode and getting back from it
- Lists of task descriptors
- Watchdog for every task
- A system clock generates periodic events
Native RTAI applications can still run under Cleopatre environment; nevertheless, tasks that have been created with the native RTAI interface cannot use Cleopatre primitives. And tasks issued from the Cleopatre interface cannot use the native RTAI primitives.
RTAI schedules Linux as a background task. As a result Linux processes are scheduled whenever there is no activity from RTAI. And TCL allows RTAI to run its tasks whenever there is no activity from Cleopatre.
TCL is the abstraction layer that permits to make the components as generic as possible. Using components with other versions of RTAI or other RTOSes is made possible by only modifying TCL software. TCLCreateType is a Cleopatre structure that gathers all the parameters needed to create tasks for any RTOS. Usually, the components do not use these data, but they can transmit them to TCL without loosing genericity.
2. Library of components
2.1 Scheduling
Static and dynamic priority driven schedulers, including Deadline Monotonic and Earliest Deadline First are available in the Cleopatre library [2][3]. Tasks may be periodic or not and characterized by a critical delay less than or equal to the period. Programmers may change from one scheduler to another in loading the corresponding component without involving recompilation of their application.
2.2 Semaphores
Three components in this category are easy to implement: SPP (Super Priority Protocol) that gives a super priority to the task that locks a semaphore, FIFO which releases the task that waits for a semaphore the longest, and “priority” which releases the blocking task with the highest priority. Moreover, the library contains a Priority Inheritance Protocol, namely PIP, usable with a static or a dynamic priority scheduler [4].
Finally, to avoid both deadlocks and priority inversions, Cleopatre provides priority ceiling protocols: PCP (Priority Ceiling Protocol) and DPCP (Dynamic Priority Ceiling Protocol) respectively designed for a static and a dynamic priority driven scheduler [5][6]. Both need to know the list of semaphores possibly locked by the tasks.
2.3 Fault tolerance
Two fault tolerance mechanisms have been implemented in Cleopatre: The Imprecise Computation and the Deadline Mechanism.
The imprecise-computation technique is a way to deal with transient overloads. The technique is motivated by the fact that one can often trade off precision for timeliness. It prevents missed deadlines and provides graceful degradation during a transient overload. A task based on this model consists of two or more logical parts: a mandatory part and at least one optional part.
The mandatory part should include all the operations necessary to produce a logically correct result. The optional part, on the other hand, includes all the other operations. In other words, operations included in the optional part only affect the quality of result. In order to ensure this, there is a rigid precedence constraint between these two parts: the mandatory part must always complete before the corresponding optional part starts its execution. In our implementation, a task may have more than one optional part.
With the Deadline Mechanism, each fault-tolerant task is implemented as two distinct tasks (primary and backup copy) [7]. Hence, whenever a task tries to execute for an interval of time longer than its reserved execution time, it is suspended and the scheduler is able to guarantee the execution of the backup copy which never executes unnecessarily, using the so-called Last Chance strategy.
In our implementation, the processor time reserved for the execution of the backup copy is realized with EDL (Earliest Deadline as Late as possible) algorithm and is reclaimed as soon as the primary task executes successfully. This technique, above all, permits failure recovery coming from an under-estimated evaluation of the execution time required by primary tasks or programming errors which produce unbounded computation times like infinite loops.
2.4 Aperiodic task servicing
An aperiodic task server aims to schedule soft and hard aperiodic tasks together with periodic tasks. Whenever a hard aperiodic task occurs, an acceptance test is performed in order to verify the feasibility of the resulting schedule. If the aperiodic task is rejected, a message is printed. Whenever a soft aperiodic task occurs, it is scheduled so as to minimize its response time. Soft aperiodic tasks are served on a FCFS (First Come First Serve) basis.
Three servers are available in the library: BG (Background server), EDL (Earliest Deadline as Late as possible server) and TBS (Total Bandwidth Server) [8][9][10]. EDL is based on the dynamic Slack Stealing approach while TBS is based on the dynamic computation of a virtual deadline for the aperiodic task.
Both EDL and TBS have been proved optimal in the sense that they minimize the mean response time for the soft aperiodic tasks and they maximize the acceptance ratio for the hard aperiodic tasks while guaranteeing that periodic tasks still meet their timing requirements.
3. Cleopatre features
Implementation of additional components and application software has been made easy with the following facilities: A software automatic stop which permits to safely terminate applications even in emergency situations, a communication mechanism between user space and kernel space, and aspect oriented programming.
3.1 Software automatic stop
This mechanism registers tasks descriptors, semaphores descriptors, interrupt handlers and user safe ending functions. When the primitive TCL.end() is invoked, the context switches to a safe environment in which every descriptor is destroyed, interrupt handlers are unlinked and user safe ending functions are called.
For developers, this mechanism is more reliable than manually destroying descriptors and unlinking handlers, since it avoids forgetting to execute one of these primitives that often lead to a computer crash.
“TCL.end” can be used in case of emergency stop, as the watchdog does when it detects an infinite loop.
3.2 Communication between user and kernel spaces
Applications and components are contained in modules which are loaded in the kernel space of Linux.
These modules cannot use standard C libraries and Linux drivers. While RTAI proposes unidirectional FIFOs to establish communications between user space and kernel space, bidirectional FIFOs buffers are proposed in Cleopatre with KLI module (Kernel Linux Interface).
KLI offers an interface similar to a Linux driver (open/close/read/write prefixed by Cleo_buf). Each buffer is identified by a string. LXRT (LinuX Real-Time) allows Linux processes present in user space to access to RTAI real-time primitives. LXRT is still usable with Cleopatre environment, but only with RTAI interface.
3.3 Aspect Oriented Programming
AOP (Aspect Oriented Programming) is a recent software engineering technique that facilitates maintenance of large programs [11]. AOP is able to add, modify or even remove some functionality from a program, following rules.
For example, a security aspect can be weaved to a web server application to encode every message sending, even if the sending primitives are scattered over different modules.
Technically, in our case, an aspect is a dynamic Linux module. Every component possesses a data structure that contains the addresses of every primitive of the component. To call a primitive, an application or another component that uses these structures. When this module is weaved to a component, the addresses from theses structures are modified in order to point to other primitives issued from the aspect. Most often, these primitives issued from the addresses, call themselves the primitives they replace adding new functionalities as logging or measuring time.
The Cleopatre system contains logging aspects that can be weaved to trace both tasks executions and calls to Cleopatre real-time primitives. The Aspect Oriented Programming interface is also envisaged to implement other protocols or functionalities, such as permit the access of real-time primitives to Linux processes.
4. An example
The application described in this part aims to count the number interruptions generated by the mouse. This example brings to light the main features of Cleopatre which are useful to implement a real-time application: periodic tasks, aperiodic tasks, interruptions and semaphores.
In this example, an interruption handler is linked to the mouse signal to release an aperiodic task. This aperiodic task keeps up to date a variable that contains the number of interruptions. A periodic task reads this variable every second and prints it. The access to this variable is protected by a mutual exclusion semaphore.
4.1 Source code
To compile the application, a programmer needs to include the headers of every component which is required.
/* ----- Components interfaces ----- */
#includeTCL.h> /* Task Control Layer */
#include
#include
#include
Parameters are declared with #define directive.
The stack and the heap are memories to store local variables and for dynamic memory allocation. The FPU (Floating Point/Processor Unit) is the arithmetic processor that the computer uses to perform arithmetic operations with floating point data.
/* ----- Parameters ----- */
#define TIMERTICKS 1e6 /* Timer period: 1ms */
#define irq 12 /* Mouse interrupt */
#define HEAP 0 /* Heap size */
#define STACK 2000 /* Stack size */
#define NO_FPU 1 /* 0 to use FPU */
Task, semaphore and interruption descriptors are declared as global and static variables.
/* ----- Descriptors ----- */
static DSchTaskType t_mouse; /* Tasks */
static DSchTaskType t_report;
static irqType irq_mouse; /* Interrupt */
static SemType sem_nb; /* Semaphore */
A global variable must be protected by a semaphore if it is used by several tasks (for example, "nb" is protected by "sem_nb")
/* ----- variables ----- */
static unsigned nb; /* number of mouse interruption */
static unsigned i=0; /* number of printings */
Infinite loop and explicit “wait next period” primitive aren't needed to implement periodic tasks with the Cleopatre system, the scheduler manages periodicity. As a result, the program is more concise.
/* ----- Periodic report task ----- */
void report() {
sem.P(&sem_nb); /* variable nb protected */
print("report %4i: %un",++i,nb);
sem.V(&sem_nb);
}
Infinite loop and semaphore aren't required to program aperiodic tasks in contrast with most of RTOSes.
/* ----- Aperiodic count task ----- */
void mouse() {
sem.P(&sem_nb); /* variable nb protected */
nb++;
sem.V(&sem_nb);
}
Cleopatre real-time handlers begin with the macro-command "IRQ_begin" and end with "IRQ_end". These macro-commands protect handlers from new occurrences of interruptions during execution and give hand to Linux handlers if needed.
The following handler just releases the aperiodic task.
/* ----- Interrupt Handler ----- */
void handler() {
IRQ_begin(&irq_mouse);
Dsch.wakeup(&t_mouse,TCL.time);
IRQ_end(&irq_mouse);
}
Linux runs the init_module() function for loading the application (with "insmod" command). This function creates tasks, initializes semaphores, attaches handlers to interruptions, switches the system to real-time mode, sets the watchdog timer and releases periodic tasks for their first execution.
"TCLCreateType" gathers all the parameters needed to create tasks adapted to the Linux/RTAI environment.
/* ----- Application initialization ----- */
int init_module(void) {
/* Linux/RTAI specific parameters */
TCLCreateType creat = {HEAP,STACK, NO_FPU,0};
/* Creations: Tasks, semaphore, interrupt */
Dsch.create(&t_report,report,1000,1000,creat);
Dsch.create(&t_mouse, mouse, 0, 0,creat);
sem.create(&sem_nb,1);
IRQ.create(&irq_mouse,12,handler);
/* Run periodic task */
Dsch.wakeup(&t_report,1000);
TCL.begin(TIMERTICKS,20); /* Real time */
return 0;
}
Linux runs the "cleanup_module()" function to unload the application (with the "rmmod" command). The "TCL.end()" function deletes every descriptor safely. The interrupt descriptor is used here to detach the handlers from their interruption.
/* ----- Application deletion ----- */
void cleanup_module(void) {
TCL.end();
}
The name of every primitive is composed of two words separated by “.”. The first word identifies the component which the primitive belongs to and the second one identifies the primitive. For example, "TCL.begin" is the "begin" primitive of the TCL component.
4.2 Results
The application produces two kinds of results: Text results and graphical results which can be visualized and analyzed through LTT (Linux Trace Toolkit).
The periodic task prints text reports. These results can be viewed with the “dmesg” Linux command.
This application shows that a mouse is able to generate about 300 interruptions per second. But, this result is not as important as the way to get it.
5. Conclusion
We have implemented a modular and flexible RTOS based on Linux/RTAI in the framework of a national R&D project, Cleopatre, which will end in June 2005. It is public, can be freely downloaded and is protected by the GNU/LGPL license.
Components have been designed to be independent from any RTOS and compatible with a given RTOS by adapting a software module called TCL. Cleopatre components have been tested on a mobile robotic platform, an Automated Guided Vehicle that executes orders which are transmitted through wireless communications [12].
In the future, we aim first to adapt LXRT to Cleopatre and second, to develop Cleopatre components for multiprocessor architectures and to provide components for dynamic scheduling with quality of service constraints.
Please note: A longer version of this paper, with additional diagrams and photos, was presented at the sixth annual RTL workshop, and is available as a PDF download. Chetto and Audrey Marchand also presented a paper at the RTL workshop on QoS and aperiodic scheduling.
[1] T. Garcia, A. Marchand, M. Silly-Chetto, 2003, CLEOPATRE: A R&D Project for Providing New Real-Time Functionalities to Linux/RTAI, Proceedings of the Fifth Real-Time Linux Workshop
[2] J.Y.T. Leung, M.L. Merril, 1980, A note on preemptive scheduling of periodic real-time tasks, Information processing letters, vol. 20 n3 pp. 115-118.
[3] C. Liu, J.W. Layland, 1973. Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of ACM, vol.20
[4] Kaiser C - 1981. De l'utilisation de la priorité en présence de l'exclusion mutuelle, INRIA report RR 84.
[5] R. Rajkumar, 1991, Synchronization in real-time systems: a priority inheritance approach, Boston: Kluwer Academic Publishers, ISBN: 0792392116.
[6] M.I. Chen, K.J. Lin, 1990, Dynamic Priority Ceilings: A Concurrency Control Protocols for Real-Time Systems, Real-Time Systems Journal, 2(4), pp. 325-346.
[7] A.L. Liestman, R.H. Campbell, 1986, A fault tolerant scheduling problem, IEEE Trans. on software engineering, vol.12 pp.1089-1095.
[8] H. Chetto, M. Chetto-Silly, 1989, Some results of earliest deadline scheduling algorithm, IEEE Trans. on SW Eng., 18(8), pp.736-748.
[9] J.P. Lehoczky, L. Sacha, Y. Ding, 1992. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority pre-emptive systems. Proceedings of the IEEE Real-time Systems Symposium, pp.110-123.
[10] M. Caccamo, G. Lipari, G. Buttazzo, December 1999, Sharing Resources among Periodic and Aperiodic Tasks with Dynamic Deadlines, Proceedings of the IEEE Real-Time Systems Symposium, Phoenix, Arizona. n1 pp.46-61.
[11] G. Kiczales, E. Hilsdale, J. Hugunin, M. Kersten, J. Palm, W.G. Griswold, 2001, An Overview of AspectJ, European Conference for Object-Oriented Programming.
[12] A. Marchand, C. Plot* and M. Chetto, 2002, Real-time mobile robot navigation with LINUX/RTAI, Proceedings of the IEEE International Conference on Control and Automation, Xiamen, China.
Maryline Chetto received the degree of Docteur de 3ème cycle in control engineering and the degree of Habilitée à Diriger des Recherches in Computer Science from the University of Nantes, France, in 1984 and 1993, respectively. She is a professor with the Institute of Technology of the University of Nantes, and she is conducting her research at LINA (Laboratoire d'Informatique de Nantes-Atlantique). Her main research interests include scheduling and fault-tolerance technologies for real-time applications. She has published more than 60 journal articles and conference papers in the area of real-time operating systems. She is the leader of a French national R&D project, namely Cleopatre, supported by the French government, which aims to provide free open source real-time solutions.
Thibault Garcia-Fernandez is a PhD student from the University of Science of Nantes. He has been working on the Cleopatre project for three years with Maryline Chetto. He studied operating systems in the LIP6 laboratory in Paris, where he worked on a dynamically compiled system called VVM (Virtual Virtual-Machine).
This article was originally published on LinuxDevices.com and has been donated to the open source community by QuinStreet Inc. Please visit LinuxToday.com for up-to-date news and articles about Linux and open source.