Сети Петри для моделирования дискретных динамических систем

Лекция 8 ТИ Сети Петри Основные понятия, определения. Сети Петри используются для моделирования дискретных динамических систем. Для систем, моделируемых с помощью КА, характерен последовательный способ функционирования – система последовательно переходит из состояния в состояние в соответствии с заданной функцией перехода. Сложные системы с недетерминированным поведением, в которых отдельные компоненты функционируют независимо, лишь время от времени взаимодействуя друг с другом, с помощью КА описать затруднительно (к таким системам относятся многопроцессорные вычислительные системы, параллельно работающие программы, мультипрограммные операционные системы и т.д.). Для моделирования таких систем имеет смысл отказаться от дискретного времени и заменить его причинно-следственными связями между событиями, которые моделируют компоненты систем и их действия (события – исполняемые операторы программы, прерывание в ОС, завершение этапа проекта и т.д.). Взаимодействия событий моделируются не указанием непосредственной связи между ними (что сделать трудно в сложных динамических системах), а указанием тех ситуаций, при которых данное событие может реализоваться. Эти ситуации называются условиями реализации событий. Условие имеет емкость: условие не выполнено (емкость равна 0), условие выполнено (емкость равна 1), условие выполнено с n-кратным запасом (емкость равна n, n>0) (условие – наличие данных для операции в программе, состояние некоторого регистра в ЭВМ, наличие деталей на конвейере и т.д.). Определенные сочетания условий разрешают реализоваться некоторому событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), т.е. события и условия взаимодействуют друг с другом. В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов и множеством мест. В графическом представлении переходы изображаются "барьерами", а места – кружками. Условия-места и события-переходы связаны отношением непос­редственной зависимости (непосредственной причинно-следственной связи), которое изображается с помощью направленных дуг, ведущих из мест в переходы и из переходов в места. Места, из которых ведут дуги на данный переход, называются его входными местами. Места, на которые ведут дуги из данного перехода, называются его выходными местами. В сети на рисунке места р1 и р2 являются входными для перехода t1, а места р3 и р4 — выходными. В этом примере событие-переход t1 непосредственно зависит от условий-мест p1 и р2, а места р3 и р4 непосредственно зависят от t1. В этой же сети место p2 является входным одновременно для двух переходов t1 и t2, место р6 является выходным для двух переходов t3 и t4. Выполнение условия изображается разметкой соответствующего места, а именно помещением числа n фишек (маркеров) в это место, где n > 0 - емкость условия: n = 0 – условие р не выполнено, n = 1– условие р выполнено, n = 3 – условие р имеет емкость 3, n = 5 – условие р имеет емкость 5. Динамика поведения моделируемой системы находит свое отражение в функционировании (работе) сети Петри. Неформально работу сети можно представить как совокупность локальных действий, которые называются срабатываниями переходов. Они соответствуют реализациям событий и приводят к изменению разметки мест, т.е. к локальному изменению условий в системе. Переход может сработать, если выполнены все условия реализации события. Например, для так называемых ординарных сетей Петри все входные места перехода должны содержать хотя бы по одной фишке. Срабатывание перехода неделимое действие, изменяющее разметку его входных и выходных мест следующим образом: из каждого входного места изымается по одной фишке, а в каждое выходное место добавляется по одной фишке. Тем самым реализация события, изображаемого переходом, изменяет состояние (емкость) непосредственно связанных с ним условий так, что емкость предусловий, вызвавших реализацию этого события, уменьшается, а емкость постусловий, на которые оно влияет, увеличивается. Переход t1 на первом рисунке может сработать, так как оба его входных места p1 и р2 содержат фишки, а после срабатывания t1 разметка его входных и выходных мест изменяется так, как показано на втором рисунке. Если два (и более) перехода могут сработать и они не имеют общих входных мест, то их срабатывания являются независимыми действиями, осуществляемыми в любой последовательности или параллельно. Если несколько переходов могут сработать и имеют общее входное место (как переходы t1 и t2 на первом рисунке), то срабатывает только один, любой из них. При этом может оказаться, что, сработав, этот переход лишит возможности сработать другие переходы (так, после срабатывания t2 разметка сети будет следующей): Таким способом в сети моделируется конфликт между событиями, когда реализация одного события может исключить возможность реализации других. В сети никак не указывается, каким образом конфликт следует фактически разрешить. Считается, что решение о том, какое из конфликтующих событий следует реализовать, принимается вне формализма сети, т.е. поведение сети носит недоопределенный недетерминированный характер. Аналогичный конфликт возникает в том случае, когда несколько переходов могут сработать и они имеют общие выходные места, как переходы t3 и t4. В процессе функционирования сети происходит смена разметок мест как результат срабатывания ее переходов. Сеть останавливается, если ни один из ее переходов не может сработать. Если сеть Петри описывает функциональную схему моделируемой системы, то работа сети моделирует процесс, происходящий при функционировании системы. Поскольку процесс протекает во времени, для его изу­чения нужно зафиксировать его в форме некоторой "истории процесса", которую обычно отождествляют с самим процессом. Недетерминированный характер функционирования асинхронной системы и соответствую­щей сети Петри приводит к тому, что система может порождать не един­ственный процесс, а множество возможных процессов. Кроме того, процессы, порождаемые такими системами, являются параллельными. Возникает вопрос, каким образом формализовать понятие параллель­ного процесса, в какой системе понятий можно удобно и полно описывать параллельные процессы (а также множества параллельных процессов) и изучать их. Другими словами, возникает необходимость в разработке моделей параллельных процессов. Поскольку параллельный процесс можно рассматривать как дискретную динамическую систему, то в этом случае можно использовать сетевую модель, которая является частным случаем условно-событийной системы. Модели такого типа будем называть реализационными сетями, или сетями-процессами. Они представляют собой сети, в общем случае бесконечные, с дополнительными ограничениями на структуру связей между условиями и событиями и на начальную разметку условий. Возможность описывать системы и порождаемые ими процессы в рамках одного и того же формализма сетей позволяет не только унифицировать математический аппарат теории систем и процессов, но и более наглядно выявлять связи между функциональными и операционными свойствами систем. Рассмотрим в качестве простого примера моделирование работы автомата-продавца, который находится в состоянии ожидания до тех пор, пока ни появится заказ, который он выполняет и отправляет на доставку. События: 1) заказ поступил; 2) автомат начинает выполнение заказа; 3) автомат заканчивает выполнение заказа; 4) заказ посылается на доставку. Условия: a) автомат свободен и ждет; b) заказ прибыл и ждет; c) автомат выполняет заказ; d) заказ выполнен. Составим таблицу предусловий и постусловий для всех событий: событие предусловие постусловие 1 - b 2 a, b c 3 c d, a 4 d - 1 2 3 4 b c d a Формальное определение сети Петри Сеть Петри - это набор N = (P, Т, F, W, М0}, где P – непустое множество элементов, называемых местами, Т - непустое множество элементов, называемых переходами, F –отношение смежности (связи между р и t или между t и р ), F⊆PТТP (множество Х = РT конечно), причем выполняются условия: 1) Р ∩ T=; 2) любой элемент сети связан хотя бы с одним элементом сети другого сорта, т.е. (F≠) ˄(xРT yРT|xFy или yFx); 3) сеть не содержит пары мест, которые связаны с одним и тем же множеством переходов, т.е. если для произвольного элемента сети x обозначить 'x множество его входных элементов 'x={y|yFx }, а через x' - множество его выходных элементов x'={y|xFy}, то p1,p2Р из того, что ('p1='p2)˄(p1'= p2') → p1= p2, W - F  N \ 0} – функция, называемая кратностью дуг, (если кратность всех дуг равна 1, то сеть называется ординарной); M0: Р  N - функция, называемая начальной разметкой, которая сопоставляет каждому месту рР некоторое число М0(р)N (разметка места). В графическом представлении сети разметка места р изображается помещением в вершину-кружок числа М0(р) или, если это число невелико, соответствующего числа точек (фишек). Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний и множества достижимых в сети разметок. Эти понятия определяются через правила срабатывания сети. Разметка сети N – это функция М: Р  N. Если предположить, что все места сети N строго упорядочены каким-либо образом, т.е. Р = (р1,... ,рn), то разметку М сети (в том числе начальную разметку) можно задать как вектор чисел M = (m1, ..., mn), где mi = М (pi), 1  i  n. Если Р' ={ рi1, ..., рik  - подмножество мест из Р, то условимся через М(Р') обозначать множество разметок {М(рi1),...,М(рik)}. Если Р' представить как вектор Р' = (рi1, ... , рik), то М (Р') обозначает вектор из множества Nk, называемый проекцией разметки М на Р'. На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности, которая определяется как F (x,y) = n, если xFyW(x,y) = n 0, если (xFy) Если места сети упорядочены, то можно каждому переходу t сопоставить два целочисленных вектора 'F(t) и F(t)' длиной n, где n= Р: 'F(t) = (b1, ...,bn), где bi = F(pi,t), F(t)' = (b1,...,bn), где bi = F(t,pi). Переход t может сработать при некоторой разметке М сети N, если p't: M(p)  F (p,t), т.е. каждое входное место p перехода t имеет разметку, не меньшую, чем кратность дуги, соединяющей р и t. Это условие можно переписать в векторной форме следующим образом: M'F(t). Для ординарной сети Петри условие срабатывания перехода означает, что любое входное место этого перехода содержит хотя бы одну фишку, т.е. имеет ненулевую разметку. Срабатывание перехода t при разметке M порождает разметку М' по следующему правилу: pР: M'(p) = M(p) – F(p,t) + F(t, p) или M' = M – 'F(t)+F(t)'. Таким образом, срабатывание перехода t изменяет разметку так, что разметка каждого его входного места р уменьшается на F(р, t), т.е. на кратность дуги, соединяющей р и t, а разметка каждого его выходного места увеличивается на F (t, р), т.е. на кратность дуги, соединяющей t и р. На множестве разметок можно ввести отношение [ > непосредственного следования разметок: M[ >M'  t T: (M  'F(t))  (M' = M – 'F(t) + F(t)') Будем использовать уточняющее обозначение M[t>М', если М' непо­средственно следует после М в результате срабатывания перехода t. Говорят, что разметка М' достижима от разметки М, если существует последовательность разметок М, М1, М2, …, М' и слово  = t1t2 ...tk в алфавите Т такие, что M[t1> M1[t2 >M2 … [tk>M'  M *M'. Слово  в этом случае называется последовательностью срабатываний, ведущих от М к М'. Обобщим отношения непосредственного следования до отношения "М' достижима от М", используя обозначение М[>*М' или М[> М', если уточняется последовательность срабатываний. (Последо­вательность  может быть пустой, т.е. M достижима от М). Множество {М' М[>*М'} разметок, достижимых в сети N от разметки М, обозначим через R (N, М). Множество R(N) = R (N, M0) , т.е. множество всех разметок, достижимых в N от начальной разметки М0, называют достижимых разметок сети N. Свободным языком сети Петри N называется множество L (N) =  T*  MR (N) : M0 [ >*M т.е. множество последовательностей срабатываний, ведущих от М0 к каждой достижимой в N разметке. Рассмотрим сеть Петри, t3 p2 t1 t2 p3 p1 t4 на примере которой поясним данные выше определения. В этой сети Р =р1, р2, р3},Т = {t1,t2,t3,t4}. Функция инцидентности F задается с помощью следующих двух таблиц, в которых на пересечении строки х и столбца y стоит число F{x, у}: t1 t2 t3 t4 р1 1 1 p2 2 p3 1 1 Начальная разметка М0 задается следующим образом: M0(р1) = 1, M0(p2) = 2, M0( p3 ) = 0 или, в векторной форме: М0 = (1,2,0). При разметке М0 могут сработать переходы t1 и t2, так как М0 = (1,2,0) ≥ 'F(t1) = (1,0,0), M0 ≥ 'F(t2) = (1,2,0). Переходы t3 и t4 не могут сработать, так как М0.не больше 'F(t3) = (0, 0, 1), M0 не больше 'F(t4) = (0, 0, 1). В результате срабатывания перехода t1 разметка М0 сменяется на раз­метку М1= (1, 3, 0): М1= М0 - 'F(t1) + F(t1)' = (1,2,0) – (1,0,0) + (1,1,0) = (1,3,0) , а в результате срабатывания перехода t2 разметка М0 сменяется на разметку (0,0,1): М2= М0 - 'F(t2) + F(t2)' = (1,2,0) – (1,2,0) + (0,0,1) = (0,0,1). Обе новые разметки непосредственно следуют после М0 в рассматриваемой сети. Можно представить возможные изменения разметок сети N, происходящие в результате срабатывания ее переходов, в виде графa разметок – ориентированного графа, множество вершин которого образовано множеством R (N) достижимых в N разметок. Из вершины М в вершину М' ведет дуга, помеченная символом перехода t, если и только M[t > М'. На рисунке показан начальный фрагмент графа разметок рассматриваемой сети. Этот граф бесконечен, так как множество R(N) достижимых разметок бесконечно для рассматриваемой сети. Разметка М  R (N) называется тупиковой, если в сети N не существует ни одного перехода, который может сработать при этой разметке. Для рассматриваемой сети тупиковыми являются разметки (0, 2, 0), (0, 3, 0), (0,4,0),..., (0,n,0),... Легко видеть, что если выделить путь по дугам графа разметок, начинающийся в вершине М и заканчивающийся в вершине М', и выписать подряд все встречающиеся символы переходов, то полученное слово обра­зует последовательность срабатываний, ведущих oт М к М'. Множество всех слов, полученных выписыванием символов переходов вдоль путей, начинающихся в М0, образует множество последовательностей срабатыва­ний сети, или ее свободный язык. Так, язык рассматриваемой сети включает слова {, t1, t2, t1t1, t1t2, t2t3, t2t4, t1t1t1, t1t1t2, t1t2t3, t1t2t4, t2t4t1, t2t4t1t1,…. Свойства сетей Петри и их анализ Для постановок задач анализа сетей Петри прежде всего необходимо указать и формально определить те свойства сетей, которые целесообразно анализировать. Естественно, что при выборе таких свойств главную роль играет ориентация на практические задачи, возникающие при исследовании моделируемых сетями дискретных систем. Когда такие свойства выделены, ставится вопрос о возможности их автоматического распознавания в произвольных сетях Петри или в некоторых частных случаях сетей. Наконец, третий этап исследований состоит в нахождении оптимальных алгоритмов распознавания тех свойств сетей, которые ока­зываются принципиально распознаваемыми. Основные свойства сетей Петри Первое из рассматриваемых ниже свойств сетей Петри связано с ог­раниченной емкостью реальных условий реализации событий. Действи­тельно, из определения правил срабатывания переходов сети следует, что для реализации события, моделируемого некоторым переходом, доста­точно, чтобы каждое его входное место-условие содержало некоторое ко­нечное число фишек, равное кратности дуги, соединяющей его с перехо­дом. Однако при работе сети Петри общего вида некоторые ее места накапливать неограниченное число фишек (например, место р2 в последнем примере). Если интерпретировать места как накопители (буферы) данных, сигналов или деталей в моделируемых системах, то естественно потребовать, что при любом варианте функционирования этих систем не происходило бы переполнение накопителей, которые в реальных ситуациях имеют конечную, фиксированную емкость. Следующие понятия формализуют такие требования. Место р в сети Петри N= (Р, Т, F, W, М0) называется ограниченным, если существует число n такое, что для любой достижимой в сети разметки М справедливо неравенство М(р)<=n. Сеть N называется ограниченной сетью, если любое ее место ограничено. Ясно, что множество достижимых разметок R (N) конечно, если и только если N – ограниченная сеть. В нашей сети места p1 и р3 ограничены, так как каждое из них может со­держать не более одной фишки. В то же время место p2 не ограничено, и поэтому эта сеть не является ограниченной. Место р называется безопасным, если MR(N): M(р)≤1; соответственно сеть безопасна, если все ее места безопасны. Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1. Сеть на рисунке не является безопасной. Ограниченность и безопасность характеризуют емкость условий: в дискретной информационной системе, моделируемой соответствующими сетями, можно ограничить емкость накопителей, необходимых для хранения условий наступления событий. Родственным этим понятиям является понятие консервативной сети, в которой сумма фишек во всех ее местах остается постоянной при работе сети, т.е. M1, M2R(N): M1(p)=  М2(р). pP pP В консервативной сети каждый переход консервативен в том смысле, что его срабатывание не меняет число фишек в сети, т.е. t |'t| = t' - число входов в каждый переход равен числу выходов. Переход в сети может сработать при определенных условиях, связанных с разметкой его входных мест. В общем случае может оказаться, что для некоторого перехода условие его срабатывания никогда не выполняется, как бы ни функционировала сеть. Такой переход — лишний в сети, его можно исключить без ущерба для работы сети. Может случиться также, что после некоторой последовательности срабатываний переходов сети и соответствующих изменений ее разметки некоторые переходы, в том числе те, которые уже срабатывали, больше никогда не сработают, какие бы достижимых в сети разметок не возникали. Это означает, что в модели­руемых системах могут появляться ситуации, тупиковые для некоторых событий, "исключающие их из дальнейшей игры". Например, в операцион­ных системах подобные случаи имеют место при взаимных блокировках процессов (deadlocks) . Следующие определения связаны с выявлением таких ситуаций в сетях Петри. Переход t в сети Петри N = (Р, Т, F, W, М0) называется потенциально живым при разметке М  R(N), если M'R(N,M}: М' ≥ 'F{t), т.е. существует достижимая от М разметка М', при которой переход t может сработать. Если М=М0, то t называется потенциально живым в сети N. Переход t – мертвый при М, если он не является потенциально живым при М. Переход t — мертвый, если он мертв при любой достижимой в сети разметке. Переход t в сети Петри N называется живым, если MR(N), M' R(N,M): M' ≥ F(t}, т.е. переход t является потенциально живым при любой достижимой в сети N разметке. Переход t - потенциально мертвый, если существует М R (N) такая, что при любой разметке M'R(N, М} переход t не может сработать. Разметка М в этом случае называется t-тупиковой; если она t-тупиковая для всех tТ, то она является тупиковой. Если М – тупиковая разметка, то R (N, М) = {М. Сеть называется живой, если все ее переходы живы. В сети на рисунке все переходы потенциально живы и все переходы потенциально мертвы, так как в ней достижима тупиковая разметка. Эта сеть не может быть живой, так как содержит потенциально мертвые переходы. Переход t называется устойчивым в сети N, если t'T-{t}, MR(N): (M ≥ 'F(t))/\(M ≥ 'F(t')) => (M ≥ 'F(t) + 'F(t')), т.е. если переход t может сработать, то никакой другой переход не может, сработав, лишить его этой возможности. Сеть N устойчива, если все ее пе­реходы устойчивы. В нашем примере устойчив только переход t2. Сеть не устойчива. Конечная цель специальной теории сетей Петри - автоматический анализ свойств сетей, их автоматические синтез и преобразования, на основании чего могут быть построены практические алгоритмы анализа, синтеза и преобразований дискретных систем, моделируемых сетями. В частности, полезно найти алгоритмы, с помощью которых для любой предъявленной сети можно установить, обладает ли она интересующим нас свойством – является ли она ограниченной, живой, устойчивой и т.п. В первую очередь нужно выяснить существование таких алгоритмов. Эти вопросы формули­руются как массовые алгоритмические проблемы для сетей: проблема ограниченности (существует ли алгоритм, который позволяет узнать, яв­ляется ли данная сеть ограниченной), проблема потенциальной живости переходов, проблема живости сетей, проблема устойчивости, проблема безопасности. Говорят, что проблема разрешима, если соответствующий алгоритм распознавания свойств существует, в противном случае пробле­ма неразрешима. Большинство из перечисленных выше проблем связано с определением возможности достижения некоторых специальных разметок в сети (напри­мер, с достижением t-тупиковых разметок для данного перехода t), т.е. с проблемой достижимости заданной разметки. В этой проблеме ставится вопрос о существовании алгоритма, с помощью которого можно узнать для произвольной сети N и произвольной разметки М, принадлежит ли М мно­жеству R (N).Проблемы живости и достижимости эквивалентны в том смысле, что решение одной из них авто­матически решает другую.