![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сети Петри
Одно из основных достоинств аппарата сетей Петри заключается в том, что они могут быть представлены как в графической форме (что обеспечивает наглядность), так и в аналитической (что позволяет автоматизировать процесс их анализа). При графической интерпретации сеть Петри представляет собой граф особого вида, состоящий из вершин двух типов — позиций и переходов, соединенных ориентированными дугами, причем каждая дуга может связывать лишь разнотипные вершины (позицию с переходом или переход с позицией). Вершины-позиции обозначаются кружками, вершины-переходы - черточками. С содержательной точки зрения переходы соответствуют событиям, присущим исследуемой системе, а позиции — условиям их возникновения. Таким образом, совокупность переходов, позиций и дуг позволяет описать причинно-следственные связи, присущие системе, но в статике. Чтобы сеть Петри «ожила», вводят еще один вид объектов сети — так называемые фишки, или метки позиций. Переход считается активным (событие может произойти), если в каждой его входной позиции есть хотя бы одна фишка [3]. Расположение фишек в позициях сети называется разметкой сети (пример перемещения фишек по сети приведен на рисунке 14.1.).
Рис. 14.1. Пример изменения разметки сети Петри при срабатывании переходов В аналитической форме сеть Петри может быть представлена следующим образом: P=(B, D, I, 0, M), где В = {bi} — конечное непустое множество позиций; D = {di } — конечное непустое множество переходов; I: BxD → 0, 1 — входная функция (прямая функция инцидентности), которая для каждого перехода задает множество его входных позиций; О: DxB→ 0, 1 — выходная функция (обратная функция инцидентности), которая для каждого перехода задает множество его входных позиций; М - функция разметки сети, т.е. М: В → 0, 1, 2,... - ставит каждой позиции сети в соответствие неотрицательное целое число. Срабатывание перехода dj изменяет разметку сети М(В) на разметку M'(B) по следующему правилу: М'(В) = М(В) – I(dj) + O(dj),
Основные направления анализа сети Петри следующие: 1. Проблема достижимости: в сети Петри с начальной разметкой М0. Требуется определить, достижима ли принципиально некоторая разметка М' из М0 С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы. 2. Свойство живости. Под живостью перехода понимают возможность его срабатывания в данной сети при начальной разметке M0. Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе). 3. Безопасность сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций. Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определены требования к буферным накопителям в системе. Итак, достоинства сетей Петри заключаются в том, что они: 1. позволяют моделировать ПП всех возможных типов с учетом вероятных конфликтов между ними; 2. обладают наглядностью и обеспечивают возможность автоматизированного анализа; 3. позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов).
Контрольные вопросы 1. Дайте формальное определение сети Петри? 2. Что такое разметка сети? 3. Укажите основные направления анализа сетей Петри. 4. Перечислите достоинства и недостатки сетей Петри. 5. Где можно применять сети Петри?
|