лабы / Сети Петри / Документация / lection203

СЕТИ ПЕТРИ ДЛЯ МОДЕЛИРОВАНИЯ

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

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

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

Простое представление системы сетью Петри основано на двух основополагающих понятиях:

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

«истина», либо значение «ложь».

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

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

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

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

Сеть Петри на рис. 3.1 иллюстрирует модель приведенного выше автомата-продавца. Мы указали каждому переходу и позиции соответствующие событие и условие.

Можно моделировать и более сложную систему. Система автомат-продавец состоит из трех различных автоматов M1 , M2 и М3 и двух операторов F1, и F2. Оператор F1 воздействует на автоматы М1 и М2, а оператор F2 — на M1 и М3. Заказы требуют двух стадий обработки. Сначала они должны быть обработаны автоматом M1, затем либо автоматом М2, либо М3. Эта более сложная система будет иметь следующие условия:

а) заказ прибыл и ждет обработки автоматом M1;

б) заказ обработан автоматом M1 и ждет обработки либо автоматом M2, либо М3;

Рис. 3.1. Сеть Петри для простого автомата-продавца.

Рис. 3.3. Моделирование простой вычислительной системы.

Пред- и постусловия каждого события:

События	Предусловия	Постусловия
1	нет	а
2	а, ж, г	и
3	и	ж, г, б
4	а, з, г	к
5	к	б, 3, Г
6	б, ж, д	л
7	л	в, ж, д
8	б, е, з	м
9	м	в, е, з
10	в	нет

Сеть Петри этой системы показана на рис. 3.2.

Аналогичный пример можно привести для вычислительной системы, которая обрабатывает задания, поступающие с устройства ввода, и выводит результаты на устройство вывода. Задания поступают на устройство ввода. Когда процессор свободен и в устройстве ввода есть задание, процессор начинает обработку задания. Когда задание выполнено, оно посылается в устройство вывода; процессор же либо продолжает обрабатывать другое задание, если оно имеется, либо ждет прихода задания, если устройство ввода еще не получило такового. Эта система может быть промоделирована сетью Петри, показанной на рис. 3.3.

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

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

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

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

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

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

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

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

Рис. 3.4. Моделирование непримитивного события.

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

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

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

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

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

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

Рис. 3.5. Представление непримитивного события прямоугольником.

Петри и другие предложили представлять непримитивные события в сети Петри в виде прямоугольника [244], как показано на рис. 3.5, а примитивные события — планками, как мы делали это раньше. Это упростит некоторые сети Петри, например, такую, как на рис. 3.6, которая эквивалентна сети Петри, изображенной на рис. 3.3. Но так как в принципе предложенное понятие выражено в терминах более примитивных конструкций, мы не будем использовать обозначение в виде прямоугольника. Прямоугольник может иметь существенное значение при моделировании сложных систем на нескольких иерархических уровнях, так как он позволяет выделить в отдельный элемент сети целые подсети. Это в некотором смысле подобно понятиям подпрограммы или макроса в языках программирования.

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

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

Рис. 3.6. Моделирование вычислительной системы с использованием неприми-тивиого перехода.

Рис. 3.7. Одновременность. Эти два перехода могут быть запущены в любом порядке.

Рис. 3.8. Конфликт. Переходы tj и tk находятся в конфликте, т. е. запуск одного из них удаляет фишку из pi и тем самым запрещает другой.

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

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

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

3.3. Аппаратное обеспечение ЭВМ

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

3.3.1. Конечные автоматы

На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (Q, Σ, ∆, δ, Г), где

Q — конечное множество состояний { q 1, q2, ..., qk}; Σ — конечный входной алфавит; ∆— конечный выходной алфавит;

δ : Q × Σ → Q — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние; Г : Q × Σ → ∆— функция выхода, отображающая текущее состояние и текущий вход в выходной символ.

Автоматы часто представляют в виде графов переходов, как, например, на рис. 3.9. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния qi в qj, помеченная a/b, означает, что, находясь в состоянии qi, автомат при входе а перейдет в состояние qj, выдавая при этом символ b. Формально следовало бы записать δ (qi, a) = qj и Г (qi, а) = b.

Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.

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

данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии q1. Символ сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

Рис. 3.9. Граф переходов для конечного		Рис. 3.10. Конечный автомат для определения
автомата, вычисляющего дополнение до двух		четности входного двоичного числа.
двоичного числа.

Аналогичный автомат показан на рис. 3.10. При тех же самых входах этот автомат вычисляет четность входного числа. Он начинает работу в состоянии q1. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для символа сброса будет 0 в случае нечетного числа и 1 — в случае четного числа.

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

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

Рис. 3.11. Общий подход к моделированию связи между сетью Петри и внешним миром.

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

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

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

Рис. 3.12. Альтернативный подход представления связи между сетью Петри и внешним миром, где вместо позиций используются переходы.

Рис. 3.13. Сеть Петри, эквивалентная автомату на рис. 3.9.

Для конечного автомата (Q, Σ, ∆, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом:

P = Q Σ ∆,

T = {tq,σ | q Q и σ Σ}, I (tq,σ) = {q, σ},

O(tq,σ) = {δ(q, σ), Г(q, σ)}.

Эта сеть Петри является моделью конечного автомата.

На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 — сеть Петри, соответствующая автомату с рис. 3.10.

При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Прежде всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 позиций. Это верно. Однако мы показали, что сети Петри могут представлять любую систему, представимую автоматом, и это свидетельствует о больших возможностях сетей Петри.

Кроме того, следует отметить, что модель сети Петри имеет определенное преимущество при композиции автоматов. Например,

Рис. 3.14. Сеть Петри, эквивалентная автомату на рис. 3.10.

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

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

Такая композиция является автоматом с составными состояниями, компоненты которых — это состояния обоих подавтоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — составная сеть Петри.

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

3.3.2. ЭВМ с конвейерной обработкой

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

На протяжении ряда лет было предпринято много попыток увеличения производительности вычислительных систем путем параллельного выполнения нескольких функций. Примером такого подхода к построению высокопроизводительной ЭВМ является использование конвейерной обработки [52]. Этот метод обработки подобен функционированию сборочного конвейера и особенно удобен для работы с векторами и массивами. Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция k завершается, она передает свой результат операции (k + 1) и ожидает от операции (k — 1) нового задания. Если каждая операция занимает t единиц времени и всего существует n операций, то завершение обработки одного операнда потребует nt единиц времени. Однако, если на конвейерную обработку продолжают поступать новые операнды, результаты могут выдаваться со скоростью один каждые t единиц времени.

Рис. 3.16. Составная сеть Петри, являющаяся последовательной композицией сетей Петри на рис. 3.13, 3.14.

Рис. 3.17. Параллельная композиция сетей Петри с рис. 3.13, 3.14. Необходимо обеспечивать дублирование входов для обеих компонент с помощью специальной подсети.

В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают:

1.Выделить экспоненты обоих чисел.

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

3.Сдвинуть точку в числе с меньшей экспонентой для их уравнения.

4.Сложить дроби.

5.Нормализовать, результат.

6.Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата.

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

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