Моделирование дискретно-событийных систем средствами графического языка состояний и переходов конечных автоматов
- -
- 100%
- +
1) семантические активности, связанные с состояниями автомата, включая:
активность, которая выполняется при входе в состояние (оператор entry),
активность, выполняемая в самом состоянии (оператор do),
активность, выполняемая при выходе из состояния (оператор exit).
2) активность, связанная с переходами между состояниями, которые связываются с дугами на диаграмме состояний,
3) возможность одновременного использования как активностей, связанных с состояниями, так и активностей, связанных с переходами,
4) определение начального состояния автомата, с которого начинает работу автомат при передаче ему управления, также начальное состояние определяется и в супер-состояниях, в случае иерархической декомпозиции состояний (начальное состояние обозначается в диаграмме закрашенным кругом),
5) определение конечных состояний в диаграмме состояний, т.е. состояний при достижении которых автомат завершает свою работу и, в случае вызова внешним автоматом, возвращает ему управление, включая выход по стеку вызовов из других объемлющих конечных автоматов (конечное состояние обозначается в диаграмме кругом с закрашенным кругом внутри),
6) суперсостояния, представляющие собой конечные наборы состояний и вложенных суперсостояний, что поддерживает иерархический подход в разработке моделей систем, позволяет существенно сократить число переходов (дуг в диаграмме), упростив описание сложного поведения,
7) ортогональность – параллельность исполнения независимых областей состояний (супер-состояний),
8) контроль событий, связанных с переходом состояний с помощью сторожевых предикатов защиты (Guards), которые в зависимости от значения условий, разрешают или блокируют переход,
9) запоминание истории выполнения диаграмм для обеспечения возможности при повторном входе в диаграмму продолжить ее выполнение с последнего исполнявшегося при выходе из нее состояния,
10) введение задержек и тайм-аутов для отражения в модели временных аспектов
11) введение ассоциаций с другими диаграммами состояний, в том числе с другими элементами модели и некоторые другие средства, расширяющие классические конечные автоматы.
1.6.
DEVS
— формализм для моделирования сложных динамических систем с использованием абстракции дискретных событий
DEVS (Discrete-Event Modelling and Simulation) – наиболее мощный формализм для моделирования сложных динамических систем с использованием абстракции дискретных событий, созданный профессором Бернардом Зейглером и его школой [16, 17, 18, 19]. Вообще, формализм DEVS не ограничивается только моделированием дискретных систем, а охватывает и другие виды моделирования, включая: непрерывное, параллельное, сетевое и марковское (вероятностное).
Здесь мы проанализируем возможности классического DEVS, предназначенного для моделирования дискретных событийных систем.
Формализм DEVS определяет два типа моделей:
(i) атомарные модели, обеспечивающие спецификации динамики компонентов системы
(ii) связанные модели, которые описывают, как соединить несколько компонентов модели (которые могут быть атомарными или связанными) вместе, чтобы сформировать новую модель
Иерархический способ построения моделей основан на доказательстве замкнутости операции связывания (coupling) формализма DEVS [18].
Атомарную модель DEVS можно рассматривать как автомат с набором состояний и функциями перехода, изменяющие состояние при возникновении внешнего события или по истечении времени. Когда никаких событий не происходит, состояние атомарной модели обновляется внутренней функцией перехода по истечении срока ее жизни. Когда происходит внешнее событие, атомарная модель изменяет свое состояние, применяя свою внешнюю функцию перехода. Время жизни состояния определяется функцией продвижения времени (time advance function). Каждое изменение состояния может создавать выходные сообщения через функцию вывода.
Атомарные модели являются неделимыми строительными блоками модели. Основными элементами атомарной модели являются:
1) Набор состояний модели (S)
2) Продвижение времени (ta) (Time Advance)
Для каждого состояния определен тайм-аут – функция, которая должна быть определена для каждого элемента набора состояний, она детерминировано возвращает длительность нахождения модели в соответствующем состоянии. Длительность может быть любым неотрицательным действительным числом, включая бесконечность. В DEVS допускается длительность равная нулю, которая как правило, используется в искусственных состояниях. (Заметим, что время моделирования — это просто действительное число, и его интерпретация зависит от пользователя).
3) Функция внутреннего перехода (δint)
δint: S → S
Функция внутреннего перехода δint определяет следующее состояние для каждого состояния, каждое состояние имеет не более одного следующего состояния, что предотвращает недетерминизм. Также в некоторых состояниях может не быть следующего состояния (например, если сдвиг во времени был указан как +∞), а некоторые состояния идентичны следующему состоянию.
4) Начальное общее состояние (qinit).
Определяет полное начальное состояние системы, причем это не «начальное состояние (sinit), а именно полное состояние, которое определяет не только начальное состояние системы, но и как долго система находится в этом состоянии. Поэтому к определению исходного общего состояния добавляется прошедшее время (Elapsed time), чтобы обеспечить большую гибкость при моделировании системы. Симулятору будет казаться, будто модель уже некоторое время находится в исходном состоянии.
qinit : (s, e)| s из S, 0=< e =
5) Набор выходов (Y)
Аналогично определению набора допустимых состояний, определяется набор допустимых выходов. Этот набор служит интерфейсом для других компонентов модели системы, определяя события, которые они могут получить. События также могут обладать сложными атрибутами. Если используются порты, каждый порт имеет свой собственный набор выходов. При переходе в новое состояние используется восклицательный знак, обозначающий генерацию выходных данных.
Y: ×li=1 Yi
6) Выходная функция (λ)
Данная функция реализует генерацию выходных событий. Функция вывода определяется по состоянию и детерминировано возвращает событие (или отсутствие события). Следует учитывать, что событие генерируется до достижения нового состояния, т.е. перед выполнением внутренней функции перехода.
Функция вывода может не возвращать никаких результатов, и в этом случае она возвращает специальный символ φ, тогда
λ: S → Y ∪ {φ}
7) Набор входов (X) – внешних событий
Определяет события, которые модель может получить извне, что также определяет интерфейс с другими моделями.
X = ×mi=1 Xi
8) Внешний переход (δext)
Внешняя функция перехода зависит от текущего состояния, она также определяет новое состояние системы. Функция внешнего перехода имеет доступ еще к двум значениям; прошедшее время и входное событие. Прошедшее время указывает, сколько времени прошло для этой атомарной модели с момента последнего перехода (внутреннего или внешнего). Хотя это число было неявно известно во внутренней функции перехода (т. е. значение функции продвижения времени), здесь оно передаётся явно.
На каждом временном шаге проверяется, запланировано ли внешнее событие перед внутренним событием. Если это не так, выполняется внутренний переход. Если есть внешнее событие, которое должно произойти первым, выполняется внешний переход.
Таким образом, формальная конфигурации модели описывается с помощью восьмиэлементного кортежа следующего вида:
Под связанной моделью в DEVS понимается структурная модель, объединяющая как атомарные модели, так и связанные подмодели. В отличие от атомарных моделей, связанная модель не определяет собственно поведенческих аспектов систем. Она отвечает за структурную организацию модели.
Для определения базовой структуры связной модели используются три элемента.
1) Экземпляры модели (D)
Набор экземпляров атомарных моделей определяет, какие модели включены в связанную модель:
(MS = {Mi |i ∈ D})
2) Спецификации модели (MS),
где Mi - спецификация i–ой атомарной модели. Для каждого элемента, определенного в D, спецификация представляет восьмиэлементный кортеж, определяющий атомарную модель.
MS = {Mi |i ∈ D} = {
Формальная семантика исполнения моделей в DEVF определяется с помощью связанного с формализмом DEVS алгоритма абстрактного симулятора (abstract simulator), обеспечивающего корректную реализацию поведения моделей.
По определению, подмодель связанной модели DEVS всегда должна быть атомарной моделью (в принципе, это расширяется для поддержки произвольных иерархий).
3) Влияние модели (Model influencees) - (IS = {Ii|i ∈ D ∪ {self }})
Помимо определения экземпляров модели и их спецификаций, необходимо определить связи между ними. Связи определяются с помощью наборов влияний (influencee sets): для каждого экземпляра атомарной модели определяется набор моделей, на которые влияет эта модель. Существует ограничение на связи, чтобы гарантировать невозможность создания несогласованных моделей: модель не должна влиять сама на себя, т.е. модель не должна быть элементом собственного набора влияний. ∀i ∈ D : i < Ii. Разрешены только связи внутри связанной модели, т.е. модели не должны напрямую влиять на модели за пределами текущей связанной модели, а также на модели, находящиеся глубже внутри других подмоделей на этом уровне, таким образом модель, на которую оказывается влияние должна принадлежать подмножеству множества моделей в этой связанной модели. ∀i ∈ D: Ii ⊆ D.
Как следствие, связанную модель можно определить с помощью трехэлементного кортежа:
<D, MS, IS>
Однако, чтобы связанная модель могла взаимодействовать с внешним миром, необходимо дополнить связанную модель входными и выходными событиями, которые служат интерфейсом для связанной модели. Тогда к этому кортежу добавляются компоненты Xself и Yself, соответственно набор входных и выходных событий, в результате чего получается кортеж из 5 элементов:
Отметим еще два механизма классического DEVS:
4) Это функция разрешения конфликтов (select), которая используется при выполнении сложных многокомпонентных моделей, когда возникает неопределенность в однозначном выборе порядка исполнения компонент модели. Эта функция принимает все конфликтующие модели и возвращает ту, которая имеет приоритет над остальными, решая конфликт эвристическими методами.
select: 2D → D
5) Функция трансляции (ZS), которая позволяет переименовывать выходные события моделей так, чтобы согласовать выходы со входами в другие модели. Функции трансляции определяются для каждого соединения, в том числе между входными и выходными событиями связанной модели.
ZS = {Zi,j |i ∈ D ∪ {self }, j ∈ Ii}
Функция трансляции неявно считается тождественной функцией, если она не определена. Если событию необходимо пройти несколько соединений, все функции перевода объединяются в цепочку в порядке прохождения.
В итоге связанная модель описывается семиэлементной конфигурацией элементов следующего вида:
Выводы
Проведенный анализ наиболее известных средств описания поведенческих аспектов систем на основе конечных автоматов показал, что графические языки на основе конечных автоматов широко и успешно применяются в моделировании поведенческих аспектов дискретных динамических систем.
В связи с чем в последующих главах описывается новый графический язык, названный DLAA, который характеризуется компактным и, одновременно, полным набором базовых средств, включением таких технологических возможностей как структурированная разработка диаграмм, параллелизмы и аппарат прерываний. Кроме этого, данный язык прост в реализации и поддерживает требование реализации как инструмента обогащения базовых средств разработки программного обеспечения автоматизации производства.
Глава 2. Определение языка
DLAA
, требований к языку, базовые операции языкового ядра
Разработка концепции и принципов построения языка во многом обусловлены требованиями, исходящими от рассматриваемых целей его применения. К основным требованиям, принятым при разработке языка DLAA, относятся следующие положения:
- язык должен быть построен по уровневому принципу, ядро языка должно содержать минимально необходимое число возможностей (операций над автоматами),
- язык должен быть достаточно универсальным, чтобы охватывать описание широкого спектра автоматных конфигураций,
- должна быть разработана формальная спецификация языка и верифицированы алгоритмы симуляции,
- язык должен включать средства, поддерживающие структурированную разработку сложных моделей,
- необходимо погружение языка и его инструментов в среду онтологической платформы, что позволит вести разработку моделей систем с применением непрерывного семантического контроля, используя логические средства платформы, обеспечивать непрерывную интеграцию создаваемых моделей с базой знаний жизненного цикла активов в масштабах всего проекта,
- семантическая часть моделей должна представлять собой совокупность именованных программных фрагментов на выбранном объектно-ориентированном языке программирования, связанных с конструктивными элементами модели и ими управляемых,
- язык и соответствующий ему инструментарий разрабатываются как средство обогащения базовых инструментальных средств программирования систем управления производственными объектами, требуется лёгкость реализации инструментальных средств языка и лёгкость их интеграции со средой программирования базового языка,
- необходимым условием является дуальность форм представления языка (как текстовой, так и графической),
- необходимость в простоте изучения и использования, так как предполагается его применение в учебных целях.
2.1. Ядро языка
Как определено выше, ядро языка должно содержать минимальное число операций композиций конечных автоматов. Отбор таких операций выполнялся на основе анализа алгебры конечных автоматов, предложенной в работе [3].
Первым кандидатом среди операций над автоматами для языка моделирования представляется операция системной композиции с согласованными событиями, т.к. она характеризуется, во-первых, значительной универсальностью, позволяя моделировать широкий класс автоматных конфигураций, и, во-вторых, является весьма экономичной при реализации (весовой характеристикой по состояниям). Более того, она допускает реализацию с линейной сложностью по числу автоматов-аргументов с помощью организации квазипараллельного способа работы входящих в нее автоматов. По существу, это универсальная операция, которой может оказаться достаточной для целей моделирования широкого класса задач.
Однако существенным недостатком операции системной композиции является общее поле событий, с помощью которых и осуществляются взаимодействие между автоматами моделируемой системы, так и переходы между состояниями внутри каждого автомата, при этом события должны быть согласованными (пользователем или инструментом), чтобы исключить сингулярность (неоднозначность), в процессе моделирования. Очевидно, что при увеличении числа автоматов в системе и числа состояний, число событий, определённых в одной области видимости, приводит систему в неуправляемое состояние.
Решением этой проблемы может быть структурирование поля событий, а именно разбиения событий на два класса: внешние для межавтоматного взаимодействия и внутренние, описывающие логику процессов работы автоматов.
Реализация этого решения приводит, во-первых, к развитию описания и реализации самой операции системной композиции, и, во-вторых, к расширению конструкции автомата Мили.
Эти вопросы решаются ниже посредством разработки формализмов определяемого языка моделирования.
2.2. Формализм спецификации конечного автомата языка
DLAA
В настоящем разделе предложенный в [3] алгебраический подход развивается в язык дискретного событийного моделирования динамических систем [19, 20]. Для адекватной поддержки задач моделирования поведения динамических систем выполняется функциональное расширение конечного автомата Мили.
Первым шагом для системы конечных автоматов введём два класса событий: внешних для межавтоматного взаимодействия и внутренних, описывающие логику процессов работы автоматов. Такое расширение автоматов Мили будет далее называться автоматами Мили* (Мили со звездочкой), при описании которых будет использоваться нотация подхода DAVS [16, 17, ],как наиболее близкого к рассматриваемому случаю.
Формальное определение автомата Мили* следующее:
Определение 1: Под расширенным конечным автоматом Мили, названным Мили*, будем понимать следующую конфигурацию:
FSM=<Ex, Ey, EI, S, F, qinit, δint, δext, λst , λtr, Ta, TS>, где (1)
Ex – множество внешних входящих событий автомата
Ey - множество внешних исходящих событий автомата
EI={i, *, **} - множество внутренних событий автомата
S - множество состояний автомата
F - множество конечных состояний автомата
qinit - начальное состояние автомата
δint - функция внутреннего перехода
δext - функция внешнего перехода
λst - функция вывода по состоянию
λtr - функция вывода по переходу
Ta – функция длительности пребывания в состоянии
TS - структура времени автомата
К характерным особенностям такого расширения понятия автомата Мили относятся:
1) Разделение множества событий в автомате на внутренние (обусловленные заданной логикой автомата) и внешние (E).
2) Различение внешних событий перехода E для каждого автомата на входящие (Ex) и исходящие (Ey).
3) Введение следующих внутренних событий автомата:
i - событие инициализации автомата, с помощью которого автомат становится активным и устанавливается в начальное состояние;
* – событие входа в состояние, которое рассматривается как начало выполнения некоторого (производственного) процесса;
** - событие выхода из состояния, которое рассматривается как выход из процесса состояния.
4) Для каждого автомата вводится функция внутреннего перехода (δint) из одного состояния в другое:
δint: S → S, где S – множество состояний автомата.
Функция внутреннего перехода для каждого состояния определяет следующее состояние производственного цикла, описываемого автоматом. В некоторых состояниях следующее состояние может отсутствовать. Такие состояния считаются конечными для автомата. Они принадлежат множеству F. Также вводится возможность условных локальных переходов из одного состояния в другое. В этом случае используется решающий предикат, связанный с двумя локальными состояниями, переход в одно, из которых осуществляется в зависимости от истинности или ложности предиката. Такой механизм позволяет строить разветвлённые структуры связей между локальными состояниями автомата.
5) Для каждого автомата вводится функция внешнего перехода (δext):
δext: SxEx → S
Функция внешнего перехода определяет новое состояние автомата в зависимости от текущего состояния и внешнего входящего события. Для внешних входящих событий функция внешнего перехода имеет приоритет перед событием внутреннего перехода.
6) Для каждого автомата определена функция длительности состояния (ta) (Time Advance) – аналогичная функции продвижения времени в системе DEVS [16, 17], ставящая в соответствие длительность нахождения модели в соответствующем состоянии. Длительность может быть любым действительным неотрицательным числом (в том числе случайным числом), включая бесконечность, соответствующим единицам времени структуры времени TS. Длительность равная нулю, как правило, используется в искусственных состояниях.
7) В отличие от системы DEVS в автоматах рассматриваемого вида используются две функции вывода - функция вывода по состоянию (λst) и функция вывода по переходу (λtr). Использование обеих функций вывода, в частности, применяется в режиме отладки моделей.
Функция λst, если определена, может выводить вызовы исходящих сообщений в буфер вывода, когда автомат переходит в конкретное состояние. В случае, если функция для некоторого состояний не определена, считается, что функция генерирует пустое сообщение φ.
Функция λtr реализует (если определена) свой вывод аналогично функции λst, но срабатывает, когда автомат, находясь в состоянии S, получает на входе входящее событие из множества E или внутреннее событие выхода из состояния **, после чего осуществляется переход в новое состояние.
8) Понятие состояния данного класса автоматов рассматривается как абстракция некоторого производственного процесса, в общем случае имеющего длительность во времени. Длительности равные нулю или бесконечности также возможны как частные случаи, что часто используется в технических решениях при моделировании систем. Моделирование процесса, протекающего в конкретном состоянии автомата реализуется с помощью рассмотренных выше двух типов внутренних событий – входа в состояние, соответствующего началу производственного процесса, и выхода из состояния, моделирующего выход из процесса. Внутренние события входа в состояние обозначаются звёздочкой - *, а события выхода из состояния – двумя звёздочками - **.
9) В общем случае каждый автомат обладает собственной структурой времени TSA. Поэтому при моделировании систем, состоящих из нескольких компонентов, представленных в модели отдельными автоматами, работающими в собственных временных структурах, важной задачей становится приведение временных структур компонентов к общей временной структуре системы. Примером здесь может служить модель центрального процессора, компоненты которого такие как, арифметическое и логическое устройство, память, кэши работаю в собственных тактовых режимах.