In this chapter I describe a reduced version of the event-driven infrastructure called QP-nano, which has been specifically designed to enable active object computing with UML-style hierarchical state machines on low-end 8- and 16-bit single-chip microcontrollers (MCUs). By low-end MCUs I mean devices such as 8051, PIC, AVR, MSP430, 68HC08/11/12, R8C/Tiny, and others alike, with a few hundred bytes of RAM and a few kilobytes of ROM. Embedded in myriads of products, these “invisible computers” far outnumber all other processor types in a similar way as countless species of insects far outnumber all other life forms on Earth [Turely 02].
Even though the QP event-driven platform is by no means big, a minimal QP application still requires around 1KB of RAM and some 10KB of ROM (see Figure 7.2 in Chapter 7), which is comparable to the footprint of a very small, bare-bones conventional RTOS. In comparison, a minimal QP-nano application can fit in a system with just 100 bytes of RAM and 2KB of ROM. This tiny footprint, especially in RAM, makes QP-nano ideal for high-volume, cost-sensitive, event-driven applications such as motor control, lighting control, capacitive touch sensing, remote access control, RFID, thermostats, small appliances, toys, power supplies, battery chargers, or just about any custom system on a chip (SOC or ASIC) that contains a small processor inside. Also, because the event-driven paradigm naturally uses the CPU only when handling events and otherwise can very easily switch the CPU into a low-power sleep mode (see Section 6.3.7 in Chapter 6), QP-nano is particularly suitable for ultra-low power applications, such as wireless sensor networks or implantable medical devices.
I begin this chapter by describing the key features of QP-nano. I then walk you through the QP-nano version of the “Fly ‘n’ Shoot” game, which I introduced in Chapter 1, so that you can easily compare how QP-nano differs from the full-version QP. Next I describe the QP-nano source code. I conclude with some more QP-nano examples for a very small, ultra-low-power MSP430F2013 MCU [TI 07].
QP-nano is a generic, portable, ultra-lightweight, event-driven infrastructure designed specifically for low-end 8- and 16-bit MCUs. As shown in Figure 12.1, QP-nano consists of a hierarchical event processor called QEP-nano, a minimal real-time framework called QF-nano, and a choice between a preemptive run-to-completion kernel called QK-nano or a cooperative “vanilla” kernel. The key QP-nano features are:
• Full support for hierarchical state nesting, including guaranteed entry/exit action execution on arbitrary state transition topology with up to four levels of state nesting
• Support for up to eight concurrently executing active objects1 This does not mean that your application is limited to eight state machines. Each active object can manage any number of stateful components, as described in the “Orthogonal Component” state pattern in Chapter 5. with deterministic, thread-safe event queues
• Support for events with a byte-wide signal (255 signals) and one scalar parameter, configurable to 0 (no parameter), 1, 2, or 4 bytes
• Direct event delivery mechanism with first-in, first-out (FIFO) queuing policy
• One single-shot time event (timer) per active object with configurable dynamic range of 0 (no time events), 1, 2, or 4 bytes
• Built-in cooperative “vanilla” kernel (see Section 6.3.7 in Chapter 6)
• Built-in preemptive RTC kernel called QK-nano (see Section 6.3.8 in Chapter 6)
• Low-power architecture with idle callback function for easy implementation of power-saving modes
• Provisions in the code to handle nonstandard extensions in the C compilers for popular low-end CPU architectures (e.g., allocation of constant objects in the code space, reentrant functions, etc.)
By far the biggest challenge in QP-nano design is the extremely tight RAM budget, which I assumed to be only around 100 bytes, including the C stack. Obviously, with RAM in such short supply I was forced to carefully count every byte of RAM. This is in contrast to the full-version QP, where I was not trying to save every last byte of RAM if this would reduce programming convenience, flexibility, or performance.
Perhaps the most important implication of the severely limited RAM is that QP-nano does not support events with arbitrary-sized parameters. Instead, QP-nano allows only fixed-size events with one scalar parameter, configurable to 1, 2, or 4 bytes (or 0 bytes, which means no event parameter). This has far-reaching simplifying consequences. First, event queues in QP-nano hold entire events, not just pointers to events, as in the full-version QP. Small, fixed-size events are simply copied by value into and out of event queues in an inherently thread-safe manner. Second, the copy-by-value policy eliminates the need for event pools, which would not fit into the available RAM anyway. Finally, reference counting of events is unnecessary in this design.
Note
A single scalar event parameter means that QP-nano always associates the configured number of bytes with every event, but it does not mean that you can have only one event parameter. In fact, each event can have as many event parameters as you can squeeze into the available bits.
At this time, QP-nano does not support software tracing (see Chapter 11), because I assume that the available RAM is too small for any reasonable trace buffer. Also, most low-end MCUs tend to be very limited in the number of pins, so allocating even one extra output pin only for development purposes can be a challenge.
Perhaps the best way to learn about QP-nano capabilities and how the program differs from the full version of QP is to reimplement a nontrivial QP example in QP-nano. In this section, I'll walk you through the QP-nano version of the “Fly ‘n’ Shoot” game introduced in Chapter 1. I recommend that you flip back to Chapter 1 and refresh your understanding of that application and its implementation based on the full-version QP.
The code accompanying this book contains four QP-nano implementations of the “Fly ‘n’ Shoot” game for two embedded targets and two different kernels. Here I'll use the version for DOS with the nonpreemptive kernel compiled with the legacy Turbo C++ 1.01 compiler, which you can run directly on any Windows PC. You can find this version in the directory <qp>qpnexamples80x86 cpp101game
. The same application code (except for the BSP) is also available for the Cortex-M3 EV-LM3S811 board (see Figure 1.2 in Chapter 1). The Cortex-M3 code is located in the directory <qp>qpnexamplescortex-m3iargame-ev-lm3s811
.
Note
The LM3S811 MCU (32-bit ARM Cortex-M3) with 8KB of RAM and 64KB of ROM is certainly a very big machine for QP-nano. I use it in this section only to provide a direct comparison to the same application implemented with full-version QP. In the upcoming Section 12.7, I describe QP-nano examples for the ultra-low power Texas Instruments board called eZ430-F2013, which is based on the MSP430F2013 MCU with only 128 bytes of RAM and 2KB of ROM [TI 07].
Listing 12.1 shows the main.c
source file for the “Fly ‘n’ Shoot” application, which contains the main()
function along with some important data structures required by QP-nano.
Listing 12.1. The file main.c of the “Fly ‘n’ Shoot” game application
(3)
#include "game.h" /* application interface */
(3)
/*.....................................................................*/
(6)
static QEvent l_missileQueue[2];
(6)
/* QF_active[] array defines all active object control blocks ----*/
(9)
{ (QActive *)&AO_tunnel, l_tunnelQueue, Q_DIM(l_tunnelQueue) },
(10)
{ (QActive *)&AO_ship, l_shipQueue, Q_DIM(l_shipQueue) },
(11)
{ (QActive *)&AO_missile, l_missileQueue, Q_DIM(l_missileQueue) }
(11)
/* make sure that the QF_active[] array matches QF_MAX_ACTIVE in qpn_port.h */
(12)
Q_ASSERT_COMPILE(QF_MAX_ACTIVE == Q_DIM(QF_active) - 1);
(12)
/*.....................................................................*/
(1) Every application C file that uses QP-nano must include the qpn_port.h
header file. This header file contains the specific adaptation of QP-nano to the given processor and compiler, which is called a port. The QP-nano port is typically located in the application directory.
(2) The bsp.h
header file contains the interface to the board support package and is located in the application directory.
(3) The game.h
header file contains the declarations of events and other facilities shared among the components of the “Fly ‘n’ Shoot” game. I will discuss this header file in the upcoming Section 12.2.3. This header file is located in the application directory.
(4-6) The application must provide storage for the event queues of all active objects used in the application. In QP-nano the storage is provided at compile time through the statically allocated arrays of events. Events are represented as instances of the QEvent
structure declared in the <qp>qpnincludeqepn.h
header file, included from qpn_port.h
. Each event queue of an active object can have a different length, and you need to decide this length based on your knowledge of the application. Refer to Chapters 6 and 7 for the discussion of sizing event queues.
(7) Every QP-nano application must provide the constant array QF_active[]
, which defines all active object control blocks in the application. The control block QActiveCB
structure groups together (1) the pointer to the corresponding active object instance, (2) the pointer to the event queue buffer of the active object, and (3) the length of the queue buffer.
In QP-nano, I use every opportunity to place data in ROM rather than in precious RAM. The QActiveCB
structure contains data elements known at compile time so that these elements can be placed in ROM as opposed to placing them in the active object structure (RAM). That way I save anywhere from 10 to 80 bytes of RAM, depending on the number of active objects and the pointer size of the target CPU.
The Q_ROM
macro is necessary on some CPU architectures to enforce placement of constant objects, such as the QF_active[]
array, in ROM. On Harvard architecture CPUs (such as 8051 or AVR), the code and data spaces are separate and are accessed through different CPU instructions. The const
keyword is not sufficient to place data in ROM, and various compilers often provide specific extended keywords to designate the code space for placing constant data, such as the “__code
” extended keyword in the IAR 8051 compiler. The macro Q_ROM
hides such nonstandard extensions. If you don't define Q_ROM
in qepn_port.h
, it will be defined to nothing in the qepn.h
platform-independent header file.
The Q_ROM_VAR
macro defines the compiler-specific directive for accessing a constant object in ROM. Many compilers for 8-bit MCUs provide variously sized pointers for accessing objects in various memories. Constant objects allocated in ROM often mandate the use of specific-size pointers (e.g., far
pointers) to get access to ROM objects. The macro Q_ROM_VAR
specifies the kind of the pointer to be used to access the ROM objects. An example of valid Q_ROM_VAR
macro definition is __far
(Freescale HC(S)08 compiler).
(8) The first entry (QF_active[0]
) corresponds to an active object priority of zero, which is reserved for the idle task and cannot be used for any active object.
(9-11) The QF_active[]
entries starting from one define the active object control blocks in the order of their relative priorities. The maximum number of active objects in QP-nano cannot exceed eight.
(12) This compile-time assertion (see Section 6.7.3 in Chapter 6) ensures that the dimension of the QF_active[]
array matches the number of active objects QF_MAX_ACTIVE
defined in the qpn_port.h
header file.
In QP-nano, QF_MAX_ACTIVE
denotes the exact number of active objects used in the application, as opposed to the full-version QP, where QF_MAX_ACTIVE
denotes just the configurable maximum number of active objects.
Note
All active objects in QP-nano must be defined at compile time. This means that all active objects exist from the beginning and cannot be started (or stopped) later, as is possible in the full-version QP.
The macro QF_MAX_ACTIVE
must be defined in the qpn_port.h
header file because QP-nano uses the macro to optimize the internal algorithms based on the number of active objects. The compile-time assertion in line 12 makes sure that the configured number of active objects does indeed match exactly the number of active object control blocks defined in the QF_active[]
array.
(13-15) The main()
function must first explicitly calls all active object constructors.
(17) At this point, you have initialized all components and have provided to the QF-nano framework all the information it needs to manage your application. The last thing you must do is to call the function QF_run()
to pass the control to the QF-nano framework.
Overall, the application startup is much simpler in QP-nano than in full-version QP. Neither event pools nor publish-subscribe lists are supported, so you don't need to initialize them. You also don't start active objects explicitly. The QF-nano framework starts all active objects defined in the QF_active[]
array automatically just after it gets control in QF_run()
.
The qpn_port.h
header file defines the QP-nano port and all configuration parameters for the particular application. Unlike in the full-version QP, QP-nano ports are typically defined at the application level. Also typically, the whole QP-nano port consists of just the qpn_port.h
header file. Listing 12.2 shows the complete qpn_port.h
file for the DOS version of the “Fly ‘n’ Shoot” game.
Listing 12.2. The qpn_port.h header file for the “Fly ‘n’ Shoot” game
(3)
/* maximum # active objects--must match EXACTLY the QF_active[] definition */
(6)
#define QF_INT_UNLOCK() enable()
(6)
/* Exact-width types (WG14/N843 C99 Standard) for Turbo C++/large model */
(7)
typedef signed char int8_t;
(7)
typedef signed int int16_t;
(7)
typedef signed long int32_t;
(7)
typedef unsigned char uint8_t;
(7)
typedef unsigned int uint16_t;
(7)
typedef unsigned long uint32_t;
(7)
#include <dos.h> /* DOS API */
(7)
#undef outportb /*don't use the macro because it has a bug in Turbo C++ 1.01*/
(8)
#include "qepn.h" /* QEP-nano platform-independent header file */
(9)
#include "qfn.h" /* QF-nano platform-independent header file */
(1) The macro Q_PARAM_SIZE
defines the size (in bytes) of the scalar event parameter. The allowed values are 0 (no parameter), 1, 2, or 4 bytes. If you don't define this macro in qpn_port.h
, the default of 0 (no parameter) will be assumed.
(2) The macro QF_TIMEEVT_CTR_SIZE
defines the size (in bytes) of the time event down-counter. The allowed values are 0 (no time events), 1, 2, or 4 bytes. If you don't define this macro in qpn_port.h
, the default of 0 (no time events) will be assumed.
(3) Defining the macro Q_NFSM
eliminates the code for the simple nonhierarchical FSMs.
(4) You must define the QF_MAX_ACTIVE
macro as the exact number of active objects used in the application. The provided value must be between 1 and 8 and must be consistent with the definition of the QF_active[]
array (see Listing 12.1(12)).
(5,6) The macros QF_INT_LOCK()
/QF_INT_UNLOCK()
define the task-level interrupt-locking policy for QP-nano. I discuss the QP-nano critical section in Section 12.3.2.
(7) Just like the full-version QP, QP-nano uses a subset of the C99-standard exact-width integer types. The legacy Turbo C++ 1.01 compiler, which I'm using here, is a prestandard compiler and does not provide the <stdint.h>
header file. In this case I just typedef
the six exact-width integer types used in QP-nano.
(8) The qpn_port.h
must include the QEP-nano event processor interface qepn.h
.
(9) The qpn_port.h
must include the QF-nano real-time framework interface qfn.h
.
Note
The
qpn_port.h
header file in Listing 12.2 implicitly configures QP-nano to use the built-in cooperative “vanilla” kernel. The other alternative, which is the preemptive QK-nano kernel, is configured automatically when you include theqkn.h
QK-nano interface in theqpn_port.h
header file.
In QP-nano, event signals are enumerated just as in the full-version QP. The only limitation is that signal values in QP-nano cannot exceed 255, because signals are always represented in a single byte.
In QP-nano, you cannot specify arbitrary event parameters, so you don't derive events as you do in full-version QP. Instead, all events in QP-nano are simply instances of the QEvent
structure, which contains the fixed-size scalar parameter configured according to your definition of Q_PARAM_SIZE
(see Listing 12.2(2)).
On the other hand, active objects in QP-nano are derived from the QActive
base structure, just like they are in the full-version QP. One of the main concerns with respect to active object structures is to keep them encapsulated. In all QP-nano examples, including the “Fly ‘n’ Shoot” game, I demonstrate a technique to keep the active object structures and state machines completely opaque. I describe this technique in the explanation section following Listing 12.3, which shows the header file game.h
included by all components of the “Fly ‘n’ Shoot” application.
Listing 12.3. Signals and active objects for the “Fly ‘n’ Shoot” game (the game.h header file)
(2) TIME_TICK_SIG = Q_USER_SIG, /* published from tick ISR */
(2)
PLAYER_TRIGGER_SIG, /* published by Player (ISR) to trigger the Missile */
(2)
PLAYER_QUIT_SIG, /* published by Player (ISR) to quit the game */
(2)
GAME_OVER_SIG, /* published by Ship when it finishes exploding */
(2)
PLAYER_SHIP_MOVE_SIG, /* posted by Player (ISR) to the Ship to move it */
(2)
BLINK_TIMEOUT_SIG, /* signal for Tunnel's blink timeout event */
(2)
SCREEN_TIMEOUT_SIG, /* signal for Tunnel's screen timeout event */
(2)
TAKE_OFF_SIG, /* from Tunnel to Ship to grant permission to take off */
(2)
HIT_WALL_SIG, /* from Tunnel to Ship when Ship hits the wall */
(2)
HIT_MINE_SIG, /* from Mine to Ship or Missile when it hits the mine */
(2)
SHIP_IMG_SIG, /* from Ship to the Tunnel to draw and check for hits */
(2)
MISSILE_IMG_SIG, /* from Missile the Tunnel to draw and check for hits */
(2)
MINE_IMG_SIG, /* sent by Mine to the Tunnel to draw the mine */
(2)
MISSILE_FIRE_SIG, /* sent by Ship to the Missile to fire */
(2)
DESTROYED_MINE_SIG, /* from Missile to Ship when Missile destroyed Mine */
(2)
EXPLOSION_SIG, /* from any exploding object to render the explosion */
(2)
MINE_PLANT_SIG, /* from Tunnel to the Mine to plant it */
(2)
MINE_DISABLED_SIG, /* from Mine to Tunnel when it becomes disabled */
(2)
MINE_RECYCLE_SIG, /* sent by Tunnel to Mine to recycle the mine */
(2)
SCORE_SIG /* from Ship to Tunnel to adjust game level based on score */
(2)
/* active objects .......................................................*/
(8)
void Missile_ctor(uint8_t speed);
(8)
/* common constants and shared helper functions ...........................*/
(1) All signals are defined in one enumeration, which automatically guarantees the uniqueness of signals.
(2) Note that the user signals must start with the offset Q_USER_SIG
to avoid overlapping the reserved QEP-nano signals.
(3-5) I declare all active object instances in the system as extern
variables. These declarations are necessary for the initialization of the QF_active[]
array (see Listing 12.1(12)).
Note>
The active object structures (e.g.,
struct TunnelTag
) do not need to be defined globally in the application header file. TheQF_active[]
array needs only pointers to the active objects (see Listing 12.1(9-11)), which the compiler can resolve without knowing the full definition of the active object structure.
I never declare active object structures globally. Instead, I declare the active object structures in the file scope of the specific active object module (e.g., struct TunnelTag
is declared in the tunnel.c
file scope). That way I can be sure that each active object remains fully encapsulated.
(6-8) Every active object in the system must provide a “constructor” function, which initializes the active object instance. These constructors don't take the “me
” pointers, because they have access to the global active object instances (see (3-5)). However, the constructors can take some other initialization parameters. For instance, the Missile_ctor()
takes the Missile speed parameter. Listing 12.1(13-15) shows that the constructors are called right at the beginning of main()
.
Implementing active objects with QP-nano is very similar to the full-version QP. As before, you derive the concrete active object structures from the QActive
base structure provided in QP-nano. Your main job is to elaborate the state machines of the active objects, which is also very similar to the full-version QP. The only important difference is that state-handler functions in QP-nano do not take the event pointer as the second argument. In fact, QP-nano state handlers take only one argument—the “me
” pointer. The current event is embedded inside the state machine itself and is accessible via the “me
” pointer. QP-nano provides macros Q_SIG()
and Q_PAR()
to conveniently access the signal and the scalar parameter of the current event, respectively.
Listing 12.4 shows the implementation of the Ship active object from the “Fly ‘n’ Shoot” game, which illustrates all aspects of implementing active objects with QP-nano. Correlate this implementation with the Ship state diagram in Figure 1.6 as well as with the QP implementation described in Section 1.7 in Chapter 1.
Listing 12.4. The Ship active object definition (file ship.c); boldface indicates QP-nano facilities
/* local objects ----------------------------------------------------------*/
(4)
static QState Ship_active (Ship *me);
(4)
static QState Ship_parked (Ship *me);
(4)
static QState Ship_flying (Ship *me);
(4)
static QState Ship_exploding(Ship *me);
(4)
/* global objects -------------------------------------------------------*/
(5)
/*......................................................................*/
(6) QActive_ctor(&me->super, (QStateHandler)&Ship_initial);
(6)
/* HSM definition -------------------------------------------------------*/
(7) return Q_TRAN(&Ship_active); /* top-most initial transition */
(7)
/*......................................................................*/
(13) return Q_SUPER(&QHsm_top);
(13)
/*......................................................................*/
(14) QActive_post((QActive *)&AO_Tunnel, SCORE_SIG, me->score);
(14)
/* tell the Tunnel to draw the Ship and test for hits */
(15) QActive_post((QActive *)&AO_Tunnel, SHIP_IMG_SIG,
(15) & ((QParam)SHIP_BMP << 16)
(15) & & | ((QParam)me->y << 8));
(15)
++me->score; /* increment the score for surviving another tick */
(15)
if ((me->score % 10) == 0) { /* is the score "round"? */
(15) QActive_post((QActive *)&AO_Tunnel, SCORE_SIG, me->score);
(15)
case PLAYER_TRIGGER_SIG: { /* trigger the Missile */
(15) QActive_post((QActive *)&AO_Missile, MISSILE_FIRE_SIG,
(15) | (((QParam)me->y + SHIP_HEIGHT - 1) << 8));
(15)
case DESTROYED_MINE_SIG: {
(15)
/* the score will be sent to the Tunnel by the next TIME_TICK */
(2) The Ship
active object structure derives from the framework structure QActive
, as described in the sidebar “Single Inheritance in C” in Chapter 1.
(3) The Ship_initial()
function defines the topmost initial transition in the Ship
state machine. The only difference from the full-version QP is that the initial pseudostate function does not take the initial event parameter.
(4) The state-handler functions in QP-nano also don't take the event parameter. (In QP-nano, the current event is embedded in the state machine.) As in the full-version QP, a state-handler function in QP-nano returns the status of the event handling.
(5) In this line I allocate the global AO_Ship
active object. Note that actual structure definition for the Ship
active object is accessible only locally at the file scope of the ship.c
file.
Note
QP-nano assumes that all global or static variables without explicit initialization value are initialized to zero upon system startup, which is a requirement of the ANSI-C standard. You should make sure that your startup code clears the static variables data section (a.k.a. the Block Started by Symbol section, or BSS) before calling
main()
.
(6) As always, the derived structure is responsible for initializing the part inherited from the base structure. The “constructor” of the base class QActive_ctor()
puts the state machine in the initial pseudostate &Ship_initial
. The constructor also initializes the priority of the active object based on the QF_active[]
array.
(7) The topmost initial transition to state Ship_active
is specified with the Q_TRAN()
macro.
(8) Every state handler is structured as a switch
statement that discriminates based on the signal of the event, which in QP-nano is obtained by the macro Q_SIG(me)
.
(9) You designate the target of a nested initial transition with the Q_TRAN()
macro.
(10,11) You access the data members of the Ship
state machine via the “me
” parameter of the state-handler function. You access the event parameters via the Q_PAR(me)
macro. Note that in this case two logical event parameters are actually from the scalar QP-nano parameter. The x coordinate of the Ship is sent in the least significant byte, and the y coordinate in the next byte.
(12) You terminate the case
statement with “return Q_HANDLED()
” which informs QEP-nano that the internal transition has been handled.
(13) The final return
from a state-handler function designates the superstate of that state by means of the macro Q_SUPER()
, which is exactly the same as in the full-version QP. QEP-nano provides the “top” state as a state-handler function QHsm_top()
, and therefore the Ship_active()
state handler uses the pointer &QHsm_top
as the argument to the Q_SUPER()
macro (see the Ship state diagram in Figure 1.6 in Chapter 1).
(14) The function QActive_post()
posts the specified event signal and parameter directly to the recipient active object. Direct event posting is the only event delivery mechanism supported in QP-nano.
(15) The event posting demonstrates how to combine several logical event parameters into the single scalar parameter managed by QP-nano. Of course, you must be careful not to overflow the dynamic range of the QP-nano parameter configured with the Q_PARAM_SIZE
macro (see Listing 12.2(1)).
(16) You designate the target of a transition with the Q_TRAN()
macro.
(17) The state “flying” (see Figure 1.6 in Chapter 1) nests in the state “active,” so the state handler Ship_flying()
designates the superstate by returning Q_SUPER(&Ship_active)
.
QP-nano maintains a single private time event (timer) for each active object in the system. These timers can be programmed (armed) to generate the reserved Q_TIMEOUT
events after the specified number of clock ticks. Internally, QP-nano represents a time event only as a down-counter (typically 2 bytes of RAM). Only single-shot time events are supported because a periodic time event would require twice as much RAM to store the period. The Q_TIMEOUT
signal is predefined in QP-nano and is one of the reserved signals (similar to Q_ENTRY
, Q_EXIT
, and Q_INIT
).
Listing 12.5 shows a fragment of the Tunnel active object state machine that uses the QP-nano time event for blinking the “Game Over” text in the “game_over” state.
Listing 12.5. Using a QP-nano Time Event (file tunnel.c)
(1) QActive_arm((QActive *)me, BSP_TICKS_PER_SEC/2); /* 1/2 sec */
(1)
me->blink_ctr = 5*2; /* 5s timeout */
(1)
BSP_drawNString((GAME_SCREEN_WIDTH - 6*9)/2, 0, "Game Over");
(2) QActive_disarm((QActive *)me);
(2)
BSP_updateScore(0); /* clear the score on the display */
(4) QActive_arm((QActive *)me, BSP_TICKS_PER_SEC/2); /* 1/2 sec */
(4)
BSP_drawNString((GAME_SCREEN_WIDTH - 6*9)/2, 0,
(4)
(((me->blink_ctr & 1) != 0)
(4)
if ((--me->blink_ctr) == 0) { /* blinked enough times? */
(1) The time event associated with the active object is armed to expire after the specified number of clock ticks. Usually, arming of the time event occurs in the entry action to a state.
Note
While arming a time event, you must be careful not to exceed the preconfigured dynamic range of the internal down-counter. The dynamic range is configurable by means of the macro
QF_TIMEEVT_CTR_SIZE
in theqpn_port.h
header file (see Listing 12.2(2)).
(2) The time event can be disarmed. The disarming usually occurs in the exit action from a state. At any moment you can also rearm a running timer by calling QActive_arm()
, which simply replaces the value of the timer down-counter.
(3) After the preprogrammed timeout, the timer generates the Q_TIMEOUT
event, which you can handle just like any other event dispatched to the state machine.
(4) You achieve a periodic timeout by arming the one-shot time event every time it expires. Note that often the period is a compile-time constant, which takes no precious RAM.
QP-nano calls several platform-specific callback functions that you must define, typically in the board support package (BSP). Apart from the callbacks, you must also define all the interrupt service routines (ISRs), explained in more detail in Sections 12.5.1 and 12.6.4. Listing 12.6 shows the most important elements of the BSP for the “Fly ‘n’ Shoot” game in the DOS environment.
Listing 12.6. BSP for the “Fly ‘n’ Shoot” game under DOS (file bsp.c)
(1) static void interrupt tmrISR(void) { /* 80x86 enters ISRs with int. locked */
(3) QActive_postISR((QActive *)&AO_Tunnel, TIME_TICK_SIG, 0);
(5) QActive_postISR((QActive *)&AO_Missile, TIME_TICK_SIG, 0);
(5)
outportb(0x20, 0x20); /* write EOI to the master PIC */
(5)
/*.......................................................................*/
(5)
/*.......................................................................*/
(5)
void BSP_drawBitmap(uint8_t const *bitmap, uint8_t width, uint8_t height) {
(5)
Video_drawBitmapAt(0, 8, bitmap, width, height);
(5)
/*.......................................................................*/
(5)
void BSP_drawNString(uint8_t x, uint8_t y, char const *str) {
(5)
Video_drawStringAt(x, 8 + y*8, str);
(5)
/*.......................................................................*/
(5)
void BSP_updateScore(uint16_t score) {
(5)
Video_clearRect(68, 24, 72, 25, VIDEO_BGND_RED);
(5)
Video_printNumAt(68, 24, VIDEO_FGND_YELLOW, score);
(5)
/*.......................................................................*/
(6)
/* save the original DOS vectors ... */
(6)
l_dosTmrISR = getvect(TMR_VECTOR);
(6)
l_dosKbdISR = getvect(KBD_VECTOR);
(6)
setvect(TMR_VECTOR, &tmrISR);
(6)
setvect(KBD_VECTOR, &kbdISR);
(6)
/*.......................................................................*/
(7)
/* restore the original DOS vectors ... */
(7)
if (l_dosTmrISR != (void interrupt (*)(void))0) { /* DOS vectors saved? */
(7)
setvect(TMR_VECTOR, l_dosTmrISR);
(7)
setvect(KBD_VECTOR, l_dosKbdISR);
(7)
_exit(0); /* exit to DOS */
(7)
/*.......................................................................*/
(8) void QF_onIdle(void) { /* see NOTE01 */
(8)
/*-----------------------------------------------------------------------*/
(9) void Q_onAssert(char const Q_ROM * const Q_ROM_VAR file, int line) {
(1) Usually you can use the compiler-generated ISRs with QP-nano. Here I use the capability of the Turbo C++ 1.01 compiler to generate ISRs, which are designated with the extended keyword “interrupt.
”
(2) Just as in the full-version QP, you need to call QF_tick()
from the system clock-tick ISR.
(3-5) QP-nano does not support publishing events. Instead, you directly post the TIME_TICK
event to all active objects that need to receive it.
Note
QP-nano provides different services for ISRs and for the task level. You can only call two QP-nano functions from interrupts:
QF_tick()
andQActive_postISR()
. Conversely, you should never call these two functions from the task level. This separation of APIs is closely related to the separate interrupt-locking policies for tasks and interrupts in QP-nano. I discuss the QP-nano interrupt-locking policy in Section 12.3.2.
(6) The callback function QF_onStartup()
is invoked by QP-nano after all active object state machines are started but before the event loop starts executing. QF_onStartup()
is intended for configuring and starting interrupts.
(7) The function QF_stop()
stops QF-nano and returns control back to the operating system. This function is rarely used in deeply embedded systems, because a bare-metal system simply has no operating system to return to. In the DOS version, however, the QF_stop()
function restores the original interrupts and exits to DOS.
(8) This version of the “Fly ‘n’ Shoot” application has been implicitly configured to use the “vanilla” cooperative kernel (see the final note in Section 12.2.2). The vanilla kernel works in QP-nano exactly as described in Section 6.3.7 in Chapter 6. In particular, the QF_onIdle()
callback is invoked with interrupts locked and must always unlock interrupts.
(9) Finally, in every QP-nano application you need to provide the assertion-failure callback Q_onAssert()
. QP-nano uses the same embedded-systems-friendly assertions as the full-version QP (see Section 6.7.3 in Chapter 6).
As shown in Figure 12.2, building a QP-nano application is simpler than the full-version QP. You merely need to add two QP-nano source files qepn.c
and qfn.c
to the project, and you need to instruct the compiler to search for the header files in the <qp>qpninclude
directory. (If you use QK-nano, you additionally need to add the qkn.c
source file.) The project file for building the “Fly ‘n’ Shoot” game for DOS with the Turbo C++ 1.01 compiler is found in <qp>qpnexamples80x86 cpp101gameGAME.PRJ
. Similarly, the project file to build the game for Cortex-M3 with the IAR compiler is found in C:softwareqpnexamplescortex-m3iargame-ev-lm3s811game.ewp
.
Figure 12.3 shows the main QP-nano elements and their relation to the application-level code, such as the “Fly ‘n’ Shoot” game example. As all real-time frameworks, QP-nano provides the central base class QActive
for derivation of concrete2 Concrete class is the OOP term and denotes a class that has no abstract operations or protected constructors. Concrete class can be instantiated, as opposed to abstract class, which cannot be instantiated. active objects. The QActive
class is abstract, which means that it is not intended for direct instantiation but rather only for derivation of active object structures, such as Ship
, Missile
, and Tunnel
shown in Figure 12.3 (see also the sidebar “Single Inheritance in C” in Chapter 1).
By default, the QActive
class derives from the QHsm
hierarchical state machine class defined in the QEP-nano event processor. This means that by virtue of inheritance, active objects are HSMs and inherit the init()
and dispatch()
state machine interface. QActive
also contains the active object priority, which identifies the active object thread of execution, as well as an event queue and a time event counter.
As an option, you can configure QP-nano to derive QActive
from the simpler, nonhierarchical state machine class QFsm
. By doing this, you eliminate the hierarchical state machine code, which can save you some 300-500 bytes of ROM, depending on the code density of your target CPU.
The QEvent
class represents events in QP-nano. The event signal QSignal
is typedef
’ed to a byte (uint8_t
). Also embedded directly in the event is the single scalar event parameter. You cannot add any other parameters to the event by derivation. The size of the event parameter is configurable with the macro Q_PARAM_SIZE
. In QP-nano, the state machine class QHsm
(as well as the simpler QFsm
) contains the current event. The event inside the state machine counts towards the event queue length.
QP-nano also introduces the active object control block structure QActiveCB
, which contains read-only data elements known at compile time (see Listing 12.1(7)). Every QP-application must define the constant array QF_active[]
that contains initialized active object control blocks for all active objects in the application. The length of the QF_active[]
array must match exactly the QF_MAX_ACTIVE
macro in the qpn_port.h
header file. The ordering of the active object control blocks in the QF_active[]
array determines the priorities of the active objects.
Listing 12.7 shows the directories and files comprising QP-nano. Note that the <qp>qpnexamples
directory contains several QP-nano executable examples for various embedded targets. In particular, I provide all the state design patterns described in Chapter 5 in the <qp>qpnexamples80x86 cpp101
directory. The QP-nano directory <qp>qpndoxygen
also contains the “QP-nano Reference Manual” generated from the source code by the Doxygen utility. The reference manual is available in HTML and CHM Help formats.
Listing 12.7. QP-nano code organization
| +-qassert.h - QP-nano assertions (
Section 6.7.3 in Chapter 6)
+-source - QP-nano platform-independent source code (*.C files)
| | +-comp - "Orthogonal Component" pattern (
Chapter 5)
| | +-defer - "Deferred Event" pattern (
Chapter 5)
| | +-dpp - DPP application (
Chapter 9)
| | | +-GAME.PRJ - Turbo C++ project to build the Debug version
| | +-history - "Transition to History" pattern (
Chapter 5)
| | +-hook - "Ultimate Hook" pattern (
Chapter 5)
| | +-pelican - PELICAN crossing example (see
Section 12.7)
| | +-qhsmtst - QHsmTst example (
Section 2.3.15 in Chapter 2)
| | +-reminder - "Reminder" pattern (
Chapter 5)
| | +-game-qk-ev-lm3s811 - "Fly ‘n’ Shoot" game example with QK-nano
| | +-pelican-ev-lm3s811 - PELICAN crossing example (see
Section 12.7)
| | +-pelican-qk-ev-lm3s811 - PELICAN crossing example with QK-nano
| | +-bomb-eZ430 - Time bomb example (
Section 3.6 in Chapter 3)
| | +-pelican-eZ430 - PELICAN crossing example (see
Section 12.7)
| | +-pelican-qk-eZ430 - PELICAN crossing example with QK-nano
| | +-qhsmtst-eZ430 - QHsmTst example (
Section 2.3.15 in Chapter 2)
| | +-index.html - The starting HTML page for "QP-nano Reference Manual"
| +-Doxyfile - Doxygen configuration file to generate the Manual
QP-nano, just like the full-version QP, achieves atomic execution of critical sections by briefly locking and unlocking interrupts. However, unlike the full-version QP, QP-nano uses a separate interrupt-locking policy for the task-level code and a different policy for ISRs. The ISR policy is used in the QP-nano functions QActive_postISR()
and QF_tick()
. The task-level policy is used in all other QP-nano services.
Note
Because the interrupt-locking policies for active objects and ISRs are different, you should never call the QP-nano functions intended for ISRs (
QActive_postISR()
andQF_tick()
) inside tasks, and conversely, you should never call task-level QP-nano functions inside ISRs.
For the task level (code called from active objects), QP-nano employs the simple unconditional interrupt locking and unlocking policy, as described in Section 7.3.2 of Chapter 7. In this policy, interrupts are always unconditionally unlocked upon exit from a critical section, regardless of whether they were locked or unlocked before entry to the critical section. The pair of QP-nano macros QF_INT_LOCK()
/QF_INT_UNLOCK()
, shown in Listing 12.8, encapsulates the actual mechanism the compiler provides to lock and unlock interrupts from C. You need to consult the documentation of your CPU and the compiler to find how to achieve interrupt locking and unlocking in your particular system.
The simple task-level policy of “unconditional locking and unlocking interrupts” matches very well the architecture of low-end MCUs. The critical section is fast and straightforward, but does not allow nesting of critical sections. QP-nano never nests critical sections internally, but you should be careful not to nest critical sections in your own code.
For the ISR level, QP-nano offers three critical section implementation options. The first default option is to do nothing, meaning that interrupts are neither locked nor unlocked inside ISRs. This policy is appropriate when interrupts cannot nest, because in this case the whole ISR represents a critical section of code, unless of course you explicitly unlock interrupts inside the ISR body. But unlocking interrupts inside ISRs is often not advisable, because most low-end micros aren't really designed to handle interrupt nesting. Low-end MCUs typically lack a fully prioritized interrupt controller and cannot afford the bigger stack requirements caused by nesting interrupts.
Note
Unlocking interrupts inside ISRs without an interrupt controller can cause all sorts of priority inversions, including the pathological case of an interrupt preempting itself recursively.
In case you can allow interrupt nesting, QP-nano offers two more interrupt-locking policies for ISRs. The first of these options is to use the task-level interrupt policy inside ISRs. As shown in Listing 12.9, you select this policy by defining the macro QF_ISR_NEST
. In this case the function QActive_postISR()
(as well as QF_tick()
, which calls QActive_postISR()
), unconditionally locks interrupts with the macro QF_INT_LOCK()
and unlocks with QF_INT_UNLOCK()
. Of course, to avoid nesting critical sections, you are responsible for making sure that interrupts are unlocked before calling QActive_postISR()
or QF_tick()
from your ISRs.
Finally, QP-nano also supports the more advanced policy of “saving and restoring interrupt status” (see Section 7.3.1 in Chapter 7). Listing 12.10 shows an example of this policy. This policy is the most expensive but also the most robust because interrupts are only unlocked upon exit from the critical section if they were unlocked upon entry.
(1) The macro QF_ISR_NEST
tells QP-nano that interrupts can nest.
(2) The macro QF_ISR_KEY_TYPE
indicates a data type of the “interrupt key” variable, which holds the interrupt status. Defining this macro in the qpn_port.h
header file indicates to the QF-nano framework that the policy of “saving and restoring interrupt status” is used for ISRs.
(3) The macro QF_ISR_LOCK()
encapsulates the mechanism of interrupt locking. The macro takes the parameter key_
, into which it saves the interrupt lock status.
(4) The macro QF_ISR_UNLOCK()
encapsulates the mechanism of restoring the interrupt status. The macro restores the interrupt status from the argument key_
.
As an example, where the “saving and restoring interrupt status” interrupt-locking policy for ISRs is useful, consider the MCUs based on the popular ARM7 or ARM9 cores such as the AT91 family from Atmel, the LPC family from NXP, the TMS470 family from TI, the STR7 and STR9 families from ST, and others. The ARM7/ARM9 architecture supports two types of interrupts called FIQ and IRQ. In most ARM-based MCUs, the IRQ interrupt is typically prioritized in a vectored interrupt controller, but the FIQ typically is not. This means that you should never unlock interrupts inside the FIQ interrupt, but you should unlock interrupts inside IRQs, to allow the priority controller do its job. The advanced policy of “saving and restoring interrupt status” can be used safely in both FIQ and IRQ interrupts (see also [Samek 07a]).
Just like the full-version QP, QP-nano contains an hierarchical event processor called QEP-nano. QEP-nano supports both hierarchical and nonhierarchical state machines. The only difference between the QEP-nano and full-version QEP is that the current event in QEP-nano is directly embedded in the state machine. That way, the current event is accessible to the state machine via the “me
” pointer and does not need to be passed as a parameter to the state-handler functions. Other than that, however, QEP-nano supports the same set of features as the full-version QEP, including fully hierarchical state machines with entry and exit actions and nested initial transitions. Listing 12.11 shows the declaration of the QHsm
base structure (class) that serves for derivation of HSMs in QP-nano.
Listing 12.11. QHsm structure and related functions (file <qp>qpnincludeqepn.h)
(1)
typedef uint8_t QState; /* status returned from a state-handler function */
(3)
QStateHandler state; /* current active state of the HSM (private) */
(4)
QEvent evt; /* currently processed event in the HSM (protected) */
(5)
#define QHsm_ctor (me_, initial_) ((me_)->state = (initial_))
(18)
(((QFsm *)me)->state = (QStateHandler)(target_), Q_RET_TRAN)
(19)
(((QFsm *)me)->state = (QStateHandler)(super_), Q_RET_SUPER)
(1) This typedef
defines QState
as a byte that conveys the status of the event handling to the event processor (see also lines (12-15)).
(2) This typedef
defines the QStateHandler
as a pointer to state-handler function. As you can see, the state-handler functions in QP-nano take only the “me
” pointer but no event parameter.
(3) The QHsm
structure stores the state-variable state
, which is a pointer to state-handler function. Typically, a pointer to function requires just 2 or 4 bytes of RAM depending on given CPU and C compiler options.
(4) In QP-nano, the QHsm
structure also stores the current event evt
, which can take between 1 and 5 bytes of RAM, depending on the configuration macro Q_PARAM_SIZE
(see Listing 12.2(1)).
(5) The QHsm
“constructor” function-like macro initializes the state variable to the initial-pseudostate function that defines the initial transition. Note that the initial transition is not actually executed at this point.
(6) The QHsm_init()
function triggers the initial transition in the state machine.
(7,8) The QHsm_dispatch()
function dispatches one event to the state machine.
Note
Some compilers for 8-bit MCUs, most notably the Keil C51 compiler for 8051, don't generate ANSI-C compliant reentrant functions by default due to the limited stack architecture in 8051. These compilers allow dedicating specific functions to be reentrant with a special extended keyword (such as “
reentrant
” for Keil C51). The macroQ_REENTRANT
is defined to nothing by default, to work with ANSI-C compliant compilers, but can be defined to “reentrant
” to work with Keil C51 and perhaps other embedded compilers.
(9) The QHsm_top()
function is the hierarchical state handler for the top state. The application-level state-handler functions that don't explicitly nest in any other state return the &QHsm_top
pointer to the event processor.
(10) The Q_SIG()
macro provides access to the signal of the current event embedded in the state machine.
(11) The Q_PAR()
macro provides access to the scalar parameter of the current event embedded in the state machine. The macro is only defined if the event parameter is configured.
(12-15) These constants define the status returned from state-handler functions to the QEP-nano event processor. The status values are identical in QEP-nano as in the full-version QEP.
(16) A state-handler function returns the macro Q_HANDLED()
whenever it handles the current event.
(17) A state-handler function returns the macro Q_IGNORED()
whenever it ignores (does not handle) the current event.
(18) The Q_TRAN
() macro encapsulates the transition, exactly as it is done in the full-version QEP. The Q_TRAN
() macro is defined using the comma expression. A comma expression is evaluated from left to right, whereas the type and value of the whole expression is the rightmost operand. The rightmost operand is in this case the status of the operation (transition), which is returned from the state-handler function. The pivotal aspect of this design is that the Q_TRAN()
macro can be used with respect to structures derived (inheriting) from QFsm
or QHsm
, which in C requires explicit casting (upcasting) to the QFsm
base structure (see the sidebar “Single Inheritance in C” in Chapter 1).
(19) The Q_SUPER
() macro serves for specifying the superstate, exactly as it is done in the full-version QEP. The Q_SUPER
() macro is very similar to the Q_TRAN()
macro except Q_SUPER()
returns the different status to the event processor.
As shown in Figure 12.3, the QF-nano real-time framework provides the base structure QActive
for deriving application-specific active objects. QActive
combines the following three essential elements:
Listing 12.12 shows the declaration of the QActive
base structure and related functions.
Listing 12.12. The QActive base class for derivation of active objects (file <qp>qpnincludeqfn.h)
(3)
uint8_t prio; /* active object priority 1..QF_MAX_ACTIVE */
(6)
uint8_t nUsed; /* number of events currently present in the queue */
(8)
#define QActive_ctor(me_, initial_) QHsm_ctor(me_, initial_)
(9)
#define QActive_ctor(me_, initial_) QFsm_ctor(me_, initial_)
(10)
void QActive_post (QActive *me, QSignal sig, QParam par);
(11)
void QActive_postISR(QActive *me, QSignal sig, QParam par);
(14)
#if (QF_TIMEEVT_CTR_SIZE == 1) /* single-byte tick counter? */
(15)
#define QActive_arm(me_, tout_) ((me_)->tickCtr = (QTimeEvtCtr)(tout_))
(16)
#define QActive_disarm(me_) ((me_)->tickCtr = (QTimeEvtCtr)0)
(18)
void QActive_disarm(QActive *me);
(1) By default (when the macro QF_FSM_ACTIVE
is not defined), the QActive
structure derives from the QHsm
base structure, meaning that active objects are hierarchical state machines in QP-nano.
(2) However, when you define the macro QF_FSM_ACTIVE
in qpn_port.h
, the QActive
structure derives from the QFsm
base structure. In this case, active objects are traditional “flat” state machines.
(3) Active object remembers its unique priority, which in QP-nano is the index into the QF_active[]
array. Priority numbering in QP-nano is identical as in full-version QP. The lowest possible task priority is 1 and higher-priority values correspond to higher-urgency active objects. The maximum allowed active object priority is determined by the macro QF_MAX_ACTIVE
, which in QP-nano cannot exceed 8. Priority level zero is reserved for the idle loop.
(4,5) These are the head and tail indices for the event queue buffer.
(6) The nUsed
data member represents the number of events currently present in the queue. This number includes the extra event embedded in the state machine itself, not just the number of events in the ring buffer, so that nUsed
of zero indicates an empty queue.
(7) The time event down-counter is only present when you define QF_TIMEEVT_CTR_SIZE
in qpn_port.h
. The member ‘tickCtr
’ is the internal down-counter decremented in every QF_tick()
invocation (see the next section). The time event is posted when the down-counter reaches zero.
(8,9) The active object constructor boils down to calling the base class constructor, which is either QHsm_ctor()
or QFsm_ctor()
, depending on the definition of the macro QF_FSM_ACTIVE
.
(10-13) The signatures of functions QActive_post()
and QActive_postISR()
depend on the presence or absence of the event parameter.
(14) The QP-nano function QF_tick()
(see the next section) handles the timeout events. This function is only provided when time events are configured.
(15,16) On any CPU with the word size of at least 8 bits, setting a single-byte variable is atomic. In this case the QActive_arm()
and QActive_disarm()
operations don't need to use a critical section. For speed, they are implemented as macros.
(17,18) For multibyte tick counters I assume that they are updated by multiple machine instructions. In this case the QActive_arm()
and QActive_disarm()
operations are declared as functions that use critical sections inside.
To manage time events QP-nano requires that you invoke the QF_tick()
function from a periodic time source called the system clock tick (see Chapter 6, “System Clock Tick”). The system clock tick typically runs at a rate between 10Hz and 100Hz.
Listing 12.13 shows the implementation of QF_tick()
. In QP-nano, this function can be called only from the clock-tick ISR. QF_tick()
must always run to completion and never preempt itself. In particular the clock-tick ISR that calls QF_tick()
must not be allowed to preempt itself. In addition, QF_tick()
should never be called from two different ISRs, which potentially could preempt each other.
Listing 12.13. QF_tick() function (file <qp>qpnsourceqfn.c)
(1) static uint8_t p; /* declared static to save stack space */
(4) static QActive *a; /* declared static to save stack space */
(1) The temporary variable ‘p
’ (priority of an active object) is declared static
to save the stack space.
(2) All active objects are scanned starting from the highest-priority QF_MAX_ACTIVE
, which is also the exact number of active objects in the application (see Listing 12.1(12)).
(3) I use the do
loop to avoid checking the loop condition the first time through. The number of active objects QF_MAX_ACTIVE
is guaranteed to be at least one, so I don't need to check it.
(4) The temporary variable ‘a
’ (a pointer to active object) is declared static
to save the stack space.
(5) The active object pointer is loaded from the ROM array QF_active[]
, which maps active object priorities to active object pointers.
(6) The time event of a given active object is running if the tick counter is nonzero.
(7) The tick counter is decremented and tested against zero. By reaching zero, the time event automatically disarms itself.
(8,9) QF_tick()
posts the Q_TIMEOUT_SIG
event to the active object that owns the counter by means of the QActive_postISR()
function. For that reason QF_tick()
can be called only from the ISR context.
(10) The loop continues for all active object priorities above zero.
Each active object in QP-nano has its own event queue. The queue consists of one event located inside the QActive
structure from which all active objects derive (see Section 12.3.4), plus a ring buffer of events that is allocated outside of the active object.
Figure 12.4 shows the data structures that QP-nano uses to manage event queues of active objects. The constant array QF_active[]
stores the active object “control blocks,” which are instances of the QActiveCB
structure. Each QF_active[]
element contains the pointer to the active object act
, the pointer to the ring buffer queue
, and the index of the last element of the ring buffer end
. All these elements are initialized at compile time for each active object.
The QActive
structure stores the event queue elements that are changing at runtime. The queue storage consists of the external, user-allocated ring buffer queue
plus the current event evt
stored inside the state machine (see Listing 12.11(4)). All events dispatched to the state machine must go through the “current event” evt
data member, which is indicated as dashed lines in Figure 12.4. This extra location outside the ring buffer optimizes queue operation by frequently bypassing buffering, because in most cases queues alternate between empty and nonempty states with just one event present in the queue at a time.
Note
In extreme situations when the adequate queue depth is only one event, the whole ring buffer can be eliminated entirely. In such a case, you don't allocate the ring buffer and you use
NULL
as the queue pointer and zero as a valid queue length to initialize theQF_active[]
array (see Listing 12.1(9-11)).
The ring-buffer indices head
and tail
as well as end
from QF_active[]
are relative to the queue
pointer. These indices manage a ring buffer queue that the clients must preallocate as a contiguous array of events of type QEvent
. Events are always extracted from the buffer at the tail
index. New events are inserted at the head
index, which corresponds to FIFO queuing. The tail
index is always decremented when the event is extracted, as is the head
index when an event is inserted. The end
index limits the range of the head
and tail
indices that must “wrap around” to end
once they reach zero. The effect is a counterclockwise movement of the head
and tail
indices around the ring buffer, as indicated by the arrow in Figure 12.4.
QP-nano contains a cooperative “vanilla” kernel and a preemptive RTC kernel called QK-nano. To perform efficient scheduling in either one of these kernels, QP-nano maintains the global status of all active object event queues in the application in the single byte called the QF_readySet_
. As shown in Figure 12.5, QF_readySet_
is a bitmask that represents a “ready-set” of all nonempty event queues in the system. Each bit in the QF_readySet_
byte corresponds to one active object. For example, the bit number n
is 1 in QF_readySet_
if and only if the event queue of the active object with priority n+1
is nonempty (bits are traditionally numbered starting from 0 while priorities in QP-nano are numbered from 1). With this representation, posting an event to an empty queue with priority p
sets the bit number p-1
in the QF_readySet_
bitmask to 1. Conversely, removing the last event from the queue with priority q
clears the bit number q-1
in the QF_readySet_
bitmask. Obviously, all operations on the global QF_readySet_
bitmask must occur inside critical sections.
Listing 12.14 shows the implementation of the QActive_post()
function, which is used for posting events from one active object to another. You should never use this function to post events from the ISRs, because it uses task-level interrupt locking policy.
Listing 12.14. QActive_post() function (file <qp>qpnsourceqfn.c)
(1)
void QActive_post(QActive *me, QSignal sig, QParam par) {
(3)
if (me->nUsed == (uint8_t)0) { /* is the queue empty? */
(6)
QF_readySet_ |= Q_ROM_BYTE(l_pow2Lkup[me->prio]); /* set the bit */
(8)
QF_pCB_ = &QF_active[me->prio];
(8)
/* the queue must be able to accept the event (cannot overflow) */
(9) Q_ASSERT(me->nUsed <= Q_ROM_BYTE(QF_pCB_->end));
(10)
((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[me->head].sig = sig;
(11)
((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[me->head].par = par;
(13)
me->head = Q_ROM_BYTE(QF_pCB_->end); /* wrap the head */
(1,2) The signature of the QActive_post()
function depends whether you've configured events with or without parameters.
(3) The task-level posting to the event queue always happens in the task-level critical section.
(4,5) When the event queue is empty, the new event is copied directly to the current event inside the state machine.
(6) The bit corresponding to the priority of the active object is set in the QF_readySet_
bitmask. The constant lookup table l_pow2Lkup[]
is initialized as follows: l_pow2Lkup[p] == (1 << (p-1))
, for all priorities p = 1..8
.
(7) When the preemptive QK-nano kernel is configured (see Section 12.6), the preemptive scheduler is called to handle a potential synchronous preemption. (A synchronous preemption occurs when an active object posts an event to a higher-priority task.)
(8) The global QF_pCB_
variable holds a pointer to the active object control block &QF_active[me->prio]
located in ROM.
QF_pCB_
is defined as follows at the top of the qpn.c source file:
The QF_pCB_
variable is used only locally within QP-nano functions, but I employ it to avoid loading the stack with a temporary variable. Such as global variable can be safely shared because all usage happens inside critical sections of code, anyway.
Note
QP-nano treats the inability to post an event to a queue as an error. This assertion is part of the event delivery guarantee policy (see Section 6.7.6 in Chapter 6). It is the application designer's (your) responsibility to size the event queues adequately for the job at hand.
(10,11) The new event is copied to the ring buffer at the head
index.
(13) If wrap around is required the head
index is moved to the end
of the buffer. This makes the buffer circular.
(14) The head
index is always decremented, including just after the wraparound. I've chosen to decrement the head
(and also the tail
) index because it leads to a more efficient implementation than incrementing the indices. The wraparound occurs in this case at zero rather than at the end. Comparing a variable to a constant zero is more efficient than any other comparison.
Listing 12.15 shows the implementation of the QActive_postISR()
function, which is used for posting events from ISRs to active objects. You should never use this function to post events from active objects, because it uses the ISR-specific critical section mechanism (see Section 12.3.2).
(1) Interrupts are only locked when interrupt nesting is allowed.
(2) If you define QF_ISR_KEY_TYPE
, QP-nano uses the advanced policy of “saving and restoring interrupt status.”
(4) The interrupt status is saved into the key
variable and interrupts are locked.
(5) If you don't define QF_ISR_KEY_TYPE
, QP-nano uses the simple policy of “unconditional interrupt unlocking,” exactly the same as at the task level.
Note
The ISR-level event posting operation
QActive_postISR()
does not call the QK-nano scheduler, because a task can never synchronously preempt an ISR (compare Listing 12.14(7)).
By default, QP-nano uses the simple, cooperative “vanilla” scheduler, which works exactly as I described in Section 6.3.7 in Chapter 6. Listing 12.16 shows the QF_run()
function in the qfn.c
source file, which implements the whole “vanilla” kernel.
Listing 12.16. The cooperative “vanilla” kernel (file <qp>qpnsourceqfn.c)
(2)
static uint8_t const Q_ROM Q_ROM_VAR log2Lkup[] = {
(3)
static uint8_t const Q_ROM Q_ROM_VAR invPow2Lkup[] = {
(4) static QActive *a; /* declared static to save stack space */
(5) static uint8_t p; /* declared static to save stack space */
(5)
/* trigger initial transitions in all registered active objects... */
(6)
for (p = (uint8_t)1; p <= (uint8_t)QF_MAX_ACTIVE; ++p) {
(8)
Q_ASSERT(a != (QActive *)0); /* QF_active[p] must be initialized */
(9)
a->prio = p; /* set the priority of the active object */
(10)
QHsm_init((QHsm *)a); /* take the initial transition in HSM */
(11)
QFsm_init((QFsm *)a); /* take the initial transition in FSM */
(16)
if ((QF_readySet_ & 0xF0) != 0U) { /* upper nibble used? */
(17)
p = (uint8_t)(Q_ROM_BYTE(log2Lkup[QF_readySet_ >> 4]) + 4);
(24)
if ((--a->nUsed) == (uint8_t)0) { /* queue becoming empty? */
(25)
QF_readySet_ &= Q_ROM_BYTE(invPow2Lkup[p]);/* clear the bit */
(27)
Q_SIG(a) = ((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[a->tail].sig;
(28)
Q_PAR(a) = ((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[a->tail].par;
(30)
a->tail = Q_ROM_BYTE(QF_pCB_->end); /* wrap the tail */
(1) The cooperative vanilla kernel is only compiled when the preemptive QK-nano kernel is not configured.
(2) The constant array log2Lkup[]
is the binary-logarithm (log-base-2) lookup table, defined as log2Lkup[bitmask] == log2(bmask)
, for 0 <= bitmask <= 15
(see Figure 7.6 in Chapter 7). The log-base-2 lookup quickly determines the most significant 1-bit in the bitmask.
(3) The constant array invPow2Lkup[]
is a bitwise negated power-2 lookup table, defined as invPow2Lkup[p] == ~(1 << (p-1))
, for all priorities p = 1..8
. This lookup table is used for masking off bits in the QF_readSet_
bitmask.
(4,5) The temporary variables ‘a
’ and ‘p
’ are defined as static
to save stack space.
(6) This for
loop triggers initial transitions in all active objects, starting from the lowest-priority active object.
(7) The active object pointer is obtained from the active object control block in ROM.
(8) This assertion makes sure that the QF_active[]
array has been initialized correctly.
(9) This internal priority of the active object is initialized consistently with the definition in the QF_active[]
array.
(10,11) The initial transition in the active object state machine is triggered.
(12) The QF_onStartup()
callback function configures and starts interrupts. This function is implemented at the application level (in the BSP).
(14) Interrupts are locked to access the QF_readySet_
ready-set.
(15) If the ready-set QF_readySet_
is not empty, the “vanilla” kernel has some events to process.
(15) At this point, the vanilla kernel must quickly find the highest-priority active object with a nonempty event queue, which is achieved via a binary logarithm lookup table (see Section 7.11.1 in Chapter 7). However, to conserve the ROM, the log2Lkup[]
lookup table in QP-nano can only handle values 0..15, which covers just four least significant bits of the QF_readySet_
bitmask.
(16) When the number of active objects is greater than the range of the log2Lkup[]
lookup table, I first test the upper nibble of the QF_readySet_
bitmask.
(17) If the upper nibble is not zero, I shift the upper nibble to the lower 4 bits and apply the log2Lkup[]
lookup table. I then need to add 4 to the priority of the active object.
(18) Otherwise, I simply apply the log2Lkup[]
lookup table to the lower nibble of the QF_readySet_
bitmask.
(20) The active object pointer is loaded from the ROM array QF_active[]
, which maps active object priorities to active object pointers.
(21,22) The current event is dispatched to the active object state machine.
(23) Interrupts are locked again to update the status of the active object event queue after processing the current event.
(24) The number of events in the queue is decremented and tested against zero.
(25) If the queue is becoming empty, the corresponding bit in the QF_readySet_
bitmask is cleared by masking it off with the invPow2Lkup[]
lookup table.
(26) Otherwise, the queue is not empty, so the next event must be copied from the ring buffer to the current event inside the active object state machine. The global pointer QF_pCB_
is set to point to the control block of the active object &QF_active[me->prio]
located in ROM.
(27,28) The next event is copied from the ring buffer at the tail
index to the current event inside the state machine.
(33) The else branch is taken when all active object event queues are empty, which is by definition the idle condition of the “vanilla” kernel.
(34) The “vanilla” kernel calls the QF_onIdle()
callback function to give the application a chance to put the MCU to a low-power sleep mode. The QF_onIdle()
function is typically implemented at the application level (in the BSP).
Note
Most MCUs provide software-controlled low-power sleep modes, which are designed to reduce power dissipation by gating the clock to the CPU and various peripherals. To ensure a safe transition to a sleep mode, the “vanilla” kernel calls
QF_onIdle()
with interrupts locked. TheQF_onIdle()
function must always unlock interrupts internally, ideally atomically with the transition to a sleep mode.
Interrupt processing under the “vanilla” kernel is as simple as in the foreground/background architecture. Typically, you can use the ISRs generated by the C compiler. The only special consideration for QP-nano is that you need to be consistent with respect to the interrupt-nesting policy. In particular, if you configured nesting interrupts by defining the macro QF_ISR_NEST
in the qpn_port.h
header file, you need to be consistent and unlock interrupts before calling the QP-nano functions QActive_postISR()
or QF_tick()
.
The idle callback QF_onIdle()
works in QP-nano exactly the same way as in the full-version QP. Refer to Section 8.2.4 in Chapter 8 for examples of defining this callback function for various CPUs.
QP-nano contains a preemptive run-to-completion (RTC) kernel called QK-nano, which works very similarly to the QK preemptive kernel available in the full-version QP and described in Chapter 10. I strongly recommend that you read Section 10.1 in Chapter 10 before you decide to use a preemptive kernel such as QK-nano.
Note that the preemptive QK-nano kernel puts more demands on the target CPU and the compiler than the nonpreemptive vanilla kernel. Generally, QK-nano can be used with a given processor and compiler if they satisfy the following requirements:
• The processor supports a hardware stack that can accommodate stack variables (not just return addresses).
• The MCU has enough stack memory to allow at least two levels of task nesting so that a high-priority active object can preempt a low-priority active object at least once. If you don't have even that much stack, you'll not be able to take advantage of the preemptive kernel.
• The C or C++ compiler can generate reentrant code. In particular, the compiler must be able to allocate automatic variables on the stack.
For example, some older CPU architectures, such as the 8-bit PIC MCUs, don't have a C-friendly stack architecture, even though they might have enough RAM, and consequently cannot easily run QK-nano.
You configure your QP-nano application to use the QK-nano kernel (as opposed to the default “vanilla” kernel) simply by including the QK-nano interface qkn.h
at the end of the qpn_port.h
header file. Listing 12.17 shows the qkn.h
header file.
Listing 12.17. QK-nano interface (file <qp>qpnincludeqkn.h)
(1) The qkn.h
header file defines the macro QK_PREEMPTIVE
, which configures the QF-nano real-time framework to use the QK-nano preemptive kernel rather than the cooperative “vanilla” kernel.
(2) The QK_init()
function performs CPU-specific initialization, if such initialization is necessary. This function is optional and not all QK-nano ports need to implement this function. However, if the function is provided, your application must call it, typically during BSP initialization.
(3) The QK_schedule_()
function implements the QK-nano scheduler. The QK scheduler is always invoked from a critical section but might unlock interrupts internally to launch a task.
Note
The macro
Q_REENTRANT
tells the compiler to generate ANSI-C compliant reentrant function code. See also Listing 12.11(8).
(4) The QK_onIdle()
callback function gives the application a chance to customize the idle processing (see also Listing 12.18(11)
Listing 12.18. Starting active objects and the QK-nano idle loop (file <qp>qpnsourceqkn.c)
/* Global-scope objects -------------------------------------------------*/
(1)
uint8_t volatile QK_currPrio_ = (uint8_t)(QF_MAX_ACTIVE + 1);
(2)
uint8_t volatile QK_intNest_; /* start with nesting level of 0 */
(3)
extern QActiveCB const Q_ROM * Q_ROM_VAR QF_pCB_;/* ptr to AO control block */
(3)
/* local objects --------------------------------------------------------*/
(4)
static QActive *l_act; /* pointer to AO */
(4)
/*......................................................................*/
(4)
/* trigger initial transitions in all registered active objects... */
(5) static uint8_t p; /* declared static to save stack space */
(6)
for (p = (uint8_t)1; p <= (uint8_t)QF_MAX_ACTIVE; ++p) {
(6)
l_act = (QActive *)Q_ROM_PTR(QF_active[p].act);
(6)
QHsm_init((QHsm *)l_act); /* initial transition */
(7)
QK_currPrio_ = (uint8_t)0; /* set the priority for the QK idle loop */
(8)
QK_SCHEDULE_(); /* process all events produced so far */
(5) The global variable QK_currPrio_
represents the global systemwide priority of the currently running task. QK_currPrio_
is declared as volatile
because it can change asynchronously in ISRs.
(6) The QK_SCHEDULE_()
encapsulates the invocation of the QK-nano scheduler at the exit from an interrupt to handle asynchronous preemptions.
(7) When interrupt nesting is not allowed, the QK_SCHEDULE_()
macro calls the scheduler only when the ready-set is not empty. That way, you avoid a function call overhead when all event queues are empty.
(8) The global variable QK_intNest_
represents the global systemwide interrupt-nesting level. QK_intNest_
is declared as volatile
because it can change asynchronously in ISRs.
(9) When interrupt nesting is allowed, the QK_SCHEDULE_()
macro calls the scheduler only when the ready-set is not empty and additionally the interrupt that is ending is not nesting on another interrupt (see also Section 12.6.4).
(10-12) When you define the macro QK_MUTEX
, qkn.h
defines the priority-ceiling mutex interface.
As shown in Listing 12.17(1), the qkn.h
header file defines internally the macro QK_PREEMPTIVE
, which causes elimination of the “vanilla” kernel (see Listing 12.16(1)), replacing it with the preemptive QK-nano kernel. In particular, the function QF_run()
has a different implementation under the QK-nano kernel, as shown in Listing 12.18.
(1) The global variable QK_currPrio_
represents the global systemwide priority of the currently running task. The QK-nano priority is initialized to a level above any active object, which effectively locks the QK-nano scheduler during the whole initial transient.
(2) The global variable QK_intNest_
represents the global systemwide interrupt-nesting level. QK_intNest_
is only necessary when nesting of interrupts is allowed.
(3) The qkn.c
module reuses the global variable QF_pCB_
, which is also used in QActive_post()
and QActive_postISR()
defined in qfn.c
(see Listings 12.14 and 12.15).
(4) The static variable l_act
holds a pointer to an active object and is shared among QK-nano functions.
(5) The local variable ‘p
’ (active object priority) is declared static
to save the stack space.
(6) All active objects in the application are initialized, exactly the same way as in Listing 12.16(6-11).
(8) The QK-nano scheduler is invoked to process all events that might have been posted to event queues during the initialization of the active objects.
(9) The QF_onStartup()
callback function configures and starts interrupts. This function is implemented at the application level (in the BSP).
(11) The idle loop continuously calls the QK_onIdle()
callback function to give the application a chance to put the CPU to a low-power sleep mode. The QK_onIdle()
function is typically implemented at the application level (in the BSP).
Note
As a preemptive kernel, QK-nano handles idle processing differently than does the nonpreemptive vanilla kernel. Specifically, the
QK_onIdle()
callback function is always called with interrupts unlocked and does not need to unlock interrupts (as opposed to theQF_onIdle()
callback). Furthermore, a transition to a low-power sleep mode insideQK_onIdle()
does not need to occur with interrupts locked. Such a transition is safe and does not cause any race conditions, because a preemptive kernel never switches the context back to the idle loop as long as events are available for processing.
The scheduler is the most important part of the QK-nano kernel. As explained in Section 10.2.3 in Chapter 10, the QK scheduler is called at two junctures: (1) when an event is posted to an event queue of an active object (synchronous preemption), and (2) at the end of ISR processing (asynchronous preemption). In the QActive_post()
function implementation (Listing 12.14(7)), you saw how the QK-nano scheduler gets invoked to handle the synchronous preemptions. In the previous section, you also saw the definition of the macro QK_SCHEDULE_()
, which calls the scheduler from an interrupt context to handle the asynchronous preemptions. Here I describe the QK-nano scheduler itself.
The QK-nano scheduler is simply a regular C-function QK_schedule_()
whose job is to efficiently find the highest-priority active object that is ready to run and to execute it as long as its priority is higher than the currently serviced QK-nano priority. To perform this job, the QK-nano scheduler relies on two data elements: the set of tasks that are ready to run QF_readySet_
(Section 12.4.1) and the currently serviced task priority QK_currPrio_
(Listing 12.17(5)). Listing 12.19 shows the complete implementation of the QK_schedule_()
function. You will certainly recognize in this function many elements that I already discussed for the nonpreemptive “vanilla” kernel.
Listing 12.19. The preemptive QK-nano scheduler (file <qp>qpnsourceqkn.c)
(1) void QK_schedule_(void) Q_REENTRANT {
(1)
static uint8_t const Q_ROM Q_ROM_VAR log2Lkup[] = {
(1)
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4
(1)
static uint8_t const Q_ROM Q_ROM_VAR invPow2Lkup[] = {
(2) uint8_t p; /* the new highest-priority active object ready to run */
(2)
/* determine the priority of the highest-priority AO ready to run */
(2)
if ((QF_readySet_ & 0xF0) != 0) { /* upper nibble used? */
(3)
p = (uint8_t)(Q_ROM_BYTE(log2Lkup[QF_readySet_ >> 4]) + 4);
(5)
if (p > QK_currPrio_) { /* is the new priority higher than the current? */
(6) uint8_t pin = QK_currPrio_; /* save the initial priority */
(8) QK_currPrio_ = p; /* new priority becomes the current priority */
(9) QF_INT_UNLOCK(); /* unlock interrupts to launch the new task */
(12)
/* set cb and a again, in case they change over the RTC step */
(15)
if ((--l_act->nUsed) == (uint8_t)0) {/*is queue becoming empty? */
(17)
((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[l_act->tail].sig;
(18)
((QEvent *)Q_ROM_PTR(QF_pCB_->queue))[l_act->tail].par;
(20)
l_act->tail = Q_ROM_BYTE(QF_pCB_->end);/* wrap the tail */
(23)
if ((QF_readySet_ & 0xF0) != 0) { /* upper nibble used? */
(24)
p = (uint8_t)(Q_ROM_BYTE(log2Lkup[QF_readySet_ >> 4])+ 4);
(27)
} while (p > pin); /* is the new priority higher than initial? */
Note
The ‘
p
’ variable must necessarily be allocated on the stack, because each level of preemption needs to compute a separate copy of the highest-priority active object ready to run. The compiler should never place the ‘p
’ variable in a static memory. For that reason theQK_schedule_()
function is declared as “reentrant” in line (1).
(3,4) The highest-priority active object with a not-empty event queue is quickly found out by means of the binary-logarithm lookup table, exactly the same way as already explained in Listing 12.16(16-18).
(5) The QK scheduler can launch a task only when the new priority is higher than the saved priority of the currently executing task.
Note
The QK-nano scheduler is an indirectly recursive function. The scheduler calls task functions, which might post events to other tasks, which calls the scheduler (synchronous preemption). The scheduler can also be preempted by ISRs, which also call the scheduler at the exit (asynchronous preemption). However, this recursion can continue only as long as the priority of the tasks keeps increasing. Posting an event to a lower- or equal-priority task (posting to self) stops the recursion because of the
if
statement in line (5).
Note
The ‘
pin
’ variable must necessarily be allocated on the stack because each level of preemption needs to save its own copy of the current priority. The compiler should never place the ‘pin
’ variable in a static memory. For that reason theQK_schedule_()
function is declared as “reentrant” in line (1).
(7) The do
loop continues as long as the scheduler finds ready-to-run tasks of higher priority than the initial priority pin
.
(8) The current QK-nano priority is raised to the level of the highest-priority task that is about to be started.
(10,11) The current event is dispatched to the active object state machine.
Note
Dispatching of the event into the state machine represents the run-to-completion step of the active object thread. Note that the RTC task is executed with interrupts unlocked.
(12) Interrupts are locked again to update the status of the active object event queue after processing the current event.
(13) The global pointer QF_pCB_
is set to point to the control block of the active object &QF_active[p]
located in ROM.
(14) The static active object pointer l_act
is set to point to the active object with priority ‘p.
’
Note
The active object pointed to by
l_act
is the same one that just finished the RTC step in lines 10-11. However, I did not set thel_act
earlier because the local variablel_act
could have changed when the interrupts were unlocked.
(15) The number of events in the queue is decremented and tested against zero.
(16) If the queue is becoming empty, the corresponding bit in the QF_readySet_
bitmask is cleared by masking it off with the invPow2Lkup[]
lookup table.
(17,18) The next event is copied from the ring buffer at the tail
index to the current event inside the state machine.
(23-25) The scheduler finds out the next highest-priority active objects ready to run.
(26) If the QF_readySet_
turns out to be empty, the QK-nano kernel has nothing more to do. The variable ‘p
’ is set to zero to terminate the do-while
loop in the next step.
(27) The while
condition loops back to step 7 as long as the QK-nano scheduler still finds ready-to-run tasks of higher priority than the initial priority pin
.
(28) After the loop terminates, the current QK-nano priority must be restored back to the initial level.
(29) The QK-nano scheduler always returns with interrupts locked.
QK-nano can typically work with ISRs synthesized by the C compiler, which most embedded C cross-compilers support. However, unlike the nonpreemptive vanilla kernel, the preemptive QK-nano kernel must be notified about entering and exiting every ISR to handle potential asynchronous preemptions. The specific actions required at the entry and exit from ISRs depend on the interrupt-locking policy for ISRs.
When interrupt nesting is allowed (the macro QF_ISR_NEST
is defined in qpn_port.h
), the interrupt processing in QK-nano is exactly the same as described in Section 10.3.3 for the full-version QK. In particular, the interrupt-nesting counter QK_intNest_
must be incremented upon interrupt entry and decremented upon interrupt exit. The QK-nano scheduler can only be invoked when the interrupt-nesting counter is zero, meaning that the calling ISR is not nested on top of another ISR.
However, when interrupt nesting is not allowed (the macro QF_ISR_NEST
is not defined in qpn_port.h
), QK-nano allows for a simpler interrupt handling compared to the full-version QK. Specifically, when interrupts cannot nest you don't need to increment the interrupt-nesting counter (QK_intNest_
) upon ISR entry, and you don't need to decrement it upon ISR exit. In fact, when the macro QF_ISR_NEST
not defined, the QK_intNest_
counter is not even available. This simplification is possible because QP-nano uses a special ISR version of the event-posting function QActive_postISR()
, which does not call the QK-nano scheduler. Consequently, there is no need to prevent the synchronous preemption within ISRs. Listing 12.20 shows the simplified interrupt handling when interrupt nesting is not allowed.
QK-nano supports the priority-ceiling mutex mechanism in the exact same way as the full-version QK (see Section 10.4.1 in Chapter 10). In QK-nano, the feature is disabled by default, but you can enable it by defining the macro QK_MUTEX
in the qpn_port.h
header file.
The “Fly ‘n’ Shoot” game example described at the beginning of this chapter shows most features of QP-nano, but it fails to demonstrate QP-nano running in a really small MCU. In this section, I describe the pedestrian light-controlled (PELICAN) crossing example application, which demonstrates a nontrivial hierarchical state machine, event exchanges among active objects and ISRs, time events, and even the QK-nano preemptive kernel. I was able to squeeze this application inside the MSP430-F2013 ultra-low-power MCU with only 128 bytes of RAM and 2KB of flash ROM. Specifically, the accompanying code was tested on the eZ430-F2013 USB stick3 At the time of this writing the eZ430-F2013 USB stick was available for $20 from the TI site (www.ti.com/eZ430). from Texas Instruments. The eZ430-F2013 is a complete development tool that provides both the USB-based debugger and a MSP430-F2013 development board in a small USB stick package (see Figure 12.6).
The code accompanying this book contains several versions of the PELICAN crossing application for MSP430, Cortex-M3, and 80x86/DOS. For each target CPU I provide two versions: the nonpreemptive configuration with vanilla kernel and the preemptive QK-nano configuration. Refer to Listing 12.7 in Section 12.3.1 for the location of these examples.
Before I describe the PELICAN crossing controller state machine and the QP-nano implementation, I need to provide the problem specification. The PELICAN crossing (see Figure 12.7) starts with cars enabled (green light for cars) and pedestrians disabled (“Don't Walk” signal for pedestrians). To activate the traffic light change, a pedestrian must push the button at the crossing, which generates the PEDS_WAITING
event. In response, oncoming cars get a yellow light, which after a few seconds changes to red light. Next, pedestrians get the “Walk” signal, which shortly thereafter changes to the flashing “Don't Walk” signal. When the “Don't Walk” signal stops flashing, cars get the green light again. After this cycle, the traffic lights don't respond to the PEDS_WAITING
button press immediately, although the button “remembers” that it has been pressed. The traffic light controller always gives the cars a minimum of several seconds of green light before repeating the traffic light change cycle. One additional feature is that at any time an operator can take the PELICAN crossing offline (by providing the OFF event). In the “offline” mode, the cars get a flashing red light and pedestrians a flashing “Don't Walk” signal. At any time the operator can turn the crossing back online (by providing the ON event).
Figure 12.8 shows the complete PELICAN crossing statechart. In the explanation section following the diagram I describe how it works. If you are unfamiliar with some aspects of the UML state machine notation, refer to Part I of this book.
(1) Upon the initial transition, the PELICAN state machine enters the “operational” state and displays the red light for cars and the “Don't Walk” signal for pedestrians.
(2) The “operational” state has a nested initial transition to the “carsEnabled” substate. Per the UML semantics, this transition must be taken after entering the superstate.
(3) The “carsEnabled” state has a nested initial transition to the “carsGreen” substate. Per the UML semantics, this transition must be taken after entering the sperstate. Entry to “carsGreen” changes signals green light for cars and arms the time event to expire in the GREEN_TOUT
clock ticks. The GREEN_TOUT
timeout represents the minimum duration of green light for cars.
(4) The “carsGreen” state has a nested initial transition to the “carsGreenNoPed” substate. Per the UML semantics, this transition must be taken after entering the superstate. The “carsGreenNoPed” state is a leaf state, meaning that it has no substates or initial transitions. The state machine stops and waits in this state.
(5) When the PEDS_WAITING
event arrives in the “carsGreenNoPed” state, the state machine transitions to another leaf state “carsGreenPedWait.” Note that the state machine still remains in the “carsGreen” superstate because the minimum green light period for cars hasn't expired yet. However, by transitioning to the “carsGreenPedWait” substate, the state machine remembers that the pedestrian is waiting.
(6) However, when the Q_TIMEOUT
event arrives while the state machine is still in the “carsGreenNoPed” state, the state machine transitions to the “carsGreenInt” (interruptible green light for cars) state.
(7) The “carsGreenInt” state handles the PEDS_WAITING
event by immediately transitioning to the “carsYellow” state, because the minimum green light for cars has elapsed.
(8) The “carsGreenPedWait” state, on the other hand, handles only the Q_TIMEOUT
event, because the pedestrian is already waiting for the expiration of the minimum green light for cars.
(9) The “carsYellow” state displays the yellow light for cars and arms the timer for the duration of the yellow light. The Q_TIMEOUT
event causes the transition to the “pedsEnabled” state. The transition causes exit from the “carsEnabled” superstate, which displays the red light for cars.
(9) The pair of states “carsEnabled” and “pedsEnabled” realizes the main function of the PELICAN crossing, which is to alternate between enabling cars and enabling pedestrians. The exit action from “carsEnabled” disables cars (by showing a red light for cars) while the exit action from “pedsEnabled” disables pedestrians (by showing them the “Don't Walk” signal). The UML semantics of state transitions guarantees that these exit actions will be executed whichever way the states happen to be exited, so I can be sure that the pedestrians will always get the “Don't Walk” signal outside the “pedsEnabled” state and cars will get the red light outside the “carsEnabled” state.
(10) The “pedsEnabled” state has a nested initial transition to the “pedsWalk” substate. Per the UML semantics, this transition must be taken after entering the superstate. The entry action to “pedsWalk” shows the “Walk” signal to pedestrians and arms the timer for the duration of this signal.
(11) The Q_TIMEOUT
event triggers the transition to the “pedsFlash” state, in which the “Don't Walk” signal flashes on and off. I use the internal variable of the PELICAN state machine me->pedFlashCtr
to count the number of flashes.
(12,13) The Q_TIMEOUT
event triggers two internal transitions with complementary guards. When the me->pedFlashCtr
counter is even, the “Don't Walk” signal is turned on. When it's odd, the “Don't Walk” signal is turned off. Either way the counter is always decremented.
(14) Finally, when the me->pedFlashCtr
counter reaches zero, the Q_TIMEOUT
event triggers the transition to the “carsEnabled” state. The transition causes execution of the exit action from the “pedsEnabled” state, which displays “Don't Walk” signal for pedestrians. The life cycle of the PELICAN crossing then repeats.
At this point, the main functionality of the PELICAN crossing is done. However, I still need to add the “offline” mode of operation, which is actually quite easy because of the state hierarchy.
(15) The OFF event in the “operational” superstate triggers the transition to the “offline” state. The state hierarchy ensures that the transition OFF is inherited by all direct or transitive substates of the “operational” superstate, so regardless in which substate the state machine happens to be, the OFF event always triggers transition to “offline.” Also note that the semantics of exit actions still apply, so the PELICAN crossing will be left in a consistent safe state (both cars and pedestrians disabled) upon exit from the “operational” state.
(16) The Q_TIMEOUT
events in the substates of the “offline” state cause flashing of the signals for cars and pedestrians, as described in the problem specification.
(17) The ON
event can interrupt the “offline” mode at any time by triggering the transition to the “operational” state.
The actual implementation of the PELICAN state machine in QP-nano is very straightforward and follows exactly the same simple rules as I described for the Ship state machine in Section 12.2.4. The source code for the PELICAN application is located in the directory <qp>qpnexamplesmsp430iarpelican-eZ430
.
The actual PELICAN crossing controller hardware will certainly provide a push-button for generating the PED_WAITING
event as well as a switch to generate the ON
/OFF
events. But the eZ430 USB stick has no push-button or any other way to provide external inputs (see Figure 12.6). For the eZ430, I need to simulate the pedestrian/operator in a separate state machine. This is actually a good opportunity to demonstrate how to incorporate a second state machine (active object) into the application.
The Pedestrian active object is very simple. It periodically posts the PED_WAITING
event to the PELICAN active object and from time to time it turns the crossing offline by posting the OFF
event followed by the ON
event. I leave it as an exercise for you to draw the state diagram of the Pedestrian state machine from the source code found in the file <qp>qpnexamplesmsp430iarpelican-eZ430ped.c
. Note that such “reverse engineering” of source code is very easy in QP applications because the code is always the precise specification of the state machine.
The source code for the PELICAN and Pedestrian active objects as well as the main.c
module is actually identical for all target CPUs, but each target requires a specific QP-nano port. In this section I describe the QP-nano port to MSP430 with the preemptive QK-nano kernel. A QP-nano port consists of the qpn_port.h
header file and the BSP implementation in the bsp.c
source file.
Using the preemptive kernel in the PELICAN crossing example isn't really justified by the loose timing requirements of this application. I describe the preemptive QP-nano configuration mainly to demonstrate that the QK-nano kernel is very lightweight and can fit even in a very memory-constrained MCU, such as the MSP430-F2013. The code accompanying this book contains the nonpreemptive version of the PELICAN crossing example for the eZ430 target as well (see Listing 12.7).
The PELICAN crossing example for eZ430 with the preemptive QK-nano kernel is located in the directory <qp>qpnexamplesmsp430iarpelican-qk-eZ430
. Listings 12.21 and 12.22 show the qpn_port.h
header file and the bsp.c
source file, respectively. This port has been compiled with the free KickStart edition of the IAR Embedded Workbench for MSP430 v4.10A.
Listing 12.21. QP-nano Port to MSP430 with QK-nano (file <qp>qpnexamplesmsp430iarpelican-qk-eZ430qpn_port.h)
/* maximum # active objects--must match EXACTLY the QF_active[] definition */
(4)
/*#define QF_ISR_NEST*/ /* nesting of ISRs not allowed */
(7)
#include <intrinsics.h> /* contains prototypes for the intrinsic functions */
(8)
#include <stdint.h> /* Exact-width integer types. WG14/N843 C99 Standard */
(8)
#include "qepn.h" /* QEP-nano platform-independent public interface */
(8)
#include "qfn.h" /* QF-nano platform-independent public interface */
(9) #include "qkn.h" /* QK-nano platform-independent public interface */
Listing 12.22. BSP for MSP430 with QK-nano (file <qp>qpnexamplesmsp430iarpelican-qk-eZ430sp.c)
(4) QK_ISR_EXIT(); /* inform QK-nano about ISR exit */
(4)
/*.......................................................................*/
(5)
CCR0 = ((BSP_SMCLK + BSP_TICKS_PER_SEC/2) / BSP_TICKS_PER_SEC);
(5)
TACTL = (TASSEL_2 | MC_1); /* SMCLK, upmode */
(5)
/*.......................................................................*/
(6)
CCTL0 = CCIE; /* CCR0 interrupt enabled */
(6)
/*.......................................................................*/
(7)
__low_power_mode_1(); /* adjust the low-power mode to your application */
(7)
/*.......................................................................*/
(7)
void BSP_signalPeds(enum BSP_PedsSignal sig) {
(7)
if (sig == PEDS_DONT_WALK) {
(7)
/*......................................................................*/
(7)
void Q_onAssert(char const Q_ROM * const Q_ROM_VAR file, int line) {
(7)
(void)file; /* avoid compiler warning */
(1) The PELICAN crossing application uses two active objects (PELICAN and Pedestrian).
(2,3) The IAR compiler provided very efficient intrinsic functions for locking and unlocking interrupts.
(5,6) The interrupt entry and exit macro for QK-nano are defined consistently with the interrupt nesting policy (see Listing 12.20).
(7) The IAR header file <intrinsics.h>
provides declarations of intrinsic functions, such as __disable_interrupt()
and __enable_interrupt()
.
(8) The IAR compiler is C99-compliant and provides the standard header file <stdint.h>
, which defines exact-width integer types.
(9) The QK-nano is configured by including the qkn.h
header file.
Note
Even though this macro does not do anything in this particular port, I like to use it for symmetry with the
QK_ISR_EXIT()
. This also allows me to change the interrupt-locking policy without modifying the ISRs.
(3) The ISR calls the QP-nano service designed for the ISR context.
(4) The macro QK_ISR_EXIT()
informs QK-nano about exiting the ISR.
(5) The BSP initialization configures the system clock tick timer to tick at the predefined rate BSP_TICKS_PER_SEC
(I set to 20Hz in bsp.h
).
(6) The startup callback enables the system clock-tick ISR. This is the only ISR in the PELICAN crossing application.
(7) The idle callback of the QK-nano kernel transitions to the LPM1 mode, which is just one of many low-power sleep modes available in the ultra-low-power MSP430 architecture. In your application, you should adjust the power mode to your particular requirements.
Note
When you apply low-power mode is MSP430, the
QK_onIdle()
function is actually called only once and the idle loop stops. This is because the MSP430 core keeps the power-control bits in the SR register of the CPU, which gets automatically restored upon interrupt return. So when a power-saving mode is selected, the CPU stops when returning to the idle loop. If you want to perform some processing in the QK-nano idle loop before going to sleep, you need to call__low_power_mode_off_on_exit()
in every ISR to clear the power-control bits in the stacked SR register.
To give you an idea of the QP-nano memory usage, Tables 12.1 and 12.2
Table 12.1. QP-nano memory usage in bytes for various settings of the configuration parameters (MSP430/IAR compiler/optimization-High/Size)
Configuration Parameters in qpn_port.h | qepn.c (RAM/ROM) | qfn.c (RAM/ROM) | qkn.c (RAM/ROM) | QP-nano Total (RAM/ROM) | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Configuration Number | Q\_NFSM | Q\_NHSM | Q\_PARAM\_SIZE | QF\_TIMEEVT\_CTR\_SIZE | QF\_MAX\_ACTIVE | QK\_PREEMPTIVE | ||||
1 | √ | 0 | 0 | 4 | 0/110 | 6/420 | N/A | 6/530 | ||
2 | √ | 2 | 0 | 4 | 0/110 | 6/474 | N/A | 6/584 | ||
3 | √ | 0 | 0 | 8 | 0/110 | 6/504 | N/A | 6/614 | ||
4 | √ | 2 | 2 | 8 | 0/110 | 9/578 | N/A | 9/688 | ||
5 | √ | 2 | 2 | 8 | 0/634 | 9/578 | N/A | 9/1,212 | ||
6 | 2 | 2 | 8 | 0/722 | 9/578 | N/A | 9/1,300 | |||
7 | √ | 0 | 0 | 4 | √ | 0/110 | 3/207 | 4/246 | 7/563 | |
8 | √ | 2 | 0 | 4 | √ | 0/110 | 3/238 | 4/268 | 7/616 | |
9 | √ | 0 | 0 | 8 | √ | 0/110 | 3/207 | 4/292 | 7/609 | |
10 | √ | 2 | 2 | 8 | √ | 0/110 | 6/313 | 4/314 | 10/737 | |
11 | √ | 2 | 2 | 8 | √ | 0/634 | 6/313 | 4/314 | 10/1,261 | |
12 | 2 | 2 | 8 | √ | 0/722 | 6/313 | 4/314 | 10/1,349 |
The first column of Tables 12.1 and 12.2 lists the configuration macros that are significant for the RAM or ROM usage in QP-nano. I have omitted the QF_ISR_NEST
and QF_ISR_KEY_TYPE
macros because they have virtually no impact on the code or data sizes shown in the tables (even though defining QF_ISR_KEY_TYPE
somewhat increases the stack usage.)
Both MSP430 and Cortex-M3 offer good code density and the IAR compiler generates fantastic machine code for these CPU architectures. (I've seen much worse results for older CPU architectures, such as 8051 or the PIC). Therefore, you should treat the data in Tables 12.1 and 12.2 as minimum memory footprint of QP-nano rather than average results. The intent of Table 12.1 is primarily to give you a general idea for the relative cost of various options rather than to provide you absolutely accurate measurements.
Note
The Tables 12.1 and 12.2 show only the memory used directly by the QP-nano components but do not include the memory required by the application. In particular, you don't see the stack usage or the RAM required by active objects and their event queues.
The various QP-nano configurations are listed separately in Tables 12.1 and 12.2 for the nonpreemptive “vanilla” kernel (configurations 1-6) and the preemptive QK-nano kernel (configurations 7-12). Within each group, the simpler configurations come before the more expensive ones. For example, the absolutely minimal configuration number 1 eliminates the HSM code (so only basic FSM support is provided), uses no event parameters, no time events, and up to four active objects. This minimal configuration is clearly very limited. However, the configuration number 4 is already quite reasonable. It still offers only nonhierarchical FSMs, but includes event parameter, time events, and up to eight active objects at a cost of less than 700 bytes of code space.
By far, the most expensive feature (in terms of ROM) is the HSM support, which costs about 650 bytes (e.g., compare configurations number 4 and 5 or 10 and 11). On the other hand, the QK-nano preemptive kernel increases the ROM footprint only by 50-100 bytes compared to the “vanilla” kernel. Obviously, the true cost of QK-nano lies in the increased stack requirements, which Tables 12.1 and 12.2 don't show.
In comparison, the full-version QP4 Both C and C++ versions have essentially identical footprint, the C++ version being bigger by insignificant 24 bytes of ROM, which represents less than 1% of the total code size. compiled with the IAR compiler for Cortex-M3 requires 2,718 bytes of ROM (616 bytes for the QEP component and 2,102 bytes of ROM for the QF component) and 121 bytes of RAM with eight active objects configured. This corresponds roughly to the QP-nano configuration number 6 from Table 12.2.
Low-end MCUs are a very important market segment for embedded systems because many billions of units of these devices are sold each year. These small MCUs aren't well served by the traditional kernels or RTOSes, which simply require too much RAM. However, QP-nano demonstrates that an event-driven framework is scalable to very small systems, starting from about 2KB of ROM and some 100 bytes of RAM. Quite possibly, QP-nano is the smallest event-driven framework with support for UML-style hierarchical state machines and active objects in the industry.
3.147.45.212