State Machine and Cooperative Multitasking Model: Simplify Complex Processes Programming for Microcontroller
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:
|
1 2 3 4 5 |
Initialize(); while(1) { //do all the tasks here } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Task_1() { //define the process_1 here } Task_2() { //define the process_2 here } Task_3() { //define the process_3 here } .. Task_N() { //define the process_n here } Initialize(); while() { Task_1(); Task_2(); Task_3(); .. Task_N(); } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
function_name() { unsigned long time = get_time(); if((time - function_name_last_run) < function_name_run_interval) return; function_name_last_run = time; switch(function_name_state) { case function_name_state_1: { //do the state_1 action here break; } case function_name_state_2: { //do the state_2 action here break; } ... case function_name_state_n: { //do the state_n action here break; } } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
// ledblink cooperative function and its global variables //the global variables: unsigned long ledblink_last_run = millis(); unsigned long ledblink_run_interval = 100; //in milliseconds unsigned ledblink_period_setting = 100; //the global variabel to set the period unsigned ledblink_period_count = 0; enum ledblink_states{ledblink_state_off,ledblink_state_on}; int ledblink_state = ledblink_state_on; #define LEDPin 13 //the function: void ledblink() { unsigned long time = millis(); if((time-ledblink_last_run) < ledblink_run_interval) return; ledblink_last_run=time; switch(ledblink_state) { case ledblink_state_on: { ledblink_period_count = ledblink_period_count + 100; if(ledblink_period_count >= ledblink_period_setting) { ledblink_state = ledblink_state_off; digitalWrite(LEDPin,0); ledblink_period_count = 0; } break; } case ledblink_state_off: { ledblink_period_count = ledblink_period_count + 100; if(ledblink_period_count >= ledblink_period_setting) { ledblink_state = ledblink_state_on; digitalWrite(LEDPin,1); ledblink_period_count = 0; } break; } } } // button scan cooperative function and its global variables //the global variables: unsigned long buttonscan_last_run = millis(); unsigned long buttonscan_run_interval = 10; //in milliseconds enum buttonscan_states{buttonscan_state_wait_press,buttonscan_state_wait_nobounce,buttonscan_state_wait_release}; int buttonscan_state = buttonscan_state_wait_press; int buttonscan_nobounce_counter = 0; #define buttonPin 2 // the function: void buttonscan() { unsigned long time = millis(); if((time-buttonscan_last_run) < buttonscan_run_interval) return; buttonscan_last_run = millis(); switch(buttonscan_state) { case buttonscan_state_wait_press: { if(digitalRead(buttonPin)==0) { buttonscan_state = buttonscan_state_wait_nobounce; buttonscan_nobounce_counter = 0; } break; } case buttonscan_state_wait_nobounce: { if(digitalRead(buttonPin)==0) { buttonscan_nobounce_counter++; if(buttonscan_nobounce_counter >10) { ledblink_period_setting = ledblink_period_setting + 100; if(ledblink_period_setting > 1000) ledblink_period_setting = 100; buttonscan_state = buttonscan_state_wait_release; } } else buttonscan_state = buttonscan_state_wait_press; break; } case buttonscan_state_wait_release: { if(digitalRead(buttonPin)==1) buttonscan_state = buttonscan_state_wait_press; break; } } } void setup() { pinMode(LEDPin, OUTPUT); pinMode(buttonPin, INPUT_PULLUP); } void loop() { ledblink(); buttonscan(); } //end of program |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class statemachine { protected: virtual void run(){}; unsigned long runInterval; unsigned long lastRun; int state; public: statemachine(unsigned long run_interval) //the constructor { runInterval = run_interval; lastRun = millis(); state = 0; } void execute() //the periodically called cooperative function { unsigned long currentMillis = millis(); if((currentMillis - lastRun) < runInterval) return; lastRun = currentMillis; run(); //the protected function that should be implemented by the } virtual void setup(){} }; //end of code |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
class statemachine { protected: virtual void run(){}; unsigned long runInterval; unsigned long lastRun; int state; public: statemachine(unsigned long run_interval) //the constructor { runInterval = run_interval; lastRun = millis(); state = 0; } void execute() //the periodically called cooperative function { unsigned long currentMillis = millis(); if((currentMillis - lastRun) < runInterval) return; lastRun = currentMillis; run(); //the protected function that should be implemented by the } virtual void setup(){} }; #define LEDPin 13 class ledblink:public statemachine { protected: enum states{on,off}; int periodcount; void run() { switch(state) { case on: { periodcount+=100; if(periodcount>=period) { digitalWrite(LEDPin,0); periodcount=0; state = off; } break; } case off: { periodcount+=100; if(periodcount>=period) { digitalWrite(LEDPin,1); periodcount=0; state = on; } break; } } } public: ledblink():statemachine(100){} //set the run interval in the constructor int period; //provide a public variable for external machine interface void setup() { period = 100; periodcount = 0; state = on; pinMode(LEDPin,OUTPUT); digitalWrite(LEDPin,1); } }; ledblink LedBlink; #define buttonPin 2 class buttonscan: public statemachine { protected: enum states{wait_press,wait_nobounce,wait_release}; int nobounce_count; void run() { switch(state) { case wait_press: { if(digitalRead(buttonPin)==0) { state = wait_nobounce; nobounce_count=0; } break; } case wait_nobounce: { if(digitalRead(buttonPin)==0) { nobounce_count++; if(nobounce_count > 10) { LedBlink.period+=100; if(LedBlink.period>=1000) LedBlink.period=100; state = wait_release; } } else state = wait_press; break; } case wait_release: { if(digitalRead(buttonPin)==1) state = wait_press; } } } public: buttonscan():statemachine(10){}; void setup() { nobounce_count = 0; state = wait_press; pinMode(buttonPin,INPUT_PULLUP); } }; buttonscan ButtonScan; void setup() { LedBlink.setup(); ButtonScan.setup(); } void loop() { LedBlink.execute(); ButtonScan.execute(); } //end of program |
References:
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.
Is there any example of such design pattern implementation ? Maybe source project link?
https://fjp.at/design-patterns/state