Tuesday, 25 October 2011

Finite State Machine in C

Finite State Machine is a way of modelling behaviour of some entity that can have a (finite) set of states. Depending on the received event, entity performs some action and changes its state (or remains in the current one).

Let's say we want to model a behaviour of some simple car. I call it "simple" as it has only ignition switch, accelerator and brake. Driver can turn it on, then accelerate, brake and, at the end of the journey, turn it off. If not careful, driver can break the car - if tries to turn it on (again) while driving. Driver's actions are events - inputs of our model. Car can be turned off, idling, moving or broken - and this is a set of our car's states. So, car is in some state, it reacts on driver's command (event), performs some action and goes into the next state.

We have a finite set of states and events and can draw a diagram which precisely define state transitions (state transition diagram):


FSM_CarExample_1

Now, how to implement this model and show how this state machine changes states after receiving events?

Each state can be represented as unique number - its code, or ID. The similar thing is with events. As we have finite number of both states and events, we can use enum type to represent them: one variable will be of enum STATE type and contain the ID of the current state and another variable will be of type enum EVENT and will contain the most recent event this system received. Initially, our car is turned off so the state variable will be set to STATE_TURNED_OFF. After this simple initialization we just need to wait for events and handle them in accordance to the given transition diagram. Events can be obtained from a keyboard or some other source and they are usually kept in a queue as sometimes a new event can be received before processing of the previous one is finished. In this example, in order to keep things simple, I'm gonna assume that processing is fast enough and will just create a predefined set of events and put them in an array.

As we have repetitive action - receiving and handling events - we'll put it in a loop. If our events source is keyboard and we don't know how many events will user issue, we can use while-loop and CTRL-C as a loop termination command. In this example, we have an array of events which is of predefined (known in advance) size so we can use for-loop. Inside this loop, we need to place event processing code for each event, received in each state. This means we will have switch-statement inside another switch-statement. So, here's the code:

main.c:



Output:

Whoooa! I'm turned on!
Yipee! I'm accelerating!
Whoops! Was I too fast?
That was probably enough...

Having a switch inside a switch looks a bit complex and difficult to maintain. If we add a new state, we need to add a new case-branch for each event. In the code above it would mean we need to make changes at 4 different places in the code! Not good!

A solution for this is a state transition table. It is basically a table in which each state has its column and each event has its row. Table elements are pairs action/next-state - let's put them in some structure called TRANSITION. If transition table is called trans_tbl its element, trans_tbl[evt][state] is of type TRANSITION and action is a function called during transition and next-state is the state our model goes into for the current event. Code tells this better:

main.c:


Output is the same:

Whoooa! I'm turned on!
Yipee! I'm accelerating!
Whoops! Was I too fast?
That was probably enough...

The code has shrunk and become easier to understand and maintain: if we want to add a new event or a state, we just need to change transition table (trans_tbl) - we don't need to touch the code in a loop!

My article "Finite State Machine in C++" shows how to use OOP and State design pattern in order to implement FSM described here.

Links and references:
Finite-state machine (Wikipedia)
UML Tutorial: Finite State Machines
Post a Comment