Меню


Site Logo

Конечный автомат

Конечный автомат — это модель, используемая для описания поведения некоторой системы (в нашем случае программного модуля). Упрощённо, конечный автомат можно представить в виде двух конечных множеств: множества возможных состояний системы и множества возможных переходов между состояниями.

Формально конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых множеств: M = (V, Q, q0, F, d), где:

  • V – входной язык, сообщения, которые понимает автомат,
  • Q – множество состояний,
  • q0 – начальное состояние,
  • F – множество конечных состояний,
  • d – функция переходов.

Функционирование конечного автомата

В каждый момент времени модуль может находиться только в одном состоянии. В процессе функционирования модуль переходит из одного состояния (текущего) в другое (называемое «новым»).

В какие состояния возможен переход из текущего состояния определяется множеством возможных переходов из этого состояния. Оно определяет реакцию модуля в его текущем состоянии на какое-либо воздействие. В нашей системе таким воздействием является получение модулем сообщения. Сообщения, которыми могут обмениваться модули – типизированы (т.е. могут различаться по типу). Для каждого состояния это множество задает однозначное соответствие в какое состояние следует перейти получив определенное сообщение (сообщение определенного типа). При этом «новое» состояние может совпадать с текущим.

Таким образом «новое» состояние конечного автомата, описывающего поведение модуля, однозначно определяется текущим состоянием и типом полученного сообщения. А это значит, что модули реализуют детерминированное поведение, для описания которого используются детерминированные конечные автоматы.

В устойчивых состояниях модулю не нужно ничего делать! Он в них ждет событий.

Работа модуля происходит при обработке пришедшего события – сообщения: он может что-то запомнить, что-то попросить у кого-то, просто поменять состояние на новое, таким образом отметив, что что-то произошло.

Важно! Если ваш модуль что-то у кого-то попросил сделать, то узнать результат он может только получив ответ!

Фрагмент машины состояний

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

Обратите внимание на то, что наличие функции-обработчика для перехода не является обязательным. Сам факт перехода модуля в «новое» состояние сигнализирует об обработке модулем полученного сообщения-активатора.

Диалог модулей

Получив сообщение и поняв что требуется выполнить модулю часто требуется начать диалог с другими модулями. Прямого функционального вызова архитектурная модель не допускает. Следовательно и получить ответ как возврат из вызванной функции – тоже не выйдет. Нужно просить сообщением кого-то конкретного что-то выполнить. Узнать о том, что что-то выполнено можно только если будет получен ответ. Этот ответ нужно ждать. Ответ может иметь разную смысловую окраску (например: все получилось, ошибка, не понимаю запроса). А кроме того, может так выйти, что ответ может и не прийти.

Нужен механизм защиты от бесконечных ожиданий. Такой механизм обеспечивают таймеры.

Диалог модулей

Таймеры функционируют на состояниях. Можно указать для любого состояния максимальное допустимое время нахождения в нем. Если время нахождения в этом состоянии будет превышено будет автоматически помещено в очередь сообщений новое сообщение Kernel.TimeOut (тайм-аут). Обрабатывая его можно смоделировать необходимую по сценарию реакцию.

Пример:

Состояние с тайм-аутом

Величина тайм-аута указывается в миллисекундах.

Отсчёт тайм-аута начинается при переходе в состояние и перезапускается при получении любого сообщения, для которого предусмотрен переход из этого состояния ведущий в состояние, содержащее тайм-аут. Если в новом состоянии тайм-аут не указан, то отсчет запущен не будет. Если у состояния указан тайм-аут, то из него должен быть предусмотрен переход по событию Kernel.TimeOut.

Реакция модуля на сообщения

Все разрабатываемые модули реализуют поведение описываемое детерминированным конечным автоматом. Реакцией модуля на внешнее воздействие является переход модуля из текущего состояния в «новое». В процессе этой реакции модуль получает возможность выполнить обработку полученного сообщения-активатора перехода с помощью функции-обработчика, написанной на языке C++. Функция-обработчик вызывается в момент совершения перехода. В теле этой функции модуль может выполнить какие-то нужные действия. После выхода из функции-обработчика конечный автомат переходит в целевое состояние.

Обратите внимание, что наличие функции-обработчика для перехода не является обязательным. Сам факт перехода модуля в «новое» состояние сигнализирует об обработке модулем полученного сообщения-активатора.

При каждом переходе из состояния в состояние модулем генерируется специальное информационное сообщение – StateChanged (содержащее диагностическую информацию – в какое состояние перешел автомат и какое сообщение-активатор к этому привело).

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

Конечный автомат можно наглядно представить в виде ориентированного графа:

  • множество возможных состояний — соответствует множеству вершин графа;
  • множество возможных переходов — соответствует множеству рёбер графа.

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

Пример машины состояний

Также на графе можно указывать под входящим сообщением те исходящие сообщения, которые могут быть отправлены модулем при выполнении функции-обработчика перехода.

Пример:

Пример машины состояний

В зависимости от типы состояния конечного автомата графически изображаются по-разному:

  • Стартовое состояние (обязательно наличие, единственное).
    Стартовое состояние
  • Состояние с исключающей фильтрацией событий (неподходящие события удаляются из очереди и будут недоступны в дальнейшем).
    Состояние с исключающей фильтрацией
  • Состояние с игнорирующей фильтрацией событий (неподходящие события остаются в очереди и будут обработаны в последующих состояниях).
    Состояние с игнорирующей фильтрацией
  • Финальное состояние, из которого никакой переход не возможен. Имеющиеся в очереди необработанные события очищаются. (Может быть несколько).
    Конечное состояние

Создание конечного автомата

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

Модификация заготовки автомата

Модель конечного автомата создается в Microsoft Office Visio 2013.

Перед тем как делать модель на основе сценариев следует перечислить все состояния, в которых может находиться модуль. Имена состояний должны быть записаны на английском языке и не должны содержать пробелов.

Заготовка конечного автомата создается на основе стандартного шаблона. В этом шаблоне уже размещены начальное и конечное состояния. К ним следует добавить выделенные ранее состояния.

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

Например:

Переход

У некоторых состояний могут быть тайм-ауты. Следует указать эти тайм-ауты явно как показано ниже.

Состояние с тайм-аутом

Время тайм-аута указывается в миллисекундах. Если у состояния указан тайм-аут, то из него должен быть предусмотрен переход по событию Kernel.TimeOut.

Системные события

  • При разработке модели автомата можно предусмотреть реакцию на системные события – запуск (Kernel.Start), остановку (Kernel.Stop) и тайм-аут (Kernel.TimeOut).
  • Наши автоматы реализованы таким образом, что всегда при смене своего состояния отправляют событие Kernel.StateChanged, которое содержит информацию о том из какого в какое состояние машина перешла и по какому событию.

Пример

Ниже показан конечный автомат, реализующий цикл мерцания лампы-индикатора.

Пример машины состояний

Текстовое представление конечного автомата

В модули модель конечного автомата встраивается в форме мета-данных. Для этого графическая форма преобразуется в так называемое декларативное описание машины состояний. Обычно этот переход выполняется специальной утилитой-конвертером.

Правила текстового описания машин состояний:

  • Все конечные автоматы обладают уникальным именем, заданным в виде CamelCase. Имя машины состояний соответствует имени модуля.
  • Все конечные автоматы декларативно описываются в ключе реестра /Kernel/StateMachines.
  • Декларативное описание предполагает перечисление всех состояний, событий и переходов в автомате.
  • Состояния перечисляются в подключе States.
  • Переходы и атрибуты состояния (такие как тайм-аут) описываются его подключами.
  • Все переходы из состояния описываются в подключе Transitions.
  • Все атрибуты соответствуют подключам ключа состояния с одноименным (имени атрибута) именем, указанным в CamelCase. Значение такого ключа интерпретируется как значение атрибута.
  • Каждый переход описывается в подключе Transitions в виде <Событие> : <Состояние в которое переходим по событию>. Идентификаторы событий имеют стандартный формат <Протокол>.<Имя сообщения> и обязаны содержаться в реестре мета-данных в разделе Uniteller\Protocols (т.е. должны принадлежать какому-нибудь протоколу). В момент прихода события (указанного в Transitions) срабатывает переход. В этот момент вызывается функция-обработчик перехода в подложке C++. Имя этой функции определяется автоматически по имени состояний («из» и «в» а также типу события), соответствующая привязка выполняется в коде модуля на C++.
  • Для перехода можно указать какие типы событий может сгенерировать функция обработчик. Для этого необходимо создать подключ CanRaise и в его подключах перечислить все типы событий которые может сгенерировать функция-обработчик. Если функция сненерирует событие не из данного списка, будет сгенерирована ошибка ядра UnexpectedBehaviour.
  • Если функция-обработчик сгенерирует исключение, то ядро автоматически перехватит его и обеспечит генерацию ошибки ModuleFailedOnEvent.
  • Глобальные настройки машины состояний перечисляются в ключе Options. Например, Стартовое состояние машины указывается в подключе Options\StartState. Значением этого ключа должно быть состояние (указанное ранее в качестве одного из подключей ключа States)

Формат описания машины состояний:

<root>: Kernel/StateMachines/<Имя машины состояний>
States ; Состояния. Ключ обязательный
  <Имя состояния> ; Состояние. Имена состояний должны быть уникальными. В конечном автомате должно быть как минимум одно состояние
    TimeOut : -1  ; Тайм-аут. В данном случае тайм-аута нет, т.к. значение -1. Ключ опционален и может отстутствовать. Значение задается в миллисекундах.
    IsEndState : False ; Является ли состояние конечным, логическое значение True/False. Ключ опционален и может отсутствовать.
    Transitions : 1 ; Переходы из состояния. Ключ обязателен. Значение 1 - означает фильтрация сообщений с оставлением неподходящих в очереди. 0 - удаление неподходящих сообщений. Без значения означает 0.
      <Событие> : <Состояние приемник>
        CanRaise; Если ключ присутствует, то ожидается, что будут перечислены все возможные типы событий, которые имеет право сгенерировать функция-обработчик
          <Событие> ; Событие, которое может быть сгенерировано (по числу событий)
          ...
        Handler : <Имя обработчика> ; Указывается только для декларативным образом заданных обработчиков.
      ... ; Записи в таком формате для всех ожидаемых в данном состоянии событий.
  ... ; Записи в таком формате для остальных состояний
Options ; Настройки машины. Ключ является обязательным
  StartState : <Имя состояния> ; Указатель на стартовое состояние. Ключ является обязательным.