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