fsm.rst

The Finite State Machine (FSM)

Karabo allows to define a full finite state machine (FSM) for cpp devices. The full FSM implementation will check any slot calls which lead to state transitions if they are allowed for the current source state, and automatically set the target state after execution of define entry, exit and transition hooks.

Overview

Finite state machines can be used to model real life system, which for most non-trivial tasks go through different stages (states) during their evolution, or during execution of a task. The system may change its state due to both internal or external events, and subsequent behavior may depend on the current state on the system.

Models can be used to approximate these states, stimuli and resulting behavioral changes and define them in terms of a finite set of states, events and transitions. The result of such an abstraction is a so-called finite state machine. Here the word finite is important, that all expected behavior fits into the deterministic model describe the system with a finite set of elements. Conversely, this means that any state not foreseen as part of the model should be considered faulty behavior and if implemented in software raise and error.

Karabo's FSM engine

Since implementation of FSMs is a recurring task in software development, many already exist. The Karabo framework uses the implementation found in Boost C++ template library: the Meta State Machine (MSM). This choice was recognized to be attractive due to the following reasons:

• It is a part of the Boost library, available as open source and supported by a string developer community.
• The MSM belongs to the class of UML (Unified Modeling Language) state machines with full UML support (nested state machines, orthogonal regions, anonymous and internal transitions etc.)
• It has good and up-to-date documentation.
• The MSM proposes well readable and terse interface for State Transition Diagram (STD) definitions. They are easy to use and conversion from an UML diagram to a STD is straightforward.
• The MSM has a front-end/back-end architecture and provides several front-ends for STD definitions.
• The MSM uses the template metaprogramming technique and we do not need any special precompiler or tool but just a plain C++ compiler. Most of the problems can already be discovered during compile time.
• It offers high performance.

As a disadvantage we should mention:

• Sometimes you may have limitations on a number of states handled.
• The compilation time may increase significantly depending on complexity of STD and chosen front-end.

State machine glossary

It is highly recommended to read MSM user's guide or at least the UML Short Guide and Tutorial, which are available on the boost MSM site. Here, for your convenience, we cite the glossary that can be found in MSM documentation:

state machine

The life cycle of a device, hard or software. It is made of a finite number of states, nested sub-machines, regions, transitions and acts on incoming events. It may have entry and exit behaviors.

FSM

An abbreviation of Finite State Machine

STD

A State Transition Diagram, a description of a FSM in graphical form. In UML convention states are indicated as rounded rectangles and transitions as arrows. An example is given in :ref:`Figure 1<genericFsm>`

state

A stage in the life cycle of a state machine. A state can have entry and exit behaviors.

event

An incident (possibly) provoking a reaction of the state machine in terms of changing its current state.

transition

A specification of how a state machine reacts to an event. It specifies a source state, the event triggering the transition, the target state (which will become the newly active state if the transition is triggered), guards and actions.

action

An operation executed during the triggering of the transition. The action may be an entry, exit or transition action.

guard

An operation evaluating to a boolean which prevents the triggering of a transition which would otherwise fire.

transition table

A tabular representation of a state machine. A STD is a graphical, but possibly incomplete representation of such a table model.

initial state

The state in which the state machine (or submachine) starts into. Having several orthogonal regions means having as many initial states.

sub-machine

A submachine is a state machine inserted as a state in another state machine. It can have multiple occurrences in the statemachine it is contained in.

orthogonal regions

A (logical) parallel flow of execution in a state machine. Every region of a state machine gets a chance to process an incoming event. In UML graphically represented as a round rectangle separated by dashed lines. It is needed when a status of a system during its life cycle has to be described not just by one parameter, e.g. parameters in addition to the state name See. :ref:`Figure 2 <orthogonalFsm>` as an example of a STD with regions.

terminate pseudo-state

When this state becomes active, it terminates the execution of the state machine. The boost MSM does not destroy the state machine as required by the UML standard, however. It thus lets you access the state machine's data after termination.

entry/exit pseudo state

Defined for sub-machines as the connection between a transition into and out of the sub-machine in terms of predefined point.

fork

A fork allows explicit entry into several orthogonal regions of a sub-machine.

history

A history is a way to remember the active state of a submachine so that the submachine can continue from its last active state the next time it becomes active.

completion events (also called completion/anonymous transitions)

When a transition has no named event triggering it, it automatically fires when the source state is active, unless a guard forbids it.

transition conflict

A conflict is present if for a given source state and incoming event, several transitions are possible. UML specifies that guard conditions have to solve the conflict.

internal transitions

transition from a state to itself without having exit and entry actions being called. Instead a transition action is called.

The STD given in :ref:`Figure 1 <genericFsm>` is an example of nested state machines: the top state machine GenericMachine contains two states: AllOkState and ErrorState. The AllOkState is not just a simple state but a subm-achine which in turn contains two states: ReadyState and ActiveState.

The ReadyState is a submachine as well and contains and additional two states: IdleState and ConfiguredState. Remember that every state machine has to be instructed, which state is it initial state. This is represented by an arrow with origin of a small circle. It means that AllOkState is an initial state of GenericMachine, whereas ReadyState is the initial state of AllOkState, and IdleState is the initial state of ReadyState.

In the state machine represented by the diagram this means that the GenericMachine's the first state will be IdleState and the following actions will be called: entry action for GenericMachine, entry action for AllOkState, entry action for ReadyState and entry action for IdleState.

The GenericMachine in the figure is driven by the following events:

SetupEvent

tells the system that it should set itself up, and then change from IdleState to ConfiguredState, or loop back into ConfiguredState from ConfiguredState after a reconfiguration. If the system is in ActiveState the SetupEvent will be ignored.

ActivateEvent

tells the system to go to the ActiveState. Optionally, the guard condition is suffixed to the event name, in square brackets, as shown. It tells that the transition to the ActiveState can happen only if the current state nested into ReadyState is ConfiguredState.

StopEvent

returns the system to ReadyState and, therefore, to IdleState (initial state).

ErrorFoundEvent

transfers the state machine into ErrorState independent of the current state nested into AllOkState.

EndErrorEvent

returns the state machine to the AllOkState, then to the ReadyState and finally the IdleState, as if a state machine had just started.

Another strategy of recovering from an ErrorState is shown in :ref:`Figure 2 <orthogonalFsm>`. It demonstrates two orthogonal regions, running in parallel, so that the status of a state machine is defined by two parameters:

• the state in region A
• the state in region B.

When the OrthogonalFsm state machine starts, it transitions to InitialState in region A and to AllOkState in region B. Subsequent events then drive the state machine to next state in both regions in parallel. In the example case, the events that drive machine in region A do not influence the status in region B. We would expect that if ErrorFoundEvent is processed by the state machine and the system moves to ErrorState in region B, we should not continue normal processing in region A. This is not graphically represented in :ref:`Figure 2<orthogonalFsm>`, but the ErrorState is implied to be a special state, declared as a terminate state or interrupt state. Entering such a terminate state results in termination of state machine in all orthogonal regions.

Entering an interrupt state results in all events being clocked except of EndErrorEvents. This is useful if you want to model error recovery for a real system. After recovery from the error the state of region A will be restored as it was before ErrorFoundEvent.

In the following we will discuss how to use the MSM to implement the two examples given.

FSM Model

The Boost MSM library supports three front-ends for STD definitions: basic, functor and eUML. For Karabo a mixture of basic and functor front-ends in addition to custom macros was implemented. They allow the state machine definition to be more readable in code. To define a state machine we have to operate with the following objects: events, actions, guards, states, state transition tables and state machines.

It is best to follow the mentioned order for state machine definition. Also be aware that all these objects are C++ types (classes), not instances thereof. To start integrating an FSM one should define all these types (events, actions, ...) as nested classes within the "context" of the state machine.

Note

All STDs implemented in Karabo should have errors handled by the state machine, namely, every state machine has to have the special error state.

Note

In Karabo state machine definitions should be separated from the business logic of devices. In this way definitions can be reused in other implementations. The state machine context calls should thus only declare interfaces, whereas the device class inherits from the context class to implement these interfaces.

Events

Events drive the state machine and in C++ are defined using the following macros:

KARABO_FSM_EVENTn(pointerToFSM, EventClass, slotEventFunction [ , argType1 ,...])

where n = 0..4 is the number of arguments passed to the event's slot function; pointerToFSM is a pointer to the state machine class; EventClass the name of the class generated by the macro to implement this event and slotEventFunction is an event processing member function with n arguments of types a*rgType1, ...* .

Example.

class UsersTestFsm : public karabo::core::BaseFsm {

public :
    KARABO_FSM_EVENT0(m_fsm, ActivateEvent, slotActivateEvent)
    KARABO_FSM_EVENT1(m_fsm, SetupEvent, slotSetupEvent,
                             karabo::util::Hash)
    KARABO_FSM_EVENT2(m_fsm, ErrorFoundEvent, errorFound,
                             std::string, std::string)

    // ...

private:
  KARABO_FSM_DECLARE_MACHINE(MyFsm, m_fsm);

};

Actions

A transition action is a functor, i.e. a class that implements the void operator()(...). An action may be defined using the following macros:

KARABO_FSM_V_ACTIONn(ActionClass, actionFunction, argType1,...)
KARABO_FSM_VE_ACTIONn(ActionClass, actionFunction, argType1,...)
KARABO_FSM_PV_ACTIONn(ActionClass, actionFunction, argType1,...)

where n = 0..4 is the number of arguments in the calling signature of the event that initiates the transition and ActionClass is the name of generated functor; actionFunction is a virtual (V), virtual empty (VE), or pure virtual (PV) member function with n arguments of types: argType1,...

Example.

class Abc : public karabo::core::BaseFsm
{

public :
    // ...

    KARABO_FSM_PV_ACTION1(
        ConfigureAction, // transition action class (functor)
        configureAction,  // transition action function
        karabo::util::Hash) // type of arg1

    KARABO_FSM_PV_ACTION0(StopAction, stopAction)

    // ...

private:
    KARABO_FSM_DECLARE_MACHINE(MyFsm, m_fsm);
};

Note that class Abc is an abstract base class.

Guards

Guards are functors, i.e. a class that implements operator()(...) with a Boolean return value.

A guard may be defined with the help of the following macros:

KARABO_FSM_V_GUARDn(GuardClass, guardFunction, argType1,...)
KARABO_FSM_VE_GUARDn(GuardClass, guardFunction, argType1,...)
KARABO_FSM_PV_GUARDn(GuardClass, guardFunction, argType1,...)

where n = 0..4 is the number of arguments passed to the event that initiates the transition; GuardClass is the name of generated functor andguardFunction is a virtual (V), virtual empty (VE), or pure virtual (PV) member function with n arguments of types: argType1,...

Example.

class UsersTestFsm : public karabo::core::BaseFsm {

public :

    //...

    KARABO_FSM_V_GUARD1(
        ConfigureGuard, // guard class ( functor )
        configureGuard, // guard function
        karabo::util::Hash)  // type of arg1

    KARABO_FSM_V_GUARD0(StopGuard, stopGuard)

    // ...

private:
    KARABO_FSM_DECLARE_MACHINE(MyFsm, m_fsm);
};

Note that the member functions: