Channels ▼
RSS

C/C++

State Machine Design in C++


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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

ubm_techweb_disqus_sso_-5e79a965f7db2b2a438bb9e6461d6580
2014-06-21T10:38:12

If if this article is about fsm frameworks then there are several pretty sophisticated ones available:

http://www.boost.org/doc/libs/...

http://smc.sourceforge.net

If this article about practical matters of designing fsm it is way too shallow in my view.


Permalink
AndrewBinstock
2014-01-27T17:36:14

This article was written almost 14 years ago, so it's unlikely the author will be checking for comments to respond to.


Permalink
ubm_techweb_disqus_sso_-e83a784924bbf5d1f46c7e9069798cf1
2014-01-26T17:46:19

Can you please list the issues in using reinterpret_cast for function pointers. What could be the best way in C++ to have a state machine framework which can be derived by any module for executing the state machine..

Like lets say SMFrameWork class just sets the state, executes the FSM...Derived1 class has memfns1, memfns2..memfnsN array of member functions....Deriver2 class has mFn1,mFn2,...mFnN array of member functions..I am trying to use your framework for ths model...Everything works fine...But when i have some derived class for Derived1 class..Ex: class Derived1 : public Derived5.....Then i am getting compilation error...Only way to avoid this case is declaring class SMFramework:public Derived5..

Can you please let me know is there any other approach to solve this problem...What are the problems that could arise in using reinterpret_cast


Permalink
AndrewBinstock
2013-09-10T05:58:38

Thank you!


Permalink
ubm_techweb_disqus_sso_-9b2980272a94afda643ab2441814c479
2013-09-10T05:09:56

The fix for the compile errors on GCC are here: http://www.gamedev.net/topic/2...


Permalink
ubm_techweb_disqus_sso_-f2952fb74c51b8b3afa781c75a6e175f
2012-11-07T21:26:19

Great article will try it.


Permalink
ubm_techweb_disqus_sso_-eedc6d454628af292e3eda19d6e0fc12
2012-02-13T08:27:01

It is my experience that maintaining a state machine in code, either C or C++, is very difficult. It is very hard to get an overview, as the states, their transitions and the attached activities get fragmented and spread out over many pieces of code. This goes for both the C++ state pattern and the method described in this article.
May I propose that state machines are maintained in a spreadsheet, giving the classic state table overview. Then they can be saved as comma separated files that are automatically translated by a small script or program to code, e.g. as state pattern classes or the macro approach described in this article.
If you want a graphical display of the state machine, use a similar script translating from the comma separated file into a graph, using graphviz.
This approach should be usable by all software shops, especially those who cannot afford a proper state/event machine tool with code generation, which historically have been very expensive.
Fortunately open source and inexpensive SEM tools are appearing. Take a look at some of them.


Permalink
ubm_techweb_disqus_sso_-423c3daeb800f393f38c48fd76f73ed4
2012-02-10T02:43:51

Great article. An excellent example of table driven design. This is also how you can do a state machine in C. With C++, we should rely more on objects. After spending years in C++ and C#, I would have expected a more object oriented approach. Also, the macros reduce readability when you try to translate what they are doing. Using a strategy pattern could accomplish the same thing and would lead to a good object oriented solution.


Permalink

Video