Introduction to FSM

[ea_man]

I'm going to design the software for a rover and I think I'm going to use state machines to implement the various functions, I've done some simple tutorial online about the use of the switch control structure and enum and that is ok for me.

I could use some structured info about how to design these things: I feel like I could use a better approach to manage transitions between states, some hierarchical structure, concurrent, maybe something to "dispatch signals" to multiple concurrent FMS... 

The most meaningful resources I've found on the web gogglin' for FMS are about video-games design: can you recommend something more suited do uC (I'm using arduino now for prototypes, later AVR or ARM maybe) or well, something good anyway... 

Thanks!

[ataradov]

I can't recommend a resource, since I never had a problem dealing with FSMs. But I can recommend a design approach. Do not invent FSM frameworks. Use plain switch-case statements. People reading your code will thank you for that

As for examples, one of my projects is Atmel Lightweight Mesh stack (http://www.atmel.com/tools/lightweight_mesh.aspx) is based on FSMs of all sorts. You can have a look at that for a clean (IMO) example of that.

[ea_man]

I can't recommend a resource, since I never had a problem dealing with FSMs. But I can recommend a design approach. Do not invent FSM frameworks. Use plain switch-case statements. People reading your code will thank you for that

As for examples, one of my projects is Atmel Lightweight Mesh stack (http://www.atmel.com/tools/lightweight_mesh.aspx) is based on FSMs of all sorts. You can have a look at that for a clean (IMO) example of that.

Thanks for the advice.
Is there an archive where I can read that without having to create an account on microchip / atmel site?

[ataradov]

Sure. Here it is https://dl.dropboxusercontent.com/u/6121480/work/lightweight_mesh_stack_v1.2.1.zip

[ea_man]

Sure. Here it is https://dl.dropboxusercontent.com/u/6121480/work/lightweight_mesh_stack_v1.2.1.zip

Much obliged.
Up to my reading list.

[rstofer]

One problem with FSMs is that you can get to a state and hang waiting on an event that never occurs.  In turn, things that should have happened didn't.

There is the concept of a Super Loop - a simple
while(1) {
  <all of the code, probably broken up by states>
}

So, basically, you go through the super loop looking for something to do.  You don't hang waiting on something.  If a task isn't ready (input signal, etc), we move right along to the next test.

In the "old days" of games on the Commodore 64, we had even and odd passes through the super loop.  That way the loop itself didn't take as long and we could deal with some issues on the next pass.

All of my FPGA projects use FSMs, a LOT of FSMs, but I'm pretty sure that I can't get stuck in a state and, so far, I have been successful.  But that's not how I would do robotics or anything like that.

I would prefer to use a full Real Time Operating System (probably FreeRTOS) and have tasks wait on semaphores and other tasks send signals to semaphores.  Input events are queued and processed in due time.  Outputs are buffered (thinking about UART) and that task runs autonomously.  And so on...

One of the things you get for the effort of using an RTOS is the concept of priority.  Input tasks are probably of a higher priority than output tasks.  Updating a screen might be the lowest priority.  Don't get carried away with priority but it's still a nice concept.

Spend some time looking at FreeRTOS.  If you decide not to use it, fine.  At least you will have had some exposure to the ideas.

[tggzzz]

I can't recommend a resource, since I never had a problem dealing with FSMs. But I can recommend a design approach. Do not invent FSM frameworks. Use plain switch-case statements. People reading your code will thank you for that

At first. Then other people will add a little bit of functionality. And different people will add another.

And soon you will have if-then-else or case statements nested 10 deep. Seen that. Shuddered. Ran away, fast.

Use a design pattern that allows you to separate states from each other (into classes in an OOP), and separates each event processing into a separate function within each state. That way you will be able to simply:

• determine which function in which class should be changed, in the knowledge that the changes won't affect other parts of the FSM
• log event reception and state trajectory, which is invaluable for post-mortem dump analysis

[ataradov]

And soon you will have if-then-else or case statements nested 10 deep. Seen that. Shuddered. Ran away, fast.

Any code can be turned into crap, it is not FSMs fault. I personally never had this problem.

[tggzzz]

And soon you will have if-then-else or case statements nested 10 deep. Seen that. Shuddered. Ran away, fast.

Any code can be turned into crap, it is not FSMs fault. I personally never had this problem.

Sure.

But your statement was in favour of if/case statements. While those can work for one-person small projects, they fail for multi-person long-term projects. And they don't provide easy logging that can be very useful when locating problems and deflecting the blame for problems/failure away from you your team and your company and onto other people/teams/companies.

[ea_man]

[CUT]I would prefer to use a full Real Time Operating System (probably FreeRTOS) and have tasks wait on semaphores and other tasks send signals to semaphores.  Input events are queued and processed in due time.  Outputs are buffered (thinking about UART) and that task runs autonomously.  And so on...

One of the things you get for the effort of using an RTOS is the concept of priority.  Input tasks are probably of a higher priority than output tasks.  Updating a screen might be the lowest priority.  Don't get carried away with priority but it's still a nice concept.

Spend some time looking at FreeRTOS.  If you decide not to use it, fine.  At least you will have had some exposure to the ideas.

Thanks, actually I'd like to spend some time studying FSMs as I came from hi level programming (OOP, events) and I'd like to face the limits of FMSs.
Yet working on a FMS and a RTOS implementation at the same time could prove interesting, in case as I'm going to do the very first easy steps on Arduino would it make sense to test Arduino_FreeRTOS_Library?
- https://www.hackster.io/feilipu/using-freertos-multi-tasking-in-arduino-ebc3cc
- https://github.com/feilipu/Arduino_FreeRTOS_Library

I guess an other easy option could be using Energia on a MSP432 as that would be very much Arduino-like (well I have one board around at least).
- http://energia.nu/guide/multitasking/

Otherwise I have a STM Nucleo board, one Teensey 3.1, Rpi.

Thanks all

[tggzzz]

One of the things you get for the effort of using an RTOS is the concept of priority.  Input tasks are probably of a higher priority than output tasks.  Updating a screen might be the lowest priority.  Don't get carried away with priority but it's still a nice concept.

Often you want the input tasks to be lower priority than the processing and output tasks, so they can exert flow control via back-pressure. I all depends on the overall system characteristics.

Task priority is a rathole that should be avoided where ever possible as it frequently leads to subtle rare problems that are impossible to predict. One infamous example is the Mars Pathfinder. Now space is just about the canonical definition of where careful high-rel design practices are followed, but:

The mission was jeopardised by a concurrent software bug in the lander, which had been found in preflight testing but was deemed a glitch and therefore given a low priority as it only occurred in certain unanticipated heavy-load conditions, and the focus was on verifying the entry and landing code. The problem, which was reproduced and corrected from Earth using a laboratory duplicate thanks to the logging and debugging functionality enabled in the flight software, was due to computer resets caused by priority inversion.

Bloody lucky! If they can get it wrong, so will most teams!

The best current approach to real-time communicating processes are the methods/libraries/patterns based on Hoare's CSP. Priority should be limited to background processing and grab-the-input-ISRs.

[rstofer]

One of the things you get for the effort of using an RTOS is the concept of priority.  Input tasks are probably of a higher priority than output tasks.  Updating a screen might be the lowest priority.  Don't get carried away with priority but it's still a nice concept.

Often you want the input tasks to be lower priority than the processing and output tasks, so they can exert flow control via back-pressure. I all depends on the overall system characteristics.

Task priority is a rathole that should be avoided where ever possible as it frequently leads to subtle rare problems that are impossible to predict. One infamous example is the Mars Pathfinder. Now space is just about the canonical definition of where careful high-rel design practices are followed, but:

The mission was jeopardised by a concurrent software bug in the lander, which had been found in preflight testing but was deemed a glitch and therefore given a low priority as it only occurred in certain unanticipated heavy-load conditions, and the focus was on verifying the entry and landing code. The problem, which was reproduced and corrected from Earth using a laboratory duplicate thanks to the logging and debugging functionality enabled in the flight software, was due to computer resets caused by priority inversion.

Bloody lucky! If they can get it wrong, so will most teams!

The best current approach to real-time communicating processes are the methods/libraries/patterns based on Hoare's CSP. Priority should be limited to background processing and grab-the-input-ISRs.

Yup!  Priority is a rathole and priority inversion is a real problem.

OTOH, consider a card reader (old school):  It better have a real high priority for column interrupts because the card keeps moving.  Memory wasn't always dirt cheap and large buffers weren't always common, especially on low end systems.

I think the Apollo guidance computer might be a good example of a priority based system.  The section under Operating System Architecture is very interesting.
http://history.nasa.gov/computers/Ch2-6.html

But, yes, keep priority usage to a minimum.

[tggzzz]

One of the things you get for the effort of using an RTOS is the concept of priority.  Input tasks are probably of a higher priority than output tasks.  Updating a screen might be the lowest priority.  Don't get carried away with priority but it's still a nice concept.

Often you want the input tasks to be lower priority than the processing and output tasks, so they can exert flow control via back-pressure. I all depends on the overall system characteristics.

Task priority is a rathole that should be avoided where ever possible as it frequently leads to subtle rare problems that are impossible to predict. One infamous example is the Mars Pathfinder. Now space is just about the canonical definition of where careful high-rel design practices are followed, but:

The mission was jeopardised by a concurrent software bug in the lander, which had been found in preflight testing but was deemed a glitch and therefore given a low priority as it only occurred in certain unanticipated heavy-load conditions, and the focus was on verifying the entry and landing code. The problem, which was reproduced and corrected from Earth using a laboratory duplicate thanks to the logging and debugging functionality enabled in the flight software, was due to computer resets caused by priority inversion.

Bloody lucky! If they can get it wrong, so will most teams!

The best current approach to real-time communicating processes are the methods/libraries/patterns based on Hoare's CSP. Priority should be limited to background processing and grab-the-input-ISRs.

Yup!  Priority is a rathole and priority inversion is a real problem.

OTOH, consider a card reader (old school):  It better have a real high priority for column interrupts because the card keeps moving.  Memory wasn't always dirt cheap and large buffers weren't always common, especially on low end systems.

I think the Apollo guidance computer might be a good example of a priority based system.  The section under Operating System Architecture is very interesting.
http://history.nasa.gov/computers/Ch2-6.html

But, yes, keep priority usage to a minimum.

And certainly don't tweak task priorities while designing/commissioning a system to avoid glitches and get the right result! That's been done too many times, usually with good short term and bad medium/long term outcomes!

[Cerebus]

Some collected thoughts on FSMs, some prompted by various comments, some just
based on experience.

First off, when you're designing your FSM there is, in my experience, no
substitute for drawing the whole FSM out on a big, perhaps bloody big, sheet
of paper. Circles for each state, big curved arrows between states labelled
with the signal/condition/input that causes a state change. If you need to
you can add things like timing constraints to the arrows - best colour coded.

When you've finished your diagram you've something you can use to visually
debug your design, code from, keep for documentation or just stick on the
wall to demonstrate your brilliance to everybody.

One problem with FSMs is that you can get to a state and hang waiting on an
event that never occurs. In turn, things that should have happened didn't.
...
All of my FPGA projects use FSMs, a LOT of FSMs, but I'm pretty sure that I
can't get stuck in a state and, so far, I have been successful. But that's
not how I would do robotics or anything like that.

There's a lot to be said for having a default 'get out of jail' condition
from each and every state in your FSM. The condition can be a watchdog timer
that's set when you enter each state, or any 'should not/cannot happen'
conditions while in that state. That condition should point to a state that
lets you recover from whatever has gone wrong. In most cases the recovery state
pointed to can just be your reset or initial state, but you can go for
subtler or more complex recovery schemes if that's to your taste.

Thanks, actually I'd like to spend some time studying FSMs as I came from hi
level programming (OOP, events) and I'd like to face the limits of FMSs.

A mathematical aside. The limits of FSMs are surprisingly high. Many types of
finite computation can be computed by an FSM limited only by the usual
time/space constraints and some rather abstruse mathematics. It's well known
(or at least ought to be) that a Turing Machine can can compute anything
computable including computations involving infinities. A class of machines
called push-down automata is the next most computationally capable type of
machine and FSMs are the next class of machines out from those.

If you're into linguistic computation those three classes of machine are exactly
the classes of machine required to parse context-sensitive, context-free and regular
language grammars respectively. This leads to the true but initially rather implausible
conclusion that you could use the lex (or flex) scanner generator to specify and code
an FSM in C. Having used lex and flex quite a lot, I wouldn't recommend it.


I'm sure that I missed something I thought of yesterday and meant to add but I've run out of steam.

Just remembered it (after posting, naturally).

As far as priorities, avoiding deadlock, priority inversion and the like there is a very useful set of
techniques known as wait-free or block-free algorithms. One of the aspects of these techniques is that,
used properly, they guarantee progress for computations that use them.

They are not generally well known and some aspects of them are definitely current research
projects for the computer science community but there are practical algorithms and applications
out there. You are more likely to find details reading papers rather than textbooks.

[rstofer]

It's clear that hardware uses FSMs.  That's the majority of code for FPGAs (for my projects, anyway).  But we know when we write the code how signals will (or should) behave.  In addition, each FSM is fairly small and does little in each state.  We make up for it in volume!  There are LOTS of FSMs and they all run in parallel.  Dozens and dozens of little processes all working on their own part of the puzzle.  In parallel!

I could see a super loop wandering through the processing of several FSMs but one big hairy FSM doesn't appeal to me.  The transition matrix (if used) gets too large.  Further, we spend compute cycles testing if something has (or should have) happened rather than just getting a notice that it has happened and it should be acknowledged (processed) when time is available.

In other words, I would go for the RTOS every single time.

A character comes in on the UART (hardware interrupt and char placed in queue).  The interrupt handler sets (or increments) a count on a semaphore, the kernel notices this and, when time is available, it dispatches the task the handles UART processing.  There's no time lost testing for things, the event causes the dispatcher to know that something has happened.

The RTOS is so much cleaner.  Tasks can be relatively small bits of code that do very clearly defined things.  And that's all they do.  Get in, do the job and get out!

Shared resources is another reason for using an RTOS.  If this applies in this project...

[tggzzz]

It's clear that hardware uses FSMs. 

So does software, of course. Frequently that is unclear (in several senses)

That's the majority of code for FPGAs (for my projects, anyway).  But we know when we write the code how signals will (or should) behave.  In addition, each FSM is fairly small and does little in each state.  We make up for it in volume!  There are LOTS of FSMs and they all run in parallel.  Dozens and dozens of little processes all working on their own part of the puzzle.  In parallel!

I could see a super loop wandering through the processing of several FSMs but one big hairy FSM doesn't appeal to me.  The transition matrix (if used) gets too large.  Further, we spend compute cycles testing if something has (or should have) happened rather than just getting a notice that it has happened and it should be acknowledged (processed) when time is available.

In other words, I would go for the RTOS every single time.

A character comes in on the UART (hardware interrupt and char placed in queue).  The interrupt handler sets (or increments) a count on a semaphore, the kernel notices this and, when time is available, it dispatches the task the handles UART processing.  There's no time lost testing for things, the event causes the dispatcher to know that something has happened.

The RTOS is so much cleaner.  Tasks can be relatively small bits of code that do very clearly defined things.  And that's all they do.  Get in, do the job and get out!

Shared resources is another reason for using an RTOS.  If this applies in this project...

That might be interpreted as advocating one-task-per-FSM, which is a design anti-pattern. There are better ways. Actors and the half-async-half-sync design pattern are a good starting point. Hoare's CSP is another.

[Cerebus]

It's clear that hardware uses FSMs.  That's the majority of code for FPGAs (for my projects, anyway).  But we know when we write the code how signals will (or should) behave.  In addition, each FSM is fairly small and does little in each state.  We make up for it in volume!  There are LOTS of FSMs and they all run in parallel.  Dozens and dozens of little processes all working on their own part of the puzzle.  In parallel!

I could see a super loop wandering through the processing of several FSMs but one big hairy FSM doesn't appeal to me.  The transition matrix (if used) gets too large.  Further, we spend compute cycles testing if something has (or should have) happened rather than just getting a notice that it has happened and it should be acknowledged (processed) when time is available.

In the mathematical (or computer science) study of finite automata the 'several FSMs in parallel' is known as a Non-deterministic Finite Automaton (NFA), the "one big hairy FSM" as a Deterministic Finite Automaton (DFA). That is, the state machine for an NFA can be in multiple states simultaneously, the state machine for a DFA may only be in one state at a time. It can be proven that for every NFA there is an equivalent DFA and the good bit is that there are algorithms to convert an NFA into a DFA. The trick is that one state in a DFA can represent a superposition of states from an NFA.

Problems are easier to specify and comprehend as NFAs but more efficiently represented and executed as DFAs. If you've got tools to do the transformation for you, you can reap the benefits of NFAs (easier specification, parallelism) with DFAs (less resource usage, serial execution with identical results to parallel execution).