Skip to main content

A Finite State Machine Supporting Concurrent States

September 6, 2009

{cs.r.title}







A finite state machine (FSM) models a predefined number of application
states, which are changed (transitioned) according to actions that occur when
triggered by runtime events. The FSM serves as a control point for validating
state transitions and initiating callbacks.

A typical application will go through multiple states during a runtime
session, e.g., RUNNING → PAUSED → RESTARTED, or (in the case of a data
entry form) ENTER → VALIDATE → SAVE. The state transitions are
initiated by runtime events, such as when a user presses an PAUSE button or
hits the ENTER key after entering data in a field. The FSM determines what
actions occur when an event is received, and the resulting state. The
transition to a new state will invoke a change in the immediate or subsequent
behavior of an application.

Event Flow
Figure 1. Event flow

The Bouncing Bomb Application

The Bouncing Bomb Application uses an FSM to manage the enabling/disabling
of buttons in the right button panel. The effect is that allowable events are
constrained according to the current application state. Each button initiates
an action event when pressed; those events, when propagated to the FSM, result
in state transitions. The set of actions (application events) and states are
predefined (enumerated), and allowable state transitions are determined
according to entries in a Map collection. The map defines what states are
reachable from any other state, which indirectly determines the allowed button
actions.

BB App
Figure 2. The application

It makes sense to use the enum type in Java 1.6 to enumerate
the action events and states of the application. The StateMachine
class is implemented as a monostate class (all fields and methods are static),
and contains the action Event and State enums:

public enum Event {
   START,
   PAUSE,
   CONFIGURE,
   CONFIG_DONE,
   RESET,
   END,
}

public enum State {
   RUNNING,
   PAUSED,
   CONFIGURING,
   RESET,
   ENDED,
}

Each application event received by the StateMachine causes a
state transition. The initiating event and resulting end state can be
tabularized as follows:

style="page-break-inside: avoid">

Event

State

START

RUNNING

PAUSE

PAUSED

CONFIGURE

CONFIGURING

CONFIG_DONE

PAUSED

RESET

RESET

END

ENDED

The initial application state is PAUSED. If the Start button is pressed,
then a START event is sent to the StateMachine and the StateMachine changes the
current state to RUNNING. A schematic of the state transitions in the
application can be drawn up based on the states and events shown in the table
above.

Simple State Diagram height="289" />
Figure 3. Simple State Diagram

The state transitions can be implemented in Java using a simple switch
statement. An incoming event usually initiates some behavior change in the
application in addition to the state change. The logic for that may exist in
the switch statement, or may be executed when state change listeners are
notified as a result of the call to setCurrent().

switch (event) {
    case RESET:
        int answer =
            JOptionPane.showConfirmDialog(
                    StateMachineDemo.getApp(),
                    "Are you sure you wish to reset?",
                    "Please confirm",
                    JOptionPane.YES_NO_OPTION,
                    JOptionPane.QUESTION_MESSAGE);
   
        if (answer == JOptionPane.YES_OPTION) {
            setCurrent(State.RESET);
        }
        break;
   
    case PAUSE:
        setCurrent(State.PAUSED);
        break;
   
    case START:
        setCurrent(State.RUNNING);
        break;
   
    case CONFIGURE:
        if (configFrame == null) {
            configFrame = new ConfigurationFrame(
               StateMachineDemo.getApp());
        }
   
        configFrame.setVisible(true);
        setCurrent(State.CONFIGURING);
        break;
   
    case CONFIG_DONE:
        setCurrent(State.PAUSED);
        break;
   
    case END:
        setCurrent(State.ENDED);
        break;
   
    default:
        log.severe("Unhandled event: " + command);
    break;
}

There are one or more reachable states that can be transitioned to from any
current state. A map of allowed transitions can be used to validate state
change requests. The set of reachable states is held by an EnumSet
instance.

The setCurrent() method first determines if the desired state
is valid by calling isReachable(), which checks the
stateMap for reachable states from the current state. If it is,
then setAsFinal() is called to perform the state transition and
notify change listeners of it.

static {
    stateMap = new HashMap<State, EnumSet<State>>();

    stateMap.put(State.RUNNING,
        EnumSet.of(State.PAUSED, State.ENDED));

    stateMap.put(State.PAUSED,
        EnumSet.of(State.RUNNING, State.RESET,
            State.CONFIGURING));

    stateMap.put(State.ENDED, EnumSet.of(State.RESET));
    stateMap.put(State.CONFIGURING, EnumSet.of(State.PAUSED));
    stateMap.put(State.RESET,
       EnumSet.of(State.PAUSED, State.RESET));

    // set initial state
    currentState = State.PAUSED;
}

...

private static State setCurrent(State desiredState) {
    log.info("at state: " + currentState +
       "; requesting state: " + desiredState);

    if (!isReachable(desiredState)) {
            throw new IllegalArgumentException();
    }

    return setAsFinal(desiredState);
}

private static boolean isReachable(State desiredState) {
    return stateMap.get(currentState).contains(desiredState);
}

private static State setAsFinal(State desiredState) {
    currentState = desiredState;
    final ChangeEvent e = new ChangeEvent(currentState);

    for (final ChangeListener l : stateChangeListenerList) {
            l.stateChanged(e);
    }

    return currentState;
}

The state map acts as a defensive barrier that ensures requested state
transitions are in accordance with declared intentions. If not, then an
IllegalArgumentException is thrown, which means either the map is wrong or an
event is causing the wrong state to be requested. As mentioned before, the
initial application state is PAUSED, so the initial reachable states
(highlighted) are RUNNING, RESET, and CONFIGURING.

In addition to providing an easy to read list of valid state transitions,
the state map is useful in determining what buttons are active (what states
reachable) when the application is running. The right hand panel in the
Bouncing Bomb application registers itself as a listener to the StateMachine; when a state change occurs, changeButtonEnablement() is called. The method checks a state-action map to determine which event actions are allowed given the current state. Allowed actions determine which buttons are
enabled.

static {
    stateActionMap = new HashMap<State, EnumSet<Event>>();
               
    stateActionMap.put(State.PAUSED,
       EnumSet.of(Event.START, Event.RESET, Event.CONFIGURE));
    stateActionMap.put(State.RUNNING,
       EnumSet.of(Event.PAUSE));
    stateActionMap.put(State.RESET,
       EnumSet.of(Event.START, Event.RESET, Event.CONFIGURE));
    stateActionMap.put(State.ENDED,
       EnumSet.of(Event.RESET));
}

...

public void stateChanged(ChangeEvent e) {
    if (e.getSource() instanceof StateMachine.State) {
            changeButtonEnablement();
    }
}

protected void changeButtonEnablement() {
    pauseButton.setEnabled(isAllowedAction(Event.PAUSE));
    configButton.setEnabled(isAllowedAction(Event.CONFIGURE));
    startButton.setEnabled(isAllowedAction(Event.START));
    resetButton.setEnabled(isAllowedAction(Event.RESET));
}

private static boolean isAllowedAction(Event actionEvent) {
    EnumSet<Event> allowed =
        stateActionMap.get(StateMachine.getCurrent());
    return allowed != null && allowed.contains(actionEvent);
}

The Start, Configuration, and Reset buttons are enabled when in the initial
PAUSED state. Not all state changes are triggered by button actions: the END
state is reached when all bombs explode (based on the number of bounces each
makes). Once a bomb explodes, it is removed from the bomb list. When the bomb
list has ended, the application goes to the ENDED state.

public void moveBombs() {
    if (bombs.size() == 0) {
        StateMachine.actionPerformed(this, Event.END); 
           //which leads to the ENDED state
    }
    else …
}

The state map in the StateMachine class tells us that when the ENDED state
is current (as a result of an END event being received), the only reachable
state is RESET, at which point the user can only press the Reset button and
start over.

The configuration dialog is opened when the user presses the Configuration
button. It allows the setting of the number of bombs, the number of bounces
before a bomb explodes, and whether sound is on or off.

Configuration Dialog height="187" />
Figure 4. The configuration dialog

While configuring the application no buttons should be enabled in the
ButtonPanel; hence, there are no allowed actions shown in the
stateActionMap when the CONFIGURING state is active. A CONFIG_DONE
event is sent when the configuration dialog is closed, and at that point the
state machine transitions to the PAUSED state.

Concurrent States

Here's a question: When the application is still running, why not allow the
user to set a configuration for the next run? The new configuration would then
be ready for the next run when the current run ended. To enable that behavior,
two states would have to be allowed to be active at once: RUNNING and
CONFIGURING .

How might such concurrent states be handled? The first thing to change is
the type of the currentState instance in the StateMachine. One
approach is to use an EnumSet to hold both the primary and concurrent state
enum values, and change the stateMap key to an EnumSet<State> and its
values to an array of EnumSets.

private static volatile EnumSet<State> currentState;
private static Map<EnumSet<State>, 
   EnumSet<?>[]> stateMap;

The Event and State enums remain essentially the
same, the one exception being that the CONFIGURING state is made the last value
declared; the change is needed so that the primary and concurrent states can
easily located in the currentState EnumSet, as will be shown
later.

public enum State {
    // primary states...
    RUNNING,
    PAUSED,
    RESET,
    ENDED,

    // concurrent states...
    CONFIGURING,
}

The stateMap can now validate transitions from single-to-single,
single-to-concurrent, concurrent-to-concurrent, and concurrent-to-single
states:

stateMap = new HashMap<EnumSet<State>, EnumSet<?>[]>();

stateMap.put(EnumSet.of(State.RUNNING),
       new EnumSet[] { EnumSet.of(State.PAUSED),
                       EnumSet.of(State.ENDED),
                       EnumSet.of(State.RUNNING,
                                  State.CONFIGURING) });

stateMap.put(EnumSet.of(State.PAUSED),
       new EnumSet[] { EnumSet.of(State.RUNNING),
                       EnumSet.of(State.RESET),
                       EnumSet.of(State.PAUSED,
                                  State.CONFIGURING) });

stateMap.put(EnumSet.of(State.RESET),
       new EnumSet[] { EnumSet.of(State.RESET),
                       EnumSet.of(State.PAUSED),
                       EnumSet.of(State.RESET,
                                  State.CONFIGURING) });

stateMap.put(EnumSet.of(State.ENDED),
       new EnumSet[] { EnumSet.of(State.ENDED,
                                  State.CONFIGURING),
                       EnumSet.of(State.RESET) });

// concurrent states
stateMap.put(EnumSet.of(State.RUNNING, State.CONFIGURING),
       new EnumSet[] { EnumSet.of(State.RUNNING),
                       EnumSet.of(State.ENDED,
                                  State.CONFIGURING),
                       EnumSet.of(State.PAUSED,
                                  State.CONFIGURING)});

stateMap.put(EnumSet.of(State.PAUSED, State.CONFIGURING),
       new EnumSet[] { EnumSet.of(State.PAUSED),
                       EnumSet.of(State.RESET,
                                  State.CONFIGURING),
                       EnumSet.of(State.RUNNING,
                                  State.CONFIGURING)});

stateMap.put(EnumSet.of(State.RESET, State.CONFIGURING),
       new EnumSet[] { EnumSet.of(State.RESET),
                       EnumSet.of(State.PAUSED,
                                  State.CONFIGURING)});

stateMap.put(EnumSet.of(State.ENDED, State.CONFIGURING),
       new EnumSet[] { EnumSet.of(State.ENDED),
                       EnumSet.of(State.RESET,
                                  State.CONFIGURING) });

// set initial state
currentState = EnumSet.of(State.PAUSED);

Instead of a single setCurrent() method, there are now two additional
methods: setPrimary() and setConcurrent(). The EnumSet toArray()
method returns values in their natural order. The natural order is the order in
which the enum values were declared. This is why the CONFIGURING state was
moved to the end of the State type declaration: because we always
have a primary state, any time the concurrent CONFIGURING state is added to the
EnumSet, it will always be returned in the second array position from a
toArray() call. The stateMap prevents two primary states two
concurrent states from ever being accidentally placed in the currentState.

private static EnumSet<State> setPrimary(State primaryState) {
    State[] states = new State[2];
    states = currentState.toArray(states);
    states[0] = primaryState;
   
    EnumSet<State> newState = EnumSet.of(states[0]);
    if (states[1] != null) newState.add(states[1]);
   
    return setCurrent(newState);
}


private static EnumSet<State> setConcurrent(State concurrentState) {
    State[] states = new State[2];
    states = currentState.toArray(states);
    states[1] = concurrentState;
   
    return setCurrent(EnumSet.of(states[0], states[1]));
}

Accessor methods getPrimary() and getConcurrent()
use the toArray() method as well. Except for the type change in
the method signatures from State to
EnumSet<State>, all other methods are identical to the
previous single-state example.

In the ButtonPanel, the stateActionMap will be based on primary
state transitions.

static {
     stateActionMap = new HashMap<State, EnumSet<Event>>();
               
     stateActionMap.put(State.PAUSED,
         EnumSet.of(Event.START, Event.RESET));
     stateActionMap.put(State.RUNNING,
         EnumSet.of(Event.PAUSE));
     stateActionMap.put(State.RESET,
         EnumSet.of(Event.START, Event.RESET));
     stateActionMap.put(State.ENDED,
         EnumSet.of(Event.RESET));
}

In the single-state example, determination of whether the CONFIGURE event
was allowed was based on the current (primary) state; now it is based on the
concurrent state. Rather than map all the possible primary/concurrent states in
the stateActionMap (which would be onerous), a simple check can be made in the
isAllowableAction() method -- the CONFIGURE event is allowable if
the concurrent state isn't CONFIGURING:

private static boolean isAllowedAction(Event actionEvent) {
     if (actionEvent == Event.CONFIGURE) {
          return StateMachineConcurrent.getConcurrent() !=
             State.CONFIGURING;
     }
               
     EnumSet<Event> allowed =
        stateActionMap.get(StateMachineConcurrent.getPrimary());
     return allowed != null && allowed.contains(actionEvent);
}

In other words, if the user isn't already in the process of configuring,
then the Configure button should be active. All other button activation is
based on the stateActionMap values. Aside from the StateMachine
and ButtonPanel classes, the rest of the application's code remains essentially
the same as in the simple state machine example.

Improvements

Using EnumSet.toArray() is a little inelegant, but it's good
enough in this instance. The State type could be changed from an enum to a
class:

class State {
    private PrimaryState primary;
    private ConcurrentState concurrent;
    ...
}

but care has to be taken to override the equals()and
hashcode() methods; these are automatically taken care of by
EnumSet. Also, the State class should never be returned as a modifiable
reference from getCurrent(): in the sample applications those
methods return either an enum value (simple state machine) or a copy of the
EnumSet (concurrent state machine).

A more flexible implementation would read the stateMap values
(the state transition mappings) from an input stream, rather than have them
hardcoded. Finally, while the technique works well for the simple application
demonstrated in this article, more sophisticated applications might benefit
from a fully-featured (but correspondingly complex) tool, such as one based on
SCXML.

Conclusion

What has been demonstrated is that Java enums and EnumSets can be used as a
basis to define and validate application states and state transitions. A state
machine can then be built around that to handle application events that change
application state, as well as send notification back to the rest of the
application when state transitions occur.

Resources


width="1" height="1" border="0" alt=" " />
Jeff Lowery is a long-time Java programmer and technical lead with expertise in data modeling, publishing, and printing. His was most recently project lead for a RESTful IPTV prototype.
Related Topics >> Programming   |   Featured Article   |   

Comments

Rather than concurrent state,

Rather than concurrent state, I would actually have separate states - execution state and configuration state - and have the dependencies handled in the event handling. That approach seems more generic and flexible to me. Do you see any advantage in your approach? In other situations I would just separate out the possibilities (RUNNING_CONFIGURING, RUNNING_NOTCONFIGURING, PAUSED_CONFIGURING, PAUSED_NOTCONFIGURING, etc), which I don't think is suitable in this situation.

Separate states: by that I

Separate states: by that I assume you mean separate state machine instances and separate state maps for each instance? I would say that there are some situations where the concurrent (parallel) state may not operate independently from the primary: the primary may determine what is allowable for the secondary. However, in the example given, that is not the case.

Handling state dependencies in the event handlers: my gut feeling is it violates the separation of concerns. States should be handled by a state machine, and events by an event handler. The idea is to have one state machine for the entire application, but event handlers can be scattered throughout. Putting state machine logic in various places in the application would make maintenance and debugging harder.

In a simple example, it is hard to show all the consequences of design choices. I did not discuss multithreading, for instance, which is a concern if multiple events simultaneously try to update the application state. For managing complex sets of states and events, it's a doubtful investment in time and effort to roll-your-own FSM; there are robust, heavy-hitting implementations that can found and incorporated into applications of that level of sophistication.

Thanks for this article. I

Thanks for this article. I do not need to support concurrent states, but I do like the methodology you used to implement your FSM.