ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
5
следующие маркировки рассматривать не требуется, так как все они
будут порождены из места первого появления дублирующей марки-
ровки в дереве.
Для сведéния дерева достижимости к конечному представлению
используется еще одно средство. Для позиций, которые увеличивают
число фишек некоторой последовательностью запусков переходов,
можно создать произвольно большое число фишек, просто повторяя
данную последовательность столько раз, сколько это нужно. Беско-
нечное число маркировок, получающихся из циклов такого типа,
обозначают с помощью специального символа
w
, который означает
«бесконечность». Таким образом, в маркировке число фишек может
быть либо неотрицательным целым, либо
w.
Алгоритм (рис. 2) начинается с определения корнем дерева
начальной маркировки, т. е. граничной вершины. До тех пор, пока
имеются граничные вершины, они обрабатываются алгоритмом.
Пусть
х —
граничная вершина, которую необходимо обработать.
Если в дереве имеется другая вершина
у
, не являющаяся граничной, и
с ней связана та же маркировка, т. е. μ[
х
] = μ[
у
], то вершина
х
— дуб-
лирующая.
Если для маркировки μ[
x
] ни один из переходов не разрешен (т. е.
значение δ(μ[
x
],
t
j
]) не определено для всех
t
j
∈
Т
), то
х
— терминаль-
ная вершина.
Для всякого перехода
t
j
∈
T
, разрешенного в μ[
x
] (т. е. δ(μ[
x
],
t
j
определено), необходимо создать новую вершину
z
дерева достижи-
мости. Маркировка μ[
z
], связанная с этой вершиной, определяется
для каждой позиции
p
i
следующим образом.
Если μ[
x
]
i
=
w
, то μ[
z
]
i
=
w
. Если на пути от корневой вершины к
х
существует вершина
у
с μ[
у
] < δ(μ[
x
],
t
j
) и μ[
y
]
i
< δ(μ[
x
],
t
j
)
i
, то μ[
z
]
i
=
=
w
. В противном случае μ[
z
]
i
= δ(μ[
х
],
t
j
)
i
.
Дуга, помеченная как
t
j
, направлена от вершины
х
к вершине
z
.
Вершина
х
переопределяется как внутренняя, вершина
z
становится
граничной. Когда все вершины дерева становятся терминальными,
дублирующими или внутренними, алгоритм останавливается [3].
Тупиковым состоянием или взаимоблокировкой называется такая
ситуация, когда каждый из множества процессов ожидает событие,
которое может вызвать только другой процесс из этого множества.
Условие взаимоблокировки может возникнуть в любой системе с не-
сколькими потоками. Тупиковая ситуация в терминах сетей Петри
подразумевает наличие тупиковой маркировки, при которой ни один
из переходов не является разрешенным. Однако фактическое тупико-
вое состояние сети не всегда означает взаимоблокировку в программе.
По завершении работы алгоритма сеть, в которой формализован
данный алгоритм, описывается так называемой тупиковой маркиров-
кой. Необходимо различать ситуации корректного завершения рабо-
ты сети от тупиковой ситуации. Для этого подразделяют позиции се-
ти на два типа: простые и конечные.
1,2,3,4 6,7,8,9,10