Сcылки по теме — must read
http://rsdn.ru/article/patterns/Protocols.xmlАвтор(ы): А.Рахимбердиев, А.Ксенофонтов, Е.Адаменков, Д.Антонов, Р.Степанов
Дата: 02.03.2006
Опыт авторов показывает, что решения, получающиеся при традиционном подходе к реализации реактивных систем, редко оказываются удобными и простыми для дальнейшего расширения и поддержки, особенно в случаях, когда поведение системы нетривиально. В данной статье рассматривается методика разработки, эффективно решающая большую часть подобных проблем. Поведение системы в целом описывается в виде конечного автомата на диаграмме состояний UML. Локальные действия в отдельных состояниях системы определяются при помощи соответствующих классов и функций C++. В статье также описывается расширение средства моделирования ArgoUML, предназначенное для автоматизации процесса разработки.
http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xmlАвтор(ы): Alexander Nikolayenko
Дата: 08.10.2005
Машина с конечным числом состояний (FSM, Finite State Machine, или как принято называть по-русски, конечный автомат, КА) представляет собой одну из наиболее полезных концепций в арсенале разработчика. Существует несколько методик реализации конечных автоматов, но, забегая вперед, хочется сказать, что достойный результат дают только те из них, которые связаны с генерацией кода. Возможности, предоставляемые последней версией стандарта C++ и реализованные в последних версиях компиляторов, позволяют генерировать код во время компиляции основного кода проекта. Это дает возможность избежать использования отдельных утилит или расширений IDE и, оставаясь в рамках единого языка (C++), создавать приемлемые для практического использования реализации КА, которые при этом легко поддерживать и развивать.
Определения
State machine (конечный автомат). Спецификация последовательности состояний,
через которые проходит в течение своей жизни объект, или взаимодействие в
ответ на происходящие события (а также ответные действия объекта на эти
события). Конечный автомат прикреплен к исходному элементу (классу, кооперации
или методу) и служит для определения поведения его экземпляров.
Конечный автомат представляет собой граф состояний и переходов, который
описывает, каким образом экземпляр квалификатора реагирует на получение
событий. Конечные автоматы могут прикрепляться к классификаторам, например
классам и вариантам использования, а также к кооперациям и методам. Элемент, к
которому прикреплен конечный автомат, называется его хозяином (master). Весь
конечный автомат представляет собой композитное состояние, которое можно
рекурсивно разложить на подсостояния. У самых простых внутренних состояний
подсостояний не бывает.
State (состояние). Условие или ситуация в жизненном цикле объекта, во время
которой он удовлетворяет некоему условию, выполняет определенную деятельность,
или ожидает какого-либо события.
За время своей жизни объект может находиться в различных состояниях. В
каждом из них объект пребывает в течение какого-либо конечного времени. Для
удобства при моделировании можно использовать фиктивные состояния, в которых
осуществляются тривиальные действия и немедленный выход, впрочем, это не
относится к основному назначению состояний, поэтому фиктивные состояния можно
вообще не использовать, хотя они и позволяют порой избежать дублирования.
Состояния содержатся в конечном автомате, который описывает те изменения,
которые происходят с течением времени с объектом в ответ на происходящие
события. Каждый конечный автомат описывает поведение объектов какого-либо
класса. Каждый класс может иметь конечный автомат. Реакция объекта,
находящегося в определенном состоянии, на некое событие описывается переходом:
объект выполняет опциональное действие, прикрепленное к переходу, и меняет
состояние. Каждому состоянию соответствует свое множество возможных переходов.
Действие атомарно (то есть ею нельзя прервать извне). Оно присоединяется к
переходу, который изменяет состояние, и, таким образом, изменение состояния
тоже атомарно. Текущая деятельность может быть связана с неким состоянием. При
этом она представляет собой вложенный конечный автомат или выражение do. С
другой стороны, текущую деятельность можно представить в виде пары действии;
действие при входе, которое начинает деятельность, но входу в состояние, и
действие при выходе, которое прекращает деятельность при выходе из этого
состояния.
Несколько состояний можно сгруппировать в одно композитное состояние. Любой
переход в композитное состояние затрагивает все состояния, находящиеся внутри
него. Таким образом, один переход может одинаково воздействовать сразу на все
вложенные состояния. Композитное состояние может быть как последовательным,
так и параллельным. В конкретный момент времени активно только одно
подсостояние последовательного композитного состояния. В параллельном
композитном состоянии все подсостояния активны одновременно.
Для осуществления инкапсуляции в композитном состоянии могут быть исходное и
конечное состояния. Они представляют собой псевдосостояния, назначение которых
— помочь в структурировании конечного автомата. Переход в композитное
состояние означает переход в его исходное состояние. Это позволяет
использовать композитное состояние, даже ничего не зная о его внутренней
структуре.
Переход в конечное состояние композитного состояния означает завершение в
нем всякой деятельности. При завершении деятельности во внешнем состоянии
запускается событие завершения деятельности во внешнем состоянии, что приводит
к фактическому запуску перехода по завершении. Переход по завершении
представляет собой переход, у которого нет явного переключающего события (или,
что более точно, у которого в роли неявного переключающего события выступает
событие завершения деятельности, хотя это и не моделируется явным образом).
Завершение самого внешнего состояния объекта соответствует гибели этого
объекта.
Submachine (вложенный автомат). Конечный автомат, который может быть вызван
как часть другого конечного автомата. Вложенный автомат не прикрепляется к
классу, — он является своего рода подпрограммой конечного автомата. Его
семантика соответствует ситуации, когда его содержимое копируется и
вставляется в то состояние, которое на него ссылается.
Submachine reference state (состояние-ссылка на вложенный автомат)
Состояние, которое ссылается на вложенный автомат, копия которого представляет
собой неявную часть общего конечного автомата. Может иметь
состояния-"заглушки", служащие для идентификации состояний во вложенном
автомате.
Transition (переход) В конечном автомате — отношение между двумя
состояниями, показывающее, что объект, находящийся в первом состоянии, будет
выполнять некоторые действия и перейдет в другое состояние, как только
наступит некоторое событие и при этом будут удовлетворены необходимые
сторожевые условия. Когда изменяется состояние, говорят, что переход
запустился фактически. У простого перехода есть одно начальное и одно целевое
состояние. У комплексного перехода несколько начальных и/или несколько целевых
состояний. Он указывает на изменение количества одновременно активных
состояний или же на развилку или слияние управления. У внутреннего перехода
есть начальное, но нет целевого состояния. Он представляет собой реакцию на
событие, при которой не происходит изменения состояния. Состояния и переходы
представляют собой вершины и дуги конечного автомата.
Реализация
Редактор графов КА
Для создания графов конечных автоматов используется редактор диаграм Dia
(текущая версия 0.96.1). Существуют версии под ОС Windows и Linux, что
удовлетворяет требованию кроссплатформенности. Программа распространяется под
лицензией GNU.
При создании диаграммы используются три окна: 1) основное окно программы,
содержит палитры объектов (при закрытии закрываются все окна и программа
завершается); 2) окно документа — КА (Каждый документ открывается в отдельном
окне); 3) Окно "Слои" (доступно через меню Диаграмма/Слои).
При описании редактора диаграм для всех обозначений объектов и их атрибутов
используются имена, используемые в программе (русскоязычная локализация
довольно косноязычна, поэтому для пояснения иногда приводится английская форма
названия)
Для рисования диаграмм используется палитра UML (находится в главноем окне).
Используются следующие объекты/примитивы:
Заметка (UML — Note). Заметки могут использоваться как для пояснения графа,
так и для задания дополнительных атрибутов объектам графа. В последнем случае
для связи с объектом используется соединитель "UML — Generalization". Стрелка
соединителя должна входить в объект "UML — Note".
Обобщение, наследование класса (UML — Generalization). Соединяет объекты и
заметки "UML — Note", содержащие расширенную информацию об объекте.
Начальное/конечное состояние (UML — State Term). Обозначают начальные и
конечные состояния. При помещении на диаграмму является начальным состоянием,
для преобразования в конечное состояние требуется в свойствах (двойной клик)
указать "Окончание" — "Да". Начальное/конечное состояние не имеет названия,
для начального состояния оно не требуется, для конечного необходимо добавить
заметку "UML — Note" с именем состояния и связать с конечным состоянием при
помощи "UML — Generalization".
Состояние (UML — State). Обозначает состояние автомата.
Переход (UML — Transition). Задает переход из одного состояния в другое.
Класс (UML — Class). Используется для описания класса, который реализует КА.
Также может использоваться для описания классов, используемых как аргументы
(контекст) получаемых автоматом событий.
Сведения по конкретной реализации нотации UML Statechart.
Используемые в редакторе диаграмм Dia объекты и наборы их атрибутов не
всегда полны. Для расширения наборов атрибутов используются следующие приемы:
1) На диаграмму добавлятся объект "UML — Note", содержащий расширенные
сведения об объекте, и связывается с расширяемым объектом соединителем типа
"UML — Generalization". Таким образом задаются имена конечных состояний и
список файлов, которые необходимо подключить при реализации автомата на языке
программирования (список подключаемых по include файлов — C/C++, для других
языков пока не прорабатывалось)
2) Какой либо атрибут объекта помимо собственного значения содержит (в
начале) расширенные атрибуты. Запись вида:
{name1:value;name2;name3:"string value"}
означает добаление атрибута name1 со значением value, атрибута name2 со
значением по умолчанию (обычно true), атрибута name3 со значением "string
value" (кавычки удаляются).
Имя автомата
Имя автомата задается именем слоя, на котором расположена его диаграмма.
Следует использовать имена, совместимые с синтаксисом идентификаторов целевого
языка программирования (в данный момент только C/C++).
Описание объектов
Transition — переход — может быть внешним и внутренним.
Атрибуты Transition
Триггер (trigger) — условие (событие) перехода.
Действие (action) — действие, выполняемое при переходе.
Хранитель (guard) — дополнительное условие перехода.
Пример. Допустим, необходимо создать переход, происходящий при получении
символа, если символ находится в диапазоне от '0' до '9' (цифра). Тогда
зададим Триггер="putChar" (событие: получение символа), Хранитель="'0'-'9'"
(диапазон допустимых для срабатывания перехода символов от '0' до '9',
синтаксис выражений guard описывается ниже).
Для задания внутреннего перехода атрибут "Триггер" должен содержать
расширенный атрибут inner — {inner:true} или {inner}.
При обработке переходов последовательность действий такая:
I. для внешного перехода выполняются дествия: 1) exit action состояния, из
которого производится переход; 2) выполняется action перехода; 3) выполняется
entry action перехода
II. для внутреннего перехода выполняются дествия: 1) action перехода; 2) do
action состояния.
При выполнении внешнего перехода do action состояния не выполняется.
Внутренний переход должен выходить и входить в одно и то же состояние, в
противном случае будет возникать ошибка генерации автомата и/или ошибка
компиляции сгенерированного кода.
Внешний переход также может выходить и входить в одно и тоже состояние, это
не является ошибкой.
При использовании подавтоматов (см. далее) следует избегать внутренних
переходов или переходов в само себя для состояний, которые являются составными
(complex/compaund states).
State — состояние — состояние автомата.
Атрибуты State
Начать действие (entry action) — действие, выполняемое при входе в
состояние. Не выполняется при внутренних переходах.
Произвести действие (do action) — действие, выполняемое после внутреннего
перехода. Не выпоняется при внешнем переходе или если состояние является
ссылкой на подавтомат.
Закончить действие (exit action) — действие, выполняемое при выхлде из
автомата. Не выполняется при внутренних переходах.
Для задания подавтоматов используются составные состояния. Для этого в
атрибуте "Произвести действие" (do action) задаются расширенные атрибуты
{complex:SubMachine;include:SubMachine.smxml}
complex — задает имя подавтомата.
include — задает имя файла, содержащего описание используемого подавтомата.
Необязательно, если подавтомат находится в другом слое текущего файла или если
файл описания считывается при генерации кода автомата (задается параметрами
командной строки).
State Term — начальное/конечное состояние.
Начальное состояние автомата не имеет имени и только задает состояние
автомата после создания или сброса. Фактически, начальным состоянием автомата
является состояние, в которое задан переход из стартового состояния. Переход
из этого состояния (и его атрибуты) игнорируется.
Для задания конечного состояния в свойствах объекта State Term следует
указать, что он является окончанием. Конечное состояние должно иметь имя
(задается с использованием "UML — Note" и связывается с состоянием
соединителем "UML — Generalization").
Автомат может иметь несколько конечных состояний или неиметь их вообще, в
последнем случае он не может быть использован как подавтомат.
Использование подавтоматов
Для включения автомата как составной части объемлющего автомата следует
использовать синтаксис расширенных атрибутов объекта "State".
При включении подавтомата производится подстановка (inlining) всех его
состояний и переходв. Имена новых состояний формируются из имени составного
состояния и имен состояний подавтомата, таким образом, подавтомат может
включатся в объемлющий автомат произвольное число раз.
При переходе в составное состояние происходит переход в стартовое состояние
подавтомата вне зависимости от того, по какому переходу transition это
произошло.
Количество переходов из составного состояния должно соответствовать
количеству конечных состояний подавтомата, триггеры перехода должны содержать
имена конечных состояний подавтомата (без каких-либо префиксов, так, как они
заданы в подавтомате), при этом атрибут "Хранитель" (guard) игнорируется.
Последовательность обработки действий (actions) при входе и выходе из
составного состояния.
Действия, принадлежащие вызывающему автомату, помечены '+', подавтомату —
'-'.
I. При входе в составное состояние действия выполняются в следующей
последовательности: 1) + выполняется exit action состояния, из которого
произошел переход в составное состояние; 2) + выполняется action произошедшего
перехода; 3) + выполняется entry action составного состояния, в которое
произошел переход; 4) — выполняется entry action стартового состояния
подавтомата;
II. При выходе из подавтомата составного состояния действия выполняются в
следующей последовательности: 1) — exit action состояния подавтомата, из
которого произошел переход в конечное состояние; 2) — action произошедшего
перехода в конечное состояние 3) + exit action составного состояния 4) +
action перехода из составного состояния 5) + entry action нового состояния
Класс автомата
Класс автомата может быть задан в любом автомате, описание которого
подключается при генерации кода автомата.
Класс, используемый для генерации автомата, привязывается к начальному
состоянию (объекту UML — State term) при помощи соединителя "UML —
Generalization". Имя класса-автомата задается в объекте "UML — Note".
Для класса автомата должен быть задан "стереотип" класса — "Automata".
Все события, получаемые автоматом, должны быть описаны соответствующим
методом автомата. Если событие имеет контекст, по которому производится
выборка перехода по guard условию, то он должен передаватся как параметр
метода.
Методы событий должны возвращать значение типа int — генерируемый код
возвращает код состояния, в которое перешел автомат.
Если при обработке события используются guаrd conditions, то проверяемая
переменная должна быть первым аргументом метода-обработчика события.
Если проверяемая по guаrd conditions переменная является структурой/классом
какого-то контекста события, на диаграмме (или на одной из подключаемых
диаграмм) должен быть приведен клас с таким же именем, у которого один из
атрибутов (членов класса) или методов помечен как guard (поле
"коментарий"="guard"). Описание класса больше не используется и может в
остальном не соответствовать реально используемому классу (который описывается
в одном из подключаемых по //includes заголовке).
Для использования guard переменной в условиях или при вызове действий
генерируется макрос GUARDVAR, который раскрывается в конкретное имя
переменной.
Дествия, которые могут совершаться при переходах из состояния в состояние,
следует задавать как методы, "тип наследования"="абстракция" или "виртуальная"
— генерируется (абстрактный) виртуальный метод.
Подключение сторонних заголовочных файлов и использование "inline" кода
При генерации класса можно задать заголовочные файлы, которые будут
подключены перед определением класса. Для этого с классом автомата связывается
объект "UML — Note", первой строкой которого является строка расширенных
атрибутов, в остальных — имена подключаемых файлов в угловых скобках или
кавычках.
Строка расширенных атрибутов для подключаемых файлов должна иметь вид:
{type:includes;lang:c,c++,...}
Для различных языков назначения можно задавать различные блоки includes и
размещать их в различных "UML — Note".
Для использования автомата и наполнения методов прикладным кодом следует
унаследоваться от сгенерированного класса и переопределить методы-действия.
Можно также добавлять код методов прямо на диаграмму. Для этого с классом
связывается "UML — Note" с кодом метода. Первой строкой должна следовать
строка расширенных атрибутов вида:
{type:code;method:MethodName;lang:c,c++;inline:false}
Атрибут inline можно не указывать, по умолчанию он установлен в true, при
этом для C++ код подставляется в декларацию класса (и соответственно, метод
становится inline-методом), для языка C код всегда помещается в .c файл.
Условия хранителя (guard conditions)
Условие хранителя может быть как условием на целевом языке — запись вида
"(expression)", так и списком констант, с которыми сравнивается переменная
guard var. В последнем случае можно использовать какие-либо переменные,
константы и символьные литералы. При этом guard var должна быть переменной
одного из целочисленных типов.
Список констант может содержать диапазоны, при этом нижняя граница
отделяется от верхней символом '-' (минус). Границы также входят в диапазон.
При использовании символьных литералов возможна их модификация в tchar
макросом _T() или в wide char префиксом L (задается при генерации кода опциями
командной строки).
Организация библиотек автоматов
Для организации библиотек автоматов используются пути поиска включаемых
файлов и возможность загружать помимо описания генерируемого автомата
произвольные файлы. Такми образом, при описании составных состояний можно не
указывать явно имя файла, содержащего описание подавтомата, а при
необходимости подключить одну из реализаций, явно указав в командной строке
файл, содержащий требуемое описание.
Дополнительные возможности
Возможна автоматическая генерация вызова методов lockAutomata/unlockAutomata
при входе и выходе в методы-обработчики событий. Задается из командной строки
при генерации кода автомата. Пользователь класса автомата переопределяет
данные виртуальные методы в класе наследнике.
Возможно автоматическое протоколирование переходов вызовом функции logEvent.
Задается из командной строки при генерации кода автомата. Пользователь класса
автомата переопределяет данную виртуальную функцию в класе наследнике.
Проверки графа конечного автомата
При генерации конечного автомата проводятся следующие проверки и
производятся следующие действия:
1) производится проверка на непротиворечивость переходов — из одного
состояния не может выходить два и больше переходов по одному и тому же
событию, с одним и тем же условием guard.
2) Производится проверка переходов по умолчанию (default transitions) со
значением guard '*'. При наличии нескольких переходов генерируется ошибка, при
отсутствии хотя бы родного — выдается пердупреждение.
3) Производится проверка безусловных переходов (не задано guard condition),
при наличии нескольких безусловных переходов по одному событию генерируется
ошибка.
4) составляется список всех событий всех переходов. Каждое состояние
дополняется переходами по всем событиям. Эти явно не определенные в автомате
переходы считаются запрещенными. В зависимости от параметров генерации
добавляемые переходы либо не меняют состояние автомата (при включенной опции
генерации протоколирования формируется сообщение о таком переходе), либо
происходит переход в специальное конечное состояние, сигнализирующее об ошибке
5) генерируются методы
isInFinalState — возвращает не ноль, если автомат находится в конечном
состоянии.
isInInadmissibleFinalState — возвращает не ноль, если автомат находится в
конечном состоянии по недопустимому переходу.
resetAutomata — метод инициализации и сброса автомата в начальное состояние.
customResetAutomata — метод дополнительной инициализации (определяется
пользователем класса) — вызывается из resetAutomata. Генерируется объявление
абстрактного метода.
lockAutomata/unlockAutomata — объявления абстрактных методов блокировки
класса автомата.
logEvent — объявление абстрактного метода протоколирования событий автомата.
Программы
Для обработки диаграм и генерации кода автоматов используются две программы:
dia2fsm — преобразует файл диаграммы Dia .dia в файл описания автомата
.smxml (более простой и предметно ориентированный формат).
fsmgen — генерирует код автомата, может считывать как файл описания автомата
.smxml, так и файл диаграммы Dia .dia.
Для поиска файлов описаний автоматов последняя программа использует ключ
-Ipath — путь поиска, может быть несколько таких ключей, или в одном пути
разделены символом ';'.
Для загрузки дополнительных описаний автоматов используются ключи -dfile.dia
и -ifile.smxml для загрузки файлов диаграмм Dia .dia и файлов описания
автомата .smxml.
Помощь по ключам командной строки можно получить, используя ключь -h (-?)
Символ '/' можно использовать при указании опций вместо символа '-'.
