Сохранение сетей Петри. P- и V- системы. Пример.

Ограниченность сетей Петри. Задача об обедающих мудрецах.

Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое k, что число фишек в любой позиции не может превысить k. Оба этих свойства можно проверить с помощью дерева достижимо­сти. Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в ее дереве достижимости. Присутствие символа ω в дереве достижимости означает, что число фишек потенциально не ограничено; существует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая ко­личество фишек до произвольно большого числа. Таким образом, если имеется символ ω, сеть неограниченна. Кроме того, поло­жение символа ω показывает, какие позиции

Обратное утверждение также является верным, если сеть Петри неограниченна, то число достижимых маркировок бесконечно. По­скольку дерево достижимости конечно, бесконечное число дости­жимых маркировок отражает присутствие символа ω.

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

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций равна (1), сеть безопасна.

На рис. 4.17 демонстрируется использование дерева достижи­мости для определения ограниченности.

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

Задача об обедающих мудрецах была предложена Дейкстрой в и связана с пятью мудрецами, которые попеременно то думали, то ели. Мудрецы сидят за большим круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Однако для приема китайской пищи необходимо две палочки, следовательно, каждый мудрец должен взять палочку слева и палочку справа: проблема, конечно, заключается в том, что если ' все мудрецы возьмут палочки слева и затем будут ждать, когда освободятся палочки с правой стороны, то они будут ждать вечно и умрут от голода (состояние тупика).

На рис. 3.32 показано решение этой задачи с помощью сети Петри. Позиции С₁,…,C₅ представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной мар­кировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями M_i и E_i для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе па­лочки (слева и справа) должны быть свободны. Это легко модели­руется сетью Петри.

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

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

Определение 4.3. Сеть Петри С — (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ' R(С, μ)

μ'(pi)= μ (pi)

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

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

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

Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой пози­цией сети. Вектор взвешивания ω =( ω ₁, ω ₂,…, ω_n) определяет вес ω_i для каждой позиции p_i P.

ОпределениеСеть Петри С — (Р, Т, I, О) с начальной мар­кировкой μ. называется сохраняющей по отношению к вектору взвешивания ω, ω=( ω ₁, ω ₂,…, ω _n), n=|P|, ω _i O , если для всех μ, R(С, μ.)

ω _i . μ' (p_i) =ω_i . μ' (p_i) .

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

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

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

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

При оценке сохранения необходимо быть внимательным с сим­волом ω. Если маркировка имеет ω в качестве маркировки позиции p_i, тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Напомним, что символ ω представляет бес­конечное множество значений. Так как все веса неотрицательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важно), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различающихся в своей со-компоненте. Следовательно, если ка­кая-либо маркировка с ненулевым весом равна ω, сеть — несохра­няющая.

Эти рассуждения относятся к сохранению по отношению к опре­деленному взвешиванию. Сеть Петри является сохраняющей, если она сохраняющая по отношению к некоторому вектору ω, ω_i 0. Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов ω (если он существует). Заметим, прежде всего, что для того, чтобы сеть Петри была сохраняющей по отношению к положитель­ному вектору весов, она должна быть ограниченной. Как было указано выше, неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. (Если мы хотим допустить нулевые компоненты, нужно просто установить веса всех неограниченных позиций равными нулю и рассматривать после этого только оставшиеся компоненты.) Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее s, и вектор весов ω = (ω₁ , ω ₂, .... , ω_n). Для каждой маркировки μ[x] дерева достижимости имеем

ω₁ . μ[x]1 + ω₂ . μ[x]2+…+ ω_n . μ[x]n=S

Это равенство определяет для k вершин дерева достижимости сово­купность из k линейных уравнений с n + 1 неизвестными. Добавим к ним ограничения: ω_i 0, i = 1, n, в результате чего опреде­лим ограничения для вектора весов.

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

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

Большинство задач синхронизации не могут быть решены непо­средственно сетями Петри, но разрешимы скорее на основе извест­ных механизмов синхронизации. В частности, одним из самых по­пулярных механизмов синхронизации являются Р- и V-операции Над семафорами, впервые определенные Дейкстрой . Семафор — -Это элемент данных, который может принимать только неотрицатель­ные целые значения. V-операция увеличивает значение на 1, а Р­ операция уменьшает его на 1. Р-операцию можно применять только в том случае, когда значение семафора останется в результате не­отрицательным; если же значение семафора равно 0, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит V-операцию. Р- и V-операции определены как примитивные, т. е. никакая другая операция не может изменять значение сема­фора одновременно с ними.

Такие операции легко моделируются сетью Петри, как пока­зано на рис. 3.34. Каждый семафор моделируется позицией, коли­чество фишек в позиции показывает значение семафора. Р-опера­ция использует позицию семафора в качестве входа, V-операция — в качестве выхода.

Преимущество этого заключается в том, что многие системы про­ектируются и описываются с помощью Р - и V-операций.

Напри­мер, в операционной системе Venus Р- и V-операции являются основным механизмом связи между процессами. Такие системы, следовательно, можно промоделировать сетями Петри.