In many software-design methodologies, we use state transition diagrams to model the behavior of subsystems (processes) or objects with a set of finite states and transitions. In some cases, it becomes obvious that these translate into software implementations beyond the model. The state transition diagram, better known as a finite state machine (FSM) in software implementation, is one of the most popular methods for invoking control-oriented systems. This is particularly true in real-time software applications.
There are a number of techniques for developing finite state machines in software, with one of the more popular being the use of nested switch-case
statements [1]. The drawback to this approach is that as the state machine grows, so does the logic and in C++ this is not an attractive approach to true object-oriented development. There are many methods that have been discussed in development state machines in C++, but none of them has truly drawn a conclusive framework that can be ported from implementation to implementation. Many state machines are written in software straight from their state pattern(s) modeled in some design methodology, such as UML.
In the past, I developed FSMs using basic ANSI C. Listing One is the traditional C-style approach, which avoids the overuse of the switch-case
construct. Recently, with embedded real time moving into C++ as a target language, I have ported this scheme to a simple, yet reusable, framework. Even though the target of such a framework implies embedded real time, it is not limited to it. Think of all those GUI-based applications that pass messages from one window to the next. These are highly qualified state machine candidates.
Listing One: C-style FSM.
// C-style method of doing a simple Finite State Machine #define INVALID_EVENT -1 #define INVALID_STATE -1 typedef int event_t; typedef int state_t; typedef void (*FPAction)(void*); typedef struct State_ State; // State Machine components typedef struct Transition_ { const event_t event; FPAction action; const State* state; } Transition; struct State_ { const Transition* table; FPAction entry; FPAction exit; }; // Create the State Transition Table #define DEFINE_TRANSITION_TABLE(name) \ Transition name##_TransitionTable[] = { #define ADD_TRANSITION(ev,ac,st) \ { ev, ac, st }, #define END_TRANSITION_TABLE \ { INVALID_EVENT, NULL, INVALID_STATE } } // DEFINE_STATE_TABLE #define DEFINE_STATE_TABLE(name) \ State name##_StateTable[] = { #define ADD_STATE(name,entry,exit) \ { name##_TransitionTable, entry, exit }, #define END_STATE_TABLE \ { NULL, NULL, NULL } } // Access operations #define GET_STATE_TABLE_ENTRY(name,st) \ name##_StateTable[st] #define GET_STATE_TRANSITION_TABLE(name,st) \ (name##_StateTable[st]).table #define GET_STATE_ENTRY_CRITERIA(name,st) \ (name##_StateTable[st]).entry #define GET_STATE_EXIT_CRITERIA(name,st) \ (name##_StateTable[st]).exit </pre <P> <h3>The Framework</h3> <p>The new framework must provide a lightweight and portable approach to implementing finite state machines in C++. Traditionally, from what I have read, most take the approach as follows: Given a state machine, a class, <code>T</code>, extends the base state machine class. In this approach, <code>T</code> implies an is-a relationship to the state machine. While there is nothing wrong with this scheme and in itself provides a solid framework, it suffers from exposing the public nature of <code>T</code>. Therefore, <code>T</code> can either be invoked via its own public implementation or via its parent class, the state machine. </p> <P> <p>Since state machines are applied in situations where control dictates the operation of a piece of software, it would seem best to hide <code>T</code> behind the state machine. In other words, you have a state machine of <code>T</code> instead of the other way around. Not only does it hide details about <code>T</code>, but provides communication to <code>T</code> only through the state machine, thus implying the control logic driven by events or messages.</p> <P> <p>I have taken two paths, via a compile-time option, of how <code>T</code> is implemented as a state machine. The first extends <code>T</code> privately (that is, private inheritance). This approach guarantees that an instance of <code>StateMachine<></code> hides the implementation of <code>T</code> at the constructor and the state machine cannot be cast as a T-pointer except by its own members and friends [2]. The downside is that a <code>T</code> will always require a default constructor and force the developer to initialize <code>T</code> with default parameters or obtain them through some other means, which could be an issue for multiple state machine instances of <code>T</code>.</p> <P> <p>The second approach is to contain <code>T</code> as an aggregate association; that is, a private member of <code>StateMachine<></code>. This allows an instance of <code>T</code> to be constructed prior to the state machine creation with the necessary parameters required to initialize it. The drawback to this method is that although <code>T</code> is a hidden member of the state machine, its creation could have been done prior to state machine creation. This provides a dilemma as to whether you allow the state machine to destroy <code>T</code> on its destruction, or whether it is the responsibility of the original creator? I have decided that the state machine will destroy the instance of <code>T</code> upon its destructor being invoked. One way to easily work around who owns <code>T</code> at its creation is solved:</p> <P> <pre class="brush: cpp; html: collapse;" style="font-family: Andale Mono,Lucida Console,Monaco,fixed,monospace; color: rgb(0, 0, 0); background-color: rgb(238, 238, 238); font-size: 12px; border: 1px dashed rgb(153, 153, 153); line-height: 14px; padding: 5px; overflow: auto; width: 100%;"> StateMachine<T,EV,CMP> myStateMachine ( new T(_), initState );
For this article, I use T
through inheritance for the sake of illustration and example. In either case, the state machine plays the surrogate to dispatching control to T
. Listing Two presents the base state machine classes.
Listing Two: Base state machine classes.
#ifdef DERIVE_STATE_MACHINE #define THIS (*this) template <class T, class EV, class CMP = std::less<EV> > class StateMachine : private T { public: explicit StateMachine( State<T,EV,CMP>* const stStart ) : T(), m_stStart(stStart), m_stCurrent(stStart), m_stThis(eStopped) {} // Aggregated Version of State Machine #else #define THIS (*m_T) template <class T, class EV, class CMP = std::less<EV> > class StateMachine { private: T* m_T; public: explicit StateMachine( T* _T, State<T,EV,CMP>* const stStart ) : m_T(_T), m_stStart(stStart), m_stCurrent(stStart), m_stThis(eStopped) {} ~StateMachine() { delete m_T; } #endif // DERIVE_STATE_MACHINE ... // other API functions not shown private: State<T,EV,CMP>* const m_stStart; State<T,EV,CMP>* m_stCurrent; };
The Event
There are four parts to the state-machine framework:
- Event.
- State.
- Transition.
- Action.
Event (EV) is the catalyst that causes the state machine to run; in other words, transition from state to state. Events can also be messages, as they are commonly called in GUI-based applications. Events are internal or external to the system in which the state machine is running. The origin of the event is not of concern to the state machine, at least from this framework's point of view. Pre- and postprocessing of events are not the responsibility of the state machine, since this detracts from the generalization of the framework, which makes it portable.
The state machine I present offers one API for processing events, PostEvent
. Notice I did not say "handling," because in this framework the state machine does not handle the event. How could it and still be reusable, since events are handled specifically to the environment in which they are invoked? The state machine knows nothing about its environment. So as far as it is concerned, the event is only a key that is used to help the state machine transition from one state to the next. The actual handling of the event, which may require system interaction prior to and/or after the event, has been passed to the state machine.
Figure 1 shows how you might integrate FSMs into their solution. I have purposely put an event handler as the interface to the system and not the state machine. Again, the FSM is not responsible for system-level interactions, so it knows nothing about handling of events which is why the framework is portable. In this scenario, it is the responsibility of end developers to do the pre- and postprocessing of the events when calling the state machine as well as provide all synchronization.
Figure 1: Integrating FSMs into applications.
Input/output data to/from events may be encapsulated within event wrappers. For example:
class MyEvent { int hEvent; CRITICAL_SECTION hLock; ... // Other specific information to Event Wrappers public: MyEvent( const int ev ) : hEvent(ev) {...} ... // Other initialization and member functions public: char* inbuffer; mutable char* outbuffer; ... // other member functions and constructors not shown };
Since the event is passed as a const
reference, any data to be manipulated by event handlers should be a mutable type. In this example, only the output buffer has this attribute.