67194

Сетевые модели (N-схемы). Сети Петри

Лекция

Информатика, кибернетика и программирование

Теоретические основы сетей Петри: принципы построения алгоритмы поведения. Сети Петри были разработаны и используются для моделирования систем которые содержат взаимодействующие параллельные компоненты например аппаратное и программное обеспечение...

Русский

2014-09-04

264 KB

5 чел.

Лекция № 7

Сетевые модели (N-схемы). Сети Петри

1. Теоретические основы сетей Петри: принципы построения, алгоритмы поведения.

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

1.1 Введение в теорию комплектов.

  Сети Петри - инструмент исследования систем. Сети Петри делают возможным моделирование системы математическим представлением ее в виде сети Петри. Математическим аппаратом сетей Петри является теория комплектов. Теория комплектов представляет собой естественное расширение теории множеств. Как и множество, комплект является набором элементов из некоторой области. Однако в отличие от множества комплекты допускают наличие нескольких экземпляров одного и того же элемента. В отличие от множества, где элемент либо является элементом множества, либо нет, в  комплект элемент может входить заданное число раз. Пусть область представляет собой {a,b,c,d}, тогда комплекты над  этой областью будут иметь вид:

       B1={a,b,c}     B2={a}       B3={a,b,c,c}

       B4={a,a,a}     B5={b,c,b,c}   B6={c,c,b,b}

       B7={a,a,a,a,a,a,b,b,b,b,b,c,d,d,d,d,d}

Основным понятием теории комплектов является функция числа экземпляров. Обозначение #(x,B) число х в В т.е. число экземпляров  элемента х в В. Если ограничить число элементов в комплекте так, что  0 <= #(x,B) <= 1, то получим теорию множеств.

 Элемент х является членом комплекта В, если #(x,B) > 0. Аналогично, если #(x,B) = 0 то х не принадлежит В.

 Определим пустой комплект 0, не имеющий членов ( для всех х : #(x,0) = 0 ). Под мощностью |В| комплекта В понимается общее число экземпляров в комплекте  |B| = x #(x,B).

Комплект А является подкомплектом комплекта В (обозначается АВ ), если каждый элемент А является элементом В по крайней мере не больше число  раз, т.е. АВ тогда и только тогда, когда   #(x,A) <= #(x,B) для всех х.

 Два комплекта равны (А = В), если #(x,A) = #(x,B).  

 Комплект А строго включен в комплект В (АВ), если АВ и А не равно В. Над комплектами определены 4 операции. Операции для двух комплектов А и В:

  1 объединение АВ: #(x,AB) = max (#(x,A),#(x,B));

  2 пересечение А В: #(x,A B) = min (#(x,A),#(x,B));

  3 сумма А + В: #(x,A + B) = #(x,A)+#(x,B);

  4 разность А - В: #(x,A - B) = #(x,A) - #(x,B);

 

 Назовем множество элементов, из которых составляются комплекты, областью D.  Пространство комплектов Dn есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого В Dn :

   а)  из х В следует х D;

   б)  для любого х #(x,B) <= n.

 Множество D есть множество всех комплектов над областью D, без какого либо  ограничения на число экземпляров элемента в комплекте.

1.2 Структура сети Петри.

Сеть Петри состоит из 4 компонентов, которые и определяют ее  структуру:

   - множество позиций Р,

   - множество переходов Т,

   - входная функция I,

   - выходная функция О.

 Входная и выходная функции связаны с переходами и позициями. Входная функция I  отображает переход tj в множество позиций I(tj), называемых входными позициями перехода. Выходная функция О отображает переход tj в множество позиций О(tj), называемых выходными позициями перехода. Т.е.

                                                                                ( I  : T -> P)

                (O : T -> P).

Определение 1. Сеть Петри С является четверкой С = (P,T,I,O) где

                        Р={p1,p2,...,pn} конечное множество позиций, n>=0.

                T={t1,t2,...,tm} конечное множество переходов, m>=0.

 Множества позиций и переходов не пересекаются.

   I : T -> P является входной функцией -

 отображением из переходов в комплекты позиций.

                 O : T -> P выходная функция  - отображение из переходов в комплекты позиций.

      Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом pi, i=1...n; а  произвольный элемент Т - символом tj, j=1...m.

                              

рис. 1

Позиция pi является входной позицией перехода tj, в том случае, если pi   I(tj);

pi является выходной позицией перехода, если pi O(tj).

                                                                                                            

рис. 2

  Входы и выходы переходов представляют комплекты позиций. Кратность входной  позиции  для перехода tj есть число появлений позиции во входном комплекте  перехода #(pi,I(tj)). Аналогично, кратность выходной позиции pi для перехода tj есть число появлений позиции в выходном комплекте перехода  #(pi,O(tj)).

     Определим, что переход tj является входом позиции pi, если pi есть выход tj (рис. 2). Переход tj есть выход позиции pi, если pi есть вход tj (рис. 1).

Определение 2. Определим расширенную входную функцию I и выходную функцию О таким образом, что #(tj,I(pi)) = #(pi,O(tj));  #(tj,O(pi)) = #(pi,I(tj));

1.3  Графы сетей Петри.

 Для иллюстрации понятий теории сетей Петри гораздо более удобно графическое представление сети Петри. Теоретико - графовым представлением сети Петри является двудольный ориентированный мультиграф. В соответствии с этим граф сети Петри обладает двумя типами узлов:

                                               кружок   O  является позицией,

                                         планка    |   является переходом.

Ориентированные дуги соединяют позиции и переходы. Дуга направленная от позиции pi к переходу tj определяет позицию, которая является входом перехода tj. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выданая позиция указывается дугой от перехода к позиции. Кратные входы также представлены кратными дугами.

Определение 3. Граф G сети Петри есть двудольный ориентированный мультиграф G=(V,A) где  

V = {v1,V2,...,vs} - множество вершин

А = {a1,a2,...,ar}  - комплект направленных дуг,

              ai={vj,vk}    где   vj,vk    V.  

Множество  V может быть разбито  на 2 непересекающихся подмножества Р и Т, таких что P T = 0, и если ai = (vj,vk), тогда либо vj  P и  vk T, либо vj T и  vk P.

 Сеть Петри есть мультиграф, т.к. он допускает существование кратных дуг от одной вершины к другой. Т.к. дуги направлены, то это ориентированный мультиграф. Граф является двудольным, т.к. он допускает существование  вершин двух типов: позиций и переходов.

1.4 Пример. Представление сети Петри в виде графа и в виде структуры                                                                                                                                                              сети Петри.

  Пусть задана следующая структура сети Петри:  C = (P,T,I,O), n=5, m=4

       P = {p1,p2,p3,p4,p5}     T = {t1,t2,t3,t4}

       I(t1)={p1}                      O(t1)={p2,p3,p5}  

       I(t2)={p2,p3,p5}             O(t2)={p5}

       I(t3)={p3}                      O(t3)={p4}

       I(t4)={p4}                      O(t4)={p2,p3}

                                                                                                                                                                                                                                                                                                                                         

 Для сети, изображенной на рис. 3 расширенными входной и выходной функциями   являются:     

рис. 3

                 I(p1)={}                   O(p1)={t1}

                I(p2)={t1,t4}            O(p2)={t2}                                    

                I(p3)={t1,t4}            O(p3)={t2,t3}

                I(p4)={t3}                O(p4)={t4}

                I(p5)={t1,t2}            O(p5)={t2}

                                                               

 Пример 2. Пусть задана следующая структура сети Петри:  C = (P,T,I,O)

         P={p1,p2,p3,p4,p5,p6}     T={t1,t2,t3,t4,t5}  n=6, m=5.

         I(t1)={p1}                  O(t1)={p2,p3}

         I(t2)={p3}                  O(t2)={p3,p5,p5}

         I(t3)={p2,p3}             O(t3)={p2,p4}

         I(t4)={p4,p5,p5,p5}    O(t4)={p4}

         I(t5)={p2}                  O(t5)={p6}

рис. 4

Заметим, что оба представления сети Петри - в виде структуры и в виде  графа - эквивалентны. Их можно преобразовать друг в друга.           

1.4 Маркировка сетей Петри.

 Маркировка есть присвоение фишек позициям сети Петри. Фишка -  это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.

Маркированная сеть Петри есть совокупность структуры сети Петри C = (P,T,I,O) и маркировки и может быть записана  в виде  M = (P,T,I,O, ). На графе сети Петри фишки изображаются крупными точками в кружке, который    представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nn. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках удобнее не рисовать фишки, а указывать их количество как на рис. 3.7.

рис. 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).

                                                           рис. 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).

                                                                   

рис. 7

.

Определение 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):

                                                               рис.8

                          Рис. 9

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

 

 

 

 

 

 

 

 

 

 

2.2 Одновременность и конфликт.

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

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

    Выполнение сети Петри рассматривается как последовательность дискретных событий. Обычно запуск перехода рассматривается как мгновенное событие, занимающее нулевое время и одновременное возникновение двух событий невозможно. Моделируемое таким образом событие называется примитивным, примитивные события мгновенны и неодновременны.

  Непримитивными называются события, длительность которых отлична от нуля. Однако это не приводит к возникновению проблем при моделировании систем. Непримитивное событие может быть представлено в виде двух примитивных: "начало непримитивного события",  "конец непримитивного события" и условия когда «непримитивное» событие происходит".

                                                               рис.10

 В сетях Петри предложено представлять непримитивные события в виде    прямоугольника (рис.10), а примитивные события планками. Прямоугольник    может иметь существенное значение при моделировании сложных систем на нескольких иерархических уровнях, т.к. он позволяет выделить в отдельный элемент сети целые подсети. Наличие прямоугольника в некотором смысле подобно понятию подпрограммы в блочном программировании и может оказаться в некоторых приложениях весьма полезным.

      рис 11                                рис 12

  Если в какой либо момент времени разрешено более одного перехода, то любой из них может стать “следующим”. Выбор запускаемого перехода осуществляется недетерминированным образом, то есть случайно и зависит от воли моделирующего систему. Недетерминорованность и неодновременность запусков переходов в моделировании паралельной системы показывается двумя способами. Одна из них представлена на рисунке 11.  В этой  ситуации два разрешённых перехода tj и tk  не влияют друг на друга. В число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход и последовательность в которой первым срабатывает другой переход. Эти два перехода могут быть запущены в любом порядке, это называется недетерминированностью и неодновременностью, переход tk  (рис 12) может быть запущен в любом порядке, но обязательно при помощи маркеров в обеих позициях. Это называется одновременностью. Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного запуска показана на рисунке 10.  Здесь переходы tj и tk находятся в конфликте, так как запуск одного из них удаляет маркёр из pi и тем самым завершает другой переход. Эта ситуация называется конфликтом и в моделируемых системах отображает борьбу за общие ресурсы.

   Существуют определённые области, в которых сети Петри являются идеальным инструментом для моделирования: это области, в которых события происходят синхронно и независимо. Одной из таких областей является использование сетей Петри для моделирования аппаратного и програмного обеспечения ЭВМ и других систем.


 

А также другие работы, которые могут Вас заинтересовать

21755. Организация табельного учета 24.5 KB
  Табельный учет выполняет следующие функции: контроль за своевременной явкой рабочих и служащих на работу фиксирование опозданий и невыходов; проверку нахождения на местах работы работников учтенных в числе явившихся на работу; проверку правильности использования внутрисменных обеденных перерывов; контроль за своевременностью ухода работников с работы по окончании смены; контроль за временными уходами с работы по разрешению администрации а также учет работников находящихся в отпусках командировках выполняющих...
21756. Режим работы шахты и ее участков 25 KB
  Под режимом работы понимают степень использования основных фондов и производственных мощностей во времени. Режим работы – одна из важнейших сторон организации производства характеризующая продолжительность использования средств труда при определенной интенсивности смены суток года во времени. Режим работы устанавливается для производственных единиц ее участковцехов отдельных бригад и рабочих.
21757. Формы организации труда на рудниках 26 KB
  В зависимости от состава и методов учета выполненных работ различают специализированные и комплексные бригады. Специализированные бригады бригады выполняющие один процесс переноску конвейера доставку крепежного материала бурение и т. В настоящее время наибольшее распространение в очистных и подготовительных забоях ПО Беларуськалий получили комплексные бригады выполняющие несколько взаимосвязанных процессов при коллективной организации труда. По сравнению со специализированными бригадами комплексные бригады...
21758. Графики выходов рабочих 26 KB
  В них показывается порядок чередования смен и выходные дни для отдельных рабочих и бригад. В графиках выходов предусматривается: соответствие принятому числу рабочих смен продолжительности рабочего дня и рабочей недели т. режиму работы данного участка во времени; правильное чередование дней работы и отдыха; полное использование установленной нормы рабочего времени за месяц минимальное значение которой при 7часовом рабочем дне составляет 1731 ч а при 6часовом рабочем дне 1525 ч; правильное чередование смен; соблюдение постоянного...
21759. Алгоритм составления графиков выходов рабочих 23 KB
  Алгоритм составления графиков следующий: определяют число бригад в сутки исходя из недельного режима работы на рабочем месте; определяют явочное число рабочих в каждой смене в соответствии с выполняемыми производственными процессами объёмом работ и обслуживанием; составляют графики выходов: обозначают общевыходной день для участка; обозначают выходные дни для отдельных членов бригады или всей бригады; отмечают номера смен и порядок их ломки; вносят графические обозначения смены обозначаются цифрами а выходные дни – нулями; при...
21760. Научная организация труда и ее элементы 29.5 KB
  Прогрессивной следует считать организацию которая основывается на достижениях науки и передовом опыте позволяет наиболее эффективно соединить в одном производственном процессе сам труд предмет и средства труда. Научная организация труда НОТ это комплекс научно обоснованных планомерно осуществляемых технических организационных и экономических мероприятий обеспечивающих рациональное разделение и кооперацию труда совершенствование трудовых приемов и организации рабочих мест улучшение их обслуживания создание благоприятных...
21761. Элементы НОТ общего характера 25 KB
  К ним относятся: подготовка и повышение квалификации кадров совершенствование нормирования и оплаты труда воспитание трудящихся в духе сознательного отношения к труду соблюдение государственной и трудовой дисциплины. Достижения научнотехнического прогресса обусловливают постоянное изменение характера и содержания труда горняков профессионального и квалификационного состава рабочих кадров. Органическим элементом научной организации труда является нормирование труда которое основано на рациональном выполнении рабочих процессов....
21762. Планирование НОТ и внедрение планов НОТ 27 KB
  Для обеспечения эффективности производства и улучшения качества работы планируют и внедряют планы НОТ. Планы НОТ должны обеспечивать комплексность планируемых и осуществляемых мероприятий; реальность планируемых мероприятий учитывающих научную обоснованность мероприятий с использованием достижений научнотехнического прогресса; непрерывность планирования мероприятий НОТ и экономичность которая обеспечивается выбором оптимального варианта и сопоставления необходимых затрат с достигаемым эффектом от внедрения отдельных...
21763. Рудничная аэромеханика 162 KB
  Режимы движения воздуха в шахтных вентиляционных системах. Применение уравнения Бернулли к движению воздуха по горным выработкам. Основное уравнение аэростатики Аэростатика наука о равновесии газов воздуха. Одной из основных задач аэростатики является определение изменения давления неподвижного воздуха с ростом высоты или глубины а также условий равновесия находящегося в воздушной среде тела.