This post has already been read 1628 times!

A common design technique in the repertoire of most programmers is the venerable state machine. Designers use this programming construct to break complex problems into manageable states and state transitions. There are innumerable ways to implement a state machine. Some are simple and elegant, others are more complex but offer increased error checking and flexibility.

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:

switch(currentState) {
   case ST_IDLE:
       // do something in the idle state
       break;
    case ST_STOP:
       // do something in the stop state
       break;
    // etc...
}

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.)

fig1

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 ChangeSpeed to Idle without first going through the Stop state.

In short, using a state machine captures and enforces complex interactions which might otherwise be difficult to convey and implement.

Nomenclature

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:

void <class>::<func>(void)
void <class>::<func>(EventData* pEventData)

<class> and <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.

A typical scenario consists of an external event being generated, which, again, boils down to a function call into the class's public interface. Based upon the event being generated and the state machine's current state, a lookup is performed to determine if a transition is required. If so, the state machine transitions to the new state and the code for that state executes. At the end of the state function, a check is performed to determine whether an internal event was generated. If so, another transition is performed and the new state gets a chance to execute. This process continues until the state machine is no longer generating internal events, at which time the original external event function call returns. The external event and all internal events, if any, execute within the caller's thread of control.

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.

Event Data

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.

 

The EventData class
#ifndef EVENT_DATA_H
#define EVENT_DATA_H
 
class EventData 
{
public:
    virtual ~EventData() {};  
};
#endif //EVENT_DATA_H

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.

State Transitions

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: StateMachine and 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:

void ExternalEvent(unsigned char, EventData* = NULL)
void InternalEvent(unsigned char, EventData* = NULL)
virtual const StateStruct* GetStateMap() = 0
Defines base class for state machines
#ifndef STATE_MACHINE_H
#define STATE_MACHINE_H
#include <stdio.h>
#include "EventData.h"
 
struct StateStruct;
 
// base class for state machines
class StateMachine 
{
public:
    StateMachine(int maxStates);
    virtual ~StateMachine() {}
protected:
    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };
    unsigned char currentState;
    void ExternalEvent(unsigned char, EventData* = NULL);
    void InternalEvent(unsigned char, EventData* = NULL);
    virtual const StateStruct* GetStateMap() = 0;
private:
    const int _maxStates;
    bool _eventGenerated;
    EventData* _pEventData;
    void StateEngine(void);
};
 
typedef void (StateMachine::*StateFunc)(EventData *);
struct StateStruct 
{
    StateFunc pStateFunc;    
};
 
#define BEGIN_STATE_MAP \
public:\
const StateStruct* GetStateMap() {\
    static const StateStruct StateMap[] = { 
 
#define STATE_MAP_ENTRY(entry)\
    { reinterpret_cast<StateFunc>(entry) },
 
#define END_STATE_MAP \
    { reinterpret_cast<StateFunc>(NULL) }\
    }; \
    return &StateMap[0]; }
 
#define BEGIN_TRANSITION_MAP \
    static const unsigned char TRANSITIONS[] = {\
 
#define TRANSITION_MAP_ENTRY(entry)\
    entry,
 
#define END_TRANSITION_MAP(data) \
    0 };\
    ExternalEvent(TRANSITIONS[currentState], data);
 
#endif //STATE_MACHINE_H
Implements StateMachine class
#include <assert.h>
#include "StateMachine.h"
 
StateMachine::StateMachine(int maxStates) :
    _maxStates(maxStates),
    currentState(0),
    _eventGenerated(false),
    _pEventData(NULL)
{
}    
 
// generates an external event. called once per external event 
// to start the state machine executing
void StateMachine::ExternalEvent(unsigned char newState, 
                                 EventData* pData)
{
    // if we are supposed to ignore this event
    if (newState == EVENT_IGNORED) {
        // just delete the event data, if any
        if (pData)  
            delete pData;
    }
    else {
        // generate the event and execute the state engine
        InternalEvent(newState, pData); 
        StateEngine();                  
    }
}
 
// generates an internal event. called from within a state 
// function to transition to a new state
void StateMachine::InternalEvent(unsigned char newState, 
                                 EventData* pData)
{
    _pEventData = pData;
    _eventGenerated = true;
    currentState = newState;
}
 
// the state engine executes the state machine states
void StateMachine::StateEngine(void)
{
    EventData* pDataTemp = NULL;
 
    // TBD - lock semaphore here
    // while events are being generated keep executing states
    while (_eventGenerated) {         
        pDataTemp = _pEventData;  // copy of event data pointer
        _pEventData = NULL;       // event data used up, reset ptr
        _eventGenerated = false;  // event used up, reset flag
 
        assert(currentState < _maxStates);
 
        // execute the state passing in event data, if any
        const StateStruct* pStateMap = GetStateMap();
        (this->*pStateMap[currentState].pStateFunc)(pDataTemp);
 
        // if event data was used, then delete it
        if (pDataTemp) {
            delete pDataTemp;
            pDataTemp = NULL;
        }
    }
    // TBD - unlock semaphore here
}

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 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.

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
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.

Reference of this Article

http://www.drdobbs.com/cpp/state-machine-design-in-c/184401236?pgno=1

Leave a Reply

Post Navigation