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

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

4.3.1. События и условия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Событие	Предусловия	Постусловия
	нет а, б в г	б в г, а нет

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

Рисунок 4.4.

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

4.3.2. Одновременность и конфликт

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

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

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

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

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

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

4.3.3.1. Моделирование последовательных процессов.

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

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

begin

read(Y);

X1:=1;

X2:=1;

while Y>0 do

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