Advertisement

State machine shortcuts

Michael Kreiman

June 23, 2003

Michael KreimanJune 23, 2003

A subset of the UML statechart notation leads to relatively simple code implementations. This article will show you which subset to use and how to go about it.

If you've never used state machines to implement your software designs, you'll discover that they enable you to specify your system's behavior to perform deterministically. Needless to say, if you've used state machines before, you're probably a big fan. Designing your software using state machines and formalized UML semantics and notations enables you to take advantage of commonly used software design principles. As you go through the more detailed parts of your design, having these standardized pictorial representations enables you to find and design even the most esoteric parts of your system prior to coding.

Two design patterns commonly occur: event-based state machines and periodic state machines.

Event-based state machines are state machines in which all internal transitions occur in response to events. These events can be generated from timers, interrupts, or other software.

Periodic state machines run at a regular interval and make all internal transitions in response to changes in data or input signals polled at those times. This type of state machine might also be a source of events for an event-based counterpart.

This article begins with examples of both types of state machines using a subset of UML I find extremely useful. We'll then get into the basics of problem partitioning and communication between state machines and finish by discussing some aspects of code generation that take advantage of the UML subset.

Event-based state machines
Let's start by discussing some basic semantics that occur within event-based state machine designs.


Figure 1: An event-based state machine

You'll notice several things from Figure 1. First, there are six states in the diagram: SUPERSTATE_A, SUBSTATE_A, SUBSTATE_B, SUBSTATE_C, SUBSTATE_D, and STATE_B. Second, notice that transitions (arrows) originate from one of two sources: the states or the conditional connectors (diamonds); transitions also end at a state or conditional connector. Third, notice the superstate concept exhibited by SUPERSTATE_A, which contains four substates. This construction is called a hierarchical state, because it represents two (or more) distinct levels of states that will be active concurrently at any given point in time, typically with the substate providing more detailed information than the superstate. For example, while you're swimming, your superstate might be called SWIMMING, while you might also be in one of several substates, such as FREE_STYLE, BACK_STROKE, or UNDER_WATER. They're also called "OR" states, because if your state machine is in SUPERSTATE_A, it also must be in one of the four substates. Hierarchical states are known as Harel extensions.

Several transitions occur at the superstate level. This means that the event will be accepted regardless of the current substate. In Figure 1, EV_4 begins at the boundary of SUPERSTATE_A, and ends at SUBSTATE_C. This means that, as long as your system is in SUPERSTATE_A, and regardless of which substate it's in, the system will transition to SUBSTATE_C on reception of EV_4. Another example is the transition that occurs on reception of EV_7. SUPERSTATE_A will be exited, including whatever substate the system is in, and STATE_B will be entered.

In the UML, all levels of state machines must have default states. A default state represents the first state that the state machine is in at initialization or object construction. Default transitions are represented by solid dots with arrows to the initial (default) state. In Figure 1, note the difference in transitions between EV_8 and EV_9. If EV_8 is received while the system is in STATE_B, the system will transition directly to SUBSTATE_D. In contrast, if EV_9 is received while the system is in STATE_B, the system will transition to SUBSTATE_A, since this is the default substate of SUPERSTATE_A.

Now let's discuss the conditional evaluation of transitions that occurs when events are received. Two UML notations allow this sort of evaluation.

The first notation is the conditional connector, which allows the option to perform a transition if a given condition evaluates to true. For example, consider EV_1 from SUBSTATE_A, which enters into a conditional connector (represented by the diamond). The conditional connector will then branch to SUBSTATE_B if case_x is true; to SUBSTATE_C if case_y is true; otherwise it will not branch.

The second notation is a guard condition, which is similar to a conditional connector. As an example, consider the reception of EV_2 while in SUBSTATE_B. In this case, case_z will be evaluated, and the transition to SUBSTATE_C will only occur if case_z is true. Thus, the guard condition will only allow a transition to occur if the condition evaluates to true.

Now let's look at some actions that can be associated with states and transitions. I've used two types of actions in this subset. The first actions, called entry actions, are performed on entry into a state. In Figure 1, entry actions exist in substates A, C, and D. The second type of actions, called transition actions, are performed on transition to a state. Note that the transition destination may be a new state (EV_3) or a return to the same state (EV_6). Although the difference between a transition action and an entry action might be hard to grasp at first, the more you work with and optimize your state machines, the more you'll find cases in which one action type is favorable over the other.

It's possible to mix transition and entry actions in the same event-response. If you do, you can be assured that as you execute your state machine, all event responses are treated as atomic operations—that is, once the response is started, regardless of how many transition or entry actions must occur, the entire transition response is guaranteed to complete prior to processing any other events occurring in the application that affects this state machine. Examples of handling different types of actions within a single response are entry actions c1 and c2 in SUBSTATE_C and transitional action 1y from the conditional connector.

By the way, real state-machine designs have more meaningful state, event, and action names. Consider the entry into SUBSTATE_D from SUBSTATE_C. This might be implemented as:


switch (event):
{	case EV_3
		if (current_state==SUBSTATE_C)
		{
			transition_action_3b();
			entry_action_d();
		}
		break;
. . .

Note that I haven't used two UML action notations: exit actions and do actions. Although exit actions are easy to implement, they're merely a shortcut for transition actions that must be executed in all exits from the state. In many of my designs I end up either placing the exit processing in transition or entry actions or partitioning complex hierarchical state machines into separate state machines, with explicit and well-defined protocols for communication, which I'll demonstrate later.

The do action implies that an action must be performed while the software is in a given state. While this is a noteworthy principle, there's an issue with this: you can't specify the frequency with which you must perform the do action. A simple way to implement or substitute for a do action is to set a timer that will return an event and transition back to the same state; then you'll know how often you'll perform the do action.

Other statechart notations I haven't used are join and fork. For simplicity, I also don't use nested action processing per the strict UML notations, since I limit hierarchical nesting to two or three levels within a given state machine. It's possible to create simpler and more reusable designs by partitioning complex hierarchical state machines into separate, less complex state-machines.

Periodic state machines
The second design pattern is similar to the first, except for these two key differences:

  • A periodic state machine is executed at a predetermined rate. This contrasts with an event-based class, which is only invoked upon reception of an event.
  • Transitions result from changes in data or input signals.


Figure 2: A periodic state machine

Figure 2 shows an example of a periodic state machine. This state machine will periodically poll an input signal, x_poll. Transitions are based on the current state and the value of x_poll. Note that debouncing, buffering and other techniques may be appropriate before making a state transition based on a particular input.

Note that with this repertoire, periodic state-machines can be implemented as a subtype or inherited type of event-base state machines. To do this, you can set all transitions as responses to some sort of timeout event. For example, in Figure 2, a periodic timer is started that, upon expiration, sends a PERIODIC_TIMEOUT_EVENT to the state machine. Upon reception of the timeout, the periodic state machine polls input signals x_poll and y_poll, and transitions will then occur only if the x_poll or y_poll value results in a change.

To add an additional notation to our repertoire, I've included a vertical line in Figure 2. This line represents a partition of the state machine into two concurrent states. Such concurrent states are also known as "AND" states. This state machine will always be in two states simultaneously—one state on the left side and one on the right. Note that "AND" states may also exist in event-based state machines. In either type, it's possible to partition the concurrent states into separate state machines.

State machine partitioning
One of the hardest things about state-machine design is deciding when and how to use concurrent and nested state machines. When a state machine starts to seem overly complex, try breaking it out into either a separate or a nested state machine, as appropriate. I typically choose to break them out into separate state machines when the nesting levels get greater than two or three. This also keeps the code simple in each of the classes, and enables me to enforce my own rules—mainly that the higher-level class initiates the lower-level classes, whereas the lower-level classes respond upon significant activity completion to the higher-level classes.

Example
Here's an example of partitioning. Let's consider a three-class subsystem that implements channel play, scan, and seek operations, say for a radio tuner. The three classes, each containing internal state machines, are a Manager, a Scanner, and a Seeker. Figure 3 shows the relationship of the subsystem classes. What follows is an explanation of each class and how they interact.


Figure 3: Subsystem class diagram


Figure 4: Manager state machine

Manager
The Manager is the single-point interface to the outside world for this subsystem. In this example, the Manager is composed of three substates: PLAYING, SEEKING, and SCANNING, as shown in Figure 4. The Manager thus controls the overall "mode" of operation for the subsystem.

The Manager accepts the SEEK_REQUEST_EVENT, SCAN_REQUEST_EVENT, and PLAY_REQUEST_EVENT events from the outside world. The class will also receive SCAN_COMPLETED_EVENT and SEEK_COMPLETED_EVENT events from the Scanner and Seeker state-machines, upon completion of those activities. As an example of run-time event dispatching at this level, once the Manager is in the SCANNING substate, all events that are received from the external world that do not induce any processing at the Manager level are further dispatched to the respective state machines (either the Scanner or the Seeker), based on the current active substate of the Manager.

Scanner
The next level down in our subsystem contains the Scanner. This state machine receives events from the Manager and appropriately decodes them into valid SCAN transitions. Figure 5 shows the scanner state machine.


Figure 5: Scanner state machine

The SCAN_ABORT_EVENT events are accepted at the superstate level. This means that at any time, the Scanner's state machine may be aborted, via request from the Manager. In this state machine, we see three levels of hierarchical state-machine communications: the Scanner's state machine talks not only to the Manager's state machine but also to the Seeker's state machine, as shown by the SCANNING substate in Figure 5.

Seeker
At the lowest level of our subsystem resides the Seeker. This state machine receives requests from and reports back (upon significant activity completion) to either the Manager or the Scanner.

A SEEK_START_EVENT event has an additional parameter associated with it: the requester. The Seeker state machine must keep this information once it begins seeking, so that upon completion of the seek activity, it can inform the requester that the action has been completed. The requester will then be able to clean-up its own state machine, and in the case of the Scanner, report completion up another level (to the Manager).

As you get more classes with state machines in your subsystem, you'll find it more and more important to clearly identify the synchronization patterns and mechanisms, with common issues being how to initiate starts, stops, and aborts of state machines. A good code structure will definitely make your life easier as you progress through your design and encounter similar scenarios in other state machines in your system.

Note that in this example implementation, I have explicitly broken up one hierarchical state machine, containing the Manager, Scanner, and Seeker state machines as nested levels, into three simpler and separate state machines, with strict protocols for starting, stopping, and aborting each state machine. This has helped me generate relatively simple, low-complexity code, as you'll see in the next section.


Figure 6: Seeker state machine

Generating code
It's straightforward to generate simple code, because a class or subsystem of classes can be decomposed into a single or set of state machines following the subset of UML notations I've presented in this article. In this section, I'd like to discuss a few strategies that I've found useful. As you work with them, you'll probably add plenty of your own.

Keep state machines simple.
As you go through your design, you'll refine the number of classes and what their responsibilities are. If a state machine gets overly complex, it's probably best to see if you can break it up into multiple classes, each with a state machine of its own. If you can clearly define a logical partition between the two parts of your larger state machine, then it's easier to break these out into multiple state machines. Or, perhaps implement some basic nesting into your state machine, following UML specification guidelines.

Use the Active Object design pattern as your base class.
For the purpose of this article, Active Objects are classes that respond to stimuli (internal or external events). Active Objects are typically represented as separate threads or processes in your system. They're typically mapped at design time to your overall application task model. By designing your system using Active Objects, you'll find it much easier to move your Active Objects to different tasks and processes as your application tasking model requirements change. The design pattern takes the following form:

// State Variable
static uint8_t xxx_current_state;

// Generic Event Receptor Function
xxx_process_event(event_type e);

where the xxx_current_state variable represents the current state in your state machine. The xxx_process_event() function accepts an event and processes it to completion.

Using the above base pattern, many classes can inherit from this to support their individual state-machine implementations. The inheritance can be manual, through coding practices, if you don't have inheritance support within your programming language.

Clearly separate superstates and substates.
For example, when implementing Figure 1, you might have the following code:


// Superstates
#define SUPERSTATE_A	0
#define STATE_B		1


// Substates
#define SUBSTATE_A	0
#define SUBSTATE_B	1
#define SUBSTATE_C	2
#define SUBSTATE_D	3

Note that if you had multiple sets of substates within different superstates, you should make these mutually exclusive with all other substates at that level. For example:


#define SUBSTATE_A1  	4

You'll also need two global variables for your state machine:

static uint8_t current_superstate;
static uint8_t current_substate;

Implement events as entries in a lookup table.
Consider the following state table entry format:


struct state_table_type
{
 uint8_t 	current_state;
 event_type	received_event;
 fn_ptr	execute_function;
 uint8_t 	next_substate;
 uint8_t 	next_superstate;
};

where fn_ptr is a typical function pointer:

typedef void (*fn_ptr)(void);

Each entry contains the following fields:

  • current_state: the current substate
  • received_event: the event that occurred
  • execute_function: the code to execute on this transition
  • next_substate: the next substate (after the transition)
  • next_superstate: the next superstate

Now it's possible to create an entry in a table, placed as a constant in ROM, for each part of your state machine. For example, the following entry would be used for accepting event EV_3 while in state SUBSTATE_C:


{
 SUBSTATE_C,
 EV_3
 transition_action_3,
 SUBSTATE_D,
 SUPERSTATE_D
}

Note that at the end of the code in function transition_action_3(), you could directly invoke entry_action_D() (since the system is now entering SUBSTATE_D).

Remember that placing the state-machines into tables is a key part of this technique. This allows direct and easy mapping from design to code, and vice-versa.

Develop a generic event processor function.
A generic event processor function can be called from multiple classes. It's responsible for searching your tables for matching event, state, and possibly superstate entries. On finding a match, the relevant execute_function is called and the state changed. Conveniently, the generic event processor can be overloaded to support tables with no superstate, one superstate, two superstates, and so on, for as many table variations as you intend to use in your application.

Handle conditionals and guard conditions partly in your tables and partly in your execute actions.
If an event moves to either a guard condition or conditional connector, special processing is required in your execute_function. Specifically, you must evaluate the condition, and assign the destination superstate and substate within the execute_function, and not within the ROM table. For example, from Figure 1, EV_1 from SUBSTATE_A enters into a conditional connector. The following would be your table entry:


{
 SUBSTATE_A,
 EV_1,
 Handle_conditional_1,
 NO_NEW_STATE,
 NO_NEW_MODE
}

The handle_conditional_1() function might look like that in Listing 1. Note that on return from executing the conditional function, the generic event processor function would not change either the substate or superstate, due to the NO_NEW_STATE literal.

Listing 1: One way of handling conditional transitions


static void handle_conditional_1(void)
{
 if (case_y)
 {
  transition_action_1y(); 
  entry_action_c1()
  entry_action_c2();
  current_state = SUBSTATE_C;
 }
 else if (case_x)
 {
  current_state = SUBSTATE_B;
 }
}

Minimize the length of your tables.
To do this, you might want to have a different table that's indexed based on the superstate. In that table, you would only process events that are respective to the superstate.

Handle events received at the superstate level with a table entry of ANY_STATE.
You'll find that this is a powerful way to reduce the length of your tables. For example, EV_4 can be accepted when you're in any substate of SUPERSTATE_A with the following table entry:


{
 ANY_STATE,
 EV_4,
 substate_C_entry,
 SUBSTATE_C,
 SUPERSTATE_A
}

Note that this reduces the number of table entries for EV_4 from four to one.

Starter kit
For an example of a complete table-based implementation of the state machine in Figure 1, please download the code at ftp://ftp.embedded.com/pub/2003/07kreiman.

Michael Kreiman is a software architect in Visteon's Telematics/Multimedia Software Group. He has developed embedded software for the military, wireless, and automotive industries. He holds a BSEE from Wayne State University and is currently pursuing an MSCS. Contact him at mkreiman@visteon.com.

Loading comments...