textbook (527012), страница 4
Текст из файла (страница 4)
Дуга направлена от перехода к позиции,если позиция является выходной для перехода. Кратные входы и выходы23изображаются кратными дугами, поэтому сеть Петри в общем случае является ориентированным двудольным мультиграфом. Рассмотрим пример сетиПетри C = 〈P, T, I, O〉.I(t1) = {p1},O(t1) = {p1, p2, p3},I(t2) = {p2, p3, p5},O(t2) = {p5},I(t3) = {p3},O(t3) = {p4, p4},I(t4) = {p4}.O(t4) = { p2, p3}.Граф этой сети изображен на рис. 2. 2Маркировка µ сетей Петри C = 〈P, T, I, O〉 – это функция, отображающая множество позиций Р в множество неотрицательных целых чисел N,µ : Р → N. Другими словами, маркировка присваивает каждой позиции некоторое, быть может, нулевое, число меток.
На графе метки отображаютсяточками внутри позиций. Сеть Петри с определенной на ней разметкой называется маркированной. Маркировку µ можно определить как n-мерныйвектор µ = (µ1, ..., µn), где n = |Р| – число позиций, а µi ∈ N – число меток впозиции pi.P2t4P5P1t2P4t1t3P3Рис. 2. 2. Пример графа сети ПетриЧисло и расположение меток могут изменяться при выполнении сетиПетри, которое само зависит от числа и распределения меток по сети.
Подвыполнением сети Петри понимается последовательность запусков переходов. Переход запускается удалением меток из его входных позиций и добав-24лением меток в выходные позиции перехода. Переход может запускатьсятолько в том случае, если он разрешен. Переход называется разрешенным,если каждая из его входных позиций имеет число меток, по крайней мере,равное числу дуг из позиции в переход. Метки во входных позициях, которые разрешают переход, называются его разрешающими метками.Формальное определение: переход tj в сети с маркировкой µ разрешен,если для всех рi ∈ Р µ(рi) ≥ #(рi, I(tj)), где µ(рi) – количество меток в позициирi.Переход запускается удалением всех его разрешающих меток из входных позиций и последующим помещением в каждую из его выходных позиций по одной метке для каждой выходящей из перехода дуги.
В общем случае запуск перехода заменяет маркировку сети Петри µ на новую маркировку µ'. Запуск перехода tj приводит к новой маркировке µ', определяемой изсоотношения:µ'(рi) = µ(рi) – #(рi, I(tj)), + #(рi, О(tj)).Поскольку запускаться могут только разрешенные переходы, для которых µ(рi) ≥ #(рi, I(tj)) для всех рi, то число меток в любой позиции будет оставаться неотрицательным.Рассмотрим маркированную сеть на рис. 2.3, а.
В этой сети переход t1разрешен, а переход t2 запрещен, так как отсутствует разрешающая метка впозиции р3. После срабатывания перехода t1 разметка изменится, как показано на рис. 2.3, б. В этом состоянии разрешен переход t2, а переход t1 запрещен, так как отсутствует разрешающая метка в позиции р1. С выполнением сети Петри связаны две последовательности: последовательность маркировок (µ0, µ1, µ2, ...) и последовательность переходов (tj0, tj1, tj2, ...).
Эти двепоследовательности связаны соотношениемδ(µk, tjk) = µk+1,k = 0, 1, 2, ...Имея последовательность переходов и µ0, легко получить последовательность маркировок, но не наоборот.25Пусть некоторый переход в маркировке µ разрешен и, следовательно,может быть запущен. Результат запуска перехода в маркировке µ есть новаямаркировка µ'. Говорят, что µ' является непосредственно достижимой измаркировки µ.Р1t2Р3Р1t2Р3Р2t1Р4Р2t1Р4абРис. 2.3. Маркированная сеть Петри: а – до срабатывания перехода t1;б – после срабатывания перехода t12.3. Моделирование с помощью сетей ПетриПростое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия,имеющие место в системе.
Возникновением событий управляет состояниесистемы. Состояние системы может быть описано множеством условий. Условие – это предикат или логическое описание состояния системы. Условиеможет принимать либо значение «истина», либо значение «ложь».Условия, выполнение которых необходимо для возникновения события,называются его предусловиями. При возникновении события система переходит в состояние, характеризующееся выполнением условий, называемыхпостусловиями.Рассмотрим задачу моделирования логического управления технологическим участком, на котором детали проходят весь путь обработки.Для этой системы выделим следующие условия:А – деталь ожидает обработки;Б – технологический робот свободен;26В – деталь обрабатывается;Г – деталь ожидает транспортного робота.Событиями в системе являются следующие действия:1 – деталь поступает во входную очередь;2 – деталь начинает обрабатываться;3 – обработка детали завершена;4 – передача детали в накопитель.Связь событий с предусловиями и постусловиями показана в табл.
2.1.Таблица 2.1СобытиеПред-Пост-условиеусловие1НетА2А, БВ3ВГ, Б4ГНетЭта таблица интерпретируется сетью Петри следующим образом. Условия представляются позициями, события – переходами. Входами переходаявляются предусловия соответствующего события, выходами – его постусловия. Возникновение события моделируется запуском перехода. Выполнение условия моделируется наличием метки в позиции, соответствующейусловию. Сеть, моделирующая описанную систему, приведена на рис.
2.4.Выполнение сети Петри (и соответственно поведение моделируемойсистемы) рассматривается как последовательность дискретных событий.Последовательность возникновения событий может быть реализованалюбая из множества возможных. Если в какой-либо момент времени разрешено несколько переходов, то следующим запускаемым переходом может27быть любой из них. Это свойство сетей Петри отражает неоднозначностьпорядка возникновения событий, связанных с параллельно протекающимипроцессами.
Таким образом, выполнению сети Петри свойственен недетерминизм.Деталь поступает в очередьДеталь ожидаетобработкиДеталь заканчиваетобрабатыватьсяДеталь начинаетобрабатыватьсяДеталь обрабатываетсяПередача деталив накопительДеталь ожидаеттранспортногороботаРобот свободенРис. 2.4. Модель технологического участка в виде сети ПетриДругая важная особенность сетей Петри – их асинхронная природа. Сети Петри не обладают какими-либо средствами, отражающими течение времени или фиксирующими некоторые моменты времени. Однако они представляют возможность отображать частичный порядок возникновения событий, т.е. обладают важным свойством отражения относительного временипротекания процессов путем установления причинно-следственной связисобытий.Средства установления причинно-следственных связей событий позволяют моделировать важные свойства систем логического управления – параллелизм и конфликтные ситуации.
Параллелизм моделируется в сети Петри независимыми разрешенными переходами (рис. 2.5, а). Переходы tj и tk втакой ситуации не влияют друг на друга, поэтому возможные последовательности срабатывания переходов здесь такие ... tj, ...., tk, ... и .... tk, ...., tj, ...28tjtjtktkабРис. 2.5. Представление в терминах сетей Петри: a – параллельныхпроцессов; б – конфликтных ситуацийВ другой ситуации (рис. 2.5, б), называемой конфликтной, разрешенныепереходы имеют общую разрешающую метку, и поэтому запуск одного перехода удаляет общую метку и таким образом запрещает другой переход.Таким образом, сети Петри – удобный инструмент для моделированиясистем, события в которых происходят асинхронно и независимо, и представления причинно-следственных связей, на основе чего моделируются параллелизм и конфликты.Введение параллелизма полезно только в том случае, когда компонентыпроцессов могут взаимодействовать при решении задачи.
Такое взаимодействие требует распределения ресурсов между процессами. Для обеспеченияправильности работы системы в целом распределением необходимо управлять. При взаимодействии процессов возникает проблема синхронизации.Рассмотрим моделирование некоторых разновидностей задачи синхронизации.291. Задача о производителе-потребителеПусть процесс-производитель создает объекты, которые помещаются вбуфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляетего оттуда и использует. Такая ситуация моделируется сетью, представленной на рис.
2.6. Позиция В представляет собой буфер, каждая метка соответствует элементу, который произведен, но еще не использован.Р1Р2Удалить из буфераПроизвестиВПоместить вбуферИспользоватьПроизводительПотребительРис. 2.6. Сетевая модель задачи о производителе-потребителеРазновидность этой задачи – задача о нескольких производителяхпотребителях. Если имеем t потребителей и s производителей, начальнаямаркировка сети изменится.
В позиции р1 будет s меток, в позиции р2 – t меток. Третий вариант задачи – задача о производителе-потребителе с ограниченным буфером, т.е. буфер имеет только n ячеек элементов данных. Следовательно, производитель не имеет возможности работать с постоянной скоростью и иногда вынужден ждать, если буфер заполнен, т.е.
потребитель работает медленно.Сеть, моделирующая эту ситуацию, представлена на рис. 2.7.Ограниченному буферу соответствует две позиции: В и В'. Разметка в Всоответствует количеству помещенных в буфер элементов данных, разметкав В' – количеству свободных мест хранения в буфере. Начальная разметкасоответствует показанной на графе (n меток в позиции В').30Р1Р2Удалить из буфераПроизвестиВПоместить вбуферnИспользоватьВ'ПроизводительПотребительРис.
2.7. Сетевая модель задачи о производителе-потребителес ограниченным буферомОтсутствие меток в позиции В' соответствует полностью заполненномубуферу. В этом случае переход «поместить в буфер» запрещен, и производитель будет ожидать события «удалить из буфера», которое приведет к появлению разрешающей метки в В'.2. Задача о чтении-записиПусть имеются процессы двух типов: процессы чтения и процессы записи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
