ГЛАВА 4. АНАЛИЗ СЕТЕЙ ПЕТРИ

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

Однако само моделирование малополезно. Необходимо провести анализ моделируемой системы. Этот анализ, можно надеяться, приведет к глубокому проникновению в поведение моделируемой системы. Таким образом, мы подошли к необходимости рассмотрения методов анализа сетей Петри. Несколько методов анализа уже разработано, однако в области анализа сетей Петри существует еще много проблем. Для того чтобы лучше оценить разработанные методы анализа, рассмотрим прежде всего типы задач, которые требуют решения. Цель анализа сети Петри — получение ответа на вопрос о конкретной сети Петри. Какие же вопросы о сети Петри можно задать?

4.1. Задачи анализа сетей Петри

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

4.1.1. Безопасность

Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, — безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1. Сеть Петри безопасна, если безопасны все позиции сети.

Определение 4.1. Позиция сети Петри с начальной маркировкой является безопасной, если для любой Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно или 1. Следовательно, позицию можно реализовать одним триггером.

В первоначальном определении сети Петри были безопасны, поскольку переход не мог быть запущен, если не все из выходных

позиций были пусты (а кратные дуги не были разрешены). Это объяснялось интерпретацией позиции как условия. Условие, будучи логическим высказыванием, либо истинно (представляется фишкой в позиции), либо ложно (представляется отсутствием фишки); кратные фишки не имеют никакой интерпретации. Таким образом, если интерпретировать сети как условия и события, маркировка каждой позиции должна быть безопасной.

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

Цель введения этой новой позиции представить условие пуста». Следовательно, дополнительны; имеет фишку, только если не имеет фишки и наоборот. Любой переход,

Рис. 4.1. Сеть Петри, не являющаяся безопасной.

Рис. 4.2. Безопасная сеть Петри, эквивалентная сети, приведенной на рис. 4.1.

удаляющий фишку из должен помещать фишку в а всякий переход, удаляющий фишку из должен помещать фишку в Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в либо в допускаем, что начальная маркировка безопасна.) Заметим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной. Простая сеть Петри на рис. 4.1 преобразована в безопасную, как показано на рис. 4.2.

4.1.2. Ограниченность

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

Определение 4.2. Позиция сети Петри с начальной маркировкой является -безопасной, если для всех -безопасная позиция называется просто безопасной. Заметим, что граница по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция может быть -безопасной, тогда как позиция -безопасной). Однако, если позиция -безопасна, то она также и -безопасна для всех Поскольку число позиций конечно, можно выбрать равное максимуму из границ каждой позиции, и определить сеть Петри -безопасной, если каждая позиция сети -безопасна.

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

4.1.3. Сохранение

Сети Петри можно использовать для моделирования систем распределения ресурсов. Например, сеть Петри может моделировать запросы, распределения и освобождения устройств ввода/вывода в вычислительной системе. В этих системах некоторые фишки могут представлять ресурсы. Группа из трех построчно печатающих устройств представляется позицией, имеющей в начальной маркировке три фишки. Запрос построчно-печатающего устройства — это переход, для которого данная позиция является входной; затем устройство освобождается переходом, для которого позиция построчно печатающих устройств является выходной.

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

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

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

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

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

(кликните для просмотра скана)

Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания определяет вес для каждой позиции

Определение 4.4. Сеть Петри с начальной маркировкой называется сохраняющей по отношению к вектору взвешивания если для всех

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

Сеть Петри с рис. 4.3 является поэтому сохраняющей, поскольку она сохраняющая по отношению к (1, 1, 2, 2, 1). Сеть Петри с рис. 4.5 не является сохраняющей.

Рис. 4.5. Несохраняющая сеть Петри.

Рис. 4.6. Распределение ресурсов для случая двух процессов и двух ресурсов (q (моделируется ) и (моделируется ).

4.1.4. Активность

Причиной рассмотрения сохранения в сети Петри было распределение ресурсов в операционной системе ЭВМ. Другая задача, которая может возникнуть при распределении ресурсов вычислительной системы — тупики. Тупики служат предметом многих исследований в области вычислительной техники [119]. Лучше всего иллюстрирует задачу простой пример. Рассмотрим систему, включающую два различных ресурса и два процесса Если оба процесса нуждаются в обоих ресурсах, им необходимо будет совместно использовать ресурсы. Для выполнения этого потребуем, чтобы каждый процесс запрашивал ресурс, а затем освобождал его. Теперь предположим, что процесс а сначала запрашивает ресурс затем ресурс наконец, освобождает и Процесс (работает аналогично, но сначала запрашивает а затем Сеть Петри на рис. 4.6 иллюстрирует два процесса и распределение ресурсов между ними.

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

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

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

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

Уровень 1: Переход обладает активностью уровня 1, если он потенциально запустим, т. е. если существует такая что разрешен в

Уровень 2: Переход обладает активностью уровня 2, если для всякого целого существует последовательность запусков, в которой присутствует по крайней мере раз.

Уровень 3: Переход обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой присутствует неограниченно часто.

Уровень 4: Переход обладает активностью уровня 4, если для всякой существует такая последовательность запусков что разрешен в

Переход, обладающий активностью уровня 0, называется пассивным. Переход, обладающий активностью уровня 4, называется активным. Сеть Петри обладает активностью уровня если каждый ее переход обладает активностью уровня

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

запусков перехода Если мы хотим запустить пять раз, мы запускаем пять раз затем и после этого пять раз Однако, как только запустится должен быть запущен до того, как будет запущен число возможных запусков станет фиксированным. Следовательно, обладает активностью уровня 2, но не уровня 3. С другой стороны, переход можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится больше запустить будет нельзя.

Рис. 4.7. Сеть Петри, иллюстрирующая различные уровни активности.

4.1.5. Достижимость и локрываемость

Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок. Задача достижимости является, по-видимому, наиболее простой (для формулировки).

Определение 4.5. Задача достижимости. Для данной сети Петри С с маркировкой и маркировки определить:

Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости. Например, для сети Петри с рис. 4.6 тупик может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

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

(кликните для просмотра скана)

Определение 4.6. Задача покрываемости Для данной сети Петри С с начальной маркировкой и маркировки определить, существует ли такая достижимая маркировка что

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

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

4.1.6. Последовательности запусков

Другой, предложенный к анализу подход основан не на позициях, а на последовательностях запусков переходов, т. е. связан с активностью, поскольку уместен вопрос: может ли переход быть запущен (иначе, не является ли он пассивным)? В более общем случае можно потребовать определить, возможна ли заданная последовательность запусков переходов или возможна ли какая-либо последовательность из множества последовательностей запусков. В сети Петри на рис. 4.8, например, взаимное исключение было бы нарушенным, если бы могла осуществиться последовательность или или, более общо, если бы могла возникнуть последовательность где произвольная последовательность запусков, не включающая Эти вопросы анализа приводят к понятию языков сетей Петри и будут исследованы более детально в гл. 6.

4.1.7. Задачи эквивалентности и подмножества

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

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

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