UML Statecharts at $10.99

UML-style state machines can help you produce efficient, maintainable, testable systems--and you don't need big UML tools to use them.


May 24, 2006
URL:http://www.drdobbs.com/windows/ternary-search-trees/database/uml-statecharts-at-1099/188101799

Too many embedded developers believe that UML is all about using big tools and that the UML concepts, such as the advanced form of state machines (UML statecharts), are too heavy for most embedded designs, let alone small microcontrollers. In this article I describe a method and software for implementing UML statecharts in C, small enough to fit a low-end 8-bit microcontroller. More specifically, I present a nontrivial UML statechart example that runs on the USB Toolstick from Silicon Laboratories with room to spare. The USB Toolstick (Figure 1) is a complete evaluation board for the C8051F300 microcontroller (256 bytes of RAM, 8KB of Flash, 11 pins).

Figure 1: The USB Toolstick from Silicon Labs combines the USB debugger (left part) and the C8051F300 microcontroller (the smaller chip to the right). The "F300" controls the two LEDs at the right edge of the Toolstick (green LED at the top and red LED at the bottom).

The Toolstick is available online from the Silicon Labs web site for just $10.99. Actually, you can even start without the Toolstick, because I provide a Toolstick software emulation that uses the same state machine code, but runs on a Windows PC.

Why Bother?

The legitimate question is "Why even bother using advanced UML statecharts in low-end 8-bitters?" After all, these parts are so small that no big programs can fit into them anyway, let alone designs requiring UML statecharts.

Well, a lot can go wrong in 8KB, or even 4KB of code. All these small microcontrollers are archetypal event-driven systems with the main job of constantly reacting to events. In general, the reaction to an event depends both on the event type and, more importantly, on the current execution context. For example, if you press a button of an electronic watch, the watch probably reacts differently when it is in the timekeeping mode, compared to the same button pressed in the setting mode.

From the programming point of view, the dependency on the context often leads to convoluted, deeply nested if-else spaghetti code. The "spaghetti" results from capturing the various bits and pieces of the relevant event history (the context) in multitude of variables and flags, then setting, clearing, and testing these variables in complex expressions scattered throughout the code until it's really hard to tell which path through the code will be taken in response to a given event.

Finite State Machines (FSMs) offer a better alternative because they make the reactions to events explicitly dependent on the execution context, represented as "state". By recognizing the importance of the context upfront, FSMs become powerful spaghetti reducers that drastically cut the number of execution paths through the code, simplify the conditions tested at each branching point, and simplify transitions between different modes of operation; see my article "Back to Basics" for more information. In doing this, state machines eliminate many variables and flags used to store the context, and replace most of them with a single "state variable". Therefore the resulting application typically requires less RAM than the original spaghetti, which is a big deal for a small 8-bitter.

But I'm probably not saying anything new. The classical automata theory has been around since dirt. Nonetheless, it is also widely known that the traditional FSMs have a nasty tendency called "state and transition explosion". The number of states and transitions necessary to represent a system tends to grow faster than the complexity of the system itself because the traditional FSM formalism imposes repetitions; see my article "Deja Vu". For example, a FSM model of a simple 4-operation calculator might have some 15 states. Every one of these states needs to handle the "C" (CANCEL) event, because users must be able to cancel computations and start over at any stage. In traditional FSMs, you have to repeat the essentially identical CANCEL transition some 15 times. Similarly, you have to repeat at least a few times the "CE" (CANCEL_ENTRY) transition, the "=" (EQUALS) transition, and many others. Needless to say, the resulting code is not just bloated, but is also full of impossible to maintain repetitions, all of which renders the whole formalism barely usable. The complexity level at which FSMs start to "explode" is quite low. Apparently, traditional state machines are already in trouble to handle the complexity of a 4-operation calculator, a small home appliance, or even a more advanced digital watch--all application areas for low-end microcontrollers.

To become truly usable, the classical automata theory needs a mechanism for sharing and reusing transitions across many states. The formalism of statecharts, invented originally by David Harel and adapted subsequently into virtually all modern methodologies, including the UML, adds exactly such a mechanism. By allowing hierarchical nesting of states, statecharts provide an efficient way of sharing behavior, so that the complexity of a statechart no longer explodes but grows linearly with the complexity of the modeled system. Obviously, formalism like this is a blessing to embedded developers because it makes the state machine approach truly applicable to real-life problems; see "Deja Vu".

Designing a Statechart

Considering the limited capabilities of the Toolstick, I was constrained with the choice of a compelling example. Basically, the Toolstick can only blink its two LEDs (see Figure 1), or at most change the LED intensity using the built-in PWM generators. To me this resembled the operation of a PEdestrian LIght CONtrolled (PELICAN) crossing that I've used before in "Deja Vu".

The PELICAN crossing controller 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, the cars get the 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 (coming late into the project) 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 yellow and pedestrians flashing don't-walk signal. At any time the operator can turn the crossing back online (by providing the ON event).

Due to the hierarchical character of statecharts, you can approach the design from the top down or bottom up. Here, I use a combination of the two.

The limitation on the number of diagrams I can use here does not permit me to show a series of progressively elaborated statecharts, which would be perhaps the most educational method of explaining the design process. Instead, Figure 2 shows the complete PELICAN crossing statechart.

[Click image to view at full size]

Figure 2: Complete PELICAN crossing statechart.

I start the design with just two states: carsEnabled and pedsEnabled. This pair of states realizes the main function of the PELICAN crossing, which is to alternate between enabling cars and enabling pedestrians. Obviously, both states need some substates to realize the details of the specification, but I ignore this at first. At this stage, I only make sure that the design guarantees mutually exclusive access to the crossing, which is the main safety concern here. The exit action from the pedsEnabled state disables pedestrians, and the exit action from carsEnabled disables cars. Now, the UML semantics of state transitions guarantees that these exit actions execute whichever way the states happen to be exited, so I can be sure that the pedestrians have always don't-walk signal outside the pedsEnabled state and cars have the red light outside the carsEnabled state.

In the next step, I concentrate on the internal structure of the pedsEnabled state. The job of the pedsWalk substate is to display the walk signal and to time out. The job of the pedsFlash substate is to turn the don't-walk signal on/off. All actions are triggered by the TIMEOUT events, which are generated by the timer object associated with the state machine. The function QActive_arm() arms the timer for a one-shot delivery of the TIMEOUT event in the specified number of clock ticks. In the substate pedsFlash, the TIMEOUT event triggers two internal transitions and one regular transition leading out of the state. Internal transitions in UML are different from regular transitions, because the internal transitions never cause execution of state exit or entry. Internal transitions have also a distinctive notation that is similar to the entry/exit actions (Figure 2). The two internal transitions in state pedsFlash have different guard conditions (the Boolean expressions in the square brackets), which means that they are enabled only if the conditions in the square brackets evaluate to TRUE. The guard conditions are based in this case on the internal counter pedFlashCtr_ that controls the number of flashes of the don't-walk signal.

Turning to the internal structure of the carsEnabled state, the most interesting problem is to guarantee the minimum green light for cars before enabling pedestrians. Upon entry to the carsGreen substate, the timer is armed to expire after the minimum green light time. When the PEDS_WAITING event arrives before the expiration of this timeout, the active state is carsGreenNoPed, and the state machine transitions to the substate carsGreenPedWait, which has the purpose of "remembering" that a pedestrian is waiting. When the minimum green light time expires in the carsGreenPedWait state, it triggers the TIMEOUT transition to the carsYellow state, which after another timeout transitions out of carsEnabled state to open the crossing to pedestrians. However, if the PEDS_WAITING event does not arrive before the minimum green light timer expires the state machine will be in the carsGreenNoPed state that does not prescribe how to handle the TIMEOUT event. Per the semantics of state nesting, the event is passed to the higher-level state, that is, to carsGreen, which handles the TIMEOUT event in the transition to carsGreenInt (interruptible green light).

At this point, the statechart accomplishes the main functionality of the PELICAN crossing. The design progressed top-down, by gradually elaborating the inner structure of hierarchical states. However, you can also design statecharts in the bottom-up fashion. In fact, this is the best way to add the last feature--the "offline" mode of operation.

The offline mode of operation is added simply by enclosing the whole state machine elaborated in the previous steps inside the superstate operational that handles the transition OFF to the offline state. Note how 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. Now, imagine how difficult it would be to make such a last-minute change to a traditional, non-hierarchical FSM.

The PELICAN crossing is ready now, but we still have a big problem of actually generating the external events to the PELICAN state machine, such as PED_WAITING, ON, and OFF. The actual PELICAN crossing hardware provides a push button for generating the PED_WAITING event, as well as the ON/OFF switch to generate the ON/OFF events, but the Toolstick has no external input (Figure 1). For Toolstick, we need to simulate the pedestrian/operator in a separate state machine. This is actually a good opportunity to demonstrate how to combine many state machines that collectively deliver the intended functionality of the application. Refer to the accompanying code for the implementation of the straightforward Pedestrian state machine.

Coding a Statechart in C

Contrary to popular belief, you don't need big code-synthesizing tools to translate UML statecharts to efficient and highly maintainable code. The implementation strategy I use to hand-code the PELICAN crossing statechart in Figure 2 in portable C is based on QP-nano, a generic "event processor" from my company Quantum Leaps. Actually QP-nano is more than just an event processor; it is a complete platform for executing concurrent state machines. Besides the optimized hierarchical event processor, QP-nano also provides event passing mechanism, event queuing, time event generation (timers), and a simple non-preemptive, prioritized scheduler to execute state machines in run-to-completion (RTC) fashion. All these services require about 1300 bytes of code (ROM) and just a few bytes of RAM on the 8051.

QP-nano has been designed for small systems with limited RAM. In this minimal version, events are represented as structures containing the byte-wide enumerated type of the event, such as TIMEOUT or PED_WAITING, which in the UML is called the "signal." Optionally, QP-nano lets every event have a single scalar event parameter. Event parameters are useful to convey the quantitative information associated with the event. For example, an ADC conversion might generate an event with the signal ADC_READY and the parameter containing the value produced by the ADC.

Each state in QP-nano is represented as a C function called a "state handler" function. The job of QP-nano is to invoke these state handler functions in the right order to process events according to the UML semantics.

A state handler function is a regular C function that takes the state machine pointer as the argument and returns a pointer to another state handler function, which is typedefed as QSTATE in the QP-nano header file qpn.h. You need to structure your state handler functions such that they return the pointer to the superstate handler, if they don't handle the current event, or a NULL-pointer, if they handle the current event. QP-nano uses this information to "learn" about the nesting of states to process events hierarchically and correctly execute state transitions.

To determine what elements belong a given state handler function, you first need to look up the state in the diagram and follow around the state's boundary. You need to implement all transitions originating at the boundary, any entry and exit actions defined directly in this state, as well as all internal transitions enlisted directly in the state. Additionally, if there is an initial transition embedded directly in the state, you need to implement it as well. You don't worry about any substates nested in the given state. These substates are implemented in their own state handler functions.

Take, for example, the state carsGreen in Figure 2. This state has one transition TIMEOUT originating at its boundary, an exit action and the initial transition to the substate carsGreenNoPed. The state carsGreen nests directly inside carsEnabled.

Listing One shows the state handler function Pelican_carsGreen() corresponding to the PELICAN state carsGreen. The state handler takes only one argument: the state-machine pointer; Pelican* in this case (1).

By convention, I always name this argument "me". (If you are familiar with C++, you'll recognize that me corresponds to the this pointer in C++.) Generally, every state handler is structured as a big switch that discriminates based on the signal of the current event. To reduce the number of arguments of the state handler function, QP-nano stores the current event in the state machine object pointed to by the me pointer. For convenience, QP-nano provides the macro Q_SIG() to access the signal of the event (2). Each case is labeled by an enumerated signal and terminates with return (QSTATE)0. Returning a zero-pointer from a state handler informs the event processor that the particular event has been processed. On the other hand, if no case executes, the state handler exits through the final return statement, which returns the pointer to the superstate handler function (QSTATE)&Pelican_carsEnabled in this case (11). Please note that the final return statement from a state handler function is the only place where you specify the hierarchy of states. Therefore, this one line of code represents the single point of maintenance for changing the nesting level of a given state.

(1) QSTATE Pelican_carsGreen(Pelican *me) {
(2)     switch (Q_SIG(me)) { /* switch on signal of current event */
(3)         case Q_ENTRY_SIG: {         /* entry action */
                QActive_arm((QActive *)me, CARS_GREEN_MIN_TOUT);
                BSP_signalCars(CARS_GREEN);
(4)             return (QSTATE)0;       /* event handled */
          }
(5)        case Q_INIT_SIG: {                  
(6)           Q_INIT(&Pelican_carsGreenNoPed);/* initial transition */
(7)          return (QSTATE)0;               /* event handled */
          }
(8)       case Q_TIMEOUT_SIG: {
(9)          Q_TRAN(&Pelican_carsGreenInt);    /* state transition */
(10)          return (QSTATE)0;             /* event handled */
            }
        }
(11)    return (QSTATE)&Pelican_carsEnabled;    /* the superstate */
    }

Listing One: State-handler function for the "carsGreen" state.

At the label (3) in Listing One, you can see how to code the entry action. QP-nano provides a reserved signal Q_ENTRY_SIG (and also Q_EXIT_SIG for exit actions) that the event processor sets in the state machine before calling the appropriate state handler function to execute the state entry actions. Therefore, to code a state entry action, you provide a case statement labeled with signal Q_ENTRY_SIG, enlist all the actions you want to execute upon the entry to the state, and terminate the actions with return (QSTATE)0 (4). Coding an exit action is identical, except that you provide a case statement labeled with signal Q_EXIT_SIG.

Every composite state (a state with substates) can have its own initial transition, which in the diagrams is represented as an arrow originating from a black ball. For example, state carsGreen in Figure 2 has such a transition to the substate carsGreenNoPed. QP-nano provides a reserved signal Q_INIT_SIG that the event processor sets in the state machine before calling the state handler function to execute the initial transition. At the label (5) of Listing One you can see how to code the initial transition. You provide a case statement labeled with signal Q_INIT_SIG, enlist all the actions you want to execute upon the initial transition, and then designate the target substate with the Q_INIT() macro (6). You terminate the case statement with return (QSTATE)0, which informs the event processor that the initial transition has been handled (7).

Finally, at the label (8) in Listing One, you can see how to code a regular state transition. You provide a case statement labeled with the triggering signal (Q_TIMEOUT_SIG in this case), enlist the actions, and then designate the target state with the Q_TRAN() macro provided by QP-nano (9). You terminate the case statement with return (QSTATE)0, which informs the event processor that the event has been handled (10).

And this is about all you need to know to code any state (To conserve stack space, QP-nano can handle up to four levels of state nesting). The PELICAN crossing source code (pelican.c) accompanying this article provides more examples, such as coding internal transitions and transitions with guards.

Declaring State Machine Objects

While state handler functions specify the state machine behavior, and as such are represented in code only (ROM), they require a state machine object (RAM) to remember the current active state and the current event. These state machine objects are represented in QP-nano as C structures derived from the QActive structure, which is provided in QP-nano header file qpn.h. The "derivation of structures" means simply, that you need to literally embed the QActive structure as the first member of the derived structure. Listing Two shows the declaration of the Pelican structure. By a convention, I always name the parent structure member super_.


typedef struct PelicanTag Pelican; /* type definition for Pelican */
    struct PelicanTag {
        QActive super_;              /* derived from QActive */
        uint8_t pedFlashCtr__;    /* private pedestrian flash counter */
    };

Listing Two: Declaration of the Pelican state machine "derived from" QActive structure.

Looking at Listing Two, you should convince yourself that the "derivation of structures" simply means aligning the QActive object at the beginning of every Pelican object in memory. Such alignment allows treating every pointer to Pelican as a pointer to QActive at the same time, so any function designed to work with a pointer to QActive will work correctly if you pass to it a pointer to Pelican. In other words, all functions that QP-nano provides for QActive objects will work just fine for the derived Pelican (or Pedestrian) objects. You can think of this mechanism as single inheritance implemented in C.

Actually, when you look at the declaration of the QActive structure in the qpn.h header file, you will notice, that QActive itself is also derived from another structure QHsm. The QHsm structure represents a Hierarchical State Machine (HSM) and stores the current active state and the current event. QActive adds to this an event queue and a timer, which are both necessary elements of an independently executing state machine. In UML, such independently executing entities are called active objects, which explains the origin of the name QActive. The memory cost of QActive object is 6 to 10 bytes of RAM, depending on the size of the pointer-to-function and the configured size of the timer counter.

Of course, it doesn't matter what else you add in the derived structure after the super_ member. In Listing Two, I've declared additionally the pedFlashCtr__ counter, which the Pelican state machine uses for counting the number of flashes of the "don't walk" signal in the pedsFlash state (Figure 2).

Initializing State Machine Objects

Initialization of hierarchical state machines requires some attention because you need to execute the top-most initial transition, which in general case can be quite involved. For example, the top-most initial transition in the PELICAN crossing statechart (Figure 2) consists of the following steps: (1) entry to operational, (2) initial transition in operational, (3) entry to carsEnabled, (4) initial transition in carsEnabled, (5) entry to carsGreen, (6) initial transition in "carsGreen", and finally (7) entry to carsGreenNoPed. Of course, you want QP-nano to deal with this complexity, which it can actually do, but in order to reuse the already implemented mechanisms, you need to execute the top-most initial transition as a regular transition.

Figure 3 illustrates how you do it. You need to provide a special state initial that handles the top-most initial transition as a regular state transition. The initial state is nested directly in the top state, which is the UML concept that denotes the ultimate root of the state hierarchy. QP-nano defines the top state handler function QHsm_top, which by default "handles" all events by returning NULL pointer. ("Handling" events in the top state means really silently discarding them, per the UML semantics.)

Figure 3: The top-most initial transition for the PELICAN state machine.

Configuring and Starting the Application

After you've coded all state machines, you need to tell QP-nano about them, so that it can start managing the state machines (or actually active objects) as components of the application.

QP-nano executes all active objects in the system in a run-to-completion (RTC) fashion, meaning that each active object completely handles the current event before processing the next one. After each RTC step, QP-nano engages a simple scheduler to decide which active object to execute next. The scheduler makes this decision based on the priority statically assigned to each active object upon the system startup (priority-based scheduling). The scheduler always executes the highest-priority active object that has some events in its event queue.

Listing Three shows how to configure and start the application. You customize QP-nano in the qpn_port.h header file, which contains extensive comments explaining all the options (1). Next, you statically allocate all active objects (2-3) as well as correctly sized event queues for them (4-5). Please note, that the highest-priority active object in the system, such as Pedestrian, might not need an event queue buffer at all, because the single event stored inside the state machine itself might be sufficient.

(1) #include "qpn_port.h"        /* QP-nano port */
    #include "bsp.h"            /* Board Support Package (BSP) */
    #include "pelican.h"       /* application header file */

    /*................................................................*/
(2) static Pelican l_pelican;   /* statically allocate PELICAN object */
(3) static Ped     l_ped;    /* statically allocate Pedestrian object */

(4) static QEvent  l_pelicanQueue[1];        /* PELICAN's event queue */
 /* as the highest-priority task, Ped does not need event queue    */

    /*................................................................*/
    /* CAUTION: the QF_active[] array must be initialized consistently
    * with the priority assignement in pelican.h
    */
(5) QActiveCB const Q_ROM QF_active[] = {
(6)     { (QActive *)0,          (QEvent *)0,    0                    },
(7)     { (QActive *)&l_pelican, l_pelicanQueue, Q_DIM(l_pelicanQueue)},
(8)     { (QActive *)&l_ped,     (QEvent *)0,    0 /* no queue */     }
    };
(9) uint8_t const Q_ROM QF_activeNum =
        (sizeof(QF_active)/sizeof(QF_active[0])) - 1;

    /*................................................................*/
    void main (void) {
(11)    BSP_init();                           /* initialize the board */

(12)    Pelican_init(&l_pelican);  /* take the top-most initial tran. */
(13)    Ped_init(&l_ped, 15);      /* take the top-most initial tran. */

(14)    QF_run();                   /* start executing state machines */
    }
Listing Three: Definition of the state machine objects and the main() function.

Next, at label (5) of Listing Three, you define and initialize a constant array QF_active[], in which you configure all the active objects in the system in the order of their relative priority. QP-nano has been carefully designed not to waste the precious RAM for any information available at compile time. The QF_active[] array is an example of such compile-time information and is allocated in the code-space by the Q_ROM modifier. Q_ROM is a macro that for the IAR 8051 compiler is defined as __code in qpn_port.h. Other Harvard-architecture processors can benefit from this scheme as well. Similarly, at label (9) of Listing Three, you define and initialize another compile-time variable QF_activeNum, which is the total number of active objects actually used in the system. Please note that the zero-element of the QF_active[] is unused, so the number of active objects in the application is the dimension of the QF_active[] array minus 1.

The main() function is remarkably simple. You call the board initialization (11), trigger all initial transitions in the active objects (12-13), and finally transfer the control to the QF_run() function, which implements the QP-nano scheduler running in an endless loop.

Deploying the Application on the Toolstick

Deploying the application on the Toolstick requires only providing the board-specific initialization and the time-tick interrupt, which must call the QP-nano function QF_tick() to generate the TIMEOUT events. The PELICAN example contains a small board support package (bsp.c) for the Toolstick, which has been modeled largely after the standard PWM_demo application that comes on the Toolstick CD.

The code accompanying this article contains an extensive README file explaining all the examples included and the usual workarounds for minor bugs in the demo tools and their incompatibilities. I just wanted to mention here that I ended up using the 4-KB KickStart(tm) 8051 compiler from IAR Systems, instead of the 2-KB demo version of the Keil 8051 compiler that comes with the Toolstick. Finally, because the memory footprint is of primary interest in this article, here are the numbers I've obtained with the IAR 8051 compiler optimized for size: QP-nano: 1254 bytes of CODE, 1 byte of DATA; application totals: 2712 bytes of CODE, 16 bytes of DATA, 88 bytes of IDATA (including 64 bytes of stack), 1 byte of BIT memory.


Reuse of Behavior in UML Statecharts

Statecharts achieve reuse of actions and transitions through a combination of hierarchy and "programming-by-difference" semantics. States may have substates that inherit the actions and transitions of their superstates, just as classes have subclasses that inherit the attributes and operations of their superclasses.

For example, a state diagram of a pocket calculator can be vastly simplified by introducing an abstract superstate "on" that contains most of the calculator states inside (see Figure 4).

[Click image to view at full size]

Figure 4: UML state diagram of a pocket calculator where all substates of "on" superstate share the common transitions CANCEL and OFF.

To understand how the high-level transitions apply, assume that the user presses the CANCEL button while the calculator state machine is in the result state. The state result does not pre-scribe how to handle the CANCEL event. However, the CANCEL event is not silently discarded, as it would be the case in the traditional FSM. Rather, because result is now nested inside the on superstate, the state machine attempts to handle the event at the higher level of state hierarchy of the on state. Because UML statecharts support entry and exit actions on states, the self-transition CANCEL in the on state requires in this case exiting the result state, exiting the on state, en-tering the on state again, taking the initial transition within the on state, and finally entering the begin state.

In summary, the transition CANCEL took the state machine from state result to state begin, properly exiting and entering all the states on the way. Identical argumentation can be made for every substate of the on superstate, so the single CANCEL transition in the on superstate replaces all low-level transitions that would be necessary in the traditional "flat" FSM without hierarchy.

As you can see, the semantics of hierarchical state nesting is based on the "programming-by-difference" principle. All substates of the on superstate need only define the differences from the superstate, and otherwise can reuse the behavior by simply ignoring the commonly handled events, such as CANCEL or OFF.

—M.S.


Conclusions

UML-style state machines can help you produce efficient, maintainable, testable systems with well understood behavior, rather than creating the usual "spaghetti" code littered with convoluted ifs and elses. In this article I've demonstrated that the technique is applicable to quite small systems, starting from about 4KB of ROM, and some 128 bytes of RAM.

Contrary to widespread misconceptions, you don't need big UML tools to take full advantage of the hierarchical state nesting and the guaranteed initialization and cleanup of states, which are the most important features of UML statecharts. In fact, manual coding of a nontrivial PELICAN crossing statechart turned out to be a rather simple exercise in following just a few straightforward rules. The implementation technique based on an "event processor", such as QP-nano, results in concise, highly maintainable code that truly reflects the statechart structure without any repetitions. The resulting state machine representation in C is flexible, allowing even sweeping changes in the state machine structure to be accomplished quite easily, at any stage of the project.

Once you design a system with UML statecharts, you will not want to go back to the "spaghetti" code or even to the traditional RTOS. Welcome to the 21st century.

References

Quick UML Reference.

Quick UML Visio stencil.

IAR Embedded Workbench for 8051: KickStart Version.

Borland Turbo C++ 1.01.


Miro Samek is the Founder and President of Quantum Leaps, a provider of real-time, state machine-based application frameworks for embedded real-time systems, and author of "Practical Statecharts in C/C++" (CMP Books, 2002).

Listing One shows the state handler function Pelican_carsGreen() corresponding to the PELICAN state carsGreen. The state handler takes only one argument: the state-machine pointer; Pelican* in this case (1).

By convention, I always name this argument "me". (If you are familiar with C++, you'll recognize that me corresponds to the this pointer in C++.) Generally, every state handler is structured as a big switch that discriminates based on the signal of the current event. To reduce the number of arguments of the state handler function, QP-nano stores the current event in the state machine object pointed to by the me pointer. For convenience, QP-nano provides the macro Q_SIG() to access the signal of the event (2). Each case is labeled by an enumerated signal and terminates with return (QSTATE)0. Returning a zero-pointer from a state handler informs the event processor that the particular event has been processed. On the other hand, if no case executes, the state handler exits through the final return statement, which returns the pointer to the superstate handler function (QSTATE)&Pelican_carsEnabled in this case (11). Please note that the final return statement from a state handler function is the only place where you specify the hierarchy of states. Therefore, this one line of code represents the single point of maintenance for changing the nesting level of a given state.

(1) QSTATE Pelican_carsGreen(Pelican *me) {
(2)     switch (Q_SIG(me)) { /* switch on signal of current event */
(3)         case Q_ENTRY_SIG: {         /* entry action */
                QActive_arm((QActive *)me, CARS_GREEN_MIN_TOUT);
                BSP_signalCars(CARS_GREEN);
(4)             return (QSTATE)0;       /* event handled */
          }
(5)        case Q_INIT_SIG: {                  
(6)           Q_INIT(&Pelican_carsGreenNoPed);/* initial transition */
(7)          return (QSTATE)0;               /* event handled */
          }
(8)       case Q_TIMEOUT_SIG: {
(9)          Q_TRAN(&Pelican_carsGreenInt);    /* state transition */
(10)          return (QSTATE)0;             /* event handled */
            }
        }
(11)    return (QSTATE)&Pelican_carsEnabled;    /* the superstate */
    }

Listing One: State-handler function for the "carsGreen" state.

At the label (3) in Listing One, you can see how to code the entry action. QP-nano provides a reserved signal Q_ENTRY_SIG (and also Q_EXIT_SIG for exit actions) that the event processor sets in the state machine before calling the appropriate state handler function to execute the state entry actions. Therefore, to code a state entry action, you provide a case statement labeled with signal Q_ENTRY_SIG, enlist all the actions you want to execute upon the entry to the state, and terminate the actions with return (QSTATE)0 (4). Coding an exit action is identical, except that you provide a case statement labeled with signal Q_EXIT_SIG.

Every composite state (a state with substates) can have its own initial transition, which in the diagrams is represented as an arrow originating from a black ball. For example, state carsGreen in Figure 2 has such a transition to the substate carsGreenNoPed. QP-nano provides a reserved signal Q_INIT_SIG that the event processor sets in the state machine before calling the state handler function to execute the initial transition. At the label (5) of Listing One you can see how to code the initial transition. You provide a case statement labeled with signal Q_INIT_SIG, enlist all the actions you want to execute upon the initial transition, and then designate the target substate with the Q_INIT() macro (6). You terminate the case statement with return (QSTATE)0, which informs the event processor that the initial transition has been handled (7).

Finally, at the label (8) in Listing One, you can see how to code a regular state transition. You provide a case statement labeled with the triggering signal (Q_TIMEOUT_SIG in this case), enlist the actions, and then designate the target state with the Q_TRAN() macro provided by QP-nano (9). You terminate the case statement with return (QSTATE)0, which informs the event processor that the event has been handled (10).

And this is about all you need to know to code any state (To conserve stack space, QP-nano can handle up to four levels of state nesting). The PELICAN crossing source code (pelican.c) accompanying this article provides more examples, such as coding internal transitions and transitions with guards.

Declaring State Machine Objects

While state handler functions specify the state machine behavior, and as such are represented in code only (ROM), they require a state machine object (RAM) to remember the current active state and the current event. These state machine objects are represented in QP-nano as C structures derived from the QActive structure, which is provided in QP-nano header file qpn.h. The "derivation of structures" means simply, that you need to literally embed the QActive structure as the first member of the derived structure. Listing Two shows the declaration of the Pelican structure. By a convention, I always name the parent structure member super_.


typedef struct PelicanTag Pelican; /* type definition for Pelican */
    struct PelicanTag {
        QActive super_;              /* derived from QActive */
        uint8_t pedFlashCtr__;    /* private pedestrian flash counter */
    };

Listing Two: Declaration of the Pelican state machine "derived from" QActive structure.

Looking at Listing Two, you should convince yourself that the "derivation of structures" simply means aligning the QActive object at the beginning of every Pelican object in memory. Such alignment allows treating every pointer to Pelican as a pointer to QActive at the same time, so any function designed to work with a pointer to QActive will work correctly if you pass to it a pointer to Pelican. In other words, all functions that QP-nano provides for QActive objects will work just fine for the derived Pelican (or Pedestrian) objects. You can think of this mechanism as single inheritance implemented in C.

Actually, when you look at the declaration of the QActive structure in the qpn.h header file, you will notice, that QActive itself is also derived from another structure QHsm. The QHsm structure represents a Hierarchical State Machine (HSM) and stores the current active state and the current event. QActive adds to this an event queue and a timer, which are both necessary elements of an independently executing state machine. In UML, such independently executing entities are called active objects, which explains the origin of the name QActive. The memory cost of QActive object is 6 to 10 bytes of RAM, depending on the size of the pointer-to-function and the configured size of the timer counter.

Of course, it doesn't matter what else you add in the derived structure after the super_ member. In Listing Two, I've declared additionally the pedFlashCtr__ counter, which the Pelican state machine uses for counting the number of flashes of the "don't walk" signal in the pedsFlash state (Figure 2).

Initializing State Machine Objects

Initialization of hierarchical state machines requires some attention because you need to execute the top-most initial transition, which in general case can be quite involved. For example, the top-most initial transition in the PELICAN crossing statechart (Figure 2) consists of the following steps: (1) entry to operational, (2) initial transition in operational, (3) entry to carsEnabled, (4) initial transition in carsEnabled, (5) entry to carsGreen, (6) initial transition in "carsGreen", and finally (7) entry to carsGreenNoPed. Of course, you want QP-nano to deal with this complexity, which it can actually do, but in order to reuse the already implemented mechanisms, you need to execute the top-most initial transition as a regular transition.

Figure 3 illustrates how you do it. You need to provide a special state initial that handles the top-most initial transition as a regular state transition. The initial state is nested directly in the top state, which is the UML concept that denotes the ultimate root of the state hierarchy. QP-nano defines the top state handler function QHsm_top, which by default "handles" all events by returning NULL pointer. ("Handling" events in the top state means really silently discarding them, per the UML semantics.)

Figure 3: The top-most initial transition for the PELICAN state machine.

Configuring and Starting the Application

After you've coded all state machines, you need to tell QP-nano about them, so that it can start managing the state machines (or actually active objects) as components of the application.

QP-nano executes all active objects in the system in a run-to-completion (RTC) fashion, meaning that each active object completely handles the current event before processing the next one. After each RTC step, QP-nano engages a simple scheduler to decide which active object to execute next. The scheduler makes this decision based on the priority statically assigned to each active object upon the system startup (priority-based scheduling). The scheduler always executes the highest-priority active object that has some events in its event queue.

Listing Three shows how to configure and start the application. You customize QP-nano in the qpn_port.h header file, which contains extensive comments explaining all the options (1). Next, you statically allocate all active objects (2-3) as well as correctly sized event queues for them (4-5). Please note, that the highest-priority active object in the system, such as Pedestrian, might not need an event queue buffer at all, because the single event stored inside the state machine itself might be sufficient.

(1) #include "qpn_port.h"        /* QP-nano port */
    #include "bsp.h"            /* Board Support Package (BSP) */
    #include "pelican.h"       /* application header file */

    /*................................................................*/
(2) static Pelican l_pelican;   /* statically allocate PELICAN object */
(3) static Ped     l_ped;    /* statically allocate Pedestrian object */

(4) static QEvent  l_pelicanQueue[1];        /* PELICAN's event queue */
 /* as the highest-priority task, Ped does not need event queue    */

    /*................................................................*/
    /* CAUTION: the QF_active[] array must be initialized consistently
    * with the priority assignement in pelican.h
    */
(5) QActiveCB const Q_ROM QF_active[] = {
(6)     { (QActive *)0,          (QEvent *)0,    0                    },
(7)     { (QActive *)&l_pelican, l_pelicanQueue, Q_DIM(l_pelicanQueue)},
(8)     { (QActive *)&l_ped,     (QEvent *)0,    0 /* no queue */     }
    };
(9) uint8_t const Q_ROM QF_activeNum =
        (sizeof(QF_active)/sizeof(QF_active[0])) - 1;

    /*................................................................*/
    void main (void) {
(11)    BSP_init();                           /* initialize the board */

(12)    Pelican_init(&l_pelican);  /* take the top-most initial tran. */
(13)    Ped_init(&l_ped, 15);      /* take the top-most initial tran. */

(14)    QF_run();                   /* start executing state machines */
    }
Listing Three: Definition of the state machine objects and the main() function.

Next, at label (5) of Listing Three, you define and initialize a constant array QF_active[], in which you configure all the active objects in the system in the order of their relative priority. QP-nano has been carefully designed not to waste the precious RAM for any information available at compile time. The QF_active[] array is an example of such compile-time information and is allocated in the code-space by the Q_ROM modifier. Q_ROM is a macro that for the IAR 8051 compiler is defined as __code in qpn_port.h. Other Harvard-architecture processors can benefit from this scheme as well. Similarly, at label (9) of Listing Three, you define and initialize another compile-time variable QF_activeNum, which is the total number of active objects actually used in the system. Please note that the zero-element of the QF_active[] is unused, so the number of active objects in the application is the dimension of the QF_active[] array minus 1.

The main() function is remarkably simple. You call the board initialization (11), trigger all initial transitions in the active objects (12-13), and finally transfer the control to the QF_run() function, which implements the QP-nano scheduler running in an endless loop.

Deploying the Application on the Toolstick

Deploying the application on the Toolstick requires only providing the board-specific initialization and the time-tick interrupt, which must call the QP-nano function QF_tick() to generate the TIMEOUT events. The PELICAN example contains a small board support package (bsp.c) for the Toolstick, which has been modeled largely after the standard PWM_demo application that comes on the Toolstick CD.

The code accompanying this article contains an extensive README file explaining all the examples included and the usual workarounds for minor bugs in the demo tools and their incompatibilities. I just wanted to mention here that I ended up using the 4-KB KickStart(tm) 8051 compiler from IAR Systems, instead of the 2-KB demo version of the Keil 8051 compiler that comes with the Toolstick. Finally, because the memory footprint is of primary interest in this article, here are the numbers I've obtained with the IAR 8051 compiler optimized for size: QP-nano: 1254 bytes of CODE, 1 byte of DATA; application totals: 2712 bytes of CODE, 16 bytes of DATA, 88 bytes of IDATA (including 64 bytes of stack), 1 byte of BIT memory.

Conclusions

UML-style state machines can help you produce efficient, maintainable, testable systems with well understood behavior, rather than creating the usual "spaghetti" code littered with convoluted ifs and elses. In this article I've demonstrated that the technique is applicable to quite small systems, starting from about 4KB of ROM, and some 128 bytes of RAM.

Contrary to widespread misconceptions, you don't need big UML tools to take full advantage of the hierarchical state nesting and the guaranteed initialization and cleanup of states, which are the most important features of UML statecharts. In fact, manual coding of a nontrivial PELICAN crossing statechart turned out to be a rather simple exercise in following just a few straightforward rules. The implementation technique based on an "event processor", such as QP-nano, results in concise, highly maintainable code that truly reflects the statechart structure without any repetitions. The resulting state machine representation in C is flexible, allowing even sweeping changes in the state machine structure to be accomplished quite easily, at any stage of the project.

Once you design a system with UML statecharts, you will not want to go back to the "spaghetti" code or even to the traditional RTOS. Welcome to the 21st century.

References

Quick UML Reference.

Quick UML Visio stencil.

IAR Embedded Workbench for 8051: KickStart Version.

Borland Turbo C++ 1.01.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.