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/cpp/lock-options/cpp/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).
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.
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".
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.
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.
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 typedef
ed 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 */ }
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.
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 */ };
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).
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.)
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 */ }
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 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).
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.
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.
IAR Embedded Workbench for 8051: KickStart Version.
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 */ }
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.
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 */ };
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).
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.)
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 */ }
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 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.
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.
IAR Embedded Workbench for 8051: KickStart Version.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.