For many small applications, the simplest of all real time processing architectures is the most obvious choice. This is the 'superloop', familiar to many microcontroller users. If written in C, this corresponds to a main() loop that cycles through a series of statements and function calls, collecting data from inputs and setting outputs before returning to the beginning ready to start again.
This may not sound like a real time system but, as long as the performance of the code is predictable and everything gets done within the time needed to maintain control, it is real time enough. Eventually, the superloop model breaks down – so many features need to be added that timing is no longer predictable and even simple changes to code can cause important functions to miss deadlines.
It's about this time that most people find they are ready to shift to a real time operating system (RTOS), whether they pull one off the shelf or decide to implement it themselves.
An rtos isn't inherently real time
There is nothing inherently 'real time' about an RTOS. The distinction between an RTOS and an operating system that does not have its features lies simply in the choice of scheduling modes, although there are subtleties that make some better at delivering determinism than others.
An RTOS supports tasks with different priorities. Other types are mainly aimed at timesharing, where the tasks each get a turn to run on a round robin basis. Although these operating systems have a concept of priority, this tends to mean they get a longer time slot or are returned to the ready queue with greater frequency than those considered low priority.
In an RTOS, a higher priority task that is considered ready to run by the scheduler will always be picked ahead of one with a lower priority; a round robin scheduler can choose to suspend a task once it has run out of time. Desktop operating systems rarely implement pure priority based scheduling because of the potential for deadlock: a runaway thread or process may never yield the processor and block all others.
Anyone implementing a system using an RTOS takes that risk in exchange for the assurance that an important task will never be blocked from running if it has not finished its work. If everything is working correctly, it will meet its deadlines, providing the real time behaviour that system designers expect. In practice, there are many subtleties to the design of an RTOS that can prevent a system from meeting its deadlines, even when priorities are all set correctly, and which make analysis of the timing behaviour of the system difficult to achieve, except through extensive testing.
Interactions between tasks and hardware resources and between interrupts and the RTOS have been known to cause intriguing problems. The bug in the Mars Pathfinder is an old example, but illustrates some of the subtleties involved. A few days after it bounced onto the surface of Mars, the craft started to reset itself periodically and unexpectedly. A watchdog timer would run out, indicating the system had locked up, and triggered a reset each time.
Engineers at NASA's Jet Propulsion Laboratory realised the source of the lock up was the lander's information bus – a central memory block used by the lander's different components to pass data to each other. Access to this bus was protected using mutual exclusion semaphores (mutexes) – a task could only enter the block of code that could read or write the shared memory if it first acquired ownership of the semaphore (NE, 8 February 2011).
Tasks with a variety of priority levels could access the information bus and it was this interaction that led to the resets. In a system without interrupts, each task could acquire, read and write and then release the mutex in one contiguous sequence of events until it relinquished the processor and went back to sleep. In effect, this is not very different from a superloop program. However, in a pre emptive RTOS, interrupts can stop a task from executing.
Not only that, the interrupt may make a higher priority ready to run. Usually, the scheduler in the RTOS will reevaluate which tasks should run next when the interrupt handler has finished running – the handler may well have provided the input that a high priority task needs to continue its work so it makes sense to schedule it immediately.
On Pathfinder, it was possible for a low priority task that collected meteorological data to acquire the mutex to write to the bus but, before it could release the semaphore, be interrupted by the high priority task information-bus manager thread, which would then block on the mutex held by the meteorological-data thread. This would not matter ordinarily, as the low priority task could finish its work.
However, a second interrupt might cause another task with higher priority to be scheduled. In the case of Pathfinder, this was a medium priority task that, by preventing the meteorological data thread from running, would effectively block a task with higher priority. The result is priority inversion: a high priority task is blocked by one with a lower priority. The watchdog timer monitored the information bus and, if the bus manager did not run within a certain period of time, would force a reset on the assumption that something had gone wrong.
The cure was to activate a priority inheritance mode for the mutex. This mode provides any thread that owns a mutex with the same priority as a more important task that is blocked on it until the semaphore is released. Fortunately, it was NASA policy to leave a debugger mode in any spacecraft to allow 'on the fly' changes to be made: even to a system that is millions of miles away.
Priority inheritance
Many RTOS implementations support priority inheritance (see fig 2) or a close relative, the priority ceiling protocol. However, it is not a cure all and study has shown it can, in itself, cause problems if used indiscriminately.
You are, in effect, designing in a certain amount of priority inversion (see fig 3) deliberately and so need to be sure that a normally low priority task will not simply hog a resource and keep running indefinitely in a state where it cannot easily be pre empted. There also also subtleties in implementation.
If an application is migrated from a single core to a dual core processor that uses the priority ceiling protocol, it cannot guarantee mutual exclusion. So a distributed priority ceiling protocol has to be used instead. A way around the priority inversion problem is to force all accesses to a shared resource through a dedicated task which arbitrates between the different requests.
This task needs to run at a priority level higher than the most important thread that will request its services to ensure that it can complete its work. As a result, a form of priority inversion can still take place as the resource manager may pre empt a high priority task when it takes on work on behalf of a low priority thread. However, the delay it incurs should be more predictable as all requests go through the same code.
A shift to an interrupt driven asynchronous RTOS can reveal hidden dependencies on timing. In the mid 1990s, the flight software for a fighter aircraft was migrated from a cyclic executive – with known timing – to an interrupt driven system. After the port, the display showing tracked objects blurred randomly. The transfer of target data from the sensor to the display used to take four frames.
Under pre emption, it could take between four and eight frames, so the target appeared to oscillate when this period stretched out. If the incoming samples are not time stamped, the time jitter of data used in a control loop can cause instabilities or excess noise. Techniques have appeared that attempt to help engineers work out whether their proposed design has scheduling problems.
The most famous is rate monotonic analysis, first proposed by Liu and Layland in 1973. Under this system, a task's priority depends on how often it has to run. The task with the shortest period has highest priority and the sequences runs down monotonically to the task with the longest period, giving the approach the name 'rate monotonic'. The approach has merit, but suffers from some serious limitations.
A key shortcoming is that it assumes tasks do not interact; it is often interactions between tasks that cause the problems in scheduling in the first place. And the tasks have to be periodic, which may not be possible to achieve without forcing tasks to be scheduled, even when they have nothing to do. To guarantee that all tasks can run, the algorithm is quite conservative: the processor cannot be more than 70% loaded for a system shared by more than a few tasks.
Given the problems of analysing schedulability in asynchronous, interrupt driven real time systems, it should come as little surprise that many systems that have to guarantee dependable behaviour resort to some form of strict time sharing. In this scenario, important tasks may have nothing to do, but they are guaranteed a number of cycles within a period of time to run, just in case they do need to respond to a problem.
ARINC 653 avionics systems have used this approach for years and automotive systems are adopting the Flexray architecture, which is based on time triggered operating systems. ARINC 653 uses an application executive (APEX) that partitions a system in both space and time, isolating software components from each other so they cannot bring down one another in the event of application failure.
Each partition in an ARINC 653 system has its own dedicated, protected memory space and the APEX provides a guaranteed time slice to each partition (see fig 1). Each ARINC 653 partition can run a multitasking system, but vital functions will generally have their own dedicated partitions. Multicore and multiprocessor systems provide a further degree of freedom. If you have processing capacity to spare, why not dedicate processors to important tasks to ensure they can always be scheduled to run when needed?
Even with such rigidly enforced partitions, timing problems can still arise courtesy of interactions with the hardware. One problem identified by GE Aviation and Wind River Systems lay in the use of direct memory access (DMA). If a partition towards the end of its time slice decided to initiate a long DMA transfer, the partition that runs immediately afterwards will stall because the DMA hardware has exclusive access to the memory bus – effectively shortening the new partition's time slice enough to cause it to miss its own deadline.
The recommendation in this case was to transfer the responsibility for setting up DMA transfers to a system level task, which would take into account the amount of time a partition had remaining before it would be forced to relinquish the processor. Similarly, interrupt handling can upset the operation of an otherwise strictly time sliced system. A number of systems prevent all but the system timer, which is used to help manage scheduling, from being able to assert an interrupt.
Others may record the interrupt and then allow the affected system to then poll for the associated data when it next runs. Although ARINC 653 and Flexray systems are intended for specialised applications and will not be encountered by many engineers, the rise of virtualisation will make these side effects apparent to a wider range of system designers. Whether the hypervisor time slices virtual machines, runs them with strict priority policies or a mixture of both, there is clear potential for data transfers and interrupts associated with low priority subsystems to interfere with the timing of critical applications.
Again, multicore architectures can provide a way out of the dilemma, so long as shared subsystems are managed carefully – a vital task running alone on a processor core can still be blocked by long I/O transfers made by a less important task if they have to share the same I/O bus or port or make accesses to the same system management registers.
One option for the real time systems designer is to have a system that is more explicit about what is required. Priority is only a proxy for what is actually required: the ability to meet a hard deadline. This is where techniques such as deadline monotonic analysis come in. It is not implemented widely and still has some shortcomings in that it cannot deal directly with resource conflicts that trip up other systems.
But the system has the advantage of allowing the designer to set deadlines explicitly and then allowing the RTOS to set priorities that enable each task to meet its deadline using an algorithm similar to that used by rate monotonic analysis. Variations on deadline monotonic analysis have appeared that attempt to take account of changes in behaviour caused by resource sharing. In this approach, a kernel tracks the amount of time under which tasks run under priority inheritance conditions.
This is compared with a maximum blocking time and, if it is exceeded, the RTOS sends a message to the task through the reservation API to make it easier to diagnose problems. Other techniques concentrate on a mixture of static analysis and instrumented tests to try to identify worst case behaviour and provide probabilities on whether the system can meet its deadlines under different conditions. The instrumented tests in the target system are needed because of the interactions between tasks.
A task that runs slower, possibly because of thrashing in cache memory, will often have a knock on effect on another task – possibly because they may contend over the same cache lines in worst case conditions. These interactions are tough to pick up with a static analysis or unit test. Research continues into schedulability analysis and ways to determine how well an arbitrary system design will hit its deadlines. But until those tools appear, engineers will have to be attuned to all the subtle things that can go wrong, go wrong, go wrong …
