close

Вход

Забыли?

вход по аккаунту

?

ТВП_лекция_8__2003

код для вставкиСкачать
Теория вычислительных
процессов
Сети Петри
для моделирования
Преподаватель: Веретельникова
Евгения Леонидовна
1
Введение
Сети Петри были разработаны и используются в
основном для моделирования. С их помощью могут
быть промоделированы многие системы, в особенности системы с независимыми компонентами,
например аппаратное и программное обеспечение
ЭВМ, физические системы, социальные и др. Сети
Петри применяются дл моделирования возникновения
различных событий в системе. В частности, сети Петри
могут моделировать поток информации или другие
ресурсы системы.
Рассмотрим некоторые примеры систем, моделируемых при помощи сетей Петри.
2
События и условия
Простое представление системы сетью Петри основано на
двух основополагающих понятиях: событиях и условиях.
События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий.
Условие – есть предикат или логическое описание
состояния системы. Условие может принимать либо
значение «истина», либо значение «ложь».
Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо
выполнение соответствующих условий. Эти условия
называются предусловиями события. Возникновение
события может вызвать нарушение предусловий и может
привести к выполнению других условий – постусловий.
3
События и условия
В качестве примера рассмотрим задачу моделирования
простого автомата-продавца. Автомат-продавец находится в
состоянии ожидания до тех пор, пока не появится заказ,
который он выполняет и посылает на доставку.
Условиями для такой системы являются:
а) автомат-продавец ждет;
б) заказ прибыл и ждет;
в) автомат-продавец выполняет заказ;
г) заказ выполнен.
Событиями будут:
1. Заказ поступил.
2. Автомат-продавец начинает выполнение заказа.
3. Автомат-продавец заканчивает выполнение заказа.
4. Заказ посылается на доставку.
4
События и условия
Предусловия события 2 (автомат-продавец начинает
выполнение заказа) очевидны: (а) автомат-продавец ждет;
(б) заказ прибыл и ждет.
Постусловие для события 2: (в) автомат-продавец выполняет
заказ. Аналогично мы можем определить предусловия и
постусловия для других событий и составить следующую
таблицу событий и их пред- и постусловий:
События
1
2
3
4
Предусловия
нет
а, б
в
г
Постусловия
б
в
г, а
нет
5
События и условия
Такое представление системы легко моделировать сетью
Петри. В сети Петри условия моделируются позициями,
события – переходами. При этом входы перехода являются
предусловиями соответствующего события; выходы –
постусловиями. Возникновение события равносильно
запуску соответствующего перехода. Выполнение условия
представляется фишкой в позиции, соответствующей этому
условию. Запуск перехода удаляет разрешающие фишки,
представляющие выполнение предусловий и образует новые
фишки, которые представляют выполнение постусловий.
Сеть Петри следующем слайде иллюстрирует модель
этого автомата-продавца. Мы указали каждому переходу и
позиции соответствующие событие и условие.
6
События и условия
Сеть Петри для простого автомата-продавца
7
События и условия
Можно моделировать и более сложную систему.
Система автомат-продавец состоит из трех различных
автоматов M1 , М2 и M3 и двух операторов F1 и F2.
Оператор F1 воздействует на автоматы M1 и М2,
а оператор F2 — на M1 и М3.
Заказы требуют двух стадий обработки. Сначала они
должны быть обработаны автоматом М1, затем либо
автоматом М2, либо М3.
8
События и условия
Эта система будет иметь следующие условия:
а) заказ прибыл и ждет обработки автоматом M1;
б)заказ обработан автоматом M1 и ждет обработки либо
автоматом М2, либо М3;
в) заказ выполнен;
г) автомат М1 незанят;
д) автомат М2 незанят;
е) автомат М3 незанят;
ж) оператор F1 незанят;
з) оператор F2 незанят;
и) автомат M1 находится под воздействием оператора F1,
к) автомат М1 находится под воздействием оператора F2;
л) автомат М2 находится под воздействием оператора F1;
м) автомат М3 находится под воздействием оператора F2.
9
События и условия
При этом могут происходить следующие события:
1. Поступление заказа.
2. Оператор F1 начинает выполнение заказа на автомате М1.
3. Оператор F1 закончил выполнение заказа на автомате M1.
4. Оператор F2 начинает выполнение заказа на автомате M1.
5. Оператор F2 закончил выполнение заказа на автомате M1.
6. Оператор F1 начинает выполнение заказа на М2.
7. Оператор F1 закончил выполнение заказа на М2.
8. Оператор F2 начинает выполнение заказа на М3.
9. Оператор F2 закончил выполнение заказа на М3.
10. Заказ посылается на доставку.
10
События и условия
Пред- и постусловия каждого события:
События
1
2
3
4
5
6
7
8
9
10
Предусловия
нет
а, ж, г
и
а, з. г
к
б, ж, д
л
б, е, з
м
в
Постусловия
а
и
ж, г, б
к
з, г, б
л
в, ж, д
м
в, е, з
нет
11
События и условия
Сеть Петри для сложного автомата-продавца
12
События и условия
Аналогичный пример можно привести для простой
вычислительной системы, которая обрабатывает
задания, поступающие с устройства ввода, и выводит
результаты на устройство вывода. Задания поступают на
устройство ввода. Когда процессор свободен и в
устройстве ввода есть задание, процессор начинает
обработку задания. Когда задание выполнено, оно
посылается в устройство вывода; процессор либо
продолжает выполнять другое задание, если оно
имеется, либо ждет прихода задания, если устройство
ввода еще не получило такового.
Модель такой системы в виде сети Петри показана
на следующем слайде.
13
События и условия
Задание помещается
во входную очередь
Задание
ждет
Начало
выполнения
задания
Задание обрабатывается
Завершение
выполнения
задания
Задание
ждет
вывода
Задание
выводится
Процессор
свободен
Моделирование простой вычислительной системы
14
Одновременность и конфликт
Рассмотренные примеры иллюстрируют некоторые
особенности сетей Петри и систем, моделируемых с их
помощью. Одной из особенностей является
свойственный сетям и их моделям параллелизм или
одновременность. В модели сети Петри два
разрешенных и взаимодействующих события могут
происходить независимо друг от друга.
Синхронизировать события, пока это не требуется
моделируемой системе, нет нужды. Но, когда
синхронизация необходима, моделировать ее легко.
Таким образом, сети Петри представляются идеальными
для моделирования систем с распределенным
управлением, в которых несколько процессов
выполняются одновременно.
15
Одновременность и конфликт
Другая важная особенность сетей Петри – это их
асинхронная природа. В сети Петри отсутствует измерение
времени или течение времени. Это отражает философский
подход к понятию времени, утверждающий, что одно из
важнейших свойств времени, с логической точки зрения, это определение частичного упорядочения событий. В
реальной жизни различные события укладываются в
различные интервалы времени, и это отражено в модели
сети Петри независимо от времени управления последовательностью событий. структура сети Петри такова. что
содержит в себе всю необходимую информацию для
определения возможных последовательностей событий. Т.е.
событие «завершение выполнения задания» должно
следовать за событием «начало выполнения задания», но
нет и не нужно информации. связанной с количеством
16
времени, необходимым для выполнения задания.
Одновременность и конфликт
Выполнение сети Петри рассматривается здесь как
последовательность дискретных событий. Порядок
появления событий является одним из возможных,
допускаемых основной структурой. Это приводит к явной
недетерминированности в выполнении сети Петри. Если в
какой-то момент времени разрешено более одного перехода, то любой из нескольких возможных переходов может
стать "следующим запускаемым". Выбор запускаемого
перехода осуществляется недетерминированным образом,
т.е. случайно. Эта особенность сети Петри отражает тот факт,
что в реальной жизненной ситуации, где несколько действий
происходит одновременно, возникающий порядок появления событий - не однозначен; скорее может возникнуть
любая из множества последовательностей событий. Однако
частичный порядок появления события - единственен. 17
Одновременность и конфликт
Проблемы, включающие в себя эти понятия, имеют
философский характер. В своей точке зрения на природу и
Вселенную многие ученые склонны к детерминизму: все
действия предопределены состоянием Вселенной, и
никакого беспорядка не существует. Кажущийся беспорядок
– просто результат недостатка знаний о состоянии
Вселенной и ее переходов из состояния в состояние. В этом
смысле выбор для запусков одного из разрешенных
переходов в моделируемой системе детерминирован, но не
в модели, просто потому что модель не дает полной
информации о системе.
18
Одновременность и конфликт
Обратимся к теории относительности. Одним из ее
основных положений является утверждение, что передача
чего-либо не может быть мгновенной. Даже информация о
возникновении события распространяется в пространстве со
скоростью, ограниченной скоростью света. Это значит, что
если два события и произойдут одновременно (т.е. они не
имеют причинной взаимосвязи), то порядок возникновения
этих событий для двух разных наблюдателей может оказаться различным. Для двух событий А и В, происходящих в
одно и то же время, наблюдатель, расположенный в непосредственной близости от события А, получит информацию,
связанную с событием А, прежде, чем информацию, связанную с событием В. Таким образом, он сделает вывод, что
событие а произошло раньше, чем событие В. С другой
стороны, наблюдатель, расположенный в непосредственной
близости от события В, отметит прямо противоположную
19
последовательность событий.
Одновременность и конфликт
Такое представление, хоть и является необходимым для
полноты рассмотрения происходящего, однако влечет за собой значительные трудности при описании и анализе динамического поведения сети Петри, когда определяется последовательность запусков переходов. Для простоты обычно
вводят следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное
событие, занимающее нулевое время, и возникновение
двух событий одновременно невозможно. Моделируемое
таким образом событие называется примитивным;
примитивные события мгновенны и неодновременны.
(Иногда это обосновывается тем, что время – это непрерывная
действительная переменная. Следовательно, если мы присвоим
каждому событию время возникновения, то вероятность того, что
любые две произвольно выбранные непрерывные действительные переменные совпадают, равна нулю, и, следовательно,
20
события неодновременны.)
Одновременность и конфликт
Непримитивными называются такие события,
длительность которых отлична от нуля. Они не являются
одновременными и, следовательно, могут пересекаться во
времени. Так как осуществление большинства событий в
реальном мире занимает некоторое время, то они являются
непримитивными событиями и поэтому не могут должным
образом моделироваться переходами в сети Петри. Однако
это не приводит к возникновению проблем при моделировании систем. Непримитивное событие может быть представлено в виде двух примитивных событий «начало непримитивного события» и «конец непримитивного события» и
условия «непримитивное событие происходит». Эта ситуация моделируется сетью Петри следующего вида:
Начало непримитивного события
Конец непримитивного события
21
Одновременность и конфликт
Петри и некоторые другие ученые предложили
представлять непримитивные события в сети Петри в виде
прямоугольника, а примитивные события – планками, как и
раньше. Однако прямоугольник может иметь существенное
значение при моделировании сложных систем на
нескольких иерархических уровнях, так как он позволяет
выделить в отдельный элемент сети целые подсети. Это в
некотором смысле подобно понятиям подпрограммы или
макроса в языках программирования.
22
Одновременность и конфликт
Задание помещается
во входную очередь
Задание
ждет
Задание
обрабатывается
Задание
ждет
вывода
Процессор
свободен
Задание
выводится
Моделирование вычислительной системы
с использованием непримитивного перехода
23
Одновременность и конфликт
Недетерминированность и неодновременность запусков
переходов в моделировании параллельной системы показываются двумя способами. Один из них представлен ниже:
Это называется
одновременность
(2 перехода могут
запускаться в любом
порядке)
В этой ситуации два разрешенных перехода в любом случае не влияют друг на друга, и в число возможных последовательностей событий входят последовательности, в которых
24
первым запускается tj или tk
Одновременность и конфликт
Другая ситуация, в которой одновременное выполнение
затруднено и которая характеризуется невозможностью
одновременного возникновения событий, показана ниже
Это называется
конфликт
(запуск любого из них
запрещает запуск
другого)
Здесь два разрешенных перехода находятся в конфликте.
Может быть запущен только один переход, так как при запуске
он удаляет фишку из общего входа и запрещает другой
переход. Таким образом моделируются взаимоисключающие
25
события системы.
Одновременность и конфликт
Рассмотренные ситуации требуют внимательного
изучения моделируемых сетями Петри систем для
правильного отображения их поведения. К сожалению,
многие работы по сетям Петри исследовали только свойства
данной сети или класса сетей. Разработке же методов
моделирования специально для сетей Петри внимания
уделялось мало.
Однако существуют определенные области, в которых
сети Петри представляются идеальным инструментом для
моделирования: это те области, в которых события
происходят асинхронно и независимо.
Далее рассмотрим моделирование сетями Петри
аппаратного и программного обеспечения ЭВМ и других
систем.
26
Документ
Категория
Презентации
Просмотров
24
Размер файла
646 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа