Тупиковые состояния, вызываемые разделением функциональных ресурсов

Значительная часть тупиковых состояний возникает из-за использования одних и тех же ФР процедурами параллельных подпроцессов. Рассмотрим более подробно такую ситуацию и способы ее устранения на примере сети Петри рис. 7.7, которая задает два циклических асинхронных процесса П ₁ и П ₂, разделяющих ФР С ₁ и С ₂. В начальной маркировке сети Петри содержатся метки в позициях с ₁ и с ₂, так как оба ресурса свободны, и в позициях a ₁, а ₇, поскольку оба процесса находятся в состоянии готовности. Для указания на асинхронность процессов введены внешние входные позиции b ₁, и b ₂ для переходов t ₁ и t ₇ соответственно, так что при появлении метки в позиции b ₁ (b ₂) начинается выполнение процесса П ₁ (П ₂). Если метки появляются одновременно в позициях b ₁ и b ₂, то оба процесса начинают выполняться параллельно.

Построим граф достижимых маркировок сети Петри и для наглядности изобразим его в виде решетки, горизонтальные пути которой соответствуют функционированию только подсети N ₁, т. е. развитию процесса П ₁, а вертикальные— подсети N ₂ (рис. 7.18). Вершины графа, определяющие состояние сети N, обозначим двойным индексом, первый из которых соответствует состояниям подсети N _1, а второй — подсети N ₂.

 

 

Рис. 7.18 Граф достижимых маркировок сети Петри

Начальное состояние S₀₀ является состоянием готовности процессов П ₁ и П ₂, каждый из которых начинает выполняться при его активизации, что отмечается появлением метки во внешней входной позиции сети Петри. Следует отметить, что маркировка внешних позиций не зависит от самого процесса. Эти позиции могут заполняться метками и освобождаться от них в любой момент, делая процесс активным либо пассивным. Важно только, чтобы метка во внешней входной позиции b_f перехода t_i сохранялась в течение времени, необходимого для реализации этого перехода. В отличие от внутренних входных позиций перехода t_i, метки из которых удаляются после его реализации, метка из позиции b_f не удаляется.

Активизация и выполнение процесса П ₁ (П ₂) вызывают последовательность состояний S₁₀, S₂₀, …, S₅₀ (S₀₁, S₀₂, …, S₀₅). Одновременное выполнение двух процессов соответствует остальным вершинам графа достижимых маркировок. Как видно из рис. 7.18, сеть Петри рис. 7.7 имеет 28 достижимых состояний. Нетрудно заметить, что не все эти состояния являются равноценными. В некоторых состояниях активизировано и может быть реализовано два перехода, что означает параллельное выполнение двух процессов. Другие состояния, например S₁₃, допускают развитие обоих процессов, но одновременно — только одного из них. В других состояниях активизирован только один переход, что говорит о возможности выполнения лишь одного процесса и блокировке другого (S₄₁, S₁₄). Имеется состояние (S₃₃), в котором, несмотря на наличие меток во внутренних позициях сети Петри, ни один из переходов не активизирован, т. е. ни один из процессов не может выполняться. Наличие такого множества различных состояний в графе достижимых маркировок сети Петри приводит к необходимости осуществить их классификацию, введя некоторые определения.

Состоянием блокировки S _б назовем состояние, в котором при наличии метки во внутренней позиции а_μ, являющейся входной для перехода t_i, этот переход не активизирован, т. е. число процессов, которые могут развиваться, меньше числа активных процессов. Такая блокировка процесса происходит из-за занятости необходимых ему ресурсов другими процессами, после выполнения которых ресурсы освобождаются и заблокированный процесс может выполняться.

Состояние взаимной блокировки S _в.б назовем состояние, в котором заблокировано несколько активных процессов и они не могут быть разблокированы, несмотря на развитие других процессов. Таким образом, если в состоянии S _б развивающиеся процессы освобождают ресурсы, необходимые для выполнения заблокированного процесса, то в состоянии S _в.б все ресурсы, запрашиваемые заблокированным процессом, заняты процессами этого же множества, так что развитие других процессов не выводит систему из состояния взаимной блокировки. Если в множество заблокированных процессов входят все рассматриваемые процессы, система попадает в состояние полной взаимной блокировки S_п.в.б, когда ни один из процессов не может развиваться. Очевидно, состояния S _п.в.б и S _в.б одинаково недопустимы; будем называть их тупиковыми (S _T).

Состояние сети Петри, из которого все пути графа достижимых маркировок ведут в состояние S _T, назовем предтупиковым S _П.T. Состояние S _T и все предшествующие ему состояния S _П.T объединим в одно множество Q_з, которое назовем множеством запрещенных состояний. Если в графе достижимых маркировок сети Петри имеется ребро, соединяющее вершины S_u и S_v такие, что S_v   Q_з, а S_u   Q_з, то состояние S_u назовем опасным (S _oп). Все опасные состояния образуют множество опасных состояний Q_оп. Остальные состояния являются безопасными. Состоянием конфликта (S _кн) назовем состояние, в котором запрещена одновременная реализация хотя бы одной пары активизированных переходов.

Как видно из рис. 7.18 состояние S ₃₈ является тупиковым, Q_з = { S ₂₂, S ₃₂, S ₂₃, S ₃₃}; Q_оп = { S ₁₁, S ₂₁, S ₃₁, S ₁₂, S ₁₃}.

Состояния S ₁₃ и S ₃₁ являются состояниями конфликта, а S ₄₁, S ₅₃, S ₁₄, S ₃₅ — состояниями блокировки.

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

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

Рис. 7.19

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

Для графа достижимых маркировок рассматриваемого примера состояние S ₁₁ является корнем двух опасных отрезков S ₂₁, S ₃₁ и S ₁₂, S ₁₃. Это состояние переводится в состояние конфликта введением в сеть Петри рис. 7.7 позиции а _б, являющейся входной для переходов t ₂ и t ₈. Тогда после реализации перехода t ₂ (t ₈), что соответствует развитию процесса П ₁ (П ₂), удаляется метка из позиции а _б и процесс П ₂ (П ₁) блокируется. Как видно из графа рис. 7.18 состояние S ₃₁ (S ₁₃) является последним состоянием выбранного опасного отрезка, поэтому при реализации перехода t ₄ (t ₁₀) блокировка может быть снята. Для этого позиция а _б должна быть выходной позицией переходов t ₄  и t ₁₀ (рис. 7.19). Теперь состояния S ₁₂, S ₁₃, S ₂₁, S ₃₁, которые в исходном графе были опасными, становятся безопасными состояниями блокировки, а состояние S ₁₁ — состоянием конфликта. Ясно, что при этом запрещенные состояния S ₂₂, S ₃₂, S ₂₃, S ₃₃ станут недостижимы.

Для сложной системы взаимодействующих процессов, при которой имеется несколько процессов и они неоднократно обращаются к одним и тем же ресурсам, граф достижимых маркировок может содержать не одно, а несколько множеств запрещенных состояний. Тогда для каждого множества определяются множество опасных состояний, множество опасных отрезков путей графа и корень этих опасных отрезков. Затем в сеть Петри вводится блокирующая позиция так, чтобы опасное состояние, соответствующее корню, перевести в безопасное состояние конфликта. В каждом из конфликтующих опасных отрезков определяется последнее опасное состояние и переходы, которые отмечают ребра, переводящие эти состояния в безопасные, становятся входными переходами позиции а _б. В сети Петри, которая содержит необходимое число таких блокирующих позиций, не будут возникать тупиковые состояния, связанные с использованием общих ФР процедурами параллельных подпроцессов.

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

Очевидно, все преобразования структуры УП могут производиться по согласованию с проектировщиком УА, так как иногда тупиковые состояния, например, вводятся специально для сигнализации о неисправностях в системе и т. д. Кроме того, после всех преобразований УП должен соответствовать управляемому технологическому процессу.

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

 

Вопросы и задания для самоконтроля

1. Что называют управляющим процессом?

2. Дайте понятие технологического процесса.

3. Определите разницу между параллельным и последовательным процессами.

4. Что сопоставляется с технологической операцией?

5. Перечислить основные разновидности управляющего и технологического процессов.

6. Назовите причины возникновения конкуренции процессов.

7. Перечислите основные этапы построения правильного управляющего процесса.

8. Дайте определение сети Петри.

9. Назовите основные понятия сети Петри.

10. Для чего предназначены метки в сетях Петри?

11. Чему соответствуют переход и позиция в сети Петри?

12. Перечислите основные особенности оригинальной сети Петри.

13. Перечислите основные модификации оригинальной сети Петри.

14. Отражение процедуры процессов в сетях Петри.

15. Как обозначаются функциональные и логические ресурсы в сетях Петри?

16. Назовите основные особенности представления разветвленного процесса сети Петри.

17. Перечислите основные разновидности дуг в сетях Петри.

18. Назовите основные особенности задания неавтономного управляющего процесса в сетях Петри.

19. Дайте определение графа достижимых маркировок сети Петри.

20. Обозначьте основные причины возникновения тупиковых состояний в сети Петри.

21. Перечислите основные виды состояний в графе достижимых маркировок сети Петри.

 

Тесты к разделу

 (Теоретические вопросы)

Предыдущая123456789Следующая

Поделиться:

Воспользуйтесь поиском по сайту: