Hands-on State Machine Programming for Embedded Systems Using Simple Machine (SM): 10 Steps
In this tutorial, I am going to cover the design process of a tiny state machine using my simple machine HSM processor, which is referred to as SM in the remainder of this document.
State machine programming can result in spaghetti code in a short time If you do not use an effective technique to implement it. UML state machines provide a state-of-art way of implementing a state machine in an effective way.
There are a couple of tools you can implement UML state machines. Because of its simplicity, I am going to use my own “experimental” HSM processor to construct a simple blinker machine. Other tools like Boost.MSM, Boost.SML, Tiny FSM, and QP are a little bit complicated to make the water clear. I do not want to make the blurry point blurrier using a sophisticated tool. My HSM processor is very simple and implements most aspects of UML state machines.
Notice: I strongly recommend using QP in your microcontroller system projects. Because implementing a fully-fledged asynchronous architecture needs a bunch of other components. QP has been developing and testing for the last 25 years. It is a robust, reliable, and state-of-art tool to complete even the most complicated MCU projects.
The problem is very simple, do not think much about it: blinking an LED with a 1000 ms period.
The very first solution even baby programmers have is,
The clear drawback of this solution is that blocking and CPU cycle consuming call,
I do not even mention the issues of this call.
Most developers think an RTOS task as a solution for blocking calls,
RTOS would block the thread that calls the task function after toggling the LED. So, other threads would have an opportunity to run their own algorithms. However, an RTOS task is responsive to adedicated code. led_toggle is the dedicated code to the task in our situation. The task is not responsive to other jobs yet.
We are going to solve this stupid and very simple blinking problem using the SM tool.
The SM has only one source file and only one header file. What all we need is included in those files.
Notice: do not judge me because of the quality, algorithm performance, and design of the code. It is an experimental tool and was built in a few days. But, it works and supports most aspects of UML.
The very first step of designing a machine is to define known states. In our case, we will break the whole problem just into two sub-states, “on” and “off” and one top-state which is called “top”.
Designing a state machine usually is not as simple as our blinker machine. Known states are unknowable most of the time. The design process is an iterative process that contains a lot of repetitive steps of the “design-code-test” cycle. You start with some states, they are evolved during the design.
UML diagram of blinker machine was drawn using the QM tool:
Each rounded rectangle represents a state. I am not going to dive into details of UML diagrams, however, I need to put my effort to explain some of the points presented in the diagram:
- 1: this arrow represents a transition called “initial transition”. Initial transitions are basically an opportunity to execute a piece of code once when a state initialize.
- 2 and 5: UML defines an entry and an exit action for every state. Whenever a state begins, again a piece of code can be executed once in the enter action of the state.
- 3 and 4: UML defines a bunch of transition types. Transitions (leaving the current state and going to the target state) occurred whenever an event of interest result in a state transition.
We have got some kind of terminology like action, transition, event, state, and so on. Let’s make them more clear in the code in 10 steps.
The Step 1is to define event IDs,
Events are identified with their event IDs. In our blinker SM example, EVT_ID_TIMEOUT is an event id that is used to create a timeout event.
We can construct an event with the EVT_ID_TIMEOUT id like,
event_t e = MAKE_NAKED_EVT(EVT_ID_TIMEOUT);
MAKE_NAKED_EVT is a macro provided by SM that is used to construct an instance of event_t. Events are represented using event_t type in SM. IDs are needed to be defined in a space that can be seen by state handler implementation later. Event IDs are not defined from the zero value of the enum type because early values of the enum type are used by SM itself.
Naked event term is not an official name, it's mine. I call events that have nothing but just an ID “naked” events.
The next step is to define states. What do those rounded rectangles mean in code, in the SM domain? These kinds of representations are very abstract terms to understand. Let’s see them in code.
A state is basically a variable that has a parent and state handler callback. Because SM supports HSM construction, states are linked with a parent-child relationship. The parent variable is just a pointer to another state, which behaves as a parent. The handler variable is a function callback in which all incoming events to the machine are handled when the machine is in that state. This is the definition of the state handler term also.
const state_t* parent;
};typedef struct _state_t state_t;
state_handler_t is a function callback type.
typedef int (*state_handler_t)(machine_t* sm, event_t e);
The very first parameter of a state handler is the instance of the SM object in which the second parameter, which is the incoming event, can be handled.
So, for step 2, what we need to construct a state is to declare its handler first. We can simply use another SM macro to accomplish the task,
Yes, we declared that there are 3 state handler functions which are defined in “somewhere” for our top, on, and off states, respectively.
Step 3 is to define states. We can use another macro to accomplish the task,
The first column is used to assign the parents of the states. The top state does not have a parent, so a macro called NO_PARENT, which is simply a 0, like NULL of “stdlib.h”, is used. The second parameter is the name of the state. The DEFSTATE macro expands its parameters to the corresponding C valid expressions. STATEREF is a macro that expands its parameter as a C valid expression to be a state reference.
Step 4 is to define a state table. The state table is an array of pointers to the states,
In step 5, we define the blinker machine’s topmost initial handler function,
The topmost initial handler functions must transit to the initial state. The initial state is the off state in our design. The LED starts in the off state.
TRANSIT macro is defined in SM. The line in function body means that “switch to the off state”. We are going to use the notation later again.
The next job, which is step 6, is to define an SM object,
In step 7, we define state handlers which are declared and used to define states previously. State handlers are functions are used to pass events by SM. Assume that the blinker machine was in the off state. This means all the incoming events would be posted into the off state handler.
We have 3 state handlers for the top, on, and off states, respectively. I prefer to implement large state handlers in separate files personally, however, I implemented all the state handlers in a single file in this case,
Yes, we have completed almost all the necessary elements to construct a state machine instance. The next step, which is step 8, is to initialize the state machine object using our prepared arguments,
A state machine instance is initialized with a table, which contains all the defined state references, the size of the table, and a topmost initial handler function.
YES! Machine construction has been completed and it is ready to use!
Step 9, is to start the machine using an SM function,
When the machine starts, SM posts an event to the target state that has EVT_ID_ENTRY id value. This is an autonomous process and triggered by SM itself after calling the sm_start function.
This means that we can make some preparation processes when that event is posted. As I said before, I am not going to dive into UML state machine transition rules. You can get the necessary information from the official UML documentation and also from chapter 2 of the PSiCC2 book.
Yes, our machine is ready to use, what we need to do is just to post events when it occurs. That is the last step, step 10,
I posted a naked timeout event in a pseudo manner to see that my machine works. My debug output from my Eclipse IDE is,
LED ONLED OFFLED ONLED OFFLED ONLED OFFLED ON
That output comes from my bsp.h file,
When I post a timeout event in the last step, which is step 10, the machine switches to another state. Because that event results in state changing. When a switch occurs, this means that the entry action of the target state is executed. So, I called these pseudo BSP functions from the entry actions of the state handlers. That is the reason why my debug output looks like that. The whole implementation can be found on Github.