Deepti Mani
embedded.com
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. | |
There are two common approaches for implementing an event based state machine like the one above:
- Using conditional statements
- 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.
typedef enum {
IDLE_STATE,
COIN_INSERTED_STATE,
OPTION_SELECTED_STATE,
MAX_STATES
} state_e;
typedef enum {
INSERT_COIN_EVENT,
SELECT_OPTION_EVENT,
COFFEE_READY_EVENT,
MAX_EVENTS
} event_e;
state_e state = IDLE_STATE;
state_e next_state;
event_e event;
while (1)
{
event = readevent();
if (state == IDLE_STATE)
{
if(event == INSERT_COIN_EVENT)
{
next_state = insert_coin_event_handler();
}
}
else if(state == COIN_INSERTED_STATE)
{
if(event == SELECT_OPTION_EVENT)
{
next_state = select_option_event_handler();
}
}
else if(state == OPTION_SELECTED_STATE)
{
if(event == COFFEE_READY_EVENT)
{
next_state = coffee_ready_event_handler();
}
}
state = next_state;
}
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.
state_e (*state_table[MAX_STATES)[MAX_EVENTS])(void) = {
{insert_coin_event_handler, error_handler, error_handler},
{select_option_event_handler, error_handler},
{error_handler, error_handler, coffee_ready_event_handler},
};
while (1)
{
event = read_event();
if((event >= 0) && (event < MAX_EVENTS))
{
next_state = state_table[state][event]();
state = next_state;
}
}
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.
