Ограниченность дерева достижимости

Использование сетей Петри для моделирования процессов синхронизации. Задача Д.Питерсона. PERT-диаграммы и сети Петри. Примеры.

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

Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, — безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 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.

Введение параллелизма полезно только в том случае, когда ком­поненты процессов могут взаимодействовать при получении реше­ния задачи. Такое взаимодействие требует распределения ресурсов между процессами. Для гарантии правильности работы системы в целом распределением необходимо управлять. Проблемы синхро­низации, возникающие при взаимодействии процессов, иллюстри­руются многочисленными примерами, приведенными в литераторе. Среди задач синхронизации: задача о взаимном исключении, производителе/потребителе , обедающих мудрецах , чте­нии/записи и др.

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

Описанные до сих пор системы относятся к самому очевидному типу систем, моделируемых сетями Петри: аппаратному и про­граммному обеспечению ЭВМ. Но в большей части эта «очевидность» является результатом того, что сети Петри были определены и раз­работаны главным образом для этой цели. Но они также приме­нимы для моделирования большого числа других систем, совер­шенно отличных от вычислительных систем. В этом разделе мы бег­ло ознакомимся с некоторыми из них.

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

PERT-диаграмма и сеть Петри взаимосвязаны: PERT-диаграмма легко преобразуется в сеть Петри. Каждый этап PERT-диаграммы представляется позицией, причинно-следственные связи — пере­ходами. Диаграмма на рис. 3.35 может быть преобразована в экви­валентную сеть Петри, изображенную на рис. 3.36.

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

Конвейерная обработка, описанная в разд. 3.3.2, является част­ным случаем производственной системы . Сборочная линия — другой пример производственной системы. Производственные систе­мы и сборочные линии могут быть промоделированы сетями Петри.

Одно из первых применений сетей Петри — применение в качестве средства генерации оптимального кода для компилятора с [ Фортрана CDC 6600. Подход к решению этой задачи, предложенный , заключался в моделировании программы на Фортране | сетью Петри способом, подобным моделированию блок-схемы £(разд. 3.4.1). Затем отдельные операторы программы рассматривались с целью определения минимального набора причинно-следственных связей между операторами, позволяя исключать из сети • Петри некоторые из искусственно введенных ограничений на последовательность операторов программы. Эти искусственные ограничения введены из-за необходимости для программиста представ­лять программу на Фортране в виде последовательности, задающей полный порядок на множестве операторов, даже если требуется только частичное упорядочение. В качестве примера рассмотрим следующие три оператора:

10y=x+1 ,

20y=y+1,

30z=x+y.

Они написаны таким образом, что оператор 10 предшествует опера­тору 20, но такая последовательность вовсе необязательна. Поря­док, в котором будут выполнены операторы 10 и 20 (или они будут выполнены одновременно), не имеет значения для программы. Од­нако оператор 30 должен следовать только после операторов 10 и 20. После изменения упорядочения операторов необходимо рас­смотреть и поток управления. Этот анализ заключается в примене­нии условий Бернстайна для обеспечения детерминированности.

Результатом такого анализа является сеть Петри, представляю­щая программу с минимальными ограничениями на последователь­ность операторов, т. е. допускающую максимальный параллелизм. Теперь задача состоит в компиляции такой программы. Это требует отображения переменных в регистры и упорядочения инструкций для получения полностью упорядоченной последовательности ин­струкций машинного языка. CDC 6600 — это ЭВМ с несколькими регистрами и кратными функциональными блоками (разд. 3.3.3). Так как функциональные блоки могут выполнять различные ин­струкции параллельно, то очень важно порождать инструкции в порядке, максимально увеличивающем параллелизм при работе функциональных блоков. На это также влияет распределение пере­менных по регистрам. Сеть Петри, моделирующая программу и представляющая ограничения, налагаемые программой, объединя­ется с сетью Петри, моделирующей устройство управления CDC 6600 и представляющей ограничения, налагаемые аппаратным обе­спечением. Такая объединенная сеть представляет все возможные последовательности инструкций, которые могут выполняться ап­паратурой и реализовать алгоритм данной программы. Эта сеть затем выполняется для получения всех таких последовательностей инструкций. Две (или более) последовательности образуются вся кий раз, когда два (или более) перехода одновременно разрешены. Запуск одного перехода будет порождать одну последовательность; запуск другого перехода — другую. Например, сеть Петри на рис. 3.37 представляет последовательности abcdef, bacdef, abcedf, bacedf. После того как последовательности получены, вычисляются необходимые затраты времени на их выполнение, и наиболее быст­рая последовательность генерируется компилятором для действи­тельного выполнения.

Химические системы — другой пример систем, которые могут быть промоделированы сетями Петри. Химические уравнения моде­лируются переходами; вещества, участвующие в реакции, — по­зициями. Количество фишек в позиции указывает на количество данного вещества в системе. Например, сеть Петри на рис. 3.38 представляет два химических уравнения:

Н2С204 → 2СОа + 2Н+ + 2е-

2е- + 2Н+ + Н202 → 2Н20.

Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н2 + С2Н4 → С2Н6) только в присутствии платины. Это отражено на рис. 3.39.

Мельдман и Хольт выдвинули предположение, что и юри­дические системы могут быть промоделированы сетями Петри. В этих системах несколько действующих лиц (судьи, адвокаты, об­виняемые, клерки и др.) могут одновременно выполнять действия, относящиеся к конкретному делу. Действия и их взаимосвязи могут быть представлены сетью Петри. Например, сеть Петри на рис. 3.40 является моделью начальных стадий гражданского процесса.

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

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

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

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

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

Рассмотрим, например, сети Петри на рис. 4.20 и 4.21, дерево достижимости которых изображено на рис. 4.22. Одно дерево достижимости представляет эти две схожие (но различные) сети Петри. Множества же достижимости их не совпадают. В сети Петри на рис. 4.20 число фишек в позиции р₂ всегда четно (пока не будет запущен переход t₁), тогда как в сети Петри на рис. 4.21 оно может быть произвольным целым. Символ t₀ не позволяет обнаруживать информацию такого рода, препятствуя использованию дерева до­стижимости для решения задачи достижимости.

Аналогичная трудность существует и для задачи активности На рис. 4.23 и 4.24 приведены две сети Петри, дерево достижимости которых изображено на рис. 4.25. Однако сеть на рис. 4.23 может иметь тупик (например, в результате последовательности t₁ t₂ t₃ ) а сеть Петри с рис. 4.24 — нет. Дерево достижимости же вновь не может передать различие этих двух случаев.

Заметим, что хотя дерево достижимости не обязательно содер­жит достаточную информацию для решения задач достижимости и активности, тем не менее в некоторых случаях это бывает возмож­но.

Сеть, дерево достижимости которой содержит терминальную вершину (вершину, не имеющую исходящих дуг), не активна (по­скольку некоторая достижимая маркировка не имеет последую­щих маркировок). Аналогично маркировка μ.' в задаче достижимос­ти может встретиться в дереве достижимости, и если это так, то она достижима. Кроме того, если маркировка не покрывается некото­рой вершиной дерева достижимости, то она недостижима.

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