EN 
DE Create state machines that are easy to read and maintain
Author: Pawel Wiśniewski, Pawel Wiśniewski Consulting
Contribution – Embedded Software Engineering Congress 2017
State machines are an important part of software. Unfortunately, they are too often implemented manually, for example, using if-else or switch-case constructs. Such constructs are difficult to understand and extend. Additionally, they always look slightly different because they are rewritten from scratch each time. This presentation will demonstrate a solution based on the Boost.SML library. State machines created with this library are not only easier to understand and extend, but they are also often more efficient than handwritten versions.
What are state machines and what are they good for?
Embedded systems are mostly event-driven, meaning they wait for various (internal or external) events. When an event occurs, it is processed. Further internal events can be generated during this processing. If there are no events to process, the system waits again.
This behavior can be implemented as sequential software. However, if the order of events is unknown or if multiple events need to be awaited, sequential software becomes complex. It is significantly simpler to implement event-driven behavior using state machines.
State machines can be graphically represented using UML state diagrams [1]. A state diagram shows the states of a state machine that are allowed at runtime and indicates the events that trigger its state transitions.
The states in a state diagram are represented by rectangles with rounded corners. The arrows between the states symbolize possible state transitions. They are labeled with the events that lead to the respective state transition.
In diagram 1 (see PDFThe most important UML elements can be seen below.
- Initial – Starting point of the state machine
- State – condition
- Transition – Change of state
- Event – An event that triggers a state transition.
- Guard – condition for the transition
- Action – Action during the transition
- Final – End of the state machine
Handwritten implementations (switch-case, if-else)
Let us consider the state machine from diagram 2 (see PDFIt includes three states (Wait for first value, Wait for second value and Calculate), two events (value and done) and one action (insert_value).
It would be possible to implement this state machine using if-else or switch-case constructs. The source code could be as shown in Listing 1 (see PDF) (switch case) or Listing 2 (see PDFThe `if-else` statement looks like this. Unfortunately, at first glance, it's difficult to see what the software actually does in both cases. The entry action of `State Calculate` (`Play_animation`) is, in both cases (`if-else` and `switch-case`), more of an exit action of `State WaitForSecondValue`. This can lead to problems if the system is to be extended with further transitions towards `Calculate`.
When there are multiple events and transitions in the system, the source code becomes long and unwieldy. If we want to extend our software to include more states, we need to consider all conditions – even those that are not immediately obvious.
We are trying to replicate the state machine from diagram 2 (see PDF) to extend to include simple error handling, as shown in Diagram 3 (see PDF) can be seen.
The source code (Listing 3, see PDFThe code is now almost twice as long; an extra level with an if condition has been added. We now also have Stop_animation in two places (in lines 11 and 24) as exit actions for Calculate State. With realistic state machines, there are significantly more duplicates.
The basics of the [Boost].SML library [3]
The behavior of state diagram 2 (see PDF) can be defined using UML 2.5 („Textual Representation“) as a state machine transition table (Listing 4, see PDF).
The transitions table clearly shows the conditions under which we transition from one state to another. If we want to extend our transitions table to include error handling, we simply need to add the new transitions (Listing 5, see below). PDF).
The heart of [Boost].SML is the transitions table. The syntax is based on the UML notation shown:
SourceState + event [Guard] / Action = TargetState
The transitions table from Listing 4 (see PDF) can be adopted almost unchanged for use with the [Boost].SML framework (Listing 6, see PDF).
Extending the table is just as easy as in Listing 5 (see PDF).
Besides the transitions table, we need to define all events, actions, and guards. The actions and guards are Callable [2] elements, such as lambda functions (Listing 7, see PDF).
The difference between actions and guards is that actions must not return a value, while guards must return a boolean value. Events are user-defined types, such as structures (Listing 8, see...). PDF).
The completed state machine from diagram 2 (see PDF) is in Listing 9 (see PDF) can be seen there. All states (lines 6-8), actions (lines 11-13), events (lines 2-3), and the transition table (lines 19-25) are clearly visible. The entire source code is easily readable and can be easily compared with Diagram 2. Modifications are easy to implement because the state machine's logic is located in one place and is easy to understand.
Lines 29 to 44 show a simple application of a Boost::SML state machine. It is only necessary to instantiate the state machine (line 32), and then we can trigger transitions in our state machine using process_event (lines 36, 39 and 42).
Additionally, in line 33 we see the RAM usage check performed by the state machine instance. If the instance size exceeds one byte, a compile-time error is generated. Further checks are shown in lines 34, 40, and 43. These checks verify that the transitions are correctly defined. Our state machine is intended to start in the state `Wait_For_First_Value`; this check is performed in line 34. Further checks are carried out after the `process_event` call. These checks occur at runtime and can be used in unit tests.
Comparison of approaches
|
|
Handwritten constructions |
Boost::SML |
|
complexity |
Depending on the number of states and events |
Constant |
|
Expandability/maintainability |
Depending on the number of states and events |
Constant |
|
Testability |
Complex, fragile tests |
Easier |
|
Run time |
Depending on code quality, usually slower. |
Fast, Jump Table |
|
Compile time |
Fast |
A little slower |
|
Dependencies |
no |
C++14 |
Handwritten constructs are usually complex. Implementing transitions requires additional variables containing state information and conditions for the transition logic. If-else constructs are difficult for compilers to optimize and require several CPU cycles to execute. Handwritten state machines are fragile, and all changes must be made carefully.
In the Boost::SLM framework, the transition logic is generated as a jump table at compile time. This makes the compile process slightly slower, but reduces runtime because the compiler can optimize the state machine more effectively. An additional advantage is simplified testing, as transactions, actions, and guards are separated by design. It's easy to test individual components separately. Tests are more robust because changes to the state machine logic only require adjustments to the tests that test the transitions.
Using frameworks like Boost::SML allows us to save development time. Our software becomes easier to read, extend, and test. Runtime is also usually faster because most decisions are made at compile time.
References
[1] https://www.omg.org/spec/UML/2.5/
[2] https://en.cppreference.com/w/cpp/concept/Callable
[3] https://boost-experimental.github.io/sml/index.html
Implementation – our training & coaching
Do you want to bring yourself up to date with the latest technology?
Then find out more here MircoConsult offers training courses/seminars/workshops and individual coaching on the topic of implementation/embedded and real-time software development.
Training & coaching on the other topics in our portfolio can be found here. here.
Implementation – Expertise
Valuable expertise in the field of implementation/embedded and real-time software development is available. here Available for you to download free of charge.
You can find expertise on other topics in our portfolio here. here.
