Finite State Machine and Multithreading using .NET

• Download demo project - 170 Kb
• Download source - 74 Kb

Motivation

In automation and other multi-threading programming disciplines, the Finite State Machine (FSM) is an important model for designing dynamic behavior. The FSM is an object, which is always in one state of a defined set of states. It is able to receive events from a set of events, depending on the actual state. Upon receiving a given event, the FSM executes a specific transition. I created a framework of classes which simplifies the implementation of FSMs in .NET applications.

Background

A common approach to implement an FSM is a cross-table with the states on one axis and the events on the other axis. In the crossfields, you define the actions (if there are any). Unfortunately, this approach is not object-oriented. Another approach comes from “the Gang of Four” (Gamma, etc.) with their design pattern “States”. This is an object-oriented approach with a class for each event and each state. Even if this is a very flexible solution, it is somewhat “talkative”: you need a lot of classes and relations between these classes for a single FSM.

The approach described here is also object oriented, but requires less code than the "States"-pattern. You write handler methods for your Fsm class. But you need not bind them to events and states. This is done automatically in the startup of your program. In the startup phase, the Fsm gathers all necessary information from your source by the reflection capabilities of .NET. You just have to follow some naming and signature rules, that's it! Or, if you want to have more control over the binding, you can tag classes, members and methods with some attributes. The price you have to pay is some “magic” behavior behind the code and some loss of transparency.

Features

• Supports multithreading
• Supports multiple FSMs on one thread
• Supports timer events
• Allows definition of transition handlers and / or event handlers
• Supports state entry and exit handlers
• Allows definition default transition and event handlers
• Minimal effort to write an FSM, you write simply less code
• Flexible through optional usage of attributes
• Allows one-to-one translation from UML state diagrams

Implementing an FSM, Step by Step

1. Derive a class from the RTLib base class Fsm. Add a state enumeration type and a state member state. Override the GetCurrentState method. Initialize state with the initial state:

   public class MyFsm : RTLib.Fsm
   {
       public enum MyState 
       {
           MyState1, 
           MyState2, 
           MyState3
       };
   
       public MyFsm ()
       {
           state = MyState.MyState1;
       }
   
       private MyState state;
   
       override protected int GetCurrentState()
       {
           return (int)state;
       }
   }

   Note: The only reason for GetCurrentState() is that the Fsm class gets to know the current state. I did not find a way to create it automatically by reflection.

2. Define your event classes. Every event type is a class derived from the base class FsmEvent. There exists special event base classes for timer events and synchronizable events. Even it is possible to define them public, they are usually private to your Fsm as nested classes. Examples:

   private class MyEvent : RTLib.FsmEvent
   {
       public MyEvent()
       {
       }
   }
   
   private class MyEventWithParam : RTLib.FsmEvent
   {
       public MyEventWithParam(Param1Type param1)
       {
           this.param1 = param1
       }
   
       public Param1Type Param1
       {
           get { return param1;}
       }
   
       private Param1Type param1;
   }
   
   private class MyTimerEvent : FsmTimerEvent
   {
       public MyEventA()
           : base( new TimeSpan(0,0,6) ) // 6 sec
       {
       }
   }
   
   private class MyAbsoluteTimerEvent : FsmTimerEvent
   {
       public MyEventA(): base( new DateTime(DateTime.Now.Year, 
               DateTime.Now.Month, DateTime.Now.Day,
               12, 0, 0) ) // Today at noon (12:00:00)
       {
       }
   }

3. Define your transition-, event- and state handlers.

   Transition Handler	A method, which is called upon receiving a specific event in a certain state. Either you can use the naming convention State_Xxxxx(MyEvent) or you can define a method attribute [FsmTransitionHandler("State")]. If you define a transition handler with an event parameter of the base event class FsmEvent, it is a default transition handler for this state. This can be used to implement default handling for unexpected events.
   Event Handler	A method, which is called upon receiving a specific event in an FSM without states or with no transition handler for this event and the current state. Either you can use the naming convention Xxxxx(MyEvent) or you can define a method attribute [FsmEventHandler].
   State Handler	A method, which is called upon entering or on exit of a certain state. Either you can use the naming convention State_EntryState(), respective State_ExitState() or you can define a method attribute [FsmStateHandler("State", EStateHandlerType.Entry )], respective [FsmStateHandler("State", EStateHandlerType.Exit )].

   Important note: Attributes can be used only if your FSM class has the following attribute: [FsmCoding(ECodingType.WithAttributes)]. If you want to suppress resolution of the naming convention in an FSM without attribute usage, you can use the method attribute [FsmNoHandler] for any kind of handler methods.

   Examples:

   // A transition handler
   private void MyState1_OnMyEventWithParam( MyEventWithParam ev )
   {
       Trace.Write(DateTime.Now+" "+GetType().Name+": ");
       Trace.Write("MyState1_OnMyEventWithParam, Param = ");
       Trace.WriteLine(ev.Param1);
       state = MyState.MyState2;
   }
   
   // A transition handler with attribute
   [FsmTransitionHandler("MyState1")]
   private void TransitionHandlerWithAttribute( MyEvent ev )
   {
       Trace.Write(DateTime.Now+" "+GetType().Name+": ");
       Trace.Write("TransitionhandlerWithAttribute");
       state = MyState.MyState2;
   }
   
   // A state handler
   private void MyState1_EntryState( FsmEvent ev,  State oldState)
   {
       Trace.Write(DateTime.Now+" "+GetType().Name+": ");
       Trace.WriteLine("MyState1_EntryState, oldState = "+oldState.ToString() );
   }
   
   // An event handler
   private void OnMyEventWithParam( MyEvent ev )
   {
       Trace.Write(DateTime.Now+" "+GetType().Name+": ");
       Trace.WriteLine("OnMyEvent");
   }

4. Create an FsmProcessor object and push the FSM to it. If you want to synchronize to completion of the FSM, add also a Wait() call:

   FsmProcessor processor = new FsmProcessor("MyProc");
   MyFsm myFsm = new MyFsm();
   processor.PushFsm(myFsm);
   myFsm.Wait();

   Note: With Wait(), it is also possible to synchronize to the processing of a posted event if it is derived from SyncEvent. Fsm and EventBase have a constructor with a synchronized parameter.

5. There are several ways to terminate the FSM:

   FSM Internally	In any handler, call the base method TerminateFsm()
   FSM Externally and FSM Internally	Call Terminate() on Fsm or TerminateFsm(Fsm) on FsmProcessor
   FSM Externally	Call TerminateAllFsm(delay) on FsmProcessor

Classes in RTLib

FSM Entry and Exit Code

When an FSM is posted, the thread associated with the FSM processor calls first the override method OnFsmEntry(). When an FSM terminates the thread associated with the FSM processor calls the override method OnFsmExit() just before the FSM object is deleted. By overriding these methods, the user has a chance to execute some initialization and clean-up code in the context of the FSM processor thread the FSM is executing on.

Event Processing

For performance reasons, all time consuming reflection code is done at start-up time. At runtime, just a few look-ups are necessary to find and call the right handler method. An FSM can have a state variable or not. This has influence to the event handling. With states, the FSM handles the events in the following order:

With states:

• Try to dispatch the event to a transition handler.
• If not existing, try to dispatch the event to a default transition handler.
• If not existing, try to dispatch the event to a event handler.
• If not existing, call the default event handler.
• If not overridden, output an error trace.

Without states:

• If not existing, try to dispatch the event to a event handler.
• If not existing, call the default event handler.
• If not overridden, output an error trace.

Attributes and Naming Convention

Sample 1: RTLibConsoleTest

This program is a console application and does nothing useful. There are two FSMs:

Sample 2: Dining Philosophers

Five philosophers sit around a circular table. Each philosopher spends his life alternatively thinking and eating. In the center of the table is a large plate of spaghetti. A philosopher needs two forks to eat a helping of spaghetti. Unfortunately, as philosophy is not as well paid as computing, the philosophers can only afford five forks. One fork is placed between each pair of philosophers and they agree that each will only use the fork to his immediate right and left. Philosophers are depicted in yellow when they are thinking, blue when hungry and green when eating.

Points of Interest

While programming FSM, I learned something about reflection and threading.

History

• December 1, 2003 - Initial version.
• December 23, 2003 - Added default transition handler and completed description.
• April 27, 2005 - Fixed some bugs and improved documentation.

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here