Contact Desaware and order today! 

Sign up for Desaware's Newsletter for the latest news and tech tips.

Introduction to State Machines

Copyright © 2002 by Desaware Inc. -- All rights reserved.

A State Machine, in the context of software, is a way of organizing the operations that take place in an application. The idea is that your program exists in a finite number of possible states, and that something happens to move your program from one state to the next.

For example: You might have a web application that allows you to log in and view your account information. This could be divided into the following states:

• Not yet logged in.
  • Action: Display the login page
• Logged in and viewing the account balance
  • Display the account balance
  • Display logout button, and view transaction button.
• Logged in and viewing recent transactions
  • Display recent transactions
  • Display logout button, and view account balance button.
• Logged out
  • Display "Goodbye page"

At any given time, the application exists in one of these four states. In each state there exist a limited number of possible events (typically called "messages" when discussing state machines). For example, during the "Logged in" state, the page displays text boxes for the user name and password and a "login" button. If the user enters a correct login, the application switches to the "Logged in and viewing the account balance" state. If the login fails, the user sees an error message and the application remains in the "Not logged in state".

State machines are frequently described using State Diagrams (or State Transition Diagrams - STD) that look something like this (click on the image to zoom):

The initial state is where the state machine starts (the circle marked Initial state, and the one marked End State are not states themselves - rather pointers to the actual initial and end states). Each state is represented by a circle. Each arrow represents a message that can be received by the state machine (often triggered by an event) that can cause the machine to change states. Thus in this example, a successful log-in moves the application into the account viewing state.

Why are State Machines Important?

To understand why state machines are so important, remember that much of what we do as software developers consists of managing complexity. We implement very complex applications and algorithms by breaking them up into smaller manageable tasks.

One of the key purposes of object oriented programs (OOP) is to help manage complexity. By using information hiding within objects (implementing private functions and variables) and defining a limited number of public methods and properties, you are able to deal with an object as a single indivisible entity. Once the object is created and implemented, you no longer have to worry about how it works or the possibility of accidentally modifying one of its internal data variables. Thus Object Oriented Programming inevitably results in simpler programs - programs that are easier to understand and support.

State machines serve the same purpose, but on an architectural level. As part of the development of a state machine you define all of the valid events that may occur during that state. For each event you define an action and a state transition (which includes the possibility of remaining in the same state). You might also define an action for all invalid states.

What does this accomplish?

• First, it makes the program far easier to modify. Adding new features might consist of adding new states. By clearly defining the events that can bring you to that state and events for that state you at the same time define the code that needs to be modified. Code that is not involved with that state can be safely ignored.
• It becomes dramatically easier to test programs implemented as state machines. Why? Because it is possible to break down the testing process into testing of individual states. If you test each state for all of its possible events (often a reasonable task), you can go a long way to eliminating bugs in your program. True, there may remain subtle bugs due to the interaction of states (especially if they share any data), and your state machine may itself have design flaws (say, forgetting a particular event), but the results of this approach will always result in a higher quality program than otherwise.
• Using state machines also demands that you spend some time designing them before you start coding. And let's face it, design time is something that developers often skimp on, especially in the face of deadline pressures.

Here's another way of looking at it.

Figure 1 shows how object oriented programming reduces complexity by reducing the number of functions and variables you need to deal with at a given level of your program. In this illustration you can see on the left side a large number of variables and functions that might appear in a non OOP program. When using OOP the variables and functions are hidden inside of objects. These objects expose a limited number of methods that provide a high level encapsulation of the enclosed variables and functions. As a result, once you've implemented these objects, instead of having to worry about a large number of variables and functions (and their interactions), you need only concern yourself with a small number of objects and their methods. Fewer items to work with results in reduced complexity, increased reliability, and overall lower software development costs. 

Figure 1 - Object oriented programming.

Now consider figure 2. On the left side, instead of lists of functions and variables you can see a list of events. These are possible inputs to your program. These can be in the form of user actions, data received from a network, data read from a disk or other source and even results of an operation or exceptions that occur while a program is running - basically anything that can represent input to your program.

Figure 2 - State machine programming.

If your code has to consider all possible inputs at all times, the complexity of the any non-trivial program would be impossible to deal with. Fortunately, this is rarely the case - programs naturally deal with certain events at certain times. A function that reads data from disk rarely worries about user input. Yet at the same time, that function that reads data from disk may receive unanticipated input - a user abort or disk error, and the failure to deal with unanticipated input is a key source of bugs and instability in software.

A state machine serves to divide an application's life into a series of states, each of which has a set of acceptable input. Once in a given state, you need only concern yourself with valid inputs. Invalid inputs are by definition errors that can be trapped and handled. Just as OOP simplifies a program by reducing the number of variables and functions you need to deal with, state machines simplify a program by reducing the number of inputs you need to deal with. Collapsing a given set of inputs into a state machine that has a set start point and end point, and can be dealt with as a single entity, just as an object can deal with a group of variables and functions as a single entity.

State machines work at multiple levels. Consider the following state machine (click on the image to zoom):

This represents a state machine that processes incoming characters to look for words in the format of a proper noun (i.e., the first character is upper case, all other characters are lower case.

The first state handles three possible messages. A white space character (such as space or tab) indicates the word has not yet started, so the machine remains in the same state. An upper case character means that the word has started, so the machine transitions into the second state. Any other character represents a failure, so the machine moves into the Failed state. Once in the second state, all subsequent lower case letters indicate continuation of the word, so the machine remains in the same state. A white space or legal punctuation indicates the end of the word, which moves the machine into the "success" state. any other character again moves the machine into the failed state.

Do people use state machines to process text in this manner? Absolutely. In fact, the .NET framework includes a namespace called System.Text.RegularExpressions whose sole purpose is the processing of text using state machines that are defined using a special Regular Expression Language! For an in-depth tutorial and reference of this language (that is considerably easier to follow than Microsoft's documentation) refer to the E-book "Regular Expressions in .NET".

State Machine Design Patterns - or How State Machines can help you avoid creating bad .NET code.

"Design patterns" is one of those terms that has received a great deal of attention lately and can be intimidating to those who don't realize that the idea behind them is very simple. A design pattern is just a common way of doing something.

For example: let's say you want to swap two elements in an array. The following pseudocode demonstrates a design pattern that performs this task:

Temp = A(n)

A(n) = A(m)

A(m) = Temp

Unless a language contains a function designed to swap two variable, you'll see something that looks more or less like this code anywhere that two array elements need to be swapped. This code can thus be thought of as a design pattern for swapping elements in an array.

Design patterns enable us to look at common solutions (both good and bad) for various problems.

Now, state machines are applicable in many different scenarios. There are many problems that can be solved both with and without clearly defined state machines, where the state machine based design pattern will improve the code (I say clearly defined, because in many cases your code is acting as a state machine even if you haven't thought about it). However there are a number of areas in .NET where state machine based design patterns are vastly better than any other approach. They are:

• Performing long synchronous operations
• Any time you handle asynchronous operations
• Any time you use multithreading
• When implementing a protocol based application

In this section, you'll see common but flawed design patterns for the first two of these scenarios, and how you can use a state machine based design pattern to eliminate those flaws. The third scenario will become clear as you read the first two. The fourth scenario won't be demonstrated because it's obvious - you can't implement a non-trivial protocol without a state machine - so any implementation that doesn't use a clearly defined (and properly designed) state machine is bound to be less reliable than one designed using using state machine design techniques.

There are many applications for state machines that fall outside of these design patterns, some of which can be found in articles on our web site, but these four areas tend to benefit most from formal implementation in state machines (largely because implementations that don't include formal implementations of state machines tend to suffer the most problems).

Long Synchronous operations

One common problem in single threaded applications relates to performing a sequence of time consuming synchronous operations. Let's say you have three long operations to perform in sequence. These can be CPU intensive operations, or operations such as service or network requests or database queries that are synchronous (i.e., you must wait until the operation concludes in order to continue). The obvious design pattern is:

LongOperation1( )

LongOperation2( )

LongOperation3( )

Or the closely related pattern

Do

LongOperation

Loop While . 

The problem with this approach in a single threaded application is that while you are waiting for this sequence to conclude, the rest of your application is frozen. One design pattern I've seen in all too many Visual Basic programs tries to alleviate the problem as follows:

LongOperation1( )

Application.DoEvents( )

LongOperation2( )

Application.DoEvents( )

LongOperation3( )

Or

Do

LongOperation

Application.DoEvents( )

Loop While .

The DoEvents allows temporary event processing to occur (it's the equivalent of a PeekMessage call for those of you from the C++ world). This is a terrible design pattern. First, the degree to which it actually helps depends on the length of the long operations. This often results in "jumpy" form behavior. Worse, the DoEvents command adds the possibility of reentrancy - during the event the entire gamut of input messages becomes possible and must be dealt with - otherwise you might find yourself reentering this sequence - a potentially fatal problem. It is the exact opposite of simplification.

A better design pattern is to turn this into a state machine such as the one shown in the following pseudocode.

Enum StateVariable

    0 = DoLongOperation1

    1 = DoLongOperation2

    2 = DoLongOperation3

End Enum

On Timer

    Select Based on StateVariable

        Case 0: LongOperation1 ( )

                StateVariable = 1

        Case 1: LongOperation2 ( )

                StateVariable = 2

                Case 2: LongOperation3( )

    End Select

End

For a loop, you would have a single state, and during the state would determine (based on a counter) if the state machine should terminate or continue.

Now, this pattern is better. You'll still get jumpy performance because you are using a single thread, but you no longer have the problem of reentrancy. Yes, input may come in between states, but you can easily detect the current status of your state machine and deal with the input accordingly.

With .NET, it becomes easy to create multithreaded applications, in which case the following pattern becomes possible.

In main thread:

Create LongOperationThread( LongOperationThread_Start ) 

  In the launched thread

LongOperationThread_Start

    LongOperation1( )

   LongOperation2( )

   LongOperation3( )

End

You can detect whether the operations are complete by checking the thread object or waiting for the thread to terminate using the Join method.

This is a very reasonable pattern for this simple case. Problems occur in three cases:

• What if this is a business object that has to support multiple clients. Creating a new thread for each client or on each call is very expensive in terms of system resources and can seriously impair performance.
• What if its not a simple sequence of long operations, but rather a series of long operations, where the choice of the operation to perform depends on the results of the previous operation?
• If the long operations share ANY data with the main thread, you run into the possibility of memory corruption due to a failure to synchronize access to the data.

In the first case, the answer is to use a thread pool to perform the desired operations. Each client uses a thread from the pool if one is available, waiting if necessary for a thread to become available.

In the second case, the obvious answer is to implement a state machine instead of a simple sequence. After each operation returns you can choose the next state based on the result of the previous operation.

The third case is by far the most serious. Chapter 7 of Dan Appleman's book "Moving to VB.NET: Strategies, Concepts and Code" includes an in-depth explanation of the sources of these synchronization problems and the risks involved. How big are the risks? The book demonstrates an easy to overlook problem in a financial application which causes an error on the average of  once every 50 million operations. The error causes an arbitrary amount of money to appear or vanish. Obviously, it is not feasible to test for errors that occur so rarely, yet the cost of these errors can be virtually unlimited. Careful design is essential when creating multithreaded applications.

Multithreading synchronization problems can occur any time data is shared among threads. It is especially serious in .NET because the .NET framework itself is not by and large thread safe. Thus it is essential that programmers use great care when deciding to launch additional threads in their applications - especially if they do not have experience designing multithreaded applications.

Desaware's StateCoder is ideal for implementing this design pattern. It addresses all three issues:

1. State machines implemented using StateCoder can be run in their own thread, or in a thread pool - as you prefer.
2. It is trivial to change the sequence of long operations into states. The transition from one state to another is a single method call, and the choice of state can be based on the results of the previous operation.
3. With Desaware's StateCoder, each state is an object that is not accessible from the main operation other than through messages. The architecture makes it easy to isolate data from the main thread (in fact, you have to go out of your way to share data). More important, each state machine runs in a single thread, and incoming messages are synchronized to that thread. You can read more about this in the StateCoder documentation and other articles on our web site, but in a nutshell - it provides much of the thread safety with which Visual Basic programmers are familiar, but unlike Visual Basic 6, does not prevent you from bypassing the protection and performing your own synchronization.

Meanwhile, the StateCoder design pattern for this might be as follows:

In the main thread:

Create LongOperationStateMachine object.

LongOperationStateMachine.Start( )

You can detect whether the operations are complete by polling the state machine object, waiting for it (using a wait operation), or watching for an event. The state machine object itself contains objects and code that implement the state machine, but the details of that implementation are hidden at this higher level of abstraction. The result is a dramatic simplification in your program (especially in the case of more complex state machines).

Asynchronous Operations

Regardless of whether a long operation takes place in a background thread or a foreground thread, sequentially or as part of a state machine, that long operation will tie up a thread for some period of time. Many such operations provide the ability to perform the operation asynchronously. The design pattern for an asynchronous operation in .NET is shown in the following pseudocode:

The main thread starts the asynchronous operation:

AsyncResultVariable = BeginOperation(DelegateToCallOnCompletion)

This function return immediately. When the operation is complete, the completion function is called:

CallOnCompletion(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

End

A state machine to perform the three long operations can be implemented using a series of events as follows:

AsyncResultVariable = 

    BeginOperation(DelegateToCompletionLongOperation1) 

CallOnCompletionLongOperation1(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

    AsyncResultVariable =

       BeginLongOperation2(DelegateToCompletionLongOperation2)

End

CallOnCompletionLongOperation2(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

    AsyncResultVariable = 

       BeginLongOperation3(DelegateToCompletionLongOperation2)

End 

CallOnCompletionLongOperation3(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

End 

You can, in fact, build a complex state machine simply by choosing which asynchronous operation to start in each event.

If you were to look at a StateCoder implementation of a similar state machine, you might find a similar pattern inside the state machine itself. StateCoder provides full support for asynchronous operations, and in fact encourages their use. The difference being that while the design pattern might be used inside the state machine, the high level design pattern for using the state machine would again look like this:

Create LongOperationStateMachine object.

LongOperationStateMachine.Start( )

Isolation of the state machine implementation from the rest of your code is a key feature of StateCoder.

What you don't want to do is implement this design pattern:

AsyncResultVariable = BeginOperation( _
DelegateToCompletionLongOperation1)
Do
  DoEvents
Loop until CompletionFlag1

      

AsyncResultVariable = BeginOperation( _
DelegateToCompletionLongOperation2)
Do
  DoEvents
Loop until CompletionFlag2

      

AsyncResultVariable = BeginOperation( _
DelegateToCompletionLongOperation3)
Do
  DoEvents
Loop until CompletionFlag3
      

Continue running...

CallOnCompletionLongOperation1(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

    CompletionFlag1 = True

End 

CallOnCompletionLongOperation2(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

    CompletionFlag2 = True

End 

CallOnCompletionLongOperation3(AsyncResultVariable)

    EndOperation(AsyncResultVariable)

    CompletionFlag3 = True

End

The programmer implementing this code is trying to run asynchronous operations synchronously. At first glance, this code looks truly terrible. But in fact, it is truly terrible. It does avoid the problem of freezing the main thread, but opens the door to the reentrancy problems described earlier. Any time you see this design pattern, your code is begging for a redesign into a state machine.

Conclusion

This is a very basic introduction to the idea of state machines, and we've tried to focus on the philosophy behind using state machines as much as on their specific implementation. Other articles on our site focus more on specific solutions and implementations, and will help you to better understand how to incorporate state machines into your own applications.

For notification when new articles are available, sign up for Desaware's Newsletter.