Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 34
Текст из файла (страница 34)
В (159, 7), следуя работе Патила, получена задача, которая не может быть решена Р- и Ъ'-операциями или сетями Петри. То же ограничение мощности моделирования было ранее определено Келлером )150). Задача, сформулированная в (159, 7), вполне реальна. Пред- положим, что мы имеем два процесса производителя и два процесса ,потребителя. Первый процесс: производитель Ре создает элементы данных для первого процесса потребителя С„а другой производи'тель Р, — для второго потребителя Са.
Элементы данных, которые произведены, но еще не использованы, помещаются в буфер: буфер В~ для пары (Рь С,) и Ва для (Рм Са). Передача данных из буферов к потребителям происходит через общий канал. Канал может передавать только по одному элементу за сеанс, причем из любого буфера любому потребителю. Производители просто помещают данные 'в буфера. Потребители должны координировать свои действия по Использованию канала. Управляющий потребитель приказывает каналу передать данные из соответствующего буфера. Все зто схе- атично изображено на рис. 7.4. Глаза 7 !'! Рис.
7.4. Процессы произзол~пелиlпотребители с буферизацией и совместив испельзуеиыи каналом Главная проблема, связанная с этой системой, состоит в распределении канала. Пара производитель!потребитель (Ро СД должна иметь приоритет по отношению к (Р,, Сз) на использование канала. А именно, канал никогда не должен передавать элементы данных из буфера Вз потребителю Сз до тех пор, пока буфер В, не пуст. Это правило приоритета не позволяет системе быть моделируемой сетью Петри. Идея доказательства относительно проста. Предположим, что мы находимся в состоянии, когда имеется р элементов в двух буферах Ве и Вз.
Если сейчас производитель Р, делает перерыв, то все элементы из буфера В, будут в конце концов переданы производителю Со и буфер В, будет пуст. Это позволит переместить элементы из буфера В, потребителю С,. Таким образом, существует путь из состояния в в состояние р', в котором потребитель Сз может использовать канал. Если сейчас в действительности производитель Р, произведет дополнительно Й элементов данных, то мы будем в состоянии р, + л„а не в состоянии р. Но из-за нечувствительности условий запусков переходов сетей Петри к числу фишек в позиции последовательность запусков, которая переводила нас из р в р', будет все еще допустимой и переведет нас из состояния р+ л в состояние р'+ й.
И поскольку потребитель Сз мог использовать канал в р', а сеть Петри является не чувствительной к числу фишек Расигиренные и ограниченные модели сетей Петри в позиции, то потребитель Сз может использовать канал, несмотря на присутствие Ь элементов в буфере Во Таким образом, нечувствительность условий запусков переходов сети Петри к числу фишек в позиции не позволяет корректно моделировать эту приоритетную систему. Более конкретно ограничение на моделирование с помощью сетей Петри состоит в неспособности проверить на наличие точно определенной маркировки в некоторой неограниченной позиции и осуществить действие в зависимости от результатов проверки.
Это ограничение общеизвестно как неспособность к проверке на нулевую маркировку в некоторой позиции, и поэтому это свойство известно как проверка на нуль (150). Сети Петри не могут проверить неограниченную позицию на нуль. [Если позиция ограниченна, то нуль может быть выявлен. Для ограниченной позиции р, с границей Й мы можем создать дополнительную позицию рг— такую, что сумма п(рг) + р(р ) является константой, равной Ь для всех достижимых маркировок.Это позволяет нам проверить, равняется ли р(рг) нулю, проверяя, равно ли р(р ) Й (см.
разд. 5.6).) внражнення 1. Изобразите модель сети Петри для «решения» задачи о курильщиках сигарет с рис. 7.3. Покажите, что эта сеть не является активной. Предложите сеть Петри, которая может решить задачу о курильщиках сигзрет. В чен эта вторая сеть отличается от первой» У.2. Расширения Как указанное ограничение мощности моделирования сети Петри соотносится с предложенными расширениями сетей Петри? Все предложенные расширения направлены на создание в сетях Петри возможности проверки на нуль. Самым простым расширением сетей Петри, которое допускает проверку на нуль, являются сдерживаюгцпв дуги.
Сдерживающая дуга показана на рис. 7.5. Сдерживающая дуга из позиции рг в переход гг имеет маленький кружок, а не стрелку у конца дути, присоединенного к переходу. Это обозначе' ние перешло из теории переключательных функций, где маленький кружок означает «неьп. Правило запуска изменяется следующим образом: переход является разрешенным, когда фишки присутствуют во всех его (обычных) входах и отсутствуют в сдерживающих входах.
Переход запускается удалением фишек из всех его (обычных) входов. Таким образом, в расширенной сети Петри с рис. 7.5 переход ва может быть запущен, только если фишки присутствуют в позициях Ь, н р«и отсутствуют в Ь,. Эта сеть является решением для за- П Отрицание. — Прим. нерев. Глава 7 ! 92 дачи о приоритетном совместном использовании канала, которая сформулирована в (159), чтобы показать ограниченность сетей Петри. Сети Петри со сдерживающими дугами являются интуитивно самым прямым подходом к увеличению мощности моделирования с помощью сетей Петри.
К тому же верно, что все другие предло- га Рис. 7.5. Расширеииая сеть Петри со сдерживааицей дугой. женные расширения сетей Петри либо на самом деле не являются расширением (то есть они фактически эквивалентны обычным сетям Петри), либо являются эквивалентными сетями Петри со сдерживающими дугами. Ниже обсудим несколько предложенных расширений для того, чтобы проиллюстрировать эту точку зрения. ! 7.2Л.
Области ограничения ! Области ограничения были предложены Патилом (231) для увеличения мощности моделирования сетей Петри. В контексте Патила области ограничения были только средством для того, чтобы сделать процесс моделирования проще, а не для того, чтобы увеличить мощность моделирования, поскольку все позиции в работе Патила были ограниченны. Однако определение областей ограничения не исчерпывается ограниченными сетями Петри, а для более общего класса сетей Петри верно, что они эквивалентны сетям Петри со сдерживающими дугами. Чтобы показать эквивалентность областей ограничения н сдерживающих дуг, предположим, что мы имеем сеть Петри С =- (Р, Т, л,О) соблжтью ограничения 9: — Р.
Мы должны гарантировать, что в любой достижимой маркировке не все позиции в Я имеют фишки. Это может случиться только тогда, когда переход гт, будучи запущенным, помещает фишки в те позиции области ограничения, кс- Расширенные и огриниченныс модели сетей Петри Рис. 7.6. Сеть Петри с областью ограни«ения (ра. рД, которая означает, что в произвольной достижимой маркировке фишки могут быть либо в рз, лабо в рт, но ие в обеих одиоврел1еяио.
Рис. 7,7. Сеть Петри со сдерживающими дугамн, соответствующая сети Петри с ограничениями (рис. 7.6). Сдерживающие дуги гарантируют невозможность одновременного появления фишек в поз1щиях рз и рт. 'тз7 — 562 Глава 7 торые не содержали фишек до того, как переход был запущен. Таким образом, для каждого перехода г;, выходные позиции которого являются членами области ограничения, мы должны гарантировать, что по меньшей мере один нз членов области ограничения пе будет маркирован после запуска этого перехода. Для обеспечения этого мы создадим для каждой позиции ра из области ограничения 0, пе вошедшей в 0(1)), новый переход Г;,». Этот переход с) а идентичен Гп за нсключейием того, что он имеет сдерживающую дй) дй) Рис.
7.8. Преооразоаание перехода в переход-НАЧАЛО и переход-КОНЕЦ с позицией, представлякяцей запуск перехода. дугу из ра к () а. Действие, производимое запуском ()л, совпадает с действием, производимым запуском )), и, если 17 может быть запущен без нарушения накладываемого областью ограничения, то по меньшей мере один из Г;„» также может быть запущен.
В качестве примера такого построения рассмотрим сеть Петри на рис. 7.6. Если мы введем область ограничения (р,, р,) (то есть при любой маркировке позиции рз и р, не должны одновременно иметь фишки), то эквивзлентной сетью Петри со сдерживающими дугами будет сеть с рис. 7.7. Преобразование сдерживающих дуг в области ограничения является более сложным.
Мы не можем просто потребовать, чтобы выход перехода не был бы маркирован в одно время со сдерживающим входом, поскольку фишки могут быть помещены в выходные позиции другими переходами. Мы должны сосредоточить свое внимание на переходе Гп Потребуем расщепления каждого перехода Г7 на два перехода, Г и (;", н позицию р)'. Мы определим 1(г ) = 1(г)) (без сдерживающих дуг) и 0(1;") = О())). позиция р)' представляет запуск Г,, поэтому 0(~,') =- (р ) =- !(Г)").
Это показано на рис. 7.8. Теперь определим область ограничения Расширенные и ограниченные модели сетей Петри Оор 01тт) Рис. 7ЛО. Преобразование пере- илючателей в сети Петри со сдер- живающими дутаыи. Рис. 7.9. Интерпретация перехода ис- ключающее ИЛИ с помощью сдержи- вающих дуг. (р;, р ) для каждой позиции рь которая является сдерживаю- щим входом для 1;. Это обеспечит то, что переход не может быть за- пущен, если маркировка р; ненулевая. 7.22.
Переходы исключающее ИЛИ и переключатели Переход истслииииои(ее 7тЛИ гт с входом У(17) требует, чтобы один и только один из его входов бйл не пустым, для того чтобы этот переход был разрешенным. Эта конструкция эквивалентна множеству переходов по одному для каждого элемента в 7(17). Каждый переход имеет один (обычный) вход, а остальные входй являются сдерживающими дугами.
На рис. 7.9 представлен пример. Переключатели также могут быть легко преобразованы в сдерживающие дуги. Это показано на рис. 7.10. Способ преобразования сдерживающих дуг в переключатели или в переходы исключающее ИЛИ не ясен, но такой способ определенно существует. 7.2.3. Другие расспиреиия Имеются еще два других важных расширения сети Петри. Переходам могут быть поставлены в соответствие приоритеты так, что если 7т и 1а оба допустимы, то переход с высшим приоритетом бу'67а~ Глава 7 дет запущен первым 11151. Во временных сетях Петри (1941 каждому переходу 1; сопоставляются два момента времени ть; н т,,1. Переход 11 может быть запущен, только если он был разрешен к моменту времени ть;.
Если он является разрешенным, то должен быть запущен до наступления момента времени тел. Оба этих расширения могут использоваться для проверки на нуль. 77озиттия р ложа /7оожФж рт содерлпап риеияи и Рис. 7.11. Использование приоритетов дли проверки позиций р на нуль. Переход 11 имеет по сравнению с 1а более высокий приоритет. В случае приоритетов легко проверить, есть ли фишка в позиции р, (рис. 7.11). Если мы помещаем фишку в позицию «р; == О?» и назначаем переходу 1~ более высокий приоритет, чем переходу 1„ то в результате в одной из двух позиций справа появится фишка. Выбор позиции зависит от маркировки позиции рп Справедливость этого определяется тем фактом, что переход 1, может быть запущен, только если он разрешен, а он является разрешенным, только если позиция р; имеет фишку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
