State Machines¶
Learning Objectives: The student understands how state machines can be used in the design and implementation of embedded programs.
State machines (finite-state machine, FSM) are commonly used in digital technology for implementing sequential logic. In addition, state machines are widely used in computer science as a tool for modelling. In embedded systems, state machines are an excellent way to model the behaviour of software during the design phase and to control and manage the logic of event-driven programs. In this course, state machines are particularly useful when we implement event handling across multiple tasks in SensorTag's RTOS.
In this material, we will not delve deeply into the secrets of state machines (formal representations, etc.), but we will show how they can easily be incorporated into the design and implementation of our program. Professional programmers have development environments and tools at their disposal to create state machines as part of the program code. Some tools even automate programming by generating ready-made code from a state machine description.
State Machine¶
A state machine is a model of a system or process where its functionality is described by states and transitions between them. In a Moore-type state machine, inputs and current state determines which is the next state. The output is determined solely by the current state, and not by the transitions or inputs. This type of state machine is deterministic, meaning that for any given state, the output is fixed regardless of the transitions. A state transition diagram illustrates the possible states of the system, the transitions between them, and the events (inputs) that trigger a transition from one state to another.
In the diagram below, the state machine has two states,
State a
and State b
. The arrows represent the state transitions, which are also associated with their inputs
. Each state might produce one or more outputs
.This simplified representation of a state machine is sufficient for our purposes in this course.
Example of a State Machine¶
Below is the behavior of an embedded program depicted as a state machine. The state machine defines functionalities, transitions, and a global state variable, whose value (= state) changes as a result of events. The program's logic is based on the state variable, so that execution progresses from one phase to another through state transitions triggered by events.
- In the IDLE state, we simply wait for events in an infinite loop.
- Once every second, an event (= timer interrupt) occurs, causing a state transition from IDLE to READ_SENSOR.
- From the READ_SENSOR state, where new sensor data is read, the transition goes to the UPDATE state, where the sensor data is updated and displayed on the device's screen.
- From the UPDATE state, the transition goes back to the waiting state IDLE.
- In the infinite loop, it checks whether messages (events) have been received by the device. If so, a state transition occurs to NEW_MSG.
- In this state, the received message is handled
handle_msg
and a response is sentsend_reply
. - After this, the system returns to the IDLE state.
If you want to emphasize the behaviour, instead of the input that force the change of state, you can use a different approach. In this case the arrows indicate the state and the boxes, the functions executed in each state.
Implementation in C¶
There are four principles in state machine programming:
1. State functionality is placed in tasks.
2. State transitions are handled with assignment operations to the state variable. For this reason, the state variable is a global variable, so its value can be accessed throughout the program!
3. The state variable's value is checked in the task's infinite loop, and the appropriate state transition is made accordingly.
4. There may be several nested state machines in a program. For example, one state machine might be handling a specific RTOS task, while another manages the entire system.
1. State functionality is placed in tasks.
2. State transitions are handled with assignment operations to the state variable. For this reason, the state variable is a global variable, so its value can be accessed throughout the program!
3. The state variable's value is checked in the task's infinite loop, and the appropriate state transition is made accordingly.
4. There may be several nested state machines in a program. For example, one state machine might be handling a specific RTOS task, while another manages the entire system.
Based on these principles, let's take a look at an event-driven implementation of the state machine for the SensorTag, using task-based logic.
// Note! The example below doesn't work directly because IDLE is a reserved word.
// Use a different name for this state.
// State definitions
enum state { IDLE=1, READ_SENSOR, UPDATE, NEW_MSG };
// Global state variable, initialized to the waiting state
enum state myState = IDLE;
// Timer interrupt once every second
Void clkFxn(UArg arg0) {
// Change to the desired state
// Note! The if-statement checks if the state transition is possible!!
// Now, only the transition from IDLE -> READ_SENSOR is allowed
if (myState == IDLE) {
// Transition IDLE -> READ_SENSOR
myState = READ_SENSOR;
}
}
// Communication task
Void commTask(UArg arg0, UArg arg1) {
while (1) {
// The function is_message_waiting checks
// if there are messages in the buffer
// Additionally, only the transition IDLE -> NEW_MSG is allowed
if (is_message_waiting() == TRUE && myState == IDLE) {
// Transition IDLE -> NEW_MSG
myState = NEW_MSG;
// State functionality
handle_message();
send_reply();
// Transition NEW_MSG -> IDLE
myState = IDLE;
}
}
}
// Sensor handling
Void sensorTask(UArg arg0, UArg arg1) {
while (1) {
if (myState == READ_SENSOR) {
// State functionality
read_sensor_values();
// Transition READ_SENSOR -> UPDATE
myState = UPDATE;
}
Task_sleep(..);
}
}
// Display handling
Void displayTask(UArg arg0, UArg arg1) {
while (1) {
if (myState == UPDATE) {
// State functionality
update_screen();
// Transition UPDATE -> IDLE
myState = IDLE;
}
Task_sleep(..);
}
}
Note! The state machine implementation above will not work (intentionally) without modifications on the course's SensorTag device!
In the program, a timer interrupt is set once every second, with its handler being
clkFxn
, which changes the state to READ_SENSOR. Using the state machine, we read the sensor value once per second. Similarly, in the commTask
, we change the state to NEW_MSG if there are messages waiting in the buffer.Notice the crucial point here. With the
if
-statement, we check whether the state change is allowed. Without these checks, unintended state transitions could occur, disrupting the program's operation. Generally, checking the validity of state transitions is a critical part of using state machines in programs!When designing a state machine, it's helpful to organize the states in, for example, increasing numerical order so that state transitions can be checked with comparison operators (less than, etc.) for simplicity. Avoid overly complex
if-else
structures! Another important aspect of improving the code structure is minimizing the number of states. However, we won't go into more detail on this in the course, other than considering whether a state is really necessary in our program. In this example, the UPDATE state isn't strictly necessary, but we use it because we handle screen updates in a separate task. This way, the state variable helps us control the program's logic across different tasks!Another use case for state machines in embedded systems is implementing the logic of a user interface. With a state machine, we can define different functionalities for limited resources (such as the two buttons on a SensorTag) depending on the state of the program. For example, in the MENU state, one button might serve as a power button, while in the GAME state, it could be used for something else. Convenient!
Other FSM: Mealy machine¶
In the Moore machine the output depends, uniquely in the state. However, there are other type of FSM with different appraches. The Mealy-type state machine, the state transition is determined by both the current state and the inputs. During state transitions, actions can also be performed that produce an output. This state machine is also deterministic, but in this case from one state and one input, only one state transition can occur. The following figure represents a Mealy state machine. In general, implementing a Mealy machine produce faster reponse to inputs, providing a more responsive behaviour for certain transitions. However, it can make systems handle with RTOS a bit more complicated. The following diagram represents a Mealy state machine diagram. Observe that the output is included in the transition.
In this case the implementation would be slightly different. Observe, that in this case, the state is not linked to a task, but the transition to the target state is. Observe also that the change of state happens when the output is provided.
// State definitions
enum state { IDLE=1, READ_SENSOR, UPDATE, NEW_MSG };
// Global state variable, initialized to IDLE
enum state myState = IDLE;
bool sensor_ready = FALSE; // Flag for checking if sensor reading should be done
// Timer interrupt once every second
Void clkFxn(UArg arg0) {
// Timer triggers every second, setting sensor_ready flag
sensor_ready = TRUE; // Indicating that the sensor should be polled
}
// Communication task
Void commTask(UArg arg0, UArg arg1) {
while (1) {
if (is_message_waiting() == TRUE && myState == IDLE) {
// Action during transition: handle message and send reply
handle_message();
send_reply();
// Transition IDLE -> NEW_MSG
myState = NEW_MSG;
}
}
}
Void idleTask(UArg arg0, UArg arg1){
if (myState == NEW_MSG || myState == UPDATE){
myState= IDLE;
}
}
// Sensor handling task
Void sensorTask(UArg arg0, UArg arg1) {
while (1) {
if (sensor_ready && myState == IDLE) {
// Reset the sensor_ready flag
sensor_ready = FALSE;
// Action during transition: read sensor values
read_sensor_values();
// Transition IDLE -> READ_SENSOR. The sensor_ready flag mark when timer signals the sensor should be read
myState = READ_SENSOR;
}
Task_sleep(..);
}
}
// Display handling task
Void displayTask(UArg arg0, UArg arg1) {
while (1) {
if (myState == READ_SENSOR) {
// Action for updating the display happens during this transition
update_screen();
// Transition READ_SENSOR -> UPDATE
myState = UPDATE;
}
Task_sleep(..);
}
}
UML discussion is not included this year.
Conclusion¶
State machines will be used in the course's project work.
Give feedback on this content
Comments about this material