QP/C++  7.3.3
Real-Time Embedded Framework
Loading...
Searching...
No Matches
Active Objects

State Machinessrs_edm

Concepts & Definitions

As described in the Overview, the main goal of the QP Framework is to provide a lightweight and efficient implementation of the Active Object Model of Computation with the specific focus on real-time embedded (RTE) systems, such as single-chip microcontroller units (MCUs).

Active Object Model of Computation

The Active Object Model of Computation represents a paradigm shift compared to the traditional "shared state concurrency" based on explicit mutual exclusion and managing threads by blocking. The following subsections describe Active Object properties and explain why this model of computation is safer and makes it easier to write correct concurrent software.

Active Objects

Active Objects (a.k.a., Actors) are autonomous software objects, each possessing an event queue and execution context. They encapsulate state and behavior and communicate asynchronously by exchanging events. Figure SRS-41 below shows a QP Application consisting of multiple, event-driven Active Objects that collectively deliver the desired functionality:

Figure SRS-41: Active Objects in QP

Encapsulation for Concurrency

The traditional object-oriented encapsulation, as provided by C++, C# or Java, does not really encapsulate anything in terms of concurrency. As shown in Figure SRS-42a, any operation on a passive object still runs in the caller's thread. If that passive object is shared among multiple threads, the object's attributes are subject to the same race conditions as global data, not encapsulated at all. To become concurrency-safe, operations need to be explicitly protected by an appropriate mutual exclusion mechanism, such as a mutex (for threads) or a critical section (for Interrupt Service Routines). However, this reduces responsiveness (blocking or increased latency), causes contention, and often leads to missed real-time deadlines [Sutter:10]. Also this style of managing concurrency is inherently unsafe because developers might simply forget to apply mutual exclusion or use an incorrect mechanism, which can lead to latent, highly intermittent, hard-to-find and hard-to-fix concurrency bugs.

Figure SRS-42a: Threads interacting (synchronously) with a passive object

In contrast, as shown in Figure SRS-42b, all interactions with an Active Object occur by posting events, which are all handled in the execution context of the Active Object. As long as there is no sharing of data or resources among Active Objects (or any other concurrent entities), there are no concurrency hazards. Also, because each event is processed to completion (see Run-to-Completion processing), event processing is naturally serialized. This means that an Active Object is truly encapsulated without any mutual exclusion mechanisms. In this sense Active Objects are the most stringent form of object-oriented programming because they enable strict encapsulation for concurrency, which is much safer than the "naked" threads.

Figure SRS-42b: Threads interacting (asynchronously) with an Active Object
Note
Please note that 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 on behalf of the application developers 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/broker of the resource and the rest of the system can access the resource only via events posted to this broker Active Object.
Attention
QP Framework by itself cannot and is not required to guarantee or enforce Active Object encapsulation. Achieving the strict encapsulation of Active Objects becomes then the responsibility of the QP Applications. But at the very least, the QP Framework architecture and design must provide adequate and thread-safe event-based information exchange mechanisms, which can replace the traditional sharing of data or resources.

Event Queue

Each Active Object has its own event queue and receives all events exclusively through that queue. This means that the event queue has only a single consumer (the Active Object that owns the queue). On the other hand, the event queue must accommodate multiple producers that don't need to be only Active Objects, but also interrupts (ISRs), or other software components (see Figure SRS-41). The Active Object infrastructure, such as the QP Framework in this case, is responsible for delivering and queuing the events in a deterministic and thread-safe manner.

Execution Context

In the UML, Active Object is defined as: "the object having its own thread of control" [UML 2.5]. A traditional thread might indeed be used for Active Objects when the QP Framework runs on top of a traditional multitasking kernel (e.g., traditional RTOS or general-purpose OS).

However, the Active Object model of computation can also work with real-time kernels that don't necessarily support the notion of traditional blocking threads. Active Objects have no need for blocking while handling events, which opens up possibilities of using lightweight, non-blocking kernels that might be cooperative or fully preemptive. (See also lightweight kernels provided in QP, such as Cooperative Run-to-Completion Kernel, Preemptive Run-to-Completion Kernel, and Preemptive Dual-Mode Kernel.)

Priority

The execution context of an Active Object is closely related to its priority relative to other Active Objects or "naked" threads in the system. In fact, an Active Object can be viewed primarily as a priority level for executing the functionality it encapsulates. In the QP Framework, each Active Object is required to have a unique priority. (See also REQ-QP-03_01.)

Asynchronous Communication

All events are delivered to Active Objects asynchronously, meaning that an event producer merely posts an event to the event queue of the recipient Active Object but doesn't wait in line for the actual processing of the event.

The QP Framework makes no distinction between external events generated from interrupts and internal events originating from Active Objects. As shown in Figure SRS-41, an Active Object can post events to any other Active Object, including to self. All events are treated uniformly, regardless of their origin.

Run-to-Completion (RTC)

Each Active Object processes events in run-to-completion (RTC) fashion, which must be guaranteed by the underlying QP Framework. RTC means that Active Objects process the events one at a time and the next event can only be processed after the previous event has been processed completely. RTC also means that QP Framework must guarantee that the event being processed (called current event) remains available and unchanging for the whole duration of the RTC step. RTC event processing is the essential requirement for proper execution of state machines.

Note
It is very important to clearly distinguish the notion of RTC from the concept of preemption [OMG 07]. In particular, RTC does not mean that the Active Object thread has to monopolize the CPU until the RTC step is complete. In fact, RTC steps can be preempted by interrupts or other threads executing on the same CPU. Such thread preemption is determined by the scheduling policy of the underlying multitasking kernel, not by the Active Object model. When the preempted Active Object is assigned the CPU time again, it resumes its event processing from the point of preemption and, eventually, completes its RTC step. As long as the preempting and the preempted threads don't share any resources (see Encapsulation), there are no concurrency hazards.

No Blocking

Most traditional operating systems manage the threads and all inter-thread communication based on blocking, such as waiting on a semaphore or a time-delay. However, blocking (as in the middle of the RTC step) is incompatible with the RTC event processing requirement. This is because every blocking call is really another way to deliver an event (event is delivered by unblocking and return from a blocking call). Such "backdoor" event delivery happening in the middle of the RTC step violates the RTC semantics, because after unblocking the Active Object needs to process two events at a time (the original one and the new one delivered by unblocking).

Another detrimental consequence of blocking (or polling for events) inside RTC steps is that Active Objects become unresponsive to events delivered to their event queues. This, in turn, can cause Active Objects to miss their hard-real time deadlines and also can cause overflow of the internal event queue.

Finally, blocking (or polling for events) means that the expected sequences of events are hard-coded, which is inherently inflexible and not extensible, especially if the system must handle multiple event sequences (which turns out to be the case in most real-life systems).

Support For State Machines

Event-driven components, like Active Objects, must often retain the execution context from one event to the next. This must be done without blocking, so the context can't be preserved on the call-stack as it is done in the traditional, blocking RTOS threads. Instead, the context between events must be preserved in some other way, which often leads to multitude of variables and flags checked and modified in a convoluted if-then-else logic (a.k.a. "spaghetti code").

A well know alternative to such "improvised context management" is the concept of a state machine, which manages the execution context using "states". QP Framework augments and complements the Active Object model of computation by providing support for state machines to represent the internal behavior of Active Objects.

Remarks
The relationship between Active Objects and state machines is mutually synergistic. On one hand, the Active Objects provide the execution context and event queuing that the state machines need to process the events in a run-to-completion fashion. On the other hand, state machines provide the structure and clear design for the event-driven behavior running inside the Active Objects. State machines are also the most constructive part of the design amenable to modeling and automatic code generation.

Inversion of Control

Event-driven systems require a distinctly different way of thinking than traditional sequential threads. When a sequential thread needs some incoming event, it explicitly blocks and waits in-line until the event arrives. Thus the sequential thread remains "in control" at all times, but while waiting for one kind of event, it cannot respond (at least for the time being) to any other events.

In contrast, most event-driven applications are structured according to the Hollywood principle, which essentially means "Don't call us, we'll call you." So, an event-driven Active Object is not in control while waiting for an event; in fact, it's not even active. Only once the event arrives, the event-driven program is called to process the event and then it quickly relinquishes the control again. This arrangement allows an event-driven program to wait for many events in parallel, so the system remains responsive to all events it needs to handle. This scheme implies that in an event-driven system the control resides within the event-driven infrastructure (QP Framework), rather than in the application. In other words, the control is inverted compared to a traditional sequential thread.

Framework vs. Toolkit

Inversion of control is the key property that makes a software framework different from a software toolkit. A toolkit, such as a traditional RTOS, is essentially a set of predefined functions that you can call. When you use a toolkit, you write the main body of the application, such as the body of all RTOS threads, and call the various blocking functions from the RTOS. When you use a framework (such as QP), you reuse the main body (codified inside the framework) and provide the application code that it calls, so the control resides in the framework rather than in your code. Indeed, this inversion of control gives the event-driven infrastructure all the defining characteristics of a framework:

"One important characteristic of a framework is that the methods defined by the user to tailor the framework will often be called from within the framework itself, rather than from the user's application code. The framework often plays the role of the main program in coordinating and sequencing application activity. This <u>inversion of control</u> gives frameworks the power to serve as extensible skeletons. The methods supplied by the user tailor the generic algorithms defined in the framework for a particular application."
–Ralph Johnson and Brian Foote

Low Power Architecture

Most modern embedded microcontrollers (MCUs) provide an assortment of low-power sleep modes designed to conserve power by gating the clock to the CPU and various peripherals. However, the sleep modes are entered under the software control and therefore require an appropriate software infrastructure.

An event-driven framework, like QP, based on inversion of control is particularly suitable for taking advantage of these power-savings features because the framework can easily detect situations in which the system has no more events to process, called the idle condition. In that case the framework can place the MCU into a low-power sleep mode safely and without creating race conditions with active interrupts.

Requirements

REQ-QP-03_00

REQ-QP-03_00
QP Framework shall provide the Active Object abstraction to QP Application
Description
QP Framework shall define an event-driven Active Object abstraction, which can be customized by QP Application and executed by QP Framework according to the Active Object model of computation.
Use Case
QP Framework can meet this requirement by proving the Active Object abstraction as a class, which the QP Applications can customize by subclassing. Such an Active Object base class must be customizable at compile-time for a wide variety of real-time kernels, including traditional blocking RTOS and event-driven, non-blocking kernels.

REQ-QP-03_01

REQ-QP-03_01
QP Framework shall be able to manage up to 64 Active Object instances
Description
The maximum number of Active Object instances managed by QP Framework at any given time shall be compile-time configurable, but is limited to 64 instances.
Use Case
For best memory and CPU performance, the maximum number of Active Object instances can be configured below the 64 maximum, and often it might be advantageous to use powers of 2, for example, configure the limit as 32 or 16. The actual number of Active Object instances registered with QP Framework can be lower than the configured compile-time limit, but it cannot exceed the limit.

REQ-QP-03_10

REQ-QP-03_10
Active Object abstraction shall provide the unique priority for each Active Object instance
Description
The Active Object priority is a positive integer number between 1 and the maximum configured number of Active Objects (see REQ-QP-03_20). The priority shall conform to the numbering scheme defined as follows: priority 1 corresponds to the lowest priority and higher numbers correspond to higher priorities (direct priority numbering scheme). The priority 0 cannot be assigned to any Active Object, and is reserved for the idle thread (or the idle condition) of the underlying real-time kernel.
Use Case
This QP priority numbering scheme is fixed and does not change, even if the underlying real-time kernel uses a different priority scheme (e.g., reversed priority numbering). However, the QP priority must remain consistent with the priority of the underlying kernel in that higher QP priority numbers must correspond to a higher (or at least not lower) urgency threads.

REQ-QP-03_11

REQ-QP-03_11
Active Object abstraction may provide second "auxiliary priority" for each Active Object instance
Description
The second "auxiliary priority" may be used for different purposes, depending on the underlying real-time kernel.
Use Cases
In some real-time kernels, the "auxiliary priority" might be used to represent preemption threshold. In other kernels, it might represent the native thread priority according to the priority numbering scheme of the kernel.

REQ-QP-03_12

REQ-QP-03_12
Active Object abstraction shall provide an event queue for each Active Object instance
Description
The event queue shall provide the FIFO (First-In-First-Out) policy for posting events from the outside of the Active Object instance and the LIFO (Last-In-First_out) policy (intended primarily for self-posting events). The event queue type shall be compile-time configurable to allow various blocking/no-blocking mechanisms corresponding to the chosen real-time kernel. The capacity of the event queue (maximum number of events it can hold) shall be run-time configurable before the Active Object instance starts executing.
Use Case
QP Framework can meet this requirement by proving event queue as an attribute inside the Active Object class. The type of the event queue must be compile-time configurable to match the underlying real-time kernel that executes the Active Objects in QP.

REQ-QP-03_13

REQ-QP-03_13
Active Object abstraction may provide an optional execution context for each Active Object instance
Description
The execution context (e.g., thread) attribute shall be compile-time configurable to allow various thread types corresponding to the chosen real-time kernel.
Use Case
In case QP uses a traditional RTOS, the execution context might be a thread-control-block (TCB) or just a thread handle/pointer. In case of other real-time kernels, the execution context might be a thread identifier or might not be needed at all.

REQ-QP-03_14

REQ-QP-03_14
Active Object abstraction may provide optional "operating-system object" for each Active Object instance
Description
The optional "operating system object" shall be compile-time configurable to allow various operating-system object types corresponding to the selected real-time kernel.
Use Case
For example, the Active Object's event-queue for the POSIX operating system might require additional condition-variable attribute ("operating system object") to implement blocking on an empty queue.

REQ-QP-03_20

REQ-QP-03_20
Active Object abstraction shall encapsulate its internals
Description
The Active Object abstraction should hide and protect its internals, both for reading and writing by any outside entities. Additionally, QP framework shall allow the QP Application to hide and protect any additional attributes added to the derived Active Objects.

REQ-QP-03_21

REQ-QP-03_21
Active Object abstraction shall allow Applications to easily access the internal attributes from inside the Active Object
Description
Notwithstanding Requirement REQ-QP-03_10, QP framework shall allow for easy and computationally inexpensive access to the internal attributes of an Active Object from within the AO, such as from its internal state machine.
Use Case
A good example of implementing such a policy is the concept of class encapsulation in OOP, where the internal attributes are accessible to the class operations (e.g., via the this pointer) and are harder to access from the outside.
Related To
REQ-QP-02_24

REQ-QP-03_30

REQ-QP-03_30
Active Object abstraction shall support run-to-completion event processing
Description
Regardless of the real-time kernel used, QP Framework must guarantee that every event is processed to completion and that during this time the event remains available and unchanged.

REQ-QP-03_40

REQ-QP-03_40
Active Object abstraction shall provide support for state machines.
Description
Each Active Object instance shall have an internal state machine, with the features and semantics specified in Section State Machines. QP Framework shall guarantee execution of such internal state machines in Run-to-Completion fashion.

REQ-QP-03_50

REQ-QP-03_50
QP Framework shall support low-power sleep modes.
Description
In systems with (hardware-assisted) sleep modes, QP Framework shall detect the idle condition of the system and provide a mechanism for QP Application to enter the desired sleep mode safely. "Entering a sleep mode safely" means that there should be no race conditions and situations, where the system would enter a sleep mode with some events present in the Active Object event queues and thus available for processing.

State Machinessrs_edm