Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 15

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

Сеть Петри С = (Р, Т, 1, 0) с началыюй маркировкой р называется апрого сохранлюи/ей, если для всех м бЖС й) Х Р'(Р*)= Х Р(Р*). в~6 в1с" Строгое сохранение — это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, ~/'(/,)1 =- [0(//)~. Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Однако для более общего представления о свойстве сохранения рассмотрим рис. 4.3. Изображенная на нем сеть Петри не является строго сохраняющей, поскольку запуск перехода /, илн Гв умеш шит число фишек иа г, а запуск перехода 1, илн /4 добавит фишку к маркировке. Мы можем тем не менее преобразовать эту сеть Петри в сеть на рис. 4.4, являющуюся строго сохраняющей. Сеть Петри должна сохранять ресурсы, которые она моделирует. Однако взаимно однозначного соответствия между фишками и ресурсамн нет. Фишка может представлять и один программный счетчик нли какой-нибудь другой элемент и может представлять несколько ресурсов сразу.

Во втором случае фишка позже используется для создания кратных фишек (по одной на ресурс) путем запуска перехода с бблыьим числом выходов, чем входов. В общем следует определить взвешивание фишек, Взвешенная сумма для всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0; другим фишкам можно присвоить веса 1, 2, 3 или любое другое целое. (Допустимы рациональные веса, поскольку для определения целого взвешивания такое взвешивание можно умножить на общее кратное. Иррациональные веса не представляются необходимыми.) Глава 4 Фишка определяется ее позицией в сечи, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания гв =- (шп гаа, ..., ш„) определяет вес шч для каждой позиции ре Е Р.

Определение 4.4. Сеть Петри С = (Р, Т, 1, 0) с начальной маркировкой р называется сохраняющей по отношению к вектору взвешивания гв, ш = (гз,, ша, ..., ш„), и = 1Р), ш, ъ О, если для всех р' Е тч(С, р) Хш. р'(рч) =Хш р(р.). 4 а Строго сохраняющая сеть Печри является сохраняющей по отношению к вектору взвешивания (1, 1, ..., 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (О, О, ..., 0). Этот факт вносит в теорию некоторую нестройность, поскольку нам бы хотелось определить сеть Петри как сохраняющую, если она является сохраняющей по отношению к некоторому вектору взвешивания. Однако, так как всякая сеть Петри является сохранякацей по отношению к нулевому вектору, такое определение не является удовлетворительным.

Таким образом, сеть Петри называется сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому векчору взвешивания и > 0 (с положительными ненулевыми весами, шч > 0), Сеть Петри с рис. 4.3 является позтому сохраняющей, поскобьку она сохраняющая по отношению к (1, 1, 2, 2, 1). Сеть Петри с рис. 4.5 не является сохраняихцей. Рис. 4.5. Несохраяячочяая сеть Петри. Аяиеие сетей Петри Процесс Б Процесс а Ряс.

4.6. Распределение ресурсов для случая двух процессов (а и Ь) я двух ресурсов (о (моделируется ре) и т (моделируется ре)). 4 1.4. Активность Причиной рассмотрения сохранения в сети Петри было распределение ресурсов в операционной системе ЭВМ. Другая задача, которая может возникнуть прн распределении ресурсов вычислительной системы — тупики. Тупики служат предметом многих исследований в области вычислительной техники 1119ь Лучше всего иллюстрирует задачу простой пример.

Рассмотрнмсистему, включающую два различных ресурса д и т и,пва процесса а и Ь. Если , оба процесса нуждаются в обоих ресурсах, им необходимо будет , совместно использовать ресурсы. Для выполнения этого потребуем, чтобы каждый процесс запрашивал ресурс, а затем освобождал ", .его. Теперь предположим, что процесс а сначала запрашивает ре- ~, суре д, затем ресурс г и„наконец, освобождает и д, н г. Процесс )~ Ь работает аналогично, но сначала запрашивает г, а затем ~у.

Сеть Петри на рнс. 4.Б иллюстрирует два процесса и распределение Ресурсов между ними. Глава 4 Начальная маркировка помечает ресурсы д(р4) и г(рь) доступными и указывает на готовность процессов а и Ь. Одним выполнением этой сети является 8АГе4аГь44, другим — гАЩЩ. Ни одно нз этих выполнений не приводит к тупику. Однако рассмотрим последовательность, которая начинается переходами Гь Га: процесс а обладает ресурсом д и хочет получить г, процесс Ь обладает г и хочет получить д. Система заблокирована; никакой процесс продолжаться не может Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены.

В сети Петри на рис. 4.6. тупик возникает, если нельзя запустить переходы 4э и 1м Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход г; сети Петри С называется потенциально эапустимьья в маркировке р, если существует маркировка м' Е К(С, р), в которой г; разрешен. Переход активен в маркировке р, если потенциально запустим во всякой маркировке из Д(С, а).

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

если существует такая )ь' Е К(С, 1г), что Гх разрешен в р'. Уровень 2: Переход г 4 обладает активностью уровня 2, если для всякого целого и существует последовательность запусков, в кспорой 4~ присутствует по крайней мере и рвз. Уровень 3: Переход 4~ обладает активностью уровня 8, если существует бесконечная последовательность запусков, в которой Гг присутствует неограниченно часто. Уровень 4: Переход 44 обладает акпшвностью уровня 4, если для всякой р' б )т(С, р) существует такая последовательносп запусков о, что 14 разрешен в б(1г', а). Переход, обладающий активностью уроння О, называется пассивньих. Переход, обладающий активностью уровня 4, называется активньиэ.

Сеть Петри обладает активностью уровня г, если каждый ее переход обладает активностью уровня 1. В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 4 7. Переход 4ь не может быть запущен никогда; он пассивен. Переход 4, можно запустить точно один раз; он обладает активностью уровня 1. Переход Гэ может быть запущен произвольное число раз, но это число зависит от числа 87 Ллалиа сетей Петри запусков перехода 1а. Если мы хотим запустить га пять раз, мы запускаем пять раз га, затем 1, и после этого пять паз 1а. Однако, как только запустится 1, (1т должен быть запущен до того, как будет запущен га), число возможных запусков га станет фиксированным. Следовательно, 7а обладает активностью уровня 2, но не уровня 3.

С другой стороны, переход 1а можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится гь га больше запустить будет нельзя. Рис. 4.7. Сеть Петри, иллюетрирующаи рааличине уров- ии активности. М $ 4.1.5. Достижимость и поирываемость Большинство задач, к которым мы до снх пор обращались, касаются достижимых маркировок. Задача достижтсиастлгс являет,, ся, по-внднмому, наиболее простой (для формулировки). '( Определение 4.5. Задача досглижилостли. Для данной сети Петри С с маркировкой 1а н маркировки (а' определить: 1а' ~ К(С, р)Р Задача достижнмости, быль может, основная задача анализа е сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимостн. Например, для сети Петри с рис.

4.8 тупик может возникнуть, если достижимым является состояние (О, 1, О, О, О, О, 1, О). На рис. 4.8 показана сеть Петри, пель которой заключается в , решении задачи о взаимном исключении, — предполагается, что позиции па и р, будут взаимно исключающими. Мы хотим знать, ЯвлЯетсЯ ли какое-либо состоЯние с 1с(Ре) 1 и Р(Ра) ъ. 1 достижимым.

Эта задача аналогична достижимостн, но несколько отличается", она называется задачей покрываемостн. Маркировка р" покрывает маркировку 1', если р" ~~ р'. Рнс. 4.8. Представление сетью Петрн ерепюнняа Хамана задачи о взаимном нсключеннн г1341. Вследствне постоянного использовання позиций АО, йг, 1 а1 н ЬО онн для удобства продублнровани в графе, представляющей сеть. Все позиции, помеченные йО, являются одной позицией.

Аемие сетей Петли Определение 4.6. Задача локрыеаемости. Для данной сети Петри С с начальной маркировкой р н маркировки 1«' определить, существует ли такая достижимая маркировка р" ~ 1?(С, р), чтор ъ р'. В других возможных задачах типа достижимости могло бы игнорироваться содержимое некспорых позиций н приниматься во внимание сравнение нли покрытие содержимого нескольких важных позиций. Например, в сети Петри на рис.

4.8 наш интерес ограничен позициями р, и ре — маркировка остальных позиций не '«4 важна. Таким образом, мы можем рассматривать достижимость и покрываемосгь «по модулям множества позиций. Эти задачи называются задачами достлижимости лодмаркироеки и покрываемости лодмаркироеки. Их можно еще более усложнить требованием, определить достижимость и покрываемость для множества маркировок, придя к задачам дсстижилости множества и покрыеаемосоис множества. Однако, если множество конечно, задачи можно решить обычно многократным решением задач достижимости и покрываемости 4.!.б.