ГЛАВА 1. ВВЕДЕНИЕ

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

1.1. Моделирование

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

Как правило, модели имеют математическую основу. Характеристики многих физических явлений можно описать числами, а связь этих характеристик — уравнениями или неравенствами. В частности, в естественных науках и технике уравнениями описываются такие характеристики, как масса, положение в пространстве, момент, ускорение и силы. Однако для успешного использования подхода моделирования необходимо знание как моделируемых явлений, так и свойств метода моделирования. Поэтому математика как наука развивалась частично благодаря использованию ее в моделировании явлений, изучаемых другими науками. Так,

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

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

1.2. Природа систем

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

Итак, несмотря на разнообразие моделируемых систем, выделяется несколько общих черт, которые должны быть отражены в особенностях используемой модели этих систем. Основная идея заключается в том, что системы состоят из отдельных взаимодействующих компонент. Каждая компонента сама может быть системой, но ее поведение можно описать независимо от других компонент системы, за исключением точно определенных взаимодействий с другими компонентами. Каждая компонента имеет свое состояние. Состояние компоненты — это абстракция соответствующей информации, необходимой для описания ее (будущих) действий. Часто состояние компоненты зависит от предыстории этой компоненты, поэтому оно может со временем изменяться. Понятие «состояние» очень важно при моделировании компоненты. Например, в модели системы очередей банка могут присутствовать несколько кассиров и несколько клиентов. Кассиры могут быть свободны (ожидая клиента) или заняты (обслуживая клиента). Аналогично клиенты могут быть свободны (ожидая, когда кассир освободится для обслуживания их) или заняты (при обслуживании их кассиром). В клинической модели состояние пациента может быть критическим, серьезным, удовлетворительным, хорошим или превосходным.

Действиям компонент системы присущи совмещенность или параллелизм. Действия одной компоненты системы могут производиться одновременно с действиями других компонент. В

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

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

1.3. Зарождение теории сетей Петри

Сети Петри разрабатывались специально для моделирования тех систем, которые содержат взаимодействующие параллельные компоненты. Впервые сети Петри предложил Карл Адам Петри 1241]. В своей докторской диссертации «Kommunikation mit Automaten» («Связь автоматов») Петри сформулировал основные понятия теории связи асинхронных компонент вычислительной системы. В частности, он подробно рассмотрел описание причинных связей между событиями. Его диссертация посвящена главным образом теоретической разработке основных понятий, с которых начали развитие сети Петри.

Работа Петри привлекла внимание А. В. Хольта и сотрудников из Проекта Information System Theory (Теория информационных систем) фирмы Applied Data Research (ADR). Ими была развита большая часть начал теории, предложены обозначения и представления сетей Петри, опубликованные в окончательном отчете по этому проекту [128] и в отдельном отчете, имеющем название «Events and Conditions» («События и условия») [127]. В этой работе показано, как сети Петри можно применить к анализу и моделированию систем, включающих параллельные компоненты.

Работа Петри привлекла также внимание группы, работающей над Проектом MAC в Массачусетском технологическом институте (МТИ). Руководимая профессором Дж. Б. Деннисом группа вычислительных структур стала источником значительных исследований и публикаций по сетям Петри, были написаны несколько Диссертаций на степень доктора философии и множество отчетов и меморандумов (см. библиографию). Группой вычислительных структур были проведены две большие конференции по сетям Петри: Конференция Проекта MAC по параллельным системам и

параллельным вычислениям в 1970 г. в Вудс Холле [73] и Конференция по сетям Петри и связанным с ними методам в 1975 г. в МТИ. Обе эти конференции внесли вклад в распространение результатов и методов теории сетей Петри.

За последние несколько лет использование и изучение сетей Петри значительно расширились. В 1977 г. в Париже и в 1979 г. в Гамбурге на лекциях по общей теории сетей проводились заседания рабочей группы по сетям Петри. В ФРГ была образована группа интереса по сетям Петри. Исследования и применения сетей Петри расширяют сферу действия.

1.4. Применение теории сетей Петри

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

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

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

Рис. 1.1. Использование сетей Петри для моделирования и анализа систем. Сначала система моделируется сетью Петри, затем модель анализируется. Оценка системы, являющаяся результатом анализа, приведет, как ожидается, к лучшей системе. Необходимы исследования, направленные на разработку автоматических методов моделирования и анализа систем сетями Петри.

1.5. Прикладная и чистая теории сетей Петри

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

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

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

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

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

Теория сетей Петри родилась в диссертации Петри [241], но большинство работ в США основано на окончательном отчете по Проекту теории информационных систем [128], в котором переведена на английский язык и значительно расширена диссертация Петри. Кроме того, среди первых публикаций важную роль играет работа Хольта и Коммонера «События и условия» [127]. Петри представил небольшую статью на конгресс ИФИП, которая опубликована в трудах конгресса [242]. Она основана на идеях, изложенных в диссертации.

Представленный в книге подход во многом основан на работе группы вычислительных структур МТИ и работах Денниса [72], Патила [231] и др., кончая работой Хэка [113]. Насодержание книги также оказал влияние Келлер — своим отчетом по системам замещения векторов [150] и своей точкой зрения на моделирование [152].

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

1. Проследите истоки и направления важных идей теории сетей Петри. Очевидно, что исходная точка принадлежит Петри, но как и к кому направлялись идеи дальше, как они появились в Соединенных Штатах? Куда они направились оттуда? Для определения предшествования используйте даты и ссылки из опубликованных отчетов, статей, диссертаций и меморандумов. Возможно, вам захочется проинтервьюировать некоторых «ключевых» людей: Петри, Хольта, Денниса, Патила и др.