big vs. nested statemachines

Question

I have a statemachine in a real-time system with very few (3) states.

typedef enum {
    STATE1,
    STATE2,
    STATE3
} state_t;

However, the transitions between those states need considerable time and have their own subdivisions. So I have two choices, either I extend the main statemachine such that all the intermediate states are represented:

typedef enum {
    STATE1,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3,
    STATE2,
    ...
} state_t;

or I create a nested statemachine for the relevant main states:

typedef enum {
    STATE1_NOT_ACTIVE,
    STATE1_NORMAL,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3
} sub_state1_t;
...

Both possibilities have their advantages and drawbacks. The big statemachine gets messy and complicated very easily. However, having all the states consistent in the second case isn't trivial either and many functions would need information about both the global state and the substates.

I'd like to avoid complicated code which has to handle several parallel states, like:

if ((global_state == STATE1) &&
    (sub_state_1 == STATE1_DO_TRANSITION_TO_STATE2))
{
    ...
    if (transition_xy_done(...))
    {
        global_state = STATE2;
        sub_state_1 = STATE1_NOT_ACTIVE;
        sub_state_2 = STATE2_NORMAL;
    }
}

What is the general best approach for such a problem: many small and nested statemachines (with many invalid combinations), one big statemachine or anything else?

Answer 1

As you mentioned, big state machine gets messy so it is very difficult to maintain. Several smaller SMs are always easier to understand and maintain.

Another drawback of big SM - bigger transition table, thus lookup takes longer.

Answer 2

Many small state machines are going to give you more code flexibility down the road, especially if you need to redesign anything. Then you should (hopefully) be able to change a nested state machine without having to change any of the other nested state machines.

Having a bigger transition table shouldn't result in longer lookups, since I assume that you lay out the table sensibly in memory. If anything, you should actually be able to get a little more speed out of the big machine simply because you don't have the extra one or two steps you might need with the small state machines to transition cleanly between them. But given the added complexity of this method, I'd suggest the following: design with nested state machines, then once everything works, refactor into a single state machine if necessary to gain a little speed boost.

Answer 3

Why don't you use the state pattern?

Answer 4

First, I want to commend you for recognizing what's happening and making these states explicit (since they are in fact additional states in your model, not really transitions with an action). Far too often I see state machines that end up like your last example (that you want to avoid). When you have tests for 'additional' state variables inside your event handlers, it's a sign that your state machine has more states that you've really put into the design - those show be reflected in the design, not jammed into the existing state's event handlers with a bunch of spaghetti coded checks for additional 'state' encoded in global variables.

There are several frameworks for C++ that model hierarchical state machines - HSMs - (which is what your nested state machine idea sounds like), but the only one I'm aware of that supports straight C is Quantum Framework, and I think that buying into that would probably mean a decent level of commitment (ie., it's probably not a simple change). However, if you wnt to look into this possibility, Samek has written a lot of articles (and a book) about how to support HSMs in C.

However, if you don't need some of the more sophisiticated parts of the HSM models (such as events that aren't handled by the 'innermost' state get bubbled up to be possibly handled by parent states, full enter and exit support for the entire state hierarchy), then it's pretty easy to support nested state machines just as completely independant state machines that happen to start and stop when a parent state is entered/exited.

The big state machine model is probably a bit easier to implement (it's just several more states in your existing framework). I'd suggest that if adding the states to your current state machine mode doesn't make the model too complex, then just go with that.

In other words, let what works best for your model drive how you implement the state machine in software.

Answer 5

I don't think there is a single, general approach. As others have said, it depends on what you're trying to do.

Broadly speaking, I'd avoid nesting small state machines inside larger ones, as not only are you adding more states - and hence complexity - when you're trying to simplify things, you now have two state variables to keep track of.

In particular, the "inner" state variable has to be properly initialised when traversing states in the "outer" state machine. For example, what if, due to a bug, there's a transition in the outer state machine which fails to reset the state variable for the inner state machines?

The one possible exception to this is where all the inner state machines do the same thing. If it's possible to parameterise the data (say, by using an array), then you can have a single implementation of the inner state machine, and it may be possible to replace the outer state machine with a counter or similar.

To give a simplistic example:

#define MyDataSIZE 10

void UpdateStateMachine(void)
{
    static enum {BeginSTATE, DoStuffSTATE, EndSTATE} State = BeginSTATE;
    static unsigned int Counter = 0;
    static unsigned int MyData[MyDataSIZE];

    switch(State)
    {
        default:
        case BeginSTATE:
            /* Some code */
            if(/* Some condition*/)
                {State = DoStuffSTATE;}
            break;
        case DoStuffSTATE:
            /* Some actions on MyData[Counter] */
            if(/* Some condition*/)
                {State = EndSTATE;}
            break;
        case EndSTATE:
            /* Some code */
            if(/* Some condition*/)
            {
                Counter++;
                if(Counter >= MyDataSIZE)
                    {Counter = 0;}
                State = BeginSTATE;
            } /* if */
            break;
    } /* switch */
} /* UpdateStateMachine() */

Answer 6

I vote for the bigger state machine, assuming that a single machine can only be in one of the big state machine states, it should logically be there.

By using one big machine you are using a characteristic of the environment to prevent a state in which two states exist at the same time, making the program safer, and more readable.

Also one big state machine has the advantage that any other programmer can easily understand all the states by looking in a single place (that is, get the big picture), vs looking in a single place, hopefully be aware of the sub-division, then having to look at each sub-division.

Also as you've suggested working with several state machines will force you to send more parameters, performing more than one test for each state, etc'...

As for future expectations I'm a believer in the YAGNI.