Достижимость и покрываемость сетей Петри. Пример.

Теорема Задача достижимости сводится к задаче активности.

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

Причиной рассмотрения сохранения в сети Петри было распре­деление ресурсов в операционной системе ЭВМ. Другая задача, которая может возникнуть при распределении ресурсов вычисли­тельной системы — тупики. Тупики служат предметом многих исследований в области вычислительной техники . Лучше всего иллюстрирует задачу простой пример. Рассмотрим систему, включающую два различных ресурса 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.

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

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

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

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

Для доказательства основного утверждения раздела покажем следующее.

Теорема 5.6. Задача активности одного перехода сводится к задаче достижимости.

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

где-либо в дереве запустить переход t_j. Если нельзя, то μ массивна для t_j. Проверка активности t_j в таком случае требует проверки достижимости какой-либо пассивной для t_j маркировки.

В общем случае, однако, может существовать бесконечное число пассивных для t_j маркировок и бесконечное множество маркиро­вок, в котором находятся пассивные для t_j маркировки. Заметив два свойства, сведем множество маркировок, которые необходимо проверить для достижимости, к конечному числу. Во-первых, если маркировка μ пассивна для t_j, то и любая маркировка μ' μ пас­сивна для t_j. (Любая последовательность запусков, возможная из μ', возможна также из μ, поэтому если μ' может привести к запуску t_j , то это может и μ.) Во-вторых, маркировки некоторых позиций не будут влиять на пассивность для t_j данной маркировки, поэтому маркировки этих позиций являются «несущественными», они могут быть произвольными. Заимствуя прием из построения дерева дости­жимости, заменим «несущественные» компоненты на ω, показывая, что в этих позициях может быть произвольно большое число фишек, не влияющих на пассивность маркировки для t_j. Теперь, поскольку любая μ' μ пассивна для t_j, если μ пассивна для t_j, нам не нужно рассматривать позиции p_i с μ(p_i)=. Это означает, что мы приме­няем задачу достижимости подмаркировки с P^’ = P_i |μ(P_i)ω}

Рассмотрим в качестве примера сеть Петри на рис. 5.7. Марки­ровки (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3),... являются пассивными для t₂ , но их можно представить конечным образом множеством {(2, 0), (1, 0), (0, ω)}.

Хэк показал, что для сети Петри С существует такое конечное множество D_t маркировок (расширенных, т. е. включающих ω), что С активна тогда и только тогда, когда никакая марки­ровка из D_t недостижима. Если маркировка из D_t содержит ω, тогда подразумевается достижимость подмаркировки.

Более того, D_t можно эффективно вычислять. Поскольку D_t конечно, не- ω -компоненты имеют верхнюю границу b. Граница b определяется как такое наименьшее число, что если пассивна для t_j любая маркировка μ, такая, что μ(p_i) b + 1 для всех p_i то является пассивной для t_j и подмаркировка μ', такая, что μ'(p_i) = μ(p_i), если μ(р_i) < b, и μ'(p_i) = ω, если μ(р_i) = b + 1. При таком определении b можно построить D_t следующим образом.

Вычислить b. Начать с b = 0, увеличивать b до тех пор, пока не окажется, что b удовлетворяет описанному определению границы. Проверка каждого b требует проверки всех (b + 2)n маркировок с компонентами, меньшими или равными b+1.

Вычислить D_t проверкой всех маркировок и подмаркировок с компонентами, не превышающими b или равными ω. D_t — это множество пассивных для t_j маркировок из множества (b + 2)n маркировок.

Построив D_t, можно рассматривать задачу достижимости под­маркировки для каждого элемента D_t. Если какой-либо элемент D_t достижим из начальной маркировки, сеть Петри неактивна, если же никакой элемент D_t недостижим - сеть Петри активна.

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

На рис. 3.33 иллюстрируется решение задачи в том случае, когда количество процессов чтения ограничено величиной n. Если в системе количество процессов чтения не ограничено, то только n процессов могут выполняться в одно и то же время.

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

ограниченному количеству процессов читать одновременно.

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

вычитается. Это легко моделируется позицией, в которой количество фишек равно количеству процессов чтения. Однако, для того, чтобы предоставить процессу записи возможность приступить к записи, необходимо, чтобы счетчик был нулевым, т. е. соответствующая позиция была бы пустой. В сетях Петри нет механизма, который бы осуществлял проверку на нуль неограни­ченной позиции [1]К Таким образом, оказывается, что задача о чтении/записи с неограниченным числом процессов чтения не может быть решена с помощью сетей Петри. Это первый случай, когда мы столк­нулись с тем, что сети Петри не способны моделировать все системы.

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

Определение 4.5. Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ’ определить: μ' R(C, μ)?

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

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

μ "пок­рывает маркировку μ,, если μ" μ'.

ОпределениеЗадача покрываемости. Для данной сети Петри С с начальной маркировкой μ и маркировки μ.' определить, сущест­вует ли такая достижимая маркировка μ" R(C, μ), что μ" μ'.

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

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

Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемос­ти мы хотим для данной маркировки μ' определить, достижима ли маркировка μ" μ'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево дости­жимости. Затем ищем любую вершину х с μ[х] μ'. Если такой вершины не существует, маркировка р' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую Маркировку, покрывающую μ'.

Путь от корня к покрывающей маркировке определяет последо­вательность переходов, которые приводят из начальной маркиров­ки к покрывающей маркировке, а маркировка, связанная с этой вершиной, определяет покрывающую маркировку. Символ (о вновь должен рассматриваться как обозначение бесконечного множества значений. Если компонента покрывающей маркировки — μ , то в пути от корня к покрывающей маркировке имеется «цикл». Для увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточное число раз повторить этот цикл.

Заметим, что, если несколько компонент покрывающей марки­ровки равны w, между изменениями маркировки, получающимися в результате прохождения циклов, возможна взаимосвязь. Рассмот­рим сеть Петри на рис. 4.18 и ее дерево достижимости, показанное на рис. 4.19. Согласно проведенному анализу, маркировка (0, 14, 1, 7) покрывается в множестве достижимости. Путь, порождающий покрывающую маркировку, состоит из некоторого числа переходов t₁, за которыми следует переход t₂, после которого уже следует некото­рое число переходов t₃. Задача заключается в определении того, сколько раз нужно запустить переходы t₁ и t₃. Так как мы хотим иметь в позиции р₁ 14 фишек, a t₁ помещает в р₂ одну фишку, попытаемся

выполнить 14 t₁. Однако нам необходимо выполнить 7t₃, а каждый за­пуск t₃ удаляет из р₂ фишку, поэтому в действительности необходимо выполнить не менее 21 t₁ затем t₂ и после этого не менее 7t₃ (выпол­нить t₃ такое число раз, чтобы в позиции р₂ осталось не менее 14 фишек). Карп и Миллер предложили алгоритм, определяю­щий минимальное число запусков переходов, необходимых для покрытия дайной маркировки.