Real-Time Linux (RT- Linux)

Basic Concepts of Real-Time (RT). Hard real-time with RT-Linux

What is Real-time?

" A Real Time System is an information system whose correction does not only depend on the logical output of the algorithms but also on the moment in time when these output occurred ."

It is not sufficient that the resulting output is correct, this output must be reached within a specified time interval. Notice from this definition that a real time system is not necessarily fast, as one could be lead to believe. For example: the guidance system of a ship may appear at first to be a non real time system, because its speed is low and usually one has "enough" time (of the order of minutes) to take a control decision. Nevertheless, according to our definition it is effectively a RT system.

Notice what we have defined is a "Real Time System" and not a System in Real Time. "System in Real Time" are generally rapid systems capable of giving the impression of "reality". Typically all the simulations and interactive games need to give the user the appearance of time continuity and the most images generated per unit time the best.

Let us next consider in more detail the concept of "temporal restriction". Suppose one wants to control the velocity of an engine subject to a variable load, and that one wants to perform a PID control (Proportional- Integral-Derivative). The PID control, from our point of view, is a function that takes a number of parameters -- in this example, the velocity of the engine -- and returns the value of the control signal that has to be applied to the engine -- the voltage that must be fed to the engine. The theory behind the design of PID algorithms, which by the way is extensive, assumes that the computational time is negligible, that is, the time from reading the speed of the engine until the time when we act is very small. Under normal circumstances systems allow for a small delay time. Another characteristic of this type of control is that it must be executed periodically, in other words, the PID algorithm must be executed regularly. If the time between two consecutive calls to the PID function is too large, then the engine may reach an undesirable velocity. Summarising: The PID function can be viewed as a program that must be executed periodically (Pi); from the starting time until the time of completion must last a time interval no larger than a maximum specified by the design of the PID (Di) and according to the speed of the processor the PID code requires certain amount of time (Ci).

Pi: Period of Task i.

Di: Deadline for task i.

Ci: worse case Computational time for task i.

If the system is made up of a single task, then there is no problem of real-time: either the processor can run the process in the required time or not. In case the processor is not sufficiently fast one just replaces the CPU for a faster one.

The RT problems appear when the system is made up of a number of tasks and there is need to divide the processor (or processors) power among them. This prevents us from using a classical shared time system like Linux . Of course, it is hardly necessary to mention not to even try to write programs requiring real time under Windows.... An even better advice is not write any sort of program under that platform.

Not all the real-time systems are identical, it is not the same to control the ABS breaking system of a car and the combustible injection system in an aircraft engine or the decompression and visualisation of an mpeg file. In the first case, a small delay in the execution time may cause the loss of human life or grave material loses; in the second case, there is simple degradation of the quality of the system (the image may remain frozen and some photograms could be lost). The first type of systems are known as Hard Real-Time Systems , and the second type Soft Real-Time System. We will concentrate our discussion to hard real-time systems.

The design of a real-time system goes through several phases: First the tasks to be performed and the temporal restrictions that must be satisfied are identified, Secondly the code is written and Finally the run-time of each task is measured and a schedulability test is done to ensure that the task will not miss its deadline while the system is running. The schedulability test consists on applying a number of tests to the whole set of tasks, and if they pass the tests then it will be possible to warranty that no task will loose its deadline. If the tests are not passed it is necessary to start our design again from the beginning, picking a faster CPU or using other algorithms to implement the tasks.

In summary: The tasks are identified with three time values: Pi , Di and Ci. The objective of the system is to warranty that all tasks (in all their executions) will satisfy their deadlines. To warranty execution times the system must be predictable . Saying that a system is real-time or that the system is predictable is practically the same statement.

What is the relationship between the Operating System and Real-Time?

The semantic correction of the response is the responsibility of the programmer and the temporal correction depends on the operating system (O.S.).

The O.S. has to support and organize the execution of all the tasks, it is also the duty of the O.S. to handle the interruptions. The O.S. must offer:

• The algorithm for scheduling
• The mechanisms for inter-process communication (semaphores, messages, etc.)
• Handle interruptions.
• Activate tasks in each of its periods.

Contrary to "normal" O.S., the goal of Real-time Operating Systems is to minimize the complexity. One does not need an operating system that does many things, what is really important is that tasks are run with predictability and speed.

It is preferable an O.S. that normally takes 10 time units (t. u.) on performing a context change and in the worse case takes 12 t. u., than another O.S. that on average takes 3 t. u. But from time to time it may take up to 20 t. u.

We should not be surprised discovering that Real-Time Operating Systems are "slower" than the normal O.S. Occasionally, in order to get a predictable behaviour it may be even be necessary to disable the cache memory, with the associated performance loss. The cache memory, processors with pipeline units and the algorithms for jump prediction are clear enemies of predictability and therefore real-time operating systems.

POSIX TR Extensions.

POSIX are the initials for Portable Operating System Interface (And what is an O.S. without an X at the end?). This is a standard that intends to achieve software portability at the source code level. In other words, a program for an operating system that is POSIX compliant should compile and execute under any other POSIX, even if it is from a different manufacturer. The POSIX standard defines the interface the O.S. should offer to applications: the set of system calls. POSIX is being developed by the IEEE (Institute of Electrical and Electronic Engineering) and standarized by ANSI (American National Standards Institute) and ISO (International Standards Organisation). Obviously POSIX is based on UNIX. The majority of the O.S. (including Windows NT) tend through their various versions towards POSIX compatibility.

The work on the POSIX definition is divided in several work-groups involving computer manufactures, software companies, government officials and computer gurus. Each group takes care of designing an aspect of the operating system. For example, the group named POSIX.4 takes care of the issues concerning real time.

The extension POSIX.4 -- renamed as 1003.1b since 1993 -- allow the usage of an O.S. in real-time situations. Clearly, the great majority of these extensions are related to time management and process priorities, there are also system calls to facilitate the inter-process communication.

The POSIX extensions are designed to enhance the control on the management of resources of the O.S.

Linux 2.0 has many of the POSIX extensions system calls for real time implemented... but this aspect of Linux is something we will discuss in a future article. Version 2.2, most likely will be 100% compatible POSIX 1003.1b.

Real Time Linux

RT-Linux was developed in the Department of Computer Science of the Institute for Mining and Technology of New Mexico by Victor Yodaiken and Michael Barabanov. It is part of the work submitted by Michael to complete his Master in Computer Science. The last version available is 0.6. For the moment it is only available for INTEL architecture.

RT-Linux solves the problem in a radically different way. Instead of modifying the kernel of Linux to make it predictable, what it does is to build directly over the processor (i386) a small kernel -- independent of the Linux kernel -- with a scheduler. The Linux kernel runs on top of this kernel sharing the processor with other RT-tasks. Linux then shares the CPU with other tasks, more precisely Linux is the background task, and runs only when no other RT-tasks are running.

I imagine many readers will be confused by now, perhaps many thought that the O.S. is all-mighty and it is not possible to play with it.

It will be even more surprising to know the fact that it is possible to install and remove the time scheduler dynamically, because it is compiled as a module.

The Linux kernel code (like any other O.S.) usually disables the interrupts as a means for synchronization or to implement critical sections. If while Linux disables the interrupts there is a clock interrupt, this remains blocked and consequently there is a loss of temporal precision. RT-Linux implements an elegant solution: all calls to cli, sti, and iret (assembler calls that modify the state of the interrupts) are repaced by S_CLI, S_STI and S_IRET that emulate them, this way Linux never can disable the interrupts.

The default scheduler that comes with RT-Linux is a preemptive, fixed priority scheduler and considers the Linux task as the task with the lowest priority. If the real-time tasks consume all the processor time, then the Linux task will not received time from the CPU and it may give the impression that the system is halted.

With RT-Linux we not only have a real time system but also a classic O.S. We can surf the web at the same time we are sampling and controlling a physical system.

Installation of RT-Linux

The files for the distribution can be found at: http://luz.cs.nt.edu/~rtlinux.

To "transform" a Linux system to RT-Linux we have to apply to the source code of the kernel a patch that comes with the RT-Linux and then recompile the kernel. Here is the recipe to do it. I will assume that the file rtlinux-0.6-2.0.33.tgz is in the directory /usr/src and it has been extracted in /usr/src/rtlinux-0.6. I also assume that all the options for the kernel are already configured (make config), then

# cd /usr/src/linux
# patch       -p1 <../rtlinux-0.6-2.0.33/kernel_path
# make dep; make clean; make zlilo; make modules; make modules_install
# reboot

The new kernel appear to be identical to a normal kernel, however it is already prepared to convert into a real time system. Inside the directory /usr/src/rtlinux-0.6-2.0.33/testing there are various demo programs.

Aside from the examples that come with the distribution (inside the directory testing), you can download another example prepared by Oleg Subbotin that allows us to create an execution chronogram of the tasks. One file of this demo is a scheduler with some modifications that permit to perform not only task scheduling, but also sending information concerning the decisions is taking. This information is collected and stored in a file that can later be displayed graphically. As a result we can see in what order the various tasks have been executed, and how the higher priority tasks preempts tasks with lower priority. The Linux task is not represented.

Each task is represented by a horizontal axis. The rectangles represent times when each task is using the processor (in a given instance only one task can be executed because we are in a mono-processor system). In this example, the deadline for each task is equal to their period, the period of each task is marked by a time interval (represented by: ) during which the task must be executed. The tasks on the upper part have higer priority and are capable of preempting other tasks from the processor, as happens for example in the instant 600.

The Future of RT-Linux

There is already a multiprocessor RT-Linux version. The services offered by RT-Linux are intentionally minimal, it is not necessary to include functionality not strictly needed in order to keep the system as predictable as possible. Nevertheless, the are several extensions already available that allow to work with semaphores and to control RT-tasks from the Linux processes through /proc/sys.

Few weeks ago began the creation of a manual-tutorial for RT-Linux.

Conclusions

Before the appearance of RT-Linux most engineers who wanted to use real-time system were forced to either use MS-DOS and build all the necessary drivers, or buy a real-time O.S. (at very prohibitive prices). Now developers have a full Operating System to develop real-time applications on the same system were they are going to run. In fact, we can even have several real-time applications running at the same time we are surfing the web without problems.

Our next article in this series will examine several examples of real-time applications and how to write our own real-time applications.

Translated by Miguel Angel Sepulveda