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

У даній статті під терміном «кінцевий автомат» мається на увазі алгоритм, який може знаходитися в одному з невеликої кількості станів. «Стан» - це якесь умова, що визначає задану взаємозв'язок вхідних і вихідних сигналів, а також вхідних сигналів і наступних станів. Кмітливий Новомосковсктель відразу відзначить, що кінцеві автомати, описані в даній статті, це автомати Мілі. Автомат Мілі - це кінцевий автомат, де вихідні сигнали є функціями поточного стану і вхідного сигналу, на відміну від автомата Мура, в якому вихідні сигнали - це функції тільки стану. В обох випадках подальший стан - це функція поточного стану і вхідного сигналу.

Розглянемо приклад простого кінцевого автомата. Уявіть, що в текстовому рядку вам потрібно розпізнати послідовність символів «//». На малюнку 1 показано, як це виконується за допомогою кінцевого автомата. Перша поява слеша не дає вихідного сигналу, але призводить до того, що автомат переходить в другий стан. Якщо в другому стані автомат не знаходить слеша, він повертається до першого, оскільки необхідна наявність 2-х слешів поспіль. Якщо другий слеш знайдений, автомат видає сигнал «готове».

Я рекомендую застосовувати наступний підхід до розробки кінцевих автоматів:

- З'ясуйте, що необхідно замовнику.

- Складіть діаграму переходу станів

- Закодуйте «скелет» кінцевого автомата без деталізації операцій переходу.

- Переконайтеся, що переходи функціонують правильно.

- Конкретизуйте деталі переходів.

Розглянемо більш цікавий приклад кінцевого автомата - програму, яка контролює втягування і висунення шасі літака. Хоча у більшості літаків ця процедура виконується за допомогою електрогідравлічного рульового механізму (просто тому, що на борту відсутній комп'ютер), в деяких випадках, наприклад в безпілотних літальних апаратах, варто використовувати програмне керування.

Для початку розберемося з обладнанням. Шасі літака складається з передньої опори, основного лівого шасі і основного правого шасі. Вони приводяться в дію гідравлічним механізмом. Гідравлічний насос з електроприводом подає тиск на силовий виконавчий механізм. За допомогою програмного забезпечення насос включається або вимикається. Комп'ютер регулює положення клапана напрямки - «вниз» або «вгору», щоб дозволити тиску підняти або опустити шасі. Кожна з опор шасі має кінцевий вимикач: один з них закривається, якщо шасі піднято, інший - якщо воно зафіксовано в положенні «вниз». Щоб визначити, чи знаходиться літак на землі, кінцевий вимикач на стійці передньої опори замикається, якщо вага літака доводиться на передню опору. Засоби управління пілота складаються з верхнього / нижнього важеля шасі і трьох лампочок (по одній на кожну опору), які можуть виключатися, загорятися зеленим (положення «вниз») або червоним світлом (положення «перехід»).

А тепер перейдемо до розробки кінцевого автомата. Перший, і самий складний крок - це зрозуміти реальні очікування замовника. Одним з переваг кінцевого автомата полягає в тому, що він змушує програміста продумувати всі можливі випадки і, як наслідок, отримувати від замовника всю необхідну інформацію. Чому я вважаю це найскладнішим етапом? А скільки разів вам давали опис завдання подібне до цього: чи не зарухалися шасі, якщо літак знаходиться на землі.

Безумовно, це важливо, але замовник вважає, що на цьому все закінчується. А як щодо інших випадків? Чи достатньо засовувати шасі в той момент, коли літак відривається від землі? Що, якщо літак підскочить на купині на злітно-посадковій смузі? Що, якщо пілот переведе важіль перемикання швидкостей в положення «вгору» під час паркування і, як наслідок, почне злітати? Чи повинно шасі в цьому випадку піднятися?

Одним з переваг мислення в термінах кінцевого автомата є те, що ви можете швидко намалювати діаграму переходу станів на проекційної дошці, прямо перед замовником, і пройти весь процес разом з ним. Прийнято таке позначення переходу станів: «подія, яке стало причиною переходу» / «вихідний сигнал як результат переходу». Якби ми розробляли тільки те, про що спочатку просив замовник ( «Не засовувати шасі, якщо літак знаходиться на землі»), то ми б отримали автомат, зображений на малюнку 2.

При складанні діаграми переходу станів (або будь-якого іншого алгоритму) пам'ятайте про наступне:

- Комп'ютери працюють дуже швидко в порівнянні з механічною апаратурою

- Інженер-механік, який пояснює, що потрібно зробити, можливо, не знає про комп'ютери та алгоритмах всього того, що знаєте ви. І це теж позитивний момент, в іншому випадку, ви б не потрібні були!

- Як поведе себе ваша програма, якщо зламається механічна або електрична деталь?

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

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

Лістинг 1 - це моя реалізація кінцевого автомата зображеного на малюнку 3. Давайте обговоримо деякі деталі коду.

По-перше, ви можете помітити, що функціональність кожного стану реалізується окремої Сі функцією. Звичайно, можна було б реалізувати автомат, використовуючи оператор 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))

Пам'ятайте про те, що слід уникати прихованих станів. Приховане стан з'являється тоді, коли через ліні ви намагаєтеся додати умовне субсостояніе замість того, щоб додати конкретний стан. Наприклад, якщо ваш код обробляє один і той же вхідний сигнал різними способами (тобто ініціює різні переходи станів) в залежності від режиму, то він є прихованим станом. В цьому випадку я б задумався, а чи не варто розбити даний стан на два? Застосування прихованих станів зводить нанівець всю перевагу використання кінцевого автомата.

В якості тренування ви можете розширити кінцевий автомат, який ми тільки що розглянули, додавши таймаут до циклу втягування або висунення шасі, тому що інженер-механік не хоче, щоб гідравлічний насос працював довше 60 секунд. Якщо цикл закінчується, пілот повинен бути попереджений перемиканням зеленою і червоною лампочки, і він повинен мати можливість знову перемістити важіль, щоб повторити спробу. Також ви можете запитати гіпотетичного інженера-механіка, як позначається на насосі зміна напрямку на протилежне під час його роботи, тому що це відбувається в 2-ух випадках, коли пілот передумує. Звичайно, механік скаже, що негативно. Тоді як би ви змінили кінцевий автомат, щоб швидко зупинити насос при зміні напрямку?

Принадність кодування алгоритмів у вигляді кінцевих автоматів полягає в тому, що план проведення тесту майже автоматично пишеться сам. Все, що вам потрібно зробити - це пройти через кожен перехід стану. Я зазвичай роблю це з маркером в руках, викреслюючи стрілки на діаграмі переходу станів у міру того, як вони успішно проходять тест. Це хороший спосіб уникнути «прихованих станів» - в тестах вони беруться частіше, ніж конкретні стану.

Це вимагає значного терпіння і великої кількості кави, так як навіть кінцевий автомат середніх розмірів може мати до 100 різних переходів. До речі, кількість переходів - це відмінний спосіб виміряти складність системи. Останнє визначається вимогами замовника, а кінцевий автомат робить очевидними обсяги тестування. При менш організованому підході обсяг необхідного тестування може виявитися таким же значним, але ви про це просто не впізнаєте.

Дуже зручно використовувати в коді оператори друку, виводять поточний стан, значення вхідних і вихідних сигналів. Це дозволяє вам з легкістю спостерігати те, що виражає «Золоте Правило Тестування Програм»: перевіряйте, що програма виконує задумане, а також те, що вона не робить нічого зайвого. Іншими словами, чи отримуєте ви тільки ті вихідні сигнали, які ви очікуєте, і що ще відбувається крім цього? Чи немає «скрутних» переходів станів, тобто станів, які випадково проходять, тільки для одного повтору циклу? Чи змінюються вихідні сигнали, коли ви цього не очікуєте? В ідеалі вихідні сигнали ваших printfs повинні помітно нагадувати таблицю переходу станів.

Нарешті - і це стосується будь-якого вбудованого ПО, а не тільки ПО, заснованого на кінцевих автоматах - будьте дуже обережні при першому запуску ПЗ на реальному обладнанні. Дуже легко помилитися з полярністю сигналів - «Ой, я думав, що« 1 »означає підняти шасі, а« 0 »- опустити його». У багатьох випадках, мій помічник по обладнанню застосовував тимчасовий «курячий перемикач» для захисту цінних компонентів, поки не був упевнений, що моє ПО переміщує предмети в правильному напрямку.

Коли всі вимоги замовника виконані, я можу запускати кінцевий автомат подібної складності через пару днів. Практично завжди автомати виконують те, що я хочу. Найскладніше - це, звичайно, точно зрозуміти, чого хоче замовник і переконатися, що замовник сам знає, чого він хоче. Останнє займає значно більше часу!

Martin Gomez "Embedded State Machine Implementation". Вільний переклад - ChipEnable.Ru

Добре б не такий тупий приклад, а хоча б двухзадачную систему РВ (вимір-зв ь) з застосуванням переривань. І ще, а як зробити щоб прибрати суб'єктивний фактор при перерахуванні членів typedef і імен функцій в масиві покажчиків, адже це повинно бути строго синхронізований про, а якщо їх 100 штук і додавалися в різний час хаотично то можна нечайно порушити порядок їх слідування. Кожен раз перевіряти чи що?

Як говорить народна мудрість: "Будеш намагатися догодити всім, не догодиш нікому"

паш, все нормально, краще завести тему на форумі, і там при необхідності привести приклад простіше / складніша
Дякую за статтю

Добре б не такий тупий приклад, а хоча б двухзадачную систему РВ (вимір-зв'язок) із застосуванням переривань. І ще, а як зробити щоб прибрати суб'єктивний фактор при перерахуванні членів 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)

Зверніть увагу на відсутність коми в останньому рядку