I am Lao Wen, an embedded engineer who loves learning.
Follow me, and let's become better together!The state machine pattern is a behavioral pattern that effectively implements state transitions through polymorphism. Unfortunately, in embedded environments, we often have to write pure C code, and we also need to consider reentrancy and multitasking requests, which makes implementation quite challenging.
Recently, while looking at an open-source system, I saw 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 needs to 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;} Transition, * pTransition;Then, according to the transition relationships shown in the figure, we define three transitions and one trap transition:
// (s1, c1, s2, a1)Transition t1 = { STATE_2, action_1};
// (s2, c2, s3, a2)Transition t2 = { STATE_3, action_2};
// (s3, c1, s2, a3)Transition t3 = { STATE_2, action_3};
// (s, c, trap, a1)Transition 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");}Then we define the transition table, which can express the transition relationships mentioned above.
pTransition 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){ pTransition 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, other tasks may request a transition, which can lead to data inconsistency issues.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 has become uncertain, which is unacceptable.Therefore, we need to redesign the state machine, adding a “in transaction” 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; pTransition 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
-END-
Previous Recommendations: Click the image to read.
I’ve dived in, got a board, and continue to push myself!
[Technical Sharing] What is “B-code synchronization”? Which embedded heterogeneous multicore processors can achieve this function?
It’s really annoying! This kind of embedded C language bug is truly hard to guard against!