сети Петри
.docТнАрИТС Технологии и архитектура ИТС
Тема А07.01 Основы проектирования Switch
Сети Петри Сети Петри – одно из самых выразительных средств для моделирования процессов, в том числе параллельных, синхронных и асинхронных. Они отражают логическую последовательность событий, позволяют отслеживать потоки данных, отрабатывают взаимодействие процессов. Сеть Петри задается графом, вершины которого разбиты на два подмножества. На рис.*** показан пример такого представления сети.
Рис. ***
Одно из этих подмножеств представляет узлы-позиции (обозначаются кружочками и размечаются символами Pi), другое узлы-переходы (обозначаются черточками и размечаются символами ti). Вершины связанны направленными дугами, которые не помечаются.
Входы и выходы как таковые в сети Петри могут не обозначаться. Ее позиции маркируются (помечаются внутри заштрихованной точкой) и это рассматривается как начальная разметка. Еще это называют размещением по позициям фишек. Количество фишек в позиции может изменяться от 0 до бесконечности. Бесконечность обычно обозначается как .
Сеть Петри выполняется посредством запусков переходов, который управляется фишками.
В каждый конкретный момент может запускаться только один из переходов в том случае, если он разрешен (активен). В принципе, могут быть активными несколько переходов. Но запуститься может один.
Переход называется разрешенным, если каждая из его входных позиций содержит число фишек не меньше числа дуг, ведущих из этой позиции в переход.
Для уяснения принципа функционирования сети Петри рассмотрим более содержательный пример, показанный на рис.***
Рис. ***
Здесь помеченными являются позиции P1 и P3, что обозначается как маркировка (1010). То есть, если в позиции находится фишка, то она маркируется как (1), в противном случае как (0). Маркировка всех вершин представляется в виде вектора (1, 2, …, n), где I терм i-й позиции, а n – число позиций в сети. Переходы данной сети представлены в виде следующего деорева.
В качестве узлов дерева выступают те маркировки, которые реализуются в ходе выполнения сети Петри.
Начальная маркировка является вершиной дерева. При этом активной является только переход t3. Запуск перехода t3 осуществляется тем, что вначале фишка изымается из нее, а затем помещается в позицию p4. Это и констатирует новая маркировка (1001).
Далее активным становится переход t2. Но в этом случае запуск этого перехода сопровождается тем, что изымается одна фишка из позиции p4, а размещается две – одна в позицию p2, а другая в позицию p3.
После этого активными становятся уже два перехода t1 и t3. В этой ситуации может запускаться один из них.
Если мы пойдем по ветви t3, то повторим уже пройденные шаги. Это означает, что сеть Петри попадает в цикл. При этом в позиции p2 будут накапливаться фишки. Причем, такое накопление ничем не ограничено, что и помечается как .
Если мы пойдем по ветви t1, то попадаем в тупик. Дело в том, обнуляется позиция p3. А, следовательно, переход становится t1 запрещенным
Рис. ***
Сеть Петри, у которой нет тупиков, называется «живой». А сеть Петри, у которой нет позиций типа , называется безопасной.
Безопасная и живая сеть Петри называется правильной. Вот этот тип сетей Петри и представляет наибольший интерес.
Пример правильной сети Петри показан на следующем рис.***
Нетрудно видеть, что граф переходов между маркировками есть не что иное как диаграмма автомата, а котором в качестве состояний выступают маркировки. Такая система может находиться только в одном маркированном состоянии. При этом наименования переходов выполняют функции распознаваемых выражений.
Рис. ***
Таким образом, сеть Петри задает язык. По своей выразительной силе такой язык сопоставим с автоматным языком. В то же время каждая маркировка сети Петри задает некоторый взаимоувязанный комплекс фактических значений одновременно нескольких позиций исходной сети.
Граф переходов данной сети показан на рис.****
1000000
t1
0110000
t2 t5
t4
0011010 0100001
t3 t2
0010110 0001011
t5
t3 t4
t6
0001011
Рис. ***
Это делает более богатыми моделирующие свойства сети Петри.
Правильная сеть Петри называется автоматной, если все ее переходы имеют не более одной входящей и не более одной выходящей дуги, а в ее начальной маркировке имеется не более одной метки.
Задание для самостоятельной работы. Постройте и исследуйте автоматную сеть Петри.
2.3.2.Моделирование систем на основе сетей Петри.
Представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. Возникновением событий управляет состояние системы, которое может быть описано множеством условий. Условие может принимать либо значение «истина», либо значение «ложь».
Возникновение события в системе возможно, если выполняются определенные условия – предусловия события. Возникновение события может привести к выполнению других условий – постусловий события. В качестве примера рассмотрим следующую ниже задачу моделирования.
Пример. Моделирование последовательной обработки запросов сервером базы данных. Сервер находится в состоянии ожидания до тех пор, пока от пользователя не поступит запрос, который он обрабатывает и отправляет результат такой обработки пользователю.
Для приведенного описания можно составить соответствующую спецификацию событий и условий , а также таблицу их пред- и постусловий.
Условиями для рассматриваемой системы
являются:
а. сервер ждет;
б. запрос поступил и ждет;
в. сервер обрабатывает запрос;
г. запрос обработан.
Событиями для этой системы являются:
1. Запрос поступил.
2. Сервер начинает обработку запроса.
3. Сервер заканчивает обработку запроса.
4. Результат обработки отправляется.
|
Событие |
Предусловие |
Постусловие |
|
1 |
нет |
б |
|
2 |
а, б |
в |
|
3 |
в |
г, а |
|
4 |
г |
нет |
Такое представление моделируется следующей сетью Петри.
Рис.
В данной сети Петри условия моделируются позициями, события – переходами. При этом входы перехода являются предусловиями соответствующего события; выходы – постусловиями. Возникновение события моделируется запуском соответствующего перехода. Выполнение условия представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет фишки, представляющие выполнение предусловий и образует новые фишки, которые представляют выполнение постусловий.
Пример. Одновременность и конфликт. Рассмотрим сеть Петри.
Рис.
Два перехода данной сети находятся в конфликте то есть запуск одного из них удаляет фишку из общей входной позиции и тем самым запрещает запуск другого. Таким образом моделируются взаимоисключающие события.
Пример. Реализация алгоритма вычисления Y! И произведение всех четных чисел на отрезке [1, Y] для произвольного положительного целого Y.
Программа на абстрактном языке.
Рис.
С
еть
Петри имеет следующий вид
Рис.
2.4. Моделирование взаимодействий процессов сетями Петри.
Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей (разделяемой) памяти; посредством передачи сообщений различных видов.
Их моделирование осуществляется уже получившим известность графо-аналитическими конструкциями на основе сетей Петри.
Далее покажем, как сети Петри могут моделировать различные механизмы синхронизации процессов на основе решения задач, ставших классическими в этой области их применения.
Задача о взаимном исключении. Пусть два процесса разделяют общую переменную, запись, файл или другой элемент данных.
Для обновления разделяемого элемента данных процесс должен сначала считать старое значение, затем вычислить новое и, наконец, записать его на то же место. Если два процесса P1 и P2 в одно и то же время пытаются выполнить такую последовательность действий, то может возникнуть искажение данных.
Для исключения подобных проблем используется метод взаимного исключения, основанный на понятии критической секции. Критическая секция – это участок кода процесса, на котором он осуществляет доступ к разделяемому объекту данных. Прежде чем выполнить свою критическую секцию, процесс ждет, пока другой процесс не закончит выполнение собственной критической секции (если такое выполнение имеет место). Затем он входит в критическую секцию и блокирует доступ для любого другого процесса к своей критической секции. После выполнения процессом критической секции деблокируется доступ для других процессов к разделяемому объекту данных.
Следующая ниже сеть Петри моделирует механизм взаимного исключения для двух процессов P1 и P2.
Рис.
Позиция m представляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P1 (P2) войти в критическую секцию осуществляется после помещения фишки в его позицию s1 (s2). Такая попытка может увенчаться успехом, если в позиции m содержится фишка. Если оба процесса пытаются одновременно войти в критическую секцию, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит запуск перехода t2, вынуждая процесс P2 ждать, пока процесс P1 выйдет из своей критической секции, и возвратит фишку обратно в позицию m.
Задача о производителе/потребителе. В этой задаче также имеет место разделяемый объект – буфер, посредством которого реализуется взаимодействие через асинхронную передачу сообщений. Процесс-производитель создает сообщения, которые помещаются в буфер. Потребитель ждет, пока сообщение не будет помещено в буфер, извлекает его оттуда и использует. Такое взаимодействие может быть промоделировано следующей ниже сетью Петри.
Рис.
Позиция В представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано.
Задача об обедающих мудрецах. Задача об обедающих мудрецах была предложена Дейкстрой и связана с пятью мудрецами, которые попеременно то думали, то ели.
Мудрецы сидят за круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Для приема китайской пищи необходимо две палочки. Поэтому каждый мудрец должен сначала взять палочку слева и палочку справа, а затем приступить к еде. Возможна ситуация, когда каждый мудрец возьмет палочку слева, а затем будет ждать, когда освободится палочка с правой стороны. Так они будут ждать, пока не умрут с голода. Тем самым, это состояние для системы «обедающие мудрецы» является тупиковым.
Проблема тупика в этой системе может быть решена путем следующей модификации ее правил поведения: Пусть мудрец при переходе из состояния размышлений в состояние приема пищи захватывает не по очереди, а одновременно обе палочки (слева и справа), если они свободны. Эта ситуация моделируется следующей сетью Петри.
В этой сети Петри позиции ni, i{1, 2, 3, 4, 5} представляет условие «i-я палочка свободна». В начальной маркировке каждая из этих позиций имеет фишку. Каждому мудрецу i{1, 2, 3, 4, 5} соответствует две позиции: позиция дi – представляющая условие «i-й мудрец думает»; и позиция еi – представляющая условие «i-й мудрец ест». В начальной маркировке каждая позиция дi содержит фишку, а каждая позиция еi пуста.
Рис.
Каждому мудрецу также соответствует два перехода: переход начi – представляющий событие «начало приема пищи i-м мудрецом»; и переход завi – представляющий событие «завершение приема пищи i-м мудрецом».