Finite State Machine Design Pattern

Intent

Decouple the implementation of the state-dependent behaviour in a FSM from the management of the states and the state transitions and decouple the clients responsible for triggering state transitions from the FSM implementation.

Based On

This pattern is based on the principle of abstract coupling.

Motivation

Some of the requirements of an OBS are expressed in terms of finite state machines (FSM) which are used to model mode-dependent behaviour. This is typically the case of the management of the operational modes of the OBS as a whole but can also be the case for other functionalities where reference to an FSM is not explicit but where there is a clear need for modelling mode-dependent behaviour.

The most straightforward implementation of these requirements is to construct a module that represents the FSM and that hard-codes the logic for the state transitions and has hard links to the modules that implement the behaviours associated to each state foreseen by the FSM. This approach however leads to ad hoc code that cannot be reused because different FSMs have different mode transition logics and different state behaviours.

This design patterns introduces abstractions that model both the states associated to the FSM and the events that trigger the state transitions in a manner that is application-independent. This allows the construction of a component that represents a generic FSM and that can be customized - without changes to its source code - to represent specific FSMs within a particular application.

Dictionary Entries

The following abstractions or domain-wide concepts are defined to support the implementation of this design pattern:

Structure

The finite state machine design pattern proposes:

an abstract interface to represent the FsmState abstraction
a concrete component to represent the FsmEvent abstraction
a concrete component to represent the FSM abstraction

The FsmState abstract interface is constructed on the assumption that the behaviour of an FsmState abstraction consists of:

actions that are associated to the FSM state.
an entry check that verifies whether the state can be entered.
an exit check that verifies whether the state can be exited.
a termination check that verifies if all actions associated to the current state have been executed.
a next state that must be entered when the actions associated to the current state have been completed.

It is furthermore assumed that the actions that are associated to a state are of three types:

An initialization action: a punctual action performed immediately after the state is entered
A continued action: an action performed continuously while the state is active
An exit action: a punctual action that is performed immediately before the state is exited

Finally, to each state, a next state may be associated. If B is the next state associated to state A, then the FSM will perform an autonomous transition to state B after execution of all the actions associated to state A has been completed.

Given these assumptions, an initial definition for the FsmState abstract interface can be as follows:

The semantics of the methods of this abstract interface can be inferred from their names.

The FSM abstraction is represented by a component instantiated from class FSM. This component acts as a manager for the states associated to the finite state machine. It sees these states as instances of abstract type FsmState and is therefore decoupled from their implementation. The FSM component should be periodically activated by an external agent. The activation will cause the actions associated to the currently active state to be executed.

The FsmEvent abstraction is represented by an abstract interface or abstract class FsmEvent. An FsmEvent is always associated to a finite state machine component. An FsmEvent simply knows that, when its fire method is called, it must lodge with its associated finite state machine a request to perform a transition from the current state to a target state. The target state is encapsulated in the FsmEvent component (it might, for instance, be supplied to it as a constructor parameter). It is up to the FSM to decide when and whether to actually perform the state transition (based, for instance, on whether the current state can be exited and the target state can be entered).

The FsmEvent abstract interface or class could also be characterize by additional operations such as, for instance, an operation to inhibit the event firing.

The logic to perform the state transition can vary. For instance, in some cases, it may be desired to check that the transition has occurred and take a recovery action if this is not the case. In other cases, the transition is not simply to a target state but rather from an initial and pre-defined state to a target state. It is owing to this variability in state transition logic, that the FsmEvent abstraction is represented by an abstract class or abstract interface. Applications are free to create concrete subclasses that implement specific transition logic. Clients that wish to control the state machine hold references to FsmEvents associated to the state machine and, when they wish the state transition to be performed, they call their fire methods. One FsmEvent has to be created for each transition event. Several clients may hold references to the same FsmEvent.

Participants

Client: The components that triggers the state transitions.
FsmEvent: The abstract class or abstract interface that represents the FsmEvent abstraction. State transitions, unless they are autonomous, should only be commanded through instances of this interface.
ConcreteFsmEvent: A component implementing FsmEvent that represents a specific and concrete state transition policy.
FsmState: The abstract class or abstract interface that represents the FsmState abstraction. State-dependent behaviour should be encapsulated in components that implement this interface.
ConcreteFsmState: A component implementing FsmState that represents a specific and concrete state-dependent behaviour.
FSM: A component that implements a generic finite state machine. The component is customized to fit the needs to a specific finite state machine by loading into it the concrete FsmState components and by linking it to the concrete FsmEvent components.

Collaborations

The typical operational scenario for this design pattern is:

A client requests a state transition by calling the fire method in an FsmEvent component. The client sees the event component only through the abstract interface FsmEvent and is therefore insulated from the specific state transition policy that the latter implements.
Some high-level component (perhaps a scheduler) calls the activate methods on the FSM component and causes the state machine to perform the actions associated to the current state.

Consequences

Clients are decoupled from the implementation of the state transition policy and from the implementation of the state-dependent behaviour. Changing the state transition policy or the behaviour associated to a particular state can be done with no impact on the client.
The FSM component can be reused "as is" because it is customizable both with respect to the state-dependent behaviours and with respect to the state triggering policies.
It is possible to build a library of commonly recurring event transition policies and to use them within applications as ready-made components.
It is necessary to have a dedicated class for each concrete transition event and for each state that is required by a concrete finite state machine.

Applicability

This design pattern is useful when:

an application must implement state-dependent behaviours
it is necessary to be able to vary the policies regulating the transitions between states and the behaviour associated to each state

Implementation Issues

Conceptually, there are two different types of operations that can be performed on the FSM components. FsmEvents will want to use its state transition operations to control the FSM state. Other entities will need to have access to its activate operation to direct the FSM component to execute the currently valid state-dependent behaviour. In order to have a better decoupling between these two sets of operations, the structure of the design pattern could be changed as shown in the figure. Now, clients of the FSM components only see the parts of its interface that are relevant to them and safety of operation is correspondingly enhanced.

Which state transition operations should be provided by the FSM component? Probably, a minimal set would include operations to: force a transition from some state A to some state B; inhibit transition from some state A to some state B; and inhibit transitions to some target state. Other operations might be required to allow linking the FSM component to facilities allowing state transitions to be recorded as events.

An FsmEvent makes a request for a state transition to take place in its associated FSM. When is the state transition actually be performed? The simplest policy is for the state transition to be performed immediately: a call to method fire results in the FsmEvent component actually forcing the FSM to change state. This policy however means that the state of the FSM can change in between successive activation. In fact, it can change more than once since different FsmEvents may be fired at different times in the interval between two successive activations. A better policy is for the state transition requests to be processed by the FSM every time it is activated.

FsmEvent and FsmState are conceptually abstract interfaces but in both cases it is possible to identify some basic housekeeping operations that could be implemented at the level of base class. Hence, both FsmEvent and FsmState could be implemented as base abstract classes.

OBS Framework Mapping

The implementation of this design pattern in the OBS Framework is supported by the following classes:

FSMcomponent --> CC_FSM
FsmStateabstract interface --> FsmState
FsmEventcomponent --> DC_FsmEvent

Sample Code

Consider an application that includes a FSM with four modes MOD1 to MOD4 and where two mode transitions are commanded by the ground while the others are autonomous. Implementation of this state machine requires implementation of four FsmState classes corresponding to the four modes and instantiation of two FsmEvent components to represent the commanded transitions. The autonomous mode transitions are modelled inside the FsmState classes.

The kind of FsmEvent components that are required for this state machine is very simple. Their class definition could be as follows:

	class ApcFsmEvent : FsmEvent {

	  int targetState;
	  FSM* fsm;

	  ApcFsmEvent(int ts, FSM* apcFsm) {
		targetState = ts;
		fsm = apcFsm;
	  }

	  void fire() {
		fsm->setState(targetState);
	  }
	}

This class encapsulates a reference to the FSM that it must control and to the target state (represented here as an integer). Its fire method simply calls a setState method on the FSM that causes the transition to be performed. A more sophisticated state transition policy might implement method fire as follows:

    void fire() {
        fsm->setState(targetState);
        if (FSM-getState()!=targetState)
            . . . // state transition did not take place, raise error!
    }

Still other variants of the state transition policy are possible that include operations to inhibit certain state transitions or to check that the starting state is correct.

The example application would need two instances of the FsmEvent. The corresponding instantiation code would look like this:

	FSM* apcFsm;	// reference to operational mode FSM
	. . .
	FsmEvent* t1 = new ApcFsmEvent(MOD1, apcFsm);
	FsmEvent* t2 = new ApcFsmEvent(MOD2, apcFsm);

The t1 objects covers the commanded transition into mode MOD1. The t2 object covers the commanded transition into mode MOD2.

Note how the FsmEvent objects are given the generic type FsmEvent. This makes the code using it independent of the particular transition policy that they encapsulate.

For each state, a dedicated class implementing interface FsmState must be constructed. Consider for instance the class associated to the a simple initialization state:

	class IniState : FsmState {

	  int nextState;

	  IniState(int ns) {
		nextState = ns;
	  }

	  void doInit() {
		return;
             }

	  void doContinued() {
                . . .   // do actions associated to the state
	  }

	  void doExit () {
		return;
	  }

	  bool canExit () {
		return true;
	  }

	  bool isFinished () {
		return true;
	  }

	  int getNextState() {
		return nextState;
	  }

	}

This is a very simple state object where all the actions associated to the state are performed in one single activation cycle and where there are no state initialization or state exit actions. The state "knows" about its successor state which is loaded as a constructor parameter.

The state activation code in the FSM component could be as follows:

	class FSM {
	  FsmState* states[N];
	  FsmState* currentState;
	  . . .
	  void activate() {
		currentState->doContinued();
		if (currentState->isFinished())
		  if (currentState->getNextState()!=NULL)
			setState(currentState->getNextState());
		  else
		. . .	// no successor state is defined, error!
	  }

	  void setState(int newState) {
		if (currentState->canExit())
		{	currentState->doExit();
			currentState = states[newState];
			currentState->doInit();
		}
		else
		. . .	// transition cannot be performed, error!
          }
	  . . .
	}

Method activate would be called periodically to step forward the finite step machine. In the FSM implementation, the continued actions associated to the current state are performed and then a check is done to verify whether the current state wishes to perform an autonomous transition to another state. State transitions are controlled by method setState that verifies whether the current state can be exited and, if so, it performs the associated exit action and then loads the new state and performs its initialization actions. Clearly, the code shown above is independent of either the state transition logic or the implementation of the state-dependent behaviour. This makes the component fully reusable.

The pseudo-code for the FSM class does not show the methods required to configure the FSM component by loading the FsmState components during the initialization phase.

Remarks

There is no equivalent to the finite state machine design pattern in the AOCS Framework because the AOCS framework is using a different concept to model mode-dependent behaviour.

Author

A. Pasetti (P&P Software)

Last Modified

2002-06-22

OBS Framework

Implementation - Design Patterns