As described in the Overview, the main goal of the QP/C++ Framework component 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).
The Active Object Model of Computation represents a paradigm shift compared to the traditional "shared state concurrency" based on a traditional Real-Time Operating System (RTOS) with hard-coding various blocking calls to the RTOS and managing shared resources by explicit mutual exclusion. 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 (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-AOS below shows a QP/C++ Application consisting of multiple, event-driven Active Objects that collectively deliver the desired functionality:
The traditional object-oriented encapsulation, as provided by C++, C#, or Java, does not encapsulate anything in terms of concurrency. As shown in Figure SRS-SEQ-TH, any operation on a passive object still runs in the caller's thread (e.g., RTOS 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 in threads or increased latency for ISRs), causes contention, and often leads to missed real-time deadlines [Sutter:10]. Also, this style of managing concurrency is inherently unsafe because developers might 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 hazards.
In contrast, as shown in Figure SRS-AOS, 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.
Encapsulation for concurrency is not a programming language feature, so it is no more difficult to achieve in C than in C++. Still, 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.
In the UML, Active Object is defined as: "the object having its thread of control" [UML 2.5]. A traditional thread might indeed be used for Active Objects when the QP/C++ Framework component operates with a conventional 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 non-preemptive or fully preemptive. (See also lightweight kernels provided in QP, such as Non-Preemptive Kernel, Preemptive Non-Blocking Kernel, and srs-qp_qxk.)
The execution context of an Active Object is closely related to its priority relative to other Active Objects or "naked" threads in the system. An Active Object can be viewed primarily as a priority level for executing the functionality it encapsulates. In QP/C++, each Active Object is required to have a unique priority. (See also SRS_QP_AO_01.)
Each Active Object processes events in run-to-completion (RTC) fashion, which must be guaranteed by the underlying QP/C++ Framework component. 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.
Current event is the event being processed in the run-to-completion (RTC) step. The event-driven infrastructure (QP/C++ Framework component in this case) must guarantee that the current event remains available and unchanging for the whole duration of the RTC step, which might be preempted multiple times (by higher-priority processing).
Most traditional operating systems (both RTOS and general-purpose OS) 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 semantics. This is because every blocking call is really another way to deliver an event (event is delivered by unblocking and returning 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 in-line polling for events) means that the expected sequence of events becomes 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. (See also "Blocking==Technical Debt"↑.)
Each Active Object has its 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-AOS). The Active Object infrastructure, such as the QP/C++ Framework component in this case, is responsible for delivering and queuing the events in a deterministic and thread-safe manner.
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 (AO) but doesn't wait in line for the actual processing of the event. The QP/C++ Framework makes no distinction between external events generated from interrupts and internal events originating from Active Objects. As shown in Figure SRS-AOS, an Active Object can post events to any other Active Object, including to itself. All events are treated uniformly, regardless of their origin.
Event-driven components, like Active Objects, must generally 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 maintained in some other way, which often leads to a multitude of variables and flags checked and modified in a convoluted if-then-else logic (a.k.a. "spaghetti code").
A well-known alternative to such "improvised context management" is the concept of a state machine, which manages the execution context using "states". QP/C++ Framework augments and complements the Active Object model by providing support state machines to represent the internal behavior of Active Objects.
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.
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 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/C++ Framework component), rather than in the application. In other words, the control is inverted compared to a traditional sequential thread.
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
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. 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-saving 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.
An Event is the specification of some occurrence that may potentially have significance to the system under consideration. Upon such an occurrence, a corresponding Event (class) is instantiated, and the generated Event Instance (object) outlives the instantaneous occurrence that generated it.
Event Instances (a.k.a. Messages) are objects specifically designed for communication and synchronization within an event-driven system, such as a QP/C++ Application. Once generated, an Event Instance (a.k.a. Message) is propagated to the system, where it can trigger various Actions. These Actions might involve generating secondary Event Instances.
An Event always has information about the type of occurrence that generated the Event Instance ("what happened"), which will be called Signal in this document. Event Signals are typically enumerated constants that indicate which specific occurrence out of a set of all possible (enumerated) occurrences has generated the Event Instance.
An Event can have (optionally) associated Parameters, allowing the Event Instance to convey the quantitative information regarding that occurrence. For example, a Keystroke event generated by pressing a key on a computer keyboard might have associated parameters that carry the character scan code and the status of the Shift, Ctrl, and Alt keys.
Event-driven systems work by responding to Events. In general, the system's response to a given Event depends both on the nature of that Event (captured in its Signal) and on the history of events the system has received. In practice, not all aspects of the whole "history of past events" are relevant. The simplified history consisting only of factors that are consequential for the system's response to future events is called the Relevant History.
State is an equivalence class of past histories of a system, all of which are equivalent in the sense that the future behavior of the system given any of these past histories will be identical. Thus, the concept of "State" is the most efficient representation of the Relevant History of the system. It is the minimum information that captures only the relevant aspects for the future behavior and abstracts away all irrelevant aspects.
Transition is a change from one State to another during the lifetime of a system. In event-driven systems, a change from one state to another can be caused only by an event. The events that trigger a Transition are called the Triggering Event or the Trigger of the Transition.
State Machine is the set of all States (equivalence classes of relevant histories), plus all the Transitions (rules for changing States). An essential benefit of the State Machine formalism is the expressive graphical representation of State Machines in the form of state diagrams.
Hierarchical State Machine (a.k.a. UML statechart) is an advanced formalism that extends the traditional state machines in several ways. The most crucial innovation of UML state machines over classical state machines is the introduction of hierarchically nested states. The value of state nesting lies in avoiding repetitions, which are inevitable in the traditional "flat" state machine formalism. The semantics of state nesting allow substates to define only the differences in behavior from the superstates, thus promoting sharing and reuse of behavior.
State Machines, and Hierarchical State Machines, in particular, can be implemented in many different ways. A specific way of implementing a state machine will be called here a State Machine Implementation Strategy, and the following properties can characterize it:
No single state machine implementation strategy can be optimal for all circumstances, and therefore, the QP/C++ Framework component shall support multiple and interchangeable strategies (see SRS_QP_SM_20).
All state machine formalisms assume run-to-completion (RTC) event processing. RTC means that a state machine can process only one event at a time and that the next event can only be processed after the previous event has been processed completely.
Every state machine must be initialized before it can process any events. The initialization is accomplished by executing the top-most initial transition, which must be present in every well-formed state machine.
The event processing inside a state machine is called dispatching an event to the state machine, and it requires collaboration between the QP/C++ Framework component and the QP/C++ Application. Figure RS-SM-DIS illustrates the interactions between the State Machine Processor inside QP/C++ Framework component and State Machine Specification inside QP/C++ Application, whereas a typical RTC event processing step involves multiple such interactions.
The framework chooses elements of the "State Machine Specification" to call (e.g., states). The "Specification" then performs the actions and returns the status of processing (e.g., a transition has been taken) to the "State Machine Processor". Based on this status, the "State Machine Processor" decides which element of the "Specification" to call next or that the processing is complete.
The "State Machine Specification" is provided inside the QP/C++ Application and is prepared according to the rules defined by the chosen State Machine Implementation Strategy in QP/C++ Framework component. Typically, an implementation strategy represents a state machine as several elements, such as states, transitions, etc.
The "State Machine Specification" can mean state machine code (when the state machine is coded manually) or a state machine model (when the state machine is specified in a modeling tool, like "QM"↑). Either way, it is highly recommended to think of the state machine implementation as the specification of state machine elements, not merely code. This notion of "specifying" a state machine rather than coding it can be reinforced by selecting an expressive and entirely traceable state machine implementation strategy, see SRS_QP_SM_40. The advantage of a traceable implementation is that each artifact at all levels of abstraction (design to code) unambiguously represents an element of a state machine.
A state machine is executed in the QP/C++ Framework component by the "State Machine Processor", which is a passive software component that needs to be explicitly called from some context of execution (e.g., Active Object). Once called, the "State Machine Processor" decides which parts of the "State Machine Specification" shall execute and then examines the status of returned back by the "State Machine Specification" as to what has happened. For example, the returned status might inform the "State Machine Processor" that a state transition needs to be taken, or that the event needs to be propagated to the superstate in the hierarchical state machine.
Between the discrete RTC steps, the state machine remains in a stable state configuration, which is called the current state. The current state changes in real-time as the state machine executes RTC steps and transitions from one state to another. Because the state changes occur at run-time, every state machine must store its state in a variable, which is called state variable.
The event that has been dispatched to the state machine is called the current event. This current event must not change and must be accessible to the state machine over the entire RTC step.
One of the primary responsibilities of the QP/C++ Framework component is to reliably and safely deliver QP events from various producers to Active Objects. The event delivery is asynchronous, meaning that the producers only post events to Active Objects, but don't wait in line for the processing of the events. Any part of the system can produce events, not necessarily only the Active Objects. For example, ISRs, device drivers, or legacy code running outside the framework can produce events. On the other hand, only Active Objects can consume QP events, because only Active Objects are guaranteed to have event queues.
Event delivery mechanisms can be broadly classified into the following two categories (see Figure SRS-EDM):
Direct event posting is the simplest mechanism that allows producers to post events directly to the event queue of the recipient Active Object. Figure SRS-EDM illustrates this form of communication as red arrows directly connecting event producers and the consumer Active Objects.
Direct event posting is a "push-style" communication mechanism, in which recipients receive unsolicited events whether they "want" them or not. Direct event posting is well-suited for situations where a group of Active Objects, or an Active Object and an ISR, form a subsystem providing a particular service, such as a communication stack, GPS capability, digital camera subsystem in a mobile phone, or the like. This style of event passing requires that the event producers "know" the recipients and their interests in various events. The "knowledge" that a sender needs is, at a minimum, the handle (e.g., a pointer) to the recipient Active Object.
A direct event posting mechanism might increase the coupling among the components, especially when the recipients of the events are hard-coded inside the event producers. However, one way of reducing the coupling is to allow the recipients to "register" with the producers at runtime (e.g., the event producer can store a pointer to the direct consumer of the events), so that the producer does not need to hard-code the recipient(s).
Publish-subscribe event delivery is shown in Figure SRS-EDM as a "software bus" into which Active Objects "plug in" through the specified interface. Active Objects interested in specific events subscribe to one or more event signals by the QP/C++ Framework component. When an event producer chooses to publish an event, QP/C++ Framework component delivers the event to all subscribers, which entails event multicasting the event (sometimes incorrectly called broadcasting). Publication requests can originate asynchronously from many sources, not necessarily just from Active Objects. For example, events can be published from interrupts (ISRs), device drivers, or the "naked" threads (in case QP runs on top of a conventional RTOS/OS).
Publish-subscribe is a "pull-style" communication mechanism in which recipients receive only solicited (subscribed) events. The properties of the publish-subscribe model are:
In any event-driven system, event delivery is critical for the proper function of the entire system. If the underlying event-driven infrastructure does not or cannot guarantee event delivery, the application has to compensate by checking, verifying, and potentially repeating delivery of most events. However, in the single address space of an embedded MCU, there is no reason why event delivery (via shared memory) should fail. Under such circumstances, the event delivery mechanism is similar to the basic function call mechanism. In both cases, these basic mechanisms can fail if the system does not provide enough resources (event queues and event pools in the case of event delivery and stack space in the case of the function call mechanism). Virtually all systems consider the basic function call mechanism to be guaranteed, which assumes adequate stack resources (this involves multiple stacks if a traditional RTOS is used). Similarly, event-driven systems running in a single address space can consider the basic event delivery mechanism to be guaranteed, which assumes adequate event-queue and event-pool sizes. Such event delivery guarantee is the single most powerful feature that drastically simplifies QP Applications.
Not all events in the system are critical. Some events are not essential, and the application can afford to lose them occasionally. If events of this kind are produced frequently and would overwhelm the system, the event delivery guarantee would not be the desired approach. Instead, events of this type should be delivered by an alternative "best-effort event delivery" policy.
In the QP/C++ Framework component, as in any event-driven system, events are frequently passed from producers to consumers. The exchanged event instances can be either immutable or mutable.
Immutable events are event instances that never change at runtime. Such immutable events can be pre-allocated statically (typically and preferably in ROM) and can be shared safely among any number of concurrent entities (Active Objects, ISRs, "naked" threads, etc.) rather than being created and recycled dynamically every time. QP/C++ Framework component does not need to manage memory for immutable events, but needs to clearly distinguish them from mutable events, precisely to avoid any memory management for them.
Many event instances, especially events with parameters, cannot be easily made immutable because their primary function is specifically to deliver information produced at runtime. Consequently, such mutable events must be dynamically created, filled with information (mutated), passed around, and eventually recycled. The management of these processes at runtime is one of the most valuable services that QP/C++ Framework component can provide to QP/C++ Application.
The main challenge of managing mutable events is to guarantee that once a mutable event gets posted or published (which might involve event multicasting), it does not change and does not get recycled until all Active Objects have finished their Run-to-Completion processing of that event. Changing or prematurely recycling the current event constitutes a violation of the RTC semantics.
Every dynamically created mutable event must be eventually recycled, or the memory would leak. Some event-driven systems leave the event recycling to the application, but in the safety-related context, this is considered unreliable and unsafe. Therefore, the event memory management in the QP/C++ Framework component must also include automatic event recycling.
From the safety point of view, the ideal would be to copy entire mutable events into and out of the event queues, as it is often done with the message queues of a traditional RTOS. Unfortunately, it is prohibitively expensive in RAM and nondeterministic in CPU cycles for larger event instances (events with large parameters). However, an event-driven framework, like QP, can be far more sophisticated than a traditional RTOS because, due to inversion of control, the framework manages an event's whole life cycle. The framework extracts an event from the Active Object's event queue and dispatches it for processing. After the Run-to-Completion processing, the framework regains control of the event and can automatically recycle the event.
An event-driven framework can also easily control the dynamic allocation of mutable events (e.g., the QP/C++ Framework component provides an API for this purpose). All this permits the framework to implement controlled, concurrency-safe sharing of mutable events, which, from the application standpoint, is almost indistinguishable from copying entire events. Such event management is called zero-copy event management.
The whole event memory management must also carefully avoid concurrency hazards around the shared mutable events. Failure in any of those aspects results in defects (bugs) that are the hardest to detect, isolate, and fix.
To manage the memory for mutable events, QP/C++ Framework component needs a deterministic, efficient, and concurrency-safe method of dynamically allocating and recycling the event memory. The general-purpose, variable-block-size heap does not fit this bill and is inappropriate for safety-related applications anyway. However, simpler, higher-performance, and safer options exist to the general-purpose heap. A well-known alternative, commonly supported by RTOSs, is a fixed-block-size heap, also known as a memory partition or memory pool. Memory pools are a much better choice for a real-time event framework like QP to manage mutable event memory than the general-purpose heap. Unlike the conventional (variable-block-size) heap, a memory pool is deterministic, has guaranteed capacity, and is not subject to fragmentation because all blocks are precisely the same size.
The most obvious drawback of a memory pool is that it does not support variable-sized blocks. Consequently, the blocks have to be oversized to handle the largest possible allocation. Such a policy is often too wasteful if the actual sizes of allocated objects (mutable events, in this case) vary a lot. A good compromise is often to use not one but multiple memory pools with memory blocks of different sizes. QP/C++ Framework component chooses that option to implement event pools, which are numerous memory pools specialized to hold mutable events.
Time management available in a traditional RTOS includes delaying a calling thread by timed blocking (delay()) or blocking with a timeout on various kernel objects (e.g., semaphores or event flags). These blocking mechanisms are not applicable in Active Object-based systems where blocking is not allowed. Instead, to be compatible with the Active Object model of computation, time management must be based on the event-driven paradigm in which every relevant occurrence for the system manifests itself as an event instance.
An event-driven framework like QP needs an event-driven time management mechanism based on Time Events (sometimes called timers). A Time Event is a UML term and denotes a point in time (at the specified time, the event occurs [UML 2.5]). A Time Event is said to be armed when it is actively timing out towards the specified time in the future. When the specified time arrives, the Time Event expires and the QP/C++ Framework component directly posts the Time Event to the event queue of the recipient Active Object. An expired Time Event armed initially for one-shot gets automatically disarmed. A Time Event armed for periodic expiration gets automatically re-armed to expire again in the specified time interval in the future. A disarmed Time Event is dormant and must be explicitly armed to time out in the future.
Most real-time systems, including traditional RTOSes and Active Object Frameworks like QP, require a periodic time source called the System Clock Tick to keep track of time delays, timeouts, and armed Time Events in case of the event-driven QP/C++ Framework component. The System Clock Tick must call a dedicated service in the QP/C++ Framework component to periodically update all armed Time Events.
The System Clock Tick is typically a periodic interrupt (asynchronous with respect to the baseline code execution) that occurs at a predetermined rate, typically between 10Hz and 1000Hz. This rate establishes the basic time units as "clock ticks" and the resolution of Time Events as an integer number of "clock ticks". The faster the tick rate, the finer the granularity of "clock ticks" and higher resolution of Time Events, but also the more overhead the time management implies.
Even though the resolution of Time Events is one "clock tick", it does not mean that the accuracy is also one "clock tick". Figure SRS-TE-JIT shows in a somewhat exaggerated manner that the Time Event delivery and eventual handling are always subject to jitter. The primary sources of this jitter are the following variable delays:
[1] Delay caused by the varying length of processing inside the System Clock Tick ISR
[2] Delay caused by the varying length of processing inside the higher-priority Active Objects or other "naked" threads in the system (such processing might also be triggered by the system Clock Tick ISR)
[3] Delay caused by the varying length of processing inside the recipient Active Object.
Generally, the jitter in Time Event processing gets worse as the priority of the recipient Active Object gets lower. In heavily loaded systems, the jitter might even exceed one "clock tick" period. In particular, a Time Event armed for just one tick might expire almost immediately because the System Clock Tick is asynchronous concerning Active Object execution. To guarantee at least one "clock tick" timeout, you need to arm a Time Event for two clock ticks. Note too that Time Events are generally not lost due to event queuing. This is in contrast to clock ticks of a traditional RTOS, which can be lost during periods of heavy loading.
Time management has a significant impact on the power efficiency of the system. Specifically, the need to periodically service Time Events (or various timeouts in a traditional RTOS kernel) has the unfortunate side effect of constantly interrupting the CPU, which means that the CPU can spend less time in the low-power sleep mode.
While a fixed System Clock Tick is very convenient, it often interrupts the CPU regardless of whether real work needs to be done or not. To mitigate that problem, some real-time kernels use the low-power optimization called the "Tickless Mode" (a.k.a. "tick suppression" or "dynamic tick"). In this mode, instead of indiscriminately making the System Clock Tick expire with a fixed period, the kernel adjusts the clock ticks dynamically, as needed. Specifically, after each clock tick, the kernel recalculates the time for the next clock tick and then sets the clock tick interrupt for the earliest timeout it has to wait for. For example, if the shortest timeout the kernel has to attend to is 300 milliseconds in the future, then the clock interrupt will be set for 300 milliseconds.
This approach maximizes the amount of time the CPU can remain asleep. Still, it requires the kernel to perform the additional work to calculate the dynamic tick intervals and to program them into the hardware. This additional bookkeeping adds complexity to the kernel, might be an extra source of jitter, and, most importantly, extends the time CPU spends in the high-power active mode and thus eliminates some of the power gains the "Tickless Mode" was supposed to bring.
Also, the "Tickless Mode" requires a more capable hardware timer that must be able to be reprogrammed for every interrupt in a wide dynamic range and also must accurately keep track of the elapsed time to correct for the irregular (dynamic) tick intervals. Still, even with various precautions and corrections, "Tickless Mode" often causes a drift in the timing of the clock tick.
For the reasons just described, the QP/C++ Framework component does not support "Tickless Mode". Instead, the QP/C++ Framework component supports multiple clock tick rates as an alternative way of achieving similar goals (to avoid interrupting the CPU at a higher rate than necessary.)
Support for multiple tick rates means that each Time Event instance in QP is associated with a particular clock tick rate. For example, the TimeEvt0 instance might be related to a rate #0 of only 10Hz, while the TimeEvt1 instance might be associated with a rate #1 of 1000Hz. The higher tick rate #1 is needed only occasionally (only in specific modes of the system), which means that TimeEvt1 is armed only during these periods and otherwise is disarmed. This provides an opportunity to shut down the high tick rate #1 of 1000Hz when it is not needed, and the QP/C++ Framework component provides a method for finding out when there are no armed Time Events for any given rate. The high tick rate #1 can be restarted only when some Time Events (like TimeEvt1) get armed again. In an extreme case, a system can shut down all clock tick rates until some external event (typically an interrupt) wakes the system up.
"Shutting down" a clock rate might be implemented in various ways. For example, a hardware timer that generates an interrupt at that rate can be turned off. But it is also possible to create multiple tick rates from one hardware timer. In that case, shutting down a clock rate might mean reprogramming that timer to generate interrupts at a different period. All of this is under the control of the QP/C++ Application.
From the point of view of the QP/C++ Framework component, the support for multiple static clock tick rates is significantly simpler than the "Tickless Mode", and essentially does not increase the complexity of the framework because the same code for the single tick rate can handle other tick rates the same way. Also, multiple static tick rates require much simpler hardware timers, which can be explicitly clocked to the desired tick rate and don't need extensive dynamic range. For example, 16-bit timers or even 8-bit timers with or without prescalers are entirely adequate. Yet the multiple clock rates can deliver similar low-power performance for the system, while keeping the QP/C++ Framework component much simpler and easier to certify than "Tickless" Kernels.
In any real-life project, getting the code written, compiled, and successfully linked is only the first step. The system still needs to be tested, validated, and tuned for best performance and resource consumption. A single-step debugger is frequently not helpful because it stops the system and hinders seeing live interactions within the application. Clogging up high-performance code with printf() statements is usually too intrusive and simply unworkable in most embedded systems. So the questions are: How can you monitor the behavior of a running real-time system without degrading the system itself? How can you discover and document elusive, intermittent bugs that are caused by subtle interactions among concurrent components? How do you design and execute repeatable unit and integration tests of your system? How do you ensure that a system runs reliably for long periods of time and gets top processor performance? Techniques based on Software Tracing can answer many of these questions.
Software Tracing is a method for obtaining diagnostic information in a live environment without the need to stop or even significantly slow down the application to get the system feedback. Software Tracing always involves some form of a target system instrumentation to log the relevant discrete occurrences inside the target for subsequent retrieval from the target to the host computer and analysis. An example of Software Tracing is sprinkling the code with printf() statements, which are a crude tracing instrumentation in this case. Of course, a professional Software Tracing system can be far less intrusive and more powerful than the primitive printf().
The Figure SRS-QS-SET below shows a typical setup for Software Tracing, which always consists of two components:
Software Tracing is particularly effective and powerful in combination with the event-driven Active Object model of computation. Due to the inversion of control, a running application built of Active Objects is a highly structured affair where all meaningful system interactions funnel through the underlying event-driven framework. This arrangement offers a unique opportunity for applying Software Tracing in a framework like QP.
Tracing instrumentation inside just the QP/C++ Framework component provides an unprecedented wealth of information about the running system, far more detailed and comprehensive than any traditional RTOS can provide (because RTOS is not based on control inversion.) The Software Trace data from the framework alone can produce:
[1] detailed state machine activity in all Active Objects and other state machines in the system.
[2] detailed information about event posting/publishing, queuing, and recycling. This also includes complete, time-stamped sequence diagrams.
[3] detailed information about real-time kernel activity, like kernel objects, context switches, scheduler, etc.
[4] custom application-specific trace records
This ability can form the foundation of the whole testing strategy for the QP/C++ Application. In addition, individual Active Objects are natural entities for unit testing, which you can perform simply by injecting events into the Active Objects and collecting the generated execution trace. Software Tracing at the framework level makes all this comprehensive information available to the application developers, even with no instrumentation added to the application-level code.
QP/Spy is a Software Tracing and testing system specifically designed for and embedded in the QP/C++ Framework component. As shown in Figure SRS-QS-STR, QP/Spy consists of the following components:
The QS target-resident component inserts trace records into the QS-TX RAM buffer using a binary data protocol. The QP/Spy protocol must be lightweight, but must support delimited frames, as well as provisions to check data continuity and integrity of the frames. These features are necessary to allow flexible removal of data from the RAM buffer in any chunks, typically not aligned with the frame boundaries. Finally, the data transmitted from the target with the QS data protocol must also allow the host to instantaneously re-synchronize after any buffering or transmission error to minimize loss of valuable data.
To minimize the intrusiveness of tracing, the QS target-resident component must perform efficient, selective logging of trace records using as few processing and memory resources of the target as possible. Selective logging means that the tracing system provides user-definable, fine-granularity filters so that the QS target-resident component only collects trace records of interest, and you can filter out as many or as few instrumented trace records as you need.
QP/C++ Framework component contains the tracing instrumentation for pre-defined trace records, such as state machine activity (dispatching events, entering/exiting a state, executing transitions, etc.), Active Object activity (allocating events, posting/publishing events, time events, etc.), and more. These QS records have a predefined (hard-coded) structure both in the QS target-resident component and in the QSPY host-based application.
In addition to the predefined QS records, QP/C++ Application can add its own, flexible, application-specific trace records, whose structure is not known in advance to the QSPY host-resident component. Application-specific trace records carry the format information in them.
Every Software Tracing system, just like every single-step debugger, needs the symbolic information, such as the names of various objects, names of functions, and symbolic names of event signals. This is because by the time the source code is compiled and loaded into the target, the symbolic information is stripped. Therefore, the symbolic information must be somehow provided to the QSPY host-resident component, so that it can associate the symbolic names with binary addresses and other binary information received from the target and then display the symbolic names in the human-readable trace. Various Software Tracing systems approach this problem differently.
The QS target-resident component provides special dictionary trace records designed expressly for providing the symbolic information about the target code in the trace itself. These "dictionary records" provide mapping between the unique object or function addresses in the target memory and the corresponding symbolic names from the source code. The dictionary trace records are typically generated during the system initialization, and this is the only time they are sent to the QSPY host component. Generating the "dictionaries" is the responsibility of the QP/C++ Application.
The QS target-resident component can also implement a receive-channel (QS-RX), which allows receiving, parsing, and executing commands from the QSPY host application. Such a QS-RX channel can be the backbone for interacting with the target system and implementing such features as unit testing and monitoring of the target system.
Finally, the QS target-resident tracing component must allow consolidating data from all parts of the system, including concurrently executing Active Objects, "naked" threads (if used), and interrupts. This means that the QS API must be reentrant (i.e., both thread-safe and interrupt-safe).
The Active Object model of computation can work with a wide range of real-time kernels. Specifically for the kernel discussed in this section, an Active Object requires an execution context only during the RTC (Run-to-Completion) processing and an Active Object that is merely waiting for events does not need an execution context at all. This opens up the possibility of executing multiple Active Objects in a single thread (e.g., the main() function in C or C++).
QV is a simple non-preemptive, cooperative, fixed-priority, event-driven kernel integrated with the QP/C++ Framework component. As shown in Figure SRS-QV-LOOP, QV executes all Active Objects in the system in a single loop (similar to the traditional "superloop", a.k.a. "main+ISRs" architecture), so Active Objects cannot preempt each other (non-preemptive kernel). The QV priority-based scheduler engages only at the top of the loop and selects the highest-priority Active Object ready to run (with some event(s) in its queue). When such an Active Object is found, QV executes the RTC step in this Active Object and then loops back. That way, Active Objects cooperate to share a single "superloop" and implicitly yield to each other after every RTC step. When the QV scheduler finds no Active Objects ready to run, it invokes the idle processing.
As described in the Shared-Nothing Principle for Active Objects, QP/C++ Applications should generally strive to avoid any sharing of resources among Active Objects. However, the simplistic and non-preemptive nature of the QV kernel allows applications to relax the "shared-nothing" principle and safely share some resources among Active Objects.
The situation when QV scheduler finds no events for processing in a given pass through the "superloop" is called the idle condition. In that case, the QV kernel executes idle processing to let the application, among others, put the CPU and peripherals in a low-power sleep mode (see Figure SRS-QV-IDL). Existence of such a single point to apply low-power modes is a hallmark of a power-friendly architecture.
However, as in the traditional "superloop" (a.k.a., "foreground/background" architecture) QV kernel must detect the idle condition inside a critical section (with interrupts disabled) and must be careful to enter the low-power mode safely without re-enabling interrupts too soon (see [Samek:07]). Otherwise, any interrupt allowed after determining the idle condition but before calling the idle processing could post events to Active Objects, thus invalidating the idle condition. However, due to the simplistic, non-preemptive nature of the QV kernel, the idle processing would still be called and would enter the sleep mode. At the same time, some events might be available and waiting (indefinitely) for processing.
The maximum time an event for the highest-priority Active Object can be delayed is called the task-level response. The task-level response in the QV kernel is equal to the longest RTC step of all Active Objects in the system. Note that this task-level response is still a lot better than the traditional "superloop" (a.k.a. main+ISRs) architecture, where the task-level response is typically the sum of the worst-case execution times of all tasks in the "superloop".
Due to the non-blocking nature of event processing inside Active Objects, the RTC steps tend to be short (typically microseconds), which can deliver adequate real-time performance to a surprisingly wide range of applications. Also, the task-level response can often be improved by breaking up the longest RTC steps into shorter pieces (multi-stage processing). For example, an Active Object can perform only a fraction of the overall event processing and post an event to itself to trigger continuation next time ("Reminder" state pattern).
The Active Object model of computation can work with a wide range of real-time kernels. Specifically for the kernel discussed in this section, the non-blocking and run-to-completion characteristics of the Active Object model open up a possibility of using a non-blocking, run-to-completion kernel. Such a kernel can be preemptive and fully compatible with the requirements of Rate Monotonic Scheduling/Analysis (RMS/RMA) method [RMS/RMA:91]. Still, a non-blocking kernel is much simpler and significantly more efficient than any traditional blocking RTOS kernel.
QK is a preemptive, non-blocking, fixed-priority, run-to-completion, single-stack, event-driven kernel integrated with the QP/C++ Framework component. QK executes all Active Objects in discrete, one-shot, non-blocking RTC steps that can preempt each other. This preemption is similar to how prioritized interrupts can preempt each other and nest on a single stack (e.g., see description of interrupt handling in ARM Cortex-M [Yiu:14]). Interrupts, just like RTC steps in Active Objects, are also one-shot, run-to-completion steps that are not allowed to block.
As a fully preemptive, fixed-priority kernel, QK must ensure that at all times the CPU executes the highest-priority Active Object (AO) as soon as it becomes ready to run. Fortunately, only two scenarios can lead to preemption of a lower-priority AO1 by a higher-priority AO2.
Synchronous Preemption
When a lower-priority AO1 posts an event to a higher-priority AO2, the QK kernel must immediately suspend the execution of the lower-priority AO1 and start the higher-priority AO2. This type of preemption is called synchronous preemption because it happens synchronously with posting an event to the AO2's event queue.
Figure SRS-QK-SYN illustrates a synchronous preemption scenario:
[1] QK idle loop (QK idle task) is preempted by an AO1, which executes its RTC step
[2] AO1 posts an event to a higher-priority AO2, which calls the "QK activator"
[3] "QK activator" activates (calls) the AO2 RTC step
[4] AO2 RTC step completes and returns to the "QK activator."
[5] "QK activator" returns back to AO1, which remained synchronously preempted
[6] AO1 completes its RTC step and returns to "QK activator" (previous instance)
[7] "QK activator" finds no more AOs to run and returns to the QK idle loop.
Asynchronous Preemption
When an interrupt posts an event to a higher-priority AO2 than the interrupted AO1, upon completion of the ISR, the QK kernel must start execution of the higher-priority AO2 instead of resuming the lower-priority AO1. This type of preemption is called asynchronous preemption because it can happen asynchronously, any time interrupts are not explicitly disabled.
Figure SRS-QK-ASN illustrates an asynchronous preemption scenario:
[1] QK idle loop (QK idle task) is preempted by an AO1, which executes its RTC step
[2] An interrupt fires and asynchronously preempts the AO1 RTC step
[3] The ISR for the interrupt starts running and posts an event to the high-priority AO2
[4] The ISR sends the EOI (End-of-Interrupt) command to the interrupt-controller, but does NOT return to the preempted context (so the interrupt stack frame remains on the stack). Instead, the ISR calls "QK activator".
[5] "QK activator" activates (calls) the AO2 RTC step
[6] AO2 RTC step completes and returns to the "QK activator."
[7] "QK activator" performs interrupt-return back to AO1, which remained asynchronously preempted
[8] AO1 completes its RTC step and returns to "QK activator" (previous instance)
[9] "QK activator" finds no more AOs to run and returns to the QK idle loop.
By requiring that all AOs run-to-completion and enforcing fixed-priority scheduling, a non-blocking kernel like QK can manage all context information using only a single stack and the CPU's natural stack protocol. Whenever an AO posts an event to a higher-priority AO, the QK kernel uses a regular C function call to build the higher-priority AO context on top of the existing stack context (synchronous preemption). Whenever an interrupt preempts an AO and the interrupt posts an event to a higher-priority AO, the QK kernel uses the already established interrupt stack frame on top of which to build the higher-priority AO context, again using a regular C function call (asynchronous preemption).
This simple form of context management is adequate because every AO, just like every ISR, runs to completion. Because the preempting AO must also run to completion, the lower-priority context will never be needed until the preempting AO (and any higher-priority AO that might preempt it) has completed and returned. At that time, the preempted AO will, naturally, be at the top of the stack, ready to be resumed.
The situation when the QK kernel finishes processing all RTC steps in all Active Objects is called the idle condition. In that case, the QK kernel executes idle processing. Idle processing in QK can be viewed as the lowest-priority task (of priority 0), but unlike all other one-shot tasks, it has a structure of an endless loop (see "QK idle loop" in Figure SRS-QK-SYN and Figure SRS-QK-ASN).
This QK idle loop invokes a QK-idle-callback defined in the application, to let the application, among others, put the CPU and peripherals in a low-power sleep mode. Existence of such a single point to apply low-power modes is a hallmark of a power-friendly architecture.
As all preemptive kernels, QK requires the QP/C++ Application to be cautious with any resource sharing among Active Objects. Ideally, the Active Objects should communicate exclusively via events and otherwise should not share any resources. However, at the cost of increased coupling among Active Objects, the QP/C++ Application might choose to share selected resources. However, such QP/C++ Application takes the burden on itself to apply a mutual exclusion mechanism while accessing any shared resources.
QK kernel provides selective scheduler locking as a powerful mutual exclusion mechanism. Specifically, before accessing a shared resource, an Active Object can lock the QK scheduler up to the specified priority ceiling. This prevents Active Object preemption up to the specified priority ceiling, while not affecting Active Objects (or interrupts) of priority higher than the priority ceiling. After accessing the shared resource, the Active Object must unlock the QK scheduler. Selective scheduler locking in QK is related to IPCP/SRP (Immediate Priority Ceiling Protocol/Stack Resource Policy) and is immune to unbound priority inversion [SRP:90].
Selective scheduling locking is a non-blocking mechanism. If an Active Object that needs to protect a shared resource is running, it means that all Active Objects of higher priority have no events to process. Consequently, simply preventing activation of higher-priority AOs that might access the resource is sufficient to guarantee the mutually exclusive access to the resource. Of course, you don't need to worry about any lower-priority AOs that might be preempted because they never resume until the current AO runs to completion.
Selective scheduler lock requests made by the same Active Object can nest. The nested lock requests can only increase the priority ceiling. Also, the nested lock requests must unlock the scheduler by restoring the previous priority ceiling.
While preemption is a desirable property that enables techniques like RMS/RMA by decoupling higher-priority Active Objects from lower-priority ones in the time domain, too much preemption also has adverse effects. These include the overhead of preemption and restrictions on sharing resources. For example, sometimes a group of Active Objects forms a cohesive subsystem, where preemption of one group member by another might be unnecessary and undesirable.
To ease some of the inherent problems of preemption, QK provides an advanced feature called preemption threshold scheduling (PTS), [PTS:07]. PTS allows an Active Object to specify a preemption threshold to selectively restrict preemption by other Active Objects. Active Objects that have priorities higher than the preemption threshold are still allowed to preempt, while those with priorities less than the threshold are not allowed to preempt.
For example, all Active Objects in a group might specify the same preemption threshold (alongside their unique priorities). Such a preemption threshold will prevent preemption within the group, while still allowing preemption by other Active Objects with higher priorities than the preemption threshold.
The maximum time an event for the highest-priority Active Object can be delayed is called the task-level response. The preemptive QK kernel always executes the highest-priority Active Object immediately as it becomes ready to run (see Preemptions in QK). Therefore, the task-level response in the QK kernel is determined only by the context switch time, which is independent of the lower-priority Active Objects. That is what is meant by a preemptive kernel, which decouples tasks in the time domain.
As a preemptive kernel with fixed-priority scheduling, QK fulfills all requirements of the Rate Monotonic Scheduling/Analysis (RMS/RMA) [RMS/RMA:91] and the related Deadline-Monotonic Scheduling (DMS) [RMS/RMA:91][DMS:91]. Additionally, the no-blocking nature of QK makes the applications easier to analyze and thus actually even more suitable for RMS/RMA than a traditional blocking RTOS.
The Active Object model of computation can work with a wide range of real-time kernels. Among others, event-driven Active Objects can be executed by a traditional, blocking RTOS kernel, where each Active Object runs in its own RTOS thread structured as an event-loop. However, using a conventional, blocking RTOS to execute non-blocking Active Objects is wasteful. As demonstrated in the QK Preemptive Non-Blocking Kernel, non-blocking Active Objects can be executed more efficiently as one-shot, run-to-completion steps.
QXK is a preemptive, fixed-priority, dual-mode (blocking / non-blocking) kernel that executes Active Objects like the QK kernel (basic tasks), but can also execute traditional blocking threads (extended tasks). In this respect, QXK behaves like a conventional RTOS.
QXK has been explicitly designed for combining event-driven Active Objects with traditional code that requires blocking, such as commercial middleware (TCP/IP stacks, UDP stacks, embedded file systems, etc.) or legacy software. To this end, QXK is not only more efficient than running QP on top of a traditional 3rd-party RTOS (because non-blocking basic tasks take less stack space and CPU cycles for context switch than the much heavier extended tasks). But the most significant advantage of QXK is that it protects the application-level code from inadvertent mixing of blocking calls inside the event-driven Active Objects. Specifically, QXK "knows" the type of the task context (extended/basic) and asserts internally if a blocking call (e.g., semaphore-wait or a time-delay) is attempted in a basic task (Active Object).
Basic tasks are one-shot, non-blocking, run-to-completion activations. The basic task can nest on the same stack. Also, context switching from a basic-task to another basic-task requires only activation of the basic-task, which is simpler and faster than full context-switch required for extended-tasks (that QXK also supports, see below).
Extended tasks are endless loops allowed to block. Extended tasks require private per-task stacks, as in conventional RTOS kernels. Any switching from a basic-to-extended task or an extended-to-extended task requires a complete context switch.
QXK provides most blocking mechanisms found in traditional blocking RTOS kernels:
As all preemptive kernels, QXK requires the QP/C++ Application to be cautious with any resource sharing among Active Objects. Ideally, the Active Objects should communicate exclusively via events and otherwise should not share any resources. However, at the cost of increased coupling among Active Objects, the QP/C++ Application might choose to share selected resources. However, such QP/C++ Application takes the burden on itself to apply a mutual exclusion mechanism while accessing any shared resources.
QXK kernel provides selective scheduler locking as a powerful mutual exclusion mechanism. Specifically, before accessing a shared resource, an Active Object can lock the QXK scheduler up to the specified priority ceiling. This prevents Active Object preemption up to the specified priority ceiling, while not affecting Active Objects (or interrupts) of priority higher than the priority ceiling. After accessing the shared resource, the Active Object must unlock the QXK scheduler.
Selective scheduling locking is a non-blocking mechanism. If an Active Object that needs to protect a shared resource is running, it means that all Active Objects of higher priority have no events to process. Consequently, simply preventing activation of higher-priority AOs that might access the resource is sufficient to guarantee the mutually exclusive access to the resource. Of course, you don't need to worry about any lower-priority AOs that might be preempted because they never resume until the current AO runs to completion.
Selective scheduler lock requests made by the same Active Object can nest. The nested lock requests can only increase the priority ceiling. Also, the nested lock requests must unlock the scheduler by restoring the previous priority ceiling.
As a fully preemptive, fixed-priority kernel, QXK always executes the highest-priority task that is ready to run (is not blocked). The scheduling algorithm used in QXK meets all the requirements of the Rate Monotonic Scheduling (a.k.a. Rate Monotonic Analysis, RMA) and can be used in hard real-time systems.
