Инструментальная среда имитационного моделирования

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Формальные модели распределенных систем

1.1 Классические сети Петри

1.2 Временные сети Петри

1.3 Сети активных ресурсов

1.4 Ресурсно-управляемые сети автоматов

1.5 Временные автоматы

1.6 Ресурсно-управляемые сети временных автоматов

2. Система TRDA Tool

2.1 Анализ исходных данных и выбор оптимального решения поставленной задачи

2.2 Методы проектирования

2.3 Обоснование выбора программных и аппаратных средств

2.4 Проектирование связей ключевых компонент языка описания RDA сетей

2.5 Разработка языка описания модели типа ресурсно-управляемых сетей временных автоматов

2.6 Описание разработанного языка в нотации Бэкуса-Наура

2.7 Возможности TRDA Tool

2.7.1 Возможности моделирования

2.7.2 Возможности анализа

2.7.3 Поведенческие свойства

2.7.4 Способ установки программы

2.7.5 Соответствие графической визуализации текущего состояния модели ее структурному представлению

3. Примеры применения trda tool для моделирования и анализа некоторых классических задач

3.1 Задача об обедающих философах, гуляющих в парке

3.2 Задача о философах с дедлоком

3.3 Задача о спящем парикмахере

3.4 Задача о мусорщиках

3.5 Задача о курильщиках

Заключение

Список использованной литературы

Приложения

распределенный автомат графический визуализация



Введение

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

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



Таблица 1 - Интересующие нас свойства формальных моделей

Формальная модель	Основные интересные для нас свойства
Классические Сети Петри [8]	Известная классическая модель, графическая визуализация, наличие большого количества алгоритмов для проверки свойств
Временные сети Петри: модель Мерлина [6], модель Штарке [7]	Учет временных характеристик: время выполнения перехода, время задержки начала выполнения перехода
Временные автоматы [1]	Учет временных характеристик: несколько счетчиков внутри одной модели, сбросы счетчиков, ограничения
Сети активных ресурсов [2] - AR nets	Эквиваленты по выразительности классическим сетям Петри. Модель ресурсно-ориентированна: вместо классического разделения вершин на позиции и переходы (активные и пассивные компоненты) в данной модели один тип вершин, но два типа дуг - потребляющие и производящие.
Ресурсно-управляемые сети автоматов [3] - RDA nets	Двухуровневое обобщение сетей активных ресурсов. Конечные автоматы, представляющие элементные сети в данной модели (аналог фишки в классических сетях Петри) могут вести себя как активным, так и пассивным образом (производить/потреблять ресурсы или быть потребленными/быть произведенными ресурсами)

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

Таблица 2 - Программные инструменты и реализуемые ими формальные модели

Программный инструмент	Формальная модель
CPN Tool [10], ProM [11]	Классические сети Петри [8]
UPPAAL [9]	Временные сети Петри: модель Мерлина [6], модель Штарке [7]
UPPAAL [9]	Временные автоматы [1]
	Сети активных ресурсов [2]
	Ресурсно-управляемые сети автоматов [3]

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

Разработать формальную модель для описания распределенных систем мобильных агентов - ресурсо-управляемые сети временных автоматов и создать инструментальную среду имитационного моделирования на основе данного формализма.



1. Формальные модели распределенных систем

В данном разделе будут изложены теоретические основы выбранных для исследования моделей. На схеме 1 ниже приведена взаимосвязь разрабатываемой модели с уже существующими формальными моделями. Зеленым цветом на диаграмме выделена разрабатываемая модель - TRDA модель. Желтые квадраты - модели, послужившие основой для разработки ресурсно-управляемых сетей автоматов в данной работе. Формальные модели в красных квадратах приведены на диаграмме для представления взаимосвязи разрабатываемой модели с другими известными по литературе формализмами.

Схема 1. Предыстория формализма TRDA

1.1 Классические сети Петри

Классические сети Петри - это формальная модель, разработанная Карлом Адамом Петри в 1962 для описания химических реакций [8]. Модель представляется в виде двудольного ориентированного графа, где два типа вершин соответствуют позициям (метсам) и переходам. Внутри вершин типа «Позиция» находятся фишки, изображенные в виде черных точек, символизирующие ресурсы. Позиции соединены с переходами (вершинами типа «Переход») с помощью направленных дуг, сверху на которых указывается их кратность. Считается, что переход готов к срабатыванию, если имеется достаточное количество фишек во входных позициях данного перехода (достаточность определяется с учетом кратности входных дуг данного перехода).

Дадим формальное определение Сети Петри. Сетью Петри называется набор

N=(P,T,F,M0),

P -- конечное множество мест

T -- конечное множество переходов, PT=

F: (PT)(TP)Nat -- функция инцидентности (0 включается в множество натуральных чисел). Функция инцидентности определяет наличие и кратность направленных дуг между позициями и переходами (и наоборот, между переходами и позициями) .

Маркировкой сети Петри N называется функция M: P Nat, сопоставляющая каждой позиции сети некоторое натуральное число - количество фишек в данной позиции.

Маркировка M0 - начальная маркировка, то есть начальная разметка системы.

Переход tT активен при разметке M, если pP M(p)F(p,t) . Это условие означает, что во входных позициях перехода t количество фишек больше или равно кратности соответствующих входных дуг этого перехода.

Активный при разметке M переход t может сработать, породив при этом новую разметку M', где pP M'(p) =def M(p)F(p,t)+F(t,p). В новой разметке количество фишек, в позициях, из которых идут входные дуги перехода, уменьшается на кратность соответствующих дуг. Аналогичным образом, количество фишек в позициях, в которые идут выходные дуги перехода, увеличивается на кратность выходных дуг перехода.



1.2 Временные сети Петри

Для более выразительного моделирования можно использоваться сети Петри со временем. Время может быть введено в различные элементы сети: время срабатывания перехода; время, которое фишка находится в состоянии, и т.д. Существует две основные модели временных сетей Петри: модель Мерлина [6] и модель Штарке [7].

Рассмотрим эти две модели, введя время в срабатывание переходов.

Пусть N - множество натуральных чисел, а R - множество рациональных чисел

1)Модель Мерлина - непрерывно временная модель.

Непрерывно-временной сетью Петри называется набор

CTN=(P,T,F,M0,D),

где

(P,T,F,M0) - классическая сеть Петри

D:T>Interv -- временная функция, сопоставляющая каждому переходу t ? T интервал D(t) из множества Interv, где множество Interv = {[d1,d2] ?R,d1?d2}.

Активность перехода определяется аналогичным классическим сетям Петри образом.

Пусть V:T>R -- множество наборов значений часов, связанных с переходами из T.

Состоянием в CTN называется пара q=<M,н>, где M -- маркировка в CTN и н?V.

Будем говорить, что в состоянии q=<M,н> переход t ? T может сработать, если переход T активен t ? En(M) и счетчик времени v(t)?D(t), соответствующий переходу t v(t), имеет значение, попадающее в интервал, задаваемый временной функцией данного перехода D(t).

Срабатывание перехода происходит мгновенно.

2)Модель Штарке - дискретно временная модель. [7]

Дискретно-временной сетью Петри называется набор

DTN=(P,T,F, M0,D),

где

(P,T,F,M0) - классическая сеть Петри

D:T>N -- временная функция, сопоставляющая каждому переходу натуральное число, соответствующее временной длительности его срабатывания.

Для каждого перехода t значение D(t) определяет длительность срабатывания t, т.е если переход t срабатывает в момент времени x, то фишки из входных мест перехода t "уходят" в момент времени x и появляются в выходных местах перехода t в момент времени x + D(t).

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

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

1.3 Сети активных ресурсов

Сеть активных ресурсов [2], AR nets, - еще один формализм для моделирования распределенных систем. Идея связана с тем, что активные агенты системы являются одновременно ее ресурсами. AR nets по выразительности эквиваленты классическим сетям Петри. Однако они отличаются от классических сетей Петри способом моделирования. В отличие от классических сетей Петри, в которых вершины разбиты на позиции и переходы (активные и пассивные компоненты), в AR nets все вершины одного типа, а дуги делятся на производящие и потребляющие.

Сетью активных ресурсов называется набор AR=(V,I,O), где

V -- конечное множество вершин

I: (VV) Nat -- множество потребляющих дуг. Потребляющей дуге ставится в соответствие количество потребляемых ресурсов.

O: (VV) Nat -- множество производящих дуг. Производящей дуге ставится в соответствие количество производимых ресурсов.

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

Разметкой сети AR называется функция вида M: V Nat. Для каждой вершины определяется количество находящихся в ней фишек (ресурсов).

Ресурс (агент) в вершине vV активен при разметке M, если M(v)>0 (узел v непустой) и wV M(w)I(w,v) (в потребляемых узлах вершины v, из которых идут потребляющие дуги в вершину v, содержится достаточное количество фишек). Активный ресурс v при разметке M может сработать, порождая при этом новую разметку M', где wV M'(w) =def M(w)I(w,v)+O(v,w). Как видно, вершина, в которой находится активный ресурс, срабатывает, как если бы она временно стала переходом в обычной сети Петри.

1.4 Ресурсно-управляемые сети автоматов

Ресурсно-управляемые сети автоматов, RDA-сети, [3] - разработанный на основе AR-сетей формализм для моделирования взаимодействия распределенных агентов с учетом ресурсных зависимостей. RDA-сеть имеет два уровня. Системный уровень задается сетью активных ресурсов, которая описывает распределение агентов/ресурсов и порты, через которые они могут взаимодействовать. Агенты, представлены конечными автоматами, взаимодействующими друг с другом через порты системной сети. Выполнение агентом перехода может быть связано с потреблением и производством ресурсов.

Константа в модели RDA nets - это аналог фишки в классических сетях Петри. Константы могут быть как простыми ресурсами, так и агентами, имеющими структуру конечного автомата. Все константы типизированы. Пусть ? - конечное множество типов (types). Типы ? типизируют как константы, так и порты системной сети. Тип порта означает, что по нему возможна обработка (потребление или производство) констант только данного типа.

П - конечное множество типизированных портов. Для порта p П, тип порта обозначается type(p). При этом type(p) ?.

Const - Множество констант, каждая из которых принадлежит некоторому типу A, где А ?.

Системная сеть - кортеж SN= (V,I,O,р), где

(V,I,O) - сеть активных ресурсов: набор вершин, соединенных между собой потребляющими и производящими дугами.

р : (IO) П - функция разметки дуг именами портов

Маркировкой M системной сети SN называется функция M: V М(Const), где М(Const) - мультисет множества Const, множество состоящее из произвольного (в том числе и равного 0) количества элементов множества Const. Таким образом, в любой вершине системной сети может находится произвольное количество констант из множества Const любого типа и маркировка М задает заполнение вершин системной сети фишками (агентами и ресурсами).

Элементная сеть

Ресурсно-управляемый автомат A=( SA,TA,lA), типа A (A?), где

S A - конечное множество состояний

TA? SA SA - конечное множество переходов

lA: TALA пометки переходов (перечень входных и выходных термов перехода)

LA - выражение на языке L для автомата A.

L - язык выражений вида р1у1e1+ р2у2e2+…+ рkуkek, где

рi - имена портов ( type(рi) ? )

уiу{?,!}, где ? - потребление, ! - производство

ei - переменная или константа типа рi

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

Выполнение перехода t агента А требует ресурсы, перечисленные во входных термах этого перехода lA(t). Входной терм имеет вид рi?ej, где ej - переменная или константа того же типа , что и порт рi. Выходной терм имеет вид рi!ej. Выходной терм определяет, где и какие объекты будут созданы (произведены) в результате выполнения перехода.

1.5 Временные автоматы

Формальная модель временных автоматов [1] была разработана Alur и Dill в 1994 году.

Временной автомат - это конечный автомат, расширенный с помощью вещественных переменных (счетчиков). В начале работы все счетчики равны нулю. В процессе работы счетчики синхронно увеличиваются. На каждом переходе имеется охранник (guard) - это разрешающее (а не обязывающее) условие. Временной автомат - это кортеж A = (L, L0,Lacc , ?, X, E), где

L -конечное множество позиций (вершин)

L0 L - начальная позиция (вершина)

Lacc ? L - множество принимаемых (в качестве финальных) позиций

? - конечный алфавит

X - конечное множество счетчиков

E LG ?2XL - множество ребер

G = {x op c | x X, c N} - множество охранников

op {<,<=,=, >=,>}

2X - все возможные комбинации наборов счетчиков (для сброса, обнуления, значений счетчиков - reset). Сброс счетчика x обозначается на схеме «{x}».

Пример:

Рисунок 1. Пример классического временного автомата.

Зеленым выделены охранники (guard) (x > 0, x=1, y=1) (фф, в данной нотации, обозначает отсутствие охранников)

Синим - символы входного слова (a, b)

Красным - сбросы счетчиков (reset clocks) ({x}, {y} )

Голубым - счетчики (часы) (clock) ( X ={x,y} )

Значение vR назначает каждому счетчику его часовое значение

Состояние (l,v) LR состоит из позиции и значений счетчиков

Изменение состояний временного автомата могут быть двух типов:

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



(l,v) (l,v+ф)

переход в новое состояние, то есть автомат переходит в следующую позицию, а вместе с этим изменяется и значение счетчиков

(l,v) (l',v')

Ресурсно-управляемые сети временных автоматов

Модель ресурсно-управляемых сетей временных автоматов, TRDA nets, - модель, созданная в рамках данной работы. TRDA модель строится на базе ресурсно-управляемых сетей автоматов с добавлением возможностей временных сетей Петри или временных автоматов. Тем самым в данной работе были созданы две разновидности TRDA моделей. Будем обозначать TRDAPetri nets - модель, построенную с добавлений возможностей временных сетей Петри в элементную сеть и TRDATimed automata - модель с добавлений возможностей временных конечных автоматов. В случае, если при изложении нет разницы, про какую из моделей идет речь, будем обозначать модель как TRDA. TRDA сеть (обеих разновидностей) является двухуровневой сетью, состоящей из системного и автоматного (элементного) уровней. Системная сеть - это распределенная система позиций (вершин), соединенных между собой потребляющими и производящими дугами, аналогичная сетям активных ресурсов. Автоматные (элементные) сети - это совокупность графов изменения состояния агентов, которые являются расширенными конечными автоматами, асинхронно потребляющими/производящими общие ресурсы через входные/выходные порты (поименованные и типизированные дуги) системной сети.

Константа в модели TRDA nets - это аналог фишки в классических сетях Петри. Константы могут быть как простыми ресурсами, так и агентами, имеющими структуру конечного автомата с добавлением временных характеристик. Все константы типизированы. Пусть ? - конечное множество типов (types). Типы ? типизируют как константы, так и порты системной сети. Тип порта означает, что по нему возможна обработка (потребление или производство) констант только данного типа.

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

Обозначим R как множество вещественных чисел.

Дадим определение системной сети TRDA модели. Оно аналогично системной сети RDA модели.

(Напомним,

Системная сеть SN=(V,I,O,р) - это сеть активных ресурсов, где

V -- конечное множество вершин

I: (VV) -- множество потребляющих дуг

O: (VV) -- множество производящих дуг

р : (IO) П - функция разметки дуг именами порта)

Теперь дадим определение элементной сети. Ее определение различно для TRDAPetri nets и TRDATimed automata.

Рассмотрим элементную сеть TRDAPetri nets:

Элементная сеть APetri nets=(SA, TA, lA, WaitA, TimeA) конечный автомат с дополнительными пометками переходов, где A=( SA,TA,lA) - RDA сеть.

( Напомним,

SA - конечное множество состояний

TA? SA SA - конечное множество переходов

LA :TA L - функция разметки переходов, сопоставляющая каждому переходу описание входных и выходных термов на языке выражений (L) вида р1у1e1+ р2у2e2+…+ рkуkek, где

рi - имена портов ( type(рi) ? )

уi{?,!}, где ? - потребление (вход), ! - производство (выход)

ei - переменная или константа типа рi )

WaitA: TA Interv - функция, сопоставляющая каждому переходу временной интервал, время ожидания срабатывания перехода. В ходе выполнения модели в момент, когда переход становится активным, из этого интервала произвольным образом выбирается число. Это число означает время, когда сработает (начнет выполняться) переход при условии, если он в течение всего этого времени будет оставаться активными.

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

Interv = {[d1,d2] ?R,d1?d2}.

Теперь рассмотрим элементную сеть TRDA Timed automata.

Элементная сеть ATimed automata =(SA, TA, lA, TimeA, XA, GA, ResetA) конечный автомат с дополнительными пометками переходов, где

A=( SA,TA,lA) - RDA сеть

TimeA - аналогично TRDAPetri nets

XA - множество счетчиков времени. В начале работы все счетчики равны нулю. В процессе работы все счетчики синхронно увеличиваются.

GA: TA{ConstrA} - функция, сопоставляющая каждому переходу набор ограничений ConstrA., где

ConstrA - ограничение, предикат вида x?c или y+z?c или x-y?c, где x,y,zXA, а ? может принимать значения {<,?,=,?,>}, с N.

В случае, если все ограничения GA(t) перехода t автомата A выполняются в некоторый момент времени, когда данный переход активен, то переход может сработать.

ResetA: TA{reset(x)|xXA} - функция, сопоставляющая каждому переходу набор счетчиков времени, сбрасывающих свои значения в ноль при выполнении этого перехода. Сбросы счетчиков могут отсутствовать в некотором переходе, это означается, что ни одно из значений счетчиков при выполнении этого перехода в ноль не сбрасывается. Так же возможно сбрасывать значения сразу нескольких счетчиков при выполнении одного перехода.

Состояние системы Y - это отображение вершины системной сети в мультимножество пар: агент A и его состояние S.

Теперь дадим определение, что будем называть состоянием агента в случае TRDAPetri nets и TRDATimed automata и как будет выполняться модель.

TRDATimed automata:

Возможны следующие варианты смены состояний агента:

агент находится в некотором состоянии, и ни один из его переходов не активен

агент имеет один или несколько активных переходов, и ожидает того, что ограничение на одном или нескольких переходах станет выполняться

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

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

Более детальное пояснение приведено ниже. Пусть переходы tr1 и tr2 агента б активны в состоянии s.

После загрузки системы все счетчики принимают значения 0. В случае, если в процессе работы системы создается новый агент, т.е. новая автоматная сеть, а с ней и новые счетчики, то они получают начальные значения так же равные 0. В случае, если на текущий момент, у нас есть два активных (с точки зрения наличия необходимых для их выполнения ресурсов) перехода tr1 и tr2, рассматриваются их ограничения (охранники). В случае, если ограничение ни на перехода tr1, ни на переходе tr2 не выполняется, значения счетчиков (совместно с глобальным временем системы) увеличивается до тех пор, пока одно их ограничений не начнет выполняться. ( В случае, если ограничения на переходах tr1 и tr2 выполняются одновременно, то переход для выполнения выбирается либо случайным образом с учетом весовых коэффициентов вероятности соответствующих переходов, либо на усмотрение пользователя.) Затем для того перехода, для которого выполнилось ограничение, начинается отчет длительности выполнения перехода. В конце выполнения перехода осуществляется обнуление счетчиков, указанных в спецификации reset данного перехода. После этого агент производит все ресурсы, указанные в выходных термах перехода.

Если в системе нет активных (имеющих активные переходы) агентов, то рассматривается множество работающих агентов и их временные характеристики - оставшееся время выполнения работающих переходов. Находится минимальное время: timemin. Время всех агентов перевычисляется путем вычитания timemin и те агенты, которые получили время 0, завершают работу своего перехода и производят ресурсы, предусмотренные для этого перехода.

TRDAPetri nets

Возможны следующие варианты смены состояний агента:

агент находится в некотором состоянии, и ни один из его переходов не активен

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

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

агент закончил выполнение перехода, произвел все соответственные ресурсы, перешел в следующую позицию

. Пусть Y некоторое состояние системы, и пусть переходы tr1 и tr2 агента б активны в состоянии s.

Тогда агент б переходит в состояние {<s, w1>, <s,w2>}, где wi - время ожидания начала работы перехода tri, выбранное из соответствующих временных интервалов переходов tr1 и tr2. В дальнейшем возможны три варианта: если w1<w2, если w1>w2 и если w1=w2.

В первом случае, по истечению w1, для перехода tr1 определится время t1, выбранное из своего соответствующего интервала, означающее длительности работы перехода tr1. Во втором случае, по истечению w2, для перехода tr2 определится время t2, выбранное из своего соответствующего интервала, означающее длительности работы перехода tr2. В третьем случае, в ход вступает весовой коэффициент вероятности, заданный для переходов (либо, в случае пошагового выполнения, решение принимает пользователь). Если для перехода весовой коэффициент вероятности не задан, то, по умолчанию весовой коэффициент равен 100 (для всех переходов). Если весовые коэффициенты вероятности конкурирующих переходов одинаковые, то вероятность их выполнения так же одинаковая. Согласно имеющимся весовым коэффициентам вероятности, система решает, какой переход будет работать. И для соответствующего перехода определится время ti - длительность выполнения этого перехода. По окончании работы перехода агент производит все ресурсы, указанные в выходных термах перехода.

Если в системе нет активных агентов, то поведение системы аналогично поведению модели TRDATimed automata в аналогичной ситуации.



2. Система TRDA Tool

2.1 Анализ исходных данных и выбор оптимального решения поставленной задачи

Для построения в TRDA Tool программе моделей типа ресурсно-управляемых сетей временных автоматов необходимо было, во-первых, придумать способ представления входных данных. Ввиду сложности модели, было решено разработать язык, позволяющий в текстовом виде описывать и сохранять в файле структуру модели и начальную разметку сети, а не выполнять ввод исходных данных с помощью графического представления. Стоит так же отметить, что стандартный язык PNML (Petri Net Markup Language) [12] для описания необходимой нам структуры и конфигурации моделей использовать было нельзя, поскольку в нем нет всех необходимых для нас возможностей: вложенность, учет времени, возможность задания мобильного перемещения агентов, т.д.

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

После создания TRDA Tool программы, реализующей ресурсно-управляемые сети автоматов, необходимо было расширить возможности формализма RDA-сети: добавить в модель возможности учета временных характеристик. В процессе анализа было рассмотрены следующие интересные модели, учитывающее время по-разному: модель Мерлина временных сетей Петри, модель Штарке временных сетей Петри, временные автоматы. Именно они и легли в основу расширения автоматной уровня RDA сети.

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

2.2 Методы проектирования

В проектирование включается:

Построение модели данных ключевых элементов внутреннего представления модели RDA сетей

Проектирование классов

Проектирование интерфейса

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

2.3 Обоснование выбора программных и аппаратных средств

Для разработки была выбрана операционная система Windows 7, Windows 8 и среда разработки Microsoft Visual Studio 2008 с программным языком С#. Так как от программы не требуется обладать свойством кроссплатформенности, то для ее реализации был выбран язык С#. Язык C# - объектно-ориентированный, а значит легок в использовании и был основным предметом изучения в Национальном Исследовательском Университете Высшей Школе Экономике на отделении программной инженерии факультета бизнес-информатики.

Для проектирования ER моделей была выбрана программа Oracle SQL Developer Data Modeler 3.0.0., которая обладает всеми требуемыми атрибутами для создания задуманной ER модели.

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

Диаграмма классов TRDA Tool приведена на рис.2

Рисунок 2. Диаграмма классов TRDA Tool

2.4 Проектирование связей ключевых компонент языка описания RDA сетей

Для разработки входного языка описания модели RDA типа, необходимо определить взаимосвязь между элементами внутреннего представления модели ресурсно-управляемых сетей автоматов. Для этого была построена ER-модель (Схема 2) этого представления.

Схема 2. ER модель модели (метамодель) ресурсно-управляемых сетей автоматов



В прямоугольники заключены объекты метамодели. Линиями показаны связи между ними. Обозначения «прямой вход» в прямоугольник и «лапка» означают возможную кратность связей, где прямая линия - это 1, где лапка - многие. К примеру, рассмотрим, все элементы, связанные с элементом Type. Это: port, state, trans, const, VAR. Связь элемента Type с каждым из выше перечисленных - один ко многим. У одного типа объекта может быть множество портов, состояний, переходов из состояния в состояние, констант, переменных.

Для улучшения понимания, ниже приводится таблица соответствий объектов метамодели и элементов формализма ресурсно-управляемых сетей автоматов [3] (таблица 3).

Таблица 3 - Таблица соответствий объектов метамодели и элементов формализма ресурсно-управляемых сетей автоматов

Объект метамодели	Ссылки на описание формализма ресурсно-управляемых сетей автоматов	Комментарии
Place	resource node, элемент множества V (preliminaries)1	Места (вершины) системной сети
arc_in	input arc, consumption relation, элемент множества I (preliminaries)	Пунктирные дуги системной сети
arc_out	output arc, production relation, элемент множества O (preliminaries)	Непрерывные дуги системной сети
Type	Элемент множества? (def.4) Здесь и далее в таблице приведены ссылки на статью и определения из статьи [3].
State	state , элемент множества SA (def.3)
Const	Элемент множества Const (3.2definitions начало)	Возможный идентификатор (их может быть несколько) для обозначения экземпляра объекта соответствующего типа
Port	arc label, элемент множества П (def.1)
Trans	resource transformation expression, элемент transition relation, элемент множества TA (def.3)
term_in	input term (p?e)
term_out	output term (p!e)
Inst	элемент marking M (def.2)	Экземпляр объекта соответствующего типа. Их совокупность составляет маркировку сети
var	Var(def.5)

Разработка языка описания модели типа ресурсно-управляемых сетей временных автоматов

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

model(<название модели>) - определение названия модели

Системная сеть описывается следующим образом:

place(<название места системного слоя>) - определение места (вершины) системной сети

arc_in(<название вершины потребителя>,<название вершины источника>,<название порта>) - определение потребляющей (входной) дуги системной сети с названием соответствующего порта

arc_out(<название вершины производителя>, <название вершины назначения >,

<название порта>) - определение производящей (выходной) дуги системной сети c названием соответствующего порта

Автоматный слой описывается следующим образом:

type(<название типа объекта >)

state(<название состояния типа объекта>)

const(<название объекта в программе, показываемое пользователю>)

var(<название переменной>)

port(<название порта для производства/потребления объектов данного>)

trans (<текущее состояние>, <следующее состояние>,<название перехода>)

constr (<счетчик_1>, [арифметический оператор: + или - ], [счетчик_2], <оператор сравнения>,<натуральное число >)

1. reset(<счетчик>)

2. wait(<нижняя граница ожидания начала работы перехода>,<верхняя граница ожидания начала работы перехода>)

priority(<числовое значение приоритета>)

time(<нижняя граница длительности работы перехода>,<верхняя граница длительности работы перехода>)

trans_chart_name(<название перехода для временной диаграммы>)

term_in (<название порта>, <название объекта>,[состояние объекта]) - потребление

term_out (<название порта>,<название объекта>,[состояние объекта]) - производство

- определение типа объекта:

его название

все возможные состояния данного типа объекта (если это не элементарный тип)

константы - возможные обозначения объектов данного типа в модели

названия всех возможных переменных

названия всех портов для производства/потребления данного типа объектов

список возможных переходов из состояния в состояние для данного типа объекта и название перехода

1. ограничение (охранник) на переходе

1. сброс счетчика после выполнения того или иного перехода

2. время до начала выполнения перехода с того момент, как переход становится активным

Одновременно возможно использовать либо ограничение и сброс (вариант 1), либо время задержки (вариант 2).

Приоритет - весовой коэффициент вероятности, что в объекте сработает именно в этот переход

длительность перехода из состояния в состояние

название перехода на временной диаграмме (задав для разных переходов одно и то же название, можно получит объединенное отображение этих переходов на временной диаграмме для удобства просмотра)

описание потребления/производства для данного перехода с помощью входных/выходных термов

Начальное состояние модели (начальная маркировка) описывается следующим образом:

place(<название места системного слоя>)

inst(<const - обозначение объекта в программе >,<состояние объекта автоматного слоя>) - если объект не элементарный

inst (<const - обозначение объекта>) - если объект элементарный

- начальная разметка (маркировка):

места (вершины) системной сети, и объекты (экземпляры типов объектов), которые в нем находятся и их состояния, если объекты не элементарны

2.6 Описание разработанного языка в нотации Бэкуса-Наура

<Описание модели> ::= model(<название модели>)

<системная сеть>

<автоматный слой>

<начальная разметка>

<системная сеть> ::=

[<определение вершины системного слоя>, … ]

[<определение дуги системного слоя>, … ]

<определение вершины системного слоя> ::= place(<название вершины>)

<определение дуги системного слоя> ::=

<определение входящей дуги> | <определение исходящей дуги>

<определение входящей дуги> ::=

arc_in(<вершина приемник>, <вершина источник>, <название порта>)

<определение исходящей дуги> ::=

arc_out(<вершина источник>, <вершина приемник>, <название порта>)

<автоматный слой> ::= [<определение типа>, … ]

<определение типа> ::= type(<имя типа>)

[<определение элемента типа>, … ]

[<обозначение состояния на графике>, … ]

[<определение перехода>, … ]

<определение элемента типа> ::= <определение состояния> | < определение порта>

| < определение константы> | < определение переменной>

<определение состояния> ::= state(<имя состояния>)

<определение переменной> ::= var(<имя переменной>)

<определение константы> ::= const(<имя константы>)

<определение порта> ::= port(<имя порта>)

<обозначение состояния на графике> ::=

state_chart_name(<имя состояния>, <имя состояния на графике>)

<определение перехода> ::=

trans(<имя исходного состояния>, <имя итогового состояния> [, <название перехода>])

[<атрибут перехода>, … ]

[<определение преобразования ресурсов>, … ]

<атрибут перехода> ::= <параметр задержки>

| <ограничение>, <сброс счетчика>

| <ожидание начала работы перехода>

<ограничение> ::=

constr(<счетчик_1>[,<арифметический оператор: + или - >][,<счетчик_2>],<оператор сравнения>, <натуральное число>)

<сброс счетчика>::=

reset(<счетчик>)

<атрибут перехода> ::= <продолжительность перехода>

| <обозначение перехода на графике>

| <вероятность перехода>

<ожидание начала работы перехода> ::=

wait(<минимальное время ожидания перехода>[, <максимальное время ожидания перехода>])

<продолжительность перехода> ::=

time(<минимальное время длительности работы перехода>[, <максимальное время длительности работы перехода>])

<вероятность перехода> ::=

priority(<приоритет перехода>)

<обозначение перехода на графике> ::=

trans_chart_name(<имя перехода на графике>)

<определение преобразования ресурсов> ::=

<определение потребления ресурсов> | <определение производства ресурсов>

<определение потребления ресурсов> ::=

term_in(<имя порта>, <имя ресурса>[, <состояние потребляемого ресурса>])

<определение производства ресурсов> ::=

term_out(<имя порта>, <имя ресурса>[, <состояние производимого ресурса>])

<имя ресурса> ::= <имя константы> | <имя переменной>

<начальная разметка> ::= place(<имя вершины>)

[<определение объекта>, … ]

<определение объекта> ::= inst(<имя константы>[, <имя состояния>])

2.7 Возможности TRDA Tool

2.7.1 Возможности моделирования

TRDA Tool позволяется выполнять следующие действия с моделями вида TRDA

Загружать модель. Для того, чтобы загрузить модель необходимо воспользоваться функцией Файл - Открыть - выбрать текстовый файл с расширением .rda на TRDA языке.

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

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

Проверять поведенческие свойства. Для просмотра результатов анализа необходимо воспользоваться кнопкой «Результаты анализа». Более детально о возможностях анализа TRDA Tool написано в разделе «Возможности анализа».

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



2.7.2 Возможности анализа

Для целей анализа было необходимо создать следующую функциональность TRDA Tool:

1) добавить возможность выполнения определенного количества моментов времени или определенного количество шагов по задаваемому пользователем числу.

2) разработать способ задания параметров анализа.

3) реализовать анализатор модели. Анализатор включает в себя следующее:

Поведенческие свойства:

Живость

Живость переходов системной сети

Ограниченность

Достижимость

Наличие тупиковой ситуации

Статистический анализ по каждому агенту:

Количество состояний, в которых побывал конкретный агент

Количество состояний, в которых мог бы побывать конкретный агент

Анализ состояний

Среднее время нахождения в состоянии

Общее время нахождения в состоянии

Количество нахождений в состоянии

Анализ переходов

Среднее время нахождения в переходе

Общее время нахождения в переходе

Количество нахождений в переходе

2.7.3 Поведенческие свойства

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

Введем определение хода выполнения модели, обозначив XB.

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

Живость

Свойство живости выполняется в модели, если все переходы, определенные для всех типов, выполнялись хотя бы раз в ходе выполнения модели.

Иначе говоря, свойство живости выполняется, если где

st - начальное состояние агента (описанное в разделе 1.1.)

st' - текущее состояние агента

Живость переходов системной сети

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

Ограниченность

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

Достижимость

Свойство достижимости выполняется в модели, если разметка системы, заданная в параметрах анализа**, достигалась хотя бы раз за ход выполнения модели.

Наличие тупиковой ситуации

Свойство наличие «тупиковой» ситуации выполняется в модели, если за ход выполнения модели система пришла в такое состояние, что ресурсы в системе есть, но ни один переход системной/элементной сети выполниться не может.

Параметры анализа

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

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

*Ограниченность

Синтаксис задачи параметров:

bound(<название вершины системной сети>|*,<тип объекта>|* ,<количество>)

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

общее количество объектов в системе: bound(*,*,<число>)

количество всех объектов в вершине: bound(<вершина>,*,<число>)

количество объектов определенного типа в системе: bound(*,<тип>,<число>)

количество объектов определенного типа в определенной вершине: bound(<вершина>,<тип>,<число>)

Количество проверяемых условий, описанных во входном файле, не ограничено.

**Достижимость

Синтаксис задачи параметров:

marking(<название разметки для поиска>,[like])

place(<название вершины системной сети>)

inst(<экземпляр агента>,<состояние агента>)

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

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

Количество разметок для анализа, описанных во входном файле, не ограничено.

Предусмотрена возможность остановки при контроле Достижимости по достижении заданных разметок. Для этого необходимо поставить галку «Пауза при нахождении» (Рисунок 3)

Рисунок 3. Галка «Пауза при нахождении» на главной форме

2.7.4 Способ установки программы

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

Для установки программы Graphviz 2.28 необходимо скачать ее на локальный диск Вашего компьютера. Программа доступна для скачивания на сайте http://www.graphviz.org/Home.php. После установки программы, требуется перезагрузить операционную систему, для того, чтобы путь к программе dot.exe добавился в пути по умолчанию (path).

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

2.7.5 Соответствие графической визуализации текущего состояния модели ее структурному представлению

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

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

Рисунок 4. Структурный вид текущего состояния модели



Рисунок 5. Визуализация текущего состояния системной сети

Рисунок 6. Визуализация текущего состояния автоматной сети

Таблица 4 - Соотнесения структурного и графического представления текущей конфигурации модели

Структурное представление	Графическое представление	Комментарии
Вершина, внутри которой может находиться раскрывающийся список	Серый кластер внутри с белым овалом. Белый овал характеризует вершину системной сети, к которой присоединяются потребляющие/производящие дуги. Имя кластера совпадает с белым овалом.	«Главная вершина», вершина системной сети
Агенты из раскрывающего списка	Разноцветные овалы внутри кластера	Агенты, ресурсы
Количество агентов в раскрывающемся списке главной вершины	Число в квадратных скобках внутри разноцветного овала кластера	Количество агентов внутри главной вершины
На форме не отображается	Синяя стрелочка и ее подпись. Стрелка выходит из вершины источника и входит в вершину назначения.	Потребляющая дуга + имя порта
На форме не отображается	Черная стрелочка и ее подпись. Стрелка выходит из вершины источника и входит в вершину назначения.	Производящая дуга + имя порта
Вершина системной сети: агент его текущее состояние --> агент его возможное новое состояние	Зеленые стрелки на форме визуализации Автоматной сети	Активные переходы автоматной сети
На форме не отображается	Красные стрелки на форме визуализации Автоматной сети	Выполняющиеся переходы автоматной сети

3. Примеры применения trda tool для моделирования и анализа некоторых классических задач

В данном разделе будут рассмотрены классические задачи на распределенные системы, их TRDA представление и анализ при помощи TRDA Tool.

3.1 Задача об обедающих философах, гуляющих в парке

Постановка задачи

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

Цели моделирования и анализа

На примере данной задачи проведем анализ свойства живости переходов автоматных сетей и живости дуг системной сети.

Решение

Графическое представление задачи



Рисунок 7. Системная сеть

Рисунок 8. Автоматная сеть

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

Входной файл для данной модели можно взять из приложения 2.

Загрузим входной файл в эмулятор - рис. 9

Рисунок 9. Задача об философах, гуляющих в парке загружена



Выполним 500 шагов и нажмем кнопку «Результаты анализа», увидим - Рисунок10

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

Как видно из протокола анализа, не все переходы, как автоматной, так и системной сети сработали.

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

Поэтому загрузим модель еще раз и опять запустим выполнение на 500 шагов, нажмем «Результаты анализа». - Рис.11



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

Как видно на картинке, на этот раз, все переходы элементной сети выполнены. Стоит отменить, что при анализе живости проверяет лишь выполнение перехода для определенного типа в целом, а не для конкретного агента этого типа. Если же мы хотим просмотреть параметры поведения конкретного агента, то следует обратиться к разделу статистического анализа по агентам - Рисунок 12 и 13.



Рисунок 12. Статистический анализ агентов (часть 1)

Рисунок 13. Статистический анализ агентов (часть 2)



Еще раз загрузим модель и запустим ее на 500 шагов, нажмем «Результаты анализа» - Рис. 14

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

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

...