Формализованное описание сетей Петри.

Р − и V − операции над семафорами

Задача о чтении/записи

Задача об обедающих мудрецах

Задача о производителе/потребителе

Задача о взаимном исключении

Механизмы синхронизации процессов.

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

- задача о взаимном исключении;

- задача о производителе/потребителе;

- задача об обедающих мудрецах;

- задача о чтении/записи;

- - и - операции над семафорами.

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

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

Процесс I Процесс 2

Рис. 5.4. Механизм взаимного исключения

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

Переходы и находятся в конфликте за метку в позиции . Запуск, например, перехода , вынуждает 1-ый процесс ждать, пока 2-ой процесс выйдет из своей критической секции и возвратит метку в позицию .

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

Производитель Потребитель

Рис.5.5. Механизм обмена через буфер

Буферу сопоставлены две позиции: В − указывает на количество компонентов данных размещенных в буфере, но еще не использованных, В° − количество свободных мест в буфере для размещения компонентов данных. Первоначально позиция В° имеет меток, а позиция В не имеет. Если буфер будет полностью заполнен, то в позиции В будет меток, а в В° − 0 меток. Таким образом, доступ процесса-производителя в заполненный буфер невозможен, так как в позиции В° будет 0 меток.

Мудрецы сидят за круглым столом и каждый из них может пребывать в одном из двух состояний: думает или обедает. На столе блюда китайской кухни, а между мудрецами лежит по одной палочке. Для приема пищи мудрец должен взять палочку слева и палочку справа. В этом случае соседи обедающего мудреца могут только думать и ждать, когда освободятся палочки, чтобы приступить к обеду. На рис.5.6 сетью Петри представлено взаимодействие трех процессов (трех мудрецов), состояния которых отражены позициями и : −обедает, − думает. Позиции представляют палочки для еды (разделяемые ресурсы). В исходной маркировке мудрецы думают, а все палочки свободны. При такой исходной маркировке любой из трех мудрецов может приступить к обеду, захватив палочки слева и справа.

Рис.5.6. Механизм разделения ресурса

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

Рис.5.7. Механизм взаимодействия процессов чтения и записи

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

Следует обратить внимание на то, что в данной сети позиция после завершения процессов чтения всегда будет иметь меток и тем самым разрешает запуск процессов записи.

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

Одним из распространенных механизмов синхронизации процессов являются Р - и V - операции над семафорами. Семафор − это переменная, которая может принимать только неотрицательные целые значения. V - операция увеличивает значение на единицу, а Р-операция уменьшает его на единицу. Р-операция может выполняться только в том случае, когда полученное значение семафора остается неотрицательным. Таким образом, если значение семафора равно 0, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит V -операцию. Р- и V -операции определены как примитивные, то есть никакая другая операция не может изменять значения семафора одновременно с ними. На рис.5.8 показано как такие операции моделируются сетью Петри. Каждый семафор моделируется позицией, количество меток r в позиции показывает значение семафора. Р-операции используют позицию семафора в качестве входа, а V-операции в качестве выхода.

Рис.5.8. Механизм семафоров

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

Сеть Петри определяется пятеркой , где

, - множество позиций;

, - множество переходов;

- функция следования;

- функция предшествования;

- начальное маркирование (состояние) сети;

- множество положительных целых чисел.

Функции и задают множества дуг и соответственно.

Дуги, предшествующие позиции , обозначим множеством , а дуги, предшествующие переходу , множеством .

Здесь запись означает наличие дуги , а запись - дуги . Аналогично, дуги, следующие из и , представим множествами , .

Входные позиции перехода объединяются в множества его предшественников , а выходные позиции – в множества позиций–последователей .

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

Срабатывание перехода приводит к тому, что каждая позиция теряет меток, а каждая из позиций получает меток.

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