Should I use multiple state machines for a layered protocol?

Question

When implementing a layered communications protocol are layers commonly implemented as state machines?

I have an implementation of PMBus I am currently working on for an embedded device. I have a interrupt driven interface for handling how the I2C uses the H/W driver to receive and transmit bytes onto and off of a buffer, essentially serialising the data.

A state machine then implements the "middle" SMBus layer taking the data from the buffer and forming messages from it according to how the protocol dictates what to expect for a generic type message, this state machine may also adds information based on input from additional I/O lines.

A second state machine then caps the stack with the PMBus layer by checking the generic message as it applies to specific types of messages, again adding some further information from I/O lines and subsequently looks up a command handler according to the message and passes it data from the message.

The whole caboodle then works in reverse for transmitting responses from the command handler or requests by other parts of the system (which works from a third state machine) to change output on I/O lines, such as recording an error status requiring a request for service signal.

I'm coming from a low level embedded background with little real-job programming experience consequently having only a little idea of the expected and accepted design patterns for common problems. Thus my question; is such state machine layering a common or logically expected solution to implementing layered protocols?

It seemed effective and robust to me (a soft requirement is that the layer functionality be encapsulated) when I thought it up some time ago but looking back on it it begins to seem somewhat over-engineered and that there could be some simpler method.

EDIT: I remembered the main reason that I followed this route is so that the execution of the higher layers is de-coupled from the interrupt driven interface. This is handy because from an interrupt for data being received up to the return from the command handler for the transmitted data may (depending on how the implementation is to be used) may constitute a relatively long time in comparison to my device's main business logic which operates quite fast and has a worst-case execution time requirement. Thus my business logic state machine (the third one from above) is what calls the protocol state machines, from the top on down, when it has time to. This means that while data receipt and transmission is asynchronous, the processing of the data is not.

Answer 1

You say you have little real-world experience in this area. Learn from experts to become one. Look around at what professionals of this field are doing to solve your problem. Open source PMBus implementations are out there. The Linux kernel is an example. But Freescale also has a PMBus library out there that is likely better for your background.

General advice about how to think about these things:

If the levels of the protocols are complex enough, then layering is a very good way to handle this complexity. However, layers create little mini-interfaces. So you don't want too many of them. Each of these can break up possible optimizations or slow performance. So, there is a balance to be made with layering to reduce complexity vs. performance. Remember that layering creates a rigid structure around the implementation. This rigidness helps to make it understandable, but the price is that you have by definition less flexibility.

Another way of looking at the problem is whether layers have state or not. In general, stateless layers are preferred. Many interacting state machines can lead to problems with keeping them in sync with one another. Don't take this too far. Obviously some layers have inherent state (such as the lower hardware I2C level with a multi packet message). But many layers do not. Often times, state is inherent at the hardware level and at the application layer. Try to keep any middle layers stateless. In your case, those extra bits of info from the I/O lines in the middle state might be a bit troublesome.

The most overlooked and complex part of these kinds of designs is the error handling. It may seem simple and straightforward at first, but then you realize all those little cases where the bus doesn't respond and you have to break out of that wait loop. Or the buffer is full and you received data, etc. This is where those interacting state machines can become a nightmare. Make sure you watch for those paths or you will have a lot to deal with.

Answer 2

I don't know about industry standards, but I have used state-machines in multiple layers of a communication protocol stack (sp. the PS/2 protocol) for the same reasons you gave; it worked pretty well: it allowed me to coordinate and control everything that was going on, esp. the interrupt-driven stuff.

Even though it went ok for me, I think you should pay heed to the advice and warnings of @thepacker and @caveman, because there is more overhead and complexity involved in running and coordinating multiple machines; you also have to be rigorous so that the design doesn't get away from you.

I should also mention that I have not had to maintain the stack -- it was a one-off project -- so I'm not sure how things would grow over time.

Problem areas I recall having had when designing things (it's been a few years and more than a few projects since I worked on this, so my recollection may be inaccurate) were having the machines of the different layers communicate with each other -- I ended up using static data, with accessor functions, shared between layers -- and controlling error handling. In the end my design had machines in each layer controlling the machine(s) in the layer below it for transmission; I forget how exactly reception was structured, but it was sort of on a separate band of control from the transmission.

As an alternative to using state-machines you might check out functional reactive programming (this looks like a nice tutorial on reactive programming). Though you probably won't be able to use it directly in an embedded project, it might give you some ideas on how to approach things.

If you still want to use state-machines, I've had good experience implementing them in C with this approach:

Use 3 functions to define and control the machine:

// get the next state based on the current
// state and the transition input --
// this should be a pure function
static State findNextState(prevState, input);

// react to a state transition --
// side-effects go in here
static void reactToStateTransition(prevState, nextState, input);

static State currentState = INIT;

// control the machine's state and
// call the other two functions
void transitionStates(input)
{
    State prevState = currentState;
    State nextState = findNextState(prevState, input);

    if (prevState != nextState)
    {
        reactToStateTransition(prevState, nextState, input);
        currentState = nextState;
    }
}

Then you can use this to transition states in, say, an interrupt:

void isr()
{
    transitionStates(SOMETHING_HAPPENED);
}

Or, better yet, have the interrupt flag for the transition to be carried out by non-interrupt-level code.

This structure works well for small- to medium-sized flat machines, but if you get a lot of states with a lot of transitions or, worse yet, nested state-machines, it doesn't handle things so well.