Article - Example state machine code for microcontrollers

[jakeypoo]

This is the about the only way you can do it and get safety certifiable code (I.E.  MIRSA,  Medical or Flight Safety) that is maintainable.

A couple other things I do:

Querys to the state Machine are always done through a function

uint8_t MyFSM_GetState();

transition are always done with a function (NEVER modify the variable directly)

uint8_t MyFSM_TransitionToState(uint8_t NextState);

The FSM has a Process and Init() function for The FSM

MyFSM_Init();

MyFSM_Process();

...

All programs need a super loop....   Even with an RTOS... Which is a glorified *set* of super loops with automated way to switch between them.

Thanks, all good points.
Sometimes the super loop can be less -- super. Sticking all of the logic flow in the main loop of a program is one of these things that those of us who were not formally taught programming tend to do for too long.

[nctnico]

Actually it is better to stick everything in one loop. Having several concurrent threads is a major pain in the ass to get right. The phases I see with programmers is:
- put everything in one loop
- use parallel threads
- put everything in one loop but get it right this time

[tggzzz]

Actually it is better to stick everything in one loop. Having several concurrent threads is a major pain in the ass to get right. The phases I see with programmers is:
- put everything in one loop
- use parallel threads
- put everything in one loop but get it right this time

It depends on the application domain's requirements. Sometimes it is necessary and beneficial to have multiple threads, but they have to be used judiciously, preferably following simple design patterns. Fail to do that and you have an unholy mess.

Rule of thumb: if an application programmer uses "synchronised" "volatile" "wait" "notify" etc, then the design is probably a mess.
Rule of thumb: if an application programmer uses library components such as "fifo" "queue" "mailbox" and sets the capacities and the send/receive blocking/non-blocking characterisitics appropriately, then the implementation is probably sound.

The "Half-sync half-async" design pattern is a well-proven technique, see http://www.cs.wustl.edu/~schmidt/PDF/PLoP-95.pdf

Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).

[ehughes]

Sometimes the super loop can be less -- super.

I certainly don't disagree!        My point was more about what all that code translates not,  not necessarily what the text file looks like.         My main loops almost always to be  Init phase followed by a very high level system state machine.    Something you can generally follow with minimal scrolling, etc.   There is not really behavioral code, other than that main switch for a state machine and function calls with descriptive names to understand what processes are in what state.   If the machine grows bigger than a handful of "system" states then it needs to be re-thought.

I.E.  something that you could start at main() and get a gross level understanding of where to go next.   Something that you can easily see what processes are running in what state, etc.     


Here is what I have generally observed.   

1.)    There are "software" people who obsess over what the text file(s) looks like for state machine encoding.   These are the "Java people"  of the world (not using this as a pejorative) who obsess over how a code looks more than it acts,   use delegates and function pointers everywhere to make the text representation compact, etc.

2.)   Then there are hardware people who have built state machines from raw gates or used a ROM as a state decoder.     Anyone who does this or has written HDL look at the state machine design in C in a completely different way.    Hardware is a lot less forgiving and doesn't give a shit about cute software paradigms.   These people almost always use a switch as that IS the optimal way that a synthesize wants to see it in HDL.   It is exactly how it would map to a hand wired ROM.  Hardware can't crash, get funky, etc.  as fixing silicon and cutting PCB traces is a lot more tough than fixing high level software.

Not to say there aren't people in the middle but those are the two bins that cover the 6-sigma in my observations/     I have always been more aligned with camp #2 but there are many CS people who do #1 as that is what they know.  Neither is "right" or "wrong",  it is just 2 different approaches.

Most of what I do has to fall into the category of safety certifiable and high reliability.  That eliminatws 99% of the CS "fluff" from implementations.   That stuff is nice in a classroom but useless when it comes to applications that simply cannot fail.

Not all behavior falls into textbook FSM implementations.     That and if your system grows to a point where it takes 6-months to upgrade,   there is something else wrong in the general approach.   The problem needs to be rethought.  This is not a problem with the choice of state machine implementation but the general solution to how the problem is solved.

[Mechatrommer]

Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard.

what kind of nonsense is this? a java fanboy keeps bragging about "java built-in library" as a "java language specification"? can you differ "language's specification" with "language's standard library implementation?", or do you even know how a "language's standard library" is built? if you are incapable of making a code without a "library" (namespace or class or whatever higher level encapsulation) then we are sorry, get a life, there are still so much you need to learn, your "fast java" is not so entertaining.

[tggzzz]

Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard.

what kind of nonsense is this? a java fanboy keeps bragging about "java built-in library" as a "java language specification"? can you differ "language's specification" with "language's standard library implementation?", or do you even know how a "language's standard library" is built? if you are incapable of making a code without a "library" (namespace or class or whatever higher level encapsulation) then we are sorry, get a life, there are still so much you need to learn, your "fast java" is not so entertaining.

Thank you for so clearly demonstrating your profound ignorance of several key points. It makes it easy for everyone to assess your contribution.

In future, would you please make your rants more entertaining.

[nctnico]

Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).

I still see a lot of typical concurrency problems in Java applications. Regarding C++: you can offload the multi-threading headaches to a framework but just like Java you do need to make sure things keep happening in the correct order.

[Dinsdale]

1.)  There are "software" people who obsess over what the text file(s) looks like for state machine encoding.   These are the "Java people"  of the world (not using this as a pejorative) who obsess over how a code looks more than it acts,

I'm very picky about how code looks on the page -- state machine or otherwise. I think formatting is very important to readability. But I hate Java. So I thought your comment was kind of funny. But I think I know what you are trying to say. Being overly picky about looks (guilty) is one thing, but the anal retentive coding style that Java demands just drives me crazy.

But all this about using loops, state machines, threads, and every other programming pattern is silly. I mean picking one method to apply to all problems is silly. The PROBLEM you are trying to solve is what picks the programming pattern. At least if you let it. You may not recognize the ideal pattern at first, but if you find yourself writing convoluted code, or it's becoming a struggle to fit your problem to the code you are writing, then you need to rethink what you are doing.

I remember a long time ago studying recursion. I sort of got the idea but thought it was an extravagant and dangerous (stack depth problems) solution. Then, much later, I was having to write a kind of calculator. I wrote a function to do the basic four arithmetic functions in a very general way. When I had that I started running it in my head: Add 7 + 8, save the result; now return the result to caller; now divide by 3. Well, now I need to call my function again... Oh, now I'm going to have a stupid string of calls to the same function and tracking precedence is going to get hairy. How about if I just store intermediate results and re-call this function while I'm still in it? I'll just "eat" this equation completely before I ever leave the function. Oh, yeah, that's that recursion thing I studied a while back!

My data told me what solution to use. Hell, it practically begged me to use recursion. I think a lot of problems are like this, and if you learn to "listen" to your problem, it will many times give you the answer.

[tggzzz]

I'm very picky about how code looks on the page -- state machine or otherwise. I think formatting is very important to readability.

But all this about using loops, state machines, threads, and every other programming pattern is silly. I mean picking one method to apply to all problems is silly. The PROBLEM you are trying to solve is what picks the programming pattern. At least if you let it. You may not recognize the ideal pattern at first, but if you find yourself writing convoluted code, or it's becoming a struggle to fit your problem to the code you are writing, then you need to rethink what you are doing.
...
 and if you learn to "listen" to your problem, it will many times give you the answer.

I agree with all of that.

I know when things are "going right" because my codebase becomes smaller. (Please don't mention idiots that think anything resembling "lines of code" is a good metric for progress).

[tggzzz]

Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).

I still see a lot of typical concurrency problems in Java applications. Regarding C++: you can offload the multi-threading headaches to a framework but just like Java you do need to make sure things keep happening in the correct order.

Oh, sure you can avoid using language and library facilites correctly, just as you can drive down the wrong side of a motorway.

The difference is that C/C++ explicitly precludes you from doing it correctly in the general case, albeit not in some ad-hoc special cases.
Don't take my word for it. Read and understand Nick Maclaren's "Why Posix Threads Are Unsuitable for C++" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf
That isn't a crackpot document; Hans Boehm regards that document as an important contribution to standardisation, see http://www.hboehm.info/c++mm/

I suspect that the latest C/C++ standards have improved in this respect, but how many full compilers exist and how many projects can use them due to stability and backward compatibility issues?

[nctnico]

The article in the PDF is rather dramatic and focusses on dividing single tasks into multiple processes which need a tight coupling of data. Nowadays there are several ways to deal with threads in C++. Yet you need to be aware of what data belongs to which thread. Perhaps that can be offloaded as well (*) which IMHO is what the article is about: sharing data between parallel tasks. For loosely coupled tasks there isn't a problem at all.

(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.

[tggzzz]

The article in the PDF is rather dramatic and focusses on dividing single tasks into multiple processes which need a tight coupling of data. Nowadays there are several ways to deal with threads in C++. Yet you need to be aware of what data belongs to which thread. Perhaps that can be offloaded as well (*) which IMHO is what the article is about: sharing data between parallel tasks. For loosely coupled tasks there isn't a problem at all.

Not really. I regard multiple threads with zero inter-thread communication as a theoretical construct of no practical relevance whatsoever.

The problems are related to sharing data, not to the amount of data. If you have any communication whatsoever, then there can be intermittent problems - and problems are observed in real live code.

The author works in an environment (HPC at University of Cambridge Computing Centre) which stress tests all aspects of computation - and he has done since the 1960s. He really knows where the sore points are, and where the bones are buried.

(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.

No. The problems are fundamental and explicit.

The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.

The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!

[Mechatrommer]

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf
enuff said...

Why Posix Threads Are Unsuitable for C++? because Posix Threads is an unholy mess.

[hamster_nz]

Howdy,

I wanted to share a write-up I put together on a piece of code I use regularly when a microcontroller application calls for a state machine. It goes over some example state machine code and explains some basics about how state machines work. Take a look if you're interested: http://www.heptapod.com/lib/statemachines/

The example uses an atmega328, but the concepts could be applied to any micro that uses C. It might be a little basic if you already know this stuff, but I hope it helps any beginners or intermediate folks out there trying to get away from writing the giant while(1) loops in their event-driven microcontroller code.

Hi Jakeypoo,

I enjoyed your post / blog entry. Well done. It looks like you are learning a lot during the process. Far more than I learned reading the thread

Also, I just wanted to say you have my sympathies - It seems that the first rule of EEVBlogs is that when anybody is proud of their achievement others come along to say "you have done it all wrong" but never actually bother to teach what the better way is, and how or why it is better. Maybe there is a law that any programming discussion devolves into a C++ vs Java bashing thread?

I could even put up a simple "I flashed a LED with a 555" and people would endlessly comment on with gems like "oh, you should have used the CMOS parts for lower power", "oh those resistors are too high - you'll get too much noise causing jitter", "oh, are you sure that you want THAT much/little current through the LED?","Did you use a low ESR cap?", "how stable is it? You should use a crystal reference", "You can do that for 0.02c with a ATtiny, and fewer parts".

[nctnico]

(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.

No. The problems are fundamental and explicit.

The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.

The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!

If the problem would be really that big we wouldn't have functioning PCs on/under our desks... IOW the problems are known and workarounds (if necessary) are in place. A lot has improved on C++ over the past 10 years (I recall the C++ mess required to program with Nokia's Symbian OS). The STL libraries also solve a lot of common programming problems.

[tggzzz]

(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.

No. The problems are fundamental and explicit.

The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.

The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!

If the problem would be really that big we wouldn't have functioning PCs on/under our desks... IOW the problems are known and workarounds (if necessary) are in place.

That is one of the special cases corresponding to "specific processor+memory+compiler+library + compiler switches".

A lot has improved on C++ over the past 10 years (I recall the C++ mess required to program with Nokia's Symbian OS). The STL libraries also solve a lot of common programming problems.

And, from what I can make out, introduced others.

[tggzzz]

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf
enuff said...

Why Posix Threads Are Unsuitable for C++? because Posix Threads is an unholy mess.

True, but that's not the only problem with C/C++.

In C/C++ explicitly and by definition, no memory model in the C language. Anything related to that is "implementation defined" and punted to the libraries. The latest specification finally gives up on attempting to justify that gross omission by including a memory model. The success and backward compatibility are yet to be determined.

Hence the Posix (and other) libraries to do with, for example, multithreading are in an impossible position: they have to rely on language properties that are explicitly undefined and left up to the libraries to sort out. The best they can do is select a few common cases and hope programmers/users don't find the corner cases.

Memory models are very difficult; even though it was possible to start with a clean slate, Java still got it wrong and had to introduce a revised memory model! I don't fancy C/C++'s chances, but we'll see how it progresses and what crawls out of the woodwork.