Безопасность сетей Петри. Задача о взаимном исключении

Безопасность сетей Петри. Задача о взаимном исключении.

Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, — безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1. Сеть Петри безопасна, если безопасны все позиции сети.

Определение 4.1. Позиция pi  P сети Петри С= (Р, Т, I, О)

с начальной маркировкой μ является безопасной, если μ(р_i)  1 Для любой μ'  R(C, μ.). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность — очень важное свойство для устройств аппарат­ного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним Триггером.

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

Если позиция не является кратной входной или кратной выход­ной для перехода, ее можно сделать безопасной. К позиции *р_i которую необходимо сделать безопасной, добавляется новая пози­ция p'_i. Переходы, в которых p_i используется в качестве входной или выходной, модифицируются следующим образом:

Если P_i  I(t_j)   и  P_i   0(t_j), тогда добавить p'_i к 0(t_j).

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

Если P_i  0(t_j)   и  P_i   I (t_j), тогда добавить р'_i к I (t_j).

Цель введения этой новой позиции p_i — представить условие «р_i пуста». Следовательно, p_i и p_i,    дополнительны; p_i имеет фишку, только если р_i- не имеет фишки и наоборот. Любой переход, удаля-

ющий фишку из р_i должен помещать фишку в p_i, а всякий переход, удаляющий фишку из p_i, должен помещать фишку в p_i. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в либо в р_i. (Мы допускаем, что начальная маркировка безопасна.) За­метим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна О или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следова­тельно, не может быть безопасной. Простая сеть Петри на рис. 4.1 преобразована в безопасную, как показано на рис. 4.2.

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

Первый процесс считывает значение x из разделяемого объекта;

Второй процесс считывает значение х из разделяемого объекта;

Первый процесс вычисляет новое значение x/ = f(х);

Второй процесс вычисляет новое значение хn = g(x);

Рекомендуем посмотреть лекцию "Мышление, интуиция, воображение в решении задач".

Первый процесс записывает х' е разделяемый объект;

Второй процесс записывает х" в разделяемый объект, уничтожая значение х .

Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им Должно быть либо g(f(x)), либо f(g(x)). (Представьте себе, что g(x) — «снять со счета х 1000 долл.», f(x) — «поместить на счет х 1000 долл.», а процессы 1 и 2 — банковские операции.)

Для предотвращения проблем такого рода необходимо обеспе­чить механизм взаимного исключения. Взаимное исключение — это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому объекту данных. Участок кода, в котором осуществляется доступ к разделяемому объекту и который требует защиты от вмешательства других процессов, на­зывается критической секцией. Идея состоит в том, что когда про­цесс готов выполнить свою критическую секцию, он сначала ждет, пока другой процесс не выполнит свою собственную критическую секцию. Затем он «блокирует» доступ к критической секции, не давая возможности никакому другому процессу войти в свою кри­тическую секцию. Он входит в критическую секцию, выполняет ее и, выйдя из нее, освобождает ее для доступа со стороны других про­цессов.

Эта задача может быть решена сетью Петри, как показано на рис. 3.28. Позиция T представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в p₁ или в р₂ соот­ветственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в t₁, дающая раз­решение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t₁ и t₂ вступят в конфликт, и только один из них сможет запуститься. Запуск tt запретит переход t₂, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию T.