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

Общие сведения о сетях Петри. Исходные понятия.

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

Причинно-следственная связь событий в асинхронных системах задается множеством отношений вида "условия-события".

Построение моделей систем в виде сетей Петри заключается в следующем:

1. Моделируемые процессы описываются множеством событий (действий) и условий определяющих возможность наступления этих событий, а также причинно-следственными отношениями, устанавливаемыми на множестве пар "события-условия".

2. Определяются события-действия, последовательность выполнения которых управляется состояниями системы. Состояния системы задаются множеством условий, формируемых в виде предикатов. Количественно условия характеризуются величиной которая выражается числами натурального ряда.

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

В сетях Петри условия - это позиции, а события - переходы. В соответствии с этим граф сети Петри является двудольным ориентированным мультиграфом. Изображение позиции и перехода на графе показано на рисунке 5.1.

 

а) б)

Рис 5.1. а) − изображение позиции; б) − изображение перехода.

 

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

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

Рис.5.2. Пример графа сети Петри.

 

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

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

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

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

 

а) б)

 

Рис.5.3, а − возбужденный переход, б) − невозбужденный переход.

 

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

 

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

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

		Запись
	Чтение

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

 

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

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

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

 

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

 

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

r

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

 

 

Примеры построения сети Петри

.

Пример 1. В примере рассматривается описание двух взаимодействующих процессов на основе механизма семафоров. Пусть в общей памяти выделен участок длиною единиц, который используется для хранения запросов на выполнение задач. Процессы записи запросов в очередь и выбора их из очереди могут происходить независимо (асинхронно). Описатель очереди содержит четыре элемента: и - число заполненных и свободных ячеек очереди; и - адреса начального и конечного элементов очереди. Алгоритмы записи в очередь и выборки запросов из очереди приведены на рис. 5.9. Запись вида представляет операцию размещения в ячейку очереди с номером , а запись вида - считывание содержимого ячейки и использование его в качестве информации о запросе.

 

6

4

6

Рис. 5.9. а) – алгоритм постановки запроса в очередь;

б) – алгоритм выборки запроса из очереди;

в) – пример состояния очереди в буфере из ячеек.

 

С очередью может работать несколько программ «в очередь» и «из очереди». Для организации корректного использования очереди необходимо исключить одновременный доступ программ к области хранения запросов. Иначе возможны ошибки. Например, два потребителя могут выбрать один и тот же запрос, не выбрав из очереди следующий за ним. Для исключения подобной ситуации параллельные процессы «в очередь» и «из очереди» могут синхронизироваться с помощью семафорных примитивов и . Сеть Петри, описывающая эти параллельные процессы, приведена на рис. 5.10. Содержательный смысл позиций и переходов отражен у этих элементов сети.

Рис. 5.10. Сеть Петри, описывающая параллельные процессы управления буферированием: - создание запроса; - запись запроса в очередь; - выполнение запроса; - выборка запроса из очереди.

 

Позиция - семафор, ограничивающий доступ процесса к очереди. Операции над - переменная увеличивается на 1, если ; - если , то уменьшается на 1, в противном случае процесс блокируется, ожидая состояния семафора . Примитив запрещает доступ процесса в критическую область, а - разрешает.

Аналогично определяются операции над считывающими семафорами и : - если , то уменьшается на 1 и процесс продолжается, иначе он блокируется в текущей точке; - если , то увеличивается на 1 и процесс продолжается.

Пример 2. В данном примере рассматривается ВС (Рис. 5.11), содержащая процессор (П), устройство связи с объектом (УСО) и запоминающее устройство (ЗУ). УСО и П могут работать параллельно.

Рис. 5.11. Однопроцессорная ВС с УСО и ЗУ

 

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

Рис. 5.12. Модель процесса в виде сети Петри

 

Переходы: - ввод данных с ЗУ в ОЗУ; - операция 1; - работа УСО с ОУ и ЗУ; - операция 2; - подготовка ЗУ к работе (установка головок).

Позиции: - П свободен; - ввод данных с ЗУ в ОЗУ выполнен; - операция 1 выполнена; - работа УСО закончена; - УСО свободно; - ЗУ готово к работе; - операция 2 выполнена.

Переход срабатывает, если есть запрос, свободный процессор и готовое к работе ЗУ. Возможность параллельной работы процессора и УСО отражена параллельными ветвями с и . Операция 2 (переход ) выполняется по завершению операции 1 и работы УСО. После срабатывания перехода освобождается процессор, ЗУ и фиксируется метка о завершении процесса. После подготовки ЗУ (переход ) может отрабатываться следующий запрос оператора.

В приведенных примерах сети Петри описывали:

- параллелизм и синхронизацию процессов;

- взаимодействие процессов и ресурсов, представленных метками;

- независимые действия, представленные переходами;

- накопители информации (ячейки и буферы) и состояния процессов, представленные позициями.

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

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

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

В ряде случаев на множестве цветов задают отношения приоритетности и сопоставляют их определенным дугам . Правила возбуждения перехода реализуют приоритетный выбор метки для возбуждения перехода на основе значения соответствующего атрибута – приоритета (цвета) метки. Приоритетные раскрашенные сети адекватно представляют приоритетное обслуживание процессов.

Таким образом, процедура раскраски сети Петри – это модельный способ трактовки различных по характеру реальных элементов: в алгоритмах – номера оператора или этапа обработки; в мультипрограммных системах – номера задачи, ее приоритета и других атрибутов; для ресурсов – их типа, способа использования и т.д.

 

Задачи анализа сетей Петри

 

Анализ заключается в изучении основных свойств сетей Петри: безопасности, ограниченности, сохранении, активности, достижимости и покрываемости. Напомним определение каждого из этих свойств.

 

 

Безопасность. Позиция p_iÎP сети C=(P, T, I, O, M₀) является безопасной, если m(p_i)£I для любой MÎR(C, M₀). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность – важное свойство для аппаратной реализации. Безопасная позиция имеет число меток 0 или 1 и может быть реализована одним триггером.

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

 

Ограниченность. Безопасность – это частный случай более общего свойства ограниченности. Безопасность позволяет реализовать позицию триггером, а в более общем случае можно использовать счетчик. Любой счетчик ограничен по максимальному числу К. Соответствующая позиция также является К-безопасной или К-ограниченной, если количество меток в ней не может превысить целое число К.

Позиция p_iÎP сети C=(P, T, I, O, M₀) является К-безопасной, если m(p_i)£К для всех MÎR(C, M₀).

Позиция называется ограниченной, если она К-безопасна для некоторого К.

Сеть Петри ограничена, если все ее позиции ограничены.

 

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

Сеть Петри называется строго сохраняющей, если для всех MÎR(C, M₀)

выполняется условие:

å m(p_i) = å m₀(p_i).

p_iÎP p_iÎP

 

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

 

Активность. Другой задачей, возникающей при распределении ресурсов, является задача выявления тупиков. Рассмотрим на рис. 5.14 систему, включающую два различных ресурса q и r и два процесса а) и в), нуждающиеся в обоих ресурсах. Каждый процесс запрашивает ресурс, а затем освобождает его. Процесс а) сначала запрашивает ресурс q, затем ресурс r, и освобождает их. Процесс в) работает аналогично, но запрашивает сначала ресурс r, а затем q.

а) в)

 

Рис. 5.14. Иллюстрация наличия тупика

Начальная маркировка помечает ресурсы свободными и готовность процессов к работе. Выполнение сети в последовательности t₁, t₂, t₃, t₄, t₅, t₆ или t₄, t₅, t₆, t₁, t₂, t₃ не приводит к тупику. Если начать с переходов t₁, t₄ то выполнение заблокировано, процесс а) обладает ресурсом q и хочет получить r, процесс в) обладает r и хочет получить q.

Тупик в сети Петри – это переход (или множество переходов), которые не могут быть запущены. Переходы t₂ и t₅ являются тупиковыми. Переход называется активным, если он не заблокирован, то есть потенциально запустимым.

 

Достижимость и покрываемость. Задача достижимости заключается в определении для маркировки M₀ маркировки MÎR(C, M₀). К этой задаче могут сводиться многие перечисленные выше задачи. Например, тупик в сети на рисунке может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

Задача покрываемости. Для сети С с начальной маркировкой M₀ и маркировки M определить, существует ли такая достижимая маркировка M’ÎR(C, M₀), что M’³M.

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

 

Модификации сетей Петри

 

 

Временная сеть Петри

 

Такая сеть позволяет более реалистично отражать процессы в ВС. Во временных сетях каждому переходу t_j сопоставляется время τ_j. Если переход возбуждается, то метки, вызвавшие запуск перехода, покидают входные позиции Pre(t_j). Порождение меток в выходных позициях Post(t_j) происходит через время τ_j.

Формальное определение временной сети:

TN = {N, τ},

где N - сеть Петри; τ: T → R₀ -функция времён срабатывания, сопоставляющая каждому переходу постоянное время срабатывания; R₀ - множество неотрицательных рациональных чисел.

 

Пример взаимодействия двух узлов сети ЭВМ

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

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

Переходам t_j сопоставлены времена τ_j, отражающие длительность выполнения соответствующих действий в системе обработки и обмена, генераторах помех и тайм-аута. отношения приоритетности введены для двух пар переходов – (t­₂,t₈) и (t₇,t₁₁), поскольку только по отношению к ним может возникнуть конфликт за метку. Они имеют вид:

 

PR(t₈) > PR(t₂) и PR(t₇) > PR(t₁₁).

 

 

 

ПрИ – процессор-источник;

ПрП – процессор-приёмник;

ГТ – генератор тайм-аута;

ИП – источник помех;

t₁ - передача сообщений в буфер обмена;

t₂ - приём сообщения;

t₃ - посылка подтверждения о приёме данных;

t₄ - приём подтверждения;

t₅ - обработка данных в ПрИ;

t₆ - обработка в ПрП;

t₇ - повторение передачи;

t₈, t₉ - переходы модели источника помех;

t₁₀, t₁₁ - элементы ГТ;

P₁ - конец обработки в ПрИ и запрос действия t₁;

P₂ - буфер сообщения;

P₃ - ПрП готов принять сообщение и запрашивает t₂;

P₄ - ПрИ ожидает подтверждения;

P₅ - завершение действия t₂ и запуск t₃;

P₆ - запрос t₆;

P₇ - буфер подтверждения;

P₈ - запрос t₅;

P₉, P₁₀ - позиции ГТ;

P₁₁, P₁₂ - позиции ИП;

 

Рис. 5.17. Пример временной сети Петри с приоритетами.

Передача сообщения процессором-источником порождает буферирование копии сообщения и запуск генератора тайм-аута, посылку сообщения в канал, а также формирование условия подтверждения о приёме, что отражается появлением меток в P₂, P₄, P₉. Если сообщение в канале P₂ исчезнет благодаря действию ИП (что отражается возбуждением t₈), то не приходит подтверждение приёма (метка в P₇ не появится), и через время тайм-аута (связанное с t₁₀) произойдёт повторная выдача сообщения в канал (что отражается срабатыванием t₇). С t₉ связан интервал времени между потерей в канале очередного сообщения и возникновением условия для потери следующего сообщения. С t₁₀ связано время тайм-аута, через которое организуется повторная посылка потерянного сообщения. Если через τ₁₀ в P₄ нет метки, то не создадутся условия возбуждения t₇ и метка из P₁₀ покинет ГТ.

 

Рис. 5.18. Граф допустимых маркирований

 

На рисунке изображён граф допустимых маркирований элементов модели ПрП и ПрИ. В вершинах графа состояний перечислены наборы позиций, в которых одновременно находятся метки-сообщения, полученные для начального маркирования M₀. Ориентированные дуги указывают переходы между состояниями системы, а пометки у дуг указывают на переходы t, срабатывание которых вызывает данное изменение состояния.

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

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

 

 

Раскрашенные сети

 

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

Метками раскрашенной сети приписывают атрибуты, которые называют цветами. Правила возбуждения переходов дополняются условиями, предполагающими выбор меток определённых цветов из позиций Pre(t_j). Срабатывание переходов сопровождается посылкой в позиции Post(t_j) меток, с задаваемыми значениями цвета.

 

 

t₁, t₂ - загрузка процессоров;

t₃, t₄ – обработка;

t₅, t₆ - освобождение процессоров

P₀ - позиция супервизора;

P₁, P₂ - заявки на обработку;

P₃, P₄ - Заявки приняты;

P₅, P₆ - конец обработки;

P₇, P₈ - обработанные заявки;

P₉, P₁₀ - двоичные семафоры,

исключающие запуск

занятых процессоров.

 

 

Рис. 5.19. Пример раскрашенной сети для двухпроцессорной системы.

 

На Рис.5.19 приведена модель процессов в двухпроцессорной системе, управляемой супервизором. Множество атрибутов-цветов, связываемых с метками и дугами сети, принято равным С = {λ, C₁, C₂, C₃, C₄}. В сети раскрашена метка, имитирующая работу супервизора и дуги, имитирующие последовательность запуска процессоров. Прочие дуги, а также метки-заявки и метки управления не нарушены.

Начальный цвет метки в P₀ равен C₁ и дуга (P₀,t­₁) окрашена в C₁. Поэтому условие возбуждения выполнимо для перехода t₁. После срабатывания t₁ в P₀ метка возвращается, уже имея цвет C₂, поскольку дуга (t₁,P₀) раскрашена в цвет C₂.

Раскрашивание дуг обеспечивает возбуждение только одного из переходов, следующих за P₀, при любом состоянии системы. При данной раскраске алгоритм работы супервизора представлен последовательностью срабатывания переходов t₁, t₂ (t₃, t₄) t₅, t₆, т. е. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.

Рис. 5.20. Пример раскрашенной сети: а) – граф алгоритма; б) – биграф алгоритма;

в) – модель мультипрограммного выполнения алгоритмов, представленная раскрашенной сетью.

 

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

На Пр и УВВ параллельно могут выполняться операторы 2 и 3, завершение которых является условием выполнения оператора 0, что видно из рис.5.20а. Переходы t₀ – t₃ биграфа (рис. 5.20б) соответствуют вершинам графа на рис. 5.20а. Для отображения точки входа в алгоритм на его биграфе введена маркированная позиция P₁, поэтому нулевой вершине графа (рис. 5.20а) поставлены в соответствие переходы t₀ и t₄ биграфа. При построении сети (рис. 5.20в) учтено, что время выполнения операций t₁ и t₄ мало по сравнению с остальными. Учитывая также, что действия t₀ и t₂ выполняются на процессоре, позиции P₁ и P₅, а также P₂ и P₆ биграфа совмещены на рис.5.20в и обозначены как P₁ и P₂. Процессы выполнения алгоритмов представлены движением меток. Раскраска меток двухэлементная, определяющая номер процесса a = {1, 2, 3} и номер этапа обработки C = {C₀, C₁, C₂, C₃}.

Из рис. 5.20в видно, что некоторые из дуг раскрашены одним цветом (C_i), другие парой цветов (a C_i), третьи не раскрашены вовсе, что учитывается при управлении возбуждением переходов и изменении цвета меток. Заметим, что при раскрашивании парой цветов все эти признаки анализируются или изменяются в комплексе. Например, входные дуги перехода t₄ помечены парами a C₂ и a C₃, что определяет выбор для синхронизации на t₄ процессов с одним и тем же номером a и завершенными этапами обработки C₂ и C₃ соответственно.

Следующий пример (рис. 5.21) показывает изобразительные возможности раскрашенных сетей по разделению путей данных и управления в УВВ. Данные от двух источников U₁ и U₂ помечены квадратами в P₁ и P₃, а сигналы запроса на обработку – кружками в P₂ и P₄. Запросы принимаются (переходы t₁, t₂), накапливаются в регистре (позиция P₅), выбираются из неё (переход t₃) и запускают пересылку данных от источников (P₁ или P₃) в буфер P₇. Метка-треугольник в позиции P₈ отражает управляющий процесс, разрешающий выполнение только одной из двух операций считывания t₄ или t₅. Читателю предлагается самостоятельно разобраться, почему необходимо использовать раскрашенную метку в позиции P₈ и на дугах и .

 

 

 

Рис. 5.21. Пример сети с разделением передачи данных

 

Таким образом, процедура раскраски сети Петри – это модельный способ трактовки различных по характеру реальных элементов:

- в алгоритмах – номера оператора или этапа обработки;

- в мультипрограммных системах – номера задачи, её приоритета и других атрибутов;

- для ресурсов – их типа, способы использования и т. п.

 

 

Общие сведения о сетях Петри. Исходные понятия.

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

Причинно-следственная связь событий в асинхронных системах задается множеством отношений вида "условия-события".

Построение моделей систем в виде сетей Петри заключается в следующем:

1. Моделируемые процессы описываются множеством событий (действий) и условий определяющих возможность наступления этих событий, а также причинно-следственными отношениями, устанавливаемыми на множестве пар "события-условия".

2. Определяются события-действия, последовательность выполнения которых управляется состояниями системы. Состояния системы задаются множеством условий, формируемых в виде предикатов. Количественно условия характеризуются величиной которая выражается числами натурального ряда.

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

В сетях Петри условия - это позиции, а события - переходы. В соответствии с этим граф сети Петри является двудольным ориентированным мультиграфом. Изображение позиции и перехода на графе показано на рисунке 5.1.

 

а) б)