Embedded multitasking with small MCUs: Part 1 – State Machine Constructs

Control systems that manage electrical or mechanical systems must
often be able to generate, or respond to, sequential events in the
system. This ability to use time as part of the driver equation is in
fact one of the important abilities of a microcontroller that makes it
such a good control for electrical and mechanical systems. However,
implementing multiple sequences can become long and involved if a
linear coding style is used.

A simple construct, called a state machine, simplifies
the
task of generating a sequence by breaking the sequence into a series of
steps and then executing them sequentially. While this sounds like an
arbitrary definition of a linear piece of code, the difference is that
the individual sections, or steps in the sequence, are encoded within a
SWITCH/CASE statement.

This breaks the sequence into logical units that
can be easily recognized in the software listing and, more importantly,
it allows other functions to be performed between the individual steps.
It does this by only executing one step each time it is called.
Repeatedly calling the state machine results in the execution of each
step in the sequence.

To retain the state machine's place in the
sequence, a storage variable is defined that determines which step in
the sequence is to be executed next. This variable is referred to as
the state variable, and it is used in
the SWITCH/CASE
statement to determine which step, or state, in the state machine is to
be executed when the state machine is called.

SiC Wafer Cutting Speed Up to 100 Times Faster than Dicing 

By Mitsuboshi Diamond Industries  07.08.2024

Revolutionary Solutions for Enhancing the Efficiency of Robotic Arms: YMIN Capacitor Applications

By Shanghai Yongming Electronic Co.,Ltd  07.08.2024

Environmental Protection and Efficiency Combined: YMIN’s Supercapacitors SDS/SLX Series Revolutionize the Electronic Pen Market

By Shanghai Yongming Electronic Co.,Ltd  07.01.2024

For this system to work, the state variable must be incremented at
the completion of each state. However, it is also true that the
sequence of states may need to change due to changes in the condition
of the system. Given that the state variable determines which state is
executed, it follows that to change the sequence of states, one must
simply load the state variable with a new value corresponding with the
new direction the sequence must go. As we will see in this book, this
simple construct is very powerful, and is in fact the basis for
multitasking.

So, the short definition of a state machine is a collection of steps
(states) selected for execution based on the value in a state variable.
Further, manipulation of the value in the state variable allows the
state machine to emulate all the conditional statements previously
presented in this chapter.

One of the advantages of the state machine-based design is that it
allows the easy generation of a sequence of events. Another advantage
of state machine-based design is its ability to recognize a sequence of
events. It does this by utilizing the conditional change of the state
variable, much as described in the previous paragraph. The only
difference is that the state variable does not normally change its
value, unless a specific event is detected. As an analogy, consider a
combination lock: to open the lock, the numbers have to be entered in a
specific sequence such as 5, 8, 3, 2. If the numbers were entered 2, 3,
5, 8, the lock would not open, so the combination is not only the
numbers but their order. If we were to create a state machine to
recognize this sequence, it would look something like the following:

State = 0;
SWITCH (State)
{
CASE 0: IF (in_key()==5) THEN state = 1;
Break;
CASE 1: IF (in_key()==8) THEN State = 2;
Else State = 0;
Break;
CASE 2: IF (in_key()==3) THEN State = 3;
Else State = 0;
Break;
CASE 3: IF (in_key()==2) THEN UNLOCK();
Else State = 0;
Break;
}

Code Snippet 2.16

Provided that the values returned by in_key() are in the order of 8,
5, 3, 2, the state variable will step from 0 to 3 and the function
UNLOCK() will be called. The state variable is only loaded with the
value of the next state when the right value is received in the right
state. If any of the values are out of sequence, even though they may
be valid for another state, the state variable will reset to 0, and the
state machine will start over. In this way, the state machine will step
through its sequence only if the values are received in the same
sequence as the states in the state machine are designed to accept.

So, state machines can be programmed to recognize a sequence of
events, and they can be programmed to generate a sequence of events.
Both rely on the history of the previous states and the programmable
nature of the state-to-state transitions.

Implementing a state machine is just a matter of:

1. Creating a state
variable.
2. Defining a series of
states.
3 . Decoding the state
variable to access the states.
4. Tying actions to the
states.
5. Defining the sequence of
the states, and any conditions that change
the sequence.

For example, consider a state machine designed to make peanut and
jelly sandwiches. The sequence of events is:

1. Get two slices of bread.
2. Open peanut butter jar.
3 . Scoop out peanut butter.
4. Smear on first slice of
bread.
5. Open jelly jar.
6. Scoop out jelly.
7. Smear on second slice of
bread.
8. Invert second slice of
bread.
9. Put second slice on first slice of bread.
10. Eat.

OK, the first thing to do is create a state variable; let's call it
PBJ. It has a range of values from 1 to 10, and it probably defines as
a CHAR. Next, we have to define the sequence of steps in the process,
and create a means to decode the state variable.

If we take each of these instructions and build them into a CASE
statement to handle decoding the state variable, then all
it
needs is
the appropriate updates to the state variable and the state machine is
complete.

SWITCH(PBJ)
{
case 1: Get two slices.
PBJ = 2
break
case 2: Open peanut butter jar.
PBJ = 3
break
case 3: Scoop out peanut butter.
PBJ = 4
break
case 4: Smear on first slice of bread.
PBJ = 5
break
case 5: Open jelly jar.
PBJ = 6
break
case 6: Scoop out jelly.
PBJ = 7
break
case 7: Smear on second slice of bread.
PBJ = 8
break
case 8: Invert second slice of bread.
PBJ = 9
break
case 9: Put second slice on first slice of bread.
PBJ = 10
break
case 10: Eat
break
Default: break
}

Algorithm 2.3

The calling routine then simply calls the subroutine 10 times and
the result is an eaten peanut butter and jelly sandwich.

Why go to all this trouble? Wouldn't it be simpler and easier to
just write it as one long function? Well, yes, the routine could be
done as one long sequence with the appropriate delays and timing. But
this format has a couple of limitations. One, making a PB and J
sandwich would be all the microcontroller could do during the process.
And, two, making one kind of a PB and J sandwich would be all the
routine would be capable of doing. There is an important distinction in
those two sentences; the first states that the microcontroller would
only be able to perform one task, no multitasking, and the second
states that all the program would be capable of would be one specific
kind of PB and J sandwich, no variations.

Breaking the sequence up into a state machine means we can put other
functions between the calls to the state machine. The other calls could
cover housekeeping details such as monitoring a serial port, checking a
timer, or polling a keyboard. Breaking the sequence up into a state
machine also means we can use the same routine to make a peanut butter
only sandwich simply by loading the state variable with state 8,
instead of state 5 at the end of state 4. In fact, if we include other
steps such as pouring milk and getting a cookie, and include some
additional conditional state variable changes, we now have a routine
that can make several different varieties of snacks, not just a PB and
J sandwich.

The power of the state machine construct is not limited to just
variations of a sequence. By controlling its own state variable, the
state machine can become a form of specialized virtual
microcontroller—basically a small, software-based controller with a
programmable instruction set. In fact, the power and flexibility of the
state machine will be the basis for the multitasking system described
later in the book. Before we dive into some of the more advanced
concepts, it is important to understand some of the basics of state
machine operation.

The best place to start is with the three basic types of state
machines: execution-indexed , data-indexed , and the hybrid
state machine. The execution-indexed state machine is
the type of state machine that most people envision when they talk
about a state machine, and it is the type of state machine shown in the
previous examples. It has a CASE statement structure with routine for
each CASE, and a state variable that controls which state is executed
when the state machine is called. A good example of an
Execution-indexed state machine is the PB&J state machine in the
previous example. The function performed by the state machine is
specified by the value held in the state variable.

The other extreme is the data-indexed state machine . It is
probably the least recognized form of a state machine, even though most
designers have created several, because it doesn't use a SWITCH/CASE
statement. Rather, it uses an array variable with the state variable
providing the index into the array. The concept behind a data-indexed
state machine is that the sequence of instructions remains constant,
and the data that is acted upon is controller by the state variable.

A hybrid state machine combines aspects of both the
data-indexed and the execution-indexed to create a state machine with
the ability to vary both its execution and the data it operates on.
This hybrid approach allows the varied execution of the execution
indexed with the variable data aspect of the data-indexed state machine.

We have three different formats, with different advantages and
disadvantages. Execution indexed allows designers to vary the actions
taken in each state, and/or respond to external sequences of events.
Data indexed allows designers to vary the data acted upon in each
state, but keep the execution constant. And, finally, the hybrid
combines both to create a more efficient state machine that requires
both the varied execution of the execution-indexed and the indexed data
capability of the data-indexed state machine. Let's take a closer look
at the three types and their capabilities.

Data-Indexed State Machines
Consider a system that uses an analog-to-digital converter, or ADC, to
monitor multiple sensors. Each sensor has its own channel into the ADC,
its own calibration offset/scaling factors, and its own limits. To
implement these functions using a data-indexed state machine, we start
by assigning a state to each input and creating an array-based storage
for all the values that will be required.

Starting with the data storage, the system will need storage for the
following:

1. Calibration offset and
scaling values.
2. Upper and lower limit
values.
3. The final, calibrated
values.

Using a two-dimensional array ,
we can store the values in the
following format. Assume that S_var
is the state value associated with
a specific ADC channel:

ADC_Data[0][ S_var] variable in the array holding the calibration
offset values
ADC_Data[1][ S_var] variable in the array holding the calibration
scaling values
ADC_Data[2][ S_var] variable in the array holding the upper limit values
ADC_Data[3][ S_var] variable in the array holding the lower limit values
ADC_Data[4][ S_var] variable in the array holding the ADC channel
select command value
ADC_Data[5][ S_var] variable in the array holding the calibrated final
values

The actual code to implement the state machine will look like the
following:

Void ADC(char S_var, boolean alarm)
{
ADC_Data[4][S_var] = (ADC*ADC_Data[1][S_
var])+ADC_Data[0][S_var];
IF (ADC_Data[4][S_var]>ADC_Data[2][S_var]) THEN
Alarm = true;
IF (ADC_Data[4][S_var] Alarm = true;
S_var++;
IF (S_var > max_channel) then S_var = 0;
ADC_control = ADC_Data[5][S_var];
ADC_convert_start = true;
}

Code Snippet 2.17

In the example, the first line converts the raw data value held in
ADC into a calibrated value by multiplying the scaling factor and
adding in the offset. The result is stored into the ADC_Data array.
Lines 2 and 3 perform limit testing against the upper and lower limits
store in the ADC_Data array and set the error variable if there is a
problem. Next, the state variable S_var is incremented, tested against
the maximum number of channels to be polled, and wrapped around if it
has incremented beyond the end. Finally, the configuration data
selecting the next channel is loaded into the ADC control register and
the conversion is initiated—a total of seven lines of code to scan as
many ADC channels as the system needs, including both individual
calibration and range checking.

From the example, it seems that data-indexed state machines are
fairly simple constructs, so how do they justify the lofty name of
state machine? Simple—by exhibiting the ability to change its operation
based on internal and external influences. Consider a variation on the
previous example. If we add another variable to the data array and
place the next state information into that variable, we now have a
state machine that can be reprogrammed “on the fly” to change its
sequence of conversions based on external input.

ADC_Data[6][ S_var] variable in the array
holding the next channel to convert

Void ADC(char S_var, boolean alarm)
{
ADC_Data[4][S_var] = (ADC*ADC_Data[1][S_
var])+ADC_Data[0][S_var];
IF (ADC_Data[4][S_var]>ADC_Data[2][S_var]) THEN
Alarm = true;
IF (ADC_Data[4][S_var] Alarm = true;
S_var = ADC_Data[6][S_var];
ADC_control = ADC_Data[5][S_var];
ADC_convert_start = true;
}

Code Snippet 2.18

Now the sequence of channels is controlled by the array
ADC_Data.  If the system does not require data from a specific
channel, it just reprograms the array to route the state machine around
the unneeded  channel. The state machine could also be built with
two or more next channels, with the actual next channel determined by
whether a fault has occurred, or an external flag is set, or a value
reported by one of the channels has been exceeded.

Don't let the simplicity of the state machine deceive you; there is
power and flexibility in the data-indexed state machine. All that is
required is the imagination to look beyond the simplicity and see the
possibilities.

Execution-Indexed State
Machines
Execution-indexed state machines, as described previously, are often
mistakenly assumed to be little more than a CASE statement with the
appropriate routines inserted for the individual states. While the CASE
statement, or an equivalent machine language construct, is at the heart
of an execution-based state machine, there is a lot more to their
design and a lot more to their capabilities.

For instance, the capability to control its own state variable lends
itself to a wide variety of capabilities that rival normal linear
coding. By selectively incrementing or loading the state variable,
individual states within the state machine can implement:

Sequential execution.
Computed GOTO instructions.
DO/WHILE instructions.
WHILE/DO instructions.
FOR/NEXT instructions.
And even GOSUB/RETURN instructions.

Let's run through some examples to demonstrate some of the
capabilities of the execution-indexed state machine type.

First of all, to implement a sequence of state steps, it is simply a
matter of assigning the value associated with the next state in the
sequence, at the end of each state. For example:

SWITCH(State_var)
{
CASE 0: State_var = 1;
Break;
CASE 1: State_var = 2;
Break;
CASE 2: State_var = 3;
Break;
}

Code Snippet 2.19

Somewhere in each state, the next state is loaded into the state
variable. As a result, each execution of the state machine results in
the execution of the current state's code block and the advancement of
the state variable to the next state. If the states are defined to be
sequential values, the assignment can even be replaced with a simple
increment.

However, there is no requirement that the states be sequential, or
that the state machine must sequence down the case statement on each
successive call to the state machine. It is perfectly valid to have the
state machine step through the case statement in whatever pattern is
convenient, particularly if the pattern of values in the state variable
is convenient for some other function in the system, such as the
sequence of energized windings in a brushless motor. The next state can
even be defined by the values in an array, making the sequence entirely
programmable.

Computed GOTO instructions are just a simple extension of the basic
concept used in sequential execution. The only difference is the
assignment is made from the result of a calculation. For example:

SWITCH(State_var)
{
CASE 0: State_var = 10 * Var_a;
Break;
CASE 10: Function_A;
State_var = 0;
Break;
CASE 20: Function_B;
State_var = 0;
Break;
CASE 30: Function_C
State_var = 0;
Break;
}

Code Snippet 2.20

Based on the value present in Var_a ,
the state machine will execute one of three different states the next
time it is called. This essentially implements a state machine that
cannot only change its sequence of execution based on data, but can
also change its execution to one of several different sequences based
on data.

Another construct that can be implemented is the IF/THEN/ELSE
statement. Based on the result of a comparison in one of the states,
the state machine can step to one of two different states, altering its
sequence. If the comparison in the conditional statement is true, then
the state variable is loaded with the new state value associated with
the THEN part of the IF statement and the next time the state machine
is executed, it will execute the new state. If the comparison results
in a false, then the state variable is loaded with a different value
and the state machine executes the state associated with the ELSE
portion of the IF statement. For example:

SWITCH(State_var)
{
CASE 0: IF (Var_A > Var_B) THEN State_var = 1;
ELSE State_var = 2;
Break;
CASE 1: Var_B = Var_A
State_var = 0;
Break;
CASE 2: Var_A = Var_B
State_var = 0;
Break;
}

Code Snippet 2.21

In the example, whenever the value in Var_A is larger than the value in Var_B , the state machine advances to
state 1 and the value in Var_A
is copied into Var_B . The
state machine then returns to state 0. If the value in Var_B is greater than or equal to Var_A , then Var_B is copied into Var_A , and the state machine returns
to state 0.

Now, having seen both the GOTO and the IF/THEN/ELSE, it is a simple
matter to implement all three iterative statements by simply combining
the GOTO and the IF/THEN/ELSE. For example, a DO/ WHILE iterative
statement would be implemented as follows:

CASE 4: Function;
State_var = 5;
Break;
CASE 5: IF (comparison) THEN State_var = 4;
ELSE State_var = 6;
Break;
CASE 6:

Code Snippet 2.22

In the example, state 4 holds the (DO) function within the loop, and
state 5 holds the (WHILE) comparison. And, a WHILE/DO iterative
statement would be implemented as follows:

CASE 4: IF (comparison) THEN State_var = 5;
ELSE State_var = 6;
Break;
CASE 5: Function;
State_var = 4;
Break;
CASE 6:

Code Snippet 2.23

In this example, state 4 holds the (WHILE) comparison, and state 5
holds the (DO) function within the loop. A FOR/NEXT iterative statement
would be implemented as follows:

CASE 3: Counter = 6;
State_var = 4;
Break;
CASE 4: IF (Counter > 0) THEN State_var = 5;
ELSE State_var = 6;
Break;
CASE 5: Function;
Counter = Counter ” 1;
State_var = 4;
Break;
CASE 6:

In the last example, the variable (Counter) in the FOR/NEXT is
assigned its value in state 3, is compared to 0 in state 4 (FOR), and
is then incremented and looped back in state 5 (NEXT).

These three iterative constructs are all simple combinations of the
GOTO and IF/THEN/ELSE described previously. Building them into a state
machine just required breaking the various parts out into separate
states, and appropriately setting the state variable.

The final construct to examine in an execution-indexed state machine
is the CALL/RETURN. Now, the question arises, why do designers need a
subroutine construct in state machines? What possible use is it? Well,
let's take the example of a state machine that has to generate two
different delays. State machine delays are typically implemented by
repeatedly calling a do-nothing state, and then returning to an active
state. For example, the following is a typical state machine delay:

CASE 3: Counter = 6;
State_var = 4;
Break;
CASE 4: IF (Counter == 0) THEN State_var = 5;
Counter = Counter ” 1;
Break;
CASE 5:

Code Snippet 2.25

This routine will wait in state 4 a total of six times before moving
on to state 5. If we want to create two different delays, or use the
same delay twice, we would have to create two different wait states.
However, if we build the delay as a subroutine state, implementing both
the CALL and RETURN, we can use the same state over and over, saving
program memory. For example:

CASE
3: Counter = 6;
State_var = 20;
Back_var = 4
Break;
| |
| |
CASE 12: Counter = 10;
State_var = 20;
Back_var = 13
Break;
| |
| |
CASE 20: IF (Counter == 0) THEN State_var = Back_var;
Counter = Counter ” 1;
Break;

Code Snippet 2.26

In the example, states 3 and 12 are calling states and state 20 is
the subroutine. Both 3 and 12 loaded the delay counter with the delays
they required, loaded Back_var
with the state immediately following the calling state (return
address), and jumped to the delay state 20 (CALL). State 20 then
delayed the appropriate number of times, and transferred the return
value in Back_var into the
state variable (RETURN). By providing a return state value, and setting
the counter variable before changing state, a simple yet effective
subroutine system was built into a state machine. With a little work
and a small array for the Back_var ,
the subroutine could even call other subroutines.

Hybrid State Machines
Hybrid state machines are a combination of both formats; they have the
CASE structure of an execution-based state machine, as well as the
array-based data structure of a data-indexed state machine. They are
typically used in applications that require the sequential nature of an
execution-based state machine, combined with the ability to handle
multiple data blocks.

A good example of this hybrid requirement is a software-based serial
transmit function. The function must generate a start bit, 8 data bits,
a parity bit and one or more stop bits. The start, parity, and stop
bits have different functionality and implementing them within an
execution- based state machine is simple and straightforward. However,
the transmission of the 8 data bits does not work as well within the
execution based format. It would have to be implemented as eight nearly
identical states, which would be inefficient and a waste of program
memory. So, a second data-driven state machine, embedded in the first
state machine, is needed to handle the 8 data bits being transmitted.
The following is an example of how the hybrid format would be
implemented:

SWITCH(Ex_State_var)
{
CASE 0: // waiting for new character
IF (Data_avail == true) THEN Ex_State_var = 1;
Break;
CASE 1: // begin with a start bit
Output(0);
Ex_State_var = 2;
DI_State_var = 0;
Break;
CASE 2: // sending bits 0-7
If ((Tx_data & (2^DI_State_var))) == 0)
Then Output(0);
Else Output(1);
DI_State_var++;
If (DI_State_var == 8) Then Ex_State_var = 3;
Break;
CASE 3: // Output Parity bit
Output(Parity(Tx_data));
Ex_State_var = 4;
Break;
CASE 4: // Send Stop bit to end
Output(1);
Ex_State_var = 0
}

Code Snippet 2.27

Note that the example has two state variables, Ex_State_var and DI_State_var . Ex_State_var is the state variable
for the execution-indexed section of the state machine, determining
which of the four cases in the Switch statement is executed. DI_State_var is the state variable
for the data-indexed section of the state machine, determining which
bit in the 8-bit data variable is transmitted on each pass through
state 2.  Together the two types of state machine produce a hybrid
state machine that is both simple and efficient.

On a side note, it should be noted that the Ex_State_var and DI_ State_var can be combined into
a single data variable to conserve data memory. However, this is
typically not done due to the extra overhead.

Next, in Part 2: “ The basics
of multitasking in an Embedded MCU environment.“

Author Keith Curtis is principal
applications engineer at Microchip Technology.

Used with the
permission of the publisher, Newnes/Elsevier, this series of two
articles is based on Chapter 2: Basic Embedded Programming Concepts
from “Embedded multitasking with small microcontrollers,” by Keith Curtis.