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

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

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



Оглавление

• Введение
• 1. Постановка задачи
• 1.1 Основные понятия и определения
• 1.2 Общее описание разрабатываемого ПП
• 2. Анализ методов и средств решения поставленной задачи
• 2.1 Теоретические основы
• 2.2 Аналитический обзор существующего ПО
• 3. Анализ требований к ПП
• 3.1 Анализ предметной области разработки
• 3.2 Система приоритетов при разработке ПП
• 4. Проектирование ПП
• 4.1 Архитектура ПП
• 4.2 Выбор инструментальных средств разработки
• 4.3 Проектирование структур данных и алгоритмов
• 4.4 Проектирование пользовательского интерфейса
• 5. Реализация ПП
• 6. Тестирование ПП
• 6.1 Обоснование методики тестирования
• 6.2 Результаты тестирования
• 6.3 Пример анализа сети
• Заключение
• Список использованных источников
• Приложение
• Введение

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

Цель работы - разработать программу, способную помочь в обучении студентам, изучающим сети Петри. В ходе работы необходимо решить следующие задачи:

· Реализовать возможность добавления элементов сети (позиций, переходов и дуг), их изменения, удаления и рисования;

· Реализовать возможность моделирования активации перехода, а также моделирования такта системы;

· Реализовать возможность отображения сети Петри в текстовом виде (Petri Net Markup Language (PNML) код);

· Реализовать возможность воссоздания сети Петри по заданному PNML коду;

· Реализовать ведение статистики по моделированию сети.

• 1. Постановка задачи
• 1.1 Основные понятия и определения

Сети Петри - инструмент для математического моделирования и исследования сложных систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы. Эта информация может использоваться для оценки моделируемой системы и выработки предложений по ее усовершенствованию [1].

• 1.2 Общее описание разрабатываемого ПП
• ПП представляет собой Web-приложение для моделирования сетей Петри. Задача приложения - помочь в обучении студентам изучающих, или использующих в обучении сетей Петри. В качестве заказчика выступает кафедра АВТ. вычисление проектирование программный петри
• 2. Анализ методов и средств решения поставленной задачи
• 2.1 Теоретические основы

1 Основные положения в теории сетей Петри

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

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

Условие имеет емкость: условие не выполнено (емкость равна 0), условие выполнено (емкость равна 1), условие выполнено с n-кратным запасом (емкость равна n, где n -- целое положительное число). Условие соответствует таким ситуациям в моделируемой системе, как наличие данного для операции в программе, состояние некоторого регистра в устройстве ЭВМ, наличие деталей на конвейере и т.п. Определенные сочетания условий разрешают реализоваться некоторому событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), т.е. события взаимодействуют с условиями, а условия -- с событиями.

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

В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов и множеством мест. В графическом представлении сетей переходы изображаются "барьерами", а места - кружками (Рисунок 2.1). Условия-места и события-переходы связаны отношением непосредственной зависимости (непосредственной причинно-следственной связи), которое изображается с помощью направленных дуг, ведущих из мест в переходы и из переходов в места. Места, из которых ведут дуги на данный переход, называются его входными местами. Места, на которые ведут дуги из данного перехода, называются его выходными местами. Выполнение условия изображается разметкой, а именно помещение числа n фишек (маркеров) в это место.

Рисунок 2.1 - Сеть Петри

Определение. Сеть Петри -- это набор N =(P, T, I, O, M0), где P -- непустое множество элементов сети, называемое местами, T -- непустое множество элементов сети, называемое переходами, - отношение инцидентности, а и -- две функции, называемые соответственно кратностью дуг и начальной разметкой.

Первая сопоставляет каждой дуге число п > 0 (кратность дуги). Если п > 1, то в графическом представлении сети число n выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга будет также заменяться пучком из п дуг, соединяющих соответствующие элементы сети. Условимся никак не отмечать кратность дуг, равную 1. Вторая функция сопоставляет каждому месту некоторое число (разметка места).

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

Разметка сети N -- это функция M. Если предположить, что все места сети N строго упорядочены каким-либо образом, т.е. Р = (р1,... ,рn), то разметку М сети (в том числе начальную разметку) можно задать как вектор чисел М = (m1, . . ., mn) такой, что для любого i, , mi = M(рi).

На основе отношения инцидентности I и функции кратности дуг O можно ввести функцию инцидентности, которая определяется как

Если места сети упорядочены, то можно каждому переходу t сопоставить два целочисленных вектора 'I(t) и I'(t) длиной n, где n = | Р | :

'I(t) = (b1, . . . ,bn), где bi=I(pi,t),

I'(t) = (b1, . . . ,bn), где bi=I(ti,p),

Переход t может сработать при некоторой разметке М сети N, если , т.е. каждое входное место p перехода t имеет разметку, не меньшую, чем кратность дуги, соединяющей р и t. Это условие можно переписать в векторной форме следующим образом:

М'I(t).

Срабатывание перехода t при разметке M порождает разметку М' последующему правилу:

M'(р)=M(р) - I(р,t) + I(t,р), т.е.

М'=М - 'I(t) + I'(t).

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

2 Природа систем, моделируемых сетями Петри

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

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

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

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

3 Моделирование систем сетями Петри

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

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

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

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

Условиями для рассматриваемой системы являются:

а) сервер ждет;

б) запрос поступил и ждет;

в) сервер обрабатывает запрос;

г) запрос обработан.

Событиями для этой системы являются:

1.Запрос поступил.

2. Сервер начинает обработку запроса.

3. Сервер заканчивает обработку запроса.

4. Результат обработки отправляется.

Для перечисленных событий можно составить таблицу 1 их предусловий и постусловий.

Таблица 1 - Предусловия и постусловия

Событие	Предусловие	Постусловие
1 2 3 4	нет а. б в г	б в г. а нет

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

Пример 2. Сеть Петри, моделирующая систему автомат-продавец.

На рисунке 2.2 предусловие выполняется для события 2.

Рисунок 2.2 - Сеть Петри, моделирующая систему автомат-продавец

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

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

Замечание. Переходы в сети Петри, моделирующей некоторую систему, представляют её примитивные события (длительность которых считается равной 0), и в один момент времени может быть запущен только один разрешённый переход.

Моделирование одновременного (параллельного) возникновения независимых событий системы в сети Петри демонстрируется на рисунке 2.3

Рисунок 2.3 - Сеть Петри, моделирующая систему автомат-продавец

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

Другая ситуация в сети Петри на рисунке 2.4.

Рисунок 2.4 - Взаимоисключающие события

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

Рассмотрим моделирование параллельных систем взаимодействующих процессов.

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

Пример 3. Последовательная программа на абстрактном языке программирования, вычисляющая Y! И произведение всех чётных чисел из отрезка [1,Y] .для произвольного положительного целого Y.

begin

read(Y);

X1:=1;

X2:=1;

while Y>0 do

begin

if mod(Y,2)=0

then begin

X1:=X1*Y;

end;

X2:=X2*Y;

Y:=Y-1;

end;

write(X1);

write(X2);

end

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

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

Приведем блок-схему программы из примера 3 (Рисунок 2.5).

a: read(Y); X1:=1; X2:=1;

b: Y>0

c: mod(Y,2)=0

d: X1:=X1*Y;

e: X2:=X2*Y; Y:=Y-1;

f: write(X1); write(X2);

Рисунок 2.5 - Блок-схема программы

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

Сеть Петри, представляющая блок-схему программы из примера 3 на рисунке 2.6.



Рисунок 2.6 -Сеть Петри блок-схемы

Фишка в сети Петри представляет счетчик команд блок-схемы.

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

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

Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей памяти; - посредством передачи сообщения различных видов.

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

Задача об обедающих мудрецах.

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

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

В этой сети Петри позиция пi, i{1,2,3,4,5}, представляет условие "i-тая палочка свободна". В начальной маркировке каждая из этих позиций имеет фишку. Каждому мудрецу i{1,2,3,4,5} соответствует две позиции: позиция дi - представляющая условие "i-тый мудрец думает"; и позиция еi. - представляющая условие "i-тый мудрец ест".



Рисунок 2.7 - Сеть Петри задачи об обедающих мудрецах

В начальной маркировке каждая позиция дi содержит фишку, а каждая позиция еi пуста.

Каждому мудрецу i{1,2,3,4,5} также соответствует два перехода: переход начi - представляющий событие "начало приёма пищи i-тым мудрецом"; и переход завi - представляющий событие "завершение приёма пищи i-тым мудрецом".

4 Методы анализа моделей на сетях Петри и их основные свойства

Модели на основе сетей Петри позволяют исследовать два вида свойств: определяемых начальной маркировкой и не зависящей от неё. Свойства, относящиеся к первой группе, называются поведенческими, а свойства второй группы - структурными.

К поведенческим относятся:

Достижимость. Под достижимостью понимают, что маркировка Mn достижима от начальной маркировки M0 в результате последовательностей запусков переходов.

Ограниченность. Сеть Петри называют k - ограниченной, если для любой маркировки M0, количество фишек в любой позиции не превышает некоторого конечного числа k.

Безопасность. Сеть Петри называют безопасной, если она 1 - ограниченна.

Активность (живость сети, или, что эквивалентно - живость M0 ).

Обратимость и базовое состояние. Сеть Петри обратима, если для любой маркировки M из R(M0) маркировка M0 достижима от M.

Задача покрываемости. Для данной сети Петри С с начальной маркировкой M и маркировки M' определить, существует ли такая достижимая маркировка , что .

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

Синхронное расстояние. Синхронное расстояние между переходами в сети определяется разницей числа запусков двух переходов при достижении одной маркировки

Совершенность (адекватность). Существует два основных определения адекватности:

Ограниченная. Два перехода t1 и t2 связаны отношением ограниченной совершенности (или B - совершенности), если максимально возможное число запусков одного перехода при запуске другого ограничено.

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

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

Структурными свойствами сетей Петри являются следующие:

Структурная активность. Сеть Петри называется структурно активной, если для нее существует некоторая активная начальная разметка.

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

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

Консервативность. Сеть Петри называется консервативной, если для каждой (некоторой) позиции p существует положительное число y(p) , такое что для любой маркировки взвешенная сумма фишек .

Повторяемость. Сеть Петри называется повторяемой, если существует маркировка M0 и последовательность запуска переходов s из M0 , такие что любой (некоторый) переход бесконечно часто повторяется в s.

Консистентность. Сеть Петри называется консистентной, если существует маркировка M0 и последовательность запуска переходов s из M0 обратно в M0 , такие что любой (некоторый) переход хотя бы один раз срабатывает в s.

Структурное В - совершенство. Сеть Петри называется структурно В - совершенной, если она является В - совершенной для любой начальной маркировки.

Методы анализа сетей Петри можно разбить на следующие три группы:1) методы на основе дерева покрываемости (дерева достижимости); 2) алгебраические методы на основе матричных уравнений; 3) методы преобразования и декомпозиции (используется как средство упрощения для использования первых двух).

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

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

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

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

За один раз, может сработать один переход (только один переход за раз - интерливинговая семантика), несколько переходов (шаговая семантика), максимальное количество переходов - это зависит от выбора процесса срабатывания. В сущности, срабатыванием переходов должен управлять процесс, который не содержится в самой сети. Именно этот процесс определяет, - какие и сколько переходов должны сработать. В зависимости от цели этот процесс может управлять симуляцией, верификацией или, например, слиянием сетей. Назовём этот процесс - программой срабатывания. Срабатывание переходов считается мгновенной и неделимой операцией. Если сопоставить каждому переходу уникальное имя, то событию, представленному, как срабатывание множества переходов, можно присвоить имя - как сумму имён всех переходов из множества. Тогда последовательность срабатываний переходов можно записать, как последовательность имён событий. А для отображения состояния сети, достаточно добавить первоначальную маркировку сети.

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

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

представляет все достижимые маркировки сети Петри, а также - все возможные последовательности запусков её переходов.

Пример 1. Частичное дерево достижимости маркированной сети Петри. Сеть Петри имеет вид:

Рисунок 2.8 - Сеть Петри

Частичное дерево достижимости для трёх шагов построения имеет вид:

Рисунок 2.9 - Частичное дерево достижимости

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

--а = ; + а = ; а < ; .

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

1. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана та же маркировка, [x]=[y], то вершина х становится дублирующей.

2. Если для маркировки [х] ни один из переходов не разрешен, го

x становится терминальной.

3. В противном случае, для всякого перехода tT, разрешенного в [х], создаётся новая вершина z дерева достижимости. Маркировка [z], связанная с этой вершиной, определяется для каждой позиции pP следующим образом:

3.1. Если

[х](p)=, то [z](p)=.



3.2. Если на пути от корневой вершины к x существует вершина y с [y]<' (где ' - маркировка, непосредственно достижимая из [х] посредством запуска перехода t) и

[y](p)<'(p), то [z](p)=.

(В этом случае последовательность запусков переходов, ведущая из маркировки [y] в маркировку ', может неограниченно повторяться и неограниченно увеличивать значение маркировки в позиции p.) В противном случае

[z](p)='(p).

4. Строится дуга с пометкой t, направленная от вершины x к вершине z. Вершина х становится внутренней, а вершина z - граничной.

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

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

Пример 2. Конечное дерево достижимости сети Петри.

Сеть Петри:

Рисунок 2.10 - Сеть Петри

Конечное дерево достижимости:

Рисунок 2.11 - Конечное дерево достижимости

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

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

Доказательство. Пусть x0 корневая вершина. Поскольку имеется только конечное число непосредственно следующих за x0 вершин, но общее число вершин в дереве бесконечно, по крайней мере, одна из непосредственно следующих за x0 вершин должна быть корнем бесконечного поддерева. Выберем вершину x1 непосредственно следующую за x0 и являющуюся корнем бесконечного поддерева. Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве такой вершины x2. Если продолжать этот процесс бесконечно, то получим бесконечный путь в дереве - x0,x1,x2,…,xn,… .

Лемма 2. Всякая бесконечная последовательность неотрицательных целых содержит бесконечную неубывающую последовательность.

Доказательство. Возможны два случая:

1. Если какой-либо элемент последовательности встречается бесконечно часто, то пусть x0 является таким элементом. Тогда бесконечная подпоследовательность x0,x0,…,x0,… является бесконечной неубывающей подпоследовательностью.

2. Если никакой элемент не встречается бесконечно часто, тогда каждый элемент встречается только конечное число раз. Пусть x0 -- произвольный элемент последовательности. Существует самое большее x0 целых, неотрицательных и меньших, чем x0 (0,..., x0-1), причем каждый из них присутствует в последовательности только конечное число раз. Следовательно, продвигаясь достаточно долго по последовательности, мы должны встретить элемент x1, x1 x0. Аналогично должен существовать в последовательности x2, x2 x1, и т. д. Это определяет бесконечную неубывающую последовательность x0,x1,x2,…,xn,… .

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

Лемма 3. Всякая бесконечная последовательность n-векторов над расширенными символом неотрицательными целыми содержит бесконечную неубывающую подпоследовательность.

Доказательство. Доказываем индукцией по n, где n -- размерность векторного пространства.

1. Базовый случай (n=1). Если в последовательности имеется бесконечное число векторов вида <>, то они образуют бесконечную неубывающую последовательность (так как справедливо ). В противном случае бесконечная последовательность, образованная удалением конечного числа экземпляров <>, имеет по лемме 2 бесконечную неубывающую подпоследовательность.

2. Индуктивное предположение. (Допустим, что лемма верна для n докажем её справедливость для n+1.) Рассмотрим первую координату. Если существует бесконечно много векторов, имеющих. в качестве первой координаты , тогда выберем эту бесконечную подпоследовательность, которая не убывает (постоянна) по первой координате. Если только конечное число векторов имеют в качестве первой координаты, то рассмотрим бесконечную последовательность целых, являющихся значениями первых координат. По лемме 2 эта последовательность имеет бесконечную неубывающую подпоследовательность. Она определяет бесконечную Последовательность векторов, которые не убывают по своей первой координате.

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

Докажем следующую теорему.

Теорема 1. Дерево достижимости сети Петри конечно.

Доказательство. Докажем методом от противного. Допустим, что дерево достижимости бесконечно. Тогда по лемме 1 (и так как число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов m) в нём имеется бесконечный путь x0,x1,x2,… , исходящий из корня x0. Тогда [x0], [x1], [x2],… -- бесконечная последовательность n-векторов. над Nat{}, а по лемме 4.3 она имеет бесконечную неубывающую подпоследовательность [xk0][xk1][xk2]….. . Но по построению дерева достижимости

[xi][xj]



(для ij), поскольку тогда одна из вершин была бы дублирующей и не имела следующих за собой вершин. Следовательно, это бесконечная строго возрастающая последовательность [xk0]<[xk1]<[xk2]….. . Но по построению, так как [xi]<[xj] нам следовало бы заменить по крайней мере одну компоненту [xj], не являющуюся , на в [xj]. Таким образом, [xk1] имеет по крайней мере одну компоненту, являющуюся , [xk2] имеет по крайней мере две -компоненты, а [xkn] имеет по крайней мере n -компонент. Поскольку маркировки n-мерные, [xkn] имеет во всех компонентах . Но тогда у [xkn+1] не может быть больше [xkn]. Пришли к противоречию, что доказывает теорему.

Анализ свойств сетей Петри на основе дерева достижимости

Анализ безопасности и ограниченности.

Утверждение 1. Сеть Петри ограниченна тогда и только тогда, когда символ отсутствует в её дереве достижимости.

Краткое обоснование. Присутствие символа в дереве достижимости ([х](p)= для некоторой вершины x и позиции p) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p, большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p, а следовательно, и самой сети Петри.

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

Анализ сохранения.

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

Анализ покрываемости.

Задача покрываемости требуется для заданной маркировки ' определить, достижима ли маркировка "'. Такая задача решается путём простого перебора вершин дерева достижимости. При этом ищется такая вершина х, что [x]'. Если такой вершины не существует, то маркировка ' не является покрываемой. Если она найдена, то [x] определяет покрывающую маркировку для ' Если компонента маркировки [x], соответствующая некоторой позиции p совпадает с , то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p. Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с '(p).

Анализ живости.

Утверждение 2. Переход t сети Петри является потенциально живым, тогда и только тогда, когда он метит некоторую дугу в дереве достижимости этой сети.

Доказательство очевидно.

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

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

Рисунок 2.14 - Программа QPNet

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

• 3. Анализ требований к ПП
• 3.1 Анализ предметной области разработки

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

• 3.2 Система приоритетов при разработке ПП
• Технические требования:

· Время реакции системы - не более 1с;

· Одновременно работающих пользователей - до 10.

• 4. Проектирование ПП
• 4.1 Архитектура ПП

В качестве архитектуры было выбрано локальное приложение с возможностью доступа из сети. В качестве базового ПО выбрана Windows 7 и браузер Google Chrome

• 4.2 Выбор инструментальных средств разработки
• Для разработки Web-приложения используются HTML, CSS, Javascript и библиотека JQuery. В качестве средства отладки используется Google Chrome.
• HTML (от англ. HyperText Markup Language -- "язык гипертекстовой разметки") -- стандартизированный язык разметки документов в Интернете. Большинство веб-страниц содержат описание разметки на языке HTML (или XHTML). Язык HTML интерпретируется браузерами; полученный в результате интерпретации форматированный текст отображается на экране монитора компьютера или мобильного устройства [2].
• CSS (Cascading Style Sheets -- каскадные таблицы стилей) -- формальный язык описания внешнего вида документа, написанного с использованием языка разметки.
• Преимущественно используется как средство описания, оформления внешнего вида веб-страниц, написанных с помощью языков разметки HTML и XHTML, но может также применяться к любым XML-документам [3].
• JavaScript -- прототипно-ориентированный сценарный язык программирования.
• JavaScript обычно используется как встраиваемый язык для программного доступа к объектам приложений. Наиболее широкое применение находит в браузерах как язык сценариев для придания интерактивности веб-страницам.
• Основные архитектурные черты: динамическая типизация, слабая типизация, автоматическое управление памятью, прототипное программирование, функции как объекты первого класса [4].
• jQuery -- библиотека JavaScript, фокусирующаяся на взаимодействии JavaScript и HTML. Библиотека jQuery помогает легко получать доступ к любому элементу DOM (Document Object Model - объектная модель документа), обращаться к атрибутам и содержимому элементов DOM, манипулировать ими. Также библиотека jQuery предоставляет удобный интерфейс прикладного программирования для работы с AJAX (Asynchronous Javascript and XML -- асинхронный JavaScript и XML) [5].
• 4.3 Проектирование структур данных и алгоритмов
• В проекте реализована собственная иерархия классов. На рисунке 4.1 изображена диаграмма классов.

Рисунок 4.1 - Диаграмма классов

Net - сеть Петри. Состоит из массива позиций (Places) и массива переходов (Transitions).

Place - позиция. Состоит из следующих полей:

· ID - название позиции;

· coordX, coordY - координаты X и Y;

· capacity - ёмкость позиции (максимальное количество меток);

· tokens - текущее количество меток;

· itokens - количество меток, которые ещё не прибыли в позицию из-за задержки перехода (i-метки);

· total - общее количество меток, которые прибыли в позицию;

· idletime - общее количество тактов, за которые позиция была пустая;

· edges - массив дуг, в которых данная позиция - входящая;

· delayvector - массив задержек.

Delay - задержка. Содержит пару <величина задержки, количество меток>, которая определяет сколько меток и через какое время прибудет в позицию.

Transition - переход. Состоит из следующих полей:

· ID - название перехода;

· coordX, coordY - координаты X и Y;

· total - общее число активаций;

· idletime - число тактов без активации;

· active - true если переход активен, false - иначе;

· delay - задержка в переходе. Определяет через сколько тактов метки прибудут в выходящие позиции;

· edges - массив дуг, которые указывают на выходящие позиции.

Edge - дуга. ID - название элемента, на который указывает дуга. Multiplicity - кратность дуги.



• 4.4 Проектирование пользовательского интерфейса
• На рисунке 4.2 общий вид программы. В качестве элемента рисования используется объект Canvas. Для ввода данных используются кнопки и поля ввода. Имеется 4 радиокнопки, определяющие основные режимы работы с программой. Имеется меню настроек (Рисунок 4.3), многострочное поле для ввода и вывода PNML-кода (Рисунок 4.4), и окно статистики (Рисунок 4.5). Моделирование осуществляется тремя кнопками запуска симуляции, шага симуляции и остановки симуляции.

Рисунок 4.2 - Вид программы

Рисунок 4.3 - Меню настроек

Рисунок 4.4 - Многострочное поле для ввода и вывода PNML-кода

Рисунок 4.5 - Окно статистики



• 5. Реализация ПП

Особенности реализации системы

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

$("#b1").click(function(){ … });

Где #b1 - ID кнопки.

Или на движение мыши по холсту.

$("#draw").mousemove(function(e){ … });

Где #draw - ID холста. И т.п.

На рисунке 5.1 блок-схема программы.

Рисунок 5.1 - Блок-схема программы

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

Рисунок 5.2 - Функция проверки активности перехода

Рисунок 5.3 - Блок-схема функции проверки активности перехода

Реализация функции симуляции такта на рисунке 5.3

Рисунок 5.3 - Функция симуляции такта

Рисунок 5.4 - Блок-схема функции симуляции такта

• 6. Тестирование ПП
• 6.1 Обоснование методики тестирования

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

Тесты должны быть сформированы таким образом, чтобы при их выполнении каждая строка программы была выполнена хотя бы один раз. Также проверена работа с разными браузерами (Google Chrome, Mozilla Firefox, Opera, Internet Explorer 10).

• 6.2 Результаты тестирования
• В ходе тестирования было выявлено, что функции ПП соответствуют заявленному перечню функций. Время выполнения разных функций напрямую зависит от сети и её размера, но в целом даже при большом количестве элементов задержка не была заметна.
• 6.3 Пример анализа сети
• На рисунке 6.1 модель производства изделия из двух компонентов.

Рисунок 6.1 - Модель производства изделия из двух компонентов

Пары элементов p0-t0 и p1-t1 выступают в качестве производства первого и второго компонента соответственно. Переход t2 выступает в качестве сборщика. Пара t3-p5 выступает в качестве отправления партии из 10 изделий. У позиции p4 ёмкость - 11, у всех остальных позиций ёмкость - 2. Дуга p4-t3 обладает кратностью 10. Задержки у всех переходов равны нулю.

Результат на рисунке 6.2 после моделирования 100 тактов. Статистика на рисунке 6.3.

Рисунок 6.2 - Вид сети после моделирования 100 тактов

Рисунок 6.3 - Статистика моделирования сети

Как видно переходы t0 и t1 генерировали по одному компоненту каждый такт. Переход t2 осуществлял сборку изделия каждый такт кроме самого первого. Переход t3 отправлял партию изделий каждый десятый такт.

Теперь установим задержку переходов t0 и t1 равную единице и промоделируем 100 тактов сети ёще раз. Результаты на рисунках 6.4 и 6.5.

Рисунок 6.4 - Вид изменённой сети после моделирования 100 тактов

Рисунок 6.5 - Статистика моделирования сети

Из-за задержки переходы t0 и t1 генерировали метку каждый второй такт. Из-за этого переход t2 простаивал половину времени, и партия отправлялась только раз в двадцать тактов.



• Заключение
• Программный продукт соответствует всем заявленным требованиям, требует минимальных ресурсов системы, является надёжным и удобным в использовании, а также мультиплатформенным. Программный продукт готов к внедрению.

• Список использованных источников
• 1. Введение в сети Петри [Электронный ресурс] // Studfiles: сайт. - Режим доступа: http://www.studfiles.ru/preview/2927670/
• 2. HTML [Электронный ресурс] // Wikipedia: сайт. - Режим доступа: https://ru.wikipedia.org/wiki/HTML
• 3. CSS [Электронный ресурс] // Wikipedia: сайт. - Режим доступа: https://ru.wikipedia.org/wiki/CSS
• 4. JavaScript [Электронный ресурс] // Wikipedia: сайт. - Режим доступа: https://ru.wikipedia.org/wiki/JavaScript
• 5. jQuery [Электронный ресурс] // Wikipedia: сайт. - Режим доступа: https://ru.wikipedia.org/wiki/JQuery
• Приложение

(обязательное)

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

Текущие функции программы:

1. Добавление элементов

2. Выделение и перетаскивание элементов.

3. Изменение параметров элемента.

Нужно выделить элемент, изменить его параметр в строке в поле ввода и затем кликнуть в любое место экрана, либо нажать Enter.

4. Удаление элемента.

Для удаления нужно выделить элемент нажать Delete или же нажать кнопку "Удалить элемент".

5. Для удаления всей сети нажмите "Очистить".

6. Активирование перехода.

Нужно выделить переход, и если переход - активный, то можно будет нажать кнопку "Активировать переход"" В противном случае эта кнопка будет недоступна.

7. Симуляция шага (такта).

8. Симуляция шагов через определённый временной интервал.

Для этого нужно установить время между тактами (1000 мс по умолчанию) и количество шагов (если поле пусто - то бесконечное количество), а затем нажать кнопку

Для остановки нажать

Кнопку

9. Генерация PNML-кода.

Для этого нужно нажать кнопку "Настройки PNML-кода", а затем "Сгенерировать PNML-код сети"

10. Формирование сети из PNML-кода.

Добавьте корректный PNML-код в поле ввода и затем нажмите "Загрузить сеть из PNML-кода".

11. Просмотр статистики

Статистика по позициям:

· Название позиции

· Текущее количество меток в позиции

· Максимальное количество меток в позиции

· Количество меток, которые пришли в позицию

· Загруженность = количество_тактов_с_непустой_позицией/количество_тактов

Статистика по переходам:

· Название перехода

· Количество активаций

· Загруженность = количество_активаций/количество_тактов

Размещено на Allbest.ru