Saturday, August 25, 2012

State Machine Function Calls

I had a project which controlled up to six motors. The motors ran asynchronously and (from my POV) were controlled via a CAN bus. To make the system more deterministic and simpler no RTOS was used. Everything was controlled by state machines. Logically we could consider each motor having its own "thread" and its own collection of state machines. But since all of the motors performed identical operations they could share code even though each could be executing different parts of that code. Only the data for each motor had to be unique -- like homing states or motor positions.

State machines can result in some pretty ugly code if you're not careful. They're really nothing but glorified GOTO statements. To make the code more maintainable and more efficient I wanted to simulate nested function calls. And I wanted each function call to behave like a blocking call but each call was actually going to be to yet another state machine. You can't block a state machine. It kind of defeats the purpose. If one motor "thread" was blocked then all "threads" stop. None of the other motors could proceed with their states. State machines have to keep running.

Let's say StateMachine1 calls StateMachine2 which calls StateMachine3 and this machine is in a waiting mode. Then on each cycle we have to traverse from SM1 down to SM3 to test a condition and then back out again. Normally there's no good reason to do this. SM1 is simply waiting for SM3 to finish. Why bother calling SM1 and SM2 when we know we're in SM3? It would be better if an outer loop simply proceeds directly to SM3.

I came up with a simple way to do this. Each motor "thread" is really a data structure with some global information and a reference to be used for some local information. At a minimum globally we need a function address which is the currently executing state machine, and the current state of that machine. At a minimum the local information, which could almost be considered stack information, has the parent's state machine and its state. The outermost loop simply executes an indirect function call to the appropriate machine passing a pointer to that thread's global data structure. The state machine uses the permanent thread number to reference that thread's local data for that machine. Each state machine contains its data and only knows about its data. When one state machine "calls" another, the calling code copies the parent's address and state into the child's data structure and puts the child's address into the common data structure. In other words, each "thread" has a global data structure plus a changeable portion which is local only to the currently executing state machine. Each state machine has its own data structure for each possible thread. In my case that was six data structure, one for each motor. So each motor is assigned a thread number and this thread number is used as an index into its private data area in each state machine.

Note that the state machines must have two system-known states (or cases). SM_INITIALIZE is used to load the global area's local data pointer. SM_ENTRY is always the first state of the machine on a call, that is, it's the logical entry point. Internal states begin at START_INTERNAL_STATES.

Here is sm.h which defines the global data structures:

Here is sm.c which contains the core setup, call, and return functions:

And here is a simple test program which is mostly stubbed out.

InitializeTest should be called once then ExecuteAllStates should be called in an infinite loop after that.

As I hope you can see, no matter how deep we nest the state machine calls we never pay for it with a time penalty. Execution always proceeds directly to the currently executing state. We merely load a couple of pointers and execute a case in a switch statement. The biggest penalty is with the call itself but this occurs only once to get into that state machine. While we're there that penalty disappears.

Finally, here is smlocals.h which is where I defined the local data structures:

This method of defining local data structures is a bit uncommon and may be unnecessary. As a policy I try to hide data from functions which don't need to know about that data. It may be overkill. Basically, within functions (state machines) I switch in the appropriate structure with one or more #define statements. These flags enable only the structures used by that function -- that it, its own and others it may need to know to pass variables to something it calls.

-- Don Jindra


Created August 2012