Журнал РАДИОЛОЦМАН, февраль 2017
Deepti Mani
embedded.com
Конечный автомат (или машина состояний) является одним из наиболее популярных методов проектирования встраиваемых систем. Множество приложений, от простых бытовых приборов до сложных систем связи, основано на событийных конечных автоматах.
Конечный автомат состоит из множества состояний. В любой момент времени система находится в одном состоянии, и событие вызывает определенные действия в этом состоянии, равно как имеет возможность изменения состояния. Событие может наступить вследствие прерывания в системе, сигнала операционной системы реального времени, срабатывания таймера, либо по входному сигналу другого модуля системы.
В этой статье мы рассмотрим различные подходы к реализации конечных автоматов с использованием языка C.
На Рисунке 1 показан пример машины состояний для кофейного автомата. Он имеет три состояния:
- Бездействие,
- Монета опущена и
- Опция выбрана.
Система ожидает действий пользователя и сигналов от дозатора. Также могут быть добавлены дополнительные события, такие как сигнал срабатывания отладочного таймера.
 |
||
| Рисунок 1. | Пример машины состояний для кофейного автомата. | |
Существуют два общих подхода к реализации событийного конечного автомата подобного тому, о котором говорилось выше:
- Использование условных операторов
- Использование таблицы поиска
Использование условных операторов
Это очень простой подход. Для проверки каждого состояния здесь используются операторы switch-case или if-else. В каждое состояние для проверки управляющего события добавляется еще один условный оператор. Затем добавляется обработчик для этой комбинации состояние/событие. Этот порядок можно поменять и сначала проверить событие, а затем состояние. Если происходит изменение состояния, то обработчик возвращает новое состояние.
Пример реализации конечного автомата показан в Листинге 1.
typedef enum {
IDLE_STATE,
COIN_INSERTED_STATE,
OPTION_SELECTED_STATE,
MAX_STATES
} state_e;
typedef enum {
INSERT_COIN_EVENT,
SELECT_OPTION_EVENT,
COFFEE_READY_EVENT,
MAX_EVENTS
} event_e;
state_e state = IDLE_STATE;
state_e next_state;
event_e event;
while (1)
{
event = readevent();
if (state == IDLE_STATE)
{
if(event == INSERT_COIN_EVENT)
{
next_state = insert_coin_event_handler();
}
}
else if(state == COIN_INSERTED_STATE)
{
if(event == SELECT_OPTION_EVENT)
{
next_state = select_option_event_handler();
}
}
else if(state == OPTION_SELECTED_STATE)
{
if(event == COFFEE_READY_EVENT)
{
next_state = coffee_ready_event_handler();
}
}
state = next_state;
}
Использование условных операторов является простейшим способом начала реализации. Когда количество состояний и событий невелико, этот метод интуитивно понятен, и разработчики могут быстро составить представление о том, что делает конечный автомат. Однако по мере роста числа состояний или событий код очень легко может стать громоздким. Его отладка и поддержка становятся сложными, поскольку конечный автомат начинает занимать несколько экранных страниц. Он становится еще более неконтролируемым, когда обработчики охватывают несколько файлов.
Помимо проблем с читаемостью и сопровождением, разработчики также должны принимать во внимание издержки, порождаемые использованием условных операторов, и учитывать их на этапе разработки, особенно для систем со строгими ограничениями по времени выполнения.
Подход, основанный на таблице
При этом подходе конечный автомат закодирован в виде таблицы, в которой одно измерение представляет состояния, а другое – события. Каждый элемент таблицы имеет обработчик для комбинации состояние/событие. Таблица может быть реализована на языке C с использованием двумерного массива указателей функций.
Пример реализации для кофейного автомата приведен в Листинге 2.
state_e (*state_table[MAX_STATES)[MAX_EVENTS])(void) = {
{insert_coin_event_handler, error_handler, error_handler},
{select_option_event_handler, error_handler},
{error_handler, error_handler, coffee_ready_event_handler},
};
while (1)
{
event = read_event();
if((event >= 0) && (event < MAX_EVENTS))
{
next_state = state_table[state][event]();
state = next_state;
}
}
Это элегантный способ трансляции диаграммы состояний в практический процесс обработки для каждой комбинации состояния и события, инкапсулированной в таблице. Такой конечный автомат быстро станет понятен разработчикам, и, кроме того, сопровождение программного обеспечения станет лучше контролируемым.
Однако когда таблица разрежена, то есть содержит много недействительных комбинаций состояние/событие, этот подход приводит к нерациональному использованию памяти. Расход памяти увеличивается также с ростом количества состояний и событий. Программистам необходимо четко представлять это и учитывать на начальных этапах разработки.
Другие соображения
В дополнение к обработчикам для каждого текущего состояния и обновления следующего, многие реализации также содержат логику очистки конечного автомата для текущего состояния и инициализации для следующего во время изменения состояния. Это можно осуществить путем определения функций входа и выхода для каждого состояния и их вызова во время изменения состояния.
Таблицы переходов также могут быть определены как набор специальных обработчиков, необходимых для перехода от одного состояния к другому.
В целом, не существует стандартных подходов к выбору способов реализации конечных автоматов подобных тому, который был описан выше. При определении способа реализации разработчику нужно правильно учитывать соответствующие издержки, а также принимать во внимание такие факторы, как масштабируемость и читаемость.
