State Design Pattern - Finite State Machine (FSM)
Summary
Finite state machines (FSM) are an excellent mechanism for building robust, complex loosely coupled systems. They are applicable for any solution where system requirements dictate modes of operation and more specifically where an event driven environment is required.
This article examines how to use UML state charts for modelling system modes of operation, and then translating these diagrams to design class diagrams and generating code by utilising a variation of (GoF) state design pattern. State Driven Systems
Article
A state driven system (e.g. user input, communications…) is one that receives external triggers (events) and processes this information in different ways depending on its specific mode of operation.
An example of such a system might be a communication parser reading bytes of data from a port. The parser lifecycle comprises the following states;
- Initialise
- Synch
- Parse
The initial state is dedicated to set up of hardware and software objects ready to start receiving information. The next state, synch, searches for the start byte combination indicating the beginning of a data packet. Upon receipt of a valid set of bytes the state changes to a parse state, where bytes of the packet are processed and stored into a holding buffer until the end of the packet is received. When the packet is complete the parser transfers the buffered data to a mailbox of waiting subsystem in a different thread of execution. The parser then returns to the synch state once more ready for the next data packet.
UML state chart notation explicitly captures the lifecycle of event driven systems. For example the parser lifecycle could be modelled as follows;
A further refinement of this would be to assign the 2 operational states (synch, process) as substates of an operational state. The state chart captures the parser life cycle. Now is the time to consider the solution space and develop a design. We shall consider the initial state chart for this example.
How can the state chart be used for creating a design?
A quick side track to investigate how a state machine works will help us create a generic state machine design framework that can be applied to our problem.
The following is a description of an object changing state as captured by state chart:
An object has at any one time a specific operational state. On receiving an event the object may transition from its current state to a next state. The state transition will be constrained by an optional guard condition, if the guard condition is not satisfied the transition will not happen. On leaving a state an optional exit action will be performed, similarly on entering a new state an optional entry action will be performed
In order to develop a design for our example we need to capture and model the concepts of the object lifecycle which will form potential candidate classes. The key point in an object lifecycle is that the object's current state must relate to the next valid state somehow. It is this relationship which is fundamental to the state machine design. The current state need to be able to determine if the conditions have been met to the transition to the next state.
This relationship is modelled most simply as follows;
However, this design has shortcomings in that it does not take account of the case when there is more than one possible next state. To resolve this issue we need to decouple the state from knowing about possible next states and the associated guard conditions for each of these state transition. We need to introduce additional abstractions from the object lifecycle description, moving responsibility for determining which is the next object state into specific transition and guard classes.
Additional state machine concepts;
- State
- Transition
- Event
- Action
- Guard
The key refinements are the addition of the transition class which links one state to the next and has optionally has a guard class containing the test algorithm to determine if the event and current conditions satisfy the test (i.e. the transition is valid). The action class performs processing for the specific state.
The class diagram now looks something like the following;
Here the state has a collection of all possible transition objects. Each transition object contains a next state object reference and optionally a guard object to test if the transition is valid. Also states have optional entry and exit action objects that would be called when transitioning to or from the state.
Further enhancements allow dynamic creation and modification of the state machine at runtime.
For our parser example the design requires concrete classes for each event type, guard specified, actions and transition identified on the state chart. It also needs a class for the parser and a parser context class. The classes required are as follows
- Event classes
- TimeoutEvent
- NewByteEvent
- ReadyEvent
- Guard classes
- ErrorGuard
- EndByteGuard
- StartByteGuard
- Action classes
- ResetAction
- ProcessAction
The Parser class receives messages from the system (timeout and new data received) and calls its current state with the appropriate event and the context object.The Action objects perform processing for each state, which may have an entry and an exit state. The transitions to the self result in calling the ongoing action for the state.
Example code for the parser is available for download!
