Конечные автоматы в микроконтроллерах AVR


В данной статье мы рассмотрим такой интересный стиль программирования микроконтроллеров как автоматное программирование. Точнее это даже не стиль программирования а целая концепция, благодаря которой программист микроконтроллеров может существенно облегчить свою жизнь. Благодаря ей многие задачи, поставленные перед программистом, решаются гораздо легче и проще, избавляя программиста от многих сложностей. Автоматное программирование часто также называют 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) автомата. И деятельность, и действие автомата относятся к его выходной активности.

При этом действием называется выходное воздействие, выполняемое однократно при входе в состояние или на переходе, а деятельностью – выходное воздействие, выполняющееся непрерывно в течение всего времени нахождения автомата в определенном состоянии. Также возможна реализация действий, выполняющихся на выходе из состояния.

Автомат Мура и автомат смешанного типа могут выполнять как действия, так и деятельности, а автомат Мили может выполнять только действия.

В минимальном виде объявление автомата можно записать так:

Минимальный вид объявления конечного автомата

А описание автомата выглядит следующим образом:

Пример описания конечного автомата (часть 1)

Пример описания конечного автомата (часть 2)

Приведенное описание соответствует автомату Мили, который имеет два состояния: активное и неактивное, а также два входа: сообщения MSG_FSM1_ACTIVATE и MSG_FSM1_DEACTIVATE, которые переводят автомат в активное и неактивное состояние соответственно. Граф этого автомата представлен на следующем рисунке.

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

Данный автомат выполняет действия на переходах из одного состояния в другое (именно поэтому это автомат Мили), однако его достаточно легко преобразовать в автомат Мура или в смешанный автомат. Представленный на рисунке автомат не делает ничего полезного, это просто шаблон, на основе которого можно строить автоматы с более сложным поведением.

Пример использования конечных автоматов в микроконтроллерах AVR

Для демонстрации возможностей конечных автоматов в микроконтроллерах AVR используем схему, представленную на следующем рисунке.

Схема для демонстрации использования конечных автоматов в микроконтроллерах AVR

Как видите, в ней нет ничего сложного: в ней используется микроконтроллер AVR ATMEGA328P-PU, 2 кнопки, двигатель и несколько других компонентов для увеличения скорости двигателя за 3 шага с использованием широтно-импульсной модуляции. В любом состоянии двигатель может быть остановлен с помощью 2-го переключателя, и система переходит в состояние холостого хода.

Компоненты в представленной схеме можно заменить на те, которые у вас есть под рукой. Не обязательно в точности такие же как на схеме. Как видно из схемы, двигатель вращается только в одном направлении, это было сделано для того, чтобы максимально упростить логику работы проекта и использовать минимальное количество компонентов.

Для управления скоростью вращения двигателя мы будем использовать ШИМ (широтно-импульсную модуляцию) и с помощью таймера Timer2 микроконтроллера будем изменять коэффициент заполнения ШИМ сигнала: 35% для SPEED1, 70% для SPEED2 и 100% для SPEED3. Более подробно об использовании ШИМ в микроконтроллерах AVR можно прочитать в этой статье.

На следующем рисунке представлена таблица состояний и переходов для нашего проекта. Итого имеем 4 состояния и 6 переходов, но переходы из различных состояний скорости (Speed States) в холостое состояние (Idle) похожи друг на друга, поэтому не требуют дополнительного кода.

Таблица состояний и переходов для нашего конечного автомата

В графическом виде диаграмма состояний и переходов для нашего проекта представлена на следующем рисунке.

Диаграмма состояний и переходов для нашего проекта

В следующем фрагменте кода представлена логика обработки этой диаграммы состояний обычным способом – с использованием оператора switch. Конечно, это решение кажется значительно проще чем то решение, которое мы выполним с помощью конечных автоматов. Но оно гораздо сложнее масштабируется при увеличении количества состояний и с трудом поддается модификации.

Использование конечных автоматов

Конечные автоматы могут быть внедрены в программу для микроконтроллеров несколькими способами, к наиболее популярным из которых относятся следующие: вызов методов Entry, Post и Exit и использование наследования. В нашем случае мы будем использовать наследование.

Классы в следующем фрагменте кода являются производными классами (derived classes).

Класс CStateBase в приведенном коде объявляет статические методы Start и Stop, которые потом используют все производные классы. Нам необходимо просто скопировать методы, помеченные как статические.

Следующий фрагмент программы содержит код для производных классов и он наглядно показывает как просто программа может выглядеть в данном случае и как просто ее потом можно масштабировать в случае необходимости.

Хотя представленные классы сами по себе делают относительно мало "работы", но зато они наглядно показывают как всю рассматриваемую проблему можно разделить на несколько легко управляемых фрагментов, где каждое состояние (State) имеет уникальную роль в общей схеме.

Когда мы создавали экземпляры классов мы для состояний системы не прописывали ничего лишнего, мы просто объявляли эти состояния. Но переходы (Transitions) – это уже другая история и для них уже необходимо указать в какое состояние осуществляется переход и в результате какого действия.

Далее, в основной функции программы main мы будем добавлять различные состояния для нашего конечного автомата (FiniteStateMachine), добавлять переходы для состояний, с которыми они связаны, устанавливать в качестве активного состояния холостое состояние (Idle) и выполнять метод инициализации конечного автомата (CFiniteStateMachine's Initialize method), который перебирает массив состояний и выполняет заданные методы. В данном случае метод CIdle's Initialize используется для установки порта OC2A (PB3) в режим работы на вывод данных и останавливает таймер.

В следующем фрагменте кода мы настраиваем обработчик прерывания для Timer1, который формирует программную задержку для обоих кнопок (переключателей). Прерывания INT0 и INT1 обрабатывают нажатия кнопок по восходящему фронту импульса (rising edge). Свойство g_postEvent используется для того, чтобы отложить обработку события до тех пор пока не произойдет выход из обработчиков прерываний.

Основной цикл в функции main проверяет свойство g_postEvent и если его значение не 0, а оно корректно, то это значение передается в метод конечного автомата PostEvent чтобы обработать переход в следующее состояние если переход правомерен. Затем свойству g_postEvent присваивается значение 0 и программа переходит в режим ожидания появления события нажатия какой либо из кнопок.

Метод конечного автомата PostEvent является "сердцем" нашего автомата, он производит итерацию списка переходов проверяя при этом входные параметры на предмет появления события, которое приводит к переходу, и если обнаруживается совпадение, то вызывается метод ExitAction. Затем может вызываться метод EntryAction. Таким образом, метод PostEvent обрабатывает методы EntryAction, HandleTransitionEvent и ExitAction.

Как видите, код конечного автомата достаточно прост и оставляет всю "тяжелую" работу производным классам.

Мы использовали тип uint16_t для свойства TransitionAction потому что на практике большинство датчиков, с которыми приходится работать, работают именно с 16-битными значениями. Если же эти значения не 16-битные, то их можно принудительно преобразовать в формат 16 бит (uint16_t).

Видео про конечные автоматы

Также в сети доступно обучающее видео про конечные автоматы для микроконтроллеров AVR. Поскольку его автор разрешил использование (встраивание) данного видео на других ресурсах выкладываю его здесь. Оно поможет вам закрепить и систематизировать знания, полученные при прочтении данной статьи.



Комментарии

Конечные автоматы в микроконтроллерах AVR — 8 комментариев

  1. Наш стартап на базе разработанного нами IDE развивает тему Switch технологии автоматного программирования.
    И мы предприняли попытку посмотреть представить FSM не в виде типа программирования, а в виде графической интерфейсной абстракции визуализированного настраиваемого прибора, который несет в себе возможность настроки состояний входных и выходных потоков, управление ими во времени и в группе с другими такими конечными автоматами, кроме того сама по себе IDE выполняет функции кологенерации, т.е. работу на аппаратном уровне при подключенных I/O и настраиваемых коммуникациях.

    • Alex, спамить ведь не хорошо, можно же договориться о покупке рекламы, тем более что сейчас законом об обязательной маркировке рекламы в сети предусмотрены штрафы до 500 тыс. за такой вот спам

      • Всего лишь поделился своей темой в контексте Вашего блога.
        Без ссылок на первоисточники невозможно предметно вести диспут.
        Впрочем Вы админ, Вам решать, хотите удаляйте, хотите нет.
        К слову я не обнаружил здесь правил, которые что либо оговаривают и при отправке я никаких предупреждений не увидал.
        Будем считать что диалог не состоялся.

        • Ну я не могу же совсем ссылки в комментариях запретить, люди же оставляют полезные ссылки и на гитхаб, и на яндекс диск и т.д. Просто в вашем посте не диспут, а явная реклама

    • CState мы объявляем в самом первом фрагменте кода, а CFiniteStateMachine - в последнем

      • Вы не могли бы уточнить в каких строка определяются эти классы? Я в С++ не силен, но только вижу, что в первом фрагменте несколько классов лишь наследуются от CState. А в последнем фрагменте определяется только одна из функций класса CFiniteStateMachine.

        • Да, скорее всего вы правы, я бегло посмотрел. Но на источнике, откуда я этот пример копировал, больше никаких фрагментов кода нет, к сожалению. Не готов пока сказать как лучше поступить, нужно подумать

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *