Example is not the main thing in influencing others. It is the only thing.
In the previous two chapters, I explained the internal workings of the QF real-time framework and issues related to porting QF to various CPUs, operating systems, and compilers. However, I want you to realize that the way the QF framework itself is implemented internally is very different from the way you develop applications running on top of the framework.
A real-time framework, as any piece of system-level software, must internally employ many low-level mechanisms, such as critical sections and various blocking APIs of the underlying RTOS, if you use an RTOS. These mechanisms are always tricky to use correctly and programmers often underestimate the true risks and costs of their use.
But the good news is that this traditional approach to concurrent programming is contained within the framework. Once the framework is built and thoroughly tested, it offers you a faster, safer, and more reliable way of developing concurrent, event-driven software. A QF application has no more need to fiddle directly with critical sections, semaphores, or other such mechanisms. You can program active objects effectively and safely without even knowing what a semaphore is. Yet your application as a whole can reap all the benefits of multitasking, such as optimal, deterministic responsiveness and good CPU utilization.
My goal in this chapter is to explain how to develop a QP application that uses both the QF real-time framework and the QEP event processor described in Part I of this book. I begin with some general rules and heuristics for developing robust and maintainable QP applications. Next I describe the test application that historically I have used to verify all QP ports. I walk you through all steps required to design and implement this application. As you go over these steps, you might also flip back to the “Fly ‘n’ Shoot” game in Chapter 1, which is a bit more advanced example than the one I use here. In the chapter, I explain how to adapt the test application to all three QF ports discussed in Chapter 8. The chapter concludes with guidelines for sizing event queues and event pools.
The QP event-driven platform enables building efficient and maintainable event-driven applications in C and C++. However, it is also possible to use QP incorrectly, basically defeating its advantages. This section summarizes the main rules and heuristics for making the most out of active object computing implemented with QP.
When developing active object–based applications, you should try to heed the following two rules, without exception:
I strongly recommend that you take these rules seriously and follow them religiously. In exchange, the QF real-time framework can guarantee that your application is free from the traditional perils of preemptive multitasking, such as race conditions, deadlocks, priority inversions, starvation, and nondeterminism. In particular, you will never need to use mutexes, semaphores, monitors, or other such troublesome mechanisms at the application level. Even so, your QP applications can be fully deterministic and can handle hard real-time deadlines efficiently.
The rules of using active objects impose a certain programming discipline. In developing your QP applications, you will certainly be tempted to circumvent the rules. Occasionally, sharing a variable among different active objects or a mutually exclusive blocking active object threads might seem like the easiest solution. However, you should resist such quick fixes. First, you should convince yourself that the rules are there for a good reason (e.g., see Chapters 6 and 7). Second, you must trust that it is possible to arrive at a good solution without breaking the rules.
I repeatedly find that obeying the rules ultimately results in a better design and invariably pays dividends in the increased flexibility and robustness of the final software product. In fact, I propose that you treat every temptation to break the rules as an opportunity to discover something important about your application. Perhaps instead of sharing a variable, you will discover a new signal or a crucial event parameter that conveys some important information.
Many examples from other arts and crafts demonstrate that discipline can be good for art. Indeed, an artist's aphorism says, “Form is liberating.” As Fred Brooks [Brooks 95] eloquently writes: “Bach's creative output hardly seems to have been squelched by the necessity of producing a limited-form cantata each week.”
I am firmly convinced that the external provision of architecture such as the QF real-time framework enhances, not cramps, creativity.
Throughout Part II of this book, you can find several basic guidelines for constructing active object–based systems. Here is the quick summary.
• Event-driven programming requires a paradigm shift from traditional sequential programming. In the traditional approach, you concentrate on shared resources and various blocking mechanisms, such as semaphores, to signal events. Event-driven programming is all about writing nonblocking code and returning quickly to the event loop.
• Your main goal is to achieve loose coupling among active objects. You seek a partitioning of the problem that avoids resource sharing and requires minimal communication (in terms of number and size of exchanged events).
• The main strategy for avoiding resource sharing is to encapsulate the resources in dedicated active objects that manage the resources for the rest of the system.
• The responsiveness of an active object is determined by the longest RTC step of its state machine. To meet hard real-time deadlines, you need to either break up longer processing into shorter steps or move such processing to other, lower-priority active objects.
• A good starting point in developing an active object–based application is to draw sequence diagrams for the primary use cases. These diagrams help you discover signals and event parameters, which, in turn, determine the structure of active objects.
• As soon as you have the first sequence diagrams, you should build an executable model of it. The QP event-driven platform has been specifically designed to enable the construction and execution of vastly incomplete (virtually empty) prototypes. The high portability of QP enables you to build the models on a different platform than your ultimate target (e.g., your PC).
• Most of the time you can concentrate only on the internal state machines of active objects and ignore their other aspects (such as threads of execution and event queues). In fact, developing a QP application consists mostly of elaborating on the state machines of active objects. The generic QEP hierarchical event processor (Chapter 4) and the basic state patterns (Chapter 5) can help you with that part of the problem.
The test application that I historically have been using to verify QF ports is based on the classic Dining Philosophers Problem (DPP) posed and solved by Edsger Dijkstra back in 1971 [Dijkstra 71]. The DPP application is simpler than the “Fly ‘n’ Shoot” game described in Chapter 1 and can be tested only with a couple of LEDs on your target board, as opposed to the graphic display required by the “Fly ‘n’ Shoot” game. Still, DPP contains six concurrent active objects that exchange events via publish-subscribe and direct event-posting mechanisms. The application uses five time events (timers) as well as dynamic and static events.
First, your always need to understand what your application is supposed to accomplish. In the case of a simple application, the requirements are conveyed through the problem specification, which for the DPP is as follows.
Five philosophers are gathered around a table with a big plate of spaghetti in the middle (see Figure 9.1). Between each two philosophers is a fork. The spaghetti is so slippery that a philosopher needs two forks to eat it. The life of a philosopher consists of alternate periods of thinking and eating. When a philosopher wants to eat, he tries to acquire forks. If successful in acquiring two forks, he eats for a while, then puts down the forks and continues to think. The key issue is that a finite set of tasks (philosophers) is sharing a finite set of resources (forks), and each resource can be used by only one task at a time. (An alternative Oriental version replaces spaghetti with rice and forks with chopsticks, which perhaps explains better why philosophers need two chopsticks to eat.)
A good starting point in designing any event-driven system is to draw sequence diagrams for the main scenarios (main-use cases) identified from the problem specification. To draw such diagrams, you need to break up your problem into active objects with the main goal of minimizing the coupling among active objects. You seek a partitioning of the problem that avoids resource sharing and requires minimal communication in terms of number and size of exchanged events.
DPP has been specifically conceived to make the philosophers contend for the forks, which are the shared resources in this case. In active object systems, the generic design strategy for handling such shared resources is to encapsulate them inside a dedicated active object and to let that object manage the shared resources for the rest of the system (i.e., instead of directly sharing the resources, the rest of the application shares the dedicated active object). When you apply this strategy to DPP, you will naturally arrive at a dedicated active object to manage the forks. I named this active object Table.
The sequence diagram in Figure 9.2 shows the most representative event exchanges among any two adjacent Philosophers and the Table active objects.
(1) Each Philosopher active object starts in the “thinking” state. Upon the entry to this state, the Philosopher arms a one-shot time event to terminate the thinking.
(2) The QF framework posts the time event (timer) to Philosopher[m].
(3) Upon receiving the TIMEOUT event, Philosopher[m] transitions to “hungry” state and posts the HUNGRY(m) event to the Table active object. The parameter of the event tells the Table which Philosopher is getting hungry.
(4) The Table active object finds out that the forks for Philosopher[m] are available and grants it permission to eat by publishing the EAT(m) event.
(5) The permission to eat triggers the transition to “eating” in Philosopher[m]. Also, upon the entry to “eating,” the Philosopher arms its one-shot time event to terminate the eating.
(6) The Philosopher[n] receives the TIMEOUT event and behaves exactly as Philosopher[m], that is, transitions to “hungry” and posts HUNGRY(n) event to the Table active object.
(7) This time the Table active object finds out that the forks for Philosopher[n] are not available, and so it does not grant the permission to eat. Philosopher[n] remains in the “hungry” state.
(8) The QF framework delivers the timeout for terminating the eating to Philosopher[m]. Upon the exit from “eating,” Philosopher[m] publishes event DONE(m) to inform the application that it is no longer eating.
(9) The Table active object accounts for free forks and checks whether any direct neighbors of Philosopher[m] are hungry. Table posts event EAT(n) to Philosopher[n].
(10) The permission to eat triggers the transition to “eating” in Philosopher[n].
Sequence diagrams like Figure 9.2 help you discover events exchanged among active objects. The choice of signals and event parameters is perhaps the most important design decision in any event-driven system. The signals affect the other main application components: events and state machines of the active objects.
In QP, signals are typically enumerated constants and events with parameters are structures derived from the QEvent base structure. Listing 9.1 shows signals and events used in the DPP application. The DPP sample code for the DOS version (in C) is located in the <qp>qpcexamples80x86dos cpp101ldpp directory, where <qp> stands for the installation directory you chose to install the accompanying software.
Listing 9.1. Signals and events used in the DPP application (file dpp.h)
(2) EAT_SIG = Q_USER_SIG, /* published by Table to let a philosopher eat */
TERMINATE_SIG, /* published by BSP to terminate the application */(4)
HUNGRY_SIG/* posted directly from hungry Philosopher to Table */(7)
void Philo_ctor(void); /* ctor that instantiates all Philosophers */(9)
extern QActive * const AO_Philo [N_PHILO]; /* "opaque" pointers to Philo AOs */(10)
extern QActive * const AO_Table; /* "opaque" pointer to Table AO */
Note
In this section, I describe the platform-independent code of the DPP application. This code is actually identical in all DPP versions, such as the Linux version, μC/OS-II version, Cortex-M3 versions, and the QK version described in Chapter 10.
(1) For smaller applications such as the DPP, I define all signals in one enumeration (rather than in separate enumerations or, worse, as preprocessor
#definemacros). An enumeration automatically guarantees the uniqueness of signals.(2) Note that the user signals must start with the offset
Q_USER_SIGto avoid overlapping the reserved QEP signals.(3) I like to group all the globally published signals at the top of the enumeration, and I use the
MAX_PUB_SIGenumeration to automatically keep track of the maximum published signals in the application.(4) I decided that the Philosophers will post the HUNGRY event directly to the Table object rather than publicly publish the event (perhaps a Philosopher is “embarrassed” to be hungry, so does not want other Philosophers to know about it). That way, I can demonstrate direct event posting and publish-subscribe mechanisms coexisting in a single application.
(5) I use the
MAX_SIGenumeration to automatically keep track of the total number of signals used in the application.(6) Every event with parameters, such as the
TableEvt, derives from theQEventbase structure.
I like to keep the code and data structure of every active object strictly encapsulated within its own C-file. For example, all code and data for the active object Table are encapsulated in the file table.c, with the external interface consisting of the function Table_ctor() and the pointer AO_Table.
(7,8) These functions perform an early initialization of the active objects in the system. They play the role of static “constructors,” which in C you need to call explicitly, typically at the beginning of
main().(9,10) These global pointers represent active objects in the application and are used for posting events directly to active objects. Because the pointers can be initialized at compile time, I like to declare them
constso that they can be placed in ROM. The active object pointers are “opaque” because they cannot access the whole active object, but only the part inherited from theQActivestructure.
At the application level, you can mostly ignore such aspects of active objects as the separate task contexts or private event queues and view them predominantly as state machines. In fact, your main job in developing your QP application consists of elaborating the state machines of your active objects.
Figure 9.3(A) shows the state machines associated with Philosopher active object, which clearly shows the life cycle consisting of states “thinking,” “hungry,” and “eating.” This state machine generates the HUNGRY event on entry to the “hungry” state and the DONE event on exit from the “eating” state, because this exactly reflects the semantics of these events. An alternative approach—to generate these events from the corresponding TIMEOUT transitions—would not guarantee the preservation of the semantics in potential future modifications of the state machine. This actually is the general guideline in state machine design.
Figure 9.3(B) shows the state machine associated with the Table active object. This state machine is trivial because Table keeps track of the forks and hungry philosophers by means of extended state variables rather than by its state machine. The state diagram in Figure 9.3(B) obviously does not convey how the Table active object behaves, since the specification of actions is missing. I decided to omit the actions because including them required cutting and pasting most of the Table code into the diagram, which would make the diagram too cluttered. In this case, the diagram simply does not add much value over the code.
As I mentioned before, I like to strictly encapsulate each active object inside a dedicated source file (.C file). Listing 9.2 shows the declaration (active object structure) and complete definition (state-handler functions) of the Table active object in the file table.c. In the explanation section immediately following this listing, I focus on the techniques of encapsulating active objects and using QF services. I don't repeat here the recipes for coding state machine elements, which I already gave in Part I of this book (Chapters 1 and 4).
Listing 9.2. Table active object (file table.c); boldface indicates the QF services
/* Active object class -----------------------------------------------------*/(4)
uint8_t isHungry [N_PHILO]; /* remembers hungry philosophers */
static QState Table_initial(Table *me, QEvent const *e); /* pseudostate */
static QState Table_serving(Table *me, QEvent const *e); /* state handler */(5)
#define RIGHT(n_) ((uint8_t)(((n_) + (N_PHILO - 1)) % N_PHILO))
/* Local objects ----------------------------------------------------------*/(7)
static Table l_table; /* the single instance of the Table active object */
/* Global-scope objects ---------------------------------------------------*/(8)
QActive * const AO_Table = (QActive *)&l_table; /* "opaque" AO pointer */
/*........................................................................*/(10) QActive_ctor(&me->super, (QStateHandler)&Table_initial);
/*.......................................................................*/
(void)e; /* avoid the compiler warning about unused parameter */
/*.......................................................................*/(19)
Q_ASSERT((me->fork [n] == USED) && (me->fork [m] == USED));
(1) To achieve true encapsulation, I place the declaration of the active object structure in the source file (.C file).
(2) Each active object in the application derives from the
QActivebase structure.(3) The Table active object keeps track of the forks in the array
fork[]. The forks are numbered as shown in Figure 9.4.(4) Similarly, the Table active object needs to remember which philosophers are hungry, in case the forks aren't immediately available. Table keeps track of hungry philosophers in the array
isHungry[]. Philosophers are numbered as shown in Figure 9.4.(5,6) The helper macros
LEFT()andRIGHT()access the left and right philosopher or fork, respectively, as shown in Figure 9.4.(7) I statically allocate the Table active object. By defining this object as
staticI make it inaccessible outside the .C file.(8) Externally, the Table active object is known only through the “opaque” pointer
AO_Table. The pointer is declared ‘const’ (with theconstafter the ‘*’), which means that the pointer itself cannot change. This ensures that the active object pointer cannot change accidentally and also allows the compiler to allocate the active object pointer in ROM.(9) The function
Table_ctor()performs the instantiation of theTableactive object. It plays the role of the static “constructor,” which in C you need to call explicitly, typically at the beginning ofmain().
Note
In C++, static constructors are invoked automatically before
main(). This means that in the C++ version of DPP (found in<qp>qpcppexamples80x86dos cpp101ldpp), you provide a regular constructor for theTableclass and don't bother with calling it explicitly. However, you must make sure that the startup code for your particular embedded target includes the additional steps required by the C++ initialization.
Note
I often see new QP users forget subscribing to events, and then the application appears “dead” when you first run it.
(14) Note that Table does not subscribe to the HUNGRY event, because this event is posted directly.
(15) I sprinkled the state machine with calls to the function
BSP_busyDelay()to artificially prolong the RTC processing. The functionBSP_busyDelay()busy-waits in a counted loop, whereas you can adjust the number of iterations of this loop from the command line or through a debugger. This technique lets me increase the probability of various preemptions and thus helps me use the DPP application for stress-testing various QP ports.(16,18,19) The Table state machine extensively uses assertions to monitor correct execution of the DPP application. For example, in line (19) both forks of a philosopher who just finished eating must be used.
(17) The output to the screen is a BSP (board support package) operation. The different BSPs implement this operation differently, but the code of the Table state machine does not need to change.
(20,21) It is possible that the Table active object publishes two events in a single RTC step.
(22) Upon receiving the TERMINATE event, the Table active object calls
QF_stop()to stop QF and return to the underlying operating system.
The Philosopher active objects bring no essentially new techniques, so I don't reproduce the listing of the philo.c file here. The only interesting aspect of philosophers that I'd like to mention is that all five philosopher active objects are instances of the same active object class. The philosopher state machine also uses a few assertions to monitor correct execution of the application according to the problem specification.
Most of the system initialization and application startup can be written in a platform-independent way. In other words, you can use essentially the same main() function for the DPP application with many QP ports.
Typically, you start all your active objects from main(). The signature of the QActive_start() function forces you to make several important decisions about each active object upon startup. First, you need to decide the relative priorities of the active objects. Second, you need to decide the size of the event queues you preallocate for each active object. The correct size of the queue is actually related to the priority, as I discuss in the upcoming Section 9.4. Third, in some QF ports, you need to give each active object a separate stack, which also needs to be preallocated adequately. And finally, you need to decide the order in which you start your active objects.
The order of starting active objects becomes important when you use an OS or RTOS, in which a spawned thread starts to run immediately, possibly preempting the main() thread from which you launch your application. This could cause problems if, for example, the newly created active object attempts to post an event directly to another active object that has not been yet created. Such a situation does not occur in DPP, but if it is an issue for you, you can try to lock the scheduler until all active objects are started. You can then unlock the scheduler in the QF_onStartup() callback, which is invoked right before QF takes over control. Some RTOSs (e.g., μC/OS-II) allow you to defer the start of multitasking until after you start active objects. Another alternative is to start active objects from within other active objects, but this design increases coupling because the active object that serves as the launch pad must know the priorities, queue sizes, and stack sizes for all active objects to be started.
Listing 9.3. Initializing and starting the DPP application (file main.c)
/* Local-scope objects ---------------------------------------------------*/(2)
static QEvent const *l_philoQueueSto [N_PHILO][N_PHILO];(7)
} l_smlPoolSto [2*N_PHILO]; /* storage for the small event pool */
/*.......................................................................*/(8)
Philo_ctor(); /* instantiate all Philosopher active objects */(10)
BSP_init(argc, argv); /* initialize the Board Support Package */(11)
QF_init(); /* initialize the framework and the underlying RT kernel */(12)
QF_psInit(l_subscrSto, Q_DIM(l_subscrSto)); /* init publish-subscribe */(13)
QF_poolInit(l_smlPoolSto, sizeof(l_smlPoolSto), sizeof(l_smlPoolSto [0]));
for (n = 0; n < N_PHILO; ++n) { /* start the active objects... */
(1,2) The memory buffers for all event queues are statically allocated.
(3) The memory space for subscriber lists is also statically allocated. The
MAX_PUB_SIGenumeration comes in handy here.(4) The union
SmallEventcontains all events that are served by the “small” event pool.(5) The union contains a pointer-size member to make sure that the union size will be at least that big.
(6) You add all events that you want to be served from this event pool.
(7) The memory buffer for the “small” event pool is statically allocated.
(8,9) The
main()function starts with calling all static “constructors” (see Listing 9.1(7-8)). This step is not necessary in C++.(11) QF is initialized together with the underlying OS/RTOS.
(12) The publish-subscribe mechanism is initialized. You don't need to call
QF_psInit()if your application does not use publish-subscribe.(13) Up to three event pools can be initialized by calling
QF_poolInit()up to three times. The subsequent calls must be made in the order of increasing block sizes of the event pools. You don't need to callQF_poolInit()if your application does not use dynamic events.(14,15) All active objects are started using the “opaque” active object pointers (see Listing 9.1(9-10)). In this particular example, the active objects are started without private stacks. However, some RTOSs, such as μC/OS-II, require preallocating stacks for all active objects.
(16) The control is transferred to QF to run the application.
QF_run()might never return.
Terminating an application is not really a big concern in embedded systems because embedded programs almost never have a need to terminate gracefully. The job of a typical embedded system is never finished, and most embedded software runs forever or until the power is removed, whichever comes first.
Note
You still need to carefully design and test the fail-safe mechanism triggered by a CPU exception or assertion violation in your embedded system. However, such a situation represents a catastrophic shutdown, followed perhaps by a reset. The subject of this section is the graceful termination, which is part of the normal application life cycle.
However, in desktop programs, or when embedded applications run on top of a general-purpose operating system, such as Linux, Windows, or DOS, the shutdown of a QP application becomes important. The problem is that to terminate gracefully, the application must clean up all resources allocated by the application during its lifetime. Such a shutdown is always application-specific and cannot be preprogrammed generically at the framework level.
The DPP application uses the following mechanism to shut down: When the user decides to terminate the application, the global TERMINATE event is published. In DPP, only the Table active object subscribes to this event (Listing 9.2(13)), but in general all active objects that need to clean up anything before exiting should subscribe to the TERMINATE event. The last subscriber, which is typically the lowest-priority subscriber, calls the QF_stop() function (Listing 9.2(22)). As described in Chapter 8, QF_stop() is implemented in the QF port. Often, QF_stop() causes the QF_run() function to return. Right before transferring control to the underlying operating system, QF invokes the QF_onCleanup() callback. This callback gives the application the last chance to clean up globally (e.g., the DOS version restores the original DOS interrupt vectors).
Finally, you can also stop individual active objects and let the rest of the application continue execution. The cleanest way to end an active object's thread is to have it stop itself by calling QActive_stop(me), which should cause a return from the active object's thread routine. Of course, to “commit a suicide” voluntarily, the active object must be running and cannot be waiting for an event. In addition, before disappearing, the active object should release all the resources acquired during its lifetime. Finally, the active object should unsubscribe from receiving all signals and somehow should make sure that no more events will be posted to it directly. Unfortunately, all these requirements cannot be preprogrammed generically and always require some work on the application programmer's part.
I generally use the same DPP source code to test the QP ports on various CPUs, operating systems, and compilers. The only platform-dependent file is the board support package (BSP) definition and sometimes the main() function. In this section I describe what needs to be done to execute the DPP application with the “vanilla” kernel (I cover two versions: for 80×86 and Cortex-M3), as well as μC/OS-II on DOS and Linux.
The code for the DPP port to 80x86 with the “vanilla” kernel is located in the directory <qp>qpcexamples80x86dos cpp101ldpp. The directory contains the Turbo C++ 1.01 project files to build the application. You can execute the application by double-clicking the executables in the dbg, rel, or spy subdirectories. Figure 9.5 shows the output generated by the DPP executable. Listing 9.4 shows the BSP for this version of DPP.
Listing 9.4. BSP for the DPP application with the “Vanilla” kernel on DOS (file <qp>qpcexamples80x86dos cpp101ldppsp.c)
/* Local-scope objects---------------------------------------------------*/
static uint32_t l_delay = 0UL; /* limit for the loop counter in busyDelay() */
/*......................................................................*/(3)
QF_tick(); /* call QF_tick() outside of critical section */(5)
outportb(0x20, 0x20); /* write EOI to the master 8259A PIC */
/*......................................................................*/
key = inport(0x60); /*key scan code from the 8042 kbd controller */
outportb(0x61, (uint8_t)(kcr | 0x80)); /* toggle acknowledge bit high */
outportb(0x20, 0x20); /* write EOI to the master 8259A PIC */
/*.......................................................................*/
/*.......................................................................*/
void QF_onCleanup(void) { /* restore the original DOS vectors ... */
/*.......................................................................*/
/*.......................................................................*/(13)
l_delay = atol(argv [1]); /* set the delay counter for busy delay */
/*......................................................................*/
/*......................................................................*/
/*......................................................................*/
void Q_onAssert(char const Q_ROM * const Q_ROM_VAR file, int line) {
fprintf(stderr, "Assertion failed in %s, line %d", file, line);
(1) The compiler-supported Turbo C++ 1.01 compiler provides an extended keyword “
interrupt” that enables you to program ISRs in C/C++. The compiler-supported ISRs are adequate for the “vanilla” kernel.(2) The 80x86 processor locks interrupts in hardware before vectoring to the ISR. The interrupts can be unlocked right away, though, because the 8259A programmable interrupt controller prioritizes interrupts before they reach the CPU.
(3) The
QF_tick()service is called outside of the critical section. You cannot call any QF services within a critical section, because this “vanilla” port uses the simple “unconditional interrupt locking and unlocking” policy, which precludes nesting critical sections.(5) The end-of-interrupt (EOI) instruction is sent to the master 8259A PIC, so that it ends prioritization of this interrupt level.
(6,7) The original DOS interrupts vectors are saved to be restored upon cleanup.
(8,9) The customized interrupts are set for this port. This must happen in a critical section.
(10,11) Upon cleanup, the original DOS interrupts are restored.
(12) In the “vanilla” kernel, the
QF_idle()callback is invoked with interrupts locked and must always unlock interrupts (see Section 8.2.4 in Chapter 8).(13,14) The loop counter for the
BSP_busyDelay()function is set from the first command-line parameter. You should not go overboard with this parameter, because you might overload the CPU by creating an unschedulable set of tasks. In this case QF will eventually assert on overflowing an event queue.(15) The output of the philosopher status is implemented as a
printf()statement (see Figure 9.5). Note that the output occurs only from the context of the Table active object.(16) Upon an assertion failure, the application is stopped and cleanly exits to the DOS prompt.
The code for the DPP port to Cortex-M3 with the “vanilla” kernel is located in the directory <qp>qpcexamplescortex-m3vanillaiardpp. The directory contains the IAR EWARM v5.11 project files to build the application and download it to the EV-LM3S811 board. Figure 9.6 shows the display of the board while it is executing the application. Listing 9.5 shows the BSP for this version of DPP.
Listing 9.5. BSP for the DPP application with the “vanilla” kernel on bare metal Cortex-M3 (file <qp>qpcexamplescortex-m3vanillaiardpp-ev-lm3s811sp.c)
. . . /* other Luminary Micro driver library include files */
/* Local-scope objects ----------------------------------------------------*/
static uint32_t l_delay = 0UL; /* limit for the loop counter in busyDelay() */
/*......................................................................*/
/* add any application-specific clock-tick processing, as needed */
/*......................................................................*/
/* Configure the LED, push button, and UART GPIOs as required. */(5)
GPIODirModeSet(GPIO_PORTA_BASE, GPIO_PIN_0 | GPIO_PIN_1,
GPIODirModeSet(GPIO_PORTC_BASE, PUSH_BUTTON, GPIO_DIR_MODE_IN);
GPIODirModeSet(GPIO_PORTC_BASE, USER_LED, GPIO_DIR_MODE_OUT);
/*......................................................................*/
/*......................................................................*/
/*......................................................................*/
/* Set up and enable the SysTick timer. It will be used as a reference
* for delay loops in the interrupt handlers. The SysTick timer period(10)
SysTickPeriodSet(SysCtlClockGet() / BSP_TICKS_PER_SEC);(12)
IntPrioritySet(FAULT_SYSTICK, 0xC0); /* set the priority of SysTick */(13)
SysTickIntEnable(); /* Enable the SysTick interrupts */(14)
QF_INT_UNLOCK(dummy); /* set the interrupt flag in PRIMASK */
/*......................................................................*/
/*......................................................................*/
void QF_onIdle(void) { /* entered with interrupts LOCKED, see NOTE01 */
GPIOPinWrite(GPIO_PORTC_BASE, USER_LED, USER_LED); /* User LED on */
GPIOPinWrite(GPIO_PORTC_BASE, USER_LED, 0); /* User LED off */
* you might need to customize the clock management for your application,(18)
QF_INT_UNLOCK(dummy); /* always unlock the interrupts */
/*......................................................................*/
void Q_onAssert(char const Q_ROM * const Q_ROM_VAR file, int line) {
QF_INT_LOCK(dummy); /* make sure that all interrupts are disabled */(19)
for (;;) { /* NOTE: replace the loop with reset for the final version */
/* error routine that is called if the Luminary library encounters an error */(20)
void __error__(char *pcFilename, unsigned long ulLine) {
(1) The BSP for Cortex-M3 relies on the driver library provided by Luminary Micro with the EV-LM3S811 board.
(2) As described in Section 8.2.3 in Chapter 8, ISRs in Cortex-M3 are just regular C functions. The system clock tick is implemented with the Cortex-M3 SysTick interrupt, specifically designed for that purpose. Note that the Cortex-M3 enters ISRs with interrupts unlocked, so there is no need to unlock interrupts before calling QF services, such as
QF_tick().(3-5) The board initialization includes enabling all peripherals used in the DPP application.
(6-8) The graphic OLED display driver is initialized and the screen is prepared for the DPP application.
(9) The output of the philosopher status is implemented as drawing a single letter on the screen (see Figure 9.6). Note that the output occurs only from the context of the Table active object.
(10) Upon startup, the hardware system clock tick rate is set.
(12) The Cortex-M3 performs prioritization of all interrupts in hardware, and it is highly recommended to explicitly set the priority of every interrupt used by the application. The Cortex-M3 represents an ISR priority in the three most significant bits of a byte, whereas 0xE0 is the lowest and 0x00 is the highest hardware priority. Priority 0xC0 corresponds to the second-lowest priority in the system.
(13) The system clock tick interrupt is enabled in hardware.
(15) The DPP application running on the EV-LM3S811 board operates on “bare metal” and has no operating system to return to. The cleanup callback is not used in this case.
(16-18) In Section 8.2.4, I have already discussed idle processing for the “vanilla” kernel running on Cortex-M3.
(19) The assertion handler enters a forever loop in the DPP application. You need to replace this loop with the fail-safe shutdown, followed perhaps by a reset in the production version of your application.
(20) The function
__error__()is used inside the Luminary Micro driver library. This function has the same purpose and signature asQ_onAssert().
The code for the DPP port to 80x86 with the μC/OS-II RTOS is located in the directory <qp>qpcexamples80x86ucos2 cpp101ldpp. The directory contains the make.bat batch file to build the application. You can execute the DPP application by double-clicking the executables in the dbg, rel, or spy subdirectories. Figure 9.7 shows the output generated by the DPP executable.
As shown in Listing 9.6, in case of μC/OS-II, you need to modify the main.c source file to supply the private stacks for the active object tasks. This is one of the big-ticket items in terms of RAM usage required by a traditional preemptive kernel. You also need to create a dedicated μC/OS-II task to start the interrupts, as described in the Micro-C/OS-II book [Labrosse 02]. Listing 9.7 shows the customization of the μC/OS-II hooks (callbacks) to call the QF clock tick processing.
Listing 9.6. main() function for the DPP application with the μC/OS-II RTOS on DOS (file <qp>qpcexamples80x86ucos2 cpp101ldppmain.c)
/* Local-scope objects ---------------------------------------------------*/(1) static OS_STK l_philoStk[N_PHILO][256];/* stacks for the Philosophers */
(2) static OS_STK l_tableStk[256];
/* stack for the Table */(3) static OS_STK l_ucosTaskStk[256]; /* stack for the ucosTask */
/*........................................................................*/
/* create a uC/OS-II task to start interrupts and poll the keyboard */
Listing 9.7. BSP for the DPP application for the μC/OS-II RTOS on DOS (file <qp>qpcexamples80x86ucos2 cpp101ldppsp.c)
/*.......................................................................*/
(void)pdata; /* avoid the compiler warning about unused parameter */(2) QF_onStartup(); /* start interrupts including the clock tick, NOTE01 */
/*.......................................................................*/
/* add any application-specific clock-tick processing, as needed */
/*.......................................................................*/
(1-3) You need to statically allocate the private stacks for all μC/OS-II tasks that you use in the application. Here, I have oversized all stacks of to 256 of 16-bit stack entries (see definition of OS_STK in the μC/OS-II port file
os_cpu.h). However, μC/OS-II allows each stack to have a different size.(4,5) The stack storage is passed to the active objects through the
stkStoandstkSizeparameters of theQActive_start()function.(6) I also create additional “raw” μC/OS-II task
ucosTask()that starts all interrupts and polls the keyboard to find out when to terminate the application. The body of theucosTask()function is shown in Listing 9.7.
(1) The BSP contains a “raw” μC/OS-II task with the main responsibility of starting the interrupts, which in μC/OS-II must occur only after the
OSStart()function is called fromQF_run()(see [Labrosse 02]).(2) The
QF_onStartup()callback starts interrupts and is identical in this case as in Listing 9.4(6-9).(3) As any conventional task,
ucosTask()must call some blocking RTOS function. In this case, the task blocks on the timed delay.(4) Every time the task wakes up, it polls the keyboard and checks whether the user hit the
Esckey. If so, the μC/OS-II task publishes the static TERMINATE event. This call provides an example of how to generate QP events from external, third-party code.(5) The
QF_tick()processing is invoked from the μC/OS-II hook. Note that this particular μC/OS-II port uses the “saving and restoring interrupt status” policy (μC/OS-II critical section type 3). This means that it's safe to call a QF service, even though μC/OS-II callsOSTimeTickHook()with interrupts locked.(6) Under a preemptive kernel such as μC/OS-II, a transition to a low-power sleep mode does not need to occur atomically (as it must in the nonpreemptive “vanilla” kernel). Refer to Section 8.3.6 in Chapter 8 for the discussion of idle processing under a preemptive kernel.
The code for the DPP port to Linux is located in the directory <qp>qpcexamples80x86linuxgnudpp. The directory contains the Makefile to build the application. You can execute the application from a console, as shown in Figure 9.8. The real-time behavior of the application depends on the privilege level. If you launch the application with the “superuser” privileges, the QF port will use the SCHED_FIFO real-time scheduler and will prioritize active object threads high (see Section 8.4 in Chapter 8). Otherwise, the application will execute under the default SCHED_OTHER scheduler without a clear notion of priorities for active objects or the “ticker” task. Listing 9.8 shows the BSP for Linux.
Listing 9.8. BSP for the DPP application for Linux (file <qp>qpcexamples80x86linuxgnudppsp.c)
/* Local objects ---------------------------------------------------------*/(1)
static struct termios l_tsav; /* structure with saved terminal attributes */
static uint32_t l_delay; /* limit for the loop counter in busyDelay() */
/*.......................................................................*/(2)
static void *idleThread(void *me) { /* the expected P-Thread signature */
/* sleep for the full tick or until a console input arrives */(3)
if (0 != select(1, &con, 0, 0, &timeout)) { /* any descriptor set? */
/*.......................................................................*/
l_delay = atol(argv [1]); /* set the delay from the argument */
/*.......................................................................*/(5)
tcgetattr(0, &l_tsav); /* save the current terminal attributes */
tcgetattr(0, &tio); /* obtain the current terminal attributes */(6)
tio.c_lflag &= ~(ICANON | ECHO); /* disable the canonical mode & echo */
/* SCHED_FIFO corresponds to real-time preemptive priority-based scheduler
* NOTE: This scheduling policy requires the superuser priviledges
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);(7)
if (pthread_create(&idle, &attr, &idleThread, 0) != 0) {
* Most probably this application has no superuser privileges,(8)
Q_ALLEGE(pthread_create(&idle, &attr, &idleThread, 0) == 0);
/*.......................................................................*/(9)
tcsetattr(0, TCSANOW, &l_tsav); /* restore the saved terminal attributes */
/*.......................................................................*/
/*.......................................................................*/
/*.......................................................................*/
void Q_onAssert(char const Q_ROM * const Q_ROM_VAR file, int line) {
fprintf(stderr, "Assertion failed in %s, line %d", file, line);
(1) The standard configuration of a Linux console does not allow collecting user keystrokes asynchronously. The mode of the terminal can be changed but needs to be restored upon exit. The BSP uses the local variable
l_tsavto save the terminal settings.(2) The BSP contains a “raw” POSIX-thread
idleThread()with the main responsibility of polling the console for asynchronous input and terminating the application when the user presses theEsckey.(3) The
idleThread()uses theselect()POSIX call as the main blocking mechanism.(4) The
idleThread()generates and publishes the TERMINATE event when it detects theEsckeypress.(5) Upon startup the terminal attributes are saved into the static variable
t_sav.(6) The canonical mode of the terminal is switched off to allow collecting keystrokes asynchronously.
(7) The idle thread is first created with the real-time SCHED_FIFO scheduling policy and the lowest possible priority. Using the SCHED_FIFO policy requires “superuser” privileges and might fail if the application is launched without these privileges.
(8) If creating the thread under SCHED_FIFO fails, the thread is created under the default SCHED_OTHER policy. This time, the thread must be created successfully; otherwise, the application cannot continue, and hence the assertion.
(9) The cleanup callback restores the saved terminal attributes.
(10) The output of the philosopher status is implemented as a
printf()statement (see Figure 9.8). Note that the output occurs only from the context of the Table active object.(11) Upon an assertion failure, the application is stopped and cleanly exits to Linux.
Event queues and event pools are the necessary burden you need to accept when you work within the event-driven paradigm. They are the price to pay for the convenience and speed of development.
The main problem with event queues and event pools is that they consume your precious memory. To minimize that memory, you need to size them appropriately. In this respect, event queues and pools are no different from execution stacks—these data structures all trade some memory for the convenience of programming.
The adequate sizing of event queues and event pools is especially important in QF applications because QF raises an assertion when an event queue overflows or an event pool runs out of events. QF treats both these situations as first-class bugs equally bad as overflowing the stack.
Note that the problem with sizing event queues and event pools is common to all active object–based frameworks, not specifically to QF. For instance, application frameworks that accompany design automation tools have this problem as well. However, the tools handle the problem behind the scenes by using massively oversized defaults. In fact, you should do exactly the same thing: Create oversized event queues and event pools in the early stages of development.
The minimization of memory consumed by event queues, event pools, and execution stacks is like shrink-wrapping your event-driven application. You should do it toward the end of application development because it stifles the flexibility you need in the earlier stages. Note that any change in processing time, interrupt load, or event production patterns can invalidate both your static analysis and the empirical measurements of queue and pool usage. However, that doesn't mean that you shouldn't care at all about event queues and event pools throughout the design and early implementation phase. To the contrary, understanding the general rules for sizing event queues and pools helps you conserve memory by avoiding unnecessary bursts in event production or by breaking up excessively long RTC steps. These techniques are analogous to the ways execution stack space is conserved by avoiding deep call nesting and big automatic variables.
One basic fact that you need to understand about event queues is that they work only when the average event production rate <P(t)> does not exceed the average event consumption rate <C(t)>. If this condition is not satisfied, the event queue is of no use and always eventually overflows, no matter how big you make it. This fact does not mean that the production rate P(t) cannot occasionally exceed the consumption rate C(t), but such a burst of event production can persist for only a short time. The bursts should also be sufficiently spread out over time to allow cleanup of the queue.
Some software designers try to work around these fundamental limitations by using message queues in a more “creative” way. For example, designers either allow blocking of the producer threads when the queue is full, effectively reducing the production rate P(t), or allow messages to be lost, effectively boosting the consumption rate C(t). The QF views both techniques as an abuse of event queues and simply asserts a contract violation. The basic premise behind this policy is that such a creative use of event queues destroys the event-delivery guarantee (see Chapter 6).
The empirical method is perhaps the simplest and most popular technique used to determine the required capacity of event queues, or any other buffers for that matter (e.g., execution stacks). This technique involves running the system for a while and then stopping it to examine how much of various buffers has been used. The QF implementation of the event queue (the QEQueue class) maintains the nMin data member specifically for this purpose (see Listing 7.24(12-14) in Chapter 7). You can inspect this low-watermark easily using a debugger or through a memory dump.
The alternative technique relies on a static analysis of event production and event consumption. The QF framework uses event queues in a rather specific way (e.g., there is only one consumer thread); consequently, the production rate P(t) and the consumption rate C(t) are strongly correlated.
For example, consider a QF application running under a preemptive, priority-based kernel.1 The following discussion also pertains approximately to foreground/background systems with priority queues (see Section 7.11 in Chapter 7). However, the analysis is generally not applicable to desktop systems (e.g., Linux or Windows), where the concept of thread priority is much fuzzier. Assume further that the highest-priority active object receives events only from other active objects (but not from ISRs). Whenever any of the lower-priority active objects posts or publishes an event for the highest-priority object, the kernel immediately assigns the CPU to the recipient. The kernel makes the context switch because, at this point, the recipient is the highest-priority thread ready to run. The highest-priority active object awakens and runs to completion, consuming any event posted to it. Therefore, the highest-priority active object really doesn't need to queue events (the maximum depth of its event queue is 1).
When the highest-priority active object receives events from ISRs, more events can queue up for it. In the most common arrangement, an ISR produces only one event per activation. In addition, the real-time deadlines are typically such that the highest-priority active object must consume the event before the next interrupt. In this case, the object's event queue can grow, at most, to two events: one from a task and the other from an ISR.
You can extend this analysis recursively to lower-priority active objects. The maximum number of queued events is the sum of all events that higher-priority threads and ISRs can produce for the active object within a given deadline. The deadline is the longest RTC step of the active object, including all possible preemptions by higher-priority threads and ISRs. For example, in the DPP application, all Philosopher active objects perform very little processing (they have short RTC steps). If the CPU can complete these RTC steps within one clock tick, the maximum length of the Philosopher queue would be three events: one from the clock-tick ISR and two from the Table active object (Table can sometimes publish two events in one RTC step).
The rules of thumb for the static analysis of event queue capacity are as follows.
• The size of the event queue depends on the priority of the active object. Generally, the higher the priority, the shorter the necessary event queue. In particular, the highest-priority active object in the system immediately consumes all events posted by the other active objects and needs to queue only those events posted by ISRs.
• The queue size depends on the duration of the longest RTC step, including all potential (worst-case) preemptions by higher-priority active objects and ISRs. The faster the processing, the shorter the necessary event queue. To minimize the queue size, you should avoid very long RTC steps. Ideally, all RTC steps of a given active object should require about the same number of CPU cycles to complete.
• Any correlated event production can negatively affect queue size. For example, sometimes ISRs or active objects produce multiple event instances in one RTC step (e.g., the Table active object occasionally produces two permissions to eat). If minimal queue size is critical in your application, you should avoid such bursts by, for example, spreading event production over many RTC steps.
Remember also that the static analysis pertains to a steady-state operation after the initial transient. On startup, the relative priority structure and the event production patterns might be quite different. Generally, it is safest to start active objects in the order of their priority, beginning from the lowest-priority active objects because they tend to have the biggest event queues.
The size of event pools depends on how many events of different kinds you can sink in your system. The obvious sinks of events are event queues because as long as an event instance waits in a queue, the instance cannot be reused. Another potential sink of events is the event producer. A typical event-generation scenario is to create an event first (assigning a temporary variable to hold the event pointer), then fill in the event parameters and eventually post or publish the event. If the execution thread is preempted after event creation but before posting it, the event is temporarily lost for reuse.
In the simplest case of just one event pool (one size of events) in the system, you can determine the event pool size by adding the sizes of all the event queues plus the number of active objects in the system.
When you use more event pools (the QF allows up to three event pools), the analysis becomes more involved. Generally, you need to proceed as with event queues. For each event size, you determine how many events of this size can accumulate at any given time inside the event queues and can otherwise exist as temporaries in the system.
An important aspect of QF-based applications is their integration with the rest of the embedded real-time software, most notably with the device drivers and the I/O system.
Generally, this integration must be based on the event-driven paradigm. QF allows you to post or publish events from any piece of software, not necessarily from active objects. Therefore, if you write your own device drivers or have access to the device driver source code, you can use the QF facilities for creating and publishing or posting events directly.
You should view any device as a shared resource and, therefore, restrict its access to only one active object. This method is safest because it evades potential problems with reentrancy. As long as access is strictly limited to one active object, the RTC execution within the active object allows you to use nonreentrant code. Even if the code is protected by some mutual exclusion mechanism, as is often the case for commercial device drivers, limiting the access to one thread avoids priority inversions and nondeterminism caused by the mutual blocking of active objects.
Accessing a device from just one active object does not necessarily mean that you need a separate active object for every device. Often, you can use one active object to encapsulate many devices.
The internal implementation of the QF real-time framework uses a lot of low-level mechanisms such as critical sections, mutexes, and message queues. However, after the infrastructure for executing active objects is in place, the development of QF-based applications can proceed much easier and faster. The higher productivity comes from encapsulated active objects that can be programmed without the troublesome low-level mechanisms traditionally associated with multitasking programs. Yet, the application as a whole can still take full advantage of multithreading.
Developing a QP application involves defining signals and event classes, elaborating state machines of active objects, and deploying the application on a concrete platform. The high portability of QP software components enables you to develop large portions of the code on a different platform than the ultimate target.
Programming with active objects requires some discipline on the part of the programmer because sharing memory and resources is prohibited. The experience of many software developers has shown that it is possible to write efficient applications without breaking this rule. Moreover, the discipline actually helps create software products that are safer, more robust, and easier to test and maintain.
You can view event queues and event pools as the costs inherently associated with event-driven programming paradigm. These data structures, like execution stacks, trade some memory for programming convenience. You should start application development with oversized queues, pools, and stacks and shrink them only toward the end of product development. You can combine basic empirical and analytical techniques for minimizing the size of event queues and event pools.
When integrating the QP application with device drivers and other software components, you should avoid sharing any nonreentrant or mutex-protected code among active objects. The best strategy is to localize access to such code in a dedicated active object.
Active object-based applications tend to be much more resilient to change than traditional blocking tasks because active objects never block and thus are more responsive than blocked tasks. Also, the higher adaptability of event-driven systems is rooted in the separation of concerns of signaling events and state of the object. In particular, active objects use state machines instead of blocking to represent modes of operation and use event passing instead of unblocking to signal interesting occurrences.
The active object-based computing model has been around long enough for programmers to accumulate a rich body of experience about how to best develop such systems. For example, the Real-Time Object-Oriented Modeling (ROOM) method of Selic and colleagues [Selic+ 94] provides a comprehensive set of related development strategies, processes, techniques, and tools. Douglass [Douglass 99, 02, 06] presents unique state patterns, safety-related issues, plenty of examples, and software process applicable to real-time development.