A traditional sequential program controls the CPU at all times.² Except when the CPU processes asynchronous interrupts, but the interrupts always return control to the point of preemption. Functions called directly or indirectly from the main program issue requests for external input and then wait for it; when input arrives, control resumes within the function that made the call. The location of the program counter, the tree of function calls on the stack, and local stack variables define the program state at any given time.

In the embedded space, the traditional sequential system corresponds to the background loop in the simple foreground/background architecture (a.k.a. super-loop or main+ISRs). As the name suggests, the foreground/background architecture consists of two main parts: the interrupt service routines (ISRs) that handle external interrupts in a timely fashion (foreground) and an infinite main loop that calls various functions (background). Figure 6.1 shows a typical flow of control within a background loop. This particular example depicts the control flow in the Quickstart application described in Section 1.9 in Chapter 1. The dashed boxes represent function calls. The heavy lines indicate the most frequently executed paths through the code.

Figure 6.1. Flow of control in a typical background loop. The heavy lines indicate the most frequently executed paths through the code.

The major advantage of the traditional sequential control is that it closely matches the way the conventional procedural languages work. C and C++, for example, are exactly designed to represent the flow of control in the rich set of control statements, function call tree, and local stack variables. The main disadvantage is that a sequential system is unresponsive while waiting, which is actually most of the time. Asynchronous events cannot be easily handled within the background loop because the loop must explicitly poll for inputs. Flexible control systems, communication software, or user interfaces are hard to build using this style [Rumbaugh+ 91].

Due to the explicit polling for events scattered throughout the background code, the traditional sequential architecture is not compatible with the event-driven paradigm. However, it can be adapted to implement a single event-loop, as described in Section 6.2.3. The simple sequential control flow is also an important stepping stone for understanding other, more advanced CPU management policies.

Multitasking is the process of scheduling and switching the CPU among several sequential programs called tasks or threads. Multitasking is like foreground/background with multiple backgrounds [Labrosse 02]. Tasks share the same address space³ By sharing a common address space, tasks (threads) are much lighter than heavyweight processes, which execute in separate address spaces and contain one or more lightweight threads. and, just like the backgrounds, are typically structured as endless loops. In a multitasking system, control resides concurrently in all the tasks comprising the application.

A specific software component of a multitasking system, called the kernel, is responsible for managing the tasks in such a way as to create an illusion that each task has a dedicated CPU all to itself, even though the computer has typically only one CPU. The kernel achieves this by frequently switching the CPU from one task to the next in the process called context switching. As shown in Figure 6.2, each task is assigned its own stack area in memory and its own data structure, called a task control block (TCB). Context switching consists of saving the CPU registers into the current task's stack and restoring the registers from the next task's stack. Some additional bookkeeping information is also updated in the TCBs. Context switches are generally transparent to the tasks and are activated from asynchronous interrupts (in case of a preemptive kernel) as well as synchronously from explicit calls to the kernel.

Figure 6.2. Multiple tasks with per-task stacks and task control blocks (TCBs).

The multitasking kernel works hard behind the scenes to preserve the same state for each task as the state maintained automatically by a simple sequential program. As you can see in Figure 6.2, for each task the context-switching mechanism preserves the CPU registers, including the program counter as well as the whole private stack with the tree of nested function calls and local stack variables.

A big advantage of multitasking is better CPU utilization because when some tasks are waiting for events, other tasks can continue execution, so fewer CPU cycles are wasted on polling for events. The kernel enables the efficient waiting for events by providing special mechanisms for blocking tasks, such as semaphores, event flags, message mailboxes, message queues, timed blocking, and many others. A blocked task is simply switched away to memory and does not consume any CPU cycles.

Multiple tasks can wait on multiple events in parallel, so a multitasking system as a whole appears to be more responsive than a single background loop. The responsiveness of the system depends on how a kernel determines which task to run next. Understanding of these mechanisms is important for any real-time system, including a real-time framework.

Most kernels allow assigning static priorities to tasks according to their urgency. Figure 6.3 shows execution profiles of the two most popular priority-based kernel types. Panel (A) shows a nonpreemptive kernel that gets control only through explicit calls from the tasks to the kernel. Panel (B) shows a preemptive kernel that additionally gets control upon exit from every ISR. The following explanation section illuminates the interesting points (see also [Labrosse 02]).

Figure 6.3. Execution profiles of a nonpreemptive kernel (A) and a preemptive kernel (B).

The task-level response of a nonpreemptive kernel is nondeterministic because it depends on when other tasks voluntarily call the kernel. In other words, tasks must collaborate to share the CPU. Therefore, this form of multitasking is called cooperative multitasking. The upside is a much easer sharing of resources among the tasks. The kernel has an opportunity to perform a context switch only in explicitly known calls to the kernel, so tasks can safely access shared resources between any two kernel calls. In contrast, the execution profile of a preemptive kernel is as follows:

A preemptive kernel can guarantee a deterministic task-level response of the highest-priority tasks because the lower-priority tasks can always be preempted⁴ Using some kernel blocking mechanisms can lead to the situation in which a ready-to-run higher-priority task cannot preempt a lower-priority task. This condition is called priority inversion. and so it does not matter that they even exist. But this determinism comes at a huge price of increased complexity in sharing resources. A preemptive kernel can perform a context switch at any point of the task's code as long as the scheduler is not locked and interrupts are enabled. Any unexpected context switch might lead to corruption of shared memory or other shared resources, and kernels provide a special mechanism (such as mutexes or monitors) to guarantee a mutually exclusive access to shared resources. Unfortunately, programmers typically vastly underestimate the risks and skills needed to use these mechanisms safely and therefore underestimate the true costs of their use.

In summary, perhaps the most important benefit of multitasking is partitioning of the original problem into smaller, more manageable pieces (the tasks). In this respect, multitasking is a very powerful divide-and-conquer strategy. Multitasking kernels carefully preserve the private stack contents of each task so that tasks are as close as possible to simple sequential programs and thus map well to the traditional languages like C or C++.

Ultimately, however, when it comes to handling events, tasks have the same fundamental limitations as the simple sequential programs. A blocked task waiting for an event is unresponsive to all other events. Also, the whole intervening code around a blocking call is typically designed to handle only the one event that it explicitly waits for. To get a picture of what a task control flow might look like, you can simply replace the heavy polling loops in Figure 6.1 with blocking calls. Adding new events to such code is hard and typically requires deep changes to the whole task structure.

Due to the explicit blocking calls scattered throughout the task code, which the kernel encourages by providing a rich assortment of blocking mechanisms, the traditional multitasking architecture is not compatible with the event-driven paradigm. However, it can be adapted (actually simplified) for executing concurrent active objects, as I describe in the upcoming Section 6.3. Especially valuable in this respect is the thread-safe intertask communication mechanism based on message queues that most kernels or RTOSs provide. Message queues can typically be easily customized for sending events to active objects.

A traditional event-driven system is clearly divided into the event-driven infrastructure and the application (see Figure 6.4). The event-driven infrastructure consists of an event loop, an event dispatcher, and an event queue. The application consists of event-handler functions that all share common data.

Figure 6.4. Traditional event-driven system with event loop and a single event queue.

All events in the system originating from asynchronous interrupts or from the event-handler functions are always inserted first into the event queue. The control resides within the event dispatcher that polls the event queue in the infinite event loop. For every event extracted from the queue the dispatcher calls the event-handler function associated with this event type. All event-handler functions contain essentially linear code that returns to the main event loop as quickly as possible. In particular, the event-handler functions don't poll for events and don't access the event queue. All the polling and event queuing is centralized and encapsulated within the dispatcher.

To keep the system responsive, the dispatcher must be able to check for events continuously and frequently. This implies that the event-handler functions must execute quickly. An errant event-handler function can halt the entire application, so care must be taken to avoid any “blocking” code or simply long-running code. The application cannot preserve its state using the program counter and stack because the stack contents disappear when the event-handler functions return control to the event loop. The application must rely on static variables to maintain state.

The event-loop architecture automatically guarantees that every event-handler function runs to completion, because the dispatcher can dispatch a new event only after the last event-handler function returns to the event loop. The need for an event queue is the direct consequence of the run-to-completion event processing. Queuing prevents losing events that arrive while the event-handler functions are running to completion and the dispatcher is unable to accept new events. The event queue is an essential part of the design.

The traditional event-driven architecture is immensely popular in event-driven graphical user interface (GUI) frameworks such as MFC, OWL, Delphi, Tcl/Tk, X-Windows, SunView, or, more recently, Java/AWT/Swing, ActionScript, Qt, .NET, and many, many others. The countless variations of the technique have mostly to do with the creative ways of associating events with event-handler functions, but all of them are ultimately based on the prevalent event-action paradigm, in which event types are mapped to the code that is supposed to be executed in response.

However, as explained in Chapter 2, the system response to an event depends as much on the event type as on the application context (state) in which the event arrives. The prevalent event-action paradigm recognizes only the dependency on the event type and leaves the handling of the context to largely ad hoc techniques. State machines provide very strong support for handling the context (state), but unfortunately, the event-action paradigm is incompatible with state machines because a single event-handler function contains pieces of many states. (That's exactly why event-handler functions become convoluted and brittle as they grow and evolve.) The complementary relation between the event-action paradigm and state machines is best visible in the state-table representation of a state machine (see Table 3.1 in Chapter 3), in which an event-handler function corresponds to the vertical cut through all the states in the state table along a given event column.

To summarize, the traditional event-driven architecture permits more flexible patterns of control than any sequential system [Rumbaugh+ 91]. Also, compared to any traditional sequential technique, an event-driven scheme uses the CPU more efficiently and tends to consume less stack space, which are all very desirable characteristics for embedded systems. However, the traditional event-driven architecture is not quite suitable for real-time frameworks. The remaining problems are at least threefold:

The event queues, event loops, and the event processor for state machines are all generic and as such are part of a generic real-time framework. The application consists of the specific state machine implementations, which the framework invokes indirectly through the dispatch()⁵ The dispatch() operation is understood here generically and denotes any state machine implementation method, such as any of the techniques described in Chapters 3 or 4. state machine operation.

Figure 6.6 shows the relationship between the application, the real-time framework, and the real-time kernel or RTOS. I use the QF real-time framework as an example, but the general structure is typical for any other framework of this type. The design is layered, with an RTOS at the bottom providing the foundation for multitasking and basic services like message queues and deterministic memory partitions for storing events. Based on these services, the QF real-time framework supplies the QActive class for derivation of active objects. The QActive class in turn derives from the QHsm base class, which means that active objects are state machines and inherit the dispatch() operation defined in the QHsm base class (see Chapter 4). Additionally, QActive contains a thread of execution and an event queue, typically based on the message queue of the underlying RTOS. An application extends the real-time framework by deriving active objects from the QActive base class and deriving events with parameters from the QEvent class.

Figure 6.6. Package diagram illustrating the relationship among the real-time framework, the kernel/RTOS, and the application.

The application uses the QF communication and timing services through the framework API (indicated by the ball-and-socket UML notation); however, the application typically should not need to directly access the RTOS API. Thus, a real-time framework can serve as an RTOS abstraction layer. The framework effectively insulates applications from the underlying RTOS. Changing the RTOS on which the framework is built requires porting the framework but does not affect applications. I'll demonstrate this aspect in Chapter 8, where I discuss porting QF.

As shown in Figure 6.5(A), active objects receive events exclusively through their event queues. All events are delivered 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 system makes no distinction between external events generated from interrupts and internal events originating from active objects. As shown in Figure 6.5(A), an active object can post events to any other active object, including to self. All events are treated uniformly, regardless of their origin.

Each active object processes events in run-to-completion (RTC) fashion, which is guaranteed by the structure of the active object's event loop. As shown in Figure 6.5(B), the dispatch() operation must necessarily complete and return to the event loop before the next event from the queue can be extracted. RTC event processing is the essential requirement for proper execution of state machines.

In the case of active objects, where each object has its own thread of execution, it is very important to clearly distinguish the notion of RTC from the concept of thread 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. Under a preemptive multitasking kernel, an RTC step can be preempted by another thread executing on the same CPU. This is determined by the scheduling policy of the underlying multitasking kernel, not by the active object computing model. When the suspended thread is assigned CPU time again, it resumes its event processing from the point of preemption and, eventually, completes its event processing. As long as the preempting and the preempted threads don't share any resources, there are no concurrency hazards.

Perhaps the most important characteristic of active objects, from which active objects actually derive their name, is their strict encapsulation. Encapsulation means that active objects don't share data or any other resources. Figure 6.5(A) illustrates this aspect by a thick, opaque encapsulation shell around each active object and by showing the internal state machines in gray, since they are really not supposed to be visible from the outside.

As described in the previous section, no sharing of any resources (encapsulation) allows active objects to freely preempt each other without the risk of corrupting memory or other resources. The only allowed means of communication with the external world and among active objects is asynchronous event exchange. The event exchange and queuing are controlled entirely by the real-time framework, perhaps with the help of the underlying multitasking kernel, and are guaranteed to be thread-safe.

Even though encapsulation has been traditionally associated with object-oriented programming (OOP), it actually predates OOP and does not require object-oriented languages or any fancy tools. Encapsulation is not an abstract, theoretical concept but simply a disciplined way of designing systems based on the concept of information hiding. Experienced software developers have learned to be extremely wary of shared (global) data and various mutual exclusion mechanisms (such as semaphores). Instead, they bind the data to the tasks and allow the tasks to communicate only via message passing. For example, the embedded systems veteran, Jack Ganssle, offers the following advice [Ganssle 98].

Although it is certainly true that the operating system mechanisms, such as message queues, critical sections, semaphores, or condition variables, can serve in the construction of a real-time framework, application programmers do not need to directly use these often troublesome mechanisms. Encapsulation lets programmers implement the internal structure of active objects without concern for multitasking. For example, application programmers don't need to know how to correctly use a semaphore or even know what it is. Still, as long as active objects are encapsulated, an active object system can execute safely, taking full advantage of all the benefits of multitasking, such as optimal responsiveness to events and good CPU utilization.

In Chapter 9 I will show you how to organize the application source code so that the internal structure of active objects is hidden and inaccessible to the rest of the application.

Event-driven systems are in general more difficult to implement with standard languages, such as C or C++, than procedure-driven systems [Rumbaugh+ 91]. The main difficulty comes from the fact that an event-driven application must return control after handling each event, so the code is fragmented and expected sequences of events aren't readily visible.

For example, Figure 6.7(A) shows a snippet of a sequential pseudocode, whereas panel (B) shows the corresponding flowchart. The boldface statements in the code and heavy lines in the flowchart represent waiting for events (either polling or efficient blocking). Both the sequential code and the flowchart show the expected sequence of events (A, B…B, C) very clearly. Moreover, the sequential processing allows passing data from one processing stage to the next in temporary stack variables. Traditional programming languages and traditional multitasking kernels strongly support this style of programming that relies heavily on stack-intensive nested function calls and sophisticated flow of control (e.g., loops).

Figure 6.7. Sequential pseudocode (A), flowchart (B), and state machine (C).

In contrast, the traditional event-driven code representing essentially the same behavior consists of three event-handler functions onA(), onB(), and onC(), and it is not at all clear that the expected sequence of calls should be onA(), onB()…onB(), onC(). This information is hidden inside the event-hander functions. Moreover, the functions must use static variables to pass data from one function to the next, because the stack context disappears when each function returns to the event loop. This programming style is harder to implement with standard languages because you get virtually no support for handling the execution context stored in static variables.

And this is where state machines beautifully complement the traditional programming languages. State machines are exactly designed to represent the execution context (state and extended-state variables) in static data. As you can see in Figure 6.7(C), the state machine clearly shows the expected event sequence, so this program structure becomes visible again. But unlike the sequential code, a state machine does not rely on the stack and the program counter to preserve the context from one state to the next. State machines are inherently event-driven.

As opposed to the traditional event-driven architecture, the active object computing model is compatible with state machines. The active object event loop specifically eliminates the event dispatcher (Figure 6.5(B)) because demultiplexing events based on the event signal is not a generic operation but instead always depends on the internal state of an active object. Therefore, event dispatching must be left to the specific active object's state machine.

In the most common implementations of the active object computing model, active objects map to threads of a traditional preemptive RTOS or OS. For example, the real-time framework inside the Telelogic Rhapsody design automation tool provides standard bindings to VxWorks, QNX, and Linux, to name a few [Telelogic 07]. In this standard configuration the active object computing model can take full advantage of the underlying RTOS capabilities. In particular, if the kernel is preemptive, the active object system achieves exactly the same optimal task-level response as traditional tasks.

Consider how the preemptive kernel scenario depicted in Figure 6.3(B) plays out in an active object system. The scenario begins with a low-priority active object executing its RTC step and a high-priority active object efficiently blocked on its empty event queue.

At point (2b) in Figure 6.3(B), an interrupt preempts the low-priority active object. The ISR executes and, among other things, posts an event to the high-priority active object (3b). The preemptive kernel called upon the exit from the ISR (4b) detects that the high-priority active object is ready to run, so it switches context to that active object (5b). The interrupt returns to the high-priority active object that extracts the just-posted event from its queue and processes the event to completion (6b). When the high-priority active object blocks again on its event queue, the kernel notices that the low-priority active object is still preempted. The kernel switches context to the low-priority active object (7b) and lets it run to completion.

Note that even though the high-priority active object preempted the low-priority one in the middle of the event processing, the RTC principle hasn't been violated. The low-priority active object resumed its RTC step exactly at the point of preemption and completed it eventually, before engaging in processing another event.

The active object computing model can also work with nonpreemptive kernels. In fact, one particular cooperative kernel matches the active object computing model exceptionally well and can be implemented in an absolutely portable manner. For lack of a better name, I will call this kernel plain vanilla or just vanilla. I explain first how the vanilla kernel works and later I compare its execution profile with the profile of a traditional nonpreemptive kernel from Figure 6.3(A). Chapter 7 describes the QF implementation of the vanilla kernel.

Figure 6.8 shows the architecture of the simple cooperative vanilla kernel. The most important element of the design is the scheduler, which is the part of a kernel responsible for determining which task to run next. The vanilla scheduler operates in a single loop. The scheduler constantly monitors all event queues of the active objects. Each event queue is assigned a unique priority, which is the priority of the active object that owns this queue. The scheduler always picks the highest-priority not-empty queue.

Figure 6.8. Active object system executing under the cooperative vanilla kernel.

After finding the queue, the vanilla kernel extracts the event from the queue and dispatches it to the active object that owns this queue. Note that the queue get() operation cannot block because at this point the queue is guaranteed to be not empty. Of course, the vanilla kernel applies all the necessary safeguards to protect the internal state of the scheduler and the event queues from corruption by asynchronous interrupts, which can post events to the queues at any time.

The dispatch() operation always runs to completion and returns to the main loop. The scheduler takes over and the cycle repeats. As usual in event-driven systems, the main event loop and the event queues are all part of the vanilla kernel or the framework. The application code is not supposed to poll or block.

The vanilla scheduler very easily detects the condition when all event queues are empty. This situation is called the idle condition of the system. In this case, the scheduler performs idle processing, which can be customized by the application.

Now consider how the scenario depicted in Figure 6.3(A) plays out under the vanilla kernel. The scenario begins with a low-priority active object executing its RTC step (dispatch() function) and a high-priority active object having its event queue empty. At point (2a) an interrupt preempts the low-priority active object. The ISR executes and, among other things, posts an event to the high-priority active object (3a). The interrupt returns and resumes the originally preempted low-priority active object (4a). The low-priority object runs to completion and returns to the main loop. At this point, the vanilla scheduler has a chance to run and picks the highest-priority nonempty queue, which is the queue of the high-priority active object (6a). The vanilla kernel calls the dispatch() function of the high-priority active object, which runs to completion.

As you can see, the task-level response of the vanilla kernel is exactly the same as any other nonpreemptive kernel. Even so, the vanilla kernel achieves this responsiveness without per-task stacks or complex context switching. The active objects naturally collaborate to share the CPU and implicitly yield to each other at the end of every RTC step. The implementation is completely portable and suitable for low-end embedded systems.

Because typically the RTC steps are quite short, the kernel can often achieve adequate task-level response even on a low-end CPU. Due to the simplicity, portability, and minimal overhead, I highly recommend the vanilla kernel as your first choice. Only if this type of kernel cannot meet your timing requirements should you move up to a preemptive kernel.

Finally, if your task-level response requirements mandate a preemptive kernel, you can consider a super-simple, run-to-completion preemptive kernel that matches perfectly the active object computing model [Samek+ 06]. A preemptive RTC kernel implements in software exactly the same deterministic scheduling policy for tasks as most prioritized interrupt controllers implement in hardware for interrupts.

Prioritized interrupt controllers, such as the venerable Intel 8259A, the Motorola 68K and derivatives, the interrupt controllers in ARM-based MCUs by various vendors, the NVIC in the ARMv7 architecture (e.g., Cortex-M3), the M16C from Renesas, and many others allow prioritized nesting of interrupts on a single stack.

In an RTC kernel tasks and interrupts are nearly symmetrical: both tasks and ISRs are one-shot, RTC functions (Figure 6.9(A)). In fact, an RTC kernel views interrupts very much like tasks of “super-high” priority, except that interrupts are prioritized in hardware by the interrupt controller, whereas tasks are prioritized in software by the kernel (Figure 6.9(B)).

Figure 6.9. Systemwide priority of a single-stack kernel (A) and task structure (B).

By requiring that all tasks run to completion and enforcing fixed-priority scheduling, an RTC kernel can use the machine's natural stack protocol. Whenever a task is preempted by a higher-priority task (perhaps as a result of the currently running task posting an event to a higher-priority task), the RTC kernel uses a regular C-function call to build the higher-priority task context on top of the preempted-task stack context. Whenever an interrupt preempts a task, the kernel uses the already established interrupt stack frame on top of which to build the higher-priority task context, again using a regular C-function call. This simple form of context management is adequate because every task, just like every ISR, runs to completion. Because the preempting task must also run to completion, the lower-priority stack context will never be needed until the preempting task (and any higher-priority task that might preempt it) has completed—at which time the preempted task will naturally be at the top of the stack, ready to be resumed. This simple mechanism works for exactly the same reason that a prioritized hardware-interrupt system works [Samek+ 06].

One obvious consequence of the stack-use policy, and the most severe limitation of an RTC kernel, is that tasks cannot block. The kernel cannot leave a high-priority task context on the stack and at the same time resume a lower-priority task. The lower-priority task context simply won't be accessible on top of the stack unless the higher-priority task completes. But as I keep repeating ad nauseam throughout this book, event-driven programming is all about writing nonblocking code. Event-driven active objects don't have a need for blocking.

In exchange for not being able to block, an RTC kernel offers many advantages over traditional blocking kernels. By nesting all task contexts in a single stack, the RTC kernel can be super-simple because it doesn't need to manage multiple stacks and all their associated bookkeeping. The result is not just significantly less RAM required for the stacks and task control blocks but a faster context switch and, overall, less CPU overhead. At the same time, an RTC kernel is as deterministic and responsive as any other fully preemptive priority-based kernel. In Chapter 10, I describe an RTC kernel called QK, which is part of the QP platform. QK is a tiny preemptive, priority-based RTC kernel specifically designed to provide preemptive multitasking support to the QF real-time framework.

If you are using a traditional preemptive kernel or RTOS for executing event-driven systems, chances are that you're overpaying in terms of CPU and memory overhead. You can achieve the same execution profile and determinism with a much simpler RTC kernel. The only real reason for using a traditional RTOS is compatibility with existing software. For example, traditional device drivers, communication stacks (such as TCP/IP, USB, CAN, etc.), and other legacy subsystems are often written with the blocking paradigm. A traditional blocking RTOS can support both active object and traditional blocking code, which the RTOS executes outside the real-time framework.

The simplest mechanism lets producers post events directly to the event queue of the recipient active object. This method requires minimal participation from the framework. The framework merely provides a public operation (a function in the framework API), which allows any producer to post an event directly to the given active object. For example, the QF real-time framework provides the operation QActive_postFIFO(), which is the operation of the QActive class (see Figure 6.6). Of course the framework is responsible for implementing this function in a thread-safe manner. Figure 6.10 illustrates this form of communication as thick, solid arrows 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 ideal in situations where a group of active objects, or an active object and an ISR, form a subsystem delivering 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 intimately “know” the recipients. The “knowledge” that a sender needs is more than merely having a pointer to the recipient active object; the sender must also know the kind of events the particular object might be interested in. This intimate knowledge, distributed among the participating application components, makes the coupling among the components quite strong and inflexible at runtime. For example, it might be difficult to add new active objects to the subsystem, because existing event producers won't know about the newcomers and won't send them events.

The publish–subscribe model is a popular way of decoupling the event producers from the event consumers. Publish-subscribe is a “pull-style” communication mechanism in which recipients receive only solicited events. The properties of the publish-subscribe model are:

The publish-subscribe event delivery is shown in Figure 6.10 as a “software bus” into which active objects “plug in” through the specified interface. Active objects interested in certain events subscribe to one or more event signals by the framework. Event producers make event publication requests to the framework. Such requests can originate asynchronously from many sources, not necessarily just active objects—for example, from interrupts or device drivers. The framework manages all these interactions by supplying the following services:

One obvious implication of publish-subscribe is that the framework must store the subscriber information, whereas it must allow associating more than one subscriber active object with an event signal. The framework must also allow modifying the subscriber information at runtime (dynamic subscribe and unsubscribe). The QF real-time framework supports dynamic subscriptions and cancellations of subscriptions.

Section 4.7.10 offered the general solution, which is to use event queues. Indeed, as shown in Figure 6.11, entire events can be copied into an event queue and then copied out of the queue again before they can be processed. Many RTOSs support this style of event exchange through message queues. For example, the VxWorks RTOS provides functions msgQSend() to copy a chunk of memory (message) into a message queue, and msgQReceive() to copy the entire message out of the queue to the provided memory buffer.

Figure 6.11. Copying entire events into the event queue and out of the event queue.

Copying entire events addresses all the potential problems with corrupting event memory prematurely, but the approach is terribly expensive in both space and time. In terms of space requirements, a message queue must typically be oversized so that all locations in the queue are able to accept the largest expected event. Additionally, every event producer needs an oversized memory buffer and every event consumer needs another oversized buffer to hold copies of the events. In terms of CPU overhead, each event passed through the queue requires making at least two copies of the data (see Figure 6.11). Moreover, the queue is inaccessible while the lengthy copy operations take place, which can negatively impact responsiveness of the system. Of course, the high overheads of copying events only multiply when multicasting events is required.

To mitigate the costs of message queues, some authors advise sending just pointers to larger chunks of data over a message queue and then let the recipient directly access the data via the provided pointer [Li+ 03]. You should be very careful with this approach. Due to the asynchronous nature of a message queue, the sender typically cannot know when the event actually gets processed, and the sender all too easily can prematurely corrupt the memory buffer by trying to reuse it for the next event. This is, of course, the classic concurrency problem caused by a shared memory buffer. Introducing such direct sharing of memory defeats the purpose of the message queue as a safe mechanism for passing messages (events) from producers to consumers.

The brute-force approach of copying entire events into message queues is the best a traditional RTOS can do, because an RTOS does not control the events after they leave the queue. A real-time framework, on the other hand, can be far more efficient because, due to inversion of control, the framework actually manages the whole life cycle of an event.

As shown in Figures 6.5(B), 6.8, and 6.9(A) earlier in this chapter, a real-time framework is in charge of extracting an event from the active object's event queue and then dispatching the event for RTC processing. After the RTC step completes, the framework regains control of the event. At this point, the framework “knows” that the event has been processed and so the framework can automatically recycle the event. Figure 6.12 shows the garbage collection step (event recycling) added to the active object life cycle.

Figure 6.12. Adding garbage collection step to active object thread (A), to the cooperative vanilla kernel (B), and to the one-shot task of an RTC kernel (C).

A real-time framework can also easily control the allocation of events. The framework can simply provide an API function that application code must call to allocate new events. The QF framework, for example, provides the macro Q_NEW() for this purpose.

With the addition of the event creation and automatic garbage collection steps, the framework controls the life cycle of an event from cradle to grave. This in turn permits the framework to implement controlled, thread-safe sharing of event memory, which from the application standpoint is undistinguishable from true event copying. Such memory management is called zero-copy event delivery.

Figure 6.13 illustrates the zero-copy event delivery mechanism. The life cycle of an event begins when the framework allocates the event from an event pool and returns a pointer to this memory to the event producer, such as the ISR in Figure 6.13(1). The producer then fills the event parameters, writing directly to the provided event pointer. Next, the event producer posts just the pointer to the event to the queue of the recipient active object (Figure 6.13(2)).

Figure 6.13. Passing events without copying them (zero-copy event delivery).

At some later time, the active object comes around to process the event. The active object reads the event data via the pointer extracted from the queue. Eventually, the framework automatically recycles the event in the garbage collection step. Note that the event is never copied. At the same time the framework makes sure that the event is not recycled prematurely. Of course, the framework must also guarantee that all these operations are performed in a thread-safe manner.

Not all events in the system have parameters or changing parameters. For example, the TIME_TICK event or the PLAYER_TRIGGER button-press event in the “Fly ‘n’ Shoot” game from Chapter 1 don't really change. Such immutable event objects can be shared safely and can be allocated statically once, rather than being created and recycled every time. Figure 6.13(3) shows an example of a static event that does not come from an event pool.

The “zero-copy” event delivery mechanism can very easily accommodate such static events by simply not managing them at all. All static events must have a unique signature that indicates to the garbage collector to ignore such events. Conversely, events allocated dynamically must have a unique signature identifying them as dynamic events that the framework needs to manage. The applications use static and dynamic events in exactly the same way, except that static events are not allocated dynamically.

In the publish-subscribe mechanism, it is common for multiple active objects to subscribe to the same event signal. A real-time framework is then supposed to multicast identical copies of an event to all registered active objects simultaneously, much as a newspaper publisher sends out identical copies of a newspaper to all subscribers.

Of course, sending multiple identical copies of an event is not compatible with the zero-copy event delivery policy. However, making identical copies of the event is not really necessary because all subscribers can receive pointers to the same event. The problem is rather to know when the last active object has completed processing of a given event so that it can be recycled.

A simple expedient is to use the standard reference-counting algorithm (e.g., see [Preiss 99]), which works in this case as follows: Every dynamic event object maintains internally a counter of outstanding references to this event. The counter starts at zero when the event is created. Each insertion of the event to any event queue increments the reference count by one. Every attempt to garbage-collect the event decrements the reference count by one. The event is recycled only when its reference count drops to zero. Note that the reference counter is not decremented when the event is extracted from a queue but only later, inside the garbage collection step. This is because an event must be considered referenced as long as it is being processed, not just as long as it sits in a queue. Of course, the reference counting should only affect dynamic events and must be performed in a thread-safe manner.

Reference counting allows more complex event exchange patterns than just multicasting. For example, a recipient of an event might choose to post the received event again, perhaps more than once. In any case, the reference-counting algorithm will correctly spare the event from recycling at the end of the first RTC step and will eventually recycle the event only when the last active object has finished processing the event.

The garbage collection step is part of the active object life cycle controlled by the real-time framework (Figure 6.12). The application has typically no need to recycle events explicitly. In fact, some automatic garbage collection systems, most notably Java, don't even expose a public API for recycling individual objects.

However, a real-time framework might decide to provide a way to explicitly garbage-collect an event object, but this is always intended for special purposes. For example, an event producer might start to build a dynamic event but eventually decide to bail out without posting or publishing the event. In this case the event producer must call the garbage collector explicitly to avoid leaking of the event.

The zero-copy event delivery mechanisms are designed to be transparent to the application-level code. Even so, applications must obey certain ownership rules with respect to dynamic events, similar to the rules of working with objects allocated dynamically with malloc() or the C++ operator new.

Figure 6.14 illustrates the concept of event ownership and possible transfers of ownership rights. All dynamic events are initially owned by the framework. An event producer might gain ownership of a new event only by calling the new_() operation. At this point, the producer gains the ownership rights with the permission to write to the event. The event producer might keep the event as long as it needs, but eventually the producer must transfer the ownership back to the framework. Typically the producer posts or publishes the event. As a special case, the producer might decide that the event is not good, in which case the producer must call the garbage collector explicitly. After any of these three operations, the producer loses ownership of the event and can no longer access it.

Figure 6.14. Transferring event ownership during the life cycle of a dynamic event.

The consumer active object gains ownership of the current event ‘e’ when the framework calls the dispatch(e) operation. This time, the active object gains merely the read-only permission to the current event. The consumer active object is also allowed to post or publish the event any number of times. The ownership persists over the entire RTC step. The ownership ends, however, when the dispatch() operation returns to the framework. The active object cannot use the event in any way past the RTC step.

The dynamic, reference-counted events could, in principle, be allocated and freed with the standard malloc() and free() functions, respectively. However, as described in the sidebar “A Heap of Problems,” using the standard heap for frequent allocation and recycling of events causes simply too many problems for any high-performance system.

However, simpler, higher-performance, and safer options exist to the general-purpose, variable-block-size 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 framework to manage dynamic event allocation than the general-purpose heap.

Unlike the conventional (variable-block-size) heap, a memory pool has guaranteed capacity. It is not subject to fragmentation, because all blocks are exactly the same size. Because all blocks have identical size, no header is associated with each block allocated, thus reducing the system overhead per block. Furthermore, allocation through a memory pool can be very fast and completely deterministic. This aspect allows the kernel to protect a memory pool with a critical section of code (briefly disabling interrupts) rather than a mutex. In the case of a memory pool, the access is so fast that interrupts need to be disabled only briefly (no longer than other critical sections in the system), which does not increase interrupt latency and allows access to a memory pool, even from ISRs.

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 biggest possible allocation. Such a policy is often too wasteful if the actual sizes of allocated objects (events, in this case) vary a lot. A good compromise is often to use not one but a few memory pools with blocks of different sizes. The QF real-time framework, for example, can manage up to three event pools with different block sizes (e.g., small, medium, and large, like shirt sizes).

When multiple memory pools are used, each dynamic event object must remember which pool it came from, so that the framework can recycle the event to the same pool. The QF real-time framework combines the pool ID and the reference count into one data member “dynamic_” of the QEvent structure (see Listings 4.2 and 4.3 in Chapter 4).

A real-time framework manages time through time events, often called timers. Time event is a UML term and denotes a point in time. At the specified time, the event occurs [OMG 07]. The basic usage model of these time events is as follows: An active object allocates one or more time event objects (provides the storage for them). When the active object needs to arrange for a timeout, it arms one of its time events to post itself at some time in the future.

Figure 6.15 shows the time event facility in the QF real-time framework. The QTimeEvt class derives from QEvent, which means that time events can be used in all the same contexts as regular events. Time events can be further specialized to add more information (event parameters).

Figure 6.15. QF class QTimeEvt derived from QEvent.

The time event provides public operations for that purpose: postIn() for a one-shot timeout and postEvery() for a periodic timeout event. Each timeout request has a different time event associated with it, so the application can make multiple parallel requests (from the same or different active objects). When the framework detects that the appropriate moment has arrived, the framework posts the requested time event directly into the recipient's event queue (direct event posting). The recipient then processes the time event just like any other event.

The application can explicitly disarm any time event (periodic or one-shot) at any time using the disarm() operation. After disarming (explicitly or implicitly, as in the case of the one-shot time event), the time event can be reused for one-shot or periodic timeouts. In addition, as long as the time event remains armed it can be rearmed with a different number of ticks through the rearm() operation. For one-shot time events, rearming is useful, for example, to implement watchdog timers that need to be periodically “tickled” to prevent them from ever timing out. Rearming might also be useful to adjust the phasing of periodic time events (often you need to extend or shorten one period).

Every real-time system, including traditional blocking kernels, requires a periodic time source called the system clock tick. The system clock tick is typically a periodic interrupt that occurs at a predetermined rate, typically between 10Hz and 100Hz. You can think of the system clock tick as the heartbeat of the system. The actual frequency of the system clock tick depends on the desired tick resolution of your application. The faster the tick rate, the more overhead the time management implies.

The system clock tick must call a special framework function to give the framework a chance to periodically update the armed time events. The QF real-time framework, for example, updates time events in the function QF_tick().

The delivery of time events in a real-time framework is subject to various delays, as is also the case with all real-time kernels or RTOSs [Labrosse 02]. Figure 6.16 shows in a somewhat exaggerated manner the various delays of a periodic time event programmed with one tick interval. As indicated by the varying time intervals in Figure 6.16, the time event delivery is always subject to jitter. The jitter 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.⁸ This might be indicative of incorrect system design. In particular, a time event armed for just one tick might expire immediately because the system clock tick is asynchronous with respect to active object execution. To guarantee at least one 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.

Figure 6.16. Jitter of a periodic time event firing every tick.

The Design by Contract⁹ Design by Contract is a registered trademark of Interactive Software Engineering. (DbC) approach, pioneered by Bertrand Meyer [Meyer 97], provides an excellent methodology for implementing a very robust error-handling policy within a real-time framework that makes the most of the control inversion. The DbC philosophy 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 or C++, the most important aspects of DbC (the contracts) can be implemented with assertions. The standard C-library macro assert() takes a Boolean argument and terminates the application if the argument evaluates to FALSE. A real-time framework can of course use a customized version of the macro, which would invoke an application-specific handler function when the assertion fails (see upcoming Section 6.7.3), but the general idea of asserting certain conditions at runtime is the same.

Assertions built into a real-time framework are consistent with inversion of control because through the assertions a real-time framework can enforce software contracts without relying on the application to check error codes or catch thrown exceptions.

The most important point to realize about software contracts (assertions in C/C++) is that they neither prevent errors nor really handle them, in the same way as contracts between people do not prevent fraud. For example, the QF real-time framework asserts that a published event signal is in the preconfigured range. Naturally, such an assertion neither handles nor prevents the application from publishing an event out of range. However, the assertion establishes a contract, which spells out that an attempt to publish an event out of range is an error. And sure enough, the framework will quite brutally abort the application that violates this contract. At first you might think that this must be backward. Contracts not only do nothing to prevent (let alone handle) errors, but they actually make things worse by turning every asserted condition, however benign, into a fatal error! However, when you really think about it, you must admit that publishing an event out of range is not really all right. It indicates that the application somehow lost consistency of event signals, which is a sure sign of a larger problem (a broken build, perhaps).

The DbC philosophy is the exact opposite of the popular defensive programming strategy, which denotes a programming style that aims at making operations more robust to errors, by accepting a wider range of inputs or allowing order of operations not necessarily consistent with the object's state. Defensive programming is often advertised as a better coding style, but unfortunately, it often hides bugs. To use the same example again, the QF framework could very easily make the publish() operation more “robust” simply by ignoring an event that is out of range. Defensive programming is not necessarily harder to implement than DbC. Rather, the problem with defensive programming is that it allows the code to “wonder around,” silently taking care of various invalid conditions. The DbC approach, in contrast, represents the point of view that either a program is in full control of what's going on or it isn't, whereas assertions define what it means that the program is in control. When any of these safeguards fails, the method prescribes that it is better to face up to the problem as soon as possible and put the system in a fail-safe state (whatever this might mean for a particular system) than to let a runaway program continue. This practice is especially advisable for safety-critical applications such as medical devices.

Due to their simplicity, assertions are sometimes viewed as too primitive error-checking mechanisms—something that's perhaps good enough for smaller programs but must be replaced with a “real” error handling in the industry-strength software. This view is inconsistent with the DbC philosophy, which regards contracts as the integral part of the software design. Software contracts embody important design decisions, namely declaring certain conditions as errors rather than exceptional conditions, and therefore embedding them in large-scale, mission-critical software is even more important than in quick-and-dirty solutions. As Bertrand Meyer [Meyer 97b] observes:

Another critical point to understand about the DbC philosophy is that the purpose of software contracts is to detect errors but not to handle exceptional conditions.

An error (known otherwise as a bug) means a persistent defect due to a design or implementation mistake (e.g., overrunning an array index or dereferencing a NULL pointer). Software contracts (assertions in C/C++) should be used to document such logically impossible situations to discover programming errors. If the “impossible” occurs, something fundamental is clearly wrong and you cannot trust the program anymore.

In contrast to an error, an exceptional condition is a specific circumstance that can legitimately arise during the system lifetime but is relatively rare and lies off the main execution path of your software. You need to design and implement a recovery strategy that handles the exceptional condition.

The distinction between errors and exceptional conditions is important because errors require the exact opposite programming strategy from dealing with exceptional conditions. The first priority in dealing with errors is to detect them as early as possible. Any attempt to handle a bug as an exceptional condition only increases the risks of damage that a runaway program can cause. It also tends to introduce immense complications to the code only camouflaging the bug. In the worst case, the attempts to “handle” a bug introduce new bugs.

A big often overlooked advantage of assertions is that they lead to considerable simplification of the software by flagging many situations as errors (that you don't need to handle) rather than exceptional conditions (that you do need to handle). Often, the application code is much simpler when it does not need to check and handle error codes returned by the framework but instead can rely on the framework policies enforced by assertions (see Section 6.1.6).

Listing 6.1 shows the simple, customizable, embedded systems-friendly assertions that I've found adequate for a wide range of projects, embedded or otherwise. These simple assertions are consistently used in all QP components, such as the QF real-time framework and the QEP event processor.

The qassert.h header file shown in Listing 6.1 is similar to the standard <assert.h> header file, except (1) qassert.h allows customizing the error response, (2) it conserves memory by avoiding proliferation of multiple copies of the filename string, and (3) it provides additional macros for testing and documenting preconditions (Q_REQUIRE), postconditions (Q_ENSURE), and invariants (Q_INVARIANT). The names of these three latter macros are a direct loan from Eiffel, the programming language that natively supports DbC.

Compared to the standard assert(), the assertion macros defined in Listing 6.1 conserve memory (typically ROM) by using l_this_file[] string as the first argument to Q_onAssert() rather than the standard preprocessor macro __FILE__. This avoids proliferation of the multiple copies of the __FILE__ string for each use of the assert() macro (see [Maguire 93]).

An exceptional condition is a specific situation in the lifetime of a system that calls for a special behavior. In a state-driven active object, a change in behavior corresponds to a change in state (state transition). Hence, in active object systems, the associated state machines are the most natural way to handle all conditions, including exceptional conditions.

Using state hierarchy can be very helpful to separate the “exceptional” behavior from the “normal” behavior. Such state-based exception handling is typically a combination of the Ultimate Hook and the Reminder state patterns (Chapter 5) and works as follows: A common superstate defines a high-level transition to the “exceptional” parts of the state machine. The submachine of this superstate implements the “normal” behavior. Whenever an action within the submachine encounters an exceptional condition, it posts a Reminder event to self to trigger the high-level transition to handle the exception. The exit actions executed upon the high-level transition perform the cleanup of the current context and cleanly enter the “exceptional” context.

State-based exception handling offers a safe and language-independent alternative to the built-in exception-handling mechanism of the underlying programming language. As described in Section 3.7.2 in Chapter 3, throwing and catching exceptions in C++ is risky in any state machine implementation because it conflicts with the fundamental RTC semantics of state machines. Stack unwinding inherent in propagating of thrown exceptions is also less relevant in event-driven systems than traditional sequential code because event-driven systems rely less on the stack and more on storing the state information in the static data. As Tom Cargill noticed in the seminal paper Exception handling: A false sense of security [Cargill 94]:

If you only can, consider leaving out the C++ throw-and-catch exception handling from your event-driven software. If you cannot avoid it, make sure to catch all exceptions before they can cause any damage.

The standard practice is to use assertions during development and testing but to disable them in the final product. The often-quoted opinion in this matter comes from C.A.R. Hoare, who considered disabling assertions in the final product like using a lifebelt during practice but then not bothering with it for the real thing.

The question of shipping with assertions really boils down to two issues. First is the overhead that assertions add to your code. Obviously, if the overhead is too big, you have no choice. But then you must ask yourself how you will build and test your application. It's much better to consider assertions as an integral part of the software and size the hardware adequately to accommodate them. As the prices of computer hardware rapidly drop while the capabilities increase, it simply makes sense to trade a small fraction of the raw CPU horsepower and some extra code memory for better system integrity. In practice, assertions often pay for themselves by eliminating reams of “error-handling” code that tries to camouflage bugs.

The other issue is the correct system response when an assertion fires in the field. This response must be obviously designed carefully and safety-critical systems might require some redundancy and recovery strategy. For many less critical applications a simple system reset turns out to be the least inconvenient action from the user's perspective—certainly less inconvenient than locking up the application and denying service. You should also try to leave some “bread crumbs” of information as to what went wrong. To this end, assertions provide a great starting point for debugging and ultimately fixing the root cause of the problem.

Traditional sequential systems communicate predominately by means of synchronous function calls. When module A wants to communicate with module B, module A calls a function in B. The communication is implicitly assumed to be reliable; that is, the programmer takes for granted that the function call mechanism will work, that the parameters will be passed to the callee, and that the return value will be delivered to the caller. The programmer does not conceive of any recovery strategy to handle a failure in the function call mechanism itself. But in fact, any function call can fail due to insufficient stack space. Consequently, the reliability of synchronous communication is in fact predicated on the implicit assumption of adequate stack resource.

Event-driven systems communicate predominately by asynchronous event exchange. When active object A wants to communicate with active object B, object A allocates an event and posts it to the event queue of object B. The programmer should be able to take for granted that the event delivery mechanism will work, that the event will be available, and that the event queue will accept the event. However, in fact, asynchronous communication can fail due to event pool depletion or insufficient queue depth. Consequently, the reliability of asynchronous communication is in fact predicated on the assumption of adequate event pool size and event queue depth. If those two resources are sized properly, the asynchronous event posting in the same address space should be as reliable as a synchronous function call.

I hope that this argument helps you realize that event pools and event queues should be treated on equal footing as the execution stacks in that depletion of any of these resources represents an error. In fact, event pools and queues fulfill in event-driven systems many responsibilities of the execution stacks in traditional multitasking systems. For example, parameters passed inside events play the same role as the parameters of function calls passed on the call stacks. Consequently, event-driven systems use less stack space than sequential systems but instead require event queues and event pools.

A real-time framework can use assertions to detect event pool and event queue overruns, in the same way that many commercial RTOSs detect stack overflows. For example, the QF real-time framework asserts internally that a requested dynamic event can always be allocated from one of the event pools. Similarly, the QF framework asserts that an event queue can always accept a posted event. It's up to the application implementer to adequately size all event pools and event queues in the system in the same exact way as it is the implementer's responsibility to adequately size the execution stacks for a multitasking kernel.