Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции по моделированию - файл ГЛАВА 4.doc


Загрузка...
Лекции по моделированию
скачать (1024.9 kb.)

Доступные файлы (5):

ГЛАВА 1.doc307kb.20.02.2006 19:13скачать
ГЛАВА 2.doc615kb.20.02.2006 19:13скачать
ГЛАВА 3.doc813kb.29.03.2006 11:20скачать
ГЛАВА 4.doc731kb.20.02.2006 19:13скачать
ГЛАВА 5.doc574kb.20.02.2006 19:13скачать

ГЛАВА 4.doc

  1   2   3
Реклама MarketGid:
Загрузка...
4. СЕТИ ПЕТРИ


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

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

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

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

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

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

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



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

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



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

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

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

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







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

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

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

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

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

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

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

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

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

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


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

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

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


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

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



Рис.6

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


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

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

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

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


Рис.8

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


4.2.1. Безопасность

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

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

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


4.2.2. Ограниченность

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

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

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

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


4.2.3. Сохранение

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

Сеть Петри называется строго сохраняющей, если для всех MR(C, M0)
 m(pi) =  m0(pi)

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


4.2.4. Активность

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


а) в)


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

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


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

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

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


^ 4.3. МЕТОДЫ АНАЛИЗА НА ОСНОВЕ ДЕРЕВА ДОСТИЖИМОСТИ
4.3.1.Дерево достижимости

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

P1 t2 P3



В начальной маркировке (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 определим

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

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


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

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

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

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

  1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана также маркировка М(х)=М(у), то вершина х – дублирующая.

  2. Если для маркировки М(х) ни один из переходов не разрешен для всех tjT, то х – терминальная вершина.

  3. Для всякого перехода tjT, разрешенного в М(х), создать новую вершину 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 становится граничной.

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

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

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

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



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

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

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

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

^ 4.4. Анализ сетей Петри на основе матричных уравнений
Матричный подход основывается на представлении сети двумя матрицами Д- и Д+, представляющими входную и выходную функции сети. Каждая матрица имеет 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 - 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)Д (1)
Вектор 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 = M’W. Тогда существует последовательность запусков переходов G, которая переводит сеть из M0 в M’. Поэтому
M’ = δ(M0,G) = M0 + f(G)Д
Следовательно, M0W = M’W = (M0 + f(G) Д) W = M0W + f(G) ДW, поэтому f(G)ДW = 0.

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

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

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

ПРИМЕР:





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



Д = Д+ - Д- =

В начальной маркировке 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= t­­3 t­­2 t­­3 t­­2 t­­1 представляется вектором запусков 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. Решение уравнения (*) является необходимым для достижимости, но недостаточным.



^ 4.5. Модификации сетей Петри
  1   2   3



Скачать файл (1024.9 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru