What is a State Machine?

On this page you will learn what state diagrams are, what they consist of and how to create them.

A state machine shows the dynamic behavior of an application. It is a graph of states and transitions that describe the response to events depending on the current state. State machines are used for decades in hardware design. And during the last years also more and more in the area of software development. UML state machines have some significant improvements compared to classical Moore or Mealy state machines. They support hierarchical designs, it is possible to model parallel execution (and states) and several pseudo states were added to further improve expressiveness.

Especially in the embedded real-time domain the use of state machines is popular because the behavior of devices in this domain can be often very well described with state machines.

An important aspect of state machines is that the design can be directly transformed into executable code. This means that there is no break between the design and the implementation. This is all the more important if the device under development has to be certified (e.g. according to IEC61508).

The following picture shows a hierarchical state machine that is used through out this introduction. Figure: This state diagram example shows many of the features supported by the code generator. It was created using the Cadifra UML editor.

Basically a state machine can be represented as a tree of states. A transition e13 connects the two states S12 and S22. If the transition is triggered you have to walk upwards in the tree starting from S12 until you reach a common parent of S12 and S22. Then walk downwards in the tree until the target state (in this case S22) is reached. On the way all the entry and exit code of the visited states has to be executed.

In case the starting state is a composite state it has to be determined which child state to exit in addition. If the target state is a composite state it also has to be determined which child state to enter if too. If history states are used their history has to be considered when entering states.

Luckily the code generator takes care of all these conditions in the generated code. So you don’t have to worry about all the details involved in implementing state machines in a specific language.

Figure: The code generator internally creates a tree from a state diagram. Here the state tree of the example state machine is shown.

State machines can be hierarchical or flat. A machine with sub-states within states is called a hierarchical state machine. States can have entry code that is always executed if a state is entered. Exit code is executed whenever the state is left. Note that the entry and exit code is also executed if a self transition takes place (e.g. e4 or e8 in the example machine). If events shall be processed without triggering the entry and exit actions so called inner events can be used ¹⁾. If for a state no entry and exit actions were declared an inner event behaves exactly like a self transition.

A state can also have a do activity. The do activity code is executed whenever the state is active just before event transitions are evaluated. This means that calculation results from the action code can be used as triggers for state transitions. Every state must have a unique state name.

Actions (i.e. entry/do/exit code) within states shall be non-blocking and short regarding their execution time. On every hierarchy level a default state must be specified. A final state is a state that can’t be left anymore. I.e. the state machine must be re-initialized to be reactive again.

Some UML tools makes it difficult to define action code (e.g. a few C-statements). Therefore it is possible to specify inner events, entry and exit code … for a state by linking a note to a state. See next figure on the right side for an example. The note must start with the text compartment:. Sometimes it is useful to use this option despite the UML tool allows to specify entry/action/exit code directly. As the ’constraints:’ is not supported by any UML tool it must be always defined within an attached comment note (see section 3.6 in the PDF manual for more about using constraints). In principle states can be nested again and again. The code generator was intensively tested with up to four hierarchy levels. If you use more levels reconsider your design!

Figure: Left: A state with entry-, exit-, action code and inner events. Right: Complex state with entry- and exit code specified in a linked note.

There are two types of transitions supported from the code generator. a) event based transitions and b) conditional triggered transitions. An event based transition has the following syntax eventName[guardExpression]/action. The transition is only taken if the guard expression evaluates to true and the event was sent to the state machine. Only in this case the action code is executed. From a transition like

evDoorClosed[timer_preset()>0]/timer_start();

the code generator generates the following C code:

if((msg==(OVEN_EVENT_T)evDoorClosed) && (timer_preset()>0)){
  /*Transition from Idle to Cooking*/
  evConsumed = 1U;
  /*Action code for transition */
  timer_start();
  ...

A conditional (or guard) transition is not triggered from an outside event but when a guard expression is evaluated to true. It has the syntax: #condition/action. Please note that the hash character # must be typed in (i.e. prefix your code statement) to indicate this special type of trigger. From a transition like this:

#i==1/printf(“i==1\n”); the code generator generates the following C code:

if((i==1)){
   ...
   /*Action code for transition*/
   printf("i==1\n");
   ...

Externally defined events: Usually for all events used in a state machine diagram, the required event definitions are generated in the header file *_ext.h. And only these events can be handled from the state machine.

But sometimes it is required to react on events defined externally from the state machine diagram (e.g. existing code is re-used defining own events or the operating system sends predefined events e.g. in case of a timer timeout).

The code generator needs to know that a specific event should be or shouldn’t be included in the event definition process. Therefore such events can be prefixed with an exclamation mark (!). In all other areas of the generation process (state machine handler code, debug helpers etc.) they are included as any other event. ²⁾

Action code defined in transitions must be non-blocking! The next figure shows examples for all types of supported transitions. Action code from an initial pseudo state is only used if the target state of the transition is not in a parent state with history. In history states the usage of actions on the init transition is often misapplied and therefore ignored!

Figure: Examples of possible transitions supported by the code generator.

From top to bottom:

1. Ordered List ItemTransition from an init pseudostate. Only an action expression is allowed here.
2. Simple event with no guard and no action
3. Event with guard. The guard expression enclosed in brackets( [] ) is denoting that this expression must be true for the transition to take place.
4. Event with guard and action. If the transition takes place the action code is executed. The action code must be one or more lines of valid C code.
5. Conditional transition. The transition takes place if the variable i is zero.
6. Conditional transition with action. The transition takes place if the variable i is zero. Additionally the action code is executed.

The OMG UML specification states: “…choice vertices which, when reached, result in the dynamic evaluation of the guards of the triggers of its outgoing transitions. This realizes a dynamic conditional branch. It enables splitting of transitions into multiple outgoing paths such that the decision on which path to take may be a function of the results of prior actions performed in the same run-to-completion step. If more than one of the guards evaluates to true, an arbitrary one is selected. If none of the guards evaluates to true, then the model is considered ill-formed. (To avoid this, it is recommended to define one outgoing transition with the predefined ’else’ guard for every choice vertex.”

The state chart in the next figure shows different options how choices can be used. Choices are represented as diamonds. They can be placed within a composite state or at root level. A choice must have at least one incoming transition. Guards specified at the incoming transition(s) are ignored from the code-generator. Actions are simply copied to the outgoing transitions. Place them at the outgoing transitions.

Usually choices can have only one incoming transition and multiple outgoing transitions (at least two). But the code–generator also allows more than one incoming transition. This is a convenient function to allow the compact specification of complex structures. Internally this construct is handled like two choices with one incoming transition each and the same outgoing transitions.

In case more than one incoming transition is found the choice is doubled for each incoming transition. I.e. it is like modeling two choices with one transition each, and having the same outgoing transitions. At least two outgoing transitions each one with a guard must be defined. One of the guards must be an else statement as described above. Depending of the target state of each outgoing transition the related entry/exit code is generated. Creating chains of choices is not supported.

Figure: Different options to use choices. A default path marked with else must always exist.

Sometimes the initial state of a state machine or sub–machine shall be determined during run–time and not design–time. Examples:

• If the hardware self-test of a device fails the machine should enter an error state and not a normal operation state
• Depending on a parameter (for example set by a user) a specific state shall be entered

In such cases it is possible to connect the initial pseudo–state with the input side of a choice and connect the outgoing transitions with the target states. It is important that there exists one else path to ensure that there is always one option that can be taken by default. Several examples are shown in the following figure. Note that it is possible to define an action on the incoming transition of a choice that reads a value or performs a check and use the result of that function as guard for the outgoing transitions of a choice.

Figure: Choices can be used to determine the initial state at run-time. The figure shows several possibilities how to use this feature.

The OMG UML specification states: … junction vertices are semantic-free vertices that are used to chain together multiple transitions. They are used to construct compound transition paths between states. For example, a junction can be used to converge multiple incoming transitions into a single outgoing transition representing a shared transition path (this is known as a merge).

The UML specification also discusses the possibility of multiple outgoing transitions. This is not supported by the code generator!

The junctions can be seen as a kind of drawing helper in the case you have several transitions ending all in the same state and all of these transitions share some common action. In such a case place the different triggers, guards and action code to the incoming transitions and the common part the the outgoing transition.

Figure: Junction example drawn with Cadifra UML. There is no junction symbol available in Cadifra UML. The shown (J) state is the supported replacement.

The code-generator creates two separate transitions out of this model. The first one from S1 to S3. The second one from S2 to S3.

Limitations and rules:

• A junction should have at least two incoming transitions
• A junction must have exactly one outgoing transition.
• On the outgoing transition no guard and trigger must be defined.
• The action in the outgoing path is appended to actions defined on the incoming paths.
• Incoming transitions must not start from a pseudo state e.g. another junction, choice, …
• The outgoing transition must not end in a pseudo state e.g. another junction, choice, …

Final states have only incoming transitions. Once a state machine enters a final state it will not react on any other event. Exceptions are final states inside a hierarchical state machine. Transitions leaving the parent state of a final state can still be taken. In the next figure the state Final can be left via ev3 or evRealEnd while state Final1 can’t be left anymore.

Figure: Example usage of final states. Once the machine is in state Final1 it can't be left anymore. State Final can be left via event.

In state diagrams usually only one state is active at a time. In UML state diagrams regions also allow to model concurrency – i.e. more than one state is active at a time (AND states).

A UML state may be divided into regions. Each region contains sub-states. Regions are executed in parallel. You can think of regions as independent state machines displayed in one diagram. The state machine in the next figure shows the well known microwave oven example designed using regions. Several regions each running in parallel in the state Active. Dashed lines are used to divide a state into regions.

The power setting, light and microwave radiator are be considered as independent (concurrent) parts of the oven, each with its own states. The door and timer as the main external trigger are used in the regions to trigger state transitions. For example the radiator is switched on if the door gets closed and the timer is > zero.

As you can see multiple concurrent regions can be used to explicitly visualise different parts of a device. And all the states in the one diagram.

Figure: State S1 contains two regions.

Points to consider with regions

• Transitions must not cross region boundaries: In the next figure state transitions do not cross region boundaries and therefore the modellers’ intention is clear. But look at the next diagram. Now it is not clear anymore what the modeller had in mind. And it is also not very obvious what a code generator should generate. For that reason the following constraints were defined.
• Regions must work on the same instance data: State diagrams follow the run-to- completion concept. Transitions that fire are fully executed and the state machine reaches a stable state configuration until it returns and can respond to the next event. To ensure this a copy of the instance data is kept and state changes are only performed on that copy. In practice this means that changes in one region does not influence other regions.

To adapt the generated code to your needs you can add notes to your design that have to start with either ’header:’ or ’postAction:’ or ’action:’ or ’unknownStateHandler:’.

Figure: It is possible to define own code inserted on top of the generated file. This allows to specify own include files or other required local code in the state machine file.

• All code following the ’header:’ keyword is added at the begin of the generated state machine code. This allows to include required header files or the definition of local variables needed within the state machine.
• Code following the ’action:’ keyword is inserted at the begin of the state machine function. This allows to execute own code whenever the state machine is called just before event processing starts. This can be used to receive events from a message queue.
• Code following the ’postAction:’ keyword is inserted at the end of the statem achine function. This allows to execute own code after the state machine code was processed e.g. to enable an interrupt at the end of an interrupt handler function implemented as state machine. Please note that this generator keyword is only available for the following backends: cx, cppx, java, ssc.
• Code following the ’unknownStateHandler:’ keyword is inserted between every default/break pair of the generated code. The given code is executed if the state variables do not hold a valid state. This should never happen and indicates a serious problem in the system (e.g. memory is corrupt due to stack overflow). Alternatively it is also possible to define the code to insert in the codegen.cfg file.

Figure: A message is printed whenever an invalid statevar was found.

For a quick start into state machines play with the toy example which is available in the examples folder other_examples/guisim_client_server. Start the code generator in simulation mode (see sim.run batch file on how to do it) and type in events used in the state diagram (e.g. e13 or e2 followed by a return). Then the simulation performs the state change and calls the related entry / exit and other action code. You can follow what is going on by watching the printouts. Observe especially:

• The order the entry and exit actions are executed in case of event e13
• When e1 triggers a state change to S2 and when it triggers a self-transition to S11
• Understand what happens if transitions start or end at composite states
• Understand the effect of the history marker in S2

Example output of the simulation:

....
Enter event name and press return
e14
msg: e14
printf("S12 Action\n");
printf("S12Exit\n");
printf("e14\n");
printf("S11Entry\n");
 
----------------------
E1
msg: E1
printf("S11 Action\n");
 
----------------------