State Machine and Cooperative Multitasking Model: Simplify Complex Processes Programming for Microcontroller

State Machine Illustration
State Machine Illustration

Introduction: Microcontroller Software Design for Complex Processes

Designing a software for complex tasks or processes will be easier if we organize the whole tasks into smaller functional tasks, where the tasks communicate each-other through common variables. For a functional task, a concept of state machine has been established for defining and describing the process details, which could ease the implementation of the program coding. To manage multiple tasks, a concept of cooperative multitasking has been established as well. The concept of this multitasking system has been developed many years in the operating system research area, and will applied here for managing tasks in a microcontroller program.

State Machine

State machine, also called a finite-state machine (FSM) or a finite-state automaton, is a mathematical model of computation used to design a computer programs or a sequential logic circuits. It can be viewed as an abstraction of a machine that has many states inside. See reference [1] for more details on this subject. A state can be seen as a label or a flag of a specific process, and the machine can only have one active state at a time, means that a machine can do only one specific process at a time. An abstraction of a state machine contains the detail actions of all its states, and an action of a state might change the active (current ) state to direct what to do in the next action. The decision of what the next state is, can be decided based on input reading (affected by external environment) or common variable reading (shared with and affected by other state machine).

Cooperative Multi-tasking

For managing multiple tasks, cooperative multitasking model is probably the simplest model of multitasking system. From the reference [2]:

Cooperative multitasking, also known ass non-preemptive multitasking, is a style of computer multitasking in which the operating system never initiates a context switch from a running process to another process. Instead, processes voluntarily release control periodically or when idle in order to enable multiple applications to be run simultaneously. This type of multitasking is called “cooperative” because all programs must cooperate for the entire scheduling scheme to work.

In a real operating system, a context switching involves popping and pushing the internal processor’s registers, flags, and program counter from and into stacks.

Implementing Cooperative Multi-tasking in Microcontroller Program

While in a real operating system a task or a program is a routine that should be loaded from executable files, here the tasks are implemented as special routines/functions inside a single microcontroller program. A microcontroller program is normally an infinite loop which looks like the following:

When the program is relatively simple, we can easily write all the tasks inside one infinite loop since we can memorize and keep the track of the program flow and the states in our mind. As the handled process getting more complex, it is easier if we manage the program by dividing them to smaller tasks like the following:

Now the main infinite loop serve as a function of task scheduler, where the control is returned each time the called function returns.  The functions Task_1, Task_2, .., Task_N is special functions, let’s call it a “cooperative functions“, are designed with some requirements:

  • Each of the functions Task_i represents an independent state machine, which communicates with other tasks/machines/functions through global variables.
  • Each of the functions Task_i is designed to be called periodically to implement a process/task which is normally implemented as a single infinite loop.
  • The execution time of the function call te_i (a time period from calling the function until it returns) of each functions Task_i is designed to be as fast as possible, and is allowed to have a variable execution period  with the maximum value te_max_i.
  • The total maximum execution time of all functions (te_max_1 + te_max_2 + .. + te_max_N) should be acceptable by all of each functions.

With the above requirements, now the concept of cooperative multitasking is applicable in a simple way. The simplicity of the programming is achieved by converting infinite loop processes into a periodically called functions (which represent a state machine).

Writing A Cooperative Function: Converting A Single Loop Process into State Machine Model

If we organize a complex task into smaller functional independent tasks, we will find many individual tasks are basically an infinite loop in nature. For example, in case of designing a variable-rate LED blinking with a button to adjust its rate, the separation of LED the blinking task and the button scanning will lead into two infinite loops: an infinite loop of blinking the LED and an infinite loop of the key switch scanning. This two infinite loops should be converted into a cooperative functions that implement state machine models.  Considering the requirements of a cooperative function, it can be implemented in many ways, but it could be easier if we follow a simple but consistent template or framework. Here a general template for cooperative function is proposed:

The function get_time() can be implemented in many ways depending on the employed microcontroller system. In Arduino, the function can be implemented with millis() function, which return the program’s running time since the Arduino board is started. The millis() function will overflow in about 50 days (reference [3]), but according to the characteristic of an unsigned integer difference/subtraction operation, the difference measurement will still be valid although the reading of the starting event is close to the overflow time and the ending event is read after overflow.  For simpler example, if we use a 8 bit timer/counter which is incremented every millisecond, the maximum differential measurement will be 255 milliseconds. As long as the measured event spans not more than 255 milliseconds, the measurement will be valid no matter it overflows or not. In the unsigned integer arithmetic,  it applies that (for example) 15-0 = 14-255. The first case is started at 0 and finished at 15, while the second case is started at 255 and finished at 14 (rolling back at overflow). Any regular single loop process can be converted into a cooperative function by following simple rules:

  • Select the longest acceptable interval that the state will be evaluated and the action (the ‘case statement’) will be executed. This interval value is assigned to the function_name_run_interval variable, so let’s call it a “run interval”. For example, if the function implements a fixed rate LED blink  with 1 second ON and 1 second OFF repeatedly then the longest acceptable run interval is 1 second. Another example, a same case but with a variable LED blinking period (adjustable via push button input) between 1 second and 2 second with 100 milliseconds steps then the longest acceptable run interval is 100 millisecond.
  • Convert all delay function into a “wait state” by setting up a specific state and return from the function. All delay function inside any cooperative function shouldn’t make any shorter delay than the run interval. A wait state with a same period of run interval shouldn’t be implemented as a wait state, all it has to do is just changing the state to the next state and return. So, we can say that a wait state action contains an action of counting or measuring the time laps until reaching some amount before switching the state to the next state.
  • If there is a long computation sequence that cause the maximum execution time of the cooperative function call becomes unacceptable  by the whole system then divide the sequence into multiple states. It will reduce the maximum execution time of the function call since the principle is that the function will return every time one state action is executed (implemented using ‘break’ on each ‘case’ statements).

Coding Example: 1 LED and 1 Button

For better understanding, lets try to code a simple problem: an Arduino board with 1 LED and 1 button. The LED should blink at an adjustable period from 0.1 to 1 second (using same periods for both on- and off-state). The button should be used to set the blinking rate,  where pressing the button would increment the period by 100 milliseconds, rolling back to 100 milliseconds when pressing the button after 1000 milliseconds period  is set. Here is the program code:

Object Oriented (Class) Implementation in Arduino

We can see in the above coding example that many identifiers are written in a format of function_name_  prefix to avoid conflicting identifiers. As the number of state machines inside a program increases, the identifiers naming with long prefixes could be confusing and need more and more efforts to type and to manage them in mind. Fortunately Arduino platform is implemented in C++ that has good object oriented features. Here a “statemachine” class is created as follows:

The cooperative function is implemented in the execute() function of the class. This function is placed in the public member area since it will be called by the main microcontroller loop (which serve the task scheduler functionality). To simplify the coding, the core of the state machine function, i.e. the switch(state) code block is isolated inside the run() function. The run() function is implemented as a protected virtual function, which is called by the execute() function. A real state machine should be coded by deriving a class from the statemachine class and  implements its custom run(), setup(), and constructor functions. Add some variables or functions in the public member area if they are used as the machine’s interface (to communicate with other machines), and keep them in the protected area if not. The private area is not used here for the shake of simplicity since run() function must use the protected area, so it’s simpler to place all non-public functions in one place.  Here is the complete code example:

References:

  1. Finite-state machine (FSM), https://en.wikipedia.org/wiki/Finite-state_machine
  2. Cooperative Multi-tasking, https://en.wikipedia.org/wiki/Cooperative_multitasking
  3. Arduino programming library reference for millis function, https://www.arduino.cc/en/Reference/Millis

3 comments

  • Alan Amaral

    I’m sorry, but using switch statements for anything other than a trivial state machine in C++ is NOT the way to go. You end up with unreadable and unmaintainable code this way.

    If you’re going to implement a state machine in C++, or even in C, a much better way to go is to use a state pattern, where each state is represented by an object which inherits from a base “state” class, and each input to the state machine is a member function defined in the base state class.

    Check out “Head First Design Patterns” for more information.

Leave a Reply

Your email address will not be published. Required fields are marked *


− 6 = one