I’m working toward some really nice tools for automated build and deployment of software, which I’ve written about previously both here and on point7. I’ve only just started this in earnest, so I picked what feels like a manageable subgoal; build a tool that shows you red lights and green lights re: builds and unit tests, in the dev environment. See this post about DevBuilder and LocalBuild. At the end of that post I picked on the sub task of change detection (specifically for detecting changes to files) as my first generally useful piece.
But in the immortal words of Dav Pilkey, before I can tell you that story, I have to tell you this story. This story is the General StateMachine.
Motivation
A State Machine is a useful formalism for dealing with systems with a non-trivial dynamic behavioural component. That is, anything where you are coding up an “engine” or a “worker thread” or a “service” to be in charge of some piece of a process over time, in an active way.
An example is a windows service. Any windows service is coded in terms of a state machine; you have a state (Stopped, Started, Paused, Starting, Stopping, others?) and a statically defined set of rules about how you get from one state to another, eg:
Windows Service State Machine Diagram
This diagram is simplified, leaving out particularly some error conditions.
The blue rectangles are States. Under each state there is text describing what to do on entry to that state. The Arrows are transitions from one state to another, which happen when a certain condition occurs, eg: a command is received, or something else happens inside the program or in the environment (in this case, something the program was trying to do finishes, succeeding or failing).
Let’s take the example of a windows service to monitor a file for changes. We start in the “Stopped” state. The system boots up, and instructs this service to start (sends the START command to it). It enters the Starting state, which requires it to perform initialization. It loads a config, constructs some objects to perform monitoring based on those objects, and succeeds. Success means it transitions to the Started state, and commences runtime processing, which in this case is waiting for notification of file changes, and informing the
user (sending an email, something like that?) when they occur. Later on, the user pauses the file monitoring service (sends the PAUSE command). It transitions to the Paused state, where it tells the monitoring components to stop monitoring temporarily. The user subsequently sends the CONTINUE command, and the service transitions back to Started state, recommencing change monitoring. Later still, the system is to shutdown, and sends the STOP command to the service. It transitions to STOPPING, and commences cleanup. When it finishes cleanup, whether or not that succeeds, it transitions to Stopped, where it does nothing. The system finishes shutting down.
Other examples might be a stateful engine for a communication protocol like BitTorrent or Jabber, a user session management process in a web server, or a video playback mechanism in a media player. Stateful mechanisms with dynamic behaviour over time are everywhere.
It’s common to implement these mechanisms by encoding the state using collections of boolean variables, or ad hoc created state variables, in a custom way for each such job. We know the theory of state machines, and keep it in mind as we implement these engines, but using a custom approach every time leads to cutting corners and bad practises.
I come up against this requirement all the time, in professional and personal projects. The latest instance of this is in change detection for DevBuilder. I need a process to stay awake, watching for changes in a folder hierarchy, which has state much as shown in the example above. In fact, it may need to do something slightly more complex, given that it is monitoring multiple folders, and may need to be able to manage that monitoring at run time on the fly.
So, I’ve decided to create and use a State Machine library (a c# assembly) which will introduce the state machine formalism directly into my code.
Where’s the code?
The wandev.StateMachine.core assembly is part of my Wandering Developer codebase. It lives here on SourceForge:
http://sourceforge.net/projects/wandevdeptools/
(this project no longer just does what it was initially created to do, it’s becoming my general open source C# library’s repository)
You can directly browse the assembly’s source at the url below. It’s quite a nice way to look at the code; nicely formatted and syntax coloured.
http://wandevdeptools.svn.sourceforge.net/viewvc/wandevdeptools/wandev.StateMachine/
This article refers to Revision 74 in the repository.
Overall design
To make a usable general statemachine, we firstly need to be able to define the machine’s state diagram (eg: the diagram above). This diagram is a directed graph, with States as the nodes and Conditions (what triggers transition to a new state) as the edges. We also need a way to represent States and Conditions. We need a way to run custom code when we enter a new State. And we need a way to signal that a Condition has occured to the statemachine.
States and Conditions
For our first foray into code, let’s look at representing States and Conditions.
Really they are just labels. We could easily just represent them as Strings, and be done with it. eg: States could be “Stopped”, “Starting”, “Started”, “Stopping”, “Paused” and Conditions could be “Start”, “Stop”, “Pause”, “Continue”, “Success”, “Failure”.
However, this is pretty weakly typed, and begs for us to get States and Conditions mixed up, causing mayhem. Instead, I’ve gone for classes State and Condition, which are really just simple wrappers around a string (“StringName”). Because they share a most of their implementation, I’ve made them inherit from an abstract base class, called StringNameBase. They’re not really semantically related, so this is a poor reason to use inheritance, but I’ll just go easy on myself and mark this as a something to split up later if it causes trouble.
What StringNameBase does primarily is to provide a read-only property StringName which is the name of the condition or state, implement a value equals, so that equality tests for case insensitive string equality, and implements (or forces its descendants to implement) Clone(), so we can make copies of these objects easily.
The Clone() is particularly important. I want to be able to use these objects like value types. We are in a heavily multithreaded environment, so if a caller wants to know what the current state is, for instance, or some internal code wants to work with states or conditions, concurrency becomes a lot easier if we work with copies of shared objects (lock-copy-unlock) rather than trying to share the same instances between threads, and between internal StateMachine code and external code.
State Machine definition and the constructor
The state machine definition is a directed graph as above. I’ve chosen to implement it as the following type:
Dictionary<Pair<State, Condition>, State>
What you say?!?!
This is a Dictionary, (Mapping in java? Think hash table), where the key is a (State, Condition) pair, and the value is a State. The key represents a condition occuring when you are in a particular State, and the value tells you which state to go to in that case.
The way this will be used will be when a condition occurs. We’ll get the current state, pair it with the condition, use it as a key to look up the dictionary, and transition to the state given by the value found.
(What if we find no value? We do nothing. eg: If the service is “Started” and we get the “Start” command, we throw that command away.)
I’ve also chosen not to provide the state machine with an explicit list of States and Conditions. We’ll just use what’s in the graph (ie: the dictionary) as a definitive list. So this should be enough for the constructor.
Except… we have a little bit of extra information required. Firstly, what should the first state be for the machine? That’s the Start state (not to be confused with the “Start” state; in our example above the start state would be “Stopped”!). Also, if the calling code needs to finish with the state machine altogether, dispose it, then the machine would like to be in a state appropriate for that. We want to define a Stop state (again not to be confused with Stop).
So, our constructor looks like this:
public StateMachine(Dictionary<Pair<State, Condition>, State> aTransitions, State aStart, State aStop)
Running custom code on entry to a new state
This has been done as a simple event:
public event EventHandler<NewStateEventArgs> OnNewState;
where NewStateEventArgs includes the following property:
public State NewState;
The simplest way to provide your custom State code is to hook this event, and inside the handler test for the state using e.NewState .
First you need to hook the event. You should do this before the state machine starts operating, so there is some metastate to any statemachine. You construct the statemachine, then you hook the event, then you call the Start() method to get it moving (this puts the machine into the state specified by aStart in the constructor, and call OnNewState for that state).
eg:
_stateMachine = new wandev.StateMachine.core.StateMachine(ltransitions, lstart, lstop);
_stateMachine.OnNewState += new EventHandler<NewStateEventArgs>(_stateMachine_OnNewState);
_stateMachine.Start();
Then, you need to implement the handler. Here's an example appropriate for the service example:
void _stateMachine_OnNewState(object sender, NewStateEventArgs e)
{
if (e.NewState.Equals(Starting))
{
// this is an asynchronous call, expect event handlers elsewhere to deal with success or failure
DoInitialise();
}
... etc ...
}
Note: OnNewState is called synchronously by the State Machine. It has to be, because it can’t proceed with more conditions until the state entry code has completed. This means that, inside this handler, you mustn’t do anything time consuming, especially you mustn’t sit in a loop waiting for anything (if you find yourself doing this, you need more states in your machine!). If you need to do something potentially lengthy, put it in its own method and call that method asynchronously, relying on the EndInvoke() handler to raise a condition which will transition you to the next state.
Raising a Condition
So how does this machine know when conditions have occured? You raise them.
The state machine has the following method for this purpose:
public void RaiseCondition(Condition aCondition)
This method is threadsafe (as is the entire public interface of the state machine). So from anywhere, any handler, or even from within the OnNewState handler, you can raise a condition using RaiseCondition().
The state machine uses a queue to manage these conditions, and processes them asynchronously as soon as it can.
Special Conditions: StopCondition, ProceedCondition, TimerCondition
There are three special conditions defined for every statemachine. If you need to use them before the statemachine is constructed (ie: when creating the transition graph), there are staticly defined constant strings for each of their StringNames available (StateMachine.StopConditionStringName, StateMachine.ProceedConditionStringName, StateMachine.TimerConditionStringName). You can use these like so: (new Condition(StateMachine.StopConditionStringName)) can stand in for _stateMachine.StopCondition, and similarly for the others.
StopCondition
You mustn’t ignore this condition. This condition is raised when you call Dispose(). Every state except your Stop state should have a transition for this condition, which leads irrevocably if not directly to the Stop state. Currently Dispose raises this condition and then waits until the Stop state is reached before exitting, which is rather prone to hanging (if you never get there), I’ll work into this in future versions (with, eg, a timeout).
ProceedCondition
This is just a useful condition for states where there is only one edge out, or otherwise some default behaviour, for which “Proceed” is a good description. It just saves you defining another condition. You can never use this if you don’t want to.
TimerCondition
This should be called TimeoutCondition! I’ll change this in the future.
It is really common in StateMachines for one of the edges to be a timeout edge, so I’ve provided a useful timer for states. It’s implemented using System.Threading.Timer. You use it by defining a timeout edge in your graph for any applicable states, using this condition as the condition, then in the OnNewEvent handler call SetTimer() in your processing for that state, passing the length of the desired timeout in milliseconds. If the specified timeout elapses and you haven’t transitioned to another state, this condition will be raised and the timeout transition will be invoked. Otherwise, on transition to any state the timer is cleared.
Here’s an example:
// in the transition dictionary construction code
Condition lTimer = new Condition(StateMachine.TimerCondition);
...
_transitions.Add(new Pair<State,Condition>(Starting, Success), Started);
_transitions.Add(new Pair<State,Condition>(Starting, Failure), Stopped);
_transitions.Add(new Pair<State,Condition>(Starting, lTimer), Stopped);
...
// here's the OnNewState handler
void _stateMachine_OnNewState(object sender, NewStateEventArgs e)
{
if (e.NewState.Equals(Starting))
{
// this is an asynchronous call, expect event handlers elsewhere to raise condition Success or Failure
DoInitialise();
// and give it a ten second timeout
SetTimer(10000);
}
... etc ...
}
To Be Continued
I’m out of puff, I’ll continue this later. Subsequent posts will talk about the internals of implementation (or just look at the code, it’s right there!), and give a serious concrete example of use of the StateMachine.
