В чем заключается метод моделирования конечных автоматов

В чем заключается метод моделирования конечных автоматов

На этом шаге рассмотрим термины и понятия конечных автоматов в UML.

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

Автоматы используются для моделирования динамических аспектов поведения системы. Большей частью этот процесс подразумевает спецификацию жизненного цикла экземпляров класса, варианта использования или системы в целом. Эти экземпляры могут реагировать на такие события, как сигналы, операции либо истечение некоего периода времени. Когда происходит событие, в зависимости от текущего состояния объекта наблюдается некоторый эффект. Эффект – это спецификация поведения, реализуемого внутри автомата. В конечном счете эффекты проявляют себя в выполнении действий, изменяющих состояние объекта или возвращающих какое-либо значение. Состояние объекта – это период времени, в течение которого он удовлетворяет заданным условиям, выполняет некую деятельность или ожидает определенного события.

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

Хорошо структурированные автоматы подобны хорошо структурированным алгоритмам: они эффективны, просты, адаптируемы и понятны.

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

В UML моделирование статических аспектов системы выпол няется с помощью диаграмм классов и объектов. Они позволяют визуализировать, специфицировать, конструировать и документировать те сущности, которые «живут» внутри системы, включая классы, интерфейсы, компоненты, узлы, варианты использования и их экземпляры, а также связи между ними.

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

Автоматы используются для моделирования поведения любого элемента – чаще всего класса, варианта использования или всей системы. Автоматы могут быть визуализированы на диаграммах состояний. Вы можете сосредоточиться на поведении объекта, зависящем от последовательности событий, что особенно удобно для моделирования реактивных систем.

Графическое представление состояний, переходов, событий и эффектов в UML продемонстрировано на рис. 1. Эта нотация позволяет показать поведение объекта таким образом, чтобы выделить важные элементы его жизненного цикла.

Приведем определение основных терминов и понятий.

Автомат – это поведение, специфицирующее последовательность состояний, через которые проходит объект за время своего существования в ответ на события, а также его реакцию на эти события.

Состояние – ситуация во время жизни объекта, в которой он удовлетворяет заданным условиям, осуществляет некую деятельность либо пребывает в ожидании событий.

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

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

Деятельность (activity) – происходящий в данный момент неатомарный процесс внутри автомата.

Действие (action) – исполняемое вычисление, в результате которого изменяется состояние модели или возвращается некоторое значение. Изображается в виде прямоугольника с закругленными углами.

На следующем шаге рассмотрим определение состояния автомата объекта в UML.

Использование автоматов для эмулирования жизни

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

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

Рисунок 1 — П оведение змейки

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

Усложним задачу змее: пусть она может на своем пути встретить не только жертву, но и врага, которого она не в состоянии одолеть. В таком случае змея должна будет убегать от врага. Змея может встретить врага в любой момент времени, когда находится в одном из следующих состояний: «поиск добычи», «выслеживание», «отправиться домой». Важно понимать, что если змея находилась в состоянии «выслеживания добычи», то добыча скрывается из виду, и змее придется вернуться к поиску добычи. Если в состоянии «поиск добычи», то змее все равно придется вернуться к поиску цели. Если змея отправлялась домой, то ей нет необходимости после ухода от врага возвращаться к поиску добычи, и змея просто пойдет дальше домой. Изобразим изменения на рисунке:

Рисунок 2 — У сложнение действий в поведении змейки

Казалось бы, ничего существенно не поменялось. Однако перед программистом, который решил сымитировать жизнь змеи, встала огромная проблема. Теперь из состояния «убежать от врага» змея может попасть сразу в 2 состояния: «поиск добычи» или «отправиться домой». Как было сказано ранее, змее надо отправиться домой, если она уже была в пути домой; в противном случае ей надо продолжать охотиться. Для решения таких задач были придуманы конечные автоматы, основанные на стеке.

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

Рисунок 3 — Пример стека состояний змеи

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

Рисунок 4 — Пример усложненного графа состояний змеи

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

Так мы увидели, что большая задача может быть разбита на несколько более мелких конечных автоматов, где каждый автомат (не нижнего уровня) может содержать в себе в качестве состояний другие автоматы. Автоматы нижнего уровня не могут ссылаться на другие автоматы, так как это может вызвать бесконечную рекурсивную последовательность вызова состояний в стеке.

Сети Петри

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

Приведем простой пример, для того чтобы понять устройство сетей. Представим, что человек возвращается домой с работы и не хочет терять время на приготовление еды. Лучшим способом будет заказать еду в каком-либо магазине. Также представим, что человек захочет заехать в магазин по пути домой. Садясь в машину, человек может позвонить в службу доставки еды, а затем в навигаторе указать номер ближайшего магазина. В таком случае решение задачи “заказать еду” и “съездить в магазин” может быть записано в виде автомата:

Рисунок 5 — Пример простого автомата выбора человека

Однако человек может звонить в службу доставки еды и параллельно искать нужный магазин в навигаторе. Тогда человек сможет сэкономить время и быстрее добраться домой. Человек не может поехать, пока он не выполнит все нужные действия. Как раз такую ситуацию можно показать с помощью Сети Петри. Две задачи будут вершинами сети, а переход фишки из одного состояния в другое будет организован функцией завершения действия. Наглядно это будет выглядеть так:

Рисунок 6 — Сеть Петри действий человека

Сейчас многие простые чат-боты моделируют решение задач средствами обычных автоматов, тем самым такие боты могут решать простые человеческие задачи по типу: “найти подходящий фильм по нескольким вопросам”, “забронировать билет”, “заказать такси”. Решения таких ботов не выходят за рамки решения только одной текущей задачи, а решение проблемы многозначности решения сводится к выбору одного решения без анализа.

Применение NLP для автоматического построения сетей Петри

Одна из проблем всех современных ботов – это невозможность построить свои сети или автоматы для решения новой задачи в ходе общения с человеком. Но стоит отметить, что для построения системы, способной автоматически решать ряд задач и быть универсальной в отношении решаемых задач, необходимо построить сильный ИИ. Такой ИИ должен решать ряд простых задач: уметь определять смысл разговора с человеком, уметь извлекать необходимую информацию в структурированном виде из текста, уметь делить сложные задачи на подзадачи, уметь находить оптимальный вариант решения задачи с учетом решения каждой подзадачи.

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

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

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

Проектирование конечных автоматов по методу Ohe Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Строгонов Андрей

В ряде случаев автоматная модель устройства позволяет получить быструю и эффективную реализацию последовательностного устройства. Обычно рассматривают два типа автоматов — автомат Мили (Mealy) и Мура (Moore).

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Строгонов Андрей

Проектирование цифровых автоматов с использованием системы Matlab / Simulink
Синтез моделей управляющих автоматов для socфильтров с конвейерной архитектурой

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

Методы и программные продукты для повышения производительности проектов на базе ПЛИС Xilinx
Краткий курс HDL. Часть 5. Написание кода, независимого от аппаратной платформы
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Проектирование конечных автоматов по методу Ohe»

Проектирование конечных автоматов

В ряде случаев автоматная модель устройства позволяет получить быструю и эффективную реализацию последовательностного устройства. Обычно рассматривают два типа автоматов — автомат Мили (Mealy) и Мура (Moore) [1, 2].

Андрей СТРОГОНОВ, д. т. н.

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

Обычно конечный автомат состоит из трех основных частей:

• Регистр текущего состояния. Этот регистр представляет собой набор тактируемых D-триггеров, синхронизируемых одним синхросигналом. Этот набор используется для хранения кода текущего состояния автомата. Для автомата с n состояниями требуется Log2(n) триггеров.

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

• Логика формирования выхода. Выход цифрового автомата обычно определяется как функция текущего состояния и исходной установки (в случае автомата Мили). Формирование выходного сигнала автомата определяется с помощью логики формирования выхода.

В качестве примера рассмотрим проектирование простейшего синхронного автомата, который формирует два неперекрываю-щихся импульса Outl и Out2 в ответ на появление сигнала Run на входе автомата (рис. 1а). Полностью синхронный конечный автомат использует регистры для фиксации всех выходных сигналов управления и состояний, а также для асинхронных входных сигналов. Следует заметить, что синхронные конечные автоматы по быстродействию уступают асинхронным.

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

Автомат принимает четыре состояния: Idle, Delay, Next, Done (рис. 1а). Воспользуемся методом двоичного кодирования состояний, который обеспечивает высокую степень кодирования последовательности состояний. Для кодирования состояний потребуется два триггера. Запишем булевы логические уравнения:

50 := (Idle, Run)+Delay,

Символ = обозначает комбинационную схему, ответственную за переход по состояниям, а символ := обозначает триггерный выход, необходимый для хранения кода текущего состояния автомата и выходных сигналов. Схема, построенная по булевым уравнениям в САПР ПЛИС Quartus II компании Altera, показана на рис. 2. На рис. 3 показаны временные диаграммы работы автомата. Уравнение для выходного сигнала Outl представляет собой функцию как состояния, так и входного сигнала Run. Конечный автомат с таким видом стробирования выходов называется автоматом Мили. Уравнение для выходного сигнала Out2 записывается как функция только состояния автомата, что соответствует структуре автомата Мура. Для автоматов Мили удобно представлять диаграммы в другом виде (рис. 1б).

Метод one hot encoding (ОНЕ — кодирование с одним активным, или горячим, состоянием; иначе — унитарное кодирование) получил такое название потому, что в каждый конкретный момент времени активным (hot) может быть только один триггер состояния. Применение метода ОНЕ для ПЛИС по архитектуре ППВМ (программируемые пользователем вентильные матрицы, зарубежная аббревиатура — FPGA) было предложено компанией High-Gate Design [3].

Построение конечного автомата с использованием метода ОНЕ осуществляется по следующей методике — вначале для отображения каждого состояния автомата выделяется

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

Рассмотрим конечный автомат Мура, предусматривающий семь различных состояний [3, 4]. Построим граф-автомат проектируемого устройства (рис. 4). Автомат переходит из состояния в состояние по переднему фронту синхроимпульса, который отмечен «крестиком». Иерархическая блок-схема автомата, состоящая из 7 блоков S1-S7 и логики формирования выхода, в САПР ПЛИС Quartus II компании Altera показана на рис. 5.

В примере имеется семь состояний (Stage1-7), каждый блок ответственен за формирование своего состояния, например блок S1 отвечает за формирование состояния 1. Все логические входы помечаются как переменные от А до Е. Выходы конечного автомата носят названия Multi, Contig и Single. В данном примере состояние 1, в котором должен находиться конечный автомат при включении питания, имеет структуру триггера с двумя инверторами (схема S1, рис. 6).

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

чить логическую непротиворечивость, входной информационный сигнал этого триггера также инвертируется. Таким образом, состояние 1 в начальный момент времени принимает значение логической единицы. Для всех других состояний 2-7 используется Г>-триггер с асинхронным сбросом, тактируемый фронтом синхросигнала.

Автомат спроектирован так, что активный низкий уровень сигнала И8ТО (глобальный

сброс состояний всего автомата, кроме состояния 1) в начальный момент сбрасывает состояния 2-7 (82-87) в ноль, а состояние 1 будет находиться в единице. Далее сигнал И8ТС должен всегда оставаться логической 1. В случае, если конечный автомат все же окажется в недопустимом состоянии, например, в состоянии 3, то с приходом следующего переднего фронта синхроимпульса будет установлено состояние 4. Состояние 4 сбросит состояние 3. Состояние 4 может сбросить и состояние 2. Состояние 5 сбрасывает состояние 4, состояние 6 сбрасывает состояние 5, состояние 7 сбрасывает состояние 6, а состояние 1 сбросит состояние 7. Таким образом, для правильной работы конечного автомата достаточно его один раз сбросить с помощью сигнала И8ТО, а далее автомат, шагая по состояниям, способен сам их сбрасывать.

После того как установлены начальные состояния, необходимо построить логику перехода в следующее состояние. Для определения индивидуального состояния воспользуемся алгоритмом, предложенным в работе [3]. Вначале подсчитывается число условий переходов, ведущих к данному состоянию, и добавляется еще один переход, если условие по умолчанию должно оставлять конечный автомат в том же самом состоянии. Далее строится логический вентиль ИЛИ с числом входов, равным числу условий переходов, определенных ранее.

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

Чтобы определить число условий переходов для состояния 1, рассмотрим граф-автомат. Из рис. 6 видно, что состояние 1 имеет один переход от состояния 7, когда переменная Е истинна. Другой переход — это условие

Рис. 5. Иерархическая блок-схема автомата с кодированием по методу OHE в САПР ПЛИС Quaгtus II

Рис. 6. Cхема для ^стояния 1

по умолчанию, ведущее в состояние 1. Таким образом, состояние 1 имеет два условия переходов. После этого можно построить двухвходовой логический вентиль 2ИЛИ с одним входом для условия перехода от состояния 7, а другим — для перехода по умолчанию, чтобы оставаться в состоянии 1 (рис. 6).

Следующий шаг — это построение логики переходов для данного вентиля 2ИЛИ. Каждый вход вентиля 2ИЛИ есть логическая функция И предыдущего состояния и логики переходов состояния 1. Например, состояние 7 поступает на вход состояния 1, когда

Е имеет истинное значение. Это обеспечивается при помощи логического вентиля 2И (рис. 6). Второй вход вентиля ИЛИ — переход по умолчанию, когда конечный автомат должен оставаться в состоянии 1. Если текущее состояние есть состояние 1 и нет условий переходов, выходящих из состояния 1, которые истинны, то конечный автомат должен оставаться в состоянии 1. Состояние 1 на диаграмме состояний имеет два исходящих условия переходов (рис. 6).

Первый переход является действительным, когда истинно условие (АВС), и ведет в со-

стояние 2. Второй переход, ведущий в состояние 4, является действительным при истинном значении условия (АВС). Логика по умолчанию — это функция И для состояния 1 обратной величины всех условий переходов, исходящих из состояния 1. Эта логическая функция реализуется с использованием вентиля 2И с инвертором на одном из входов и логических элементов, формирующих сигнал для инвертирующего входа вентиля 2И (рис. 6). Комбинационная логика обеспечивает декодирование с учетом входных сигналов и сигнала обратной связи.

Состояние 4 не является начальным состоянием, поэтому для его представления используется D-триггер без инверторов, с входом асинхронного сброса RSTG. Триггер может быть сброшен и выходом состояния 5 (сигнал RSTState5). Имеется три входящих условия перехода и условие по умолчанию, чтобы конечный автомат мог оставаться в состоянии 4. Поэтому на входе триггера используется вентиль 4ИЛИ (схема S4, рис. 7).

Первое условие перехода исходит из состояния 3. В соответствии с изложенными выше правилами необходимо построить функцию И для состояния 3 и логику условия, которая имеет вид A+D (рис. 7).

Следующее условие перехода исходит из состояния 2, оно требует логической функции И для состояния 2 и переменной D. Последнее условие перехода для состояния 4 — от состояния 1. Выход состояния 1 должен пройти через схему 2И с логикой его условия перехода — логическим произведением ABC (рис. 7).

Далее нужно построить логику, обеспечивающую сохранение состояния 4, когда ни одно из условий переходов, исходящих из состояния 4, не имеет истинного значения. Переход, исходящий из состояния 4, является действительным, когда логическое произведение ABC истинно. Следовательно, необходимо пропустить состояние 4 через вентиль И с обратной величиной произведения ABC . Это необходимо для поддерживания триггера в высоком уровне, пока не произойдет действительный переход в следующее состояние. В логике перехода по умолчанию используется вентиль 2И и выход вентиля 3И с инвертором на входе С.

Состояние 2 имеет только одно условие перехода, которое приходит от состояния 1, когда произведение ABC истинно. Конечный автомат будет немедленно переходить по одному из двух переходов из состояния 2 в зависимости от значения сигнала D. Состояние 3, подобно состояниям 1 и 4, имеет переход по умолчанию, и для управления входом D-триггера используется комбинация сигналов A и D, состояния 2 и состояния 3. Состояние 5 управляет состоянием 6 без всяких условий. Конечный автомат ждет в состоянии 6, пока переменная Е не переключится в низкий уровень, прежде чем перейти в состояние 7. В состоянии 7 конечный автомат ждет переключения переменной Е в истинное значение, после чего переходит в состояние 1.

После описания всей логики переходов по состояниям описывается выходная логика. В примере используются три выходных сигнала — Multi, Contig и Single, — каждый из которых относится к одной из трех основных категорий выходных сигналов:

1. Выходные сигналы, формируемые в одном состоянии. Примером может служить выходной сигнал Single, формируемый только в состоянии 6, то есть выходным сигналом является выход триггера.

2. Выходные сигналы, формируемые во многих смежных состояниях. Например, выходной сигнал Contig, который формируется в состояниях З-7, хотя есть ветвь для состояния 2,

3. Выходные сигналы, формируемые по многим несмежным состояниям. Здесь обычно оптимальное решение — это простое декодирование активных состояний. Например, сигнал Multi, который формируется для состояний 2 и 4.

Для формирования логики выходного сигнала Multi используется декодирование состояний 2 и 4 при помощи вентиля 2ИЛИ. Каждый раз, когда конечный автомат окажется в одном из этих состояний, будет сформирован активный сигнал Multi. Для декодирования выходных сигналов для смежных состояний используется синхронный RS-триггер, RS-триггер устанавливается при входе в смежное состояние и сбрасывается при выходе (рис. 5). Временная диаграмма проектируемого автомата представлена на рис. 8,

Для размещения автомата выберем ПЛИС по архитектуре ППВМ APEX20K

(EP20K30ETC144-1). Архитектура ПЛИС семейства APEX20K сочетает в себе достоинства ППВМ ПЛИС с их таблицами перекодировок (LUT). После компиляции проекта оказалось задействовано 20 логических элементов, 8 триггеров. Моделирование проводилось без учета реальных задержек распространения сигналов в ПЛИС. С учетом реальных задержек период тактового сигнала CLK для стабильной работы автомата должен быть не менее 15 нс. Уменьшить число триггеров на один позволяет декодирование состояний 3-7 при помощи 5-входового вентиля ИЛИ. Каждый раз, когда конечный автомат окажется в одном из этих состояний, будет сформирован сигнал Conting. В этом случае и сокращается число логических элементов. Максимальная тактовая частота в обоих схемных решениях составляет fMAX = 290,02 МГц.

Опишем функционирование данного автомата на языке описания аппаратных средств VHDL. Описание проектируемого конечного автомата с использованием двухпроцессного шаблона и перечисляемого типа данных (Enumerated type) на языке VHDL приведено

Рис. 8. Результаты моделирования работы конечного автомата с принудительным сбросом состояний. Показаны переходы по состояниям 1—7

далее. Перечисляемый тип — это такой тип данных, при котором количество всех возможных состояний конечно. Такой тип наиболее часто используется для обозначений состояний конечных автоматов. Любой перечисляемый тип имеет внутреннюю нумерацию: первый элемент всегда имеет номер 0, второй — 1 и т. д.

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

В данном примере стиль кодирования (например, метод двоичного кодирования или кодирование по методу OHE) не определен в коде языка VHDL. Xilinx рекомендует использовать кодирование цифровых автоматов с использованием перечисляемого типа, так как в этом случае САПР предоставляется возможность использовать модуль логического синтеза и в зависимости от архитектуры ПЛИС самостоятельно выбирать метод кодирования [5]. В САПР Quartus II предлагается использовать три метода кодирования: Auto, OHE, Minimal Bits. В САПР Xilinx используется семь методов кодирования: Auto, OHE, Gray, Compact, Johnson, Sequential, User [5].

ENTITY avtOHE IS PORT(

A,B,C,D,E,TRST,TCK : IN STD_LOGIC;

Multi, Contig,Single : OUT STD_LOGIC;

STATE1_7 : OUT STD_LOGIC_VECTOR

ARCHITECTURE a OF avtOHE IS

TYPE state_values IS (Stage1, Stage2, Stage3, Stage4, Stage5, Stage6, Stage7);

signal state,next_state: state_values;

— регистровый блок statereg: process(TCK,TRST) begin

if (TRST = ‘1’) then state

elsif (TCK’event and TCK=’1′) then state

end if; end process statereg;

— комбинаторный блок (логика переходов)

case state is when Stage1=>

IF (A=’1′ and B=’0′ and C=’1′) THEN next_state

ELSIF (A=’1′ and B=’1′ and C=’0′) THEN next_state

IF (D=’0′) THEN next_state

ELSIF (D=’1′) THEN next_state

END IF; when Stage3=>

IF (A=’1′ or D=’1′) THEN next_state

IF (A=’1′ and B=’1′ and C=’0′) THEN next_state

IF (E=’0′) THEN next_state

— логика формирования выхода

В чем заключается метод моделирования конечных автоматов

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

Введение

При создании сложных инженерных систем принято использовать приемы моделирования. Сложность большинства создаваемых сегодня программных систем не уступает сложности многих инженерных сооружений, поэтому моделирование программных систем является весьма актуальной задачей. Более того, в таких концепциях, как MDA (Model Driven Architecture — архитектура на основе моделей) и MDD (Model Driven Development — разработка на базе моделей), моделям отводится центральная роль в процессе создания программного продукта. Основной идеей этих концепций является представление процесса создания программного продукта в виде цепочки трансформаций его исходной модели в готовую программную систему.

Почти во всех инструментальных средствах, воплощающих идеи MDD, в качестве языка моделирования используется язык UML (Unified Modeling Language — унифицированный язык моделирования), целиком или какие-либо его части.

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

В свете инициатив MDA и MDD роль моделей в жизненном цикле программного обеспечения (ПО) претерпевает значительные изменения. Если ранее моделирование рассматривалось как одно из удобных средств документирования, и, соответственно, жизненный цикл моделей был близок к жизненному циклу артефактов документации, то в последнее время работа с моделями становится все более похожа на работу с исходными кодами. Подобный подход ставит перед исследователями новые задачи исследования применимости к моделям методик и приемов работы, используемых для работы с исходными кодами. Одной из таких методик является рефакторинг.

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

1. поиск плохо спроектированных участков кода (модели), для которых требуется проведение рефакторинга;
2. определение рефакторинга (синтез из поддерживаемых базовых рефакторингов), который следует применить;
3. проверка или доказательство неизменности поведения системы после выполнения преобразований;
4. реализация применения рефакторинга и, в частности, разработка пользовательского интерфейса и диалогов, поддерживающих процесс применения рефакторинга;
5. сохранение целостности модели, то есть распространение произведенных изменений на другие части модели (диаграммы, тесты);
6. оценка эффекта, полученного в результате применения рефакторинга.

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

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

Анализ исполняемых UML-моделей

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

• активный класс (active class);
• операция (operation);
• составное состояние (composite state).

1. модели, изначально спроектированные на языке UML (например, в таких программных системах, как Rational Rose, Telelogic Tau G2, I-Logix Rhapsody, Borland Together);
2. модели, изначально спроектированные на языке SDL (например, в таких программных системах, как Telelogic SDL Suite, Verilog ObjectGeode) и трансформированные в UML вручную или при помощи специальных утилит (например, Telelogic Tau G2 — Import SDL).

Исполняемые UML-модели второго класса в основном описывают различного рода коммуникационные системы (то есть такие классы систем, для моделирования которых предназначен язык SDL). Исполняемые модели первого класса в связи с универсальностью языка UML описывают гораздо более широкий спектр систем.

Характеристика конечных автоматов

Общая статистика по исследованным моделям представлена в таблице 1. Перечисленные модели были заимствованы из реальных проектов коммерческих компаний. Для сбора и анализа необходимой информации был разработан дополнительный модуль к промышленной среде UML-моделирования Telelogic Tau G2.

Ожидалось, что модели, используемые в реальных проектах, будут иметь достаточно высокий уровень сложности. Тем не менее, более 90% от всех описанных автоматов содержат не более трех состояний, а доля автоматов без состояний (включающих только один начальный переход) близка к 75% (рис. 1). Причем доля таких автоматов растет вместе с размером модели.

Рис. 1. Количество состояний в конечных автоматах

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

На основе полученных данных использование конечных автоматов без состояний может быть объяснено следующим образом. В рассмотренных моделях операции практически не обладали семантикой состояний, поэтому 99% операций описывались автоматами без состояний, вырождаясь в императивную последовательность действий. Таким образом, использование автоматов для спецификации операций, как правило, не оправдано, и, тем не менее, широко применяется на практике.

Рис. 2. Количество состояний в конечных автоматах, реализующих классы

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

Автоматы, специфицирующие иерархические состояния, составили чуть менее 2% от всех обнаруженных автоматов и были найдены всего лишь в нескольких из рассмотренных моделей, что позволяет сделать вывод об их достаточно редком использовании, несмотря на их выразительную мощность. Причиной тому может служить тот факт, что составные состояния не являлись частью языка SDL до его версии SDL-2000. Большинство крупных промышленных моделей SDL, впоследствии трансформированных в UML, было разработано до того, как появился новый стандарт SDL-2000.

На рис. 3 приведена статистика количества переходов, которые могут сработать в каждом из состояний автомата. И здесь снова 84% процента состояний достаточно просты в понимании, так как имеют не более 6 переходов. Однако состояния с большим числом переходом могут заметно затруднить понимание автомата, а их доля приближается к 15%; более того, как правило, эти состояния являются ключевыми в понимании алгоритмов, заложенных в конкретный автомат.

Рис. 3. Количество переходов из состояния

Таким образом, в среднем автомат, реализующий класс, содержит 3 состояния и около 12 переходов и 4 диаграмм, при этом около 90% автоматов содержат не более 6 состояний, и, следовательно, их понимание не должно вызывать серьезных затруднений у разработчиков. Однако внутренняя логика работы системы, как правило, реализуется оставшимися 10%, среди которых встречаются автоматы, насчитывающие до 30 состояний. Вполне очевидно, что умственные затраты на понимание такого автомата достаточно велики; соответственно, значительно затрудняется процесс его модификации, поиска ошибок и проч. Поэтому средства, уменьшающие сложность автоматов, сохраняя их внешние свойства, действительно востребованы на практике.

Рис. 4. Распределение количества символов на диаграммах

Анализ диаграмм состояний показал (см. рис. 4), что в среднем автомат, реализующий класс, включает в себя 3-4 диаграммы, каждая из которых содержит около 9 символов и 9 линий, что не должно в значительной степени препятствовать пониманию. В то же время для 10% автоматов, описывающих внутреннюю логику работы системы и содержащих более 6 состояний и переходов, количество диаграмм, на которых описан автомат, возрастает до пятидесяти, что очень сильно затрудняет понимание целостной картины работы системы.

Используемые конструкции

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

За счет использования операторов ветвления в действиях, выполняемых при срабатывании перехода в автомате, один и тот же переход может в различных условиях перевести автомат в различные состояния. Максимально возможное использование ветвления означало бы наличие в каждом состоянии не более чем одного перехода для любого сигнала. В этом случае выбор состояния, в которое перейдет автомат, происходил бы в процессе интерпретации действий, приписанных переходу. Результаты статистического исследования приведены на рис. 5.

Рис. 5. Ветвистость переходов

Как и следовало ожидать, большинство переходов не разветвляются, а около 90% из них имеет не более трех ветвей. Однако 3% переходов, имеющие более 5 ветвей, могут заметно усложнить понимание логики работы системы. Абсолютный максимум составил 21 ветвь в одном переходе.

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

Одним из средств графической декомпозиции UML являются метки. Они позволяют графически отделить участки диаграммы состояний, чтобы, например, перенести их на другую диаграмму или расположить отдельно на исходной диаграмме. Кроме того, введение меток способствует повторному использованию фрагментов диаграмм, так как переход на единожды описанную метку может быть выполнен многократно из различных частей автомата. Статистика использования меток приведена на рис. 6.

Рис. 6. Распределение переходов на метки

Распределение количества команд перехода на метки очень похоже на распределение количества ветвей. В обоих случаях наиболее простые варианты (одна ветвь и отсутствие переходов на метки) обеспечивают около 60% случаев, а следующие по сложности варианты (две ветви и одна команда перехода на метку) — около 20%, в то время как остальные варианты имеют по 3-4%. Однако в автоматах встречались и переходы, перегруженные командами перехода на метки. Для некоторых переходов в автомате максимальное количество команд перехода на метку превысило 20.

Чтобы избежать дублирования переходов для различных состояний, можно использовать несколько приемов. В UML в символе состояния можно перечислить несколько имен состояний, и тогда все переходы, выходящие из этого символа, будут относиться ко всем перечисленным состояниям. Кроме того, если в качестве имени состояния указать символ «*», то переходы, выходящие из этого символа, будут относиться ко всем состояниям автомата. Также имеется возможность исключить определенные состояния из множества состояний, описываемого символом «*». Умелое использование этих возможностей позволяет значительно упростить описание переходов, применимых более чем к одному состоянию. Результаты статистического исследования показали, что символ * присутствует в 12% символов состояния, что свидетельствует о достаточно активном использовании этой подстановки и необходимости более детального изучения вариантов ее использования и возможных трансформаций с выделением или заменой символа «*».

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

Типичные способы построения конечных автоматов

Анализ полученной выборки не выявил каких-либо стандартов или «правил хорошего тона» при разработке конечных автоматов. Единственным «паттерном» можно считать применяемую одной из компаний методику, когда при описании автомата для каждого перехода из заданного состояния используется отдельная диаграмма, и еще одна диаграмма используется для всех общих описаний. Естественным недостатком такого подхода является сложность получения целостного представления о моделируемом автомате по причине разрозненности отдельных диаграмм, описывающих состояния.

Улучшение структуры конечных автоматов UML

Трансформация «выделение метода» для конечных автоматов UML

Идея трансформации «Extract method» состоит в создании нового метода и переносе части исходного автомата в добавленный метод. Данная трансформация во многом аналогична известному рефакторингу «Extract Method» для объектно-ориентированных языков программирования, описанному в каталоге Фаулера [1]. Суть традиционной трансформации состоит в выделении участка кода и перемещении его в другой метод. Это позволяет сделать код исходного метода более понятным и повышает вероятность повторного использования выделенного метода.

Для корректного выполнения традиционного рефакторинга «Extract method» требуется тщательный анализ потока данных в выделяемом участке кода, так как все используемые переменные должны быть переданы в метод в качестве параметров, а все изменения переменных должны быть тем или иным образом возвращены исходному методу, если измененные переменные используются в нем далее.

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

Следует подчеркнуть исключительную важность автоматизированной поддержки рефакторинга при проведении подобных преобразований, ибо сложность проводимого анализа будет способствовать ошибкам.

• Для конечных автоматов UML можно применить традиционную трансформацию «выделение метода», которая состоит из выделения подпоследовательности действий одного из переходов конечного автомата в метод.
• В рамках описываемого исследования был разработан новый вариант трансформации «выделение метода», специфичный только для конечных автоматов UML — «выделение в метод части конечного автомата», который подразумевает перенос в выделяемый метод не только действий, связанных с переходом, но и самих переходов и состояний.

Выделение в метод части конечного автомата

Рассмотрим определение части конечного автомата, представленное на рис. 7.

Риc. 7. Часть автомата, допускающая выделение метода

Выбрав часть перехода вместе со следующим состоянием, можно выделить метод, в которую войдет часть состояний конечного автомата, начиная с состояния Y. Будем называть такую трансформацию Extract Sub State Machine.

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

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

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

Введём несколько обозначений. Обозначим через RS(x, y) множество, содержащее все состояния автомата, в которые можно попасть из состояния y, не проходя при этом через состояние x, включая y и исключая x. Специальный символ stop добавляется в множество RS(x, y), если из состояния y за некоторое количество переходов можно дойти до действия, завершающего работу автомата ( stop ). Обозначим множество всех переходов некоторого конечного автомата A через All_T(A), а переход из состояния а в состояние b по сигналу z — через t(a, z->b).

Определение 1. Множество состояний S замкнуто на множестве переходов T, если не существует перехода

1. x != y , иначе RS пусто и это будет случай выделения автомата без состояний;
2. множество RS(x,y ) замкнуто на множестве переходов All_T(A)\t(x,e->y );
3. stop RS(x, y ).

1. Создаётся и добавляется в активный класс метод P с реализацией в виде конечного автомата.
2. В этот метод перемещаются все состояния из множества RS(x, y ) .
3. Действия, приписанные переходу t(x,e -> y ), становятся действиями, приписанными начальному переходу конечного автомата метода P (). Вместо них в исходный конечный автомат вставляется вызов метода P () и команда перехода в исходное состояние x .
4. Все команды перехода в состояние x в созданном конечном автомате заменяются на команды возврата из метода ( return ).

Рис. 8. Часть автомата после проведения преобразования Extract Method

Рис. 9. Описание выделенного метода

Часть автомата, выделенная в метод, обладает следующей семантикой: получив сигнал Sig3 (), автомат выполняет некоторые действия, начиная с состояния y , по завершении которых возвращается в состояние x . Подобная логика близка по смыслу к вызову метода: выполнение задачи с последующим возвратом в исходное состояние. Именно это и служит основанием для выделения метода.

В результате преобразования выделяется структурная единица автомата — метод, а диаграмма, описывающая конечный автомат, уменьшается, что упрощает его понимание Результат преобразования представлен на рис. 8. Выделенный метод показан на рис. 9. Выделенный метод можно использовать повторно для уменьшения дублирования кода.

1. Ни для одного состояния из RS(x, y ) нет перехода в x . Это значит, что возврат из созданного метода невозможен, в конечном автомате найден бесконечный цикл; возможно, это «серверная составляющая» исходного автомата.
2. Множество RS(x,y ) содержит символ stop , и ни для одного состояния из RS(x, y ) нет перехода в x . Это означает, что выделенная в метод часть автомата рано или могла завершить его работу: либо выделенные действия реализуют необходимую подготовку к завершению работы автомата (аналог деструктора в объектно-ориентированном программировании), либо найдена «серверная составляющая» исходного автомата (только если есть цикл).

1. в выделенном методе все команды завершения работы автомата (stop) должны быть заменены командами возврата из метода (return);
2. вместо действий, приписанных исходному переходу, должен быть добавлен вызов метода P () и команда завершения работы автомата (stop).

В рассматриваемом случае преобразованный автомат будет выглядеть так, как показано на рис. 10

Рис. 10. Результаты применения второго варианта трансформации

Пример «Мобильный телефон»

Продемонстрируем применение трансформации «Выделение части конечного автомата в метод» на одном из конечных автоматов системы Mobile, моделирующей работу мобильного телефона.

В исходной системе конечный автомат представлен на 28 диаграммах, каждая из которых описывает ровно один переход (рис. 11).

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

Приведённый алгоритм позволяет найти и выделить из данного конечного автомата три метода. На первом шаге в метод Initialize() выделяются четыре последовательных состояния (рис. 13).

На втором шаге выделяется метод TalkingThePhone() (рис. 14), после чего становится возможным выделить ещё один метод, который назовём Working().

Обратим внимание на то, что выделение метода Working возможно только после выделения метода TalkingThePhone. Процесс применения трансформации итеративный. Поиск частей конечного автомата, которые можно вынести в отдельный метод, можно автоматизировать.

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

Выделены три метода Initialize(), TalkingThePhone() (рис. 16) и Working() (рис. 17), содержащие 4, 5 и 4 состояния соответственно.

Заключение.

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

Литература

[1]обратно	Фаулер М., Бек К., Брант Д., Робертс Д., Апдайк У. Рефакторинг: улучшение существующего кода. — СПб.: Символ-Плюс, 2002. — 432 с.
[2]	William F. Opdyke, «Refactoring Object-Oriented Frameworks». PhD Thesis, University of Illinois at Urbana-Champaign. Also available as Technical Report UIUCDCS-R-92-1759, Department of Computer Science, University of Illinois at Urbana-Champaign.
[3]	Tom Mens. A Survey of Software Refactoring, IEEE Transactions on Software Engineering, Vol. 30, No. 2, February 2004.
[4]	Van Gorp, P.; Stenten, H.; Mens, T. and Demeyer, S. Towards Automating Source Consistent UML Refactorings, in Proc. Unified Modeling Language Conf. 2003, 2003.
[5]	Astels. D., ‘Refactoring with UML’, in Marchesi, M and Succi, G (eds). XP 2002 — Proceedings of the 3rd International Conference on eXtreme Programming and Flexible Proceses in Software Engineering, 2002.
[6]	Tom Mens, Niels Van Eetvelde, Dirk Janssens, and Serge Demeyer. Formalising refactorings with graph transformations. Fundamenta Informaticae, 2003.
[7]	Robert France, Dae-Kyoo Kim, Sudipto Ghosh, and Eunjee Song, «A UML-Based Pattern Specification echnique,» IEEE Transactions on Software Engineering, Vol.30, No.3, pp. 193-206, March 2004.
[8]	Marciniak J. J. The Encyclopedia of Software Engineering // Wiley Publishers. 2002. — 2076p.: il.
[9]	Буч Г., Рамбо Д., Джекобсон А. UML Руководство пользователя // М.: ДМК Пресс. 2001. — 432 с.: ил.
[10]	Меллор С., Кларк Э., Футагами Т. Разработка на базе моделей // Сайт журнала «Открытые Системы» (2005. 25 июня).
[11]	Селич Б., Практические аспекты разработки на базе моделей // Сайт журнала «Открытые системы» (2005. 25 июня).
[12]	Zs. Pap, I. Majzij, A. Pataricza, A. Szegi. Completeness and Consistency Analysis of UML Statechart Specifications // I.Maizik homepage: URL: http://home.mit.bme.hu/~majzik/publicat/ddecs2001.pdf (2005. 25 июня).
[13]	Unified Modeling Language: Superstructure // OMG official website: URL: http://www.omg.org/docs/formal/05-07-04.pdf (2005. 25 июня).
[14]	UML 2.0 OCL Specification // OMG official website: URL: http://www.omg.org/cgi-bin/apps/doc?ptc/03-10-14.pdf
[15]	H. Eriksson, M. Penker, B. Lyons, D. Fado. UML2 Toolkit // Indiapolis: Wiley Publishing Inc. 2004. — 511 p. il.

Работа выполнена при поддержке РФФИ, проект 05-01-00998-а.