Implementing finite state machines in embedded systems

A finite state machine is one of the most popular design patterns in embedded systems. Many applications from simple home appliances to complex communication systems implement event based state machines.

The finite state machine is made up of multiple states. At any point of time, the system is in one state and an event triggers certain actions in that state along with a possible change in state. The event could be due to an interrupt in the system, an RTOS signal, a timer expiry indication or an input or indication from another module in the system.

In this article, we will look into the different approaches for implementing state machines using C.

Figure 1 shows a sample state machine for a coffee vending machine. It has three states:

  • Idle,
  • Coin Inserted and
  • Option Selected.

The system waits on user inputs and signals from the coffee dispensing unit. Additional events like debug timer expiry signal could be added.

Figure 1 Sample state machine for a coffee vending machine (Source: The author)

There are two common approaches for implementing an event based state machine like the one above:

  1. Using conditional statements
  2. Using lookup table

Using conditional statements

This is a very simple approach. A switch-case statement or if-else statement is used to check each state. Within each state, another conditional statement is added to check the event triggered. A handler is then added for that state/event combination. Alternatively, we could swap the order and check the event first and then the state. If there is a state change involved, the handler returns the new state.

A sample implementation for the state machine is shown below.

Next page >>

Using conditional statements is an extremely simple approach to get the implementation started. When the number of states and events is few, this method is intuitive and developers get a quick picture of what the state machine is doing. However, as the number of states or events grow, the code can easily go unwieldly. Debugging and maintenance get difficult as the state machine runs into multiple screen pages. It gets even more unmanageable when the handlers span multiple files.

Apart from readability and maintenance issues, designers also need to be aware of the overhead introduced with the conditional statements and account for this during design phase, especially for time critical systems.

Table based approach

In this approach, the state machine is coded in a table with one dimension as states and the other as events. Each element in the table has the handler for the state/event combination. The table could be implemented in C using a two-dimensional array of function pointers.

An example implementation for the coffee vending machine is shown below.

This is an elegant method to translate the state diagram to actual implementation as the handling for every state and event combination is encapsulated in the table. Developers get a quick picture of the state machine and software maintenance is also much more under control.

However, when the table is sparse, that is, there are many invalid state/event combinations, this approach leads to a wastage of memory. There is also a memory penalty as the number of states and events grow. Software designers need to accurately account for this during initial design.

Other considerations

In addition to having handlers for every state and updating the next state, many implementations also have logic to clean up the state machine for the current state and initialize for the next state during a state change. This could be achieved by defining entry and exit functions for every state and invoking them during a state change.

Transition tables could also be defined capturing the special handling needed for transition from one state to another.

Overall, there is no default implementation choice for developing a finite state machine like the one described above. One needs to accurately budget for the overheads introduced and also bear in mind factors such as scalability and readability when choosing an implementation approach.

5 thoughts on “Implementing finite state machines in embedded systems

  1. “I like the simplicity of the switch statement approach, but since the max number of transitions goes up with the square of the number of states, making a reasonably sized switch statement gets unwieldy after 2 or 3 states. This would work well for perhaps

    Log in to Reply
  2. “Another approach is to use a function-pointer as the current state. Then your state transition is accomplished by setting the ptr to the new function to call.nnnThis approach is similar to how it would be done using “deferred words” in 8th (or any F

    Log in to Reply
  3. “I'm really glad to see that the new generation of embedded developers re-discovers state machines. In the old days, the Embedded Systems Programming magazine used to publish several state machine articles every year. The discussed techniques ranged from s

    Log in to Reply
  4. “I think you should also atleast declare the function prototype of all the handlers -it makes it easy then to understand that they are going to always return a State”

    Log in to Reply
  5. “In the sample code, next_state is uninitialized and its initialization state depends on whether a valid state was read. If an invalid state was read, this code could do some strange stuff. Even in sample code, good programming practice should be done.”

    Log in to Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.