3.5. Другие системы

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

PERT-диаграмма давно используется для планирования больших проектов. PERT-диаграмма является графическим

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

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

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

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

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

(кликните для просмотра скана)

(кликните для просмотра скана)

Рис. 3.37. Сеть Петри, представляющая несколько последовательностей выполнения инструкции.

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

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

всякий раз, когда два (или более) перехода одновременно разрешены. Запуск одного перехода будет порождать одну последовательность; запуск другого перехода — другую. Например, сеть Петри на рис. 3.37 представляет последовательности После того как последовательности получены, вычисляются необходимые затраты времени на их выполнение, и наиболее быстрая последовательность генерируется компилятором для действительного выполнения.

Рис. 3.38. Сеть Петри, представляющая окислительно-восстановительную реакцию между щавелевой кислотой и пероксидом водорода, в результате которой получаются вода и диоксид углерода.

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

Можно представить и реакции катализа. Соединение водорода и этилена образует этан только в присутствии платины. Это отражено на рис. 3.39.

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

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

Рис. 3.39. Процесс получения этана из водорода и этилена при катализации платиной.

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

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

Упражнения

(см. скан)

(кликните для просмотра скана)

(см. скан)

3.6. Замечания к литературе

Большинство исследований по сетям Петри связано с анализом, а не с моделированием. Обзоры применений сетей Петри к моделированию появились в работах [238, 6]. Моделирование аппаратного обеспечения рассматривалось в [72, 132]. В работе [274] для реализации компилятора объединено моделирование аппаратного и программного обеспечения. Заметки [56] связаны с моделированием программных систем сетями Петри. В диссертационной работе Хэка [107] рассматривается моделирование производственных процессов, которые включают системы типа сборочных линий.

Баер и Эллис [22] использовали сети Петри для моделирования компилятора, а Ное [214] и Бест [36, 37] — для моделирования операционных систем. Ное и Кель [223] промоделировали аппаратное обеспечение вычислительной системы, Азема и др. [16, 17], Фу и Масгрэйв [83] предложили использовать сети Петри для автоматизации проектирования.

Исследования Ное и Натта главным образом направлены на моделирование систем для определения производительности. Их работы [214, 226, 227, 224] в конце концов привели к разработке модели -сетей, которая связана с сетями Петри.

3.7. Темы для дальнейшего изучения

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

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

3. Выберите любую из следующих тем и исследуйте применение сетей Петри для моделирования по темам:

а) системы операций;

б) моделирование мозга;

в) химические реакции;

г) военный конфликт;

д) политические системы;

е) экономика (в особенности макроэкономические события);

ж) транспортные потоки на дорогах и шоссе;

з) биологические популяции;

и) семантические сети для представления естественного языка.