4.2. Моделирование систем на основе сетей Петри
Первый шаг на пути к построению модели системы – это абстрагирование от конкретных физических и функциональных особенностей ее компонентов. Компоненты системы и их действия представляются абстрактными событиями, каковыми могут быть, например, исполнение оператора программы, переход триггера из состояния в состояние, прерывание
в операционной системе, операция станка или конвейерной линии, завершение этапа проекта и т. п.
Событие может произойти (реализоваться) один раз, повториться многократно, порождая конкретные действия (реализации события), или не произойти ни разу. Совокупность действий, возникающих как реализации событий при функционировании системы, образует процесс, порождаемый этой системой. В общем случае одна и та же система может функционировать в одних и тех же условиях по-разному, порождая некоторое множество процессов, т. е. функционировать недетерминированно.
Реальная система функционирует во времени, события происходят
в некоторые моменты времени и длятся некоторое время. В синхронных моделях систем события явно привязаны к определенным моментам или интервалам времени, в которые происходит одновременное изменение состояний всех компонентов системы, трактуемое как изменение общего состояния системы. Смена состояний происходит последовательно.
Этот подход к моделированию больших параллельных систем имеет ряд недостатков, таких, как громоздкость модели, потеря информации о причинно-следственных связях между событиями в системе, невозможность четкого указания времени начала, длительности и конца событий, происходящих в асинхронных системах.
Выходом может служить отказ от введения в модели систем времени и тактированных последовательностей изменений состояний, а замена их – причинно-следственными связями между событиями. Модели такого типа, в частности сети Петри, называют асинхронными. Замена временных связей причинно-следственными дает возможность более наглядно описать структурные особенности функционирования систем. Если возникает необходимость осуществить привязку ко времени, то моменты или интервалы времени представляют как события. Таким образом, синхронные системы могут описываться в терминах асинхронных моделей.
4.2. Моделирование систем на основе сетей Петри
Отказ от времени приводит к тому, что события в асинхронной модели рассматриваются или как элементарные (неделимые, «мгновенные»), или как составные, имеющие некоторую внутреннюю структуру, образованную из «подсобытий». При неформальном описании функционирования асинхронных моделей, в частности сетей Петри, можно привлекать временные отношения (раньше, позже, не одновременно и т. п.), когда это удобно или привычно, но они представляют собой лишь результаты при- чинно-следственных отношений.
В этом параграфе рассмотрим метод моделирования на основе сетей Петри, а также его применение для моделирования параллельных систем взаимодействующих процессов и решения ряда классических задач из области синхронизации процессов.
Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий. Условие есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь».
Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий, постусловий .
П р и м е р. Моделирование последовательной обработки запросов сервером базы данных. Сервер находится в состоянии ожидания до тех пор, пока от пользователя не поступит запрос клиента, который он обрабатывает и отправляет результат такой обработки пользователю.
Условиями для рассматриваемой системы являются: а) сервер ждет; б) запрос поступил и ждет;
в) сервер обрабатывает запрос; г) запрос обработан.
Событиями для этой системы могут быть:
2. Сервер начал обработку запроса.
3. Сервер закончил обработку запроса.
4. Результат обработки отправляется клиенту.
Для перечисленных событий можно составить таблицу их предусловий и постусловий (табл. 4.1)
Предусловия и постусловия событий
В сети Петри условия моделируются позициями, события – переходами. При этом входы перехода являются предусловиями соответствующего события, выходы – постусловиями.
Возникновение события моделируется запуском соответствующего перехода. Выполнение условия представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет фишки, представляющие выполнение предусловий, и образует новые фишки, которые представляют выполнение постусловий.
Рис. 4.4. Предусловие выполняется для события 2
Сеть Петри на рис. 4.4 иллюстрирует модель приведенного сервера базы данных. Здесь каждому переходу и позиции соответствует определенное событие и условие.
4.2.2. Одновременность и конфликт
Одной из особенностей сетей Петри и систем, моделируемых с их помощью, является параллелизм, или одновременность. В сети Петри два разрешенных невзаимодействующих события могут происходить независимо друг от друга. Синхронизировать события, пока это не потребуется моделируемой системе, нет нужды. Но, когда синхронизация необходима, ее можно легко смоделировать. Таким образом, сети Петри представляются идеальными для моделирования систем с распределенным управлением, в которых несколько процессов выполняются одновременно.
Другая важная особенность сетей Петри – это их асинхронная природа. Как уже отмечалось, в сети Петри отсутствует измерение времени или
4.2. Моделирование систем на основе сетей Петри
течение времени. Это отражает философский подход к понятию времени, утверждающий, что одно из важнейших свойств времени с логической точки зрения – это определение частичного упорядочения событий.
В реальной жизни различные события укладываются в различные интервалы времени и это отражено в модели сети Петри независимостью от времени управления последовательностью событий.
Структура сети Петри такова, что содержит в себе всю необходимую информацию для определения возможных последовательностей событий. Таким образом, на рис. 4.4 событие «Сервер закончил обработку запроса» должно следовать за соответствующим событием «Сервер начал обработку запроса». Однако нет и не требуется никакой информации, связанной с количеством времени, необходимым на выполнение задания.
Выполнение сети Петри (или поведение моделируемой системы) рассматривается как последовательность дискретных событий. Порядок появления событий – одно из возможных, допускаемых основной структурой. Это приводит к явной недетерминированности в выполнении сети Петри. Если в какой-то момент времени разрешено более одного перехода, то любой из нескольких возможных переходов может стать «следующим» запускаемым.
Выбор запускаемого перехода осуществляется недетерминированным образом, т. е. случайно. Эта особенность сети Петри отражает тот факт, что в реальной жизненной ситуации, где несколько действий происходит одновременно, возникающий порядок появления событий не однозначен, т. е. может возникнуть любая из множества последовательностей событий.
При описании и анализе динамического поведения сети Петри, когда определяется последовательность запусков переходов, обычно принимается следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное событие, занимающее нулевое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным . Примитивные события мгновенны и неодновременны .
Непримитивными называются такие события, длительность которых отлична от нуля. Они не являются неодновременными и, следовательно, могут пересекаться во времени. Так как осуществление большинства событий в реальном мире занимает некоторое время, то они являются непримитивными событиями и поэтому не могут должным образом моделироваться переходами в сети Петри. Однако это не приводит к возникновению проблем при моделировании систем. Непримитивное событие может быть представлено в виде двух примитивных событий: «начало непримитивного события», «конец непримитивного события» и условия «непримитивное
событие происходит». Эта ситуация может быть промоделирована с помощью сети, показанной на рис. 4.5.
Непримитивное событие происходит
Сети петри
Модель — это представление, как правило, в математических терминах наиболее характерных черт изучаемого объекта или системы. Сети Петри это инструмент для математического моделирования и исследования сложных систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы. Эта информация может использоваться для оценки моделируемой системы и выработки предложений по ее усовершенствованию. Впервые сети Петри предложил немецкий математик Карл Адам Петри.
1.1. Природа систем, моделируемых сетями Петри.
Сети Петри предназначены для моделирования систем, которые состоят из множества взаимодействующих друг с другом компонент. При этом компонента сама может быть системой. Действиям различных компонент системы присущ параллелизм. Примерами таких систем могут служить вычислительные системы, в том числе и параллельные, компьютерные сети, программные системы, обеспечивающие их функционирование, а также экономические системы, системы управления дорожным движением, химические системы, и т. д.
1.2. Подходы к проектированию систем с помощью сетей Петри.
В одном из подходов к проектированию и анализу систем сети Петри используются, как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху.
Другой подход предполагает построение проекта сразу в виде сети Петри. Методы анализа применяются только для создания проекта, не содержащего ошибок. Затем сеть Петри преобразуется в реальную рабочую систему.
В первом случае необходима разработка методов моделирования систем сетями Петри, а во втором случае должны быть разработаны методы реализации сетей Петри системами.
2. Основные определения
2.1. Теоретико-множественное определение сетей Петри.
В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов 
и множествоммест 
. В графическом представлении сетей переходы изображаются «барьерами», а места — кружками.
. Сеть Петри N является четверкой N=(P,Т,I,O), где
- I: TP* — входная функция, сопоставляющая переходу мультимножество его входных позиций;
- О: T P* — выходная функция, сопоставляющая переходу мультимножество его выходных позиций.
2.2. Маркировка сетей Петри.
Маркировка — это размещение по позициям сети Петри фишек, изображаемых на графе сети Петри точками. Фишки используются для определения выполнения сети Петри. Количество фишек в позиции при выполнении сети Петри может изменяться от 0 до бесконечности. Маркировка сети Петри N=(P,T,I,О) есть функция, отображающая множество позиций P в множество неотрицательных целых чисел Nat (где число из Nat обозначает количество фишек, помещаемых в соответствующую позицию). Маркированная сеть Петри N=(P,Т,I,О,) определяется совокупностью структуры сети Петри (P,T,I,О) и маркировки Графического представления маркированной сети Петри. =. Множество всех маркировок сети Петри бесконечно. Если фишек, помещаемых в позицию слишком много, то удобнее не рисовать фишки в кружке этой позиции, а указывать их количество.