Event Driven State Machines

Introduction

In our book we have discussed, among other topics, the misunderstandings about state machines. One of the topics which has to be developed is the event-driven idea when designing state machines. This technical note summarizes the problem using simple examples.

We have introduced two types of state machines: Parser and Controller. The Parser type is a state machine whose inputs are true events, i.e. they are used to trigger an (input) action or to change a state and thereafter they are consumed. All information represented by the event has to be stored in states. These types of state machines are used, for instance, in telecommunications for protocol definition. The Controller type of a state machine uses input signals which are of different flavors depending on their origin. Some inputs are static and always exhibit a value; for instance, a digital input can be HIGH, TRUE or UNKNOWN. Other inputs may have a limited lifetime, and it is the task of a designer to define the moment when their value is to be consumed. Most of the state machines used in the industrial control domain are of the Controller type.

Life-time of control signals

The life-time problem of control signals as well as the life-time of actions in an event-driven system has been discussed in the technical note Lifetime of Control Signals and Generating Events. To remind ourselves, we show a simple example, Lifetime, which contains all elements of the topic (Figure 1, Figure 2, Figure 3). We want to repeat an action Send triggered by the command Cmd_Do. The state machine with two states, Idle and Do, does the task.

Figure 1: State transition diagram of the state machine Lifetime

The command Cmd_Do forces the transition from the state Idle to Do. The state machine returns to the state Idle upon receiving the acknowledgement Ack.

Figure 2: Lifetime – the state transition table of the state Do

On entering the state Do, the command is cleared (thus being ready for repetition) and the required action (Send) is performed.

On entering the state Idle, both signals, the Action and Ack, are cleared and are ready for repetition (the Action may be, for instance, a command to the IO-Handler).

Figure 3: Lifetime – the state transition table of the state Idle

Pure event driven

There are systems in which input signals are events by definition. In this case, we may simplify the handling of the input signals: instead of defining the signal’s life-time in each situation, we do it in one place. This technique will be illustrated by the state machine AllEvents (see Figure 4).

Figure 4: The state transition diagram of the state machine AllEvents

The state machine has two inputs, Input1 and Input2. Input1 generates two control values: GoToA and GoToB; Input2 generates a control value, Return. If the state machine is in the state Init (see Figure 5), it goes either to StateA or to StateB depending on the value of the Input.

Figure 5: AllEvents - the state transition table of the state Init

Upon receiving the input Return in the StateA (see Figure 6), the state machine returns to the state Init. It behaves similarly in StateB. Without clearing the input signals in some way, the state machine will loop, or oscillate, thereafter because, on returning to the state Idle, it will be forced by a signal GoToA (or GoToB) to go immediately to the StateA (or StateB), where it will find the signal Return, and so on.

Figure 6: AllEvents - the state transition table of the StateA

Instead of clearing the input signals separately in each state, we may do it in the Always table input actions (see Figure 7), where the signals GoToA and GoToB generated by Input1 clear the Input1, and the signal Return clears the Input2. We may also use a single general clear signal which clears both events triggered by any input signal.

Figure 7: AllEvents - the Always input actions

Why must we make life difficult?

Let’s recollect some basic principles. A state machine models the behavior of a control task. It does it by changing states according to input changes. A state machine generates output actions. A state represents the history of all input changes (in a condensed form). Other interpretations are a sin; especially, a state should not be used to store the present input value.

Using the Parser type of a state machine, we are forced to use states for storing input values. Let’s look at the state machines shown in Figure 8 and Figure 9. The state machine is to make a transition from the state Idle to Done if both inputs arrive: Event1 and Event2. In the Parser type solution, we use states: Storing1 and Storing2 to store the inputs. If we need to do nothing in those states, the solution is probably not optimal, as there is no reasonable excuse for using states Storing1 and Storing2.

In the Controller type solution, the input values are stored (in StateWORKS as a virtual input) and will be cleared if no longer relevant (for instance, in the state Done). In effect, the Controller type state machine does not need auxiliary states for storing inputs, and the transition from Idle to Done is performed if both events arrive.

Figure 8: The state transition diagram of the state machine Parser

Figure 9: The state transition diagram of the state machine Controller

Conclusion

We should avoid using the Parser type of state machine. A Parser type state machine does not allow the use of complex transition conditions, as at any time there is only one input available: the present event. Other control information has to be stored as states, which unavoidably leads to a state explosion. A Parser state machine should be used if the specification of the inputs clearly indicates that the inputs are used to trigger an action or a transition and lose their meaning after that.

StateWORKS allows the definition and implementation of both types of state machines: Parser and Controller. The basic storing mechanism in the form of the virtual input is constructed for static input signals. The designer decides about the lifetime of the input signals. In extreme cases, a designer may use a pure Parser model, consuming all input signals by clearing them in the Always input actions.