Introducing Real-Time Linux
The basic idea is to make Linux run under the control of a real-time kernel (See Figure 2). When there is real-time work to be done, the RT operating system runs one of its tasks. When there is no real-time work to be done, the real-time kernel schedules Linux to run. So Linux is the lowest priority task of the RT-kernel.
The problem with Linux disabling interrupts is solved by simulating the Linux interrupt-related routines in the real-time kernel. For example, whenever the Linux kernel invokes the cli() - routine that is supposed to disable interrupts, a software interrupt flag is reset instead. All interrupts get caught by the RT-kernel and passed to the Linux kernel according to the state of this flag and the interrupt mask. Therefore, the interrupts are always available for the RT-kernel, while still allowing Linux to “disable” them. In the example above, the Linux kernel routine would call cli() to clear the soft interrupt flag. If an interrupt occurred, the real-time executive would catch it and decide what to do. If the interrupt caused a real-time task to be run, the executive would save the state of Linux and start the real-time task immediately. If the interrupt just needed to be passed along to Linux, the real-time executive would set a flag showing a pending interrupt, then resume Linux execution without running the Linux interrupt handler. When Linux re-enables interrupts, the real-time executive will process all pending interrupts and cause the corresponding Linux handlers to execute.
The real-time kernel is itself non-preemptable, but since its routines are very small and fast, this does not cause big delays. Testing on a Pentium 120 shows the maximum scheduling delay to be less than 20ms.
Real-time tasks run at the kernel privilege level in order to provide direct access to the computer hardware. They have fixed allocations of memory for code and data—otherwise, we would have to allow for unpredictable delays when a task requests new memory or pages in a code page. Real-time tasks cannot use Linux system calls or directly call routines or access ordinary data structures in the Linux kernel, as this would introduce the possibility of inconsistencies. In our example above, the kernel routine changing the queue would invoke cli, but this would not prevent a real-time task from starting. So we cannot allow the real-time task to directly access the queue. We do, however, need a way for real-time tasks to exchange data with the kernel and with user tasks. In a data collection application, for example, we might need to send the data collected by an RT-task over the network, or write it locally to a file, while displaying it on the screen.
Real-time fifos are used to pass information between real-time processes and ordinary Linux processes. RT-fifos, like real-time tasks, are never paged out. This eliminates the problem of unpredictable delays due to paging. And real-time fifos are designed to never block the real-time task.
Finally, the question—how the real-time kernel keeps track of the real-time—arises. When implementing schedulers for real-time systems, there is usually a tradeoff between the rate of clock interrupts and task release jitter. Typically, sleeping tasks are resumed during the execution of the periodic clock interrupt handler. A comparatively low clock interrupt rate does not impose much overhead, but at the same time causes tasks to be resumed either prematurely or too late. In real-time Linux, this problem is obviated by using a high-granularity, one-shot timer in addition to standard periodic clock interrupts. Tasks are resumed in the timer interrupt handler precisely when needed.
The current version of RT-Linux is available by anonymous ftp from luz.cs.nmt.edu. Information on RT-Linux can be found on the web at luz.cs.nmt.edu/~rtlinux. The system is in active development, so it's not at a production level of stability, but it's pretty reliable. We are developing some applications as well, and these will also be on the web site. We are asking people who use the system to make their applications available on the web site as well.
Victor Yodaiken is a professor of computer science at New Mexico Tech. His research is on operating systems, real-time, and automata theory.