99658

Сети Петри

Лабораторная работа

Коммуникация, связь, радиоэлектроника и цифровые приборы

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

Русский

2016-10-06

1.22 MB

2 чел.

ЛЕКЦИЯ 5 (6 часов). СЕТИ ПЕТРИ

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

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

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

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

  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.2 Механизмы синхронизации процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Рис. 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 и работы УСО. После срабатывания перехода  освобождается процессор, ЗУ и фиксируется метка о завершении процесса. После подготовки ЗУ (переход ) может отрабатываться следующий запрос оператора.

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

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

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

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

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

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

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

Методы анализа характеристик сетей.

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

Приведем определения некоторых характеристик сетей и их смысловое толкование применительно к задачам анализа систем.

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

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

Переход  называют живым, если он достижим в  из любого , где  - множество достижимых маркирований сети.

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

Позицию  называют -ограниченной, если существует неотрицательное целое , такое что :, где  - число меток в позиции .

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

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

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

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

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

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

                              ;      ,

где  - состояние, которое следует после состояния  в результате -го воздействия ;  - начальное маркирование;  - матрица, полученная транспонированием матрицы инцидентности позиций и переходов, причем ее элементы  равны , , или 0, когда соответственно переход  имеет  исходящих дуг к позиции ,  входящих дуг в позицию  или не имеет связи с позицией ; – управляющий вектор, компоненты которого. Если , то в -й момент асинхронного времени происходит срабатывание перехода , если же , то срабатывание не происходит.

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

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

Рис. 5.13. Переходы -сети

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

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

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

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

Безопасность.Позиция piP сети C=(P, T, I, O, M0) является безопасной, если m(pi)I для любой MR(C, M0). Сеть Петри безопасна, если безопасна каждая ее позиция.

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

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

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

Позиция piP сети C=(P, T, I, O, M0) является К-безопасной, если m(pi)К для всех MR(C, M0).

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

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

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

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

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

m(pi)  =m0(pi).

piP     piP

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

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

                                       а)                                              в)

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

Начальная маркировка помечает ресурсы свободными и готовность процессов к работе. Выполнение сети в последовательности t1, t2, t3, t4, t5, t6 или t4, t5, t6, t1, t2, t3 не приводит к тупику. Если начать с переходов t1, t4 то выполнение заблокировано, процесс а) обладает ресурсом q и хочет получить r, процесс в) обладает r и хочет получить q.

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

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

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

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

5.5.Методы анализа на основе дерева достижимости

Дерево достижимости.Дерево достижимости представляется множеством состояний сети.

В начальной маркировке (1, 0, 0) разрешены два перехода t1 и t2. Первый шаг построения дерева достижимости показан на рис (б). Из маркировки (1, 1, 0) можно снова запустить t1 (получая (1, 2, 0)) и t2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t3 (получая (0, 0, 1)). Второй шаг построения дерева достижимости показан на рис (в).

Продолжая три маркировки (рис (в)) на третьем шаге маркировки (рис (г)). Маркировка (0, 0, 1) пассивная: никакой переход в ней не разрешен. Маркировка (0, 1, 1), порождаемая запуском t3 в (0, 2, 1) была уже порождена непосредственно из начальной маркировки запуском t2.

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

Всякий путь в дереве, начинающийся в корне соответствует допустимой последовательности переходов.

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

Первая из них – это использование пассивных маркировок, именуемых терминальными вершинами, и маркировок, ранее встречавшихся в дереве, именуемых дублирующими вершинами. В нашем примере маркировка (0, 0, 1) – терминальная, а (0, 1, 1) – дублирующая.

Вторая операция. Рассмотрим последовательность запусков переходов, начинающуюся в начальной маркировке М0 и концом M’, M’>M0. Маркировка M’ совпадает с маркировкой М0, за исключением того, что имеет некоторые «дополнительные» метки в некоторых позициях, то есть M’=M0+(M’-M0) и (M’-M0)>0. Поскольку на запуски переходов дополнительные метки не влияют, последовательность можно запустить снова, начиная в M’, приходя к маркировке M”. Так как действие последовательности переходов добавило M’-M0 меток к маркировке M0, она добавит также M’-M0 меток к маркировке M’, поэтому M”=M’+(M’-M0) или M”=M0+2(M’-M0). В общем случае последовательность можно запустить n раз, получив в результате маркировку M0+n(M’-M0).

В нашем примере можно запустить переход t1 столько раз сколько необходимо для того, чтобы получить произвольное число меток в P2. Это бесконечное число маркировок обозначим символом. Для любого a определим

аа  а

Эти операции с символом достаточны для построения дерева.

Алгоритм построения дерева.Каждая вершина i дерева связывается с расширенной маркировкой M(i). В этой маркировке число меток в позиции может быть либо неотрицательным целым, либо. Каждая вершина классифицируется какграничная илитерминальная илидублирующая иливнутренняя.

Граничными являются вершины, которые не обработаны алгоритмом. Алгоритм превратит их в терминальные, дублирующие, внутренние.

Алгоритм начинает с начальной маркировки М0, принимая ее в качестве граничной вершины.

Пусть х – граничная вершина.

  1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана также маркировка М(х)=М(у), то вершина х – дублирующая.
  2. Если для маркировки М(х) ни один из переходов не разрешен для всех tjT, то х – терминальная вершина.
  3. Для всякого перехода tjT, разрешенного в М(х), создать новую вершину z дерева. Маркировка М(z) определяется для каждой позиции Pi следующим образом:

а) если М(х)i=, то М(z)i=.

б) если на пути от корневой вершины к х существует вершина у с М(у)<(M(x), tj) и М(у)i<(M(x), tj)i, то М(z)i=, - функция следующего состояния.

в) в противном случае М(z)i=(M(x), tj)i,

Функция(M(x), tj) не определена, если tj не разрешен в маркировке М(х). Если tj разрешен, то(M(x), tj)=M’(x), где M’(x) – маркировка, полученная после срабатывания tj. Дуга, помеченная tj, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина z становится граничной.

Когда все вершины дерева – терминальные, дублирующие или внутренние, алгоритм останавливается.

Для нашего примера дерево достижимости имеет вид:

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

Ниже на рис. 5.15 приведем еще один пример сети Петри и дерево достижимости для него.

Рис 5.15. Пример дерева достижимости

Анализ сетей Петри на основе дерева достижимости.Сеть Петри ограничена тогда и только тогда, когда символ отсутствует в ее дереве достижимости. Если сеть ограничена и символ отсутствует в дереве достижимости, то сеть представляет систему конечных состояний. Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых маркировок.

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

Задача покрываемости маркировки М маркировкой М’ сводится к поиску на дереве такой вершины х, состояние которой покрывает состояние М. Если такой вершины М(х) не существует, маркировка М не покрывается никакой достижимой маркировкой.

Таким образом, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости. К сожалению, в общем случае его нельзя использовать для решения задач достижимости и активности, а также для определения возможной последовательности запусков. Решение этих задач ограничено существованием символа. Символ означает потерю информации, конкретные количества меток отбрасываются, учитывается только существование их большого числа. Вместе с тем, в отдельных конкретных случаях дерево достижимости позволяет судить о свойствах достижимости и активности. Например, сеть, дерево достижимости которой содержит терминальную вершину, не активна. Аналогично искомая маркировка M’ в задаче достижимости может встретиться в дереве достижимости, что означает ее достижимость. Кроме того, если маркировка не покрывается некоторой вершиной дерева достижимости, то она недостижима.

5.6. Анализ сетей Петри на основе матричных уравнений

Матричный подход основывается на представлении сети двумя матрицами Д-и Д+, представляющими входную и выходную функции сети. Каждая матрица имеетm строк (по одной на переход) иn столбцов (по одному на позицию). Определим матрицы Д-(j,i)=K(Pi,I(tj)) и Д+(j,i)=K(Pi,O(tj)). Д- описывает входы в переходы, Д+ - выходы из переходов,K – кратность позиции по входам и выходам.

Введёмm - векторe(j), содержащий нули везде, за исключениемj-й компоненты. Переходtj представляетсяm - векторомe(j).

Тогда переходtj в маркировке М разрешён, если М≥e(j-, а результат запуска переходаtj в маркировке М обозначим функцией δ(M,tj) определяющей новую маркировку М’:

δ(M,tj)=M -e(j) Д-+e(j) Д+ =M+e(j)(- Д- + Д+) =M +e(j)Д,

гдеД = Д+ - Д-  - составная  матрица изменений состояний сети.

Тогда для последовательности запусков переходовG={tj1,tj2,…,tjk}имеем:

δ(M,G) =δ(M,tj1,tj2,…,tjk) =

=M +e(j1)Д +e(j2)Д + … +e(jk)Д =

=M +[e(j1) +e(j2) + … +e(jk)]Д =M +f(G)Д.

Векторf(G) =e(j1)+e(j2) …..+e(jk) называется вектором запуска последовательностиtj1,tj2,…,tjk.i-й элемент вектораf(G),f(G)i - это число запусков переходаtj в последовательностиtj1,tj2,…,tjk. Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами.

Рассмотрим задачу сохранения при известном векторе взвешивания метокW. ЕслиM0 - начальная маркировка, аM’ - произвольная достижимая маркировка, необходимо, чтобыM0W =MW. Тогда существует последовательность запусков переходовG, которая переводит сеть изM0 вM’. Поэтому,

M’ =δ(M0,G) =M0 +f(G)Д.

Следовательно,M0W =MW = (M0+f(G) Д)W =M0W +f(G) ДW. Исходя из условия сохранения, имеем:f(GW = 0.

Поскольку это должно быть верно для всехf(G), имеем ДW = 0.

Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный векторW, что ДW = 0. Это обеспечивает простой алгоритм проверки сохранения, а также позволяет получать вектор взвешиванияW для сохраняющей сети. Для этого нужно решить систему ДW=0 относительноW.

Матричная теория является инструментом для решения проблемы достижимости. Пусть маркировкаM’ достижима изM0, тогда существует последовательность (возможно пустая) запусков переходовG, которая приводит изM0 кM’. Это означает, чтоf(G) является неотрицательным целым решением следующего матричного уравнения дляX:

M’ =M0 +X Д.       (*)

Следовательно, еслиM’ достижима изM0, тогда уравнение (*) имеет решение в неотрицательных целых. Если уравнение не имеет решения, тогдаM’ недостижима изM0.

Покажем возможности применения уравнения (*) для анализа сети, приведённой на рис. 5.16.

1

1

1

0

0

0

0

1

0

0

1

0

Д- =

1

0

0

0

0

2

1

0

0

0

0

1

                                                                Д+=

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

                                                 Д = Д+ - Д- =

Рис. 5.16. Пример сети и построения матрицы Д

В начальной маркировкеM0=(1,0,1,0) переходt3 разрешён и приводит к маркировкеM’, где:

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

M’=(1,0,1,0)+(0,0,1) =(1,0,1,0)+(0,0, 1,1)=(1,0,0,1)

ПоследовательностьG={t3,t2,t3,t2,t1}представляется вектором запусковf(G)=(1,2,2) и получает маркировкуM’:

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

M’ = (1,0,1,0) + (1,2,2)                                             =(1,0,1,0)+(0,3,-1,0)=(1,3,0,0)

Для определения того, является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0), имеем уравнение:

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

    (1, 8, 0, 1) = (1, 0, 1, 0) +Xили

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

    (0,8,-1,1)=X   ,                      

которое имеет решениеX=(0, 4, 5). Это соответствует последовательностиG= {t3,t2,t3,t2,t3,t2,t3,t2,t3}.

Можно показать, что маркировка (1, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0)  поскольку матричное уравнение :

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

(1,7,0,1)=(1,0,1,0) +Xили

0

-1

-1

0

0

+2

+1

-1

0

0

-1

+1

     (0,7,-1,1)=X   ,

не имеет решения.

Недостатки матричных методов.

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

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

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

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

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

TN = {N,τ},

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

Сеть с приоритетами переходов

Формальное определение:

PRN = {N,PR},

гдеN - сеть Петри;PR - отношение приоритетности (порядка), задаваемое на множестве переходов Т и определяющее порядок потребления меток возбуждёнными переходами в условиях конфликта за метку.

Временная сеть с приоритетами переходов

Такая сеть объединяет элементы, описанные в рассмотренных выше классах сетей.

Формальное определение:

PRTN = {N,τ,PR}.

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

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

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

Переходамtj сопоставлены времена τj, отражающие длительность выполнения соответствующих действий в системе обработки и обмена, генераторах помех и тайм-аута. отношения приоритетности введены для двух пар переходов – (t2,t8) и (t7,t11), поскольку только по отношению к ним может возникнуть конфликт за метку. Они имеют вид:

PR(t8) > PR(t2)и       PR(t7) > PR(t11).

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

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

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

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

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

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

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

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

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

t6 - обработка в ПрП;

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

t8,t9 - переходы модели источника помех;

t10,t11 - элементы ГТ;

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

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

P3 - ПрП готов принять сообщение и запрашиваетt2;

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

P5 - завершение действияt2 и запускt3;

P6 - запросt6;

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

P8 - запросt5;

P9,P10 - позиции ГТ;

P11,P12 - позиции ИП;

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

Передача сообщения процессором-источником порождает буферирование копии сообщения и запуск генератора тайм-аута, посылку сообщения в канал, а также формирование условия подтверждения о приёме, что отражается появлением меток вP2,P4,P9. Если сообщение в каналеP2 исчезнет благодаря действию ИП (что отражается возбуждениемt8), то не приходит подтверждение приёма (метка вP7 не появится), и через время тайм-аута (связанное сt10) произойдёт повторная выдача сообщения в канал (что отражается срабатываниемt7). Сt9 связан интервал времени между потерей в канале очередного сообщения и возникновением условия для потери следующего сообщения. Сt10 связано время тайм-аута, через которое организуется повторная посылка потерянного сообщения. Если через τ10 вP4 нет метки, то не создадутся условия возбужденияt7 и метка изP10 покинет ГТ.

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

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

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

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

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

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

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

t1,t2- загрузка процессоров;

t3,t4 – обработка;

t5,t6 - освобождение процессоров

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

P1,P2 - заявки на обработку;

P3,P4 - Заявки приняты;

P5,P6 - конец обработки;

P7,P8 - обработанные заявки;

P9,P10 - двоичные семафоры,

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

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

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

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

Начальный цвет метки вP0 равенC1 и дуга (P0,t1) окрашена вC1. Поэтому условие возбуждения выполнимо для переходаt1. После срабатыванияt1 вP0 метка возвращается, уже имея цветC2, поскольку дуга (t1,P0) раскрашена в цветC2.

Раскрашивание дуг обеспечивает возбуждение только одного из переходов, следующих заP0, при любом состоянии системы. При данной раскраске алгоритм работы супервизора представлен последовательностью срабатывания переходовt1,t2(t3,t4)t5,t6, т. е. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.

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

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

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

На Пр и УВВ параллельно могут выполняться операторы 2 и 3, завершение которых является условием выполнения оператора 0, что видно из рис.5.20а. Переходыt0t3 биграфа (рис. 5.20б) соответствуют вершинам графа на рис. 5.20а. Для отображения точки входа в алгоритм на его биграфе введена маркированная позицияP1, поэтому нулевой вершине графа (рис. 5.20а) поставлены в соответствие переходыt0 иt4 биграфа. При построении сети (рис. 5.20в) учтено, что время выполнения операцийt1 иt4 мало по сравнению с остальными. Учитывая также, что действияt0 иt2 выполняются на процессоре, позицииP1 иP5, а такжеP2 иP6 биграфа совмещены на рис.5.20в и обозначены какP1 иP2. Процессы выполнения алгоритмов представлены движением меток. Раскраска меток двухэлементная, определяющая номер процессаa = {1, 2, 3} и номер этапа обработкиC = {C0,C1,C2,C3}.

Из рис. 5.20в видно, что некоторые из дуг раскрашены одним цветом (Ci), другие парой цветов (aCi), третьи не раскрашены вовсе, что учитывается при управлении возбуждением переходов и изменении цвета меток. Заметим, что при раскрашивании парой цветов все эти признаки анализируются или изменяются в комплексе. Например, входные дуги переходаt4 помечены парамиaC2 иaC3, что определяет выбор для синхронизации наt4 процессов с одним и тем же номеромa и завершенными этапами обработкиC2 иC3 соответственно.

Следующий пример (рис. 5.21) показывает изобразительные возможности раскрашенных сетей по разделению путей данных и управления в УВВ. Данные от двух источниковU1 иU2 помечены квадратами вP1 иP3, а сигналы запроса на обработку – кружками вP2 иP4. Запросы принимаются  (переходыt1,t2), накапливаются в регистре (позицияP5), выбираются из неё (переходt3) и запускают пересылку данных от источников (P1 илиP3) в буферP7. Метка-треугольник в позицииP8 отражает управляющий процесс, разрешающий выполнение только одной из двух операций считыванияt4 илиt5. Читателю предлагается самостоятельно разобраться, почему необходимо использовать раскрашенную метку в позицииP8 и на дугах  и .

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

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

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

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

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

Приоритетные раскрашенные сети

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

Приоритетные раскрашенные сети адекватно представляют приоритетное обслуживание процессов.

Например, спецификация правил приоритетного обслуживания для модели мультипрограммного выполнения алгоритма (рис 5.20) включает определение отношения порядка (приоритетности) на множестве номеров задачa = {1, 2, 3}. Сопоставление этого правила дугам (P1t0) и (P3t3) указывает на приоритетность выбора процесса для выполнения процессором и объектом управления.

Аналогично задаётся отношение порядка на множестве признаков {●,○}, представленных на рис. 5.21 графически. Правило выбора сопоставляется дуге (P5t3) этой модели.

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

5.8. Динамика сетей Петри в пространстве состояний.

Динамика сети описывается следующим рекуррентным уравнением:

Mk =Mk-1+A*Uk,k=1, 2, 3,…. (5.1)

Для вычисления управляющего вектораUk необходимо определить те переходыtj, которые срабатывают при маркированииMk-1. Еслиtj срабатывает, тоuj=1 и произведениеA*Uk даёт число меток, добавляемых в позициюPi в каждом такте.

Условие срабатывания переходаtj и выработкиuj=1 представляется логическим уравнением:

i [m(Pi) ≥ I(tj,Pi)](uj=1), (5.2)

которое управляет действиямиtj.

Для генерирования диаграммы состояний сети Петри достаточно использовать (5.1), (5.2). В теории сетей Петри иногда исходят из того, что не указывают порядок срабатывания переходов, если векторU задаёт возбуждение нескольких из них в одном и том же тактеk. Так в примере при построении дерева достижимости в состоянииM0 вектор управленияU1*=(1,0,1), что указывает на возбуждение первого и третьего переходов. При срабатыванииt1сеть перейдёт в состояниеM1=(0,1,1,1), приt3 в состояниеM5=(2,2,0,0). Однако, если следовать (5.1), то диаграмма состояний сети имеет вид рис. 5.22в. Итак, если полагать, что все возбуждённые переходы срабатывают вместе, то динамику сети можно представить уравнением (5.1). Если исходить из того, что возбуждённые переходы могут срабатывать только порознь, то уравнение состояний сети будет иметь другой вид.

P

P

t

t

1

2

3

4

t

1

2

3

4

P

1

2

3

1

-1

0

1

0

1

0

0

1

0

1

1

0

0

A:

2

0

-1

-1

0

I:

2

0

0

0

1

O:

2

0

1

0

3

1

1

0

1

3

1

1

0

0

3

0

1

0

4

0

1

1

I:TxP → {0,1}   - функция следования;

O:PxT → {0,1}  - функция предшествования.

Рис. 5.22. Построение диаграммы состояний сети

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

Свободное движение сети.В реальных ВС имеется вполне определённый способ управления сменой состояний и присутствует такой фактор как время, что позволяет уточнить уравнение (5.2). Если времена срабатывания переходов одинаковы, то динамика системы моделируется уравнениями (5.1), (5.2), поскольку такая сеть является синхронной. Этих уравнений недостаточно для моделирования асинхронных процессов, для которых  времена срабатывания различны.

В этом случае процедуру продвижения меток в сети следует производить в асинхронном времени, введя в модель часы. Если в синхронных системах достаточно вести отсчёт тактов, то в асинхронных необходимо в каждом из тактов определять момент наступления очередного. Интервал времени между тактамиk иk+1 определяется временем наступления срабатывания одновременно одного или нескольких переходов.

Вынужденное движение сети.Уравнение (5.1) отражает свободное движение сети из начального состоянияM0. Вынужденное движение сети определяется вектором-функциейW(t), компоненты которогоWi(t) описывают приход меток в позицииPi во времени;W(t) может задаваться в моменты дискретного времениk, наступление которых устанавливается моментами переключения состояния сети или внутренними часами.

Уравнение вынужденного движения сети Петри имеет вид:

Mk =Mk-1+A*Uk +Wk (5.3)

Таким образом, введённая здесь последовательностьWk описывает внешний источник меток, представленных входной лентой.

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

ПоследовательностьWk предназначена для отображения взаимодействий в структурированных сетях, она может отображать последовательные наборы данных, управляющих команд и т. д. Очевидно, что в любом состоянии системы компоненты вектора маркировки не могут быть отрицательными, то естьMk≥0,Vk. Учитывая последнее, из (5.1) получаемMk-1+A*Uk≥0.

Последовательность маркирований (5.1) можно выразить через начальную маркировкуM0 и вектор счёта срабатываний:

S = {  } ;j = 1, 2, 3, …,m. (5.4)

Элементsjуказывает, какое число раз срабатывает переходt в последовательности маркирований, ведущей отM0 к Мк.

Учитывая уравнение (5.4), из выражения (5.1) получаем:

Mk =M0 +A*S.    (5.5)

Введя вектор изменения маркирования ΔM =MkM0, из уравнения (6) получим:

A*S = ΔM.        (5.6)

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

5.9. Методы линейной алгебры для анализа сети Петри

Характеристики сети Петри на основе Р-инвариантов

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

Целочисленный векторX = {},i=1,2,…n, являющийся решением линейной системы:

AX = 0,            (5.7)

называется Р-инвариантом или Р-циклом.

Рассмотрим уравнение (5.5), обе части которого умножим наX*:

X*M =X*M0+X*A*S.      (5.8)

Известно, чтоAX =X*A*, поэтому из выражения (5.8) с учётом (5.7) получим:

X*M =X*M0 ,                (5.9)

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

Если обозначитьX*M0 =K0, гдеK0- постоянная величина, то свойство инвариантности сети представимо в виде отношения-равенства:

X*M =K0 =const .  (5.10)

Вектор Х называют Р-инвариантом, поскольку он определяет некоторое из свойств распределения меток по позициямPi.

Фундаментальной системой решений системы линейных однородных уравнений (5.7) называют такую их совокупность, через которую линейно выражаются все остальные решения. Если ранг матрицы А равен числу неизвестных (r =n), то система (5.7) имеет только нулевое решение.

Еслиr <n, то система (5.7) помимо нулевого имеет бесконечное множество других решений, причём фундаментальная система состоит из (n -r) векторов Х. Рангnm - матрицы А = ||aij || равен наивысшему порядку отличного от нуля определителя, полученного вычёркиваниемn -r столбцов иm -r строк из матрицы А.

Таким образом, все инварианты Х для маркирований сети можно получить изn -r базисных решений. Объединив записанные в виде векторов-строк решения фундаментальной системы, получим матрицу инвариантов или базисных решений В. Тогда для любого достижимого маркирования аналогично равенству (5.10) имеем:

BM =BM0 =K0 .         (5.11)

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

Инвариантная сеть Петри является ограниченной. Докажем это. Пусть Х – полная Р-цепь. ТогдаX*M=K0, т. е. взвешенная сумма меток по всем позициям - ограниченная. А посколькуxi положительные и вся сумма ограничена, то и маркирования всех позиций сети ограничены.

Характеристики сети Петри на основеt-инвариантов

Рассмотрим следующую группу характеристик, получение которых основывается на вычисленииt-инвариантов (илиt-циклов).

Целочисленный векторY называетсяt-инвариантом, если он является решением линейной системы:

A*Y = 0 .             (5.12)

Если значениеt-инварианта подставить в уравнение (6) вместо вектора счёта срабатыванийS, то окажется, что

M =M0 +A*Y =M0.

Отсюда следует, что еслиY≠0, то сеть устойчива, т. е. после ряда переключений она возвращается в исходное состояниеM0. Устойчивость процессов связана с их циклической повторяемостью, начиная с состоянияM0. Заметим, что среди решений системы (5.12) могут быть такие векторыY, компонентыyj которых  отрицательны.

Полнаяt-цепь – этоt-цикл, все компоненты которого положительны. Полнаяt-цепь включает в себя все переходы сети. Если сеть имеет полнуюt-цепь, то она жива при любом начальном маркировании, поскольку в цепи маркирований отM0до М=M0 срабатывают все переходы.

Таким образом, по устойчивости процессов и значениюt-инварианта можно определить живость сети: если сеть жива и ограничена, то она инвариантна и устойчива.

Обнаружение тупиковых состояний.

Используя уравнение (5.2), условие возбуждения переходаtj можно представить в виде:

n                          n

∑ I(tj,Pi)m(Pi) ≥   ∑ I(tj,Pi),

i=1i=1

или учитывая, чтоI(tj,Pi) =O*(Pi ,tj),

nn

O*(Pi ,tj)m(Pi)  ≥  ∑O*(Pi ,tj).       (5.13)

i=1i=1

Для краткости будем использовать векторную запись условия возбуждения переходов:

O*MO*E, где Е – единичный вектор.

Условие (5.13) объясняется следующим образом:если некоторая компонентаj  левой части при данном маркировании М равна соответствующей компоненте правой части или больше её, то переходtj возбуждается.

Поскольку множество достижимых маркированийR(N) должно удовлетворять (5.10), то отсутствие возбуждаемых переходов дляMR(N) следует определять из решения системы:

BM =BM0;

O*M =O*EE.         (5.14)

Если эта система имеет решения, то некоторое её маркирование является тупиком. Заметим, что отношению (5.11) могут удовлетворять недопустимые маркирования, поэтому решением системы (5.14) также могут быть недопустимые маркирования, хотя все допустимые тупики удовлетворяют ему.

Таким образом, система (5.14) – достаточное условие того, что маркирование М тупиково.

Для анализа тупиков можно также использовать систему:

M = M0+ A*S ≥ 0;

O*M ≤ O*E – E,

или

M0+A*S ≥ 0;

O*ASO*(E -M0) –E,          (5.15)

если в число исходных данных входит известный вектор счёта срабатыванийS. Таким образом, не совместимость системы (5.14) или (5.15) свидетельствует об отсутствии маркированияM или вектора счёта срабатыванийS, которые ведут к тупику изM0.

Рассмотрим  на простых примерах возможности изложенного подхода. Для сети на рис. 5.22а согласно уравнению (5.7) Р-инвариант Х является целочисленным решением системы:

-x1+x3=x2 +x3 =x1 +x2x4= 0.

Ранг матрицы А системы АХ=0 равен трём, поэтому данная система имеет одно целочисленное базисное решение, вектор-строка которогоX* = (1, -1, 1, 0). Подставив Х иM0в равенство (5.11)BM =BM0 =K0, получим условие, верное для любого достижимого маркирования:

M = (m1,m2,m3,m4) :m1m2 +m3 = 0     илиm1+m3 =m2.

Из последнего условия виден смысл инварианта: сумма числа меток в позицияхP1, иP3 и число меток в позиции Р2 равны для любого достижимого маркирования сети. Этот инвариант верен здесь для диаграмм состояний (рис. 5.22 б, рис. 5.22 в), соответствующих разным правилам управления срабатыванием переходов. Вывод об ограниченности сети по данному значению Х сделать нельзя.

Вычислимt-инвариантыY. Из системы (5.12) получим систему уравнений:

-y1+y3= -y2+y3=y1-y2= -y3= 0.

Система имеет только нулевое решениеY* = (0, 0, 0), поэтому в данной сети не существует маркирований, связанных циклами на диаграмме состояний. Маркирование М совпадает с начальным, только если не срабатывает ни один из переходов сети, поскольку все компоненты вектораY нулевые. Иначе говоря, посколькуY=0, то последовательность состояний сети не имеет возвратов, что подтверждается диаграммами состояний.

В связи с полученными особенностями целесообразно определить, имеет ли тупик указанная невозвратная последовательность маркировок. Система уравнений (5.14) имеет вид:

m1 -m2 +m3 =m1 =m4 = 0;

m2 +m3+m4= 2.

Система совместна, и ей удовлетворяют любые маркирования, которые имеютm1=0;m2=m3;m4=0. Тупиковыми, например, являются маркирования М=(0110), М=(0220) и т. д. Таким образом, сеть номер два не является безтупиковой приM0=(1101).

Рассмотрим ещё один пример анализа.

1

2

3

1

1

0

-1

2

-1

1

0

3

0

-1

1

Ранг матрицы А равен двум, поэтомуn-2=1, т. е. в фундаментальную систему решений однородной системы АХ=0 входит один вектор Х. Распишем систему АХ=0:

x1x3 =x2x1 =x3x2 = 0.

Взяв её целочисленное решениеX*=(1,1,1), получим условие инвариантности для позиций:

X*M =X*M0 =m1 +m2+m3= 1.

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

Для вычисленияt-инварианта рассмотрим систему:

y1y2 =y2y3 =y3y1= 0,

из которой найдёмY*=(1,1,1). ПосколькуY≠0 - сеть устойчива, т. е. процессы в ней периодически повторяются. Посколькуt-инвариантY охватывает все переходы, так как всеyi=1, то сеть жива. Система уравнений (5.14) для данной сети:

m1 +m2 +m3 = 1;

m1 ≤ 0;m2 ≤ 0;m3 ≤ 0.

Поскольку она несовместна, делаем вывод, об отсутствии тупиков в данной сети.

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

Определение количественных характеристик сетей

Для определения количественных характеристик сетей можно использовать различные методы теории графов и классического сетевого анализа. Ранее для сетей Петри рассматривались два подхода: через построение дерева достижимости и матричные методы анализа (линейная алгебра).

Для временных сетей, когда с каждым переходом связано время , важной характеристикой является время перевода сети из состояния М0в М. Для этого на дереве достижимости можно отыскать соответствующий путь с вектором запусков счёта срабатывания , переводящих сеть из состояния М0в состояние М. Тогда время перевода сети из состояния М0в состояние М определится суммой:

, где - компонента вектораS для переходаtj (число срабатываний переходаtj).

В случае параллелизма в срабатывании переходов оценка времени перехода от М0к М усложняется.

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

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

Анализ свойств раскрашенных сетей

Раскрашенная сеть характеризуется следующим множеством элементов:

CN =  {N,C,F,CM0 },

где:N = {T,P,I,O } – биграф;

C = {X,R },X = { λ, с1, с2, …, сL } = { сr}   – множество раскрашивающих цветов или других признаков, включающее элемент  λ, обозначающий «отсутствие цвета»;

R - бинарное отношение на множестве цветов Х, (чаще всего это отношение эквивалентности или равенства цветов);

F: А Х – отображение множества дуг биграфаN на множество цветов, дающее раскраску дуг: сijS - цветs-ой дугиaijS биграфа, направленной из вершиныi в вершинуj;

     С М0– начальное цветное маркирование сети.

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

CM: {P;  Х },

первое из которых указывает на размещение меток по позициям, а второе - на цвет этих меток. Факт размещения меткиm в позицииPi обозначим (mPi ).

Условимся, что меткаm, имеющая цветc(m), может принять участие в возбуждении переходаtj, если пара (c(m),сijS ) удовлетворяет заданномуR-отношению на множестве цветов. ЕслиR-отношение равенства, то метка (mPi) может участвовать в возбужденииtj  при условии чтоc(m) = сijS (т. е. когда цвет метки равен цвету дугиaijS). Для возбуждения переходаtj необходимо, чтобы по всем входящим дугам могли пройти метки соответствующего цвета из позицийPi , являющиеся предшественниками переходаtj .

Логическое уравнение, описывающее условие возбуждения переходаtj, имеет следующий вид:

PiPre(tj)mPi [R(с(m), сijS) = 1]u(tj) = 1,

иначеu(tj) = 0.

Итак, если переходtj возбуждён (u(tj) = 1), то происходит его срабатывание и возбуждавшие метки из позицийPre(tj) при этом изымаются, а позицииPost(tj) пополняются метками, цвет которых принимается равным цвету дуг, проходящих изtj в позицииPost(tj).

Для отображения цветного маркирования условимся представлять его в следующем виде:

CM = |m1mimn |*,

где: * - операция транспонирования;

mi = |mi1mi2 ……miL |, причёмmir - число метокr-го цвета в позицииPi.

Динамика меток в раскрашенной сети характеризуется матрицей инцидентности Д, элементы которойdij представим в виде векторов-строк длиноюL:

dij = |dij1dij2dijL |,             (5.16)

гдеL - число раскрашивающих цветов.

Значенияdijr задаются следующим образом. Если метка цветаr потребляется переходомtj из позицииPi при срабатыванииtj, тоdijr = -1; если метка цветаr поступает вPi  изtj , тоdijr = 1, и, наконец, в отсутствии этих действийdijr = 0.

Эти же условия можно сформировать по другому. Если позицияPi имеет исходящие дуги цветаr в переходtj, тоdijr = -1; если имеет входящие дуги цветаr, тоdijr = 1, и если не имеет инцидентных дуг цветаr, тоdijr = 0.

Динамику продвижения меток по раскрашенной сети можно описать уравнением состояния:

CMk =CMk-1 +D*Uk ,      (5.17)

гдеCMk - состояние, в которое переходит раскрашенная сеть изCMk-1 под действием управляющего вектораUk = |ujk |, компоненты которого

             1, если вk-ый момент срабатывает переходtj ;

ujk=

             0, иначе.

Р-инварианты.Введём в рассмотрение инварианты раскрашенной сети, подобно тому как это сделано в сети Петри. Р-инвариант найдём из решения линейной системы:

DV = 0 ,         (5.18)

гдеV = |Vi | - целочисленный вектор-столбец, компоненты которого имеют вид:

Vi* = |vi1vi2 ….viL | .

Учитывая уравнение (5.1), находим:

V*CM =V*CM0.    (5.19)

Итак, подобно уравнению (5.9) для сети Петри, уравнение (5.19) для раскрашенной сети описывает инвариантность в её маркированиях.

Фундаментальная система решений однородной системы линейных уравнений имеетnrL  решений, гдеn - число позиций сети;r - ранг матрицы Д;L - мощность множества цветов Х. Объединив их в матрицу СВ, получим уравнение, аналогичное уравнению (5.11):

CBCM =CBCM0 =K0  .

T-инварианты. Решение линейной системы:

D*W = 0 ,            (5.20)

даётt-инвариантыW, гдеW = |Wj | - целочисленный вектор-столбец, в котором

Wj = |Wj1Wj2WjL |.

Условие существования тупиков в раскрашенной сети находится из анализа системы:

CBCM =CBCM0 ;

CO*CMCOE’ –E,               (5.21)

подобно тому как это выполняется для сети Петри. ЗдесьCO* - матрица аналогичнаяO*, расширенная в пределах каждого элемента по принципу (5.16):

                 1, если существует дуга изtj  вPi, раскрашенная цветомr;

COijr  =

                 0, иначе,

COij = |COij1,COij2, … ,COijr ,…,COijL |,

Е’ – единичный клеточный вектор, компоненты которогоej’ представлены наборами изL единиц.

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

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

Рис.5.23. Примеры раскрашенных сетей

В изображённой на рис. 5.23а сети, описывающей взаимодействие двух процессов, обозначенных метками (□,○), протокол взаимодействия предусматривает порождение нового процесса (●), а затем возврат к исходным.

Каждому цвету из множества Х = (□,○,●) сопоставим числаr = 1, 2, 3. Тогда элементы матрицы Д = ||dij ||, гдеi = 1, 2, 3, 4,j = 1, 2, 3, 4, 5, равны:

d11 =d22 = | -1 0 0 |;d23 = | 0 0 1 |;

d12 =d31 = |  1 0 0 |;d33= | 0 0 -1|;

d35 =d44 = |  0 1 0 |;d24 =d45 = | 0 -1 0 |,

а другиеdij = | 000 |.

Вектор начального маркирования СМ0= |m0i | представлен компонентами:

m01 = | 100 |;m02 =m03 =m04 = | 000 |;m05 = | 010 |.

Уравнение состояния (5.17) здесь имеет вид:

m1

m1

d11

d21

d31

d41

U1

m2

m2

d12

d22

d32

d42

U2

m3

=

m3

      +

d13

d23

d33

d43

  *

U3

m4

m4

d14

d24

d34

d44

U4

m5

k

m5

k-1

d15

d25

d35

d45

k

Рекуррентное решение данного уравнения позволяет моделировать динамику состояний сети.

Найдём Р-инвариант сетиV* = |V1V2V3V4V5 |, гдеVi* = |vi1vi2vi3 |. Для этого нужно решить систему (5.18). Ранг матрицы Д равен 1, следовательно фундаментальная система имеет одно решение, так какnrL = 1. Распишем систему уравнений (5.18) для данной сети:

v11 =v21;v33 =v11+v52;

v33 =v21 +v42;v42 =v52.

В качестве инварианта можно взять клеточный вектор-столбец с компонентамиV1* =V2* = |100|;V3*= |003|;V4* =V5* = |020|, удовлетворяющий приведённой однородной системе линейных уравнений. Затем вычисляем произведение:

V*CM0 = |V1*V2*V3*V4*V5*||m1*m2*m3*m4*m5*|0 = 3,

и условие инвариантности:

                                     5

VCM = |Vi* ||mi* |* = ∑Vi*mi* =m11+m21 +3m33 + 2m42 + 2m52 = 3.

i=1

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

m11+ 2m42 = 3;m11+ 2m52 = 3;m21 +2m42 = 3;

m21 +2m52 = 3;   3m33 = 3.

Из условия инвариантности, содержащего в правой части константу 3, следует ограниченность сети.

Решив систему (5.20), можно установить, что данная сеть живая и устойчивая. Элементы матрицы СО равны:

CO11 =CO22 = | 100 | ;CO42 =CO54 = | 010 | ;CO33 = | 001 |;

а другиеCOij= | 000 |. Система (5.21) здесь имеет вид:

m11+m21 +3m33 + 2m42 + 2m52 = 3;

m11 ≤ 0;m21 +m42 ≤ 1;m33 ≤ 0;m52 ≤ 0.

Данная система не совместна, а, следовательно, исследуемая раскрашенная сеть не имеет тупиков.

Изменим раскраску на дуге (t3,p5) и примем новое начальное маркирование как показано на рис. 5.23б.

На основе вычислений можно установить, что приведённая сеть – ограниченная, живая, однако тупиковая, поскольку система

m11+m21 +3m33 + 2m42 + 2m51 + 2m52 = 3;

m11 ≤ 0;m21 +m42 ≤ 1;m33 ≤ 0;m52 ≤ 0,

совместна. Тупиковое маркирование описывается вектором СМ = | (000) (100) (000) (100) (000) |.

«Обесцвечивание» сети, т. е. переход от раскрашенной сети к базовой сети Петри может привести к потере и искажению информации о протекании процессов в сетевой модели. Так, если выполнить «обесцвечивание» приведённой сети, то расчётами можно установить, что её инвариант станет равнымm1 +m2 + 3m3 + 2m4 + 2m5 = 3, т. е. произошло как бы «обесцвечивание» инварианта сети, приведённой на (рис. а), а не на (рис. б). Но самое важное состоит в том, что «обесцвеченная» сеть – беступиковая, хотя исходная раскрашенная сеть имеет тупик. Искажение такого важного свойства при упрощении модели указывает, что для обеспечения достоверности проектного анализа при исследовании раскрашенных сетей недопустим переход к «обесцвеченной» сети.

P1                        t2                          P3

Чтение

Запись

r

6

4

6

да

нет

а)

в)

да

нет

б)

1

2

3

4

5

6

7

8

9

10

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

П

ОЗУ

УСО

ОУ

ЗУ

оператор

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

а)

EMBED Equation.3

EMBED Equation.3

б)

в)

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

г)

д)

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

a)

б)

в)

a)

б)


 

А также другие работы, которые могут Вас заинтересовать

33845. ПОНЯТИЕ ГЕРМЕНЕВТИКИ 18.05 KB
  Понимание тогда выступает как непосредственное проникновение в жизнь. Понимание собственного духовного мира достигается в процессе самонаблюдения понимание чужого мира – путем вживания сопереживания вчувствования. Именно в стихии языка осуществляется понимание людьми и окружающего мира и самих себя и других.
33846. Философская антропология, Макс Шелер (1874–1928) 15.15 KB
  В центре внимания этого течения проблема человека а основная идея создание интегральной концепции человека. Философская антропология объявив себя основополагающей философской дисциплиной пытается на основе тех или иных особенностей человека найти способы постановки и решения всех философских проблем. В отличие от рационалистических учений философская антропология вовлекает в сферу исследования душевнодуховную жизнь человека эмоции инстинкты влечения что зачастую приводит к иррационализму: представители данного направления...
33848. Характеристика западной философии 16.81 KB
  Эти же вопросы являются предметом исследования и других форм общественного сознания в частности и философии. Теология как одна из форм выражения религиозного сознания имеет ряд специфических черт которые отличают ее от философии. Проблема соотношения философии и теологии возникла в первые века существования христианства и несостоятельная своей актуальности до наших дней.
33849. Особенности развития русской философии 20.54 KB
  В качестве самостоятельного духовного явления о русской философии может идти речь начиная с конца XVIII начала XIX в. Первые известные за пределами России представители русской православной философии В. Дальнейшее развитие русской философии связано с тремя основными направлениями: психологическим рефлексология Бехтерева и Павлова теософскомистическим в лице русского космизма Е.
33850. Профессиональные заболевания медицинских работников 64.94 KB
  Медицинские работники занимают пятое место по распространенности профессиональной заболеваемости, опережая даже работников химической промышленности. Данные исследований, проведенных десятки лет назад и в последние десятилетия, убедительно свидетельствуют о том, что многие заболевания у медицинских работников являются профессиональными...
33851. ФИЛОСОФИЯ РУССКОГО КОСМИЗМА 13.87 KB
  Именно в космизме ставятся проблемы о космосе и человеке выдвигается положение о том что конец этого мира конец истории зависит и от творческого акта человека. необходимости нового сознательного развития мира когда человечество направляет его в ту сторону в какую диктует ему разум и нравственное чувство. Речь по существу идет о расширении прав сознательнодуховных сил об управлении духом материи об одухотворении мира и человека.
33852. Диалектика — учение о всеобщей связи и развитии 15.96 KB
  Они всегда влияют определенным образом друг на друга завцЬят друг от друга то есть находятся во взаимной связи и обусловленности. В поле зрения каждой из них находятся определенные предметы и явления а следовательно и определенные связи между ними. В социальных науках раскрываются разнообразные связи и зависимости различных общественных явлений например связь политики и экономики государства интересов различных классов и их экономического положения воздействие географической среды плотности населения и других явлений на темпы развития...
33853. Многозначность понятия природы 15.47 KB
  Природа может пониматься либо как абстракция либо как потенция либо как акт. Всякий раз следует обращать внимание на указанные обстоятельства при рассмотрении того или иного значения термина природа. Концепции природы до множества ипостасей одного вида: природаобразец и логос природы: 1 Природаобразец реально существующая до множества ипостасей данного вида а после их появления – отдельно от нихт. Тождественна платоновской идееОтметим что в данном значении термин природа не имел скольнибудь распространённого применения в...