Key Concepts

Embedded software developers from different industries are independently re-discovering patterns for building concurrent software that is safer, more responsive and easier to understand than naked threads of a Real-Time Operating System (RTOS). These best practices universally favor event-driven, asynchronous, non-blocking, encapsulated state machines instead of naked, blocking RTOS threads. The following sections explain the concepts related to this increasingly popular "reactive approach", and specifically how they apply to real-time embedded systems, which are targeted by the Quantum Leaps frameworks and tools.

Embedded Programming Paradigms

Virtually all embedded systems are event-driven by nature, which means that their main job is to react to events, such as button presses, touches on a screen, time ticks, or arrivals of some data packets. Consequently, most of the time, an embedded system is waiting for events, and only after recognizing an event, the system reacts by performing the appropriate computation. The main challenges are: to perform the right compuation and to perform it in a timely manner.


Traditional Sequential Programming

In spite of the fundamental event-driven nature, most embedded systems are traditionally programmed in a sequential manner, where a program waits for specific events in various places in its execution path by either busy-polling or blocking on a semaphore, a time-delay, or other such mechanism of a traditional Real-Time Operating System (RTOS). Example of the basic sequential code is the traditional "Blinky" implementation:


while (1) { /* RTOS task or a "superloop" */
    RTOS_delay(1000); /* wait for 1000 ms (polling or blocking) */
    BSP_ledOn();      /* turn the LED on  (computation) */

    RTOS_delay(1000); /* wait for 1000 ms (polling or blocking) */
    BSP_ledOff();     /* turn the LED off (computation) */
}

Although the sequential approach is functional in many situations, it does not work very well when there are multiple possible events whose arrival times and order you cannot predict and where it is important to handle the events in a timely manner. The fundamental problem is that while a sequential program is waiting for one kind of event (e.g., elapsing of a time delay) it is not doing anything else and is not responsive to other events (e.g., a button press).


Event-Driven Programming

For this and other reasons, experts in concurrent programming have learned to be very careful with unrestricted threads and various blocking mechanisms of an RTOS, because they often lead to programs that are unsafe and difficult to reason about. Instead, experts recommend the following best practices, which combine multi-threading with the long-known design strategy called event-driven programming:

  1. Keep data isolated and bound to threads. Threads should hide (encapsulate) their private data and other resources, and not share them with the rest of the system.
  2. Communicate among threads asynchronously via messages (event objects). Using asynchronous events keeps the threads running truly independently, without blocking on each other.
  3. Threads should spend their lifetime responding to incoming events, so their mainline should consist of an event-loop that handles events one at a time (to completion), thus avoiding any concurrency hazards within a thread itself.

Active Objects (Actors)

While the best practices of concurrent programming can be applied manually on top of a traditional RTOS, a better way is to use the Active Object (Actor) pattern, which inherently supports and automatically enforces the best practices of concurrent programming.

In this pattern, Active Objects (Actors) are event-driven, strictly encapsulated software objects running in their own threads of control that communicate with one another asynchronously by exchanging events. The UML specification further proposes the UML variant of hierarchical state machines (UML statecharts) with which to model the behavior of event-driven active objects.

The Active Object pattern is valuable, because it dramatically improves your ability to reason about your thread's code and operation by giving you higher-level abstractions and idioms that raise the semantic level of your program and let you express your intent more directly and safely, thus improving your productivity.


Historical Note:
The concept of autonomous software objects communicating by message passing dates back to the 1970s, when Carl Hewitt at MIT developed a notion of an actor. In the 1990s, methodologies like ROOM adapted actors for real-time computing. More recently, UML has introduced the concept of Active Objects that are essentially synonymous with the ROOM actors. Today, the actor model is all the rage in the enterprise computing, because it can deliver levels of reliability and fault tolerance unachievable really with the "free threading" approach. A number of actor programming languages (e.g., Erlang, Scala, D) as well as actor libraries and frameworks (e.g., Akka, Kilim, Jetlang) are in extensive use. In the real-time embedded space, active objects frameworks provide the backbone of various modeling and code generation tools. Examples include: IBM Rational Rhapsody (with OXF/SXF frameworks) and National Instruments LabVIEW (with LabVIEW Actor Framework).

Active Object (Actor) Frameworks

Active objects (actors) are universally implemented by means of a software framework that provides, at a minimum, an execution context (thread) for each active object, queuing of events, and event-based timing services.

Inversion of Control
The most important point to understand about a framework is how it differs from a toolkit, such as a traditional (Real-Time) Operating System. When you use an (RT)OS, you write the main body of each thread and you call the code from the (RT)OS (such as a semaphore, time delay, etc.) In contrast, when you use a framework, you reuse the whole architecture and write the code that it calls. This leads to inversion of control compared to the traditional (RT)OS and is very characteristic to virtually all event-driven systems, such as Active Objects.
  The inversion of control is the main reason for the architectural-reuse and enforcement of the best practices, as opposed to re-inventing them for each project at hand. This leads to a much higher conceptual integrity of the final product and dramatic improvement of your productivity.

Embedded Actor Frameworks

In the resource-constrained embedded systems, the biggest concern has always been about the size and efficiency of such Actor (Active Object) frameworks, especially that the frameworks accompanying various modeling tools have traditionally been built on top of a conventional RTOS, which adds memory footprint and CPU overhead to the final solution.

However, it turns out that an Active Object framework can be actually smaller than a traditional RTOS. This is possible, because Active Objects don't need to block internally, so most blocking mechanisms (e.g., semaphores) of a conventional RTOS are not needed.


Comparison of RAM/ROM sizes of QP frameworks and various (RT)OSes.
Note the logarithmic scales on the axes.
RAM/ROM footprint

For example, the diagram above shows the RAM/ROM sizes of the QP/C, QP/C++, and Q-nano Active Object frameworks from Quantum leaps versus a number of conventional (RT)OSes. The diagram shows the total system size as opposed to just the RTOS/OS footprints. As you can see, when compared to conventional RTOSes, QP frameworks require significantly less RAM (the most precious resource in single-chip MCUs). All these characteristics make event-driven Active Objects a perfect fit for single-chip microcontrollers (MCUs). Not only you get the productivity boost by working at a higher level of abstraction than raw RTOS tasks, but you get it at a lower resource utilization and better power efficiency, because event-driven systems use the CPU only when processing events and otherwise can put the MCU in a low-power sleep mode.


Object-Oriented Programming in C
Even though the QP/C and QP-nano frameworks are implemented in standard ANSI-C, they extensively use object-oriented design principles such as encapsulation (classes), single inheritance, and, starting with QP5, polymorphism (late binding). At the C language level, these proven ways of software design become design-patterns and coding idioms.
AN: OOP in C
The Quantum Leaps Application Note Object-Oriented Programming in C describes how the OOP design patterns are implemented in QP/C and how you should code them in your own applications.

True Encapsulation for Concurrency

In a sense active objects are the most stringent form of object-oriented programming (OOP), because the asynchronous communication enables active objects to be truly encapsulated. In contrast, the traditional OOP encapsulation, as provided by C++, C# or Java, does not really encapsulate anything in terms of concurrency. Any operation on an object runs in the caller's thread and the attributes of the object are subject to the same race conditions as global data, not encapsulated at all. To become thread-safe, operations need to be explicitly protected by a mutual exclusion mechanism, such as a mutex or a monitor, but this reduces parallelism dramatically, causes contention, and is a natural enemy of scalability.

In contrast, all private attributes of an active object are truly encapsulated without any mutual exclusion mechanism, because they can be only accessed from the active object's own thread. Note that this encapsulation for concurrency is not a programming language feature, so it is no more difficult to achieve in C as in C++, but it requires a programming discipline to avoid sharing resources (shared-nothing principle). However, the event-based communication helps immensely, because instead of sharing a resource, a dedicated active object can become the manager of the resource and the rest of the system can access the resource only via events posted to this manager active object.


Asynchronous Communication

Each active object has its own event queue and receives all events exclusively through this queue. Events are delivered asynchronously, meaning that an event producer merely posts an event to the event queue of the recipient active object but does not wait (block) in line for the actual processing of the event. The event processing occurs always in the thread context of the recipient active object. The active object framework, such as QP, is responsible for delivering and queuing the events in a thread-safe and deterministic manner.


Run-to-Completion Event Processing

Each active object handles events in run-to-completion (RTC) fashion, which also is exactly the semantics universally assumed by all state machine formalisms, including UML statecharts. RTC simply means that an active object handles one event at a time, that is, the active object must complete the processing of an event before it can start processing of the next event from its queue.

  RTC versus Preemption
In the case of active objects, where each object runs in its own thread, it is important to clearly distinguish the notion of RTC from the concept of thread preemption. In particular, RTC does not mean that the active object thread has to monopolize the CPU until the RTC step is complete. Under a preemptive kernel, for example, an RTC step can be preempted by another thread executing on the same CPU. This is determined by the scheduling policy of the underlying kernel, not by the active object model. When the suspended thread is assigned CPU time again, it resumes from the point of preemption and, eventually, completes its event processing. As long as the preempting and the preempted threads don't not share any resources, there are no concurrency hazards.

No Blocking

Most conventional RTOS kernels manage the tasks and all inter-task communication based on blocking, such as waiting on a semaphore. However, blocking is problematic, because while a task is blocked waiting for one type of event, the task is not doing any other work and is not responsive to other events. Such a task cannot be easily extended to handle new events.

In contrast, event-driven active objects don't need to block, because in event-driven systems the control is inverted compared to traditional RTOS tasks. Instead of blocking to wait for an event, an active object simply finishes its RTC step and returns to the framework to be activated when the next event arrives. This arrangement allows active objects to remain responsive to events of all types, which is central to the unprecedented flexibility and extensibility of active object systems.

The QP frameworks provide all mechanisms you might need for non-blocking operation. For example, instead of delaying an active object with a blocking delay() call, you can use a time event to arrange activation in the specific time in the future.


Simple Real-Time Kernel

While the active object model can work with a traditional blocking RTOS, it can also work with a much simpler non-blocking, run-to-completion kernel (see also basic tasks in OSEK/VDX). The QP frameworks provide such a super-simple and super-fast kernel called QK, which provides fully preemptive multitasking using a single stack for all active object threads.


  The fixed-priority, preemptive QK kernel meets all the assumptions of the Rate Monotonic Analysis (RMA) to ensure schedulability of active object's threads. In fact, the non-blocking execution model makes the RMA method much simpler to apply to a system of active objects than to a set of RTOS tasks.

Design by Contract

Design by Contract (DbC) is a philosophy that views a software system as a set of components whose collaboration is based on precisely defined specifications of mutual obligations — the contracts. The central idea of this method is to inherently embed the contracts in the code and validate them automatically at runtime. In C and C++, the most important aspects of DbC (the contracts) can be implemented with assertions. Assertions are increasingly popular among the developers of mission-critical software. For example, NASA requires certain density of assertions in such software.

In the context of active object frameworks, DbC provides an excellent methodology for implementing a very robust error-handling policy. Due to inversion of control so typical in all event-driven systems, an active object framework controls many more aspects of the application than a traditional (Real-Time) Operating System. Such a framework is in a much better position to make sure that the application is performing correctly, rather than the application to check error codes or catch exceptions originating from the framework.

  The QP frameworks extensively apply the customized embedded-systems-friendly assertions to ensure correct operation of the applications.

Hierarchical State Machines

As suggested in the UML specification and similar as in ROOM, the behavior of each Active Object in the QP frameworks is specified by means of a hierarchical state machine (UML statechart), which is a very effective and elegant technique of decomposing event-driven behavior.


State Nesting

The most important innovation of hierarchical state machines over classical FSMs is the hierarchical state nesting. The value of state nesting lies in avoiding repetitions, which are inevitable in the traditional "flat" FSM formalism and are the main reason for the "state-transition explosion" in FSMs. The semantics of state nesting allow substates to define only the differences of behavior from the superstates, thus promoting sharing and reusing behavior.


  The hallmark of the hierarchical state machine implementation strategy in QP is traceability, which is direct, precise, and unambiguous mapping of every state machine element to human-readable C or C++ code. Preserving the traceability from requirements through design to code is essential for mission-critical systems, such as medical devices or avionic systems.

Graphical Modeling

Model-driven development holds promise of being the first true generational leap in software development since the introduction of the compiler. Unfortunately, software modeling has been always associated with complex, expensive, "high-ceremony" tools with a very steep learning curve and a price tag to match. After having found that such modeling tools could not pull their own weight, many practitioners have given up modeling altogether. But this rejection of modeling for software is ironic when you consider that software is the engineering medium best positioned to benefit from it.

What embedded software developers are often asking for is a simpler, "low-ceremony" tool that works at a lower-level closer to the code. This characterization is not pejorative. It simply means that developers wish that the tool would map their graphical design unambiguously and directly to C or C++ code, without intermediate layers of "Platform-Independent Models" (PIMs), "Platform-Specific Models" (PSMs), complex "Model-Transformations", or "Action Languages".

  These are exactly the design objectives or the freeware, "low-ceremony" QM modeling tool from Quantum Leaps. QM provides intuitive diagramming environment for creating good looking hierarchical state machine diagrams and hierarchical outlines of your entire applications. QM respects your graphical layout as much as possible and will not re-attach or re-route connectors, resize nodes, or adjust text annotations. You will find that you don't need to "fight the tool". QM is available for 64-bit Windows, 64-bit Linux, and Mac OS X.

Code Generation

With modeling, just as with anything else in the embedded space, the ultimate criterion for success is the return on investment (ROI). As it turns out, the ROI of software modeling is negative unless the models are used to generate substantial portions of the production code. For example, according to the UML Modeling Maturity Index, without code generation modeling can reach at most 30% of its potential, and this is assuming correct use of behavioral modeling. Without it, the benefits are below 10%. This is just too low to outweigh all the costs.

Therefore, the QM modeling tool was designed from the ground up to be "code-centric". QM is a unique tool on the market that supports both the logical design and physical design. Unlike other graphical tools, QM gives you complete control over the generated code structure, directory names, file names, and elements that go into every file. You can mix your own code with the synthesized code and use QM to generate as much or as little of the overall code as you see fit.

As most tools capable of code generation, the models you create with QM are based on an event-driven actor framework. This is because such a framework provides well-defined "framework extension points" designed for customizing the framework into applications, which in turn provide well-defined rules for generating code.

  Much of the simplicity of QM derives from the fact that it limits itself to C or C++, and the QP frameworks, as opposed to supporting an open-ended number of programming languages and yet-to-be-defined frameworks.

Software Tracing

Software tracing is a method for obtaining diagnostic information about the embedded software in a live environment without the need to stop the application to get the system feedback. Software tracing always involves some form of a target system instrumentation to log interesting discrete events for subsequent retrieval from the system and analysis.

Software tracing is especially effective and powerful in combination with the event-driven Active Object Framework, such as QP/C or QP/C++, because a running application built of Active Objects is a highly structured affair where all important system interactions funnel through the framework and the state-machine engine. This offers a unique opportunity to instrument these relatively small parts of the overall code to gain unprecedented insight into the entire system.

For example, instrumentation added to the QP/C and QP/C++ frameworks (called QS — "QP Spy") produces trace data that is thorough enough to reconstruct complete sequence diagrams and detailed state machine activity for all active objects in the system. You can selectively monitor all event exchanges, event queues, event pools, and time events because all these elements are controlled by the framework. Additionally, if you use one of the kernels built into QP (the cooperative QV kernel or the preemptive QK kernel), you can obtain all the data available to a traditional RTOS as well, such as context switches and mutex activity.