русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 1143; Нарушение авторских прав


 

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

 

 

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

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

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

 

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

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

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

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

 

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

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

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



å m(pi) = å m0(pi).

piÎP piÎP

 

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

 

Активность.Другой задачей, возникающей при распределении ресурсов, является задача выявления тупиков. Рассмотрим на рис. 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 маркировки MÎR(C, M0). К этой задаче могут сводиться многие перечисленные выше задачи. Например, тупик в сети на рисунке может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

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

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

 



<== предыдущая лекция | следующая лекция ==>
Методы анализа характеристик сетей. | Методы анализа на основе дерева достижимости


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.008 сек.