Управление проектами - статьи

         

Алгоритм построения машин состояний по диаграммам последовательностей


Сделаем обзор алгоритма построения машины состояния, работающего в случае анонимных ролей:

  • синтаксический разбор (parsing);
  • построение графов, соответствующих диаграммам (ordering/linking);
  • объединение поведений, заданных диаграмма (placement/integration);
  • построение срезов (slicing);
  • построение автоматов, их преобразование в детерминированные автоматы, трансформация в машины состояний (automata generation & minimization);
  • кодогенерация (codegeneration).

Кратко опишем эти фазы.

Фазы синтаксического разбора и построения графов диаграмм зависят от синтаксиса их записи. В результате для каждой диаграммы обзора взаимодействий строится внутреннее представление графа, который состоит из диаграмм и связей между ними, задающих их последовательность. Для диаграмм последовательностей строятся события (и так называемые псевдособытия) и связи, задающие их последовательность на данной оси. Для inline-конструкций и ссылок на другие диаграммы строятся псевдособытия. Также строятся связи между множествами событий (и псевдособытий) на разных осях, если они взаимосвязаны - т.е. для пар событий посылки-приема сообщения, псевдособытий, соответствующих началам и концам ссылок на другие диаграммы, началам и окончаниям inline-конструкций.

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

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

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

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

Описанный алгоритм реализован для MSC-диаграмм в синтезаторе Bridge, разработанном в Институте системного программирования РАН совместно с компанией Klocwork. По построенным автоматам может генерироваться модель системы на языке SDL (очень близком к протокольным машинам состояний UML), прототип системы на языках Си/C++ или Java, тесты для системы на языках TTCN и PPL.

Для рассмотренного в начале примера спецификации системы обмена данными будут сгенерированы (с точностью до имен состояний) автоматы, изображенные в форме машин состояний на Рис. 15.



Рис. 15. Машины состояний для объектов модельной системы обмена данными.

Степень аппроксимации исходных сценариев автоматными моделями, построенными таким образом, обсуждается в работе [].


Содержание раздела