Простым примером машины с конечным числом состояний (FSM - Finite State Machine) может быть Китайская гирлянда. Конструктивно она представляет из себя черную коробочку с кнопочкой, два провода для питания (220 В), остальные провода для разноцветных лампочек, которыми управляет готовая программа. Внутри коробочки находится микроконтроллер и сопутствующая обвязка. Мы не будем углубляться в детали схемотехники а сконцентрируемся на различных методиках решения подобных задач и их анализе т.е. на программировании с использованием чистого ANSI C.
Для экспериментов нам понадобиться какой-то тестовый макет, который можно запустить / эмулировать в виртуальной среде (выбор пал на Proteus VSM). Есть простенький микроконтроллер (PIC16F1823), который управляет лампочками (гирляндой) и может менять их яркость с помощью встроенного цифро-аналогового преобразователя ЦАП (в реальном устройстве для этого лучше использовать ШИМ, ЦАП лучше подходит для эмуляции в Proteus VSM). Быстро вникнуть в суть дела можно посмотрев следующее видео:
Начнём с простого - напишем программу для гирлянды с двумя состояниями - в первом светодиоды поочерёдно вспыхивают слева направо, во втором справа налево. В системе два события - нажали кнопочку (NEXT) и внутреннее (недоступно пользователю гирлянды) событие от таймера (TICK). Событие NEXT изменяет состояние:
Операторы switch/case
Прибегнув к помощи условных операторов if / else или switch / case по-старинке задачу решили так:
FSM/Child/src/main.c
#include "main.h"
typedef enum {
LEFT_TO_RIGHT,
RIGHT_TO_LEFT
} State;
/* Global variable to hold current state */
static State currentState = RIGHT_TO_LEFT;
/* Event handlers implementations */
static void onLeftToRightTickImpl() {
nextLeftLed(); // in main.h
}
static void onLeftToRightNextImpl() {
resetLeds(); // in main.h
currentState = RIGHT_TO_LEFT;
}
static void onRightToLeftTickImpl() {
nextRightLed(); // in main.h
}
static void onRightToLeftNextImpl() {
resetLeds(); // in main.h
currentState = LEFT_TO_RIGHT;
}
void main (void) {
initHardware(); // in main.h
for (;;) {
typedef enum {
NEXT,
TICK
} Event;
/* Событие по-умолчанию */
Event eventToFire = TICK;
/* Если нажали кнопку, событие NEXT */
for (unsigned int i = 5000; i; i--) {
if (isNextButtonPressed()) {
eventToFire = NEXT;
break; // Fire NEXT event
}
}
switch (currentState) {
case LEFT_TO_RIGHT :
switch (eventToFire) {
case TICK:
onLeftToRightTickImpl();
break; // TICK
case NEXT:
onLeftToRightNextImpl();
break; // NEXT
}
break; // LEFT_TO_RIGHT
case RIGHT_TO_LEFT :
switch (eventToFire) {
case TICK:
onRightToLeftTickImpl();
break; // TICK
case NEXT:
onRightToLeftNextImpl();
break; // NEXT
}
break; // RIGHT_TO_LEFT
}
}
}
Некоторые детали реализации вынесены в заголовочный файл main.h, который прилагается к исходникам. Для сборки использовался компилятор HI-TECH PICC:
/usr/hitech/picc/9.83/bin/PICC --opt=all --chip=16F1823 --ASMLIST main.c
Что мы можем сказать об этом решении, кроме того, что там много одинаковых слов switch и case ?
-
Представьте себе несколько страниц кода с монолитным оператором
switch/case. Такой код сложно читать и сопровождать. В самихswitch/caseилиif/elseнет ничего плохого - в конце-концов это ключевые слова С. Но когда их очень много в одном месте, с этим нужно бороться. -
Hет удачного разделения между логикой обработки событий машиной с конечным числом состояний и реализацией соответствующих действий. В результате добавление нового состояния требует больших изменений в разных местах.
Табличная альтернатива
Второй способ решения задачи состоит в использовании таблицы переходов:
FSM/Table/Simple/src/main.c
#include "main.h"
typedef enum {
LEFT_TO_RIGHT,
RIGHT_TO_LEFT
} State;
/* Global variable to hold current state */
static State currentState = RIGHT_TO_LEFT;
/* Event handlers implementations */
static void onLeftToRightTickImpl() {
nextLeftLed(); // in main.h
}
static void onLeftToRightNextImpl() {
resetLeds(); // in main.h
currentState = RIGHT_TO_LEFT;
}
static void onRightToLeftTickImpl() {
nextRightLed(); // in main.h
}
static void onRightToLeftNextImpl() {
resetLeds(); // in main.h
currentState = LEFT_TO_RIGHT;
}
void main (void) {
initHardware(); // in main.h
typedef enum {
NEXT,
TICK
} Event;
typedef struct _Transition {
State state;
Event event;
void (*EventFunc)();
} Transition;
const Transition transitionTable[] = {
{LEFT_TO_RIGHT, TICK, onLeftToRightTickImpl},
{LEFT_TO_RIGHT, NEXT, onLeftToRightNextImpl},
{RIGHT_TO_LEFT, TICK, onRightToLeftTickImpl},
{RIGHT_TO_LEFT, NEXT, onRightToLeftNextImpl}
};
for (;;) {
/* Событие по-умолчанию */
Event eventToFire = TICK;
/* Если нажали кнопку, событие NEXT */
for (unsigned int i = 5000; i; i--) {
if (isNextButtonPressed()) {
eventToFire = NEXT;
break; // Fire NEXT event
}
}
/* Обработка события */
int elementsCount =
sizeof(transitionTable) / sizeof(transitionTable[0]);
while (elementsCount--) {
Transition transition = transitionTable[elementsCount];
if (transition.state == currentState &&
transition.event == eventToFire) {
transition.EventFunc();
break; // Функция EventFunc найдена и выполнена!
}
}
}
}
Давайте сравним данное решение с предыдущим:
-
Табличная реализация несколько медленнее - как минимум добавился цикл
while. Для обхода элементов таблицы задействована идиома КОЛИЧЕСТВО ЭЛЕМЕНТОВ МАССИВА КАК РЕЗУЛЬТАТ ДЕЛЕНИЯ, которая уже подробно описывалась ранее. -
Bся логика переходов сконцентрирована в одной таблице. Всё видно, как на ладони. Теперь можно быстрее разобраться / вспомнить, как всё это работает.
-
Добавление нового состояния не требует изменений логики обработки событий машиной с конечным числом состояний. Давайте добавим ещё одно состояние - лампочки плавно меняют яркость:
FSM/Table/Scale/src/main.c
#include "main.h"
typedef enum {
LEFT_TO_RIGHT,
RIGHT_TO_LEFT,
/* Add brightness algoritms States */
RIGHT_LEFT_TO_BRIGHT
} State;
/* Global variable to hold current state */
static State currentState = RIGHT_TO_LEFT;
/* Event handlers implementations */
static void onLeftToRightTickImpl() {
nextLeftLed(); // in main.h
}
static void onLeftToRightNextImpl() {
resetLeds(); // in main.h
currentState = RIGHT_TO_LEFT;
}
static void onRightToLeftTickImpl() {
nextRightLed(); // in main.h
}
/* LEFT_TO_RIGHT ==> RIGHT_LEFT_TO_BRIGHT */
static void onRightToLeftNextImpl() {
resetLeds(); // in main.h
currentState = RIGHT_LEFT_TO_BRIGHT;
}
/* Add brightness handlers */
static void onRightToLeftBrigtTickImpl() {
nextRightBrightLed(); // in main.h
}
static void onRightToLeftBrigtNextImpl() {
resetLeds(); // in main.h
currentState = LEFT_TO_RIGHT;
}
void main (void) {
initHardware(); // in main.h
typedef enum {
NEXT,
TICK
} Event;
typedef struct _Transition {
State state;
Event event;
void (*EventFunc)();
} Transition;
const Transition transitionTable[] = {
{LEFT_TO_RIGHT, TICK, onLeftToRightTickImpl},
{LEFT_TO_RIGHT, NEXT, onLeftToRightNextImpl},
{RIGHT_TO_LEFT, TICK, onRightToLeftTickImpl},
{RIGHT_TO_LEFT, NEXT, onRightToLeftNextImpl},
/* Add brightness algoritms transitions */
{RIGHT_LEFT_TO_BRIGHT, TICK, onRightToLeftBrigtTickImpl},
{RIGHT_LEFT_TO_BRIGHT, NEXT, onRightToLeftBrigtNextImpl}
};
for (;;) {
/* Событие по-умолчанию */
Event eventToFire = TICK;
/* Если нажали кнопку, событие NEXT */
for (unsigned int i = 5000; i; i--) {
if (isNextButtonPressed()) {
eventToFire = NEXT;
break; // Fire NEXT event
}
}
/* Обработка события */
int elementsCount =
sizeof(transitionTable) / sizeof(transitionTable[0]);
while (elementsCount--) {
Transition transition = transitionTable[elementsCount];
if (transition.state == currentState &&
transition.event == eventToFire) {
transition.EventFunc();
break; // Функция EventFunc найдена и выполнена!
}
}
}
}
Несложно заметить, что код в суперцикле for(;;) остался без изменений, т.е. решение с использованием таблиц характеризуется лучшей расширяемостью кода.
Далее или сопрограммы или Quantum Leaps QP и UML statecharts.
Исходники тут.