Ссылки
Wikimedia Foundation . 2010 .
Полезное
В учебно-методическом пособии изложены основы теории сетей Петри, принципы построения моделей систем в виде сетей Петри, методы определения их свойств и анализа динамических свойств моделируемых систем.
Пособие содержит задания к лабораторной работе и порядок ее выполнения.
Составитель Кирюшин О.В., доц., канд. техн. наук
Рецензент Новоженин А.Ю., ст. преподаватель
ã Уфимский государственный нефтяной технический университет, 2006
Изучение сетей Петри как методологии описания динамических свойств систем.
Краткие теоретические сведения
Сети Петри (СП) являются примером семантических сетей, представленных разновидностью ориентированных двудольных графов и предназначенных для моделирования динамических свойств различных систем (систем отношений между людьми, последовательностей действий при выполнении какой-либо работы и т.д.).
Двудольный граф включает вершины двух типов: позиции (обозначаются кружками) и переходы (обозначаются планками). Сеть Петри может быть формально представлена как совокупность множеств:
Gp-t = (p´t), Gt-p = (t´p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам (дуг, соединяющих однородные вершины, не существует);
где М0 – начальная маркировка сети.
При моделировании процессов принятия решений с помощью СП ее позиции интерпретируют собой некоторые условия, состояния, значения переменных и т.д. Переходы интерпретируют собой логические предложения (принятие решений), соответствующие выполнению действий, при этом входные позиции – условия выполнения действий, выходные позиции – результат выполнения действий. Действие (переход) связано с принятием какого-либо решения, которое инициировано определенными условиями и результатом которого является новое состояние (условие).
Другими словами, позиция – это имя существительное, а переход – глагол.
Пример. Схема принятия решений при попытке получить деньги из банкомата (см. рисунок 1).
Рисунок 1 – Пример сети Петри
Роль указателей мощности потоков выполняют маркеры (●), также именуемые фишками и метками. Формально маркер – это знак выполнения соответствующего условия. В приведенном примере позиции Р1 и Р2 содержат по одному маркеру, что говорит о наличии одной карточки на руках и одного исправного банкомата. В позиции Р3 маркера пока нет, т.е. банкомат пока не запрашивает код.
При выполнении условий переходы срабатывают, что приводит к перемещению маркеров по сети.
Правило срабатывания перехода: Переход срабатывает только в том случае, если во всех входных позициях имеется достаточное количество маркеров (по меньшей мере, по одному). При срабатывании перехода из входных позиций изымаются маркеры (в случае взвешенной СП изымается количество маркеров, соответствующее весам дуг, связывающих входные позиции с данным переходом), а в выходные – добавляются (для взвешенной СП – также соответственно весам дуг). Начальная маркировка СП есть начальное состояние системы. При срабатывании каждого перехода маркировка сети меняется.
Так, при срабатывании перехода t1 в рассматриваемом примере (банкомат принимает карту и делает запрос кода) изымаются маркеры из позиций Р1 и Р2 и помещается один маркер в позицию Р3. Это символизирует отсутствие карты на руках (она в банкомате) и свободного банкомата (вторую карту в него ввести нельзя), но при этом уже запрошен код.
В случае взвешенной СП количество перемещаемых маркеров соответствует весам дуг. Если во входной позиции маркеров больше, чем вес дуги, то забирается только часть маркеров. Например, при срабатывании перехода t11 (рисунок 2,а) маркировка изменяется соответственно (рисунок 2,б). Видно, что общее число маркеров в сети изменилось.
В сети на рисунке 3 переход не сработает из-за недостатка маркеров в одной из входных позиций.
Рисунок 2 – Срабатывание перехода
Таким образом, если осуществить начальную маркировку СП, то использованием формальных правил можно описать логику работы системы и произвести анализ ее работоспособности. Переходы маркеров описываются графом достижимости(ГД), у которого каждой вершине соответствует определенная маркировка, а каждой дуге – переход, который срабатывает при данной маркировке.
Таким образом, граф достижимости представляется как
где V – массив вершин (маркировок, соответствующих вершинам):
Мi – i-я маркировка, q – количество маркировок;
Алгоритм построения графа по исходной СП:
2.2 Для каждого разрешенного перехода или комбинации переходов производятся следующие действия:
2.2.1 Определяется маркировка М’, которая образуется при срабатывании данного перехода (комбинации переходов).
2.2.3 Просматриваются все маркировки графа. Если находится маркировка, равная новой, то в массив Е записывается новая дуга, у которой a1 = a2 и равны номеру найденной маркировки.
2.2.4 Если в п.п. 2.2 и 2.3 маркировки не найдены, то создается новая вершина графа, в которую записывается новая маркировка, в массив Е записывается дуга, у которой a1 равна номеру исходной маркировки, a2 — номеру новой маркировки, Т – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. 2.2.
Для рассмотренного выше примера СП граф ГД имеет вид (рисунок 4), список маркировок приведен в таблице 1.
С помощью ГД могут быть определены свойства СП и, в конечном счете, моделируемой системы. К ним относятся:
— живость (отсутствие тупиковых состояний);
— правильность (если сеть безопасная и живая, то она правильная);
— обратимость (сеть обратима, если в графе имеется хотя бы одна дуга, направленная к начальной маркировке М0);
— пассивность переходов (переход ti пассивен, если он не соответствует ни одной дуге графа);
— число возможных состояний Nсост.
Сеть Петри называется k-ограниченной, если в любом состоянии в любой позиции скапливается не более k фишек.
Любая система должна представляться правильной сетью.
Для рассмотренного примера можно сделать вывод, что сеть правильная, обратимая и без пассивных переходов.
Практическое значение и наиболее ясную интерпретацию имеют два вида СП:
1) маркированные графы – каждая позиция такой СП должна иметь не более одного входного и одного выходного перехода;
2) автоматные сети (А-сети) – каждый переход такой СП должен иметь не более одной входной и одной выходной позиции.
3) сеть со свободным выбором (ССВ) – это ординарная сеть Петри, в которой каждая дуга из любой позиции представляет собой или единственную выходящую дугу, или единственную входящую дугу для какого-либо перехода.
СП моделируют очень широкий класс логических задач. Существует много разновидностей сетей. Главное их достоинство – возможность анализировать логический процесс по неизбыточным моделям. Кроме того, формализованные методы анализа СП в сочетании с возможностью декомпозиции дают возможность решать очень сложные задачи принятия решений.
Сети Петри — инструмент исследования систем. Теория сетей Петри делает возможным моделирование системы математичегким представлением ее в виде сети Петри. Предполагается, что анализ сетей Петри поможет получить важную информацию о структуре и динамическом поведении моделируемой системы. Эта информация будет полезна для оценки моделируемой системы и выработки предложений по ее усовершенствованию и изменению. Таким образом, понятно, почему развитие сетей Петри основывалось на применении их к моделированию и проектированию систем.
Моделирование
Применяются сети Петри исключительно в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель — это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Ожидается, что, манипулируя представлением, можно получить новые знания о моделируемом явлении, избегая опасности, дороговизну или неудобства манипулирования самим реальным явлением. Моделирование применяется в астрономии (где модели рождения, смерти и взаимодействия звезд позволяют разрабатывать теории, имеющие дело с большими промежутками времени и огромными количествами материи и энергии), ядерной физике (где изучаемые радиоактивные атомы и элементарные частицы существуют в течение очень коротких периодов времени), социологии (где непосредственное воздействие на изучаемые группы людей связано с этическими проблемами), в биологии (где модели биологических систем требуют для развития меньшего пространства, времени и питательного вещества) и т. д.
Как правило, модели имеют математическую основу. Характеристики многих физических явлений можно описать числами, а связь этих характеристик — уравнениями или неравенствами. В частности, в естественных науках и технике уравнениями описываются такие характеристики, как масса, положение в пространстве, момент, ускорение и силы. Однако для успешного использования подхода моделирования необходимо знание как моделируемых явлений, так и свойств метода моделирования. Поэтому математика как наука развивалась частично благодаря использованию ее в моделировании явлений, изучаемых другими науками. Так,
например, дифференциальное исчисление появилось в ответ на необходимость в средствах моделирования в физике таких непрерывно изменяющихся характеристик, как положение в пространстве, скорость и ускорение.
С разработкой быстродействующих ЭВМ использование и полезность моделирования значительно возросли. Представление системы математической моделью, преобразование этой модели в команды для ЭВМ и выполнение программы на ЭВМ сделали возможным моделирование больших и более сложных систем, чем ранее. Это привело в результате к «значительным исследованиям методов моделирования на ЭВМ и самих ЭВМ, поскольку они участвуют в моделировании в двух ролях: как вычислительные средства и как объект моделирования.
Природа систем
Вычислительные системы очень сложны, часто велики, включают множество взаимодействующих компонент. Каждая компонента также может быть очень сложной, поскольку взаимодействует с другими компонентами системы. Это справедливо и для многих других систем. Экономические системы, юридические системы, системы управления дорожным движением, химические системы состоят из многих отдельных компонент, взаимодействующих друг с другом сложным образом.
Действиям компонент системы присущи совмещенность или параллелизм. Действия одной компоненты системы могут производиться одновременно с действиями других компонент. В
вычислительной системе, например, под управлением ЭВМ могут параллельно действовать такие периферийные устройства, как устройства чтения с карт, построчно печатающие устройства и др. В экономической системе в одно и то же время производители поставляют одну продукцию, тогда как продавцы сбывают другую, а покупатели используют третью.
Совмещенная природа действий в системе создает некоторые трудности при моделировании. Поскольку компоненты системы взаимодействуют, необходимо установление синхронизации. Пересылка информации или материалов от одной компоненты к другой требует, чтобы действия включенных в обмен компонент были во время взаимодействия синхронизированы. Это может привести к тому, что одна компонента будет ждать другую компоненту. Согласование во времени действий различных компонент может быть очень сложным, а получающиеся в результате взаимодействия между компонентами трудны в описании.
Зарождение теории сетей Петри
Работа Петри привлекла также внимание группы, работающей над Проектом MAC в Массачусетском технологическом институте (МТИ). Руководимая профессором Дж. Б. Деннисом группа вычислительных структур стала источником значительных исследований и публикаций по сетям Петри, были написаны несколько Диссертаций на степень доктора философии и множество отчетов и меморандумов (см. библиографию). Группой вычислительных структур были проведены две большие конференции по сетям Петри: Конференция Проекта MAC по параллельным системам и
За последние несколько лет использование и изучение сетей Петри значительно расширились. В 1977 г. в Париже и в 1979 г. в Гамбурге на лекциях по общей теории сетей проводились заседания рабочей группы по сетям Петри. В ФРГ была образована группа интереса по сетям Петри. Исследования и применения сетей Петри расширяют сферу действия.
Применение теории сетей Петри
Возможно несколько путей практического применения сетей Петри при проектировании и анализе систем. В одном из подходов сети Петри рассматриваются как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Любые трудности, встречающиеся при анализе, указывают на изъяны в проекте. Для их исправления необходимо модифицировать проект. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху. Такой подход иллюстрируется на рис. 1.1. Заметим, что его можно использовать и для анализа уже существующих действующих в настоящее время систем.
В этом общепринятом подходе использования сетей Петри в проектировании требуется постоянное преобразование проектируемой системы в модель в виде сети Петри. Можно предложить другой, более радикальный подход, в котором весь процесс проектирования и определения характеристик проводится в терминах сетей Петри. Методы анализа применяются только для создания проекта сети Петри, свободного от ошибок. Здесь задача заключается в преобразовании представления сети Петри в реальную рабочую систему.
Эти два подхода использования сетей Петри в процессе проектирования предлагают исследователю сетей Петри задачи разного типа. В первом случае необходима разработка методов моделирования систем сетями Петри, а во втором случае должны быть разработаны методы реализации сетей Петри системами. В обоих случаях необходимы методы анализа сетей Петри для определения свойств модели. Таким образом, первое, чего нам необходимо коснуться при рассмотрении теории сетей Петри, — это изучение свойств самих сетей Петри.
Рис. 1.1. Использование сетей Петри для моделирования и анализа систем. Сначала система моделируется сетью Петри, затем модель анализируется. Оценка системы, являющаяся результатом анализа, приведет, как ожидается, к лучшей системе. Необходимы исследования, направленные на разработку автоматических методов моделирования и анализа систем сетями Петри.
Прикладная и чистая теории сетей Петри
Развитие теории сетей Петри проводилось по двум направлениям. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы. Успешная работа в этом направлении требует хорошего знания области применения, сетей Петри и методов теории сетей Петри.
Чистая теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Хотя мотивация исследований по сетям Петри связана с приложениями, для применения сетей Петри необходим прочный теоретический фундамент. Большая часть работ по сетям Петри к настоящему времени относится к фундаментальной теории сетей Петри, развивающей средства и методы, которые окажутся некогда полезными для применения сетей Петри к конкретным реальным задачам. В этой книге представлены обе области теории сетей Петри (чистая и прикладная), но внимание будет сконцентрировано главным образом на основах теории. Раскрываемые приложения предназначены в основном для демонстрации широты применения и силы теории сетей Петри и обоснования разработки методов анализа.
Мы не будем пытаться раскрыть глубоко весь диапазон тем теории сетей Петри, а скорее постараемся обеспечить прочную основу в терминах, понятиях, методах, результатах и истории сетей Петри для того, чтобы специалисты и аспиранты, специализирующиеся в вычислительной технике, могли разобраться во всевозрастающем потоке литературы по сетям Петри и были способны применить эту теорию к еще более широкому спектру приложений. Мы начинаем с нескольких формальных определений и примеров в гл. 2 и
показываем далее в книге их силу и полезность. Заканчиваем аннотированной библиографией, охватывающей большинство публикаций по сетям Петри.
Замечания к литературе
Возможно несколько путей практического применения сетей Петри при проектировании и анализе систем. В одном из подходов сети Петри рассматриваются как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Любые трудности, встречающиеся при анализе, указывают на изъяны в проекте. Для их исправления необходимо модифицировать проект. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху. Заметим, что этот подход можно использовать и для анализа уже существующих действующих в настоящее время систем.
Эти два подхода использования сетей Петри в процессе проектирования предлагают исследователю сетей Петри задачи разного типа. В первом случае необходима разработка методов моделирования систем сетями Петри, а во втором случае должны быть разработаны методы реализации сетей Петри системами. В обоих случаях необходимы методы анализа сетей Петри для определения свойств модели. Таким образом, первое, чего нам необходимо коснуться при рассмотрении теории сетей Петри, — это изучение свойств самих сетей Петри.
Структура сети Петри
Сеть Петри состоит из четырех элементов: множество позиций Р, множество переходов Т, входная функция I и выходная функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj), называемых входными позициями перехода. Выходная функция О отображает переход tj в множество позиций O(tj), называемых выходными позициями перехода.
Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.
Позиция рi является входной позицией перехода tj в том случае, если piÎI(tj), pi является выходной позицией, если piÎO(tj). Входы и выходы переходов представляют собой комплекты позиций. Комплект является обобщением множества, в которое включены многократно повторяющиеся элементы – тиражированные элементы. В приложении 1 содержится описание теории комплектов. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции быть кратным входом либо кратным ‘ выходом перехода. Кратность входной позиции pi для перехода tj есть число появлений позиции во входном комплекте перехода, #(pi,I(tj)). Аналогично кратность выходной позиции pi для перехода tj есть число появлений позиции в выходном комплекте перехода, #(pi,O(tj)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.
Входные и выходные функции используются для отображения позиций в комплекты переходов, а также их можно использовать для отображения переходов в комплекты позиций. Определим, что переход tj является входом позиции pi, если pi есть выход tj. Переход tj есть выход позиции pi, если pi есть вход tj.
Определение 2. Определим расширенную входную функцию I и выходную функцию таким образом, что #(tj, I(pi)) = #(pi, I(tj)), #(tj, O(pi)) = # (pi, I(tj)).
C = (P, T, I, O),
Рис.6.1. Структура сети Петри представлена в виде четверки, которая состоит из множества позиций (Р), множества переходов (Т), входной функции (
) и выходной функции (
Графы сетей Петри
В значительной степени теоретическая работа по сетям Петри основана на формальном определении сетей Петри, изложенном выше. Тем не менее для иллюстрации понятий теории сетей Петри гораздо более удобно графическое представление сети Петри. Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф.
Структура сети Петри представляет собой совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя типами узлов. Кружок О является позицией, а планка ½ – переходом.
Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие – от переходов к позициям. Дуга, направленная от позиции pi к переходу tj определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Следует добавить, что так как дуги являются направленными, то это ориентированный мультиграф. Мы знаем, что вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом. В дальнейшем для простоты будем называть его просто графом сети Петри.
Граф сети Петри, изображенный на рис.5.2, эквивалентен структуре сети Петри из выше приведенного примера.
Для графов с большой кратностью используется пучок дуг, помеченный числом кратности, а не изображением кратных дуг (рис.5.3).
Маркировка сетей Петри
Маркировка m есть присвоение фишек позициям сети Петри. Фишка – это примитивное понятие сетей Петри (подобно позициям и переходам). Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Петри могут изменяться. Фишки используются для определения выполнения сети Петри.
Определение 3. Маркировка m сети Петри С = (Р, Т, I, O) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N:
m: P ® N
Маркированная сеть Петри М = (С, m) есть совокупность структуры сети Петри С = (Р, Т, I, O) и маркировки m и может быть записана в виде М = (Р, Т, I, O, m).
На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис.5.4 приведен пример графического представления маркированной сети Петри, аналогичной на рис.5.2 с маркировкой (1, 2, 0, 0, 1).
Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей n позициями, есть множество всех n-векторов, Nn. Это множество, хотя и бесконечно, является счетным.
Рис.5.5 Граф сети Петри с очень большой маркировкой.
Правила выполнения сетей Петри
Выполнением сети Петри управляют количество и распределение фишек в сети. Фишки находятся в кружках и управляют выполнением переходов сети. Сеть Петри выполняется посредством запусков переходов. Переход запускается удалением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции.
Запуск перехода в целом заменяет маркировку m сети Петри на новую маркировку
Определение 5. Переход tj маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода tj образуется новая маркировка
, определяемая следующим соотношением:
Пространство состояний сети Петри
Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т. е. Nn. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения d, которую мы назовем функцией следующего состояния. Когда эта функция применяется к маркировке m (состоянию) и переходу tj, она образует новую маркировку (состояние), которая получается при запуске перехода tj в маркировке m. Так как tj может быть запущен только в том случае, когда он разрешен, то функция d(m, tj) не определена, если tj не разрешен в маркировке m. Если же tj разрешен, то
Определение 6. Функция следующего состояния d: Nn´T®Nn для сети Петри С = (Р, Т, I, O) с маркировкой m и переходом tjÎT определена тогда и только тогда, когда m(pi) ³ #(pi, I(tj)) для всех piÎP. Если d(m, tj) определена, то
Пусть дана сеть Петри С = (Р, Т, I, O) с начальной маркировкой m. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tj в начальной маркировке образует новую маркировку
. В этой новой маркировке можно запустить любой другой разрешенный переход, например tk, образующий новую маркировку
. Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.
Пусть некоторый переход в маркировке m разрешен и, следовательно, может быть запущен. Результат запуска перехода в маркировке m есть новая маркировка m’. Говорят, что m’ является непосредственно достижимой из маркировки m, иными словами, состояние m’ непосредственно получается из состояния m.
Определение 7. Для сети Петри С = (Р, Т, I, O) с маркировкой m маркировка m’ называется непосредственно достижимой из m, если существует переход tjÎT, такой, что d(m, tj) = m’.
Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если m’ непосредственно достижима из m, а m» – из m’, говорят, что m» достижима из m. Определим множество достижимости R(C, m) сети Петри С с маркировкой m как множество всех маркировок, достижимых из m. Маркировка m’ принадлежит R(C, m), если существует какая-либо последовательность запусков переходов, изменяющих m на m’. Отношение «достижимости» является рефлексивным, транзитивным замыканием отношения «непосредственной достижимости».
Определение 8. Множество достижимости R(C, m) дли сети Петри С = = (Р, Т, I, O) с маркировкой m есть наименьшее множество маркировок, определенных следующим образом:
1. m Î R(C, m);
2. Если m’ Î R(C, m) и m» = d(m, tj) для некоторого tj Î T, то m» Î R(C, m).
События и условия
Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий. Условие – есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь».
Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение ; предусловий и может привести к выполнению других условий, постусловий.
В качестве примера рассмотрим задачу моделирования простого автомата–продавца. Автомат–продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиями для такой системы являются: а) автомат–продавец ждет; б) заказ прибыл и ждет; в) автомат–продавец выполняет заказ; г) заказ выполнен. Событиями будут: 1. Заказ поступил. 2. Автомат–продавец начинает выполнение заказа. 3. Автомат–продавец заканчивает выполнение заказа. 4. Заказ посылается на доставку. Предусловия события 2 (автомат–продавец начинает выполнение заказа) очевидны: (а) автомат–продавец ждет; (б) заказ прибыл и ждет. Постусловие для события 2: (в) автомат–продавец выполняет заказ. Аналогично мы можем определить предусловия и постусловия для других событий и составить следующую таблицу событий и их пред– и постусловий:
Такое представление системы легко моделировать сетью Петри. В сети Петри условия моделируются позициями, события – переходами. При этом входы перехода являются предусловиями соответствующего события; выходы – постусловиями. Возникновение события равносильно запуску соответствующего перехода. Выполнение условия представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет разрешающие фишки, представляющие выполнение предусловий и образует новые фишки, которые представляют выполнение постусловий.
Сеть Петри на рис.6.6 иллюстрирует модель приведенного выше автомата–продавца.
Рис.5.6. Сеть Петри для простого автомата–продавца
ЭВМ с конвейерной обработкой
Возможность моделировать параллелизм и довольно простого объединения подсистем, представленных сетями Петри, делают сети Петри весьма полезным инструментом моделирования сложной аппаратуры вычислительных систем. Вычислительные системы состоят из многих компонент. Это делает сеть Петри наиболее подходящим средством для их представления.
На протяжении ряда лет было предпринято много попыток увеличения производительности вычислительных систем путем параллельного выполнения нескольких функций. Примером такого подхода к построению высокопроизводительной ЭВМ является использование конвейерной обработки. Этот метод обработки подобен функционированию сборочного конвейера и особенно удобен для работы с векторами и массивами. Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция k завершается, она передает свой результат операции (k + 1) и ожидает от операции (k — 1) нового задания. Если каждая операция занимает t единиц времени и всего существует n операций, то завершение обработки одного операнда потребует nt единиц времени. Однако, если на конвейерную обработку продолжают поступать новые операнды, результаты могут выдаваться со скоростью один каждые t единиц времени.
В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают:
1. Выделить экспоненты обоих чисел.
2. Сравнить экспоненты и изменить, если необходимо, должным образом порядок большей и меньшей экспонент.
3. Сдвинуть точку в числе с меньшей экспонентой для их уравнения.
4. Сложить дроби.
5. Нормализовать результат.
6. Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата.
Каждый из этих шагов может быть выполнен отдельным вычислительным блоком, где каждый отдельный операнд передается от блока к блоку для выполнения операции сложения. Это позволит выполнять до шести сложений одновременно.
Координацию различных блоков можно осуществлять несколькими способами. Обычно управление конвейерной обработкой является синхронным: время, отпущенное на выполнение каждого шага конвейера t, постоянно и фиксировано. Каждые t единиц времени результат каждого блока перемещается по конвейеру, чтобы стать входом для следующего блока. Однако при синхронном подходе обработка может быть приостановлена без необходимости, так как требуемое время может изменяться от блока к блоку, а также внутри данного блока для различных входов. Например, для выполнения шага нормализации результата при сложении чисел с плавающей точкой может потребоваться различное количество времени в зависимости от того, на сколько разрядов необходимо произвести нормализующий сдвиг и в какую сторону: вправо или влево. В этом случае, поскольку время t должно быть выбрано максимальным, необходимым для самого медленного блока конвейера, может оказаться так, что большую часть времени все единицы будут пребывать незагруженными, ожидая окончания t единиц времени.
· входной регистр заполнен; входной регистр пуст;
· выходной регистр заполнен; выходной регистр пуст;
· блок занят;
· блок свободен;
· пересылка осуществлена.
На рис.5.7 и 5.8 показано, как можно промоделировать асинхронный конвейер такого типа. На рис. 5.7 приведена блок-схема конвейера, моделируемого сетью Петри на рис. 5.8.
Отметим, что в этой модели мы промоделировали реальную работу блоков конвейера как непримитивных событий. Это позволяет нам игнорировать на этом уровне конкретные детали того, что делают блоки, и сосредоточиться на их правильном взаимодействии. Каждая операция также может быть промоделирована сетью Петри. Затем сети Петри для каждого блока можно внести в сеть Петри на рис. ???, получив более детальную сеть. Такая возможность моделирования системы на нескольких различных уровнях абстракции, т. е. иерархическим образом, может быть весьма полезна.
Задача о взаимном исключении
Предположим, что несколько процессов разделяют общую переменную, запись, файл или другой элемент данных. Этот разделяемый элемент данных может использоваться процессами различными способами, упрощенно их можно классифицировать как чтение значения элемента данных или запись нового значения. Эти две операции являются часто единственными примитивными операциями. Это означает, что для обновления разделяемого элемента данных процесс должен сначала считать старое значение, затем вычислить новое и, наконец, записать его на то же место. Если два процесса в одно и то же время пытаются выполнить такую последовательность действий, то могут возникнуть трудности. Возможна следующая последовательность:
1. Первый процесс считывает значение х из разделяемого объекта;
2. Второй процесс считывает значение х из разделяемого объекта;
3. Первый процесс вычисляет новое значение х’ = f(x);
4. Второй процесс вычисляет новое значение х» = g(x);
5. Первый процесс записывает х’ в разделяемый объект;
6. Второй процесс записывает х» в разделяемый объект, уничтожая значение х’.
Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им должно быть либо g(f (х)), либо f(g(x)). (Представьте себе, что g(x) – «снять со счета х тысяч долл.», f(x) – «поместить на счет х тысяч долл.», а процессы 1 и 2 – банковские операции.)
Рис.5.10. Взаимное исключение.
Задача о производителе/потребителе
В задаче о производителе/потребителе также присутствует совместно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель создает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и использует. Такая ситуация может быть промоделирована сетью Петри так, как показано на рис.5.11. Позиция B представляет собой буфер, каждая фишка соответствует элементу данных, который произведен, но еще не использован.
Рис.5.11. Задача о производителе/потреьителе
Один из вариантов этой задачи – это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис.5.12 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис.5.11, за исключением того, что для представления s производителей и t потребителей мы начали выполнение сети с s фишками в начальной позиции процесса-производителя и t фишками в начальной позиции процесса-потребителя. Таким образом мы представляем s производителей и t потребителей, реализуемых реентерабельными совместно используемыми программами. Альтернативой было бы дублирование программного кода для процессов производителя и потребителя, однако результатом этого при том же самом поведении была бы гораздо большая сеть.
В другом варианте задачи о производителе/потребителе используется буфер ограниченного размера. При такой постановке задачи буфер между производителем и потребителем ограничен, т. е. имеет только n ячеек для элементов данных. Следовательно, производитель не может постоянно работать с той скоростью, которая ему нужна, а вынужден ждать, если потребитель работает медленно и буфер заполнен. На рис.5.13 показано решение этой проблемы. Ограниченному буферу сопоставляются две позиции: B представляет количество элементов данных, которые произведены, но еще не использованы (число заполненных ячеек). B’ – количество пустых ячеек в буфере. Первоначально B’ имеет n фишек, а B фишек не имеет. Если буфер заполнен, то B’ фишек не имеет, а B имеет n фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то. он будет остановлен, так как в В’ нет фишки, делающей этот переход разрешенным.
Химические системы – другой пример систем, которые могут быть промоделированы сетями Петри. Химические уравнения моделируются переходами; вещества, участвующие в реакции, – позициями. Количество фишек в позиции указывает на количество данного вещества в системе. Например, сеть Петри на рис.5.14 представляет два химических уравнения:
Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, – безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1. Сеть Петри безопасна, если безопасны все позиции сети.
Определение 10. Позиция piÎP сети Петри С= (Р, Т, I, O) с начальной маркировкой m является безопасной, если m’£1 для любой m’ Î R(C, m). Сеть Петри безопасна, если безопасна каждая ее позиция.
Безопасность – очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.
В первоначальном определении сети Петри были безопасны, поскольку переход не мог быть запущен, если не все из выходных позиций были пусты (а кратные дуги не были разрешены). Это объяснялось интерпретацией позиции как условия. Условие, будучи логическим высказыванием, либо истинно (представляется фишкой в позиции), либо ложно (представляется отсутствием фишки); кратные фишки не имеют никакой интерпретации. Таким образом, если интерпретировать сети как условия и события, маркировка каждой позиции должна быть безопасной.
Если позиция не является кратной входной или кратной выходной для перехода, ее можно сделать безопасной. К позиции pi, которую необходимо сделать безопасной, добавляется новая позиция p’i. Переходы, в которых pi используется в качестве входной или выходной, модифицируются следующим образом:
Если piÎ I(tj) и pi Ï O(tj), тогда добавить p’i к O(tj).
Если pi Î O(tj) и pi Ï I(tj), тогда добавить p’i к I(tj).
Цель введения этой новой позиции p’i – представить условие «pi пуста». Следовательно, pi и p’i дополнительны; pi имеет фишку, только если p’i не имеет фишки и наоборот. Любой переход, удаляющий фишку из pi, должен помещать фишку в p’i, а всякий переход, удаляющий фишку из pi, должен помещать фишку в p’i. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в pi, либо в p’i. (Мы допускаем, что начальная маркировка безопасна.) Заметим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна 0 или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной. Простая сеть Петри на рис.5.15 реобразована в безопасную, как показано на рис.6.16
Безопасность – это частный случай более общего свойства ограниченности. Некоторые соображения относительно реального ограничения на аппаратную, реализацию позиций позволяют прийти к заключению, что безопасность – необязательное требование. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно реализованный счетчик ограничен по максимальному числу, которое он может представить. Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.
Определение 11. Позиция pi Î P сети Петри С = (Р, Т, I, O) с начальной маркировкой m является k-беэопасной, если m'(pi) £ k для всех m’ Î R(C, m).
Иногда нас будет интересовать только то, является число фишек в позиции ограниченным или нет, а не конкретное значение границы. Позиция называется ограниченной, если она k–безопасна для некоторого k; сеть Петри ограниченна, если все ее позиции ограниченны. Ограниченную сеть Петри можно реализовать аппаратно, тогда как сеть Петри с неограниченными позициями в общем cлучае реализовать аппаратно нельзя.
В этом разделе мы представим два основных метода анализа сетей Петри, которые описывают механизмы решения некоторых из уже перечисленных задач. Первый метод анализа, используемый для сетей Петри, – это дерево достижимости, второй метод связан с. матричными уравнениями. Обсудим каждый из них.
Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис.5.17. Начальная маркировка ее – (1, 0, 0). В этой начальной маркировке разрешены два перехода: t1 и t2. Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достижимости для (достижимых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис.5.18). Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.
Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, 0) можно снова запустить t1 (получая (1, 2, 0)) и t2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t3 (получая (0, 0, 1)). Это порождает дерево, изображенное на рис.5.19. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рис.5.20.
Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1,1), порождаемая запуском t3 в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском t2.
Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся дерево достижимости может оказаться бесконечным. Будет порождена каждая маркировка из множества достижимости, поэтому для любой сети Петри с бесконечным множеством достижимости соответствующее дерево также должно быть бесконечным. Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево (рис.5.21).
Рис.5.21. Простая сеть Петри с бесконечным деревом.
Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера.
Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки – маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве.
В сети Петри на рис.5.16, например, можно запустить переход t1 столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в p2.
Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа w, который обозначает «бесконечность». Для любого постоянного a определим
Для построения дерева достижимости необходимы только эти операции над w.
Алгоритм начинает работу с определения начальной маркировки корнем дерева, т. е. граничной вершиной. До тех пор пока имеются граничные вершины, они обрабатываются алгоритмом.
Пусть х – граничная вершина, которую необходимо обработать.
В лекции «6 — Пневмомоторы» также много полезной информации.
Дуга, помеченная tj, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина z становится граничной.
Когда все вершины дерева – терминальные, дублирующие или внутренние, алгоритм останавливается.
На рис.5.22 представлено дерево достижимости для сети Петри на рис.5.16.
