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

Проектирование конечных автоматов по методу 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

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

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

КОНЕЧНЫЙ АВТОМАТ / STATE MACHINE / SWITCH-ТЕХНОЛОГИИ / SWITCH-TECHNOLOGY / АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ / STATE MACHINE PROGRAMMING / РЕАКТИВНЫЕ СИСТЕМЫ / МОДЕЛИРОВАНИЕ / SIMULATION / STATEFLOW / COMPLEX SYSTEM

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Казаненко Мария Дмитриевна

Рассмотрены проблемы проектирования сложных систем, вопросы применения автоматного управления, Switch-технологии . Обоснованы преимущества использования автоматного подхода. Описано моделирование систем управления при помощи программ Simulink и State flow.

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

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Казаненко Мария Дмитриевна

Парадигма автоматного программирования
Разработка резервированного блока управления электроприводом на основе автоматного подхода
Разработка методики автоматного программирования для управления асинхронным электродвигателем
Автоматизированные системы управления технологическими процессами. Scada система. Часть i

Проектирование и реализация систем управления дискретными событийными системами на основе иерархических модульных недетерминированных автоматов (Ч. 2. Методы и средства)

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

USAGE OF STATE MACHINE THEORY IN COMPLEX SYSTEM SIMULATION USING STATEFLOW

This article presents the main problems of complex system engineering, usage of state machine control and Switch-technology , explains advantages of using state machine attitude, and describes system»s simulation using Simulink and Stateflow .

Текст научной работы на тему «Применение теории конечных автоматов при моделировании сложных систем с использованием программы Stateflow»

- М.Д. Казаненко, 2015

ПРИМЕНЕНИЕ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ ПРИ МОДЕЛИРОВАНИИ СЛОЖНЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ПРОГРАММЫ STATEFLOW

Рассмотрены проблемы проектирования сложных систем, вопросы применения автоматного управления, Switch-технологии. Обоснованы преимущества использования автоматного подхода. Описано моделирование систем управления при помощи программ Simulink и State flow.

Ключевые слова: конечный автомат, Switch-технологии, автоматное программирование, реактивные системы, моделирование, Stateflow.

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

В 1991 г. А.А. Шалыто было предложено решение данной проблемы: Бш^сЬ-технологии — технология разработки систем логического управления на базе конечных автоматов, охватывающая процесс спецификации, проектирования, реализации, отладки, верификации, документирования и сопровождения была предложена.

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

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

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

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

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

При рассмотрении всевозможных деталей использования автоматных моделей в программировании ста-

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

Приведем формальное определение автоматизированного объекта управления.

Пара А,О, состоящая из управляющего автомата и объекта управления, называется автоматизированным объектом управления.

Управляющий автомат представляет собой шестерку (X, У, Z, у 8, ф),

ное множество входных воздействий, причем каждое входное воздействие х состоит из компоненты хЕ, порождаемой внешней средой, и компоненты х0, порождаемой объектом управления; У — конечное множество управляющих состояний; Z — конечное множество выходных воздействий; у0еУ — начальное состояние; ф = (ф’, ф») — функция выходов (выходных воздействий), состоящая, в общем случае, из двух компонент: функции выходных воздействий в состояниях ф’: У^Z и функции выходных воздействий на переходах ф1′:XxУ^■Z; 8: ХхУ^У — функция переходов.

Объект управления — это тройка (V, ¡ч, /), где V — потенциально бесконечное множество вычислительных состояний (или значений); / —

функция, сопоставляющая входное воздействие вычислительному состоянию; /.: ZxV^V — функция, изменяющая вычислительное состояние в зависимости от выходного воздействия.

Функции и / являются математическими эквивалентами набора запросов и набора команд соответственно.

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

Основные этапы проектирования системы:

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

• Строится набор управляющих состояний.

• Каждому запросу объектов управления ставится в соответствие входная переменная автомата, каждой команде — выходная. На основе управляющих состояний, событий, входных и выходных переменных строится автомат, обеспечивающий заданное поведение системы.

• Построение визуального интерфейса системы: «Система управления» — «Оператор».

В качестве примера рассматривается модель «Частотно-регулируемый привод — Задвижка».

Введем обозначения входов и выходов, которые затем будут использоваться в моделировании:

1. Входные (управляющие) воздействия: х1 — «Открыть», х2 — «Закрыть».

2. Выходные данные: z1 — «Задвижка открыта», z2 — «Задвижка закрыта», z3 — «Переходное состояние».

Для моделирования системы используется программа Ма^аЬ с под-программным пакетом Б1тиНпк, а так же графическое приложение Б1а1еАош.

(рис. з). Итоговый график переходных процессов представлен на рис. 4.

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

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

1. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. — СПб., 2008. -167 с.

2. Козаченко В.Ф. Эффективный метод программной реализации дискретных управляющих автоматов во встроенных системах управления.

КОРОТКО ОБ АВТОРЕ_

_ СПИСОК ЛИТЕРАТУРЫ

3. Вавилов К.В. Программируемые логические контроллеры SIMATIC S7-200 (SIEMENS). Методика алгоритмизации и программирования задач логического управления. [ГШ

Казаненко Мария Дмитриевна — студентка, МГИ НИТУ «МИСиС», e-mail: ud@msmu.ru.

UDC 621.37/39:658.011.56 USAGE OF STATE MACHINE THEORY IN COMPLEX SYSTEM SIMULATION USING STATEFLOW

Kazanenko M.D., Student,

Moscow Mining Institute, National University of Science and Technology «MISiS», e-mail: ud@msmu.ru.

This article presents the main problems of complex system engineering, usage of state machine control and Switch-technology, explains advantages of using state machine attitude, and describes system’s simulation using Simulink and Stateflow.

Key words: state machine, Switch-technology, state machine programming, complex system, simulation, Stateflow.

1. Polikarpova N.I., Shalyto A.A. Avtomatnoe programmirovanie (Automatic programming), Saint-Petersburg, 2008. 167 p.

2. Kozachenko V.F. Effektivnyi metod programmnoi realizatsii diskretnykh upravlyayushchikh avtomatov vo vstroennykh sistemakh upravleniya (Efficient method of software implementation of discrete control automations in inbuilt control systems).

3. Vavilov K.V. Programmiruemye logicheskie kontrollery SIMATIC S7-200 (SIEMENS). Metodika al-goritmizatsii i programmirovaniya zadach logicheskogo upravleniya (Programmable logic controllers SIMAT-1CS7-200 (SIEMENS). Procedure of algorithmization and programming of logic control).

Конечный автомат: теория и реализация

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

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

• Написание ИИ для хоккея. Часть 1.
• Написание ИИ для хоккея. Часть 2.
• Написание ИИ для хоккея. Часть 3.

Примечание автора Хоть в статье используются ActionScript 3 и Flash, вы с легкостью можете писать на удобном для вас языке.

Что такое конечный автомат?

Конечный автомат (или попросту FSM — Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

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

Планирование состояний и их переходов

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Реализация простого конечного автомата

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

public class FSM < private var activeState :Function; // указатель на активное состояние автомата public function FSM() < >public function setState(state :Function) :void < activeState = state; >public function update() :void < if (activeState != null) < activeState(); >> > 

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

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM — это делает наш класс более универсальным.

Использование конечного автомата

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Наш муравей представлен классом Ant, в котором есть поле brain. Это как раз экземпляр класса FSM.

public class Ant < public var position :Vector3D; public var velocity :Vector3D; public var brain :FSM; public function Ant(posX :Number, posY :Number) < position = new Vector3D(posX, posY); velocity = new Vector3D( -1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); >/** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void < >/** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void < >/** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void < >public function update():void < // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); >(. ) > 

Класс Ant также содержит свойства velocity и position. Эти переменные будут использоваться для расчета движения с помощью метода Эйлера. Функция update() вызывается при каждом обновлении кадра игры.

Для понимания кода мы опустим реализацию метода moveBasedOnVelocity(). Если хотите узнать поподробнее на тему движения, прочитайте серию статей Understanding Steering Behaviors.

Ниже приводится реализация каждого из методов, начиная с findLeaf() — состояния, ответственного за поиск листьев.

public function findLeaf() :void < // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) if (distance(Game.mouse, this) > 

Состояние goHome() — используется для того, чтобы муравей отправился домой.

public function goHome() :void < // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) > 

И, наконец, состояние runAway() — используется при уворачивании от курсора мыши.

public function runAway() :void < // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) < // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.setState(findLeaf); >> 

Улучшение FSM: автомат, основанный на стеке

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

public class StackFSM < private var stack :Array; public function StackFSM() < this.stack = new Array(); >public function update() :void < var currentStateFunction :Function = getCurrentState(); if (currentStateFunction != null) < currentStateFunction(); >> public function popState() :Function < return stack.pop(); >public function pushState(state :Function) :void < if (getCurrentState() != state) < stack.push(state); >> public function getCurrentState() :Function < return stack.length >0 ? stack[stack.length - 1] : null; > > 

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

Важно отметить, что при использовании конечного автомата на основе стека каждое состояние несет ответственность за свое удаление из стека при отсутствии необходимости в нем. Например, состояние attack() само должно удалять себя из стека в том случае, если враг был уже уничтожен.

public class Ant < (. ) public var brain :StackFSM; public function Ant(posX :Number, posY :Number) < (. ) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (. ) >/** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void < // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) if (distance(Game.mouse, this) > /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void < // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) if (distance(Game.mouse, this) > /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void < // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) < // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); >> (. ) > 

Вывод

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

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

Перевод статьи «Finite-State Machines: Theory and Implementation».

Следите за новыми постами по любимым темам

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

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

В статье 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-а.

• 27.10 — Президент утвердил проект Российской орбитальной станции — её развернут с 2027 по 2032 годы
• 27.10 — Microsoft Word отмечает 40-летний юбилей
• 27.10 — Samsung предложила пользователям резервное хранение и перенос данных между устройствами
• 27.10 — Выручка и прибыль IBM за III квартал превзошли ожидания аналитиков
• 27.10 — Роскомнадзор добавил PUBG Mobile в реестр организаторов распространения информации — такое с играми происходит впервые
• 27.10 — Переговоры о слиянии Western Digital и Kioxia развалились
• 27.10 — По итогам года Intel рассчитывает увеличить выручку, акции выросли на 7,7 %
• 26.10 — Доступна СУБД MySQL 8.2.0
• 26.10 — Глава Microsoft признал отказ от Windows Phone стратегической ошибкой
• 26.10 — Cisco и Bang & Olufsen представили TWS-наушники для звонков и конференций
• 26.10 — Поиск Google начал показывать происхождение и эволюцию изображений
• 24.10 — Показатель внедрения российского общесистемного ПО в 2023 году увеличен вдвое
• 24.10 — Полное отключение сетей 3G в России случится до 2027 года
• 24.10 — «Яндекс» объединил «Маркет», «Еду» и «Лавку» в единую структуру для технологической интеграции
• 24.10 — Роскомнадзор не смог остановить рост числа пиратских ресурсов с фильмами и музыкой
• 24.10 — В Chrome появится функция сокрытия IP-адреса, затрудняющая слежку за пользователями
• 24.10 — Биткоин подорожал до $35 000 — с начала года криптовалюта выросла вдвое
• 23.10 — В Chrome планируют реализовать режим скрытия IP-адреса пользователя
• 23.10 — Япония запустила антимонопольное расследование против Google — под подозрением ситуация с поиском
• 23.10 — Биткоин вырос на 11 % за одну неделю — курс штурмует $31 000