Теория вычислительных процессов Сети Петри для моделирования Преподаватель: Веретельникова Евгения Леонидовна 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 Одновременность и конфликт Другая важная особенность сетей Петри – это их асинхронная природа. В сети Петри отсутствует измерение времени или течение времени. Это отражает философский подход к понятию времени, утверждающий, что одно из важнейших свойств времени, с логической точки зрения, - это определение частичного упорядочения событий. В реальной жизни различные события укладываются в различные интервалы времени, и это отражено в модели сети Петри независимо от времени управления последова- тельностью событий. структура сети Петри такова. что содержит в себе всю необходимую информацию для определения возможных последовательностей событий. Т.е. событие «завершение выполнения задания» должно следовать за событием «начало выполнения задания», но нет и не нужно информации. связанной с количеством времени, необходимым для выполнения задания.