Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

Сети Петри


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

Сеть Петри, или сеть условий/событий, есть направленный граф, состоящий из узлов двух типов - так называемых вентилей

(еще используются термины: переходы, барьеры) и ячеек (места, площадки). Ребра по мере надобности ведут от вентилей к ячейкам или от ячеек к вентилям. Ячейки загружаются логическими значениями или натуральными числами. Содержимое ячеек определяет состояние сети. В каком-либо заданном состоянии определенные вентили (множество вентилей) готовы к передаче (они могут «открываться» - путем открытия такого множества вентилей изменяется загрузка сети, т.е. содержимое ее ячеек).

Пусть дано множество T вентилей и множество Р ячеек (с Р ? Т = Ø ). Сеть Петри есть тройка (Т0, Р0, R), такая, что справедливо

Т0

Т                                                                         вентили,

Р0

 Р                                                                        ячейки,

 (Т0

х Р0) U (Р0 х Т0)                                           отношения потока.

Множества Т0

и  Р0  конечны. В таком случае сеть Петри есть бичастичный направленный граф. Граф называется бичастичным, если множество его узлов разбито на два класса и ребра могут соединять только узлы из различных классов.

Для сети Петри (Т0, Р0, R) каждое отображение

b: Р0

> N, которое ячейкам предписывает числа, означает целочисленную конкретизацию (занесение в ячейки конкретных чисел). Сети с целочисленными конкретизациями называются также сетями ячейки-вентили. Часто для некоторых ячеек устанавливаются дополнительно определенные наибольшие значения («мощность ячейки»), которые могут иметь заносимые в эти ячейки значения.

В некоторых случаях можно ограничиться сетями Петри с конкретизациями, использующими только значения 0 и 1, или соответственно false

и true. При этом рассматриваются только конкретизации вида b: Р0 > В.




В таких случаях говорят о булевских сетях Петри или сетях условия-события.

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

Для целочисленной конкретизации b  сети Петри (Т0, р0, R) непустое подмножество К
 Т0 называется готовым к передаче, если для каждой ячейки р
 р0, справедливо:

| {k
 K: (р, k)
 R}| ? b(p).

Множество К вентилей по этому определению для некоторой конкретизации готово к передаче, если в каждой ячейке р находится достаточно меток, чтобы все вентили k
 K, для которых стрелка от ячейки р ведет к вентилю k, при переключении были снабжены метками. Если для каких-то ячеек предусмотрены ограничения на помещаемые туда метки, то имеет место ограничение мощности. Множество К только тогда готово к передаче, когда проходящие через вентили метки не превосходят соответствующие максимально допустимые значения. В случае булевских сетей Петри для каждой ячейки р
 Р0

и каждого вентиля k
 K требуется выполнение следующего условия для готовности к передаче множества вентилей К
 Т:

(р, k)
 R => b(p) ^ | { k
 K: (р, k)
 R}| ? 1

и дополнительно следующего условия бесконфликтности: для каждой ячейки р
 Р0

и каждого вентиля k
 K должно иметь место

(k, р)
 R => ¬b(p) ^ | { k
 K: (k, р)
 R}| ? 1.

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

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


Т. е. должно выполняться следующее условие:

 t
 Т0, p
 P0: ¬ ((t, p)
 R ^ (p, t)
 R).

Если бы для какого-либо вентиля t это условие не выполнялось, то такой вентиль (при учете правила переключения для сети условие-событие) никогда не был бы готов к передаче.

Лемма. Пусть заданы сеть Петри и множество К вентилей со следующим дизъюнктивным разложением:

К = К1
 К2,                               К1

 К2 = Ø.

Тогда имеет место: если множество К готово к передаче для конкретизации b0 с последующей конкретизацией b, то имеется такая конкретизация b1, что справедливо: К1 готово к передаче с последующей конкретизацией b1, и К2 готово к передаче для b1 с последующей конкретизацией b.

Доказательство.

Определение готовности к передаче К влечет за собой готовность к передаче любого его подмножества К1. Для последующей конкретизации b1

при К1 для b0 подмножество К2 готово к передаче, так как К = К1
 К2 было готово к передаче для b0. Поскольку К1
 К2 = Ø, то сумма эффектов от К1 и К2 есть эффект К.

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

Для сети N = (Т0, Р0, R) рассмотрим процесс р = (Е0, ?0, ?) с маркировкой события через действия:

?: Е0 > Т0.

Для исходной конкретизации b0 и сети Петри N0 = (Т0, Р0, R) конечная структура действий р = (Е0, ?0, ?) называется ходом работы сети Петри с конечной конкретизацией b1, если р соответствует поведению сети с исходной конкретизацией b0:

b0
b1.

Это отношение между конкретизацией и процессами для заданной сети определяется следующим образом:

(1)        Пустой процесс всегда есть ход работы и не меняет конкретизации. Т.о. для пустого процесса р и любой конкретизации b справедливо следующее соотношение:



b
b.

(2)        Пусть р = (Е0, ?0, ?) - процесс с тривиальным причинным порядком, в котором различные события являются причинно независимыми.

Для процесса р справедливо следующее:

e, d
 Е0: e ?0 d
e = d.

Тогда  для конкретизации b0 и b1

отношение

b0
b1

справедливо только тогда, когда все события в р помечены по-разному и потому справедлива следующая формула:

e, d
 Е0: e ? d
 ?(e) ? ?(d),

и множество К = { ?(e): e
 Е0 } для конкретизации b0

готово к передаче и ведет к последующей конкретизации b1.

(3)        Для каждого процесса р = (Е0, ?0, ?), который не удовлетворяет условиям (1) или (2), отношение

b0
b2

справедливо только тогда, когда для каждого непустого префикс-процесса

р1 = (Е1, ?1, ?1) со свойством

р1
 р ^ p1 ? p

существует такая конкретизация b1, что для процесса р2 = р | E0\E1

справедливо следующее высказывание:

b0
b1

^ b1
b2

Это определение принимает во внимание в пункте (2) то обстоятельство, что вентили в сети Петри рассматриваются только как последовательные единицы. Параллельные события всегда маркируются различными вентилями.

а
с

b
e

Для каждого конечного процесса р и каждой конкретизации b0 через

b0
b1

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

Лемма. Если для процесса р = (Е0, ?0, ?) и конкретизации b0 и b1 справедливо высказывание

b0
b1,

то для каждого префикса р1

процесса р с множеством событий Е1 справедливо следующее высказывание: для каждого множества событий Е2, которое является минимальным относительно ?0 в Е0\Е1, справедливо, что множество { ?(e): e
 Е2} является готовым к передаче.

Доказательство. Подпроцесс в р, который состоит только из событий из Е2, для конкретизации b1 является ходом работы.

Лемма.

Если процесс р есть ход работы сети N с исходной конкретизацией b0, то каждый префикс-процесс р1
 р есть ход работы сети N с исходной конкретизацией b0.

Доказательство.


Согласно определению понятия хода работы для сети Петри процесс р есть ход работы, если любой префикс р есть ход работы.

Структура действий р = (Е0, ?0, ?) называется совершенным ходом работы сети Петри N с конкретизацией b0, если справедливо одно из следующих условий:

(1)               Множество событий E0 бесконечно, и любой конечный префикс р есть ход работы сети N с исходной конкретизацией b0.

(2)               Множество событий Е0 конечно, и р есть ход работы сети N для начальной конкретизации b0 с конечной конкретизацией b1, и для b1

не существует непустого готового к передаче множества.

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

Две сети с исходными конкретизациями называются эквивалентными

(с точки зрения их работы), если они имеют одинаковые множества совершенных ходов работы.

Лемма (линеаризация процессов). Если р есть ход работы сети Петри N с исходной конкретизацией b, то каждая линеаризация р также есть ход работы N с исходной конкретизацией b.

Доказательство.

Каждая линеаризация, по лемме линеаризации для готовых к передаче множеств, может через может через линеаризацию достичь определенных готовых к переходу множеств.

Обратное утверждение леммы не справедливо. Из множества последовательных ходов работы сети Петри нельзя сделать вывод о множестве не последовательных ходов работы.

Бесконечный ход работы р = (Е0, ?0, ?) сети Петри N с исходной конкретизацией b называется несправедливым по отношению вентиля а, если  одновременно выполняются следующие условия:

(1)        Множество {e
 Е0: ?(e) = a} событий, помеченных действием а, конечно.

(2)        Множество конечных префиксных процессов р1
 р, причем р1 = (Е1, ?1, ?1) с

{e
 Е0: ?(e) = a} = {e
 Е1: ?1(e) = a}

и

b0
b1,

причем вентиль а в b1



готов к передаче, является бесконечным.

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

Описанное понятие справедливости является лишь одним из вариантов среди многих понятий подобного рода.

Термы для описания процессов

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

Для представления систем используются языковые термы, называемые агентами. Рассмотрим следующий БНФ-синтаксис языка агентов:

<agent>::= skip

<action>

<agent>; <agent>

<agent> or <agent>

<agent> || <agent>

<agent> id

<agent id>:: <agent>

В данном случае <action> обозначает некоторый наперед заданный принятый язык для описания отдельных действий, а <agent id> - наперед заданное множество идентификаторов для агентов. С помощью этого языка агентов, как и с помощью сетей Петри, могут описываться множества процессов. Эти множества снова означают ходы работ агентов. Агент skip может выполнить только пустой процесс. Агент t1; t2 соответствует последовательной композиции процессов, описанных агентами t1 и t2.  Агент t1 or t2.в качестве множества процессов обладает объединением множеств процессов, описанных агентами t1 и t2.  Агент t1 || t2. описывает множество процессов, которое содержит параллельную композицию некоординируемых процессов, описываемых агентами t1 и t2 . Пусть t есть терм агента, в который свободно входит идентификатор агента х. Агент соответствует агенту (вызову агента) х, который характеризуется рекурсивным объявлением х == t. С помощью рекурсивно определенных агентов могут быть специфицированы бесконечные процессы.



При известных обстоятельствах необходимо использовать непоименованные вспомогательные вентили, чтобы выразить поведение агента сетью Петри.

Для каждого терма t синтаксической единицы <agent> и каждой структуры действий р = (Е0, ?0, ?) можно аналогично конкретизациям сетей Петри установить, представляет ли структура действий р возможный ход работы агента t. Это можно сделать формально с помощью определения отношения (аналогично отношениям переходов между состояниями сети Петри) t1
t2., которое свидетельствует о том, что агент t1 может выполнить процесс р и после этого ведет себя как агент t2.

Это отношение, которое устанавливает, какие ходы работы возможны для агентов и к каким агентам они ведут, определяется рекурсивно следующим образом:

(1)        Каждый агент может выполнить пустой процесс. Для пустого процесса р0 и любого агента t определим соответственно:

t
t.

(2)        Агент а, состоящий из единственного действия а, может выполнить процесс, который содержит единственное событие, помеченное действием а.

a
 skip,

(3)        Пусть р, р0, p1 и р2 - любые процессы. Агент t1 ог t2 показывает неде-терминированно поведение агента t1 или агента t3.

t1
t2 => t1 or t2 
 t3,

t2 
 t3

=> t1 or t2
 t3.

Агент t1; t2 ведет себя как агент t1 и, если t1 этим поведением переводится в skip, в заключение ведет себя как агент t2 . Соответственно определяются следующие два правила для последовательной композиции агентов:

t1 
 t3 => t1 ; t2 
 t3

; t2,

t1 
skip

^ t2 
 t3 ^ isseq(p, p1, p2) => t1 ; t2 
 t3.

Поведение агента t1 || t2 складывается параллельно из поведения t1 и t2. Если поведение обоих агентов приводит к skip, то и поведение t1 || t2 тоже приводит к skip. Агент t1 || t2

завершается, если завершается как t1, так и t2 . Соответственно определяем:

t1 
r1 ^  t2 
 r2

^ ispar(p, p1, p2, Ø) => t1 || t2 
 r1 || r2,

t1 
skip

^ t2
 skip ^ ispar(p, p1, p2, Ø) => t1 || t2 
 skip.

(4)        Для любого процесса р определим ходы работ для рекурсивных агентов с помощью следующего правила:



t[ x::t/x ] 
 t0 => x::t
 t0.

Теперь через определенное выше отношение каждому агенту можно предписать множество процессов. Процесс р называется (несовершенным) ходом работы агента t0, если существует агент t1.

t0
 t1.

Множество ходов работ является замкнутым относительно образования префиксов.

Лемма (закон разложения). Если для агентов t0, t2 и конечного процесса р справедливо высказывание

t0
t2,

то для каждого префикса р1
 р существует агент t1 такой, что

t0
t1, t1
 t2,

Доказательство - индукцией по числу событий в p1.

Закон разложения означает, что осуществляемые с помощью процессов переходы также могут быть разложены в следующие друг за другом переходы, причем эти последние осуществляются подпроцессами исходного процесса. Справедливо также и обратное утверждение.

Предложение (связывание процессов). Если для агентов t1, t2, t3

и процессов р0, p1  справедливо высказывание

t1
 t2 ^ t2 
 t3,

то существует процесс р2 такой, что t1
 t3.

Доказательство, индукцией по структурам агентов.

Агент t0 называется терминальным, если для любого агента t1

высказывание

t0
 t1

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

Процесс р называется совершенным ходом работы агента t0, если для терминального агента t1 справедливо:

t0
 t1

или же процесс р является бесконечным и каждый его префикс р1
 р является ходом работы.

Два агента называются эквивалентными,

если они обладают одинаковыми множествами совершенных ходов работы.

К анализу агентов можно поставить такие же вопросы, какие ставятся и для сетей Петри. Концепция сети Петри с конкретизациями заменяется концепцией агентов. Тем самым агенту соответствует при сетях пара (N, b), причем N представляет сеть, a b - ее конкретизацию. В случае сетей только рассматривается отношение переходов на конкретизациях, так как сеть оставляет переходы неизменными.

Для агента t0 агент t1 называется достижимым, если существует процесс р такой, что t0
 t1



Для агента, который моделирует распределенную систему или определенный ее аспект, можно выделить следующие вопросы:

1.      Какими свойствами обладает множество достижимых агентов? Является ли это множество конечным?

2.      Исключается ли для определенных действий, что будет порожден процесс, в котором оба эти действия имеют место одновременно (взаимное исключение)?

3.      Может бы быть с помощью процесса достигнут агент (отличный от skip), для которого возможны только тривиальные переходы (тупики)?

4.      Может ли быть достигнут агент (отличный от skip), исходя из которого больше не достижим никакой агент, в котором имеют место определенные действия (локальный тупик, отсутствующая живучесть)?

5.      Существуют ли бесконечные процессы, в которых одно из действий никогда не встречается (справедливость)?.

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

Координация особенно необходима, чтобы при параллельно протекающих процессах можно было исключить конфликты.

Пусть S - подмножество множества действий А. Процесс р0 = (Е0, ?0, ?0) может быть сложен из процессов р1 и р2 тем, что события, помеченные действиями из S, установлены в качестве общих событий. Тогда справедливо: ispar(p0, p1, р2, S).

Рассмотрим частный случай для установления общих событий. Множество действий А разлагается на два дизъюнктивных подмножества U и S:

·         действия множества U являются асинхронно выполняемыми действиями,



·         действия множества S являются только синхронно выполняемыми действиями.

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

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

Наряду с несинхронизируемой параллельной композицией агентов важно рассмотреть и  синхронизируемую параллельную композицию агентов. Это может происходить посредством синхронной параллельной композиции ||s, где S обозначает множество действий, которые при параллельно протекающих процессах должны выполняться синхронно.

Точное значение синхронной параллельной композиции по отношению к ходу течения процесса задается следующими правилами:

t1 
r1 ^  t2 
 r2

^ ispar(p, p1, p2, Ø) => t1 ||s t2 
 r1 || r2,

t1 
skip

^ t2
 skip ^ ispar(p, p1, p2, Ø) => t1 ||s t2 
 skip.

Эти правила являются обобщением уже рассматривавшихся правил для несинхронизируемой параллельной композиции. Здесь имеет место то, что какой-либо процесс есть ход работы агента t1 ||s t2, если он возникает через параллельную композицию ходов работы t1  и t2, причем в параллельной композиции этих процессов события, помеченные действиями из S, являются общими событиями. По этому определению существуют агенты, которые отличны от skip, но тем не менее являются терминальными и тем самым не могут выполнять какого-либо процесса, кроме пустого (такие агенты находятся в тупике).

Пример (тупик). Агент а ; b ||(a, b)  b ; a находится в тупике, поскольку он не может выполнять ни действия а, ни действия b.

Наряду с синхронизацией процессов относительно определенных действий над общими событиями имеет место координация параллельно выполняющихся агентов о «взаимных исключениях».


Определенные последовательности действий одного агента должны выполняться без того, чтобы параллельно происходили определенные действия другого агента, например, для избежания конфликтов между действиями. С помощью синхронной параллельной композиции t1 ||s t2, порождается процесс, который (при отсутствии возникновения тупиков) содержит определенные линеаризации ходов работы t1  и t2,  как частичных процессов. Возникают дальнейшие причинные отношения между событиями в обоих частичных процессах - это следует ввести для обеспечения взаимных исключений.

Пример (взаимное исключение через пару синхронизируемых действий). Пусть даны следующие три агента:

t1 = х1 :: а1 ; p; b1; v; х1

t2 = х2 :: а2 ; р; b2; v; х2

k = y :: p; v; y.

Предположим, что действия b1 и b2 могут конфликтовать между собой и поэтов не должны выполняться параллельно. Для агента t1 || t2 возможен ход работы, заданный с помощью следующего графа действий:

а1 -> р -> b1

-> v -> а1 -> р -> b1 -> v -> ...

а2 -> р -> b2

-> v -> а2 -> р -> b2 -> v -> ...

Этот процесс содержит пару параллельных событий, которые помечены конфликтующими действиями b1 и b2. В агенте

(t1 || t2) || {v; p}k такой ход работы исключается. Каждое выполнение действий р и v агента k совпадает с одними из действий р и v или агента t1, или агента t2, но что р и v - действия в процессах t1 и t2 не помечают каких-либо общих событий.

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

и t2. В агентах t1 и t2 заменим действие а на терм агентов Р ; a; v, причем пусть р и v - до сих пор не встречавшиеся действия в t1 и t2 . Агент с :: р; v; с  в каждом ходе работы агента по мере надобности вынуждает один из обоих агентов ti' или ti ждать с выполнением р; а; v-до тех пор, пока агент с::р; v; с снова будет готов для события, помеченного действием р.


События с действием а в t1'  или t2'  в ходах работы, описанных с помощью агента

(t1' || t2' ) || (p; v)    с :: р; v; с, полностью линейно упорядочены. При таком способе действий для обеспечения взаимных исключений возникают агенты, которые обнаруживают дополнительные возможные тупики - в случае, когда в агенте t1 или t2 в параллельных композициях действие а должно выполняться синхронно.

Лемма (взаимное исключение). Для любого агента t, в котором действие а всегда встречается в виде р; а; v и иначе действия р и v не встречаются, справедливо, что каждый из процессов, порождаемых агентом не содержит никакой пары параллельных событий, помеченных действием а.

Доказательство. Пусть р' - процесс, порождаемый агентом t'. События, которые помечены действиями р или v, образуют последовательный подпроцесс, в котором р и v чередуются. Каждому событию е, помеченному через а, может быть однозначным образом предписано натуральное число событий, которые являются причиной для е и которые помечены через v, соответственно через р. Каждому событию е, помеченное через а, можно однозначно предписать помеченное через р событие еrp(е), которое является причиной для е, а также помеченное через v событие еry(е), для которого е является причиной.


Содержание раздела