4.1.4. Активность

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

Начальная маркировка помечает ресурсы q(p4) и г(р5) доступными и указывает на готовность процессов а и Ь. Одним выполнением этой сети является tiht^jt^t^, другим —    Ни одно из этих выполнений не приводит к тупику. Однако рассмотрим последовательность, которая начинается переходами іЛ, процесс а обладает ресурсом q и хочет получить г, процесс Ь обладает г и хочет получить q. Система заблокирована; никакой процесс продолжаться не может.

Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены. В сети Петри на рис. 4.6. тупик возникает, если нельзя запустить переходы іг и £5. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход t j сети Петри С называется потенциально запу- стимым в маркировке р., если существует маркировка [*' £ R(C, р,), в которой t j разрешен. Переход активен в маркировке р, если потенциально запустим во всякой маркировке из R(C, (а). Следовательно, если переход активен, то всегда возможно перевести сеть Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

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

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

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

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

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

Уровень 4: Переход tj обладает активностью уровня 4, если для всякой |/ е R(C, ц) существует такая последовательность запусков а, что tj разрешен в     а).

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

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 4.7. Переход t0 не может быть запущен никогда; он пассивен. Переход £t можно запустить точно один раз; он обладает активностью уровня 1. Переход t2 может быть запущен произвольное число раз, но это число зависит от числа

запусков перехода t3. Если мы хотим запустить t2 пять раз, мы запускаем пять раз /3, затем и после этого пять раз t2. Однако, как только запустится (/4 должен быть запущен до того, как будет запущен 12), число возможных запусков /2 станет фиксированным. Следовательно, /2 обладает активностью уровня 2, но не уровня 3. С другой стороны, переход ts можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится tt, /3 больше запустить будет нельзя.