Я создаю небольшой проект на смешанных C и C ++. Я строю один маленький конечный автомат в основе одного из моих рабочих потоков.
Мне было интересно, если бы вы, гуру из SO, поделились своими методами проектирования конечных автоматов.
ПРИМЕЧАНИЕ: я в первую очередь после проверенных и проверенных методов реализации.
ОБНОВЛЕНО: Основываясь на всех замечательных материалах, собранных на SO, я остановился на этой архитектуре:
c++
c
architecture
state-machine
jldupont
источник
источник
Ответы:
Конечные автоматы, которые я разработал ранее (C, а не C ++), все сводятся к
struct
массиву и циклу. Структура в основном состоит из состояния и события (для просмотра) и функции, которая возвращает новое состояние, что-то вроде:Затем вы определяете свои состояния и события с помощью простых определений (
ANY
это специальные маркеры, см. Ниже):Затем вы определяете все функции, которые вызываются переходами:
Все эти функции написаны так, чтобы не принимать переменные и возвращать новое состояние для конечного автомата. В этом примере глобальные переменные используются для передачи любой информации в функции состояния, где это необходимо.
Использование глобальных переменных не так плохо, как кажется, поскольку FSM обычно блокируется внутри одного модуля компиляции, и все переменные являются статическими по отношению к этому модулю (именно поэтому я использовал кавычки вокруг «global» выше - они более распространены внутри ФСМ, чем истинно глобальный). Как и во всех глобальных, он требует осторожности.
Затем массив переходов определяет все возможные переходы и функции, которые вызываются для этих переходов (включая последний из них для всех):
Это означает следующее: если вы находитесь в
ST_INIT
штате и получаетеEV_KEYPRESS
событие, позвонитеGotKey
.Работа FSM становится относительно простым циклом:
Как упоминалось выше, обратите внимание на использование в
ST_ANY
качестве подстановочных знаков, позволяющих событию вызывать функцию независимо от текущего состояния.EV_ANY
также работает аналогично, позволяя любому событию в определенном состоянии вызывать функцию.Это также может гарантировать, что, если вы дойдете до конца массива переходов, вы получите сообщение о том, что ваш FSM не был построен правильно (с помощью
ST_ANY/EV_ANY
комбинации.Я использовал подобный код для очень многих коммуникационных проектов, таких как ранняя реализация стеков связи и протоколов для встроенных систем. Большим преимуществом была его простота и относительная легкость в изменении массива переходов.
Я не сомневаюсь, что будут абстракции более высокого уровня, которые могут быть более подходящими в настоящее время, но я подозреваю, что все они сводятся к такой же структуре.
И, как
ldog
говорится в комментарии, вы можете полностью избежать глобальных переменных, передавая структурный указатель всем функциям (и используя его в цикле обработки событий). Это позволит нескольким конечным автоматам работать без помех.Просто создайте тип структуры, который содержит специфичные для машины данные (состояние как минимум) и используйте их вместо глобальных.
Причина, по которой я редко это делал, заключается просто в том, что большинство машин состояний, которые я написал, были одноэлементными (например, одноразовые, при запуске процесса, чтение файла конфигурации), не требуя запуска более одного экземпляра. , Но это имеет значение, если вам нужно запустить более одного.
источник
int (*fn)(void*);
гдеvoid*
будет указатель на данные, которые каждая функция состояния принимает в качестве параметра. Тогда функции состояния могут либо использовать данные, либо игнорировать их.Другие ответы хороши, но очень «легкая» реализация, которую я использовал, когда конечный автомат очень прост, выглядит так:
Я бы использовал это, когда конечный автомат достаточно прост, чтобы подход с указателем функции и таблицей переходов состояний был излишним. Это часто полезно для посимвольного или пословного разбора.
источник
Извините, что нарушил все правила в информатике, но конечный автомат - одно из немногих (я могу считать только два) мест, где
goto
утверждение не только более эффективно, но и делает ваш код чище и легче для чтения. Посколькуgoto
операторы основаны на метках, вы можете называть свои состояния вместо того, чтобы отслеживать беспорядок чисел или использовать перечисление. Это также делает код намного чище, так как вам не нужны все лишние указатели на функции или огромные операторы switch и while. Я уже говорил, что это более эффективно?Вот как может выглядеть конечный автомат:
Вы получите общую идею. Дело в том, что вы можете реализовать конечный автомат эффективным способом, который относительно легко читается и кричит читателю, что он смотрит на конечный автомат. Обратите внимание, что если вы используете
goto
заявления, вы все равно должны быть осторожны, так как при этом очень легко выстрелить себе в ногу.источник
Вы можете рассмотреть State Machine Compiler http://smc.sourceforge.net/
Эта великолепная утилита с открытым исходным кодом принимает описание конечного автомата на простом языке и компилирует его на любой из дюжины или около того языков, включая C и C ++. Сама утилита написана на Java и может быть включена как часть сборки.
Причина, по которой это делается, а не ручное кодирование с использованием шаблона состояния GoF или любого другого подхода, заключается в том, что после того, как ваш конечный автомат выражается в виде кода, базовая структура имеет тенденцию исчезать под весом стандартного шаблона, который необходимо сгенерировать для его поддержки. Использование этого подхода дает вам отличное разделение задач, и вы сохраняете структуру своего конечного автомата «видимой». Автоматически сгенерированный код входит в модули, к которым вам не нужно прикасаться, чтобы вы могли вернуться и поиграть со структурой конечного автомата, не влияя на написанный вами вспомогательный код.
Извините, я преувеличиваю и, несомненно, откладываю всех. Но это первоклассная утилита, и хорошо документированная тоже.
источник
Обязательно проверьте работу Миро Самека (блог State Space , сайт State Machines & Tools ), чьи статьи в C / C ++ Users Journal были замечательными.
Веб-сайт содержит полную (C / C ++) реализацию как с открытым исходным кодом, так и с коммерческой лицензией платформы конечного автомата (QP Framework) , обработчик событий (QEP) , базовый инструмент моделирования (QM) и инструмент трассировки (QSpy), который позволяют рисовать конечные автоматы, создавать код и отлаживать их.
Книга содержит подробное объяснение того, что / почему для реализации и как ее использовать, а также является отличным материалом для понимания основ иерархических и конечных автоматов.
Веб-сайт также содержит ссылки на несколько пакетов поддержки плат для использования программного обеспечения со встроенными платформами.
источник
Я сделал нечто похожее на то, что описывает paxdiablo, только вместо массива переходов между состояниями и событиями я установил двумерный массив указателей функций со значением события в качестве индекса одной оси и значением текущего состояния в виде другой. Тогда я просто звоню,
state = state_table[event][state](params)
и происходит правильная вещь. Ячейки, представляющие недопустимые комбинации состояния / события, получают указатель на функцию, которая так говорит, конечно.Очевидно, это работает только в том случае, если значения состояния и события являются смежными диапазонами и начинаются с 0 или достаточно близко.
источник
#define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...
(подразумеваемый символ новой строки после каждого\
), в которых вы (пере) определяете макрос ввода при использовании макроса STATE_LIST. Пример - создание массива названий состояний:#define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY
. Некоторая работа сначала настраивается, но это очень мощно. Добавить новое состояние -> гарантированно без промахов.Стефан Хайнцманн (Stefan Heinzmann) в своей статье дал замечательную «основу» конечного автомата C ++ на основе шаблонов. .
Поскольку в статье нет ссылки на полную загрузку кода, я позволил себе вставить код в проект и проверить его. Материал ниже тестируется и включает в себя несколько незначительных, но довольно очевидных недостающих частей.
Основным нововведением здесь является то, что компилятор генерирует очень эффективный код. Пустые действия входа / выхода бесплатны. Непустые действия входа / выхода встроены. Компилятор также проверяет полноту диаграммы состояний. Пропущенные действия приводят к ошибкам компоновки. Единственное, что не пойман, это пропавший
Top::init
.Это очень хорошая альтернатива реализации Miro Samek, если вы можете жить без того, чего не хватает - это далеко от полной реализации UML Statechart, хотя она правильно реализует семантику UML, тогда как код Samek по своему дизайну не обрабатывает выход / переход / вход действия в правильном порядке.
Если этот код работает для того, что вам нужно, и у вас есть приличный компилятор C ++ для вашей системы, он, вероятно, будет работать лучше, чем реализация Miro C / C ++. Компилятор сгенерирует для вас плоскую реализацию конечного автомата O (1). Если аудит результатов сборки подтверждает, что оптимизации работают так, как вам нужно, вы приближаетесь к теоретической производительности. Лучшая часть: это относительно крошечный, легкий для понимания код.
Тестовый код следует.
источник
Техника, которая мне нравится для конечных автоматов (по крайней мере, для управления программами), заключается в использовании указателей функций. Каждое состояние представлено другой функцией. Функция принимает входной символ и возвращает указатель функции для следующего состояния. Мониторы центрального диспетчерского контура принимают следующий вход, подают его в текущее состояние и обрабатывают результат.
Печатание на нем становится немного странным, так как C не может указать типы указателей на функции, возвращающие себя, поэтому функции состояния возвращают
void*
. Но вы можете сделать что-то вроде этого:Тогда ваши индивидуальные функции состояния могут включить их ввод для обработки и вернуть соответствующее значение.
источник
Самый простой случай
Точки: State является приватным, не только для модуля компиляции, но и для обработчика события. Особые случаи могут обрабатываться отдельно от главного коммутатора с использованием любой конструкции, которая будет сочтена необходимой.
Более сложный случай
Когда коммутатор заполнится больше, чем на пару экранов, разделите его на функции, которые обрабатывают каждое состояние, используя таблицу состояний для непосредственного поиска функции. Состояние по-прежнему закрыто для обработчика событий. Функции обработчика состояния возвращают следующее состояние. При необходимости некоторые события могут получить специальную обработку в главном обработчике событий. Мне нравится добавлять псевдо-события для входа и выхода из состояния и, возможно, запуска конечного автомата:
Я не уверен, прибил ли я синтаксис, особенно относительно массива указателей на функции. Я не запускал ничего из этого через компилятор. После проверки я заметил, что забыл явно отбрасывать следующее состояние при обработке псевдо-событий (скобка (void) перед вызовом state_handler ()). Это то, что мне нравится делать, даже если компиляторы молча принимают это упущение. Он сообщает читателям кода, что «да, я действительно имел в виду вызов функции без использования возвращаемого значения», и это может помешать инструментам статического анализа предупреждать об этом. Это может быть своеобразным, потому что я не помню, чтобы кто-нибудь еще делал это.
Точки: добавление крошечной сложности (проверка, отличается ли следующее состояние от текущего), может избежать дублирования кода в другом месте, потому что функции обработчика состояний могут наслаждаться псевдо-событиями, которые происходят при входе и выходе из состояния. Помните, что состояние не может измениться при обработке псевдо-событий, потому что результат обработчика состояния отбрасывается после этих событий. Вы, конечно, можете изменить поведение.
Обработчик состояния будет выглядеть так:
Больше сложности
Когда модуль компиляции становится слишком большим (что бы вы ни чувствовали, я бы сказал, около 1000 строк), поместите каждый обработчик состояний в отдельный файл. Когда каждый обработчик состояния становится длиннее пары экранов, каждое событие разделяется на отдельную функцию, аналогично тому, как был разделен переключатель состояния. Вы можете сделать это несколькими способами, отдельно от государства или с помощью общей таблицы, или комбинируя различные схемы. Некоторые из них были охвачены здесь другими. Сортируйте таблицы и используйте бинарный поиск, если требуется скорость.
Общее программирование
Мне бы хотелось, чтобы препроцессор имел дело с такими проблемами, как сортировка таблиц или даже создание конечных автоматов из описаний, позволяющих вам «писать программы о программах». Я полагаю, что это то, для чего люди Boost используют шаблоны C ++, но я нахожу синтаксис загадочным.
Двумерные таблицы
В прошлом я использовал таблицы состояний / событий, но должен сказать, что для простейших случаев я не нахожу их необходимыми и предпочитаю ясность и удобочитаемость оператора switch, даже если он выходит за пределы одного полного экрана. Для более сложных случаев таблицы быстро выходят из-под контроля, как отмечали другие. Приводимые здесь идиомы позволяют вам добавлять массу событий и состояний, когда вам это нравится, без необходимости поддерживать таблицу, потребляющую память (даже если это может быть память программы).
отказ
Особые потребности могут сделать эти идиомы менее полезными, но я обнаружил, что они очень ясны и понятны.
источник
Крайне непроверенный, но забавный код, теперь в более изысканной версии, чем мой первоначальный ответ; Актуальные версии можно найти на mercurial.intuxication.org :
sm.h
example.c
источник
Мне очень понравился ответ paxdiable, и я решил реализовать все недостающие функции для моего приложения, такие как защитные переменные и данные, относящиеся к конечному автомату.
Я загрузил свою реализацию на этот сайт, чтобы поделиться с сообществом. Он был протестирован с использованием IAR Embedded Workbench для ARM.
https://sourceforge.net/projects/compactfsm/
источник
Еще один интересный инструмент с открытым исходным кодом - Yakindu Statechart Tools на statecharts.org . Он использует диаграммы состояний Harel и, таким образом, обеспечивает иерархические и параллельные состояния и генерирует код C и C ++ (а также Java). Он не использует библиотеки, но следует подходу «простого кода». Код в основном применяет структуры switch-case. Генераторы кода также могут быть настроены. Кроме того, инструмент предоставляет множество других функций.
источник
Приходя к этому поздно (как обычно), но просматривая ответы на сегодняшний день, я думаю, что чего-то важного не хватает;
Я обнаружил в своих собственных проектах, что это может быть очень полезно для не иметь функции для каждой действительной комбинации состояния / события. Мне нравится идея эффективно иметь 2D таблицу состояний / событий. Но мне нравится, что элементы таблицы больше, чем простой указатель на функцию. Вместо этого я пытаюсь организовать свой дизайн так, чтобы в его основе было множество простых атомарных элементов или действий. Таким образом, я могу перечислить эти простые атомарные элементы на каждом пересечении моей таблицы состояний / событий. Идея состоит в том, что вам не нужно определять массу из N квадратов (обычно очень простых) функций. Почему есть что-то такое подверженное ошибкам, трудоемкое, трудное для написания, трудное для чтения, назовите это?
Я также включаю необязательное новое состояние и необязательный указатель функции для каждой ячейки в таблице. Указатель на функцию существует для тех исключительных случаев, когда вы не хотите просто запускать список атомарных действий.
Вы знаете, что делаете это правильно, когда вы можете выразить множество различных функций, просто редактируя свою таблицу, без необходимости писать новый код.
источник
В общем, я думаю, что мой немного отличается от всех остальных. Чуть больше разделения кода и данных, чем я вижу в других ответах. Я действительно прочитал теорию, чтобы написать это, которая реализует полный Regular-язык (без регулярных выражений, к сожалению). Ульман, Минский, Хомский. Не могу сказать, что все понял, но я обратился к старым мастерам как можно более прямо: через их слова.
Я использую указатель функции на предикат, который определяет переход в состояние «да» или «нет». Это облегчает создание конечного акцептора состояний для обычного языка, который вы программируете более похожим на ассемблер. Пожалуйста, не откладывай на мой глупый выбор имени. 'czek' == 'проверить'. 'grok' == [посмотрите в словаре хакеров].
Поэтому для каждой итерации czek вызывает функцию предиката с текущим символом в качестве аргумента. Если предикат возвращает true, символ потребляется (указатель продвинут), и мы следуем переходу «y», чтобы выбрать следующее состояние. Если предикат возвращает false, символ НЕ используется, и мы следуем переходу 'n'. Так что каждая инструкция - это двусторонняя ветвь! Должно быть, я читал «Историю Мела» в то время.
Этот код взят прямо из моего постскриптумного интерпретатора и развился в его нынешнюю форму под большим руководством коллег по comp.lang.c. Так как postscript в основном не имеет синтаксиса (требующего только сбалансированных скобок), Regular Language Accepter, подобный этому, также работает как синтаксический анализатор.
источник
boost.org поставляется с 2 различными реализациями диаграмм состояний:
Как всегда, boost перенесет вас в адский шаблон.
Первая библиотека предназначена для более критичных к производительности машин состояния. Вторая библиотека дает вам прямой путь перехода от UML Statechart к коду.
Вот SO вопрос, требующий сравнения между двумя, где оба автора отвечают.
источник
Эта серия публикаций Ars OpenForum о довольно сложной логике управления включает очень простую реализацию в качестве конечного автомата в C.
источник
Видел это где-то
источник
goto
которых создает зависимость от более ранней многозадачной ОС.Учитывая, что вы подразумеваете, что вы можете использовать C ++ и, следовательно, OO-код, я бы посоветовал оценить шаблон GoF'state (GoF = Gang of Four, ребята, которые написали книгу шаблонов проектирования, которая вывела шаблоны проектирования в центр внимания).
Он не особенно сложен и широко используется и обсуждается, поэтому легко увидеть примеры и объяснения в режиме онлайн.
Вполне вероятно, что кто-то еще будет поддерживать ваш код на более позднем этапе.
Если проблема заключается в эффективности, стоило бы провести сравнительный анализ, чтобы убедиться, что подход без ООП более эффективен, так как на производительность влияет множество факторов, и это не всегда просто ОО-плохо, функциональный код хорош. Точно так же, если использование памяти является ограничением для вас, снова стоит провести несколько тестов или вычислений, чтобы увидеть, действительно ли это будет проблемой для вашего конкретного приложения, если вы используете шаблон состояния.
Ниже приводятся некоторые ссылки на шаблон состояния «Gof», как предлагает Крейг:
источник
Вот пример конечного автомата для Linux, который использует очереди сообщений в качестве событий. События помещаются в очередь и обрабатываются по порядку. Состояние меняется в зависимости от того, что происходит для каждого события.
Это пример подключения к данным с такими состояниями, как:
Одна небольшая дополнительная функция, которую я добавил, была отметка времени для каждого сообщения / события. Обработчик событий будет игнорировать слишком старые события (срок их действия истек). Это может случиться много в реальном мире, где вы можете неожиданно застрять в состоянии.
Этот пример работает на Linux, используйте Makefile ниже, чтобы скомпилировать его и поэкспериментировать с ним.
state_machine.c
Makefile
источник
Ваш вопрос довольно общий,
вот две справочные статьи, которые могут быть полезны,
Реализация встроенного конечного автомата
источник
Я с успехом использовал State Machine Compiler в проектах Java и Python.
источник
Это старый пост с множеством ответов, но я подумал, что добавлю свой собственный подход к конечному автомату в C. Я создал скрипт Python, чтобы создать скелетный C-код для любого количества состояний. Этот скрипт задокументирован на GituHub в FsmTemplateC
Этот пример основан на других подходах, о которых я читал. Он не использует операторы goto или switch, но вместо этого имеет функции перехода в матрице указателей (справочная таблица). Код опирается на большой многострочный макрос инициализатора и функции C99 (обозначенные инициализаторы и составные литералы), поэтому, если вам не нравятся эти вещи, вам может не понравиться такой подход.
Вот скрипт Python примера турникета, который генерирует C-код скелета, используя FsmTemplateC :
Сгенерированный выходной заголовок содержит typedefs:
eFsmTurnstileCheck
используется, чтобы определить, был ли переход заблокированEFSM_TURNSTILE_TR_RETREAT
, разрешен ли переходEFSM_TURNSTILE_TR_ADVANCE
, или вызову функции не предшествовал переход сEFSM_TURNSTILE_TR_CONTINUE
.eFsmTurnstileState
- это просто список состояний.eFsmTurnstileInput
- это просто список входных данных.FsmTurnstile
является сердцем конечного автомата с проверкой перехода, таблицей поиска функций, текущим состоянием, заданным состоянием и псевдонимом основной функции, которая запускает машину.FsmTurnstile
должен вызываться только из структуры и должен иметь свой первый вход в качестве указателя на себя, чтобы поддерживать постоянное состояние, объектно-ориентированный стиль.Теперь для объявлений функций в заголовке:
Имена функций имеют формат
{prefix}_{from}_{to}
, в котором{from}
находится предыдущее (текущее) состояние и{to}
следующее состояние. Обратите внимание, что если таблица переходов не допускает определенные переходы, вместо указателя функции будет установлен указатель NULL. Наконец, магия случается с макросом. Здесь мы строим таблицу переходов (матрицу перечислений состояний) и таблицу поиска функций перехода состояний (матрицу указателей функций):При создании автомата необходимо использовать макрос
FSM_EXAMPLE_CREATE()
.Теперь в исходном коде должны быть указаны все функции перехода состояний, объявленные выше. Структура
FsmTurnstileFopts
может использоваться для передачи данных в / из конечного автомата. Каждый переход долженfsm->check
быть равен либоEFSM_EXAMPLE_TR_RETREAT
блокированию перехода, либоEFSM_EXAMPLE_TR_ADVANCE
разрешению перехода в заданное состояние. Рабочий пример можно найти по адресу (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] .Вот очень простое фактическое использование в вашем коде:
Весь этот бизнес заголовков и все эти функции только для того, чтобы иметь простой и быстрый интерфейс, стоит того, чтобы я думал.
источник
Вы можете использовать библиотеку с открытым исходным кодом OpenFST .
источник
источник
Лично я использую самоссылочные структуры в сочетании с массивами указателей. Некоторое время назад я загрузил учебник на github, ссылка:
https://github.com/mmelchger/polling_state_machine_c
Примечание: я понимаю, что этот поток довольно старый, но я надеюсь получить информацию и соображения по поводу дизайна конечного автомата, а также предоставить пример возможного проекта конечного автомата в C.
источник
Вы можете рассмотреть UML-state-machine-in-c , «облегченную» структуру конечного автомата в C. Я написал эту среду для поддержки как конечного автомата, так и иерархического конечного автомата. . По сравнению с таблицами состояний или простыми случаями переключения, каркасный подход более масштабируем. Его можно использовать для простых конечных автоматов и сложных иерархических конечных автоматов.
Конечный автомат представлен
state_machine_t
структурой. Он содержит только два члена «Event» и указатель на «state_t».state_machine_t
должен быть первым членом вашей структуры конечного автомата. напримерstate_t
содержит обработчик состояния, а также необязательные обработчики для действий входа и выхода.Если структура настроена для иерархического конечного автомата, то
state_t
содержит указатель на родительское и дочернее состояние.Framework предоставляет API
dispatch_event
для отправки события на конечный автомат иswitch_state
для запуска перехода состояния.Для получения дополнительной информации о том, как реализовать иерархический конечный автомат, обратитесь к репозиторию GitHub .
примеры кода,
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md https://github.com/kiishor/UML-State-Machine-in-C /blob/master/demo/simple_state_machine_enhanced/readme.md
источник
Вот метод для конечного автомата, который использует макросы так, что каждая функция может иметь свой собственный набор состояний: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -в
Он называется «имитировать многозадачность», но это не единственное использование.
Этот метод использует обратные вызовы для захвата в каждой функции, где он остановился. Каждая функция содержит список состояний, уникальных для каждой функции. Центральный «холостой цикл» используется для запуска конечных автоматов. «Цикл простоя» не имеет представления о том, как работают конечные автоматы, это отдельные функции, которые «знают, что делать». Чтобы написать код для функций, нужно просто создать список состояний и использовать макросы для «приостановки» и «возобновления». Я использовал эти макросы в Cisco, когда писал библиотеку Transceiver для коммутатора Nexus 7000.
источник