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

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 (i.e., it's probably not a simple change). However, if you want 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 sophisticated 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 independent 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.