Теория вычислительных процессов Сети Петри для моделирования Преподаватель: Веретельникова Евгения Леонидовна 1. - презентация

1 Теория вычислительных процессов Сети Петри для моделирования Преподаватель: Веретельникова Евгения Леонидовна 1

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

3 3 События и условия Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возни- кновением событий управляет состояние системы. Состоя- ние системы может быть описано множеством условий. Условие – есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь». Так как события являются действиями, то они могут про- исходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий – постусловий.

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

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

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

7 7 События и условия Сеть Петри для простого автомата-продавца

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

9 9 События и условия Эта система будет иметь следующие условия: а) заказ прибыл и ждет обработки автоматом M1; б)заказ обработан автоматом M1 и ждет обработки либо автоматом М2, либо М3; в) заказ выполнен; г) автомат М1 незанят; д) автомат М2 незанят; е) автомат М3 незанят; ж) оператор F1 незанят; з) оператор F2 незанят; и) автомат M1 находится под воздействием оператора F1, к) автомат М1 находится под воздействием оператора F2; л) автомат М2 находится под воздействием оператора F1; м) автомат М3 находится под воздействием оператора F2.

10 10 События и условия При этом могут происходить следующие события: 1. Поступление заказа. 2. Оператор F1 начинает выполнение заказа на автомате М1. 3. Оператор F1 закончил выполнение заказа на автомате M1. 4. Оператор F2 начинает выполнение заказа на автомате M1. 5. Оператор F2 закончил выполнение заказа на автомате M1. 6. Оператор F1 начинает выполнение заказа на М2. 7. Оператор F1 закончил выполнение заказа на М2. 8. Оператор F2 начинает выполнение заказа на М3. 9. Оператор F2 закончил выполнение заказа на М Заказ посылается на доставку.

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

12 12 События и условия Сеть Петри для сложного автомата-продавца

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

14 14 События и условия Моделирование простой вычислительной системы Задание ждет Начало выполнения задания Завершение выполнения задания Задание ждет вывода Задание выводится Задание помещается во входную очередь Процессор свободен Задание обрабатывается

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

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

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

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

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

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

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

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

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

24 24 Одновременность и конфликт Недетерминированность и неодновременность запусков переходов в моделировании параллельной системы показы- ваются двумя способами. Один из них представлен ниже: В этой ситуации два разрешенных перехода в любом слу- чае не влияют друг на друга, и в число возможных последова- тельностей событий входят последовательности, в которых первым запускается t j или t k Это называется одновременность (2 перехода могут запускаться в любом порядке)

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

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