| Patent #5,469,571 |
 “Operating System Architecture using Multiple Priority Light Weight kernel Task-based Interrupt Handling.” Granted November 21, 1995 |
One of the most difficult challenges faced by designers of embedded systems is to meet real-time performance requirements. The interaction of multiple input-output (I/O) devices and system processes gives rise to complexities in timing and can degrade system performance.
Lynx™ Software Technologies developed a new way of managing kernel threads and priority processing, and was awarded a patent for its technology, which is part of the LynxOS® real-time operating system. The invention takes a unique approach to handling hardware events in a real-time environment, and allows complex multi-process and multi-threaded applications to respond in a predictable and timely manner.
Processes and Priorities
In multi-tasking operating systems, such as UNIX®, each process or program receives a priority which helps determine when it will run. In general, higher priority processes run before lower ones. Once a process is running, it has the full attention of the CPU. The OS changes which process is executing by one of three means:
| Yielding | The process itself voluntarily gives up the CPU |
| Preemption | The system intervenes to start another process of higher priority |
| Blocking | The process waits on an event, usually I/O, and so gives up the CPU |
Yielding occurs when a process is “idle”; with nothing in particular to do, it voluntarily yields execution to the system. This is a primary mechanism in cooperative tasking systems, such as MacOS or Windows 3.1.
Preemptive scheduling allows the OS to determine which process will run next. A preemptive architecture provides for greater concurrency, i.e., more process can appear to run simultaneously. Most versions of UNIX and to a large extent Windows95 are preemptive systems.
Blocking is similar to yielding in that it is voluntary. It is common to systems where the OS governs I/O. Data is not always ready when a process requests it, so rather than looping and wasting CPU time, processes yield the CPU until their data becomes ready.
Hardware versus Software Priorities
Hardware-based events, specifically interrupts, can have a priority scheme of their own. Data coming from a mouse, for example, generates an interrupt of lower priority than one used to service a hard disk drive; the storing of hard drive data supersedes that of mouse data, which can be preempted.
When the CPU is “handling” an interrupt of a given priority, interrupt requests of a lower priority are ignored or deferred and requests of a higher priority are yielded to automatically—the disk drive interface program ignores the mouse interrupt and the mouse code yields to the disk drive’s interrupt request.
Interrupt prioritization differs sharply from its software equivalent in that it is built into the CPU hardware. Moreover, short of disabling the interrupt scheme, hardware interrupt service execution always supersedes software priority-based process execution.
This scheme generally makes good sense; it allows that data associated with an interrupt not be lost just because another program is executing.
Priority Inversion
The two priority schemes can interact in unexpected ways, however. Imagine a design in which high-priority hardware events supply data to high-priority processes, and lower priority hardware events to lower priority processes:
This common, seemingly sensible arrangement can lead to problems when even the highest priority process in the system finds itself constantly interrupted by hardware events. The lower priority process associated with lower-priority I/O may not be running but the low priority interrupt can steal cycles and significantly degrade an application’s ability to meet hard real-time deadlines.
LynxOS’ Unique Patented Approach
LynxOS is a POSIX®-conformant operating system that implements the UNIX concept of processes, but actually schedules on the basis of POSIX threads of execution which can exist within processes. LynxOS uses this difference to address priority inversion and other scheduling challenges with two solutions unique in the real-time world:
- Kernel threads (versus traditional handling):
Most operating systems make a strong distinction between internal operation and the functioning of user processes. The system “kernel” or core is a large, monolithic program that seldom offers predictable real-time response. Moreover, the OS kernel does not participate in the overall priority scheme (although it governs it). Interrupts are handled by extensions to the kernel called “drivers” which also function outside normal prioritization. Handler code within the drivers processes interrupts and exits quickly so as not to impact system performance. User processes communicate with the kernel and perform most I/O through entry points or calls into the drivers and so I/O ends up being processed outside the user process context.
The patented LynxOS approach departs from this model by allowing separate POSIX-style threads of execution within the kernel that drivers can use for interrupt handling. LynxOS treats these threads like normal user threads, with software priorities, not interrupt priorities. The driver’s interrupt handler, then, does a minimum of work and signals the kernel thread that interrupt-related data is available.
Such a strategy permits real-time-critical user tasks to execute even during interrupt processing.
- Threaded Priority Tracking:
While kernel threads give the real-time system designer more options for finer control over real-time event processing, they do not alone resolve priority inversion—a kernel thread servicing a low-priority interrupt could still rob performance from an important process (user thread). The key to really making kernel threads participate in the overall system priority scheme is priority tracking.
Kernel threads begin their existence with a very low priority (usually 0) as created by a driver. When a user thread opens the device, the kernel thread promotes its own priority and “inherits” the priority of the user thread opening the device:
If another user thread of higher priority opens the device, the kernel thread bumps its priority up to match the other thread; when the I/O is complete the kernel thread returns to the next pending thread’s priority level, or to its starting level.
As the kernel thread goes about servicing any interrupts associated with the device, it does so in step with the user thread consuming (or producing) the data. The interrupt in question, then, can be of high or low priority as needed by the hardware without serious impact to the system software priority scheme. So, by using priority tracking the designer can selectively “flatten” or restructure a processor’s interrupt handling architecture so as to serve the application’s needs. The patented technology is proprietary to Lynx Software Technologies, and has been incorporated into Lynx Software Technologies’ real-time operating systems which complies to UNIX and POSIX standards.
Conclusion
The combination in LynxOS of kernel threads and priority tracking gives developers much finer control over processes scheduling than in a traditional RTOS, such that processes can execute at their assigned priorities regardless of other activities in the system. Kernel threads and priority tracking harmonize the distinct functioning of hardware interrupts and software processes, reducing unforeseen interactions and unpredictable behaviors, and so easing the difficult task of real-time application development.