This post has already been read 2695 times!
A switch statement provides one of the easiest to implement and most common version of a state machine. Here, each case within the switch statement becomes a state, implemented something like:
This method is certainly appropriate for solving many different design problems. When employed on an event driven, multi threaded project, however, state machines of this form can be quite limiting.
The first problem revolves around controlling what state transitions are valid and which ones are invalid. There is no way to enforce the state transition rules. Any transition is allowed at any time, which is not particularly desirable. For most designs, only a few transition patterns are valid. Ideally the software design should enforce these predefined state sequences and prevent the unwanted transitions. Another problem arises when trying to send data to a specific state. Since the entire state machine is located within a single function, sending additional data to any given state proves difficult. And lastly these designs are rarely suitable for use in a multithreaded system. The designer must ensure the state machine is called from a single thread of control.
This article explores state machine design and implements a particular one using C++. The particular implementation solves the aforementioned problems by including support for both internal and external events, event data, and state transition validation. It is multithread-safe. Using this simple state machine base class, a programmer can easily employ state machines on a system-wide basis in a uniform and thread-safe manner.
Why Use a State Machine?
Implementing code using a state machines is an extremely handy design technique for solving complex engineering problems. State machines break down the design into a series of steps, or what are called states in state-machine lingo. Each state performs some narrowly defined task. Events, on the other hand, are the stimuli which cause the state machine to move, or transition, between states. To take a simple example, which I will use throughout this article, let's say we are designing motor-control software. We want to start and stop the motor, as well as change the motor's speed. Simple enough. The motor control events to be exposed to the client software will be as follows:
1. Set Speed — sets the motor going at a specific speed.
2. Halt — stops the motor.
These events provide the ability to start the motor at whatever speed desired, which also implies changing the speed of an already moving motor. Or we can stop the motor altogether. To the motor-control class, these two events, or functions, are considered external events. To a client using our code, however, these are just plain functions within a class. That's how we want it — the client blissfully unaware of the actual implementation.
These events are not state machine states. The steps required to handle these two events are different. In this case the states are:
1. Idle — the motor is not spinning but is at rest.
- Do nothing.
2. Start — starts the motor from a dead stop.
- Turn on motor power.
- Set motor speed.
3. Change Speed — adjust the speed of an already moving motor.
- Change motor speed.
4. Stop — stop a moving motor.
- Turn off motor power.
- Go to the Idle state.
Each state carries out a few specific tasks. The Start state starts the motor by first turning on the power, then adjusting the speed. When changing the speed of an already moving motor, we don't need to turn the power on (it's already on) so we just change the speed. To stop the motor we turn off the power and transition to the Idle state awaiting another command. Therefore, by breaking the motor control into discreet states, as opposed to having one monolithic function, we can more easily manage the rules of how to operate the motor.
To graphically illustrate the states and events, we can use a state diagram. Figure 1 shows the state transitions for the motor control class. A box denotes a state and a connecting arrow indicates the event transitions. Arrows with the event name listed are external events, whereas unadorned lines are considered internal events. (I cover the differences between internal and external events later in the article.)
Figure 1: State transitions for the motor control class
As you can see, when an event comes in the state transition that occurs depends on state machine's current state. When a
SetSpeed event comes in, for instance, and the motor is in the
Idle state, it transitions to the
Start state. However, that same
SetSpeed event generated while the current state is
Start transitions the motor to the
ChangeSpeed state. You can also see that not all state transitions are valid. For instance, the motor can't transition from
Idle without first going through the
In short, using a state machine captures and enforces complex interactions which might otherwise be difficult to convey and implement.
Now that I've touched on some state machine design issues and nomenclature, I want to clarify some of the more important attributes of a state machine. Every state machine has the concept of a "current state." This is the state the state machine currently occupies. At any given moment in time, the state machine can be in only a single state. Every instance of a particular state machine class will have the same originating state. That origination state, however, does not execute during object creation. Only an event sent to the state machine causes a state function to execute.
"State functions" implement each state — one state function per state-machine state. In this implementation, all state functions must adhere to one of two state-function signatures, which are as follows:
<func> are the particular class and function name respectively. For example, you might choose signatures such as
void MyClass::ST_Func(void). The important thing here is that the function return no data (has a
void return type) and that it has at most one input argument of type
EventData* (or a derived class thereof). The
EventData pointer can designate an object of a class that derives from
EventData. Deriving event data from the
EventData class allows the state-machine engine to delete the data once it has been used.
The state functions never return a value. There is no concept of returning an error code when a state function executes because the state machine is designed to handle the event at any time. Therefore, a state machine must always be ready to accept events.
Internal and External Events
As I mentioned earlier, an event is the stimulus that causes a state machine to transition between states. For instance, a button press could be an event. Events can be broken out into two categories: external and internal. The external event, at its most basic level, is a function call into a state-machine object. These functions are public and are called from the outside, or from code external to the state-machine object. Any thread or task within a system can generate an external event. If the external event function call causes a state transition to occur, the state will execute synchronously within the caller's thread of control. An internal event, on the other hand, is self-generated by the state machine itself during state execution.
Once the external event starts the state machine executing, it cannot be interrupted by another external event until the external event and all internal events have completed execution. This provides a multithread-safe environment for the state transitions. Semaphores or mutexes can be used in the state machine engine to block other threads that might be trying to be simultaneously access the same object.
When an event is generated, it can optionally attach event data to be used by the state during execution. Once the state has completed execution, the event data is considered used up and must be deleted. Therefore, any event data sent to a state machine must be created on the heap, via
operator new, so that the state machine can delete it once used. In addition, for our particular implementation the event data must inherit from the
EventData base class (see Listing One). This gives the state machine engine a common base class for which to delete all event data.
Creating event data on the heap may seem like a needless step, but it allows a pointer to the event data to travel through operating system message queues until it arrives at its destination. At that point, the data will be used by the state machine and subsequently deleted. This eliminates the need to send the entire data structure through the queue when just a pointer will do. It's also another reason that event function calls do not return data, such as a status code. When the event finally arrives at its destination, the call being made may have been initiated from a different task, or even a different processor, such that a synchronous return code will have no meaning to the calling thread.
When an external event is generated, a lookup is performed to determine the state transition course of action. There are three possible outcomes to an event: new state, event ignored, or cannot happen. A new state causes a transition to a new state where it is allowed to execute. Transitions to the existing state are also possible, which means the current state is re-executed. For an ignored event, no state executes. However, the event data, if any, is deleted. The last possibility, cannot happen, is reserved for situations where the event is not valid given the current state of the state machine. If this occurs, the software faults.
In this implementation, internal events are not required to perform a validating transition lookup. The state transition is assumed to be valid. You could check for both valid internal and external event transitions, but in practice this just takes more storage space and generates busywork for very little benefit. The real need for validating transitions lies in the asynchronous, external events where a client can cause an event to occur at an inappropriate time. Once the state machine is executing, it cannot be interrupted. It is under the control of the class's private implementation, thereby making transition checks unnecessary. This gives the designer the freedom to change states, via internal events, without the burden of updating transition tables.
State Machine Implementation
Two base classes are necessary to use a state machine object:
EventData. A class inherits from
StateMachine to obtain the necessary mechanisms to support state transitions and event handling. The
StateMachine class also contains various preprocessor macros to ease implementation of the state machine. To send data structures or classes to the state functions, the structure must inherit from the
EventData base class.
I first present a look at the internals of the
StateMachine class. Then I show how to use it correctly.
StateMachine is the base class used for handling state transitions (see Listings Two and Three). Any class implemented as a state machine inherits from this class. The interface is contained within three functions:
ExternalEvent generates an external event to the state machine using as arguments the new state and a pointer to an
EventData object, if any. The
InternalEvent function generates internal events using the same set of arguments. The
GetStateMap function returns an array of state-function pointers which will be retrieved by the state engine when appropriate. This function must be implemented by the inheriting class since it is pure virtual. However, macros are provided to implement this function for us, as I will demonstrate shortly.
StateMachine is used as an inherited base class. The
Motor class is an example of how to use it (see Listings Four and Five).
Motor implements our hypothetical motor-control state machine, where clients can start the motor, at a specific speed, and stop the motor. The
Halt public functions are the external events into the
Motor state machine. Note that to the caller an external event is just a function call. The state machine implementation details are hidden from the client's view of this class.
SetSpeed takes event data, as evidenced by the pointer to the
MotorData structure, which contains the motor speed. This data structure will be deleted upon completion of the state processing, so it is imperative that the structure inherit from
EventData and be created using
operator new before the function call is made.
Motor class is created, its initial state is
ST_Idle. The first call to
SetSpeed transitions the state machine to the
ST_Start state, where the motor is initially set into motion. Subsequent
SetSpeed events transition to the
ST_ChangeSpeed state, where the speed of an already moving motor is adjusted. The
Halt event transitions to
ST_Stop, where, during state execution, an internal event is generated to transition back to the
The state-machine engine knows which state function to call by using the state map. The state map maps the
currentState variable to a specific state function. For instance, if
currentState is 2, then the third state-map function pointer entry will be called (counting from zero). The state map is created using these three macros:
BEGIN_STATE_MAP starts the state map sequence. Each
STATE_MAP_ENTRY that follows has as an argument a state function, which is added to the state map.
END_STATE_MAP terminates the map. The completed state map just implements the pure virtual function
GetStateMap defined within the
StateMachine base class. Now the
StateMachine base class can ask for all the state function pointers via this call.
Notice that we have to use the dastardly
reinterpret_cast<> operator within the
STATE_MAP_ENTRY macro to cast the derived class member function pointer to a
StateMachine member function pointer. It is necessary to perform this upcast since the
StateMachine base class has no idea what the derived class is. So, it is imperative that the entries provided to
STATE_MAP_ENTRY are really member functions of an inheriting class and that they conform to the state function signature discussed earlier. Otherwise bad things will happen.
Each state function must have an enumeration associated with it. These enumerations are used to store the current state of the state machine. In
E_States provides these enumerations, which are used later in the transition map. It is important that the enumeration order matches the order provided within the state map. This way, we can tie a state enumeration to a particular state function call.
CANNOT_HAPPEN are two other constants used in conjunction with these state enumerations.
EVENT_IGNORED tells the state engine not to execute any state, just return and do nothing.
CANNOT_HAPPEN tells the state engine to fault. This is an abnormal catastrophic failure condition that is never suppose to occur.
The last detail to attend to are the state transition rules. How does the state machine know what transitions should occur? The answer is the transition map, which is created using these macros:
Each external event function has a transition map.
BEGIN_TRANSITION_MAP starts the map. Each
TRANSITION_MAP_ENTRY that follows indicates what the state machine should do based upon the current state. The number of entries in each transition map must match the number of state functions exactly. In our example we have four state functions, so we need four entries. The location of each entry matches the order of state functions defined within the state map. Thus, the first entry within the
Halt function indicates an
EVENT_IGNORED. This is interpreted to mean, "If a Halt event occurs while the current state is state Idle, just ignore the event." Similarly, the third entry means, "If a Halt event occurs while current is state Start, then transition to state Stop."
END_TRANSITION_MAP terminates the map. The argument to this end macro is the event data, if any.
Halt has no event data so the argument is a null pointer, but
ChangeSpeed has data so it is passed in here.
The transition map is basically a lookup table indexed by the
currentState variable to determine the course of action. This information is passed to the
ExternalEvent function as an argument along with the event data. When the
StateEngine function executes, it looks up the correct state function pointer by calling
Then, based upon the
currentState variable, it calls one of the state functions in the map:
After the state function has a chance to execute, it deletes the event data, if any, before checking to see if any internal events were generated.
At this point we have a working state machine class. Let's see how to generate events to it. An external event is generated by creating the event data structure on the heap using
new, assigning the structure member variables, and calling the external event function. Obviously, if the external event doesn't take event data then a data structure is not created. The following code fragment shows how a synchronous call is made. You could, of course, send the pointer to the data structure, along with some means of identifying the event, through an operating system message queue to be handled asynchronously by the destination task:
To generate an internal event from within a state function, call
InternalEvent. If the destination doesn't accept event data, then the function is called with only the state you want to transition to:
In the example above, once the state function completes execution the state machine will transition to the
ST_Idle state. If, on the other hand, event data needs to be sent to the destination state, then the data structure needs to be created on the heap and passed in as an argument:
To prevent preemption by another thread when the state machine is in the process of execution, the
StateMachine class uses semaphores within the
StateEngine function. Before the external event is allowed to execute, the semaphore is locked. When the external event and all internal events have been processed, the semaphore is unlocked, allowing another external event to enter the state machine instance.
Comments indicate where the semaphore lock and unlock should be placed if the application is multithreaded. Note that each
StateMachine object should have its own instance of a semaphore. This prevents a single instance from locking a semaphore and preventing all other
StateMachine objects from executing.
Implementing a state machine using this method as opposed to the old switch statement style may seem like extra effort. However, the payoff is in a more robust design that is capable of being employed uniformly over an entire multithreaded system. Having each state in its own function provides easier reading than a single huge switch statement, and allows unique event data to be sent to each state. In addition, validating state transitions prevents client misuse by eliminating the side effects caused by unwanted state transitions.
This implementation offers easy use for the inheriting classes. With the macros it lets you just "turn the crank" without much thought given to the underlying mechanics of how the state engine operates. This allows you more time to concentrate on more important things, like the design of the state transitions and state function implementation.
 Sally Shlaer. Object Lifecycles (Prentice-Hall, Englewood Cliffs, NJ), 1992.