Лекционный курс от Русакова (1087061), страница 7
Текст из файла (страница 7)
Награфе сети Петри фишки изображаются крупными точками в кружке, которыйпредставляет позицию сети Петри. Количество фишек (точек) для каждойпозиции не ограничено и, следовательно, в целом для сети существуетбесконечно много маркировок. Множество всех маркировок сети, имеющей nпозиций, является множеством всех n векторов, т.е. Nn. Очевидно, что хотя этомножество и бесконечно, но оно счетно.
Когда маркировка превышает 4 или 5фишек, то в кружках удобнее не рисовать фишки, а указывать их количество какна рис. 3.7.P1t1P22212t2t3P3108P4рис. 5Маркировка =(12,22,8,10) - как вектор. Может оказаться, что структураостается неизменной, а маркировка иная, например вектор маркировки будетиметь вид = (13,22,9,10)1.5 Правила выполнения сетей Петри.Выполнением сети Петри управляют количество и распределение фишек всети.
Сеть Петри выполняется посредством запусков переходов. Переходзапускается удалением фишек из его входных позиций и образованием новыхфишек, помещаемых в его выходные позиции.Переход запускается, если он разрешен. Переход называется разрешенным, есликаждая из его входных позиций имеет число фишек по крайней мере равноечислу дуг из позиции в переход. Фишки во входной позиции, которыеразрешают переход, называются его разрешающими фишками.
Например, еслипозиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 ир2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом{p3,p3,p3} позиция р3 должна иметь не менее 3 фишек для разрешения переходаt3 (рис.
6).a)t1t3P3б)P1P2рис. 6Определение 3.9. Переход tj, Т маркированной сети Петри С = (Р,T,I,O,) смаркировкой , разрешен, если для всех pi, P, (pi)>=#(pi,I(tj)).Переход запускается удалением разрешающих фишек, из всех его выходныхпозиций (количество удаленных фишек для каждой позиции соответствуетчислу дуг, идущих из этой позиции в переход), с последующим помещениемфишек в каждую из его выходных позиций (количество помещаемых фишек впозицию соответствует количеству дуг входящих в данную позицию изперехода).Переход t3 I(t3) = {p2} и O(t3) = {p3,p4} разрешен каждый раз, когда в р2 будетхотя бы одна фишка. Переход t3запускается удалением одной фишки изпозиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы).Переход t4, в котором I(t4) = {p4,p5} и O(t4) = {p5,p6,p6} запускается удалениемпо одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и двев р6 (рис.
7).P3P2t3t4P4P4P5рис. 7P6.Определение 3.10. Переход tj в маркированной сети Петри с маркировкой может быть запущен всякий раз, когда он разрешен. В результате запускаразрешенного перехода tj образуется новая маркировка ':'(pi) = (pj)-#(pi,I(tj)+#(pi,O(tj)).2. Сети Петри для моделирования систем: способы реализации.2.1 События и условия.Представление системы сетью Петри базируется на двух понятиях: событияхи условиях. Под событием понимается действие, имеющее место в системе.Появление события определяет состояние системы, которое может быть описаномножеством условий.
Условие - это предикат или логическое описаниесостояния системы. При этом условие может принимать либо значение"истина", либо значение "ложь".Для того, чтобы событие произошло, необходимо выполнениесоответствующих условий, которые называются предусловиями события.Возникновение события может привести к появлению постусловий.В сети Петри условия моделируются позициями, события - переходами. Приэтом входы перехода являются предусловиями соответствующего события,выходы - постусловиями. Возникновение события равносильно запускусоответствующего перехода. Выполнение условия представляется фишкой(маркером) в позиции, соответствующей этому условию.
Запуск переходаудаляет разрешающие маркеры, представляющие выполнение предусловий иобразует новые маркеры, которые представляют выполнение постусловий.Построение моделей систем в виде сетей Петри связано со следующимиобстоятельствами:1. Моделируемые процессы (явления) совершаются в системе, описываемоймножеством событий и условий, которые эти события определяют, а такжепричинно - следственными отношениями, устанавливаемыми на множестве"события - условия".2. Определяются события - действия, последовательность наступления которыхуправляется состоянием системы.
Состояния системы задаются множествомусловий. Условия формулируются в виде предикатов. Количественные условияхарактеризуются емкостью. Емкость условий выражается числами натуральногоряда.3. Условия (предикаты) могут быть выполнены или не выполнены. Тольковыполнение условий обеспечивает возможность наступления событий(предусловия).4. После наступления события обеспечивается выполнение других условий,находящихся с предусловиями в причинно - следственной связи (постусловия).После того, как событие имело место, реализуются постусловия, которые в своюочередь являютсяпредусловиями следующего события и т.д.В качестве примера рассмотрим задачу моделирования работы автомата попроизводству какого либо изделия. Автомат находится в состоянии ожидания допоявления заготовки, которую он обрабатывает и посылает в накопитель, т.е.событиями для такой системы являются:1.
заготовка поступила;2. автомат начинает обработку;3. автомат заканчивает обработку;4. деталь посылается в накопитель.Условиями для системы являются:1. автомат ждет;2. заготовка загружена;3. автомат выполняет обработку;4. деталь обработана.В сети Петри условия моделируются позициями, а события - переходами. Приэтом входы перехода являются предусловиями соответствующего события, авыходы - постусловиями. Выполнение условия представляется фишкой(маркером) в позиции, соответствующей этому условию. Запуск переходаудаляет разрешающие фишки, представляющие выполнение предусловий иобразуют новые маркеры, которые представляют выполнение постусловий.Сеть Петри рассматриваемого автомата имеет вид (рис.8):t1 ЗаготовказагруженаPбЗаготовкапоступила нанакопительt2Автоматt3обрабатываетPвPaДетальt4обработанаPгДетальпомещенана транспортёрКонец обработкиНачало обработкирис.8Автомат ждётАналогичный пример можно привести для вычислительной системы, котораяобрабатывает задания, поступающие с устройства ввода и выводит результатына устройство вывода.
Задание поступает на устройство ввода. Когда процессорсвободен и в устройстве ввода есть задание, процессор начинает обработкузадания. Когда задание выполнено, оно посылается на устройство вывода;процессор либо продолжает обрабатывать другое задание, если оно есть, либождет прихода задания. Эта система может быть промоделирована сетью Петри,изображенной на рис.9Ввод заданияЗаданиеожидаетвводаНачаловыполнениязаданияЗадание обрабатываетсяПроцесс2.2 Одновременность и конфликт.Одной из особенностей сетей Петри и ихсвободен моделей является параллелизм илиодновременность. В модели сети Петридва разрешенных взаимодействующихКонецсобытия могут происходить независимовыполнениядруг от друга, но при необходимости ихЗаданиелегко синхронизировать.
Т.о. сети Петриожидаетпредставляютсяидеальнымидлявводамоделированиясистемсраспределенным управлением, в которыхнесколькопроцессоввыполняютсяВывод заданияодновременно.Рис. 9Другая важная особенность сетей Петри- их асинхронная природа. В сети Петри отсутствует измерение времени илитечение времени. Структура сетей такова, что содержит в себе информацию дляопределения возможных последовательностей событий. В этих моделях нетникакой информации, связанной с количеством времени, необходимым длявыполнения событий.Выполнение сети Петри рассматривается как последовательностьдискретных событий.
Обычно запуск перехода рассматривается как мгновенноесобытие, занимающее нулевое время и одновременное возникновение двухсобытий невозможно. Моделируемое таким образом событие называетсяпримитивным, примитивные события мгновенны и неодновременны.Непримитивными называются события, длительность которых отлична отнуля. Однако это не приводит к возникновению проблем при моделированиисистем.
Непримитивное событие может быть представлено в виде двухпримитивных: "начало непримитивного события", "конец непримитивногособытия" и условия когда «непримитивное» событие происходит".а)б)Началонепримитивное конецнепримитивсобытие непримитивногоного события происходитсобытиярис.10В сетях Петри предложено представлять непримитивные события в видепрямоугольника (рис.10), а примитивные события планками. Прямоугольникможет иметь существенное значение при моделировании сложных систем нанескольких иерархических уровнях, т.к.
он позволяет выделить в отдельныйэлемент сети целые подсети. Наличие прямоугольника в некотором смыслеподобно понятию подпрограммы в блочном программировании и можетоказаться в некоторых приложениях весьма полезным.Если в какой либо момент времени разрешено более одного перехода, то любойиз них может стать “следующим”. Выбор запускаемого переходаосуществляется недетерминированным образом, то есть случайно и зависит отволи моделирующего систему. Недетерминорованность и неодновременностьзапусков переходов в моделировании паралельной системы показывается двумяспособами. Одна из них представлена наtjрисунке 11.В этойситуации дваразрешённых перехода tj и tk не влияютtjдруг на друга.
В число возможныхпоследовательностей событий входитпоследовательность, в которой первымtkсрабатываетодинпереходиtkрис 11рис 12 последовательность в которой первымсрабатывает другой переход. Эти дваперехода могут быть запущены в любом порядке, это называетсянедетерминированностью и неодновременностью, переход tk (рис 12) можетбыть запущен в любом порядке, но обязательно при помощи маркеров в обеихпозициях. Это называется одновременностью.
Другая ситуация, в которойодновременное выполнение затруднено и которая характеризуетсяневозможностью одновременного запуска показана на рисунке 10. Здесьпереходы tj и tk находятся в конфликте, так как запуск одного из них удаляетмаркёр из pi и тем самым завершает другой переход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
