The state machine pattern is a behavioral pattern that effectively implements different state transition behaviors through polymorphism. Unfortunately, in embedded environments, it is often necessary 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.
As shown in the figure above, {s1, s2, s3} are states, and the arrows c1/a1 indicate that when in state s1 and the input is c1, it transitions to s2 and performs action a1. The bottom shows a set of inputs, and the state machine should respond as follows:
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 the above 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, 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 plus 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 to be defined by the user; here, we only define an output statement.
void action_1(State state, Condition condition){printf("Action 1 triggered.\n");}Finally, define the transition table:
pTransition transition_table[STATES][CONDITIONS] = {/* c1, c2*//* s1 */&t1, &tt,/* s2 */&tt, &t2,/* s3 */&t3, &tt,/* st */&tt, &tt,};This expresses the transition relationships mentioned above. Finally, 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, if other tasks request a transition, data inconsistency may occur. 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 still 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 “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; 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