Discussion on state machines

[Warhawk]

Hello Everyone,

I don't do programming for living but I've already done quite a few embedded applications. Today, I'd like to ask you how you typically design your state machines? I am not talking about the code but about the design. Two main questions are:

• When do you execute "state" code?
  Do you use entry and exit events?

When I talk to my friends, who do embedded programming professionally, they always execute the state code right before the code exits the state. This is probably due to simplicity when using the switch-case statement.

Various topics on the internet often talks about enter and exit action for every single state. Does this have any benefits or caveats? In my opinion it does not make much sense and it opens the door for bugs.

One bonus question:

• Moore vs Mealy - does this make any difference, when it comes to embedded ?

Thanks for any comments and thoughts :-)

[hamster_nz]

The academically pure 'Finite State Machine' gets somewhat watered down for embedded programming vs digital logic designs (where they must be kept 'pure' to work properly).

For example. entry and exit events are actually transitional states in a 'pure' FSM design, that are passed through very quickly:

Code: [Select]

   case state_wait_entry:
         do entry stuff.
         state = state_wait;
         break;
   case state_wait:
         do waiting stuff
         if(exit_condition)
           state = state_wait_exit;
         break;
   case state_wait_entry:
         do exit stuff.
         state = state_whatever_next;
         break;

But because this is such a common pattern entry and exit functions are added:

Code: [Select]

   ...
   case state_wait:
         if(last_state != state)
             do entry stuff.

         do waiting stuff

         if(exit_condition) {
           do exit stuff.
           next_state = state_wait_exit;
         }
         break;
    ...
    last_state = state;
    state = next_state;

For embedded programming FSM paradigm it is mostly used to avoid operations that would block for a long time, and to help handling asynchronous events like interrupts.

For embedded programming the Moore vs Mealy concepts make little sense... even in HDL they are 'ideals' and can get somewhat mixed..

[NorthGuy]

I don't think it matters much.

The reason for the state machines, is to spead the execution over time. Say you have a code:

Code: [Select]

void task() {
  do_a;

  while(c) {
    do_b;
  }

  do_c;
}

The problem is that you need to run many different tasks at the same time and sequential execution will not work well. Thus, you create processing functions for each of your tasks. Each processing function advances the corresponding task by a little then yields the execution so other tasks could work too. You then create a super loop which moves through all the tasks and gives opportunity to each. In the simplest way:

Code: [Select]

while() {
  process_task_one();
  process_task_two();
  process_task_thee();
}
Now, we have to crump our sequencial execution piece by piece into the single function which will be called repeatedly. There's number of ways to do it, which are called state machines, while, in fact, they're not FSMs. The most common way:

Code: [Select]

void process_task_one() {
  switch (state) {
     case STATE_IDLE:
        break;
     case STATE_START:
        do_a();
        state = STATE_LOOP;
        break;
     case STATE_LOOP:
       if (c) {
           do_b();
        } else {
          state = STATE_STOP;
        }
        break;
      case STATE_STOP:
        do_c();
        state = STATE_IDLE;
        return;
  }
}

Now setting the state to STATE_START will execute the sequence, so you start your task as:

Code: [Select]

int start_task_one() {
  if (state != STATE_IDLE) return 0; // already running
  state = STATE_START;
  return 1;
}

But you can do it in a multitude of other ways as well. For example, you can represent the state by a function pointer:

Code: [Select]

void (*process_task_one)();

void process_start() {
  do_a();
  process_task_one = &process_loop;
}

void process_loop() {
  if (c) {
    do_b();
  } else {
    process_task_one = &process_stop;
  }
}

void process_stop() {
  do_c();
  process_task_one = &process_idle;
}

void process_idle() {
 
}
Whether you have a formal entry/exit code, or how you set your states is completely immaterial. The relationship with theoretical FSMs is not of foremost importance neither. The only requirement is that the processing is fast enough and it does the same as the corresponding sequential code would do. These are the two aspects you need to concentrate on.

[mikerj]

I don't think it matters much.

The reason for the state machines, is to spead the execution over time. Say you have a code:

That is just one (fairly trivial) use for a state machine, they are used for controlling any state based function irrespective of whether an RTOS is used or not.

[SparkyFX]

Depends on the input. As far as i understood it, if the source does not debounce or denoise ideal you might have it easier to debug a Moore machine than a Mealy machine.

I however do not see an added value in additional entry and exit conditions when the transition itself can be described as a state of its own.

[Nominal Animal]

State machines are also an excellent way to document how a device works, especially if in simplified form.

(That is, not all states need to be described; but for mission-critical or safety sensitive devices, I believe state machines to be the best way to describe the correct operating procedures. Even if the device does not internally have a state machine at all.)

[Kalvin]

Flat state machines run out of steam when the transition diagrams get more complex. When the state machine gets complex enough, a hierarchal state machine may be easier solution for comprehension, creation, debugging and maintenance. The downside is that actual implementation of the the state machine engine will be more complex.

Here is an article showing a complex state transition diagram which would be quite challenging to be implemented using typical flat implementation: https://accu.org/index.php/journals/252

The article has also links to (Miro Samek's)  https://www.state-machine.com/ which has good articles on state machines and embedded systems design in general.

[Dielectric]

If my state machine gets larger than about two pg-dn keypresses, I split it into an HSM.  Just a rule of thumb.   

[snarkysparky]

I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.

[rstofer]

I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.

Since my primary use of FSMs is for FPGAs, I tend to think of them as organizing a sequence of operations.  In CPU terms:  Instruction Fetch state, Instruction Decode state, Operand Fetch state, Operation state, Store Result state, rinse and repeat.  Clearly some instructions will skip states, eg, an operand fetch may not be required or maybe the result doesn't need to be stored (in memory) RISC type CPU.

Or a short group of states to implement a handshake request/grant type of operation.  Contention for memory, perhaps.

From my point of view, FSMs aren't so much to isolate the code but rather to enforce a sequence of operations.

But, yes, FSMs can make code a lot easier to understand as everything that needs to be done in one state is right there, not spread all over the place.

[tggzzz]

I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.

That is indeed a major consideration and benefit which is valuable in a professional context.

FSMs significantly ease:

• seeing that all possible combinations have been considered and dealt with, even if that is a "should not happen therefore panic" state/event
• modification and enhancement - you can see exactly what code to touch and can can see that touching it doesn't affect other state/events
• semi-automated verification and validation
• live logging and fault-finding - simply keep a compact representation of event-state history, to be dumped if necessary
• timing responsiveness, so you can prove the system's slowness is due to somebody else's stuff, not yours
• asynchronous and highly parallel systems, using the "half-sync-half-async" design pattern

Don't implement FSMs via nested if-then-else/case statements; over time those become impossible to maintain/enhance.

[Rerouter]

My approch is generally stacked switch / case statements. Where ISRs may toggle flag checks to enter or exit.

Each switch / case holds the states for a given task, kept as self contained as possible. Next layer up might be overall task, e.g. network layer, then top level is conditional layer for what tasks need to have there state run.

Its generally mixed in with other non fsm code for me, but for external interfacing it keep the code hard to break. Not to mention you can make the exception cases do logging and put the device in a safe state.

[tggzzz]

My approch is generally stacked switch / case statements.

I've seen that destroy a profitable product line. The idiots allowed it to become an unmaintainable mess over the years. Yes, the world isn't ideal, and while original designers might have good taste, those that come after them often don't - and business idiots don't care about long-term technical debt.

One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.

Another scalable and maintainable technique is for each state to be a class, and each event to be a virtual method within the class; the method contains the action. The top level class is fully-populated all event metiods, with the body being either "should not happen" or "do not care" as appropriate. That allows hierarchical state machines with the minimum code in each state, but still to have simple event timing statistics plus state/event logging.

[rhb]

One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.

That has the great virtue of being compact, efficient and easily verified.  It's also very easy to modify.  It's very hard for me to see why anyone would do anything else.  With the initialization of each state and the event table for each state well commented, it's easy to understand.  It's a direct translation of the state diagram topology to working code.

[tggzzz]

One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.

That has the great virtue of being compact, efficient and easily verified.  It's also very easy to modify.  It's very hard for me to see why anyone would do anything else.  With the initialization of each state and the event table for each state well commented, it's easy to understand.  It's a direct translation of the state diagram topology to working code.

Exactly.

However, the class-based mechanism has some advantages, particularly w.r.t.

• hierarchical FSM descriptions (e.g. Harel/UML StateCharts)
• conciseness of common/default actions (i.e. in a super state/class)
• strong compile-time checking
• optimal interaction with an IDE's browse / show callers / command completion features

The last two really require a strongly typed language without macros.

[Dielectric]

One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.

I just wanted to +1 this idea; I've used it and it is really fantastic.

For those playing along, here's an intro that I just found since my code isn't really share-able:
http://blog.mbedded.ninja/programming/general/control-methodology/a-function-pointer-based-state-machine

..and then in the comments, the author makes a case for a simple RTOS to manage tasks instead of a big state machine.  Also a pretty valid point if you've got the space.

[rstofer]

One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.

That has the great virtue of being compact, efficient and easily verified.  It's also very easy to modify.  It's very hard for me to see why anyone would do anything else.  With the initialization of each state and the event table for each state well commented, it's easy to understand.  It's a direct translation of the state diagram topology to working code.

On a very small scale, I used the function pointers approach some years back.  It's clean!  I would make the pointers and the table CONST using whatever scheme was appropriate.  The last thing I want is the ability to change the transition table.  That would be a lot like self-modifying code and we got out of that business decades ago.

The idea of transition tables and function pointers first came up in a compiler course I took in grad school. 

https://www.amazon.com/Compiler-Construction-Digital-Computers-David/dp/047132776X

BTW, the book is typeset on a line printer.  Very unusual for a hardbound book.

[JPortici]

I'm glad i saw this thread.

I've always implemented state machines either graphically (on PLCs) or by a/multiple switch/case
I agree that they can become a mess to mantain.. especially when you have a switch inside a switch... argh! (this was a poor design choice and i was in a hurry to get a workable prototype. it's being rewritten to be less confusing to read and therefore debug.)

I never thought of using a function pointer matrix.. maybe because i never use them? but it's an interesting approach and i will read on

in a side note, do you know of any software that takes a state machine (whitten preferably in C) and translates it into a graph.. and vice-versa?
It seems it could be a great tool to verify if your code matches your intentions.

[rstofer]

Apparently there are a number of programs for dealing with state machine graphs.  Google for 'state machine graphing editor'

[Fire Doger]

I love pointers tables.
The first time I came up with this topology was when designing menus with subemenus inside other menus on 2x16 lcd.
For each menu item I had a seperate function and menu items grouped into tables according to subemenu.

When there was a level change between submenus I was updating the main table pointer to point to the table for the specific submenu.
It was bigger than simple ifs or switch but it was a piece of cake to add/remove/modify options in any level.

[NorthGuy]

When there was a level change between submenus I was updating the main table pointer to point to the table for the specific submenu.
It was bigger than simple ifs or switch but it was a piece of cake to add/remove/modify options in any level.

... and thus the OOP was born

[tggzzz]

I've always implemented state machines either graphically (on PLCs) or by a/multiple switch/case
I agree that they can become a mess to mantain.. especially when you have a switch inside a switch... argh! (this was a poor design choice and i was in a hurry to get a workable prototype. it's being rewritten to be less confusing to read and therefore debug.)

Yes; that's the usual trajectory Seen that too many times, but always managed to avoid it myself (sometimes after serious "discussions").

in a side note, do you know of any software that takes a state machine (whitten preferably in C) and translates it into a graph.. and vice-versa?
It seems it could be a great tool to verify if your code matches your intentions.

There are many that go from FSM diagram or FSM text to executable C.

Going the other way would require that the C has been written in a sane manner (starting with no macros!) and probably using a specific set of design patterns. If you are expecting something to work well with arbitrary C (e.g. nested case statements!), then you are expecting to have solved several seriously intractable problems

[Nominal Animal]

For graphs in general, I use Graphviz. You describe the nodes and the edges in a simple Dot language, and it lays it out for you. There is a gallery of examples, but I think this one might be relevant here, as its Dot source is particularly simple. Graphviz does have several different layout engines, and they have quite a few knobs you can adjust, to get the kind of a diagram you want. The engines can display the graph in a window, or generate an image file; I prefer mine in SVG format.

[Warhawk]

Interesting discussion here. I am happy to see it.

The problem I see with the table-based FSM implementation is function pointers. I was told that the critical-safety development environment does not practically allow pointers to any functions. This is probably due to static code analysis.

Some years ago (damn, already 5) I found a set of neat macros for FSM in C. I could not find the original article except this blog post:

https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/comment-page-1/

Attached is the file I found in my archive.

I hope this helps.

[Siwastaja]

I was told that the critical-safety development environment does not practically allow pointers to any functions.

This kind of babble is totally meaningless, and this particular "rule" is a just a constantly recurring urban myth, and while some organization somewhere could internally follow it, it doesn't make it a sane general rule to follow. Developing code for any safety-critical system requires really deep understanding, never random hearsay "rules of thumb", especially with really poor rationale.

What the heck is even "the critical-safety development environment" 


I often fail to see the critique about C macro play, and use macros quite a bit. But this fsm_macros.h thing kind of opened my eyes. This is pure horror. And what's the purpose? Hide a few characters of trivial, self-documenting code away, under weird macro names that do not follow any C syntax, and that expand to {} blocks that are supposed to connect to each other in very specific ways, so that if you do any mistake (while writing code that no longer follows basic C syntax), you'll most likely inadvertly generate code that does something completely unexpected.