Активность сетей Петри. Задача о чтении и записи

Активность сетей Петри. Задача о чтении/записи.

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

Начальная маркировка помечает ресурсы q(p₄) и r(р₅) доступ­ными и указывает на готовность процессов a и b. Одним выполне­нием этой сети является t₁ t₂ t₃ t₄ t₅ t₆   Другим — t₄ t₅ t₆ t₁ t₂ t₃ Ни одно из этих выполнений не приводит к тупику. Однако рассмотрим после­довательность, которая начинается переходами t₁ t₄ . процесс а об­ладает ресурсом q и хочет получить r, процесс b обладает r и хочет получить q. Система заблокирована; никакой процесс продолжать­ся не может.

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

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

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

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

Рекомендуемые материалы

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

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

Уровень 4: Переход t_j обладает активностью уровня 4, если для всякой μ'  R(C, μ) существует такая последовательность запусков σ, что t_j разрешен в δ (μ, σ).

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

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 4.7. Переход t₀ не может быть за­пущен никогда; он пассивен. Переход t₁ можно запустить точно один раз; он обладает активностью уровня 1. Переход t₂ может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t₃. Если мы хотим запустить t₂ пять раз, мы запускаем пять раз t₃, затем t₁ и после этого пять раз t₂. Однако, как только запустится t₁ (t₁ должен быть запущен до того, как будет запущен t₂), число возможных запусков t₂ станет фиксированным. Следовательно, t₂ обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t₃ можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится t_{1 ,} t₃ больше запустить будет нельзя.

Задача активности одного перехода. Активен ли данный переход t_j   T?

Очевидно, что задача активности сводится к задаче активности одного перехода. Для нахождения решения задачи активности мы просто решим задачу активности одного перехода для каждого t_j  Т; если |Т| = т, то мы должны решить т задач активности од­ного перехода.

Задачу достижимости можно также свести к задаче активности. Поскольку варианты задачи достижимости эквивалентны, мы рас­смотрим задачу достижимости нуля в одной позиции. Если перед нами стоят какие-либо другие задачи достижимости, их можно свес­ти, как показано в разд. 5.2, к задаче достижимости нуля в одной позиции. Теперь, если мы хотим определить, может ли быть позиция p_i нулевой в какой-либо достижимой маркировке для сети Петри С₁ = (Р₁, Т₁, I₁, O₁) с начальной маркировкой μ₁ то построим сеть Петри С₂ = (Р₂, Т₂, I₂, O₂) с начальной маркировкой μ₂, кото­рая будет активна тогда и только тогда, когда нулевая маркировка не будет достижима из μ₁.

Сеть Петри С₂ строится из C₁ введением двух позиций r₁ и r₂ и трех переходов s₁ s₂ и s₃. Сначала модифицируем все переходы Т₁, включая r₁ в качестве входа и выхода. Начальная маркировка μ₂ будет включать фишку в r₁. Позиция r₁ — это позиция «действия», пока фишка остается в r₁, переходы Т₁ могут запускаться. Следова­тельно, любая маркировка, достижимая в С₁ достижима также и в позициях Р₁ в С₂. Определим переход S₁ так, что его входом будет T₁, а выход пуст. Это позволяет удалить фишку из r₁, запрещая запуск всех переходов в 7 и «замораживая» маркировку Р₁. (За­метим, что все переходы Т₁ находятся в конфликте и не только по определению, но и по построению могут запускаться каждый раз не более чем по одному.)

Позиция r₁ и переход s₁ позволяют сети С₁ достичь любой дости­жимой маркировки, затем запуском S₁ заморозить сеть в этой мар­кировке. Далее необходимо проверить, является ли позиция р_i нулевой. Введем новые позицию r₂ и переход s₂, имеющий в качестве входа р_i а в качестве выхода r₂. Если p_i может когда-либо стать нулевой, то этот переход не является активным. В действительнос­ти вся сеть будет пассивной, если в этой маркировке сработает пе­реход S₁. Следовательно, если pi может быть пустой, сеть не явля­ется активной. Если р_i не может быть пустой, тогда s₂ всегда мо­жет быть запущен, помещая фишку в r₂. В этом случае мы должны будем вернуть фишку в r₁ и гарантировать, что все переходы в С₂ активны. Необходима уверенность в том, что С₂ активна, даже если С₁ не является активной. Это обеспечивается переходом s₃, кото­рый «наполняет» сеть С₂ фишками, гарантируя тем самым, что, если фишка помещена в r₂, каждый переход активен. Переход s₃ в ка­честве входа имеет r₂ , а в качестве выхода все позиции С₂ (все p_i в С₁, r₁ и r₁). Эта конструкция иллюстрируется рис. 5.6.

Если Вам понравилась эта лекция, то понравится и эта - 10 Казахстан в условиях становления тоталитарной системы.

Далее, если маркировка μ с μ(р_i) = 0 достижима в R(C₁, μ₁), тогда С₂ также может достичь этой маркировки в позициях Р₁ пу­тем выполнения той же самой последовательности запусков пере­ходов. Затем можно запустить s₁, замораживая подмножество С₁. Поскольку μ(p_j) = 0, s₂ запустить нельзя и С₂ пассивна. Таким образом, если р_i может стать нулевой — С₂ неактивна.

Справедливо обратное, если С₂ неактивна, тогда должна быть

достижима маркировка μ с μ(r₂) = 0, из которой недостижимо состояние с фишкой в r₂. (Если в r₂ есть фишка, то s₃ разрешен, а повторно запуская s₃ достаточное число раз, можно разрешить лю­бой (или все) переход, т. е. сеть активна.) Если r₂ не имеет фишек и не может их получить, тогда маркировка p_i также должна быть нулевой. Таким образом, если С₂ неактивна, тогда достижима мар­кировка, в которой маркировка p_i нулевая.

На основе этой конструкции мы доказали следующую теорему.