Designing a state machine/task scheduler for MCUs
Background
This is a brief tutorial with examples for how to set up and design a simple "bare metal" microcontroller program consisting of a finite state machine, or a task scheduler or similar. It is common that we find ourself with the need to execute functions in a certain order.
Either we could have some manner of state machine where a state function needs to be executed based on the current state - many types of applications at least have a need for a safe state and an active/running state.
Or maybe we are designing our own "lite" version of a RTOS where a number of listed tasks need to be executed in sequence. What I'm going to describe is also essentially how you could build the foundation to OS-like behavior.
And no matter the purpose, we also want to add error handling, timeouts, watchdogs etc to ensure program integrity and safety.
There are informal design patterns for this (I don't think it got a fancy name), that ensure readability, maintainability, encapsulation and all that good stuff, while avoiding anti-patterns like "stateghetti programming" (Why is global evil? ), where a state variable is updated from deeply within each state and shared across multiple files. Programs with lots of global "flags" or "states" quickly get complex, buggy and hard to maintain, especially for others who didn't write the original source.
Listing the states
As an example, lets assume we are writing the firmware for a simple coffee machine.
It is a single core MCU with a single process program, with as few interrupts as possible. Out of our requirements gathering, we've come to the conclusion that we want to express the whole program as a state machine. The coffee machine sits idle most of the time and while it does, it scans the buttons (or touchscreen etc). If nothing was pressed, it will remain in that state, otherwise it will start making a cup of coffee by in turn grinding the beans, mixing in water and then pouring a cup. And there will be some manner of maintenance/safe state when running out of beans or when there is no water for whatever reason.
All of these states will be implemented in some state machine module of its own, lets say coffee_states.h and coffee_states.c. These may in turn include all manner of other files.
Whenever making a code module (or class or ADT, call it what you like, a rose by any other name...), we should make it a habit of always coming up with a source code prefix. That is, something we will write in front of every function, enum, constant etc that the module exposes to the outside world. That way the caller can easily identify which module a certain item belongs to without the need to manually track it down in the source every time. It also helps a lot against namespace collisions, which is definitely a thing in larger projects.
Lets settle for the prefix coffee in this case. Meaning that all functions will be named starting with coffee_ and all public enums/constants/macros will start with COFFEE_. No other module in the program should use the same prefix.
We have already identified all the states in the coffee machine, so now we can make an enum corresponding to them:
typedef enum
{
COFFEE_SCAN_BUTTONS,
COFFEE_GRIND_BEANS,
COFFEE_MIX_WATER,
COFFEE_POUR,
COFFEE_MAINTENANCE,
COFFEE_STATES_N
} coffee_state_t;
All enumeration constants have the established source code prefix. At the end we added a "counter" type of enumeration COFFEE_STATES_N, which isn't an actual state but rather a constant corresponding to the number of states present in the program. Since enumeration lists always start with zero and automatically get increased by 1, it will end up as 5 in this case - and we have 5 states indeed. Should we add states later during maintenance, this counter will automatically update itself.
There's a common coding style in C where all custom types are ended with postfix _t. If you use that style or not is entirely optional. (It will collide with POSIX in case of hosted system applications, even though the practice has been around since before POSIX. Most embedded systems probably don't care the slightest about POSIX though.)
Status/error codes
We will also like to come up with an enum to use for status and error codes - the results of every public API function in the coffee_states module. Unless the code is very complex, it will work fine for all states to use the same type for this, even if one particular state will only use a few of the status/error codes. If they all use the same type they can also have that one as a common return type from each public function, corresponding to that function's result. It is a "de facto" standard in C to always reserve function return types in public APIs to a status/error code. We should also avoid using bool/int etc for that, since that's just too blunt and nondescript.
typedef enum
{
COFFEE_OK,
COFFEE_IDLE,
COFFEE_NO_BEANS,
COFFEE_NO_WATER,
COFFEE_UNEXPECTED,
} coffee_result_t;
What's important here is that the first state in an enum like this should correspond to OK/no errors, with the value 0. This is also a de facto standard way to write programs, so that any non-zero value corresponds to a specialized status/error code. There is probably no need to know the number of status/error codes so I skipped the counter variable in the end this time. The "unexpected" error is something I always add for defensive programming purposes - it is one we can use for scenarios that should never happen in theory.
Note the trailing commas - the last item in an enum is the only one which may not end with a trailing comma, so we can use that to mark the end of an enum. Similarly, an enum that should be possible to maintain by adding more items should have a trailing comma after each item. (Even the last one may have trailing comma since C99.)
Defining states as functions
Okay so now that we know the states and the status/error type and we have concluded that all functions in the state machine should use this, we can define a function type that all functions in the coffee_states state machine should use. Such a type will be handy for declaring function pointers to the functions. The style I recommend is to always typedef a function type, not a pointer type, since hiding pointers behind typedef is error-prone and hard to read. And so:
typedef coffee_result_t coffee_func_t (void);
Notably these functions will take no parameters. Because in this simple case there is no reasonable information that the caller could pass to the state machine from the outside world. Rather, it is expected to handle things like button scanning and bean grinding internally. Since this is a single process system with a minimum of interrupts, any information about on-going processes can be shared internally between states with static variables in the coffee_states.c file. What goes on inside the states isn't really the caller's business. The scan buttons state might for example check a cyclic keyboard polling timer that also handles debouncing etc - none but that state needs to access or know about that timer. If the code gets complex, we might even put each state in an individual module of its own.
(Rule of thumb: when you are getting past 1k line of code or so, start considering if this would be better off split across several files.)
The state machine will need some manner of init/constructor function to initialize all such internal variables, but I left that out of the state machine and this example to keep things simple. Though we could have included it as the first state, never to be called again. It might also be very handy to have such an initial state that does get called again and resets all variables, particularly for safety-related programs. But lets keep things simple for now.
As for the states themselves, they could be declared like this:
coffee_result_t coffee_scan_buttons (void);
coffee_result_t coffee_grind_beans (void);
coffee_result_t coffee_mix_water (void);
coffee_result_t coffee_pour (void);
coffee_result_t coffee_maintenance (void);
That's actually the very same names as the previous enum but lower case. It is obviously best not to give the same thing multiple different names. These function declarations together with the enums will get posted in the coffee_states.h, since it is all public and to be used by the caller.
Defining the state machine itself
The declaration of the actual state machine then happens in main.c or equivalent. The function typedef allows us to define the state machine as an array of function pointers. This format is convenient since it gives unison function call syntax with a minimum of overhead, whereas something like a big switch might get verbose, complex and full of code repetition. With an array we can also ensure integrity and check that the array is of the expected size, which isn't really possible with a switch. Finally, it will also allow us to keep main minimal and neat.
In main.c, we would declare an array like this:
static coffee_func_t*const state_machine [] =
{
[COFFEE_SCAN_BUTTONS] = coffee_scan_buttons,
[COFFEE_GRIND_BEANS] = coffee_grind_beans,
[COFFEE_MIX_WATER] = coffee_mix_water,
[COFFEE_POUR] = coffee_pour,
[COFFEE_MAINTENANCE] = coffee_maintenance,
};
This declares an array of function pointers where we left the array size unspecified on purpose.
The peculiar const on the right-hand side of the pointer declaration is important. As you may know, const type* is a pointer to read-only data, whereas type* const is a read-only pointer to data. So this states that this is a table of read-only pointers, that are not allowed to be re-assigned elsewhere in run-time and that they should get allocated in flash memory and not RAM. (Had the const been to the left, it would have meant "pointer to read-only function" and that doesn't even make sense in C, since functions don't have qualifiers and are always read-only.)
I used (C99) designated initializers to ensure that the enum is coupled with each corresponding function. This prevents maintenance hiccups if we would later add a state in the middle somewhere and mix up the order. The & in front of the functions is optional in this case, it would just be "syntactic sugar" with no particular pros/cons. The function typedef ensures type safety - we will not be able to add a function with a type that doesn't match.
Now we could have declared this array as state_machine [COFFEE_STATES_N] since we really ought to have exactly that many states. However, a C compiler will only check if a fixed-size array is given too many items during initialization, it will not check if it contains too few. Rather it will fill in those silently and set them to "all zeroes". So if we used this style and forget a state, it would pass compilation silently. Instead we use state_machine [] and then check the size explicitly at compile-time:
static_assert(sizeof state_machine/sizeof *state_machine == COFFEE_STATES_N,
"coffee_states_t and state_machine does not match 1 to 1");
sizeof array / sizeof *array ought to be familiar as the way to get the number of items in an array at compile time. So now we have ensured that the array contains exactly COFFEE_STATES_N states; no more, no less. static_assert as seen as above requires either C23 or #include <assert.h> (C11/C17). Otherwise in C11/C17, _Static_assert will work too. (In older versions of C you would have to cook up your own static assert, but that's a story for another time.)
Overall, the function pointer table in flash with designated initializers and static assert gives us much greater integrity than plain arrays, switch statements or whatever else we might otherwise have used. Not only have we ensured the size and order, we have also coupled the enum with the functions.
Caller-side implementation
The caller-side (main.c etc) turns out as something like this:
int main()
{
static coffee_state_t state = COFFEE_SCAN_BUTTONS;
coffee_result_t result;
for(;;)
{
result = state_machine[state]();
state = evaluate_result(state, result);
}
}
(static coffee_state_t state since we usually want to keep critical variables away from the stack.)
And that's all. What's important here is that we have a function evaluate_result and that one is the only place in the program where states are allowed to change. Specifically, the state changes when the function returns. With this design, the state machine itself doesn't even have the ability to change states.
If we want, we could integrate a top-level error handler inside evaluate_result. Or we could create one as a separate function only getting called in case of actual errors.
Now in the evaluate_result function we could actually use a switch or get verbose, the function is just going to be a lot of state and result checks no matter what we do. But with this design, we have separated the application logic from the state machine logic and error handling, so that it doesn't all sit together as a piece of unreadable, complex goo.
The function might look like this:
static coffee_state_t evaluate_result (coffee_state_t current_state,
coffee_result_t result)
{
// stay in the same state as default behavior:
coffee_state_t next_state = current_state;
switch(current_state)
{
case COFFEE_SCAN_BUTTONS:
if (result == COFFEE_OK)
{
next_state = COFFEE_GRIND_BEANS;
}
else
{
/* otherwise if idle, remain in the same state */
}
break;
case COFFEE_GRIND_BEANS:
if (result == COFFEE_NO_BEANS)
{
next_state = COFFEE_MAINTENANCE;
error_handler(COFFEE_NO_BEANS);
}
else if (result == COFFEE_OK)
{
next_state = COFFEE_MIX_WATER;
}
else // should never happen
{
error_handler(COFFEE_UNEXPECTED);
}
break;
... // and so on
In each specific case there's a number of checks and we may change the state there, preferably always at the top of each such if compound statement. Here I also chose to integrate an error handler call with the function - it could have been separated too if we prefer that. The error handler might in turn evaluate certain errors differently: out of beans means we have to switch to the maintenance state and wait for the user to refill beans: this is an expected execution path and so the program should continue to run from there, once the beans are refilled. Maybe a more sensible coffee machine design would have been to check if there are beans from the COFFEE_SCAN_BUTTONS state before pressing a button, but that's application details.
Suppose there are more critical errors like wrong temperature measured. This is maybe a safety-critical error even, which would require that the machine puts itself out of order. (During requirements gathering, we would have to identify any safety hazards through FMEA or similar methods.)
I also wrote a lot defensive programming to catch scenarios where an enum has a value that it in theory should never have. Maybe RAM was getting corrupted by cosmic rays or EMI some might say... But far more likely we end up in 'unexpected' execution paths when there is memory corruption due to bugs, stack overflow or similar problems caused by the software itself. A program that detects bugs inside itself is pretty neat.
The code should be MISRA C compliant at least at a glance.
I made a little executable example of all of this code here: https://godbolt.org/z/fqbeEsrzP That whole code will also get posted at the bottom of this post.
Extras - Increasing program safety further or remake to task scheduler
Now with this design established, we can add additional safety measures. It is mandatory even for the simplest of microcontroller programs to have a watchdog enabled, so at the very least the program ought to look like this:
int main()
{
coffee_result_t result;
for(;;)
{
feed_dog();
result = state_machine[state]();
evaluate_result(result);
}
}
Alternatively we could start a timer before each state and check it after, to clock them. That is potentially useful diagnostic information which could be logged. But that requires non-blocking states, where each state need to check if it is still busy or not. So maybe the states need to have internal state machines in themselves too (really, this is not uncommon).
Actually, if each state is non-blocking and guaranteed to only execute up to a certain amount of time, we have now designed a bare bones RTOS, though without the stack swapping and locking mechanisms. Instead of calling it state machine, we can call it an array of tasks and instead of a decision-making function we can just do task[i++]() and execute each function in sequence.
In a safety-critical application, we could have a clock like that set to a fixed time and if it runs out, we would end up in an interrupt taking us to a safe mode. Similarly, safety-critical applications will often use a "watchdog window" with hardware support for such, including a clock separated from the main system clock, meaning that we have to service the watchdog within a given time window: not too early, not too soon. In that case, we will assign a maximum time slice that each state might execute and then service the watchdog. It might conceptually look like this:
int main()
{
coffee_result_t result;
for(;;)
{
start_timer();
result = state_machine[state]();
evaluate_result(result);
while(timer() < TIME_SLICE_MS)
{}
feed_dog();
}
}
That is, if there's time remaining after executing, we will just "burn it away" busy-waiting. Or if current consumption is important, then perhaps there wouldn't be a busy-wait while loop, but rather we would put the MCU in sleep mode and ensure that we wake up when the time runs out.
When done waiting, we will then service the watchdog, once every 1ms/5ms/10ms or whatever time that's suitable. Overall, safety-critical applications always endorses everything running in cycles. So this is how you can implement a time window watchdog.
Code example
https://godbolt.org/z/fqbeEsrzP
/* coffee_state.h */
typedef enum
{
COFFEE_OK,
COFFEE_IDLE,
COFFEE_NO_BEANS,
COFFEE_NO_WATER,
COFFEE_UNEXPECTED,
} coffee_result_t;
typedef enum
{
COFFEE_SCAN_BUTTONS,
COFFEE_GRIND_BEANS,
COFFEE_MIX_WATER,
COFFEE_POUR,
COFFEE_MAINTENANCE,
COFFEE_STATES_N
} coffee_state_t;
typedef coffee_result_t coffee_func_t (void);
coffee_result_t coffee_scan_buttons (void);
coffee_result_t coffee_grind_beans (void);
coffee_result_t coffee_mix_water (void);
coffee_result_t coffee_pour (void);
coffee_result_t coffee_maintenance (void);
/* main.c */
static coffee_func_t*const state_machine [] =
{
[COFFEE_SCAN_BUTTONS] = coffee_scan_buttons,
[COFFEE_GRIND_BEANS] = coffee_grind_beans,
[COFFEE_MIX_WATER] = coffee_mix_water,
[COFFEE_POUR] = coffee_pour,
[COFFEE_MAINTENANCE] = coffee_maintenance,
};
static_assert(sizeof state_machine/sizeof *state_machine == COFFEE_STATES_N,
"coffee_states_t and state_machine does not match 1 to 1");
static coffee_state_t evaluate_result (coffee_state_t current_state,
coffee_result_t result);
static void error_handler (coffee_result_t error_code);
#include <stdio.h>
int main()
{
static coffee_state_t state = COFFEE_SCAN_BUTTONS;
coffee_result_t result;
for(;;)
{
result = state_machine[state]();
state = evaluate_result(state, result);
}
}
static coffee_state_t evaluate_result (coffee_state_t current_state,
coffee_result_t result)
{
// stay in the same state as default behavior:
coffee_state_t next_state = current_state;
switch(current_state)
{
case COFFEE_SCAN_BUTTONS:
if (result == COFFEE_OK)
{
next_state = COFFEE_GRIND_BEANS;
}
else
{
/* otherwise if idle, remain in the same state */
}
break;
case COFFEE_GRIND_BEANS:
if (result == COFFEE_NO_BEANS)
{
next_state = COFFEE_MAINTENANCE;
error_handler(COFFEE_NO_BEANS);
}
else if (result == COFFEE_OK)
{
next_state = COFFEE_MIX_WATER;
}
else // should never happen
{
error_handler(COFFEE_UNEXPECTED);
}
break;
case COFFEE_MIX_WATER:
{
if(result == COFFEE_NO_WATER)
{
next_state = COFFEE_MAINTENANCE;
error_handler(COFFEE_NO_WATER);
}
else if (result == COFFEE_OK)
{
next_state = COFFEE_POUR;
}
else // should never happen
{
error_handler(COFFEE_UNEXPECTED);
}
break;
}
case COFFEE_POUR:
{
if (result == COFFEE_OK)
{
next_state = COFFEE_SCAN_BUTTONS; // reset state machine
}
else
{
/* otherwise if idle, remain in the same state */
}
break;
}
case COFFEE_MAINTENANCE:
{
if(result == COFFEE_OK) // errors resolved?
{
next_state = COFFEE_SCAN_BUTTONS; // reset state machine
}
else
{
/* otherwise if idle, remain in the same state */
}
break;
}
default: // should never happen
{
error_handler(COFFEE_UNEXPECTED);
}
} // switch(state)
return next_state;
}
static void error_handler (coffee_result_t error_code)
{
// do something meaningful here based on error code
(void)error_code;
}
/* coffee_state.c - whatever these functions actually do */
coffee_result_t coffee_scan_buttons (void) { puts(__func__); return COFFEE_OK; }
coffee_result_t coffee_grind_beans (void) { puts(__func__); return COFFEE_OK; }
coffee_result_t coffee_mix_water (void) { puts(__func__); return COFFEE_OK; }
coffee_result_t coffee_pour (void) { puts(__func__); return COFFEE_OK; }
coffee_result_t coffee_maintenance (void) { puts(__func__); return COFFEE_OK; }
1 comment thread