Click on the blue text above to learn more practical skills in embedded programming. If you find this article helpful, feel free to like + follow.
Introduction
The previously introduced state machine is the Finite State Machine (FSM), and this article will discuss the understanding of Hierarchical State Machines (HSM).
A hierarchical state machine is a model used to describe system behavior and control flow. It divides the system into multiple levels, with each level represented as a state machine. Each state machine describes a specific set of states and the transition rules between those states. Each state machine has its own inputs and outputs and can interact with other state machines, forming the behavior of the entire system.
The design of hierarchical state machines helps to reduce system complexity and better organize the functions and behaviors of the system. In a hierarchical state machine, each state machine is responsible for handling a specific sub-task or function, making the system easier to understand and maintain. In a hierarchical state machine, the upper-level state machine coordinates and controls the behavior of the lower-level state machines. The upper-level state machine can trigger state transitions in the lower-level state machines by sending commands or events, and the lower-level state machines can return their processing results to the upper-level state machine, allowing it to make appropriate decisions.
Differences
Hierarchical State Machines (HSM) and Finite State Machines (FSM) are two different models. Although both are used to describe system behavior and control flow, there are some differences between them.
-
Different Hierarchical Structures: A hierarchical state machine divides the system into multiple levels, each represented as a state machine, with its own inputs and outputs that can interact with other state machines, forming the behavior of the entire system. In contrast, a finite state machine is a single-layer structure that describes the states of the system under specific conditions and the transitions between states.
-
Different Number of States: The number of states in a hierarchical state machine is usually greater than that in a finite state machine. Since each level of the hierarchical state machine has its own set of states, the overall state set of the system is the union of the state sets of each level. A finite state machine has only one state set, resulting in a relatively smaller number of states.
-
Different Transition Rules Between States: In a hierarchical state machine, the transition rules between states can be defined at different levels, with each state machine having its own transition rules. In contrast, the transition rules between states in a finite state machine are usually globally unified.
-
Different Functions: Hierarchical state machines are typically used to describe the behavior and control flow of complex systems, with the design aimed at reducing system complexity and better organizing system functions and behaviors. Finite state machines are usually used to describe simple control flows or algorithms.
In summary, although both hierarchical state machines and finite state machines are models for describing system behavior and control flow, they differ significantly in terms of hierarchical structure, number of states, transition rules between states, and application scenarios.
Example Illustration
Assuming there is a vending machine that needs to dispense the corresponding product based on the button selected by the user. We can use both finite state machines and hierarchical state machines to implement this vending machine.
First, let’s look at how to implement the vending machine using a finite state machine. Suppose we have three products to sell: drinks, candies, and chips, corresponding to buttons A, B, and C. We can define the following states:
Initial State: Idle State
State 1: Waiting for User to Select a Button
State 2: Dispensing State
Based on these states, we can design the state transition rules as follows:
Idle State: If the user presses button A, B, or C, transition to the Waiting for User to Select a Button state.
Waiting for User to Select a Button State: If the user presses button A, transition to Dispensing State 1; if the user presses button B, transition to Dispensing State 2; if the user presses button C, transition to Dispensing State 3.
Dispensing State 1: Dispense the drink and transition to the Idle State.
Dispensing State 2: Dispense the candy and transition to the Idle State.
Dispensing State 3: Dispense the chips and transition to the Idle State.
Flowchart:
Next, let’s look at how to implement the vending machine using a hierarchical state machine. First, we can decompose the vending machine into three levels: product selection layer, payment layer, and dispensing layer. Each level has its own states and transition rules as follows:
Product Selection Layer: Waiting for User to Select a Button State
Payment Layer: Waiting for User to Pay State
Dispensing Layer: Dispensing State
Then, we can further refine the states and transition rules for each level as follows:
Product Selection Layer:
Initial State: Idle State
State 1: Waiting for User to Select a Button
Transition Rule: If the user presses button A, B, or C, transition to the Waiting for User to Pay State and save the selected product.
Payment Layer:
Initial State: Idle State
State 1: Waiting for User to Pay
Transition Rule: If the user completes payment, transition to the Dispensing State and send the dispense command.
Dispensing Layer:
Initial State: Idle State
State 1: Waiting for Dispense Command
State 2: Dispensing
Transition Rule: If the dispense command is received, transition to the Dispensing State and perform the dispense operation; if the dispense operation is complete, transition to the Idle State.
Flowchart:
It is important to note that both finite state machines and hierarchical state machines can be used in the design of vending machines. The choice of which method to use depends on specific requirements and complexity. If the system is relatively simple, a finite state machine can be used. If it is necessary to manage multiple subsystems, handle multiple events, and states, a hierarchical state machine should be considered.
The most important thing in practical applications is to correctly design the state transition logic and event handling functions for hierarchical state machines. If the state transition logic is incorrect, it may cause the state machine to fail to respond correctly to events; if the event handling functions are incorrect, it may cause the state machine to fail to handle events correctly. Therefore, when designing hierarchical state machines, it is necessary to carefully consider the logic of state transitions and event handling and conduct sufficient testing and validation.
Code Reference
Finite State Machine
The finite state machine can use switch/case or if/else statements to implement state transitions and perform corresponding operations during each state transition.
#include <stdio.h>
#include <stdbool.h>
enum State
{
ST_IDLE,
ST_WAIT_SELECT,
ST_WAIT_PAY,
ST_DISPENSE
};
enum Button
{
BTN_NONE,
BTN_A,
BTN_B,
BTN_C
};
enum State current_state = ST_IDLE;
enum Button current_button = BTN_NONE;
void update_fsm(enum Button button)
{
switch (current_state)
{
case ST_IDLE:
if (button != BTN_NONE)
{
current_button = button;
current_state = ST_WAIT_SELECT;
printf("Product Selected: %c\n", button);
}
break;
case ST_WAIT_SELECT:
if (button == BTN_NONE)
{
current_state = ST_WAIT_PAY;
printf("Waiting for Payment...\n");
}
break;
case ST_WAIT_PAY:
if (button == BTN_NONE)
{
current_state = ST_DISPENSE;
printf("Dispensing...\n");
}
break;
case ST_DISPENSE:
if (button == BTN_NONE)
{
current_state = ST_IDLE;
printf("Sale Completed\n");
}
break;
}
}
int main()
{
update_fsm(BTN_NONE);
update_fsm(BTN_A);
update_fsm(BTN_NONE);
update_fsm(BTN_NONE);
update_fsm(BTN_NONE);
update_fsm(BTN_NONE);
return 0;
}Hierarchical State Machine
In a hierarchical state machine, due to its complexity, simply using switch/case or if/else statements is no longer suitable for transitioning between different state machines and their sub-states. The best way is to use a table-driven approach, defining each state machine and its sub-states in an array table, along with callback functions to handle each state machine and its sub-states, improving the system’s maintainability and extensibility.
Due to the complexity of implementation, the following code is for reference only and does not provide a complete implementation.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// State machine state enumeration
typedef enum {
STATE_IDLE,
STATE_WAITING_FOR_COIN,
STATE_WAITING_FOR_SELECTION,
STATE_DISPENSING,
STATE_COUNT
} state_t;
// Event enumeration
typedef enum {
EVENT_INSERT_COIN,
EVENT_MAKE_SELECTION,
EVENT_DISPENSE,
EVENT_COUNT
} event_t;
// State transition condition function type definition
typedef bool (*condition_func_t)(void);
// State machine state structure definition
typedef struct {
void (*enter_func)(void); // Enter state function
void (*exit_func)(void); // Exit state function
void (*poll_func)(void); // Event polling handling function
condition_func_t (*cond_func)(void); // Transition condition function
} state_info_t;
// State transition table
static const int transition_table[STATE_COUNT][EVENT_COUNT] = {
// EVENT_INSERT_COIN EVENT_MAKE_SELECTION EVENT_DISPENSE
{ STATE_WAITING_FOR_COIN, STATE_IDLE, STATE_IDLE }, // STATE_IDLE
{ STATE_WAITING_FOR_COIN, STATE_WAITING_FOR_SELECTION, STATE_IDLE }, // STATE_WAITING_FOR_COIN
{ STATE_WAITING_FOR_COIN, STATE_WAITING_FOR_SELECTION, STATE_DISPENSING }, // STATE_WAITING_FOR_SELECTION
{ STATE_WAITING_FOR_COIN, STATE_WAITING_FOR_SELECTION, STATE_IDLE } // STATE_DISPENSING
};
// State machine state array
static const state_info_t state_table[STATE_COUNT] = {
// Enter state function Exit state function Event polling handling function Transition condition function
{ NULL, NULL, NULL, NULL }, // STATE_IDLE
{ wait_for_coin_enter, wait_for_coin_exit, wait_for_coin_poll, wait_for_coin }, // STATE_WAITING_FOR_COIN
{ wait_for_select_enter, wait_for_select_exit, wait_for_select_poll, waiting_for_select }, // STATE_WAITING_FOR_SELECTION
{ dispensing_enter, dispensing_exit, dispensing_poll, dispensing } // STATE_DISPENSING
};
// Current state
static state_t current_state = STATE_IDLE;