The state machine pattern is a behavioral pattern that effectively implements different state transitions through polymorphism. Unfortunately, in embedded environments, one often has to write pure C code while also considering reentrancy and multitasking request transitions, making the implementation quite challenging.
Recently, while reviewing an open-source system, I came across an implementation of a state machine and decided to write one myself to share with everyone.
First, let’s analyze what a typical state machine needs to implement.
A state machine stores changes from the start time to the present and decides the next state based on the current input. This means that the state machine must store states, obtain inputs (which we call transition conditions), and respond accordingly.
When a state encounters an unrecognized input, it defaults to a trap state, where no matter what input is encountered, it cannot escape.To express this automaton, we define their states and input types:
typedef int State;typedef int Condition;
#define STATES 3 + 1
#define STATE_1 0
#define STATE_2 1
#define STATE_3 2
#define STATE_TRAP 3
#define CONDITIONS 2
#define CONDITION_1 0
#define CONDITION_2 1In embedded environments, due to limited storage space, we define them all as macros. Additionally, to reduce execution time uncertainty, we use an O(1) jump table to simulate state transitions.First, we define the transition type:
typedef void (*ActionType)(State state, Condition condition);
typedef struct{ State next; ActionType action;} Trasition, * pTrasition;Then, according to the transition relationships shown in the figure, we define three transitions plus one trap transition:
// (s1, c1, s2, a1)Trasition t1 = { STATE_2, action_1};
// (s2, c2, s3, a2)Trasition t2 = { STATE_3, action_2};
// (s3, c1, s2, a3)Trasition t3 = { STATE_2, action_3};
// (s, c, trap, a1)Trasition tt = { STATE_TRAP, action_trap};The actions are defined by the user, and here we only define an output statement.
void action_1(State state, Condition condition){ printf("Action 1 triggered.\n");}Next, we define the transition table, which expresses the transition relationships mentioned above.
pTrasition transition_table[STATES][CONDITIONS] = {/* c1, c2*//* s1 */&t1, &tt,/* s2 */&tt, &t2,/* s3 */&t3, &tt,/* st */&tt, &tt,};Finally, we define the state machine. If we do not consider multitasking requests, the state machine only needs to store the current state. For example:
typedef struct{ State current;} StateMachine, * pStateMachine;
State step(pStateMachine machine, Condition condition){ pTrasition t = transition_table[machine->current][condition]; (*(t->action))(machine->current, condition); machine->current = t->next;return machine->current;}However, considering that when a transition is in progress, if another task requests a transition, it may lead to data inconsistency.For example:task1(s1, c1/a1 –> s2) and task2(s2, c2/a2 –> s3) can successfully reach state s3, but if action a1 is running and task2 preempts the execution, task2 will see the current state as s1, and when s1 encounters c2, it will enter the trap state instead of reaching s3. This means that the state transition becomes uncertain, which is unacceptable.Therefore, we need to redesign the state machine, adding a “transaction in progress” condition and a condition queue to store inputs.The modified code is as follows:
#define E_OK 0#define E_NO_DATA 1#define E_OVERFLOW 2
typedef struct{ Condition queue[QMAX]; int head; int tail; bool overflow;} ConditionQueue, * pConditionQueue;
int push(ConditionQueue * queue, Condition c){ unsigned int flags; Irq_Save(flags); if ((queue->head == queue->tail + 1) || ((queue->head == 0) && (queue->tail == 0))) { queue->overflow = true; Irq_Restore(flags); return E_OVERFLOW; } else { queue->queue[queue->tail] = c; queue->tail = (queue->tail + 1) % QMAX; Irq_Restore(flags); } return E_OK;}
int poll(ConditionQueue * queue, Condition * c){ unsigned int flags; Irq_Save(flags); if (queue->head == queue->tail) { Irq_Restore(flags); return E_NO_DATA; } else { *c = queue->queue[queue->head]; queue->overflow = false; queue->head = (queue->head + 1) % QMAX; Irq_Restore(flags); } return E_OK;}
typedef struct{ State current; bool inTransaction; ConditionQueue queue;} StateMachine, * pStateMachine;
static State __step(pStateMachine machine, Condition condition){ State current = machine -> current; pTrasition t = transition_table[current][condition]; (*(t->action))(current, condition); current = t->next; machine->current = current; return current;}
State step(pStateMachine machine, Condition condition){ Condition next_condition; int status; State current; if (machine->inTransaction) { push(&(machine->queue), condition); return STATE_INTRANSACTION; } else { machine->inTransaction = true; current = __step(machine, condition); status = poll(&(machine->queue), &next_condition); while(status == E_OK) { __step(machine, next_condition); status = poll(&(machine->queue), &next_condition); } machine->inTransaction = false; return current; }}
void initialize(pStateMachine machine, State s){ machine->current = s; machine->inTransaction = false; machine->queue.head = 0; machine->queue.tail = 0; machine->queue.overflow = false;}Source: www.cnblogs.com/autosar/archive/2012/06/22/2558604.html
Copyright belongs to the original author and is for learning reference only.
Finally
The author has collected some embedded learning materials. Reply with 【1024】 in the public account to find the download link!
Recommended Articles Click the blue text to jump
☞ Collection | Comprehensive Programming of Linux Applications
☞ Collection | Learn Some Networking Knowledge
☞ Collection | Handwritten C Language
☞ Collection | Handwritten C++ Language
☞ Collection | Experience Sharing
☞ Collection | From Microcontrollers to Linux
☞ Collection | Power Control Technology
☞ Collection | Essential Mathematics for Embedded Systems
☞ MCU Advanced Collection
☞ Embedded C Language Advanced Collection