Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 14
Текст из файла (страница 14)
З.б. Замачаиия а нмтературе Болыпинство исследований по сетям Петри связано с анализом, а не с моделированием. Обзоры применений сетей Петри к моделированию появились в работах [238, 61. Моделирование аппаратного обеспечения рассматривалось в [72, 1321. В работе [2?41 для реализации компилятора объединено моделирование аппаратного и программного обеспечения. Заметки [561 связаны с моделированием программных систем сетями Петри. В диссертационной работе Хэна П071 рассматривается моделирование производственных процессов, которые включают системы типа сборочных линий.
Баер и Эллис [221 использовали сети Петри для моделирования компилятора, а Нос [2141 и Бест [36, 371 — для моделирования операционных систем. Нос н Кель [2231 промоделировали аппаратное обеспечение вычислительной системы, Азама и др. Пб, 171, Фу и Масгрэйв [631 предложили использовать сети Петри для автоматизации проектирования. Исследования Ное и Натта главным образом направлены на моделирование систем для определения производительности. Их работы [214, 226, 227, 2241 в конце концов привели к разработке модели Е-сетей, которая связана с сетями Петри. 3.7.
Темы дпя двпьнайзваге изучении 1. Примените моделирование сети Петри для описания взаимодыствня субзтомных частиц в физике высоких энергий. 2. РЕЕТ-диаграммы обычно содержат информацию о времени событий. Исследуйте, каким образом можно добавить информацию о времени в сеть Петри. Как повлияет это на правила запуска? Предложите алгоритм для вычисления минимального (макснмального) времени, требующегося для окончания процесса. 3. Выберите любую из следующих тем и исследуйте применение сетей Петри для моделирования по темам: а) системы операций; б) моделирование мозга; в) химические реакции; г) военный конфликт; д) политические системы; е) экономика (в особенности макроэкономические события); ж) транспортные потоки на дорогах и шоссе; з) биологические популяции; и) семантические сети для представления естественного языка.
АНАЛИЗ СЕТЕЙ ПЕТРИ В предыдущей главе была продемонстрирована моделирующая мощность сетей Петри. С помощью сетей Петри можно моделировать широкий класс систем, представляя должным образом взаимодействие различных процессов, которые могут возникнуть. Наиболее сильны сети Петри при моделирований систем. включающих параллельные действия, причем параллельность моделируется естественным н удобным образом. Сети Петри можно испольэовать для представления и сообщения о проекте параллельной системы.
Однако само моделирование малополезно. Необходимо провести анализ моделируемой системы. Этот анализ, можно надеяться, приведет к глубокому проникновению в поведение моделируемой системы. Таким образом, мы подошли к необходимости рассмотрения методов анализа сетей Петри. Несколько методов анализа уже разработано, однако в области анализа сетей Петри существует еще много проблем. Для того чтобы лучше оценить разработанные о методы анализа, рассмотрим прежде всего типы задач, которые требуют решения.
Цель анализа сети Петри — получение ответа на вопрос о конкретной сети Петри. Какие же вопросы о сети Петри можно задать? 4Л. Задачи анализа сетей Петри В публикациях по сетям Петри рассмотрены следующие свойства и вопросы. (Здесь мы определим и проиллюстрируем зти свойства, $ а во второй части главы приведем соответствующие методы анализа.) 4.1Л. Безопасность Одно из важнейших свойств сети Петри, которая должна модет пировать реальное устройство, — безопасность.
Позиции сети Петри является безопасной, если число фишек в ней никогда не превы', шает 1. Сеть Петри безопасна, если безопасны все позиции сети. Определение 4.!. Позиция и; ~ Р сети Петри С = (Р, Т, 1, О) с начальной маркировкой р является безопасной, если (ь'(р~) -4 1 для любой р' ~ Я(С, р). Сеть Петри безопасна, если безопасна Каждая ее позиция. Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно О или 1. Следовательно, позицию можно реализовать одним триггером.
В первоначальном определении сети Петри были безопасны, поскольку переход не мог быть запущен, если не все из выходных Глава 4 80 позиций были пусты (а кратные дуги не были разрешены). Это объяснялось интерпретацией позиции как условия. Условие, будучи логическим высказыванием, либо истинно (представляется фип кой в позиции), либо ложно (представляется отсутствием фишки); кратные фишки не имеют никакой интерпретации. Таким образом, если интерпретировать сети как условия и события, маркировка каждой позиции должна быть безопасной. Если позиция не является кратной входной илн кратной выходной для перехода, ее можно сделать безопасной. К позиции "р„ которую необходимо сделать без22паснай, добавляется новая позиция р,'.
Переходы, в которых р2 используется в качестве входной или выходной, модифицируются следующим образом: Если реб1(Я н р2 ~0(~2), тогда добавить р' к 0(тт). Если 2пеЕ0(42) и р,(У(Я, тогда добавить р, 'к 1(Г2). Цель введения втой новой позиции ре — представить условие «р2 пуста». Следовательно, ре и рт дополннтельны; р; имеет фип2ку, только если р; не имеет фишки и наоборот.
Любой переход, удаля- 22 Р2 22 Р2 Рис. 4Л. Сеть Петри, не являеощаися безопасной. Р'2 Р2 Рис. 4.2. Безопасная сеть Петри, зввнвапеитная сети. приведенной на рис. 4Л. Анализ сетей Петри ющий фишку из рь должен помещать фишку в р~, а всякий переход, удаляющий фишку из рь должен помещать фишку в р,. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в рь либо в р,, (Мы допускаем, что начальная маркировка безопасна.) Заметим, что такая принудительная безопасность возможна только для позиций, котопые в начальной маркировке являются безопасными и входная и выходная кратность которых равна О илн 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной.
Простая сеть Петри на рис. 4.1 преобразована в безопасную, как показано на рис. 4.2. 4.1.2. Ограниченность Безопасность — это частный случай более общего свойства ограниченноеаш. Некоторые соображения относительно реального ограничения на аппаратную реализацию позиций позволяют прийти к заключению, что безопасность — необязательное требование. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно-реализованный счетчик ограничен по максимальному числу, которое он может представить. Позиция является А-безопасной нли й-ограниченной, если количество фишек в ней не может превышать целое число А. Определение 4.2. Позиция Р,Е Р сети Петри С= (Р, Т, 1, 0) с начальной маркировкой р является й-безопасной, если р'(р ) ( й для всех р' ~ Я(С, р).
1-безопасная позиция называется просто безопасной. Заметим, что граница й' по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например„ позиция р, может быть З-безопасной, тогда как позиция рз — 8-безопасной]. Однако, если позиция р, А-безопасна„ то она также н /г'-безопасна для всех й' ~ й. Поскольку число позиций конечно, можно выбрать А, равное максимуму из границ каждой позиции, и определить сеть Петри А-безопасной, если каждая позиция сети Й-безопасна. Иногда нас будет интересовать только то, является число фишек в позиции ограниченным илн нет, а не конкретное значение границы. Позиция называется ограниченной, если она й-безопасна для некоторого й; сеть Петри ограниченна, если все ее позиции ограниченны.
Ограниченную сеть Петри можно реализовать аппаратно, тогда как сеть Петри с неограниченными позициями в общем случае реализовать аппаратно нельзя. (Вспомним, что эти определения не зависят от интерпретации, В реализации позиция может представлять некоторый объект, являющийся ограниченным, хотя сама структура сети не отражает зтот факт.) Глава 4 4.1.3. Сохранение Сети Петри можно использовать для моделирования систем распределения ресурсов.
Например, сеть Петри может моделировать запросы, распределения и освобождения устройств ввода/вывода в вычислительной системе. В этих системах некоторые фишки могут представлять ресурсы. Группа нз трех построчно печатающих устройств представляется позицией, имеющей в начальной маркировке три фишки. Запрос построчно-печатающего устройства— зто переход, для которого данная позиция является входной; затем устройспю освобождается переходом, для которого позиция построчно печатающих устройств является выходной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
