Пример использования сети Петри при анализе состояний дедлока.

Задача о конечности функционирования сети Петри

Обратимость и базовое состояние.

Активность.

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

Сети Петри обратима, если для любой маркировки М из R(M0) маркировка М0 достижима от М. Иными словами, в обратимой сети всегда можно вернуться к начальной маркировке (состоянию). Во многих задачах необязательно возвращаться в начальное состояние, но достаточно иметь возможность вернуться в базовое состояние. Поэтому условие обратимости можно ослабить и определить понятие базового состояния. Маркировка М' называется базовым состоянием, если она достижима от любой маркировки М из R(M0).

Одна из основных проблем в теории сетей Петри - задача о конечности функционирования сети (о достижении тупиковой разметки).

Суть проблемы состоит в ответе на вопрос для данной конкретной сети - существует ли такая последовательность срабатывания переходов, которая приводит сеть к тупиковой разметке (т.е. разметке, при которой ни один переход не может сработать)?

Более того, анализ сетей позволяет утверждать, что ненкоторые сети всегда приходят к тупиковой разметке. Это математическое утверждение (теорема!) может быть строго доказано.

Заметим, что хотя некоторые сети обязательно останавливается, т.е. достигают тупиковой разметки, но сами эти тупиковые разметки могут быть различны.

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

Инструментальные средства моделирования с помощью сетей Петри позволяют запустить сеть Петри в работу (провести имитационное моделирование) и посмотреть, достигнет лисеть тупиковой разметки или нет.

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

Рассмотрим пример на рис. 6. Сеть А определяет циклическое неограниченное срабатывание переходов t1, t2, t3. При срабатывании переходы t2 и t3 потребляют единицу ресурса из места р3 каждый. Можно представить себе для определенности, что место р3 содержит два участка памяти (буферы), которые операционная система может динамически выделять программе по ее запросу. Пока процесс, управляемый сетью А, выполняется один, ситуации дедлока не возникает. Но если появляется идентичный процесс, выполняющийся параллельно А и управляемый сетью В (рис. 6), тогда возникает конкуренция за ресурс в месте р3.

Рис 6. Пример сети Петри, моделирующей состояние системы без дедлока (а) и с дедлоком (б).

Ситуация дедлока возникает при такой последовательности срабатываний переходов сети: t1, t4, t2, t5. И в этом состоянии имеем дедлок: ни один переход не может сработать. Однако сеть будет нормально функционировать, если в позиции p1 оставить одну фишку, т.е. разрешить выполняться либо процессу А, либо процессу В, но не обоим одновременно.