Парадигма развития науки (стр. 15 )

Для установления того, является ли сеть Петри сохраняющей по отношению к некоторому вектору взвешивания W = (w1, w2, …, wn), необходимо решить следующую систему линейных уравнений с огра­ничениями :

где k - число вершин дерева достижимости, которым соответствуют различные маркировки. (Очевидно, что если имеется μj (рi) =ω, то wi = 0.)

Возможность решения задач активности и достижимости ограничена существованием символа ω, скрывающего конкретную информацию о числе фишек. Например, если в сеть Петри, изображенную на рис. 19.14,б, ввести две дуги (t1, p2), (р2, t2), то полученная сеть Петри будет иметь то же дерево достижимости, что и первоначальная. При этом в новой сети Петри в позиции р2 может быть только четное число фишек, тогда как в первоначальной сети — любое, т. е. множе­ства достижимости этих сетей Петри не совпадают. Можно привести разные сети с различными свойствами активности, но имеющие одно дерево достижимости.

Тем не менее, хотя дерево достижимости и не дает полной инфор­мации о свойствах достижимости и активности, в некоторых случаях оно позволяет ответить на вопросы по достижимости и активности. Например, если в нем имеется терминальная вершина, то сеть Петри не активна. При решении задачи достижимости может оказаться, что маркировка μ' присутствует в дереве достижимости (положительный ответ) или что маркировка μ' не покрывается никакой вершиной дерева достижимости, т. е. μ" μ для всех вершин μ' (отрицательный ответ).

Другой подход к анализу сетей Петри называется матричным и основан на их матричном представлении. Введем матрицы D- и D+, столбцам которых соответствуют позиции, строкам — переходы, и

D-(j, i) = # (рi, I(tj)), D+ (j, i) = # (рi, O(tj)). Пусть e(j) - вектор-строка, компоненты которого соответствуют переходам и все равны нулю, за исключением j-й, которая равна 1. Тогда переход tj разрешен, когда μ≥e(j) ·D- (μ рассматривается как вектор), а результатом запуска tj из μ является

μ' = μ - е(j)D- + е (j)D+ = μ + е (j) · (D+ - D-) = μ + e (j) · D,

где D = D+ — D- — составная матрица изменений.

Маркировка μ', получающаяся из μ в результате запуска последо­вательности , определяется как

где f(σ) = е (j1) + ... + е (jk) — вектор запуска, i-я компонента которого равна числу запусков tj в σ.

Если маркированная сеть Петри является сохраняющей по отноше­нию к некоторому вектору взвешивания W (W — вектор-столбец), то μW= μ'W для любой μ' = R(C, μ). Так как μ' = μ +f(σ)D, то f(σ)D W = 0. Поскольку это верно для всех f(σ), имеем DW=0. Следователь­но, сеть Петри является сохраняющей по отношению к некоторому вектору взвешивания тогда и только тогда, когда имеется такой вектор W, что DW=0. Это уравнение позволяет отыскать и сам вектор взвешивания W.

Если маркировка μ' достижима из начальной маркировки μ сети Петри, то должно существовать целое неотрицательное решение урав­нения μ' = μ + xD, решением которого будет х = f(σ).

Исследуем задачу достижимости для сети Петри, изображенной на рис. 19.13, б, с начальной маркировкой (1, 0, 0, 0) для маркировки

μ' = (0, 2, 1, 2). Уравнение μ' = μ + xD принимает вид

и имеет решение х = (4, 2, 1, 0), соответствующее последовательности запусков переходов t1t1t1t1t3t2t2.

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

Установлено, что задачи достижимости и актив­ности эквивалентны, но неизвестно, разрешимы ли они вообще, т. е. нет ни алгоритма, позволяющего решить эти задачи, ни доказатель­ства его отсутствия.

Рассмотрим применение методов анализа сетей Петри, моделирую­щих практические системы научных исследований.

Специализированная система научных исследований для реализации итерационных параллельных исследовательских процессов состоит из совокупности процессорных элементов (ПЭ) и модулей памяти (памяти данных (МПД) и памяти команд (МПК)), связанных в кольцо (рис. 19.15).

Рис. 19.15

ПЭ работает в двух режимах. В первом случае он захватывает оба смежных МПД, используя левый для извлечения исходных данных новой итерации, правый - для выборки результатов предыдущей итерации. По завершении итерации он помещает результат в правый МПД и освобождает оба МПД. В другом режиме ПЭ работает с внутренними данными. Режим указывается командой, считываемой из МПК. Рассмотрим два варианта реализации устройств управления ПЭ. В первом варианте захват МПД при осуществлении итерации производится последовательно. ПЭ может находиться в следующих состояниях: «обработка внутренних данных» (S1), «захвачен левый МПД» (S2), «захвачен правый МПД» (S3), «захвачены оба МПД, обработка данных очередной итерации» (S4). МПД может быть либо свободным, либо захваченным. Событиями будем считать захват и освобожде­ние МПД. Этот вариант работы представляется сетью Петри, в которой каждому ПЭ соответствуют четыре позиции, реализующие описанные условия, а каждому МПД — позиция (фишка, в которой означает, что МПД свободен) (рис. 19.16).

Рис. 19.16

Можно убедиться, что дерево достижимости этой сети Петри со­держит две терминальные маркировки: μ1={S12,S22,S32} и μ2={S13,S23,S33}, представляющие ситуации, когда каждый ПЭ захватывает левый и правый МПД соответственно. Это означает, что сеть Петри не активна, т. е. в системе научных исследований возможны тупиковые ситуации. При другом варианте работы системы научных исследований ПЭ осуществляют только одно­временный захват смежных МПД (если он возможен). В этом случае каждому ПЭ соответствуют только условия S1 и S4 (рис. 19.17).

Рис. 19.17.

Дерево достижимости (рис. 19.18) не содержит терминальных маркировок, сеть Петри активна.

Рис. 19.18.

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

Решением его является W=(1, 1, 1, 1, 3, 1, 3, 1, 3). Действительно, позиции р5, р7, р9 представляют условия, связанные с тремя устройствами, остальные по­зиции — условия, которые связаны с одним устройством. Таким образом, сеть Петри обладает основными необходимыми свойствами, что обеспечивает работоспособность второго варианта.

Моделирования реальных систем научных исследований приводят к различным доопределениям и модификациям сетей Петри. В основном эти моди­фикации связаны с изменением правила запуска переходов.

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

Рис. 19.19

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