Ограниченность сетей Петри. Задача об обедающих мудрецах

Ограниченность сетей Петри. Задача об обедающих мудрецах.

Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое k, что число фишек в любой позиции не может превысить k. Оба этих свойства можно проверить с помощью дерева достижимо­сти. Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в ее дереве достижимости. Присутствие символа ω в дереве достижимости означает, что число фишек потенциально не ограничено; существует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая ко­личество фишек до произвольно большого числа. Таким образом, если имеется символ ω, сеть неограниченна. Кроме того, поло­жение символа ω показывает, какие позиции

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

Если сеть Петри ограниченна и символ t₀ отсутствует в дереве достижимости, то сеть Петри представляет систему конечных сос­тояний. Дерево достижимости, по существу, является графом состоя­ний и будет содержать вершину, соответствующую всякой дости­жимой маркировке. Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых мар­кировок. Например, чтобы определить границу для заданной пози­ции, нужно построить дерево достижимости и найти наибольшее значение компоненты маркировки, соответствующей этой позиции.

Рекомендуем посмотреть лекцию "Внутренние проблемы информационных систем".

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций равна (1), сеть безопасна.

На рис. 4.17 демонстрируется использование дерева достижи­мости для определения ограниченности.

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

Задача об обедающих мудрецах была предложена Дейкстрой в  и связана с пятью мудрецами, которые попеременно то думали, то ели. Мудрецы сидят за большим круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Однако для приема китайской пищи необходимо две палочки, следовательно, каждый мудрец должен взять палочку слева и палочку справа: проблема, конечно, заключается в том, что если ' все мудрецы возьмут палочки слева и затем будут ждать, когда  освободятся палочки с правой стороны, то они будут ждать вечно и умрут от голода (состояние тупика).

На рис. 3.32 показано решение этой задачи с помощью сети Петри. Позиции С₁,…,C₅ представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной мар­кировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями M_i  и E_i для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе па­лочки (слева и справа) должны быть свободны. Это легко модели­руется сетью Петри.