Книжка по сетям Петри

1ДК 81Э.В © Издательство "Науке". Главная редакция физико.математической литцтатуры, 1984 170$ЯЩЩ-ВЩ „,.8, ц Зс чцсг-и к о т о а В.е. сети пвциь — аз.: науке. Главная редакция физико-мета. магической литературы. 1984. — 1Вб с. Книга посвящмю систематическому изложеиию теории сатей Пвтри. котсрью отиосятся к числу наиболее вичкых и распространенных математическик модапай а области обработки информации. Они сбаспечивают бюрмзпьиое описание как виоритмов и программ, так и ссбствеиио вы числительных сьютаеч и ик устройств, а также порождаемых аычислитми пых процессов, и используютсл для рмиенип разнообразных задач скалите, синтеза и оптимизации. ОГЛАВЛИНИИ Преписловие .9 ..14 ГЛАВА 1 ОСНОВНЫЕ ПОНЯТИЯ.

6 1.1. системы, щюцасаьь сети. 6 1.2. Формальное оцзадвление сети Петри ГЛАВА 2 СВОЙСТВА СЕТЕЯ ПЕТРИ И ИХ АНАЛИЗ .. Е 2.1. Основные свойстве сетей Петри Ф 2.2. П1юблсмы огреначенипсти н безопасности... 5 2.3. Проблемы Ю-вклхжения и Я.зквивапвнтностн 6 2.4. Проблемы достнжимости и живости ГЛАВА 3 ЯЗЫКИ СЕТЕЙ ПЕТРИ. 6 3.1. Помвчвнньн сети и классы языков сетей Петри.........

Е 3.2. Херзктзризвция классов языков сетей Петри.......... 6 3 3. Рвзрмпимые и нцзезренммые свойстве языков сетей Петри. ГЛАВА 4 ПОДКЛАССЫ СЕТЕЙ ПЕТРИ. 5 4.1. Ординзрньа сети Петри бабйдвто е е н яр ц «граф 6 4.3. Свободнее сети ГЛАВА 6 ОБОБЩЕНИЯ СЕТЕЙ ПЕТРИ.. Ф 6.1.

Счетчнковые евтоматы.. 6 6.2. Ингибитсрные сети и сети с приоритетами......... 5 6.3. Рпскрнпенные, синхронньм и самомодифмцнруемые сати .20 ..22 ..27 .32 . 36 . 43 .47 68 .. 71 .. 74 ГЛАВА 7 СЕТИ СИСТЕМЫ И СЕТИ. ПРОЦЕССЫ .101 5 7.1. Процессы . .102 В 7.2. Сетевое прадставлвние параплальных процессов................104 5 7.3. Сетевое представление последовательно альтернативных процессов....110 $7.4. Сетевое представление параллельно.альтернативных процессов.......

111 5 7 5. Разаартка сетей Петри в сети процессы............,.........117 6 7.6. Сетваоа представлыюе параллельных процессов с конкуренцией..... 125 . 128 128 135 138 Н45 Заклинание, Пмтаратура . .150 Словарь терминов. 153 ГЛАВА 6 РЕГУЛЯРНЫЕ И ИЕРАРХИЧЕСКИЕ СЕТИ ф 8.1. Алгебра ро'улярных сетей.....................

5 6.2. Некоторыесаойстварвгуллрных сетей.....,....... 5 6 3. Иерархические сети. 5 6.4. Сравнение иерархических сатей с другими классами сетей. 5 6.5. Сети с опылением и строго иерархические сети........ ГЛАВА 8 СЕТИ ПЕТРИ И ПРОГРАММИРОВАНИЕ. 5 8,1. Сати Патри и семантике структур управлении 5 8.2. Потоксвые сети 5 8.3.

Типы управленим 5 8.* Петрмчиаитмна . 83 89 .. 92 .. 96 Среди большого числа понятий, которые возникли и исследуются в кибернетике и информатике, одним иэ наиболее общих является понятие дискретной динамической системы. Примерами дискретных систем могут служить электронно вычислительные машины, их элементы и устройства, сети ЭВМ, программы и операционные системы, системы сбора и автоматичео кой обработки цифровой информации, системы автоматического управления обьектами и прОцессами, производственные системы дискретного характера, такие как сборочные пинии и цеха, сациально-зкономические структуры и тль Изучение свойств дискретных систем и развитие методов их ксиструи.

рования проводится с помощью различных математических моделей и методов в зависимости от класса систем, степени детализации их структуры и свойств, а также от характера исследуемых проблем, В ходе развития науки, техники и производства появляются новью виды дискретных систем, их разнообразие и сложность постоянно растут. Чтобы успешно решать задачи анализа и синтеза асе более сложных систем, необходимо дальнейшее развитие и соаерцюнствование математических методов их исследования.

Особую роль в теории дискретных информационных систем сыграло понятие автомата. Автомат является математической абстракцией системы (ьюшины, устройства) переработки информации или процесса переработки. Автомат имеет конечное число входов, воспринимающих дискретную ин. формацию, т.е. информацйю, изобракаемую конечным числом символов из некоторого алфавита.

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

Конечный автомат имеет конечное»испо состояний. Если автомат моделирует систему сложнои структуры, то он ьюжет быть представлен как совокупность взаимодействующих автоматов, моделирующих ае подсистемы Псомпоненты системы] . Автоматы, построенные иэ определенных компонентов по определенным правилам, часто представляют сетями, т.е. графами спациалыюго вилл с дополнительной ннтврпретацией вершин н дуг. Понятие конечного автомата в той форме, в какой оно применялось до Настоящего времени, существенно связано с понятиями алгоритма и последовательной алгоритмической системы. Для последних характе- 5 реи лослййовательный способ функционирования: система (автомат) пос.

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

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

В случае систем с параллелизмом и тогда, когда нас интересует не только и не столько функция, реализуемая системой, а ее структурные характерно. тики и свойства, модель системы должна быть структурно подобна самой системе. Это означает, что модель можно строить по частям, как и систему.

Глобальные функции и понятия могут определяться на основе локальных, соответствуххцих компонентам, подсистемам и подпроцессам; связи и отношения между фрагментами модели подобны связям и отношениям между фрагментами системы. Наконец, немаловажным фактором является возможность представления моделей систем в форме, удобной и эффективной для обработки их с помощью ЭВМ. Среди многих существующих методов описания и анализа дискретных параллельных систем выделился подход, который основан на использо.

ванин сетевых моделей, восходящих к сетям специального вида, предложенным Картюм Петри [731 для моделирования асинхронных информационных потоков в системах преобразования данных. В рамках этого подхода рассматривались различные версии и модификации сетей Петри (под разными названиями).

Независимо предполагались также формализмы, которые оказывались эквивалентнымн по своим свойствам и возможностям сетям Петри. Систематическое изучение свойств сетей Пе1ри и возможности приме. нения их для решения прикладных задач, в основном — задач, связанных 6 с моделями и средствами параллельной обработки информации, началось на рубеже 60-х и 70-х годов. Хотя к настоящему времени фронт работ существенно расширился, теория сетей Петри еще не известна широка Поэтому автор данной книги, который на собственном опыте убедился в том, что сети Петри является не только удобным и полезным инстру. ментом для формулирования и решения проблем в области параллель- ных систем и процессов, но и источником новых, увлекательных и трудных математических задач, решил попытаться изложить ее основные понятия, проблемы и результаты в том виде, в каком сни сформировались к наста.

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

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

Эта книга посвящена, в основном, второму направлению — специальной теории сетей Петри, так как именно с него началось интенсивное изучение сетей и их свойств. Понятия и результаты специальной теории образуют ядро всей теории в целом и отправную точку для исследований в общей ' После тато квк начете была работа нед атой книгой, катарам звдуыыевлесь квк введение в лроблеттетику сетет Пегом н ик приложений. вышли ыоногрвфии П. Штарке !83[, В. Рейзигз [79! и Дж.