простой
пример из учебника: задачу, ориентированную на состояния. Попробуем найти подходящую реализацию на конечном автомате. В этом случае существует два разных решения, каждое со своими преимуществами и недостатками, и выбор зависит от оценки их плюсов и минусов.

Задача: «Оживленная главная дорога пересекается с малозагруженной местной дорогой. Вдоль местной дороги установлены датчики, которые включают сигнал C, когда транспортное средство ожидает пересечения главной дороги. Контроллер светофора должен работать следующим образом: пока на местной дороге не обнаружено транспортное средство, светофоры должны оставаться зелеными в направлении главной дороги. Если транспортное средство обнаружено на местной дороге, светофоры на главной дороге должны сменить цвет с желтого на красный, позволяя светофорам на местной дороге загореться зеленым. Светофоры на местной дороге остаются зелеными всякий раз, когда на местной дороге обнаружено транспортное средство, и никогда не остаются зелеными в течение заданного интервала времени, чтобы обеспечить движение транспорта по главной дороге. Если эти условия выполняются, светофоры на местной дороге сменят цвет с зеленого на желтый, а затем на красный, позволяя светофорам на главной дороге снова загореться зеленым. Даже если транспортные средства ожидают пересечения главной дороги, она должна оставаться зеленой в течение заданного интервала времени».¹
Это упражнение ориентировано на аппаратную часть, но с небольшой долей вольности его можно адаптировать для программной среды. Обратите внимание, что в примере используется условное обозначение, согласно которому желтый свет всегда появляется сам по себе (в некоторых частях мира используются другие условности). Но это на самом деле не влияет на сложность задачи; это просто упрощает отслеживание возможных цветовых комбинаций.

Простой подход к проектированию конечных автоматов можно описать следующим образом:

1. Идентификация событий и действий;
2. Идентификация состояний;
3. Группировка по иерархиям;
4. Группировка по параллелизму
; 5. Добавление переходов;
6. Добавление синхронизации.

Это не предписывающий рецепт, а скорее подход, который, как правило, будет полезен при структурировании решения, независимо от выбранных инструментов и методов реализации.

Давайте углубимся в тему.
Начнём с изучения описания проблемы, поиска возможных событий и действий. Что представляет собой событие в контексте конечного автомата? Проще говоря, событие — это триггер, который потенциально может привести к изменению состояния конечного автомата и выполнению какого-либо действия. В случае с семафорами мы можем обнаружить ряд потенциальных событий:

Интервалы задержки сами по себе не являются событиями; скорее, окончание интервала можно рассматривать как событие. На практике это оставляет нам два события: одно событие, связанное с длительным интервалом во время зеленого света на обеих дорогах, и другое событие, связанное с короткой, равномерной задержкой во время перехода между красным и зеленым светом и наоборот.
Таким образом, у нас остается три события, которые мы можем назвать LocalRoadTrafficEvent, LongEvent и ShortEvent.

Итак, что же в этой задаче считается действием? Изменение цвета светофора — типичное действие. Вопрос лишь в том, является ли изменение цвета на обеих дорогах одним или двумя действиями. Ответ на этот вопрос, по сути, зависит от соглашения. Мы можем рассматривать это как два отдельных действия, каждое из которых отвечает за одну из дорог, или как одно действие. Я предпочитаю рассматривать это как два отдельных действия, по причинам, которые станут ясны позже.
Я назвал эти действия ConfigureLocalRoadLight() и ConfigureMainRoadLight(); каждое действие принимает параметр цвета, указывающий желаемый цвет.

Идея заключается в том, что выбранные нами события будут вызывать изменения в определенных ситуациях, когда будут отображаться цвета светофора.
Нам также нужен способ отслеживания временных интервалов, поэтому мы вводим специальное действие, называемое действием таймера. Его цель — запустить счетчик таймера на заданный интервал и отслеживать событие, которое будет запущено, когда таймер достигнет своего конца. Для простоты мы назовем это действие таймера `ActionTemp()`.
Чтобы лучше понять логику управления системой светофора, нам необходимо знать возможные состояния и переходы между ними. Первое решение будет использовать следующие наблюдения:

в любой момент времени светофор будет отображать одну из следующих цветовых комбинаций: {ЗЕЛЕНЫЙ, КРАСНЫЙ}, {ЖЕЛТЫЙ, КРАСНЫЙ}, {КРАСНЫЙ, КРАСНЫЙ}, {КРАСНЫЙ, ЖЕЛТЫЙ}, {КРАСНЫЙ, ЗЕЛЕНЫЙ}, {КРАСНЫЙ, ЖЕЛТЫЙ}. Исходя из правил работы светофора, очевидно, что другие комбинации не должны быть разрешены, чтобы избежать создания рисков для транспорта, одновременно пересекающего перекресток обеих дорог. Первый цвет в каждой паре соответствует цвету светофора на главной дороге.
Существует фиксированная последовательность, в которой отображаются указанные выше цветовые комбинации: {ЗЕЛЕНЫЙ, КРАСНЫЙ}, {ЖЕЛТЫЙ, КРАСНЫЙ}, {КРАСНЫЙ, КРАСНЫЙ}, {КРАСНЫЙ, ЖЕЛТЫЙ}, {КРАСНЫЙ, ЗЕЛЕНЫЙ}, {КРАСНЫЙ, ЖЕЛТЫЙ}, {КРАСНЫЙ, КРАСНЫЙ}, {ЖЕЛТЫЙ, КРАСНЫЙ}, а затем возвращение к первой комбинации для начала заново.

Несложно увидеть каждый этап последовательности как возможное состояние, поскольку он явно включает состояние системы в данный момент времени. Переходы между состояниями будут запускаться различными временными интервалами для каждого изменения цвета. Предположим, что последовательность начинается с зеленого света на главной дороге, тогда вся последовательность запускается событием LocalRoadTrafficEvent.
Внимательный читатель заметит, что в последовательности цветовых комбинаций выше есть несколько дубликатов. Например, комбинация «оба светофора красные» встречается дважды. Следует ли рассматривать их как одно состояние или как два? Я решил рассматривать все позиции в последовательности как отдельные состояния. Это решение подразумевает, что переходы между состояниями должны быть максимально простыми.
У нас уже есть основа в виде набора событий, некоторых действий и набора потенциальных состояний.

На рисунке 2 представлена ​​схема в нотации UML. Предложенные состояния изображены в виде круга, а переходы названы в честь соответствующих событий. Состояния также имеют входные действия для изменения цвета светофора. Как видно, только для начального состояния необходимо настроить оба светофора, чтобы обеспечить корректный старт последовательности; для остальных состояний достаточно изменить цвет только одного светофора по сравнению с предыдущим состоянием. Это объясняет использование двух разных функций действий. Начальное состояние обозначается переходом между начальным и текущим состояниями, обозначенным маленьким кружком в верхнем левом углу.

В семантике UML начальное состояние и переход из него указывают на желаемое начальное состояние, что позволяет напрямую выразить инициализацию системы на диаграмме. Переход не содержит событий и подразумевается при запуске.
С точки зрения конечного автомата, эта схема почти завершена, но ей не хватает обработки минимального интервала зеленого света для главной дороги. Эту проблему можно решить несколькими способами, но следующее решение кажется довольно простым.

Введем небольшую иерархию в модель, создав конечный автомат внутри состояния MainGreen_LocalRed. Этот конечный автомат состоит из двух состояний плюс начальное псевдосостояние. При переходе в окружающее состояние активируется также состояние NewGreen.
Когда истекает длительный временной интервал, начавшийся при переходе в MainGreen_LocalRed, мы позволяем небольшому конечному автомату изменить состояние на LocalRoadEventOK. Теперь мы знаем, что минимальный интервал зеленого света для главной дороги истек, и теперь правильно (OK) «загорится зеленый» на местной дороге, если там есть движение.

Последним элементом, необходимым для поддержания минимального зеленого интервала на главной дороге, является «защита» при переходе из состояния GreenMain_RedLocal. Этот переход должен быть переопределен только в том случае, если срабатывает состояние LocalRoadEventOK. Это можно выразить как положительное состояние или положительную синхронизацию в переходе. Полученные изменения показаны на рисунке 3.

Это решение не идеально, поскольку оно не учитывает тот факт, что транспорт, прибывающий на местную дорогу во время минимального зеленого интервала на главной дороге, остается на месте до тех пор, пока не прибудет другой автомобиль после истечения интервала. Для решения этой проблемы необходимо регистрировать все события LocalRoadTrafficEvent, происходящие во время зеленого интервала, чтобы мы могли предпринять соответствующие действия по истечении интервала. Мы не будем рассматривать здесь полное решение проблемы, но если вы попытаетесь разработать решение, следующие пункты указывают на возможный путь вперед:

Ввести внутреннюю переменную оповещения в конечный автомат, которая сбрасывается до нуля при каждом переходе в зеленое состояние на главной дороге.
Ввести «внутреннюю реакцию» в зеленом состоянии главной дороги, которая срабатывает при получении события LocalRoadTrafficEvent, возможно, с состоянием защиты NewGreen.
«Реакцию входа» в состоянии LocalRoadEventOK, которая отправляет сигнал, если срабатывает оповещение при входе в это состояние (сигнал — это специальное событие, которое может отправлять сам конечный автомат).
Переход в желтое состояние, который запускает сигнал и короткий временной интервал.
Существуют и другие способы решения этой проблемы, но они требуют более сложного синтаксиса UML, который слишком обширен, чтобы рассматривать его здесь.

Программные конечные автоматы отличаются от своих аппаратных аналогов тем, что программный конечный автомат должен обнаруживать события в аппаратной среде и реагировать на них. Это означает, что вычислительная модель программных конечных автоматов основана на цикле «обнаружение-событие-реакция-на-событие», состоящем из дискретных шагов, тогда как аппаратный конечный автомат может реагировать «одновременно» на изменение сигнала на данном выводе. (Хотя фактическое изменение параметров логических элементов, конечно же, представляет собой дискретную активность на битовом уровне.) Например, набор аппаратных сигналов может быть объединен на логическом элементе для генерации события при наличии определенной комбинации сигналов на входе. В программной среде вам либо придется позволить драйверам прерываний и устройств выполнить это объединение, либо позволить это сделать конечному автомату. (Если, конечно, вы не контролируете аппаратную часть.)

Другой подход.
Как подчеркивалось в начале, существует как минимум один совершенно иной способ решения той же проблемы, который включает моделирование конечных автоматов как двух параллельных областей внутри одного и того же высокоуровневого конечного автомата. Преимущество этого подхода заключается в том, что полное решение можно рассматривать как систему, состоящую из отдельных и полунезависимых компонентов. Более подробное описание не позволяет привести все необходимые комментарии, но с ним можно ознакомиться онлайн по адресу www.iar.com/p236597/p236597_eng.php
.
Выбор конкретного решения не имеет большого значения, но в целом лучше максимально упростить задачу. Использование графического инструмента проектирования, такого как IAR visualSTATE, для проектирования конечных автоматов — это практичный способ повысить уровень абстракции, поскольку хороший инструмент обеспечивает поддержку таких аспектов, как генерация кода, тестирование и моделирование, а также проверка возможностей модели.

Автор: Андерс Холмберг, IAR Systems

Более подробная информация или запрос цены