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

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

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

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

Определение 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, в результате чего опреде­лим ограничения для вектора весов.

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

Люди также интересуются этой лекцией: 4.7 Исторические личности и ключевые даты.

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

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

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

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

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