В данной статье мы рассмотрим такой интересный стиль программирования микроконтроллеров как автоматное программирование. Точнее это даже не стиль программирования а целая концепция, благодаря которой программист микроконтроллеров может существенно облегчить свою жизнь. Благодаря ей многие задачи, поставленные перед программистом, решаются гораздо легче и проще, избавляя программиста от многих сложностей. Автоматное программирование часто также называют Switch-технологией.
Конечный автомат (в англ. – Finite State Machine, FSM), согласно Википедии, определяется как абстрактная машина, которая может находиться ровно в одном из конечного числа состояний в любой момент времени. Конечный автомат может переходить из одного состояния в другое в ответ на некоторые внешние входные данные и/или при выполнении заданного условия; переход из одного состояния в другое называется переходом (в англ. – transition). FSM определяется списком его состояний, его начальным состоянием и условиями для каждого перехода.
Каким же образом конечные автоматы упрощают написание программ для микроконтроллеров (да и не только для них)? Дело в том, что традиционный способ обработки в программе переходов из одного состояния в другое в системе с ограниченным числом состояний заключается в использовании операторов if или switch (или их комбинации). В системах с небольшим количеством состояний этот подход вполне успешно работает, но если состояний много, то традиционный код для их обработки становится ужасно запутанным и трудно читаемым, он очень сложно поддается модификации.
Программирование в конечных автоматах избавляет программу от этих недостатков. Программа становится проще, ее легко модифицировать. Программа написанная в автоматном стиле похожа на переключатель, который в зависимости от условий переключается в то или иное состояние. Количество состояний программисту изначально известно.
В грубом представлении это как выключатель освещения. Есть два состояния – включено и выключено, и два условия включить и выключить.
Также программы, написанные по Switch-технологии, легко документировать. В рамках этого стиля программирования программа представляет собой совокупность конечных автоматов, взаимодействующих друг с другом и с «внешним миром». При этом в наглядной графической форме могут быть выражены как связи между автоматами, так и их внутренняя структура.
Еще одним существенным преимуществом Switch-технологии является возможность повторного использования кода. Фактически, программа в данном случае состоит из компонентов, являющихся в высокой степени автономными «сущностями». Компонент имеет ограниченное количество связей с остальной программой, его можно разрабатывать и тестировать отдельно, а применять многократно, и именно это свойство подобных систем делает разработку быстрой и удобной.
Автомат в предлагаемом стиле программирования также является своего рода «кирпичиком», автономной единицей программы. Его связи с остальными автоматами сведены к минимуму и унифицированы. Автомат можно разработать отдельно, а затем применять в различных программных проектах.
Из всего изложенного вытекает и такое достоинство Switch-технологии как легкость модификации программ, написанных с ее помощью. Так как количество связей между автоматами минимально, изменения в одном из них чаще всего не влекут за собой необходимость коррекции кода в других автоматах.
Общая структура программы в Switch-технологии
Суть описываемого нами стиля автоматного программирования кратко можно сформулировать следующим образом: программа представляет собой совокупность конечных автоматов, выполняющихся параллельно и обменивающихся между собой сообщениями. Другим ключевым свойством предлагаемой концепции является активное использование таймеров, которые предназначены для привязки работы программы к реальному времени.
Итак, автоматы должны выполняться параллельно. Как достичь данного эффекта без использования многозадачной операционной системы? Все дело в особой структуре автоматной программы.
Рассмотрим структуру программ рассматриваемого класса более подробно. Будем для простоты считать, что каждый конечный автомат (КА) описан в отдельном модуле программы и имеет, как минимум, две внешние функции:
Вместо букв FSM в объявлении представленных функций необходимо подставлять имя автомата. В данном случае, к примеру, функции:
будут принадлежать автомату PasswordEditor.
При этом функция InitFSM, как следует из ее названия, будет инициализировать автомат (это что-то вроде конструктора в объектно-ориентированном программировании), а функция ProcessFSM будет отвечать за работу автомата. Главная особенность данной функции: она не должна выполнять продолжительных во времени действий, связанных с ожиданием какого-либо флага или с истечением временного интервала – то есть в ней не должно быть конструкций типа:
В автоматном программировании в таких конструкциях просто нет необходимости.
Задачей главного цикла программы является поочередный вызов функций ProcessFSM всех автоматов, составляющих программу:
Теперь становится понятно, каким образом обеспечивается «многопоточность» системы: в каждой итерации главного цикла поочередно вызываются Process-функции каждого автомата – каждому автомату выделяется время для выполнения какого-либо элементарного действия (или, что тоже может быть, просто для передачи управления далее по списку). То есть если какой либо из автоматов «зависает», то «зависает» вся система. Именно для предотвращения подобной ситуации вводится явный запрет на действия в автоматах, которые занимают продолжительное или неопределенное время.
Конечные автоматы
Существует три наиболее распространенных типов конечных автоматов (КА, в англ. Finite State Machine – FSM): автомат Мура, автомат Мили и смешанный автомат. Автомат Мура – это КА, выход которого является функцией состояния: выходные воздействия определены в состояниях. Автомат Мили – это автомат, у которого выходные воздействия определены для переходов между состояниями. А смешанный автомат – это автомат, у которого выходные воздействия могут быть определены как в состояниях, так и на переходах.
Теория КА активно развивалась в 50-е – 60-е годы XX века и нашла широкое применение во многих областях техники. Особенно плодотворной она оказалась при разработке трансляторов.
При этом КА рассматривается как своеобразное средство для «перевода» цепочек символов языка А в цепочки символов языка В, а правила перевода задаются структурой КА. Такое применение КА привело к тому, что до настоящего времени наиболее полное изложение теории КА можно найти в учебниках по компиляторам и математической лингвистике.
Достаточно широкое применение КА нашли также в задачах синтеза цифровых устройств, в задачах описания поведения сложных систем (в отрасли связи даже был создан специальный язык описания телекоммуникационных систем, базирующийся на КА).
Прежде чем перейти к рассмотрению программных реализаций конечных автоматов, укажем, что КА имеет входы, выходы и переменную состояния.
Под входом понимается сообщение, срабатывание таймера, результат выражения, которое имеет логическое значение (в том числе возвращаемое функцией логическое значение). Доступ к аппаратным ресурсам микроконтроллера (регистрам периферийных устройств, портам ввода–вывода и т. п.) выполняется также путем вызова функций.
Под выходом автомата понимается отправка сообщения; запуск, останов или сброс таймера; вызов функции.
При этом выделяется особая переменная состояния – переменная, которая определяет текущее состояние автомата. Эта переменная должна быть доступна только своему автомату, ее изменение из других автоматов недопустимо.
Автомат может осуществлять действия (action) и деятельности (activity) автомата. И деятельность, и действие автомата относятся к его выходной активности.
При этом действием называется выходное воздействие, выполняемое однократно при входе в состояние или на переходе, а деятельностью – выходное воздействие, выполняющееся непрерывно в течение всего времени нахождения автомата в определенном состоянии. Также возможна реализация действий, выполняющихся на выходе из состояния.
Автомат Мура и автомат смешанного типа могут выполнять как действия, так и деятельности, а автомат Мили может выполнять только действия.
В минимальном виде объявление автомата можно записать так:
А описание автомата выглядит следующим образом:
Приведенное описание соответствует автомату Мили, который имеет два состояния: активное и неактивное, а также два входа: сообщения MSG_FSM1_ACTIVATE и MSG_FSM1_DEACTIVATE, которые переводят автомат в активное и неактивное состояние соответственно. Граф этого автомата представлен на следующем рисунке.
Данный автомат выполняет действия на переходах из одного состояния в другое (именно поэтому это автомат Мили), однако его достаточно легко преобразовать в автомат Мура или в смешанный автомат. Представленный на рисунке автомат не делает ничего полезного, это просто шаблон, на основе которого можно строить автоматы с более сложным поведением.
Пример использования конечных автоматов в микроконтроллерах AVR
Для демонстрации возможностей конечных автоматов в микроконтроллерах AVR используем схему, представленную на следующем рисунке.
Как видите, в ней нет ничего сложного: в ней используется микроконтроллер AVR ATMEGA328P-PU, 2 кнопки, двигатель и несколько других компонентов для увеличения скорости двигателя за 3 шага с использованием широтно-импульсной модуляции. В любом состоянии двигатель может быть остановлен с помощью 2-го переключателя, и система переходит в состояние холостого хода.
Компоненты в представленной схеме можно заменить на те, которые у вас есть под рукой. Не обязательно в точности такие же как на схеме. Как видно из схемы, двигатель вращается только в одном направлении, это было сделано для того, чтобы максимально упростить логику работы проекта и использовать минимальное количество компонентов.
Для управления скоростью вращения двигателя мы будем использовать ШИМ (широтно-импульсную модуляцию) и с помощью таймера Timer2 микроконтроллера будем изменять коэффициент заполнения ШИМ сигнала: 35% для SPEED1, 70% для SPEED2 и 100% для SPEED3. Более подробно об использовании ШИМ в микроконтроллерах AVR можно прочитать в этой статье.
На следующем рисунке представлена таблица состояний и переходов для нашего проекта. Итого имеем 4 состояния и 6 переходов, но переходы из различных состояний скорости (Speed States) в холостое состояние (Idle) похожи друг на друга, поэтому не требуют дополнительного кода.
В графическом виде диаграмма состояний и переходов для нашего проекта представлена на следующем рисунке.
В следующем фрагменте кода представлена логика обработки этой диаграммы состояний обычным способом – с использованием оператора switch. Конечно, это решение кажется значительно проще чем то решение, которое мы выполним с помощью конечных автоматов. Но оно гораздо сложнее масштабируется при увеличении количества состояний и с трудом поддается модификации.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
do forever { if(switch #1 pressed) { switch(state) { case IDLE: SetSpeed(35); state = SPEED1; break; case SPEED1: SetSpeed(70); state = SPEED2; break; case SPEED2: SetSpeed(100); state = SPEED3; break; case SPEED3: break; } } else if (switch #2 pressed) { SetSpeed(0); state = IDLE; } } |
Использование конечных автоматов
Конечные автоматы могут быть внедрены в программу для микроконтроллеров несколькими способами, к наиболее популярным из которых относятся следующие: вызов методов Entry, Post и Exit и использование наследования. В нашем случае мы будем использовать наследование.
Классы в следующем фрагменте кода являются производными классами (derived classes).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
//* // Base state class for custom states. // Implements the Start and Stop method that are common // to all derived classes. //* class CStateBase : public CState { public: CStateBase() {} protected: // NOTE Initialize all states, as needed virtual void Initialize(uint16_t p1 = 0) override {} // NOTE Action to be invoked after transitioning. virtual void EnterAction(uint16_t p1 = 0) override {} // NOTE Give the Exitaction a peek at param and the value returned // determines if the transition should be cancelled or not. // true - Cancel operation // false - continue with transition virtual bool ExitAction(uint16_t p1 = 0) override { return false; } static void Start(); static void Stop(); }; //* // Derived State classes that do the work //* class CIdleState : public CStateBase { public: CIdleState() {} void Initialize(uint16_t p1 = 0) override; bool ExitAction(uint16_t p1 = 0) override; }; class CSpeed1State : public CStateBase { public: CSpeed1State() {} void EnterAction(uint16_t p1 = 0) override; bool ExitAction(uint16_t p1 = 0) override; }; class CSpeed2State : public CStateBase { public: CSpeed2State() {} void EnterAction(uint16_t p1 = 0) override; bool ExitAction(uint16_t p1 = 0) override; }; class CSpeed3State : public CStateBase { public: CSpeed3State() {} void EnterAction(uint16_t p1 = 0) override; bool ExitAction(uint16_t p1 = 0) override; }; |
Класс CStateBase в приведенном коде объявляет статические методы Start и Stop, которые потом используют все производные классы. Нам необходимо просто скопировать методы, помеченные как статические.
Следующий фрагмент программы содержит код для производных классов и он наглядно показывает как просто программа может выглядеть в данном случае и как просто ее потом можно масштабировать в случае необходимости.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// ===============> StateBase overrides <============= void CStateBase::Start() { // Timer2 - Fast PWM, Clear OC2A on compare match TCCR2A |= (1 << COM2A1) | (1 << WGM20) | (1 << WGM21); // Prescale = 64 TCCR2B |= (1 << CS22); } void CStateBase::Stop() { TCCR2A = 0; TCCR2B = 0; PORTB &= ~(1 << PB3); } // ===============> State overrides <================= void CIdleState::Initialize(uint16_t p1 /* = 0 */) { // OC2A as output DDRB |= (1 << PB3); Stop(); } bool CIdleState::ExitAction(uint16_t p1 /* = 0 */) { Start(); OCR2A = 0; // 5% duty cycle return false; } void CSpeed1State::EnterAction(uint16_t p1) { OCR2A = 90; // 35% duty cycle } void CSpeed2State::EnterAction(uint16_t p1) { OCR2A = 180; // 70.3% duty cycle } void CSpeed3State::EnterAction(uint16_t p1) { OCR2A = 255; // 100% duty cycle } bool CSpeed1State::ExitAction(uint16_t p1 /* = 0 */) { Stop(); return false; } bool CSpeed2State::ExitAction(uint16_t p1 /* = 0 */) { Stop(); return false; } bool CSpeed3State::ExitAction(uint16_t p1 /* = 0 */) { Stop(); return false; } |
Хотя представленные классы сами по себе делают относительно мало "работы", но зато они наглядно показывают как всю рассматриваемую проблему можно разделить на несколько легко управляемых фрагментов, где каждое состояние (State) имеет уникальную роль в общей схеме.
Когда мы создавали экземпляры классов мы для состояний системы не прописывали ничего лишнего, мы просто объявляли эти состояния. Но переходы (Transitions) – это уже другая история и для них уже необходимо указать в какое состояние осуществляется переход и в результате какого действия.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Finite State machine CFiniteStateMachine fsm; // состояния (The states) CIdleState sIdle; CSpeed1State sSpeed1; CSpeed2State sSpeed2; CSpeed3State sSpeed3; // переходы для увеличения скорости (Transitions for speed UP) CTransition ts1(&sSpeed1, SPEED_MASK); CTransition ts2(&sSpeed2, SPEED_MASK); CTransition ts3(&sSpeed3, SPEED_MASK); // переход для остановки двигателя (Transition for stopping motor, one common) //один общий переход для всех состояний (transition for all.) CTransition ts4(&sIdle, STOP_MASK); |
Далее, в основной функции программы main мы будем добавлять различные состояния для нашего конечного автомата (FiniteStateMachine), добавлять переходы для состояний, с которыми они связаны, устанавливать в качестве активного состояния холостое состояние (Idle) и выполнять метод инициализации конечного автомата (CFiniteStateMachine's Initialize method), который перебирает массив состояний и выполняет заданные методы. В данном случае метод CIdle's Initialize используется для установки порта OC2A (PB3) в режим работы на вывод данных и останавливает таймер.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
int main(void) { // Add states to FiniteStateMachine (добавляем состояния для конечного автомата) fsm.AddState(&sIdle); fsm.AddState(&sSpeed1); fsm.AddState(&sSpeed2); fsm.AddState(&sSpeed3); // Switch press #1 transitions, adjust duty cycle (при нажатии кнопки 1) // i.e. increase speed (настраиваем коэффициент заполнения ШИМ сигнала, то есть увеличиваем скорость) sIdle.AddTransition(&ts1); // Idle -> Speed1 sSpeed1.AddTransition(&ts2); // Speed1 => Speed2 sSpeed2.AddTransition(&ts3); // Speed2 -> Speed3 // Switch press #2 transitions, stop motor (при нажатии кнопки 2 останавливаем двигатель) sSpeed3.AddTransition(&ts4); // Speed3 => Idle sSpeed2.AddTransition(&ts4); // Speed2 => Idle sSpeed1.AddTransition(&ts4); // Speed1 => Idle // Set the active state to Idle (устанавливаем в качестве активного состояния холостое) fsm.SetActiveState(&sIdle); // Go through classes and Initialize those that need it, in this example // the Idle class is the only one that needs initialization. fsm.Initialize(); ... |
В следующем фрагменте кода мы настраиваем обработчик прерывания для Timer1, который формирует программную задержку для обоих кнопок (переключателей). Прерывания INT0 и INT1 обрабатывают нажатия кнопок по восходящему фронту импульса (rising edge). Свойство g_postEvent используется для того, чтобы отложить обработку события до тех пор пока не произойдет выход из обработчиков прерываний.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// =================> Globals <================== volatile uint16_t g_millis = 0; volatile uint16_t g_ticks = 0; volatile bool g_flg = false; volatile uint16_t g_postEvent = 0; // =============> Interrupt handlers <=========== ISR(TIMER1_COMPA_vect) { g_millis = g_millis + 1; if (g_millis >= DEBOUNCE_DELAY_MS) g_flg = true; } // Motor Speed switch (переключатель скорости двигателя) ISR(INT0_vect) { if (g_flg) { g_postEvent = SPEED_MASK; g_millis = 0; g_flg = false; } } // Motor stop switch (переключатель остановки двигателя) ISR(INT1_vect) { if (g_flg) { g_postEvent = STOP_MASK; g_millis = 0; g_flg = false; } } |
Основной цикл в функции main проверяет свойство g_postEvent и если его значение не 0, а оно корректно, то это значение передается в метод конечного автомата PostEvent чтобы обработать переход в следующее состояние если переход правомерен. Затем свойству g_postEvent присваивается значение 0 и программа переходит в режим ожидания появления события нажатия какой либо из кнопок.
1 2 3 4 5 6 7 8 9 10 11 |
// Nothing to do here (ничего не делаем здесь) while (1) { if (g_postEvent) { fsm.PostEvent(g_postEvent); g_postEvent = 0; } _delay_ms(100); } |
Метод конечного автомата PostEvent является "сердцем" нашего автомата, он производит итерацию списка переходов проверяя при этом входные параметры на предмет появления события, которое приводит к переходу, и если обнаруживается совпадение, то вызывается метод ExitAction. Затем может вызываться метод EntryAction. Таким образом, метод PostEvent обрабатывает методы EntryAction, HandleTransitionEvent и ExitAction.
Как видите, код конечного автомата достаточно прост и оставляет всю "тяжелую" работу производным классам.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
void CFiniteStateMachine::PostEvent(uint16_t param) { if (mp_currentState == nullptr) return; CTransition* ptrans = nullptr; volatile uint8_t len = mp_currentState->GetTransitionCount(); for (uint8_t i = 0; i < len; i++) { ptrans = mp_currentState->mpa_transitions[i]; // The default si to compare param to the m_value action and // return true is they match, butthis behavior may be // overriden if custom behavior is required. if (ptrans->HandleTransionEvent(param)) { // Invoke the transitiong states ExitAction virtual method // to provide functionality needed before transitioning to // the new state and give user a chance to peek at the data // and cancel the transition if return is true. if (!mp_currentState->ExitAction(param)) { mp_currentState = ptrans->mp_target; // Invoke the new states virtual EnterAction method to // provide initialization, as needed by new state. mp_currentState->EnterAction(param); } break; } } } |
Мы использовали тип uint16_t для свойства TransitionAction потому что на практике большинство датчиков, с которыми приходится работать, работают именно с 16-битными значениями. Если же эти значения не 16-битные, то их можно принудительно преобразовать в формат 16 бит (uint16_t).
Видео про конечные автоматы
Также в сети доступно обучающее видео про конечные автоматы для микроконтроллеров AVR. Поскольку его автор разрешил использование (встраивание) данного видео на других ресурсах выкладываю его здесь. Оно поможет вам закрепить и систематизировать знания, полученные при прочтении данной статьи.
Наш стартап на базе разработанного нами IDE развивает тему Switch технологии автоматного программирования.
И мы предприняли попытку посмотреть представить FSM не в виде типа программирования, а в виде графической интерфейсной абстракции визуализированного настраиваемого прибора, который несет в себе возможность настроки состояний входных и выходных потоков, управление ими во времени и в группе с другими такими конечными автоматами, кроме того сама по себе IDE выполняет функции кологенерации, т.е. работу на аппаратном уровне при подключенных I/O и настраиваемых коммуникациях.
Alex, спамить ведь не хорошо, можно же договориться о покупке рекламы, тем более что сейчас законом об обязательной маркировке рекламы в сети предусмотрены штрафы до 500 тыс. за такой вот спам
Всего лишь поделился своей темой в контексте Вашего блога.
Без ссылок на первоисточники невозможно предметно вести диспут.
Впрочем Вы админ, Вам решать, хотите удаляйте, хотите нет.
К слову я не обнаружил здесь правил, которые что либо оговаривают и при отправке я никаких предупреждений не увидал.
Будем считать что диалог не состоялся.
Ну я не могу же совсем ссылки в комментариях запретить, люди же оставляют полезные ссылки и на гитхаб, и на яндекс диск и т.д. Просто в вашем посте не диспут, а явная реклама
Непонятно откуда берутся классы: CState и CFiniteStateMachine?
CState мы объявляем в самом первом фрагменте кода, а CFiniteStateMachine - в последнем
Вы не могли бы уточнить в каких строка определяются эти классы? Я в С++ не силен, но только вижу, что в первом фрагменте несколько классов лишь наследуются от CState. А в последнем фрагменте определяется только одна из функций класса CFiniteStateMachine.
Да, скорее всего вы правы, я бегло посмотрел. Но на источнике, откуда я этот пример копировал, больше никаких фрагментов кода нет, к сожалению. Не готов пока сказать как лучше поступить, нужно подумать