Пример 1

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

Здесь переходы связаны со следующими событиями: — поступление запроса на использование WS, — занятие станции, — освобождение станции, — выход обслуженной заявки; позиция используется для отображения состояния WS: если в имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода ; пока эта заявка не будет обслужена, метки в не будет, следовательно, пришедшие в позицию запросы вынуждены ожидать срабатывания перехода .

Рис. 3. Сеть Петри для примера 1

Пример 2

На рис. 4 представлена сеть Петри, соответствующая организации параллельных вычислений на основе асинхронного message passing interface (MPI) [1].

Рис. 4. Сеть Петри для примера 2

Пример 3

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

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

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

Рис. 5. Сеть Петри для примера 3

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

Список литературы

1. В.Э.Малышкин. Основы параллельных вычислений. -2003 ЦИТ СГГА, http://www.ssga.ru/metodich/paral1/contents.html

Анализ сетей Петри

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

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

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

Безопасность — частный случай ограниченности, а именно это 1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.

Сохраняемость характеризуется постоянством загрузки ресурсов, т.е.

где — число маркеров в -й позиции, — весовой коэффициент.

Достижимость характеризуется возможностью достижения маркировки из состояния сети, характеризуемого маркировкой .

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

В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.

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

Приведем примеры анализа достижимости.

Пример 1

Сеть Петри и граф достижимых разметок представлены на рис. 1.

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

Рис. 1. Сеть Петри и ее граф достижимости для примера 1

Пример 2

Сеть Петри и граф достижимых разметок представлены на рис. 2.

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

Рис. 2. Сеть Петри и ее граф достижимости для примера 2

Пример 3

На рис. 3 представлены сеть Петри и ее граф достижимости из работы [1].

Рис. 3. Сеть Петри и ее граф достижимости для примера 3

Список литературы

1. В.Э.Малышкин. Основы параллельных вычислений. -2003 ЦИТ СГГА, http://www.ssga.ru/metodich/paral1/contents.html

Дата добавления: 2014-01-05