Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 13
Текст из файла (страница 13)
Сборочная линия— другой пример производственнойсистемы. Производственные систе- мы и сборочные линии могут быть промоделированы сетями Петри. Одно из первых применений сетей Петри — применение в ка- ' честве средства генерации оптимального кода для компилятора с Фортрана СОС 6600. Подход к решениюэтой задачи, предложенный в [2741, заключался в моделировании программы на Фортране сетью Петри способом, подобным моделированию блок-схемы [равд. 34.1). Затем отдельные операторы программы рассматри- , вались с целью определения минимального набора причинно-след- ~ственных связей между операторами, позволяя исключать из сети ° Петри некоторые из искусственно введенных ограничений на по- "следовательность операторов программы. Этн искусственные ограни- 'чения введены из-за необходимости для программиста представ- лять программу на Фортране в виде последовательности, задающей полный порядок на множестве операторов, даже если требуется только частичное упорядочение.
В качестве примера рассмотрим следующие три оператора: 1Ох,'= х+ ), 20д= р+1, 30 3 = х + ц» Гдово 8 Поойлжателиюом» Фмоолваиге гчигвзтзг Натела изге влвоаоюо!ЬфйЮоРвзт Ра тзу НаЮьшройевае РлазоЛгооаозйзнро терриомраа Ретгмпоеюызге юловаргюРозроороЮойщге раРотз| Ноноаоеа Ркооеетовзоогв влввтродаботи Рис. 3.35. РЕКТ-диаграмма строительства дома. (Ф. Леви, Г. Томпсон, Дж. Уист зВведеине в метод критических путей». в 1понзтг1а! 8сйейоИпд, ео11ей Ьу Лойп Р., Ип1й апо бега1 о Ь. Тйотрзоп, сорут1дй1 1963, р.
335. С разрешении Ргеп11се-Нв11, 1пс., Епй1евоой С1111з, Нем Легзеу.) Сети Петри длл моделирования 73 Рис. З.З6. Представление РЕКТ-дваграммы на рве. З.ЗБ сезъю Петри. Обра- тнте вниманне на то, что введены дополввтельные узлы. Онв необходнмм для вдеяватного отобрзження ограничения предвествоввния н точного представ- леввя снтувцнй с ожиданием. Глава 3 74 Рис. 3.37. Сеть Петри, прелстааляющая несколько послелоаптельностей аыполнеиия ниструкпии. Они написаны таким образом, что оператор 10 предшествует оператору Ю, но такая послезпаательность вовсе необязательна. Порядок, в котором будут выполнены операторы 10 и 20 (или они будут выполнены одновременно), не имеет значения для программы.
Однако оператор 30 должен следовать только после операторов 10 и 20. После изменения упорядоченчя операторов необходимо рассмотреть и поток управления. Этот анализ заключается в применении условий Бернстайна для обеспечения детерминированности. Результатом такого анализа являегся сеть Петри, представляющая программу с минимальными ограничениямч на последовательность опера~оров, т.
е. допускающую максимальный параллелизм. Т.парь задача состоит в компиляции такой программы. Это требует отображения переменных в регистры и упорядочения инструкций для получения полностью упорядоченной послеаовательности инструкций машинного языка'>. СОС 6600 — зто ЭВМ с несколькими регистрами н кратными функциональными блоками (разд. 3.3.3). Так как функциональные блоки могут выполнять различные инструкции параллельно, то очень важно порождать инструкции в порцаке, максимально увеличивающем параллелизм при работе функциональных блоков. На это также влияет распределение переменных по регистрам.
Сеть Петри, моделирующая программу и представляющая ограничения, налагаемые программой, объединяется с сетью Петри, моделирующей устройство управления С1)С 6600 н представляющей ограничения, налагаемые аппаратным обеспечением. Такая объединенная сеть представляет все возможные последовательности инструкций, которые могут выполняться аппаратурой и реализовать алгоритм данной программы. Эта сеть затем выполняется для получения всех таких последовательностей инструкций. Пве (илн более) последовательности обрззукпся вся- В Некоторые на которых яаляются инструкциями, реалиаующнми параллельную обработку. — 77рпм. рвд. Сети Петри для иоделироеияия изоз Рнс.
3.88. Сеть Петри, представляющая окисл иге л ьио-аосстаиовительиую реакпию между щавелевой кислотой и пероисидом водорода, в результате которой получаются вода н дионсид углерода. ! 1 кий раз„когда два (илн более) перехода одновременно разрешены. Запуск цаного перехода будет порождать одну последовательность; запуск другого перехода — другую. Например, сеть Петри на рис. 3.37 представляет последовательности айаЦ, Ьасс(еу, аЬсеЩ, Ьасейу. После того как последсвательносги получены, вычисляются необходимые затраты времени на их выполнение, и наиболее быстрая последовательность генерируется компилятором для действительного выполнения. Химические системы — другой пример систем, которые могут быть промоделированы сетями Петри. Химические уравнения моделируются переходами; вещества, участвующие в реакции, — позициямн. Количество фишек в позиции указывает на количество данного вещества в системе.
Например, сеть Петри на рис. 3.33 представляет два химических уравнения: НзсзО, 2СО, + 2Н++ 2е 2е + 2Н'+ Н,О, -» 2Н,О. Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н, + СзНе-» (~Не) только в присутствии платины. Это отражено на рнс. 3.39. Мельдман и Холы П36) выдвинули предположение, по и юридические системы могут быть промоделированы сетями Петри. В этих системах несколькадействующих лиц (судьи, адвокаты, обвиняемые, клерки идр.) могут одновременно выполнять действия, относящиеся к конкретному д лу. Действия и их взаимосвязи могут быть представлены сетью Петри. Например, сеть Петри на рис. 3.40 является моделью начальных стадий гражданского процесса.
Другое предложение заключается в использовании сетей Петри для моделирования н анализа протоколов связи 1194). В сетях ЭВМ и системах распределенных процессов необходима возможность передачи информации между ЭВМ. В этой задаче существенно присутствует параллелизм, и поэтому она попадает в класс задач, для которых определены сети Петри. Фарбер и его ученики (193, 250, 1%, 25П разработали методологию для спецификации, проектирования и анализа простых протоколов связи, используя сети Петри и подобные модели.
Рис. 3.39. Процесс получения этапа иэ водорода и этилена при катализации платиной. Другие системы, которые могли быть промоделнрованы сетями Петри, включают в себя системы очередей (где очереди были бы представлены позициями, а работы — фишками); модели мозга (запуски нейронов могли бымоделироватьсязапусками переходов); исчисление высказываний (о8, 911 (позиции представляют буквы, а переходы объединяют их для определения предложений в коньюнктнвной нормальной форме) и многие другие системы. Этот список ограничен в основном временем и воображением человека, но не свойстваьги сетей Петри. Однако мы видели по крайней мере один пример (задача о чтении/записи), который нельзя промоделировать с помощью сети Петри.
И хотя моделирование с помощью сетей Петри может быть полезным при описании системы, необходимо разработать средства анапнза, которые бы позволили исследовать сеть Петри и определить ее свойства. Обратимся к этому в следующей главе, в которой представлены методы анализа сетей Петри, Упражнения) !. Промоделируйте вычислительную сястему с тремя процессами и четырьмя ресурсами: устройство чтения с карт, построчно печатающее устройство, диск и два раздела вамзти. Любой процесс может попасть в любой раздел. Использование ресурсов тремя процессами состоит в следующем: а) процесс ! запрашивает устройство чтения с карт м построчно печатающее устройство, а затем освобозщает оба этн ресурса; Сети Петри дел иоделировикил с Плере бьтисьтбает бьюоб б суд Мт Иорк передает дьтеаб Ф ааб судебкоьчу испалиителю Ма Прошло 26 дией Рз ~~6 Рь Рр Рз Ва Рис.
ЗАО. Сеть Петри, представляющая начальные стадии гражданского нроцесса. (Из П661, авторское право Американской ассоциации юристов, 'отделение науки и технологии. Перепечатывается с разрешения.) Истек рееистрирует иск у клерка Отбет чик решает отде четь Отбетчик огриаиальио отвечает остау Оудебтютй исполпитвоь вручает бьтеоб и сообщает об иске отбетчииу Отбетчик решает дапю бстречкьтй иск Отбетчии бьчстабляет Естречиый иси' Отбетчик «е ябляетса Ю суд 78 Глаза 3 б) процесс й запрашивает устройство чтения с карт н диск, а затеи освобождает устройство чтенпя с карт, аапрашнвает построчно печатающее устройство я в конде концов освобождает н построчно печатающее устройство, н диск; в) процесс 3 требует все трн ресурса одновременно, н затем все нх освобождает.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
