StateMachine Usage
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 SetSpeed
and 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.
Listing Four: Defines Motor state machine class
#ifndef MOTOR_H
#define MOTOR_H
#include "StateMachine.h"
// structure to hold event data passed into state machine
struct MotorData : public EventData
{
int speed;
};
// the Motor state machine class
class Motor : public StateMachine
{
public:
Motor() : StateMachine(ST_MAX_STATES) {}
// external events taken by this state machine
void Halt();
void SetSpeed(MotorData*);
private:
// state machine state functions
void ST_Idle();
void ST_Stop();
void ST_Start(MotorData*);
void ST_ChangeSpeed(MotorData*);
// state map to define state function order
BEGIN_STATE_MAP
STATE_MAP_ENTRY(ST_Idle)
STATE_MAP_ENTRY(ST_Stop)
STATE_MAP_ENTRY(ST_Start)
STATE_MAP_ENTRY(ST_ChangeSpeed)
END_STATE_MAP
// state enumeration order must match the order of state
// method entries in the state map
enum E_States {
ST_IDLE = 0,
ST_STOP,
ST_START,
ST_CHANGE_SPEED,
ST_MAX_STATES
};
};
#endif //MOTOR_H
Listing Five: Implements Motor class
#include <assert.h>
#include "Motor.h"
// halt motor external event
void Motor::Halt(void)
{
// given the Halt event, transition to a new state based upon
// the current state of the state machine
BEGIN_TRANSITION_MAP // - Current State -
TRANSITION_MAP_ENTRY (EVENT_IGNORED) // ST_Idle
TRANSITION_MAP_ENTRY (CANNOT_HAPPEN) // ST_Stop
TRANSITION_MAP_ENTRY (ST_STOP) // ST_Start
TRANSITION_MAP_ENTRY (ST_STOP) // ST_ChangeSpeed
END_TRANSITION_MAP(NULL)
}
// set motor speed external event
void Motor::SetSpeed(MotorData* pData)
{
BEGIN_TRANSITION_MAP // - Current State -
TRANSITION_MAP_ENTRY (ST_START) // ST_Idle
TRANSITION_MAP_ENTRY (CANNOT_HAPPEN) // ST_Stop
TRANSITION_MAP_ENTRY (ST_CHANGE_SPEED)// ST_Start
TRANSITION_MAP_ENTRY (ST_CHANGE_SPEED)// ST_ChangeSpeed
END_TRANSITION_MAP(pData)
}
// state machine sits here when motor is not running
void Motor::ST_Idle()
{
}
// stop the motor
void Motor::ST_Stop()
{
// perform the stop motor processing here
// transition to ST_Idle via an internal event
InternalEvent(ST_IDLE);
}
// start the motor going
void Motor::ST_Start(MotorData* pData)
{
// set initial motor speed processing here
}
// changes the motor speed once the motor is moving
void Motor::ST_ChangeSpeed(MotorData* pData)
{
// perform the change motor speed to pData->speed here
}
When the 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 ST_Idle state.
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 STATE_MAP_ENTRY END_STATE_MAP
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 Motor, 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. EVENT_IGNORED and 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:
BEGIN_TRANSITION_MAP TRANSITION_MAP_ENTRY END_TRANSITION_MAP
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 GetStateMap:
const StateStruct* pStateMap = GetStateMap();
Then, based upon the currentState variable, it calls one of the state functions in the map:
(this->*pStateMap[currentState].pStateFunc)(pDataTemp);
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.
Generating Events
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:
MotorData* pData = new MotorData; pData->speed = 50; motor.setSpeed(pData);
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:
InternalEvent(ST_IDLE);
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:
MotorData* pData = new MotorData; pData->speed = 100; InternalEvent(ST_CHANGE_SPEED, pData);
Multithread Safety
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.
Benefits
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.
Reference
[1] Sally Shlaer. Object Lifecycles (Prentice-Hall, Englewood Cliffs, NJ), 1992.
David Lafreniere has designed hardware and software over the past ten years. He currently works at PropHead Development, Inc., a software-consulting firm, designing software for a variety of embedded and PC-based applications. He can be reached at [email protected].
