|
Dale presents a lightweight and portable approach for implementing finite state machines in C++.
April 01, 2004
URL:http://drdobbs.com/cpp/a-finite-state-machine-framework/184401784
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.
// 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
The Framework
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, T, extends the base state machine class. In this approach, T 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 T. Therefore, T can either be invoked via its own public implementation or via its parent class, the state machine.
Since state machines are applied in situations where control dictates the operation of a piece of software, it would seem best to hide T behind the state machine. In other words, you have a state machine of T instead of the other way around. Not only does it hide details about T, but provides communication to T only through the state machine, thus implying the control logic driven by events or messages.
I have taken two paths, via a compile-time option, of how T is implemented as a state machine. The first extends T privately (that is, private inheritance). This approach guarantees that an instance of StateMachine<> hides the implementation of T 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 T will always require a default constructor and force the developer to initialize T with default parameters or obtain them through some other means, which could be an issue for multiple state machine instances of T.
The second approach is to contain T as an aggregate association; that is, a private member of StateMachine<>. This allows an instance of T 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 T 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 T 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 T upon its destructor being invoked. One way to easily work around who owns T at its creation is solved:
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 (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.
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.
The condition of an FSM at any instance is known as the "state." The state in Listing Three contains information pertinent to how the state machine behaves when an event is received. One of the things that may or may not appear intuitive from the class diagram is how loosely coupled the states are from the state machine. The state machine is only concerned with the current state. At construction, a start state is passed in, implying that the states are created prior to the state machine (which makes sense if you think about it). Navigation from state to state occurs through the transaction table that is contained within each state.
template <class T, class EV, class CMP>
class Transition
{
friend State<T,EV,CMP>;
public:
State<T,EV,CMP>* operator()( const T& _T, const EV& ev ) throw() {
(*m_evAction)(_T,ev);
return m_stNext;
}
protected:
Transition( const State<T,EV,CMP>& stNext, Action<T,EV>* evAction ) :
m_stNext(const_cast<State<T,EV,CMP>*>(&stNext)), m_evAction(evAction) {
}
... // Other member information
};
template <class T, class EV, class CMP = std::less<EV> >
class State
{
// State Transition Table Type
typedef std::map<const EV,const Transition<T,EV,CMP>*,CMP>
TransitionTable;
public:
typedef State<T,EV,CMP> state_type;
typedef EventAction<T,EV>::HANDLE HANDLE;
public:
State( HANDLE hEnter = 0, HANDLE hExit = 0 ); {
if ( hEnter == 0 ) {
m_evEnter = new NoAction<T,EV>;
}
else { m_evEnter = new EventAction<T,EV>(hEnter); }
if ( hExit == 0 ) {
m_evExit = new NoAction<T,EV>;
}
else { m_evExit = new EventAction<T,EV>(hExit); }
}
~State() {
TransitionTable::iterator iter;
for ( iter = m_stTable.begin(); iter != m_stTable.end(); iter++ ) {
delete const_cast<Transition<T,EV,CMP>*>( iter->second );
}
delete m_evEnter; delete m_evExit;
}
... // other API functions not shown
private:
TransitionTable m_stTable;
Action<T,EV>* m_evEnter;
Action<T,EV>* m_evExit;
};
The state transaction table (STT) is a sorted associative container (STL map) where the event (EV) is the key and an instance of a transition is the data. As events are passed into the state machine, the transition is retrieved from the transition table, if the event is valid for this state. The STL map was an obvious choice because events associate with transitions to the next state and are portable in the C++ Standard Library.
I initially considered the hash version of STL's map (hash_map) because the order of the event-transition pairs was not important. The worst-case complexity of most operations in a hashed associative container is linear in the size of the container, but the average time complexity is constant [3]. This is ideal for a situation in which information is simply stored and retrieved without regard to ordering. The drawback, though, is that hash_maps are not Standard Library entities from an ANSI perspective and could create portability problems for our state-machine framework. Since the number of transitions from a given state is typically not large, the time difference appears to be minimal at best, considering that events are typically integral values.
Action Handling
Transition from state to state has little merit, other than behavior modeling, unless something is performed on object T. In this framework, you hide T, but how T is accessed is left to the action handlers. While the state machine manages the behavior of T, the action objects manipulate the data and attributes of that object during transition. It is only through the action objects that the state machine can alter the data within T. In other words, the state machine resembles a container class that manages behavior.
Actions are typically invoked when an event occurs forcing a state transition. You may recall Mealy and Moore machines from your college textbooks. The handling of the output or action, in this case, is based on what model of state machine we use. In the framework presented, actions are associated with both transitions and states, so does this make us a Mealy-Moore Machine? (Okay, just a little Automata Theory humor.)
For each transition there is an action handler. By default, if no action is to be performed on it, and in some cases this can very well happen, then the default action handler is imposed (more on this in a bit). There are also action handlers for states: on Entry and on Exit. As with transitions these are optional as well, but provide this added flexibility (in which you will also find doing UML modeling) for the developer.
Now comes an interesting situation that I am sure will draw fire from C++ purists. As mentioned, a default action handler (which does nothing) is used when no action by T is required for a given transition or state entry/exit. I am not a big fan of using conditionals, especially in real time when an alternate, faster solution presents itself — especially one that seems more object oriented. In the case of a default handler, I don't want to query the State or Transition if it has a valid handler, as that is left to those objects. However, action handlers take a this pointer of type T and store a member function pointer into T, T::*fp.
Because of this, I could not find a clean way of forcing T to have a default null handler, and had to create a scheme in which the function operator (), was overridden. The function operator requires a pointer to T to invoke the action, but in situations where no action was required and to avoid conditional event processing, I ended up making operator () virtual and created an abstract base template class for Action<>, as in Listing Four. So let the tomato throwing begin! Of course, it's not like I am the first to do both dynamic and static binding of an object in a language that supports it.
Listing Four: Base action class.
// Base action class
template <class T, class EV>
struct Action
{
virtual void operator()( const T&, const EV& ) throw() = 0;
};
// No Action default
template <class T, class EV>
struct NoAction : public Action<T,EV>
{
void operator()( const T&, const EV& ) throw() {};
};
// Action Handler for "T"
template <class T, class EV>
struct EventAction : public Action<T,EV>
{
typedef void (T::*HANDLE)( const EV& ev );
explicit EventAction( HANDLE hAction ) :
m_hAction(hAction) {}
void operator()( const T& _T, const EV& ev ) throw() {
(_T.*m_hAction)(ev);
}
private:
HANDLE m_hAction;
};
A first approach was not letting the T parameter propagate any further than the StateMachine<> class to avoid code bloating. This initially worked, but required a pointer to T in the action objects and the bloating occurred in the many instances of action objects of the many instances of T (admittedly, this can be confusing). As this framework matures, I am sure there will be a better implementation that saves both execution time and space.
Putting It All Together
So when do you use an FSM during software development? The heuristic I tend to follow is this straightforward: If you are developing a subsystem or object that runs in its own context or thread that is control oriented in its implementation, then a state machine is a candidate for managing it.
Figure 2 is a state transition diagram (STD) of a phoneline. This is not a fully functional phoneline, but suffices for demonstration purposes. The source code for this implementation, available at ftp://ftp.drdobbs.com/sourcecode/cuj/2004/cujapr2004.zip, uses both versions of the framework.
Figure 2: State transition diagram of a phoneline.
In the included software I have three important member functions: start, halt, and reset. Even though the state machine does not provide synchronization in form of semaphores or mutexes, it does require itself to be running prior to accepting input. In this, the state machine itself has its own state transition diagram consisting of just two states: running and stopped. Only in the running state can events be processed. Resetting the state machine allows a restart mechanism, which is why during object creation the initial start state is stored.
Synchronization
The most obvious weakness to the framework is synchronization of entry into the state machine. The whole intent for this framework was to work in the context of its own thread, and (as Microsoft did originally with COM) leave the handling of synchronizing threads to you. State machines are invoked on a first-come/first-served basis, so entry into it should be handled in a critical section. One way of doing this is to protect each call in the state machine, by inserting an entry and exit in each method that is public to users.
A better solution is to have a single entry point via dispatchers — the obvious choice would be the event handler (Figure 2). Recall I said that events are not handled in the state machine; they are only routed and used to invoke a response. The biggest reason for separating the event handling from the event processing is that event handlers typically use system synchronization and FIFOs or queues.
Conclusion
This approach is by no means a silver bullet to writing state machines. One drawback in the approach with either version of the state machine is the chicken and egg problem. Since the states are not tightly coupled to the state machine, except via the current state, initialization becomes a problem. You will note in the example software that the states, actions, and state machines are created dynamically, and in the case of using aggregation, object T. This could be perceived as a flaw in the framework, since it should support both static and dynamic implementations. In fact it does, but not to the fullest extent.
I can see room for improvement, but I feel I am on the right path. No software is always the most correct solution. As software engineers and architects, we often find ourselves refining, tuning, and in some cases, rewriting our designs over time. It's like buying a computer at times. Either you want to wait until the prices are just right or you are waiting for that new technology. This can be a perpetual nightmare until you finally tell yourself, just buy it and realize it will be obsolete the minute you unpack it. I guess the same can be said about software design.
References
[1] Martin, Robert C. "UML Tutorial: Finite State Machines," C++ Report (June 1998).
[2] Stroustrup, Bjarne. The C++ Programming Language, Special Edition, Addison-Wesley 1997.
[3] Musser, David R. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, Second Edition, Addison-Wesley 2001.
P. Dale Mason has focused on embedded real-time and desktop application software development for over 15 years. He holds a Masters in Computer Science Engineering and Mathematics from the University of Louisville and is presently working with Visual Studio.NET and C++. Dale can be contacted at [email protected].
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.