ALLPCB
Overview
The state machine pattern is a behavioral pattern. Implementing state transitions via polymorphism is effective, but in embedded environments one often must use plain C and handle reentrancy and concurrent task requests. The following presents a C-based approach to implementing a state machine suitable for such constraints.
Concepts
A state machine records transitions from the start time to the present and, based on current input, determines the next state. This implies the state machine must store the current state, obtain inputs (here called transition conditions), and perform corresponding actions.
In the diagram above, {s1, s2, s3} are states. An arrow labeled c1/a1 from s1 to s2 means: when in s1 and input is c1, transition to s2 and perform action a1.
If a state receives an unrecognized input, it should default to a trap state. In the trap state, no input allows exit.
State and Condition Definitions
Define the states and conditions. In embedded systems, storage is limited, so these are defined as macros for compactness. An O(1) transition table is used to avoid timing unpredictability and to represent state transitions directly.
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 1
Transition Type and Entries
Define the transition type and actions. Action functions are application-defined; here an example prints a message.
typedef void (*ActionType)(State state, Condition condition);
typedef struct
{
State next;
ActionType action;
} Trasition, * pTrasition;
void action_1(State state, Condition condition)
{
printf("Action 1 triggered.\n");
}
Define transition instances corresponding to the diagram:
// (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, a_trap)
Trasition tt = {
STATE_TRAP,
action_trap
};
Transition Table
The transition table maps current state and condition to the corresponding transition entry.
pTrasition transition_table[STATES][CONDITIONS] = {
/* c1, c2*/
/* s1 */&t1, &tt,
/* s2 */&tt, &t2,
/* s3 */&t3, &tt,
/* st */&tt, &tt,
};
Basic State Machine
A simple state machine stores only the current state. If concurrent task requests are not a concern, the step function applies a condition to the current state and performs the transition.
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;
}
Handling Concurrency and Reentrancy
If a transition is in progress and another task requests a transition, inconsistent state may occur. For example, task1 performs (s1, c1, a1 -> s2) and is preempted during a1; task2 then sees the still-stale state s1 and processes c2, which may lead to the trap state instead of the intended sequence. To avoid this, the state machine is redesigned to include an "in transaction" flag and a queue for storing incoming conditions.
#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;
}
