Embedded Control Systems Design/Real Time Operating systems

The Wikibook of

Embedded Control Systems Design

RTOS

RTOS are Operating Systems (OS) which act in Real Time (RT). This means that RTOS have other purposes than general OS or embedded operating systems (EOS). Where the general OS have the goal to maximize the average throughput of tasks (data?), in RTOS the keyword is determinism. Real-time tasks have to be completed before a certain deterministic deadline. This requires that responses to stimulus must always execute within a constant amount of time. Violation of the specified timing constraints is (normally) considered catastrophic. Non real-time systems are considered correct if certain inputs map to certain outputs: the system (code and hardware) must always do the proper thing given some current state and input. Real-time systems must achieve the same logical correctness, but must achieve this logical correctness using constant time algorithms. Because of this additional requirement on executional behavior, the implementations of RTOS differ significantly from other OS, although the general principles are the same.

An example of a different algorithm to achieve the same logical behavior but within constant time: Imagine the system must respond to 25 different inputs, and for each of these inputs, a specific output is generated. A perfectly acceptable non-real-time implementation is to have a loop that iterates through the list of possible inputs to determine the proper output. However, such a loop varies in execution time: the input that happens to be first in the list can be identified much faster than the input that happens to be 25th in the list. A constant time approach is to use a hash, such that the input itself can be immediately mapped to the proper output. So a real-time solution would use a hash instead of a loop to select between many inputs and outputs. In fact, the existence of loops with non-constant executions certainly indicates that the algorithm is not a real-time algorithm.

Another clear distinction between real-time and non-real-time is how one handles contentions for shared resources. In real-time systems, data contention is avoided to the greatest extent possible, and where contention does occur, exactly zero or one semaphores can be used, and generally zero semaphores, instead using lock-free protocols between those sharing the contended resource. To ensure that code changes cannot accidentally influence this hard and absolute limit, procedure calls are not allowed when semaphores are being held. In non-real-time systems, any number of nested semaphores can be used, as long as they are released in the order they are taken.

Some people make a distinction between soft and hard RTOS. In one way, such systems are the same: in both, it is necessary to demonstrate that there is always idle time before any deadline, hence that real-time deadlines will be met. However, the approach is fundamentally different: Soft real-time means the developers hope their computing platform is simply fast enough to keep up; hard real-time means the system is architected, designed, and implemented using only real-time algorithms.

RTOS have 4 main responsibilities:

task management and scheduling;
(deferred) interrupt servicing;
inter-process communication and synchronization; and
memory management.

Design of RTOS

Because determinism is often compromised in “high-level” programming language and OS constructs, real-time designers are confronted more directly than “normal” application developers with concepts, timing, memory and efficiency at the level of the OS.

Task management and scheduling

The responsibility of task management includes the scheduling of the multiple tasks. Because scheduling is pure overhead, the RTOS implement scheduling algorithms which are not too complex.

The simpler the algorithm, the faster, smaller (less memory) and more predictable the task will be executed.

The simplest approach to the scheduling problem is to assign (static/dynamic) priorities to all tasks. It's quite obvious as an example that the creation and deletion of tasks shouldn't be done during RT-tasks. Unfortunately, priority-based scheduling has a variety of obvious problems ("starvation", "deadlock") and more subtle problems ("livelock", priority inversion).

Using priorities implies using pre-emption: a lower priority task which is running should be interrupted in order to run a higher priority task. Priority-based scheduling, however, is difficult for the application programmers: they must try to map the often complex synchronization interdependencies between the different threads in their application onto the linear scale offered by priorities. The problem with this kind of scheduling is that it is an indirect way to specify how to cope with timing and synchronization constraints: these are translated in priorities.

One often-observed phenomenon in RT applications that grow over time, is that the programmers tend to raise the priorities of some threads, every time they notice that the introduction of new functionality disturbs the synchronization of the existing threads.

It's actually the system designer who has to decide which tasks get which priorities, because many programmers have the urge to prioritize their tasks. In this case it's important to see there's only 1 task which should obtain the highest priority. One could say that that task is the “hardest” task in the context of hard/soft RT.

Properly balancing latency, throughput, and fairness in schedulers is an open problem.^[1]

Timers

The timing constraints of RT-tasks are often specified in less than micro-seconds instead of milliseconds. Hence, the data structure in which the time is kept should be adapted to this higher rate, in order to avoid overflow. A 32 bit counter would rapidly overflow if the OS counts in nanoseconds (e.g. (2^32)/(10^9) = 4 seconds till overflow). In this case it would be more appropriate to use a 64 bit counter. These timers are called high resolution timers.

problem with atomic operation for a 64 bit counter?

Watchdog timers

The ISR contains one or more watchdog timers.^{[citation needed]} Such a timer triggers a restoring task if the current running task is taking too much time in which nothing really happened. Through this way possible faults (such as a hang) can be covered for. The watchdog could then possibly provide debugging information, if it is designed for it.

Watchdog timers may also trigger control systems to move into a safety state, such as turning off motors, high-voltage electrical outputs, and other potentially dangerous subsystems until the fault is cleared.

See also: hardware watchdog timers

Interrupt servicing

Most modern OS are interrupt-driven. This means that if there are no processes waiting to be executed, no I/O-devices requesting a service and no users waiting for an answer, the OS waits till something happens.

Events are almost always signaled by an interrupt or a trap. A trap is an interrupt that is generated by the software, either after an error or after a specific request of a user program to execute a system service. For each type of interrupt there are separate code segments available in the OS. These segments determine how the OS reacts on a particular event. Peripheral hardware are special in that they can request the attention of the OS asynchronously, e.g. at the time they want to use the OS services, the OS has to make sure it is ready to service the requests. These requests are signaled by an interrupt. It's rather obvious that during a real-time task those other tasks (reading/writing on disks, accessing USB, etc.) should be postponed.

The OS is, in principle, not involved in the execution of the code triggered by the hardware interrupt: this is taken care by the CPU without software interference. The OS does have influence on

connecting a memory address to every interrupt line and
what has to be done immediately after the interrupt has been serviced.

What does this mean for a RTOS? Interrupts have to be processed by a so-called ISR (Interrupt Service Routine). The faster this ISR can do his job, the better the real-time performance of the RTOS, because other tasks are delayed less. Let’s take a look at the hardware and software side of an interrupt-driven system (which many RTOS and EOS are) and their typical components.

Interrupt Hardware

Interrupt vector vs non-vectored Interrupt proc.

An Interrupt vector is used in systems with more than one hardware interrupt line and all these interrupt lines are assembled in an interrupt vector. The interrupt vector is an array of pointers to the interrupt service routines. In non-vectored systems when an interrupt occurs, control is transferred to a single routine that decides what to do with the interrupt. For RT-systems an interrupt vector is feasible because it lowers the processing time of an interrupt.

Edge-triggered and level-triggered interrupts

Peripheral devices can transmit their interrupt signals in two different ways. Edge-triggered interrupts hold risks for a hardware or software loss of the interrupt and are generally not an efficient solution. For RTOS and EOS where determinism is an important factor level-triggered interrupts are favourable.

Interrupt controller

This is a piece of hardware that shields the OS from the electronic details of the interrupt lines. Some are able to queue interrupts so that none get lost (determinism!) and some allow assigning priorities to different interrupts. Examples are a PIC or an APIC. Working with an APIC is beneficial in a RTOS and EOS.

Interrupt Software

Interrupt Service Routine
This software routine is called when an interrupt occurs on the interrupt line for which the ISR has been registered in the interrupt vector. The OS does not intervene in the launching of an ISR, everything is done by the CPU. The context of the current task is saved on the stack of that task, so each task must get enough stack space to cope with ISR overhead. An ISR should be as short as possible, because it runs with interrupts disabled, which prevents other interrupts from being served and tasks from proceeding (RTOS!). Further processing is a goal of the DSR. Getting data from the ISR to the DSR should be done in a non-blocking way.

Trap handler/service request
The software interrupts are called by the processor itself, such as in the case of a register overflow, errors,... They are similar to hardware interrupts, but they run with hardware interrupts enabled.

Interrupt latency
This is the time between the arrival of the hardware interrupt and the execution of the corresponding ISR. It is a statistical quantity and it is important to try and get this number as low as possible and as deterministic as possible in an RTOS. Modern processors with many levels cache and pipelines are prone to indeterminism

Interrupt priorities
Adds complexity and problems/opportunities known in task scheduling to the interrupt handling. Not wanted in a RTOS/EOS.

Interrupt nesting
Adds complexity to the code. In a deterministic environment is this not wanted.

Interrupt sharing
Many systems allow different peripheral devices to be linked to the same hardware interrupt. The ISR servicing this interrupt must then be able to find out which device generated the interrupt. RTOS do not support this feature; they only allow one single ISR per IRQ, in order to be as deterministic as possible. So a RT system designer should be careful when putting interface cards in your computer because all the ones for which you want to install real-time drivers must be connected to different interrupt lines !

Interprocess communication IPC and synchronisation

Because there are tasks that have to communicate with each other, the need exists for synchronization of different tasks, as well as for data exchange between them. The RTOS should provide easy and safe IPC primitives which can be used for programmers to build their software systems. These primitives can have different effects on task scheduling (blocking, non-blocking, conditional blocking, blocking with time out), can use different degrees of coupling (named connection, broadcast, blackboard, object request broker) and buffering.
The origin of most problems with resource sharing (or allocation) in multi-tasking and multi-processor systems is the fact that operations on resources can usually not be performed atomically, i.e., as if they were executed as one single, non-interruptible instruction that takes zero time. Indeed, a task that interfaces with a resource can at any instant be pre-empted, and hence, when it gets re-scheduled again, it cannot just take for granted that the data it uses now is in the same state before the pre-emption. Some parts of the code are called 'critical sections' because it is critical to the validity of the code that the access to the data used for a certain statement be executed atomically: un-interruptible by anything else. (Most) machine code instructions of a given processor execute atomically, but instructions in higher-level programming languages are usually translated into a sequence of many machine code instructions.
The main problem is called a “race condition”: two or more tasks compete against each other to get access to the same shared resources. Examples of these race conditions are the following: deadlock, livelock, starvation. Algorithms are available that avoid these race conditions, some more complex than others.
There are many types of synchronization: barrier , semaphore, mutex, spinlock, read/write lock (and lock-free for data exchange).
When a task reaches its so-called critical section, it requests a lock. Now it can get the lock if it isn't taken by another task and enters the critical section, or it has to wait (“blocked”, “sleeps”) till the other task releases the lock at the end of its critical section. A blocked task cannot be scheduled for execution, so locks are to be used with care in RT applications! The application programmer should be sure about the maximum amount of time that a task can be delayed because of locks held by other tasks; and this maximum should be less than the specified timing constraints of the system. The lock concept can easily lead to unpredictable latencies in the scheduling of a task. It doesn't protect the data directly, but synchronizes the code that accesses the data. As with scheduling priorities, locks give disciplined programmers a means to reach deterministic performance measures. But discipline is not sufficient to guarantee consistency in large-scale systems.
The problem with using locks is that they make an application vulnerable for the priority inversion problem. This should be prevented in the design phase. Another problem occurs when the CPU on which the task holding the lock is running, suddenly fails, or when that task enters a trap and/or exception, because then the lock is not released, or, at best its release is delayed.

Some remarks about the types of synchronization

Semaphore - spinlock
A semaphore is a lock for which the normal behaviour of the locking task is to go to sleep. Hence, this involves the overhead of context switching, so don't use semaphores for critical sections that should take only a very short time; in these cases spinlocks are a more appropriate choice.
Semaphore - mutex
Many programmers also tend to think that a semaphore is necessarily a more primitive RTOS function than a mutex. This is not necessarily so, because one can implement a counting semaphore with a mutex and a condition variable.
Spinlock
Spinlocks work if the programmer is disciplined enough to use them with care, that is for guaranteed very short critical sections. In principle, the latency induced by a spinlock is NOT deterministic (not RT). But they offer a good solution in the case that the scheduling and context switching times generated by the use of locks, are larger than the time required to execute the critical section the spinlock is guarding.

IPC and data exchange

Mechanisms of all data IPC exchange are quite similar; the OS has some memory space reserved for the data that has to be exchanged and uses some synchronisation IPC primitives for reading or writing to that memory space. The main difference between different forms of data exchange lies in their policy. Two or more tasks often have some form of shared memory. Possible problems are the available space in the RAM and some control over the freshness of the shared data What do you mean with the freshness of the shared data?. Shared memory has the properties of a block device ; programs can access arbitrary blocks on the device in any sequence. Character devices can only access data in a linear sequence. FIFO is such a device. In a RT-system no lock is needed on the real-time side as no user program can interrupt the real-time side. Another form of IPC data exchange is using messages and mailboxes. Again for a real-time system there are some things to pay attention to. An IPC approach which uses dynamic memory allocation is not feasible for a RT-system.Circular buffers is another possibility of IPC. There are some possible problems with data loss though, so an RT-system uses some specific options. These are: locking in memory and buffer half full. A better solution is using a swinging buffer. This is an advanced circular buffer and a deadlock-free lock. A swinging buffer is non-blocking and loss-prone.

Memory management

The job of the OS is memory allocation and memory mapping and to take action when a task uses memory that is not allocated (memory protection). Some of the points of attention in memory management in a RT-system are:

Fast and deterministic memory management
The easiest is no memory management at all. Some RTOS/EOS offer some basic memory management; memory allocation and deletion through system calls.
Page locking
The MMU (memory management unit) must lock pages of real-time memory tasks in the physical RAM in order to avoid the paging overhead of swapping pages from the mechanical disk drive to the RAM.
Dynamic allocation
A task’s memory may change during the lifetime of a task, so that it asks the OS for more memory. In order to do this in a deterministic way the memory pages need a pool of free pages locked in the memory. Dynamic allocation should be used very carefully in a Real-Time task. This also implies that IPC with dynamic allocation needs are to be avoided.
Memory mapping
Mapping is a configuration activity and should not be done in real-time.
Memory sharing
This is an efficient way for two tasks to communicate. The OS is responsible for 1) the (de)allocation of shared memory and 2) synchronizing the access to that memory by different tasks. There is nothing particularly real time about using shared memory, allocating it is though. The shared-memory pool is a block of physical memory set aside at the boot time, so that the OS does not use it for its processes.
RAM Disks
In order to avoid the non-deterministic overhead of accessing hard disks, part of the available RAM can be used to emulate a hard disk. To have some sort of non-volatile memory that is deterministic a designer can choose to use a flash disk.

Some modern memory management systems are complicated enough that an entire book has been written about them -- Memory Management.

Issues in Real Time System Design

A Real Time system’s goal is to behave deterministically. Determinism implies two aspects. First, if the process asks for CPU, RAM or communication, it should receive it from the coordination. Second, if a failure occurs, the system should know what to do. For a system designer, the most important features of a Real Time application are scheduling tasks, coping with failure and using available resources.

Scheduling tasks

The system designer has to make sure that (at least a clearly identified, small) part of the systems processes are scheduled in a predictable way because, even more than timing, the sequence of processes is an important part of the application. Scheduling of the processes can for example be done by the scheduler. It’s essential that the sequence is determined in a deterministic way, but the scheduler might not suffice here. For example, if two processes have the same priority, it might be unclear what process will come first. A system designer should not expect to know the duration of a process, even if this process gets the full capacity of the processor. Therefore the designer has to make sure that the scheduling works, even in case of the worst scenario.

Failure

The system should behave reliably during internal or external failure. Possible failures should be known by the real time system. If the process can’t recover from a failure, the system should go into a “fail safe/gracefully mode”. If the system can’t satisfy the task’s timing constraints and therefore also the quality demands, it should take action by triggering an error. In such a case, it is important to check if it is possible to remove certain constraints. Internal failure can be a hard- or a software failure in the system. To cope with software failure, tasks should be designed to safeguard error conditions. Hardware failure can be processor, board or link failure. To detect failure the system designer should implement watchdog systems. If the main program neglects to regularly service the watchdog, it can trigger a system reset.

Resources and services

In the context of resources and services the term Quality of Service (QoS) is important. It means that the task must get a ﬁxed amount of “service” per time unit. This service includes hardware, processing time and communication and is deterministically known by the system. In contrast to general OS, the hardware needs to be specifically assigned for every process. In assigning service to tasks, the programmer should take into account “worst case scenarios”: if various tasks could be needing a service, then sooner or later they will want it at the same time. Then the sequence has to maximise the quality of service.

Complexity

There are three classes of system complexity. The first, C1, has centralized hardware and a centralized state. Everything is determined and external factors have no influence on the process. Such a system can be designed by one person. The simplest robots belong to this category. The last, C3, has decentralized hardware and a decentralized state. The system adapts the process due to external factors when necessary. Such a system requires more (approximately 100) designers. An example is the RoboCup team. C2 is an intermediate level and it has decentralized hardware and a centralized state, like for example industrial robots do. Such systems require about 10 designers. The higher the complexity of the interactions (synchronisation and communication) in the system, the harder to make it deterministic because much more aspects should be taken into account.