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

Каждое динамическое св-во порождает задачу анализа: «Есть это св-во у сети, или нет?»

1. Безопасность.СП безопасна если число фишек в любой её позиции никогда не превышает 1:p_iPμR(C,μ⁰) [μ(p_i) ≤ 1 ]

2. Ограниченность.СП наз-тсяk-ограниченной, если число фишек в любой её позиции никогда не превышаетk:p_iPμR(C,μ⁰) [μ(p_i) ≤k]. СП наз-тсяограниченной, если онаk-ограничена для некогоk.

//Свойство безопасности – частный случай свойства ограниченности.

3. Строгая консервативность. Количество фишек в сети постоянное :μR(C,μ⁰) [μ(p_i) =μ⁰(p_i) ] Это очень сильное ограничение. Из св-ва строгой консервативности следует, что число входов в каждый переход должно равняться числу выходов из него. Для «смягчения» этого св-ва можно ввести понятиевзвешиванияфишек (это делается, потому что фишка может представлять как один ресурс, так и несколько). Взвешенная сумма всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0. Фишка определяется её позицией в сети. Все фишки неразличимы. Следовательно, веса связываются с каждой позицией сети.

Вектор взвешивания f: P → Nⁿ. Этот вектор определяет вес для каждой позиции. (n = |P|)

μR(C,μ⁰)fNⁿ[f_i*μ(p_i) =f_i*μ⁰(p_i) ] – простоконсервативность.

/* Строго консервативная сеть явл. консервативной по отношению к вектору (1, 1, …, 1). Так что это частный случай консервативности. */

Причина рассмотрения св-ва консервативности– распределение ресурсов в ОС ЭВМ: нам бы хотелось показать, что фишки, представляющие ресурсы, никогда не создаются и не уничтожаются; простейший способ сделать это – потребовать, чтоб общее число фишек в сети оставалось постоянным, что мы и делаем, вводя св-во строгой консервативности.

4.Активность. СП активна, если в ней нет тупиковых переходов (т.е. переходов, которые никогда нельзя запустить).

Причина рассмотрения активности– возможность появления тупиков при рассмотрении ресурсов вычислительной системы.

5. Задача достижимости.Состоит в том, чтобы определить для данной СП с маркировкой, принадлежит ли некая маркировка’множеству достижимомтиR(C, ). Это, пожалуй, основная задача анализа СП, т.к. многие другие задачи можно сформулировать через неё (например, для некоторой СП тупик может возникнуть, если достижима некоторая определённая маркировка).