Реализация конечного автомата (state machine)

23/03/2011 - 22:30

Конечные автоматы (State Machines)

   В данной статье под термином «конечный автомат» подразумевается алгоритм, который может находиться в одном из небольшого количества состояний. «Состояние» - это некое  условие, определяющее заданную взаимосвязь входных и выходных сигналов, а также входных сигналов и последующих состояний. Смышленый читатель сразу отметит, что конечные автоматы, описанные в данной статье, это автоматы Мили. Автомат Мили – это конечный автомат, где выходные сигналы являются функциями текущего состояния и входного сигнала, в отличие от автомата Мура, в котором выходные сигналы – это функции только состояния. В обоих случаях последующее состояние – это функция текущего состояния и входного сигнала. 
 
   Рассмотрим пример простого конечного автомата. Представьте, что в текстовой строке вам нужно распознать последовательность символов «//». На рисунке 1 показано, как это выполняется при помощи конечного автомата. Первое появление слеша не дает выходного сигнала, но приводит к тому, что автомат переходит во второе состояние. Если во втором состоянии автомат не находит слеша, он возвращается к первому, поскольку необходимо наличие 2-х слешей подряд. Если второй слеш найден, автомат выдает сигнал «готово».

Конечный автомат, распознающий последовательность символов
 
Я рекомендую применять следующий подход к разработке конечных автоматов:
 
- Выясните, что необходимо заказчику.
- Составьте диаграмму перехода состояний
- Закодируйте «скелет» конечного автомата без детализации операций перехода.
- Убедитесь, что переходы функционируют правильно.
- Конкретизируйте детали переходов.
- Проведите тест.

Пример конечного автомата

   Рассмотрим более интересный пример конечного автомата - программу, контролирующую втягивание и выдвижение шасси самолета. Хотя у большинства самолетов эта процедура выполняется при помощи электрогидравлического управляющего механизма (просто потому, что на борту отсутствует компьютер), в некоторых случаях, например в беспилотных летательных аппаратах, стоит использовать программное управление.
 
   Для начала разберемся с оборудованием. Шасси самолета состоит из передней опоры, основного левого шасси и основного правого шасси. Они приводятся в действие гидравлическим механизмом. Гидравлический насос с электроприводом подает давление на силовой исполнительный механизм. При помощи программного обеспечения  насос включается или выключается. Компьютер регулирует положение клапана направления -  «вниз» или «вверх», чтобы позволить давлению поднять или опустить шасси. Каждая из опор шасси имеет концевой выключатель: один из них закрывается, если шасси поднято,  другой -  если оно зафиксировано в положении «вниз». Чтобы определить, находится ли самолет на земле, концевой выключатель на стойке передней опоры замыкается, если вес самолета приходится на переднюю опору. Средства управления пилота состоят из верхнего/нижнего рычага шасси и трех лампочек (по одной на каждую опору), которые могут выключаться, загораться зеленым (положение «вниз») или красным светом (положение «переход»).
 
   А теперь перейдем к разработке конечного автомата. Первый, и самый сложный шаг – это понять реальные ожидания заказчика. Одним из преимуществ конечного автомата состоит в том, что он заставляет программиста продумывать все возможные случаи и, как следствие, получать от заказчика всю требуемую информацию. Почему я считаю это самым сложным этапом? А сколько раз вам давали описание задачи подобное этому: не задвигайте шасси, если самолет находится на земле.
 
   Безусловно, это важно, но заказчик считает, что на этом все заканчивается. А как насчет остальных случаев? Достаточно ли задвигать шасси в тот момент, когда самолет отрывается от земли? Что, если самолет подскочит на кочке на взлетно-посадочной полосе? Что, если пилот переведет рычаг переключения скоростей в положение «вверх» во время парковки и, как следствие, начнет взлетать? Должно ли шасси в этом случае подняться?
 
   Одним из преимуществ мышления в терминах конечного автомата является то, что вы можете быстро нарисовать диаграмму перехода состояний на проекционной доске, прямо перед заказчиком, и пройти весь процесс вместе с ним. Принято такое обозначение перехода состояний: «событие, которое явилось причиной перехода»/«выходной сигнал как результат перехода». Если бы мы разрабатывали только то, о чем изначально  просил заказчик («не задвигать шасси, если самолет находится на земле»),  то мы бы получили  автомат, изображенный на рисунке 2. 

конечный автомат, реализующий начальные требования заказчика
 
  При составлении диаграммы перехода состояний (или любого другого алгоритма) помните о следующем: 
 
- Компьютеры работают очень быстро по сравнению с механической аппаратурой
- Инженер-механик, который объясняет, что требуется сделать, возможно, не знает о компьютерах и алгоритмах всего того, что знаете вы. И это тоже положительный  момент, в противном случае, вы бы не потребовались!
- Как поведет себя ваша программа, если сломается механическая или электрическая деталь? 

   Конечный автомат, основанный на том, что действительно требуется заказчику, показан на рисунке 3. Здесь мы хотим воспрепятствовать втягиванию шасси самолета до тех пор, пока он точно не будет в воздухе. Для этого после открытия переключателя приземления автомат в течение нескольких секунд находится в ожидании. Мы также хотим реагировать на нарастающий фронт рычага пилота, а не на уровень, что позволит избежать проблем, если кто-то подвинет рычаг, пока самолет находится на парковке. Втягивание или выдвижение шасси занимает несколько секунд, и мы должны быть готовы к ситуации, что пилот в процессе этой операции передумает и переместит рычаг в противоположном направлении. Также обратите внимание, что если самолет снова приземлится, пока мы находимся в состоянии «Waiting for takeoff», таймер перезапустится  и втягивание шасси произойдет, только если самолет будет находиться в воздухе в течение 2-х секунд.
 
Конечный автомат, разработанный в результате поиска

Реализация конечного автомата

  Листинг 1 – это моя реализация конечного автомата изображенного на рисунке 3. Давайте обсудим некоторые детали кода. 

/*листинг 1*/
typedef enum {GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR} State_Type;
 
/*Этот массив содержит указатели на функции, вызываемые в определенных состояниях*/
void (*state_table[])() = {GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear};
 
State_Type curr_state;
 
main()
{
   InitializeLdgGearSM();
   /*Сердце автомата – этот бесконечный цикл. Функция, соответствующая
   текущему состоянию, вызывается один раз в итерацию */
   while (1) {
      state_table[curr_state]();
      DecrementTimer();
      /*Здесь можно вызывать другие функции, не связанные с нашим автоматом*/
   }
};
 
void InitializeLdgGearSM(void)
{
   curr_state = GEAR_DOWN;
   timer = 0.0;
   /*Остановка аппаратуры, выключение лампочек и т.д.*/
}
 
void GearDown(void)
{
   /* Переходим в состояние ожидания, если самолет
  не на земле и поступила команда поднять шасси*/
   if ((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) {
      timer = 2.0;
      curr_state = WTG_FOR_TKOFF;
   };
   prev_gear_lever = gear_lever; 
}
 
void RaisingGear(void)
{
   /*После того, как все переключатели подняты, переходим в состояние «шасси поднято»*/
   if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {
      curr_state = GEAR_UP;
   };
 
   /*Если пилот изменил свое решение, перейти в состояние «опускание шасси»*/
   if (gear_lever == DOWN) {
      curr_state = LOWERING_GEAR;
   };
}
 
void GearUp(void)
{
   /*если пилот передвинул рычаг в положение «вниз», 
   переходим в состояние «опускание шасси»*/
   if (gear_lever == DOWN) {
      curr_state = LOWERING_GEAR;
   };
}
 
void WtgForTakeoff(void)
{
   /* Ожидание перед поднятием шасси.*/
   if (timer <= 0.0) {
      curr_state = RAISING_GEAR;
   };
   
   /*Если мы снова коснулись или пилот поменял решение – начать все заново*/
   if ((squat_switch == DOWN) || (gear_lever == DOWN)) {
      timer = 2.0;
      curr_state = GEAR_DOWN;
     
       /* Don't want to require that he toggle the lever again
      this was just a bounce.*/
      prev_gear_lever = DOWN;
  };
}
 
void LoweringGear(void)
{
   if (gear_lever == UP) {
      curr_state = RAISING_GEAR;
   };
 
   if ((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) {
      curr_state = GEAR_DOWN;
   };
}

   Во-первых, вы можете заметить, что функциональность каждого состояния  реализуется отдельной Си функцией. Конечно, можно было бы реализовать автомат, используя  оператор switch с отдельным case `ом для каждого состояния, однако это может привести к очень длинной функции (10-20 строк кода на 1 состояние для каждого из 20-30 состояний). Также это может привести к ошибкам, если будете изменять код на конечных стадиях тестирования. Возможно, вы никогда не забывали оператор break в конце case`a, но со мной такие случаи бывали. Код одного состояния никогда не попадет в код другого, если для каждого состояния у вас будет отдельная функция. 
 
   Чтобы избежать применения оператора switch, я использую массив указателей на функции состояний, а переменную, используемую в качестве индекса массива, объявляю типа enum.
 
   Для простоты оборудование ввода-вывода, ответственное за считывание состояния переключателей, включение и выключение насосов и т.д., представлено в виде простых переменных.  Предполагается, что данные переменные представляют собой «магические адреса», связанные с оборудованием невидимыми средствами. 
 
   Другая очевидная вещь - в этот момент код не играет особой роли. Он просто переходит от одного состояния к другому. Это важный промежуточный этап и его не следует игнорировать. Кстати, было бы неплохо добавить операторы печати, заключенные между директивами условной компиляции (#ifdef DEBUG .. #endif), которые бы выводили текущее состояние и значения входных сигналов.
 
  Залог успеха кроется в коде, который вызывает переход состояний, т.е. определяет, что произошел ввод данных.
 
   Если код правильно проходит через все состояния, следующим этапом становится написание «начинки» кода, то есть именно того, что производит выходной сигнал. Помните, что каждый переход имеет входной сигнал (событие, которое вызвало его) и выходной сигнал (аппаратное устройство ввода-вывода, как в нашем примере). Зачастую это полезно зафиксировать в виде таблицы перехода состояний.
 
таблица перехода состояний
 
   В таблице перехода состояний одна строка приходится на один переход состояния. 
 
   При кодировании конечного автомата старайтесь сохранить его силу – ярко выраженное соответствие между требованиями заказчика и кодом. Вероятно, придется скрыть подробности касательно оборудования в другом уровне функций, например, для того, чтобы код конечного автомата максимально походил на таблицу перехода состояний и диаграмму перехода состояний. Подобная симметрия помогает предотвратить ошибки и объясняет то, почему конечные автоматы являются такой важной частью арсенала программиста встраиваемых систем. Конечно, вы могли бы добиться того же эффекта путем установки флажков и бесконечного множества вложенных операторов if, однако  при этом будет очень сложно отслеживать код и сравнивать его с пожеланиями заказчика. 
 
   Фрагмент кода в листинге 2 расширяет функцию RaisingGear(). Обратите внимание, что код для функции RaisingGear() стремится к зеркальному отображению 2-х рядов  таблицы переходов для состояния Raising Gear.
 
void RaisingGear(void)
{
   /*После того, как все переключатели подняты, переходим в состояние «шасси поднято»*/
   if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {
      pump_motor = OFF;
      gear_lights = EXTINGUISH;
      curr_state = GEAR_UP;
  };
 
   /*Если пилот передумал, начать втягивание шасси*/
   if (gear_lever == DOWN) {
      pump_direction = DOWN;
      curr_state = GEAR_LOWERING;
   };
}
 
   Помните о том, что следует избегать скрытых состояний. Скрытое состояние появляется тогда, когда по причине лени вы пытаетесь добавить условное субсостояние вместо того, чтобы добавить конкретное состояние. Например, если ваш код обрабатывает один и тот же входной сигнал разными способами (т.е. инициирует разные переходы состояний) в зависимости от режима, то он является скрытым состоянием. В этом случае я бы задумался, а не следует ли разбить данное состояние на два? Применение скрытых состояний сводит на нет все преимущество использования конечного автомата. 
 
   В качестве тренировки вы можете расширить конечный автомат, который мы только что рассмотрели, добавив таймаут к циклу втягивания или выдвижения шасси, т.к. инженер-механик не хочет, чтобы гидравлический насос работал дольше 60 секунд. Если цикл заканчивается, пилот должен быть предупрежден переключением зеленой и красной лампочки, и он должен иметь возможность снова переместить рычаг, чтобы повторить попытку. Также вы можете спросить гипотетического инженера-механика, как сказывается на насосе изменение направления на противоположное во время его работы, потому что это происходит в 2-ух случаях, когда пилот передумывает. Конечно, механик скажет, что негативно. Тогда как бы вы изменили конечный автомат, чтобы быстро остановить насос при изменении направления?

Тестирование конечного автомата

   Прелесть кодирования алгоритмов в виде конечных автоматов состоит в том, что план проведения теста почти автоматически пишется сам. Все, что вам нужно сделать – это пройти через каждый переход состояния. Я обычно делаю это с маркером в руках, вычеркивая стрелки на диаграмме перехода состояний по мере того, как они успешно проходят тест. Это хороший способ избежать «скрытых состояний» - в тестах они упускаются чаще, чем конкретные состояния. 
 
   Это требует значительного терпения и большого количества кофе, так как даже конечный автомат средних размеров может иметь до 100 различных переходов. Кстати,  количество переходов – это отличный способ измерить сложность системы. Последнее определяется требованиями заказчика, а конечный автомат делает очевидными объемы тестирования. При менее организованном подходе объем требуемого тестирования может оказаться таким же внушительным, но вы об этом просто не узнаете. 
 
  Очень удобно использовать в коде операторы печати, выводящие текущее состояние, значения входных и выходных сигналов. Это позволяет вам с легкостью наблюдать то, что выражает «Золотое Правило Тестирования Программ»: проверяйте, что программа выполняет задуманное, а также то, что она не делает ничего лишнего. Другими словами, получаете ли вы только те выходные сигналы, которые вы ожидаете, и что еще происходит помимо этого?  Нет ли «затруднительных» переходов состояний, т.е. состояний, которые случайно проходят, только для одного повтора цикла? Меняются ли выходные сигналы, когда вы этого не ожидаете? В идеале выходные сигналы ваших printfs должны заметно напоминать таблицу перехода состояний. 
 
   Наконец - и это касается любого встроенного ПО, а не только ПО, основанного на конечных автоматах - будьте очень осторожны при первом запуске ПО на реальном  оборудовании. Очень легко ошибиться с полярностью сигналов – «Ой, я думал, что «1» означает поднять шасси, а «0» -  опустить его». Во многих случаях, мой помощник по оборудованию применял временный «куриный переключатель» для защиты ценных компонентов, пока не был уверен, что мое ПО перемещает предметы в правильном направлении.

Запуск

   Когда все требования заказчика выполнены, я могу запускать конечный автомат подобной сложности через пару дней. Практически всегда автоматы выполняют то, что я хочу. Самое сложное – это, конечно, точно понять, чего хочет заказчик и убедиться, что заказчик сам знает, чего он хочет. Последнее занимает значительно больше времени!
 
Мартин Гомез – программист Лаборатории Прикладной Физики при Университете Джона Хопкинса. Занимается разработкой ПО для обеспечения полетов исследовательских космических кораблей. Проработал в области разработки встраиваемых систем в течение 17 лет. Мартин – бакалавр наук в области аэрокосмического инжиниринга и магистр в области электроинжиниринга (университет Корнелл). 

Martin Gomez "Embedded State Machine Implementation". Вольный перевод - ChipEnable.Ru

Комментарии   

# bomond 24.03.2011 05:27
С удовольствием бы прочел на этом ресурсе о IAR Visual State...Он как раз для этого. Спасибо за статью! Как всегда интересно.
Ответить | Ответить с цитатой | Цитировать
# noonv 24.03.2011 06:58
Спасибо! Отличная статья!
Ответить | Ответить с цитатой | Цитировать
# h0rr0rr_drag0n 24.03.2011 07:26
Рисунок №3 и таблица №1 не влезли до конца в статью - они обрезаны справа :sad:
Ответить | Ответить с цитатой | Цитировать
# Pashgan 24.03.2011 11:11
Можно открыть картинки в отдельном окне. Если не забуду, сделаю их кликабельными.
Ответить | Ответить с цитатой | Цитировать
# Агро 24.03.2011 08:39
Хорошо бы не такой тупой пример, а хотя бы двухзадачную систему РВ (измерение-связ ь) с применением прерываний. И еще, а как сделать чтобы убрать субъективный фактор при перечислении членов typedef и имен функций в массиве указателей, ведь это должно быть строго синхронизирован о, а если их 100 штук и добавлялись в разное время хаотически то можно нечайно нарушить порядок их следования. Каждый раз проверять что ли?
Ответить | Ответить с цитатой | Цитировать
# Pashgan 24.03.2011 11:08
Меня забавляют подобные комментарии. Как правило они бывают двух типов:
- автор слишком наворотил, дайте пример попроще.
- пример слишком тупой, дайте посложнее.

Как гласит народная мудрость: "Будешь пытаться угодить всем, не угодишь никому"
Ответить | Ответить с цитатой | Цитировать
# TERMIN 25.03.2011 10:26
Цитирую Pashgan:
Меня забавляют подобные комментарии. Как правило они бывают двух типов:
- автор слишком наворотил, дайте пример попроще.
- пример слишком тупой, дайте посложнее.

Как гласит народная мудрость: "Будешь пытаться угодить всем, не угодишь никому"

паш, все нормально, лучше завести тему на форуме, и там при необходимости привести пример попроще/посложней
Спасибо за статью
Ответить | Ответить с цитатой | Цитировать
# alboo 07.07.2011 13:50
Цитирую Агро:
Хорошо бы не такой тупой пример, а хотя бы двухзадачную систему РВ (измерение-связь) с применением прерываний. И еще, а как сделать чтобы убрать субъективный фактор при перечислении членов typedef и имен функций в массиве указателей, ведь это должно быть строго синхронизировано, а если их 100 штук и добавлялись в разное время хаотически то можно нечайно нарушить порядок их следования. Каждый раз проверять что ли?

Огромное спасибо за статью!
Кстати, для согласования констант enum с массивом указателей на функции, по моему мнению, удобно использовать препроцессор, например, так:
Код:
#define FunctionItem(id,fun) id

typedef enum {
#include "fi.h"
} State_Type;

#undef FunctionItem
#define FunctionItem(id,fun) fun

void (*state_table[])() = {
#include "fi.h"
};

Где файл fi.h такой:
Код:
FunctionItem(GEAR_DOWN = 0, GearDown),
FunctionItem(WTG_FOR_TKOFF, WtgForTakeoff),
FunctionItem(RAISING_GEAR, RaisingGear),
FunctionItem(GEAR_UP, GearUp),
FunctionItem(LOWERING_GEAR, LoweringGear)

Обратите внимание на отсутствие запятой в последней строке
Ответить | Ответить с цитатой | Цитировать
# AleGro 26.03.2011 19:46
Цитата:
Самое сложное – это, конечно, точно понять, чего хочет заказчик и убедиться, что заказчик сам знает, чего он хочет.
Вот это уж точно!
Ответить | Ответить с цитатой | Цитировать
# mih 05.04.2011 16:42
Что означает строка:
Код:void (*state_table[])() = {GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear};?
Ответить | Ответить с цитатой | Цитировать
# JoJo 05.04.2011 18:25
Там комментарий над строкой. Это массив указателей на функции
Ответить | Ответить с цитатой | Цитировать

Добавить комментарий

Защитный код
Обновить