Свойство безопасности и ограниченности сети Петри.
Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, - безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1.
Определение: Позиция сети Петри с начальной маркировкой для любой . Сеть Петри безопасна, если безопасна ее каждая позиция.
Безопасность – очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.
В первоначальном определении сети Петри были безопасны, поскольку переход не мог быть запущен, если не все из выходных позиций были пусты (а кратные дуги не были разрешены). Это объяснялось интерпретацией позиции как условия. Условие, будучи логическим высказыванием либо истинно (представляется фишкой в позиции), либо ложно (представляется отсутствием фишки); кратные фишки не имеют никакой интерпретации. Таким образом, если интерпретировать сети как условия и события, маркировка каждой позиции должна быть безопасной.
Если позиция не является кратной входной или кратной выходной для перехода, ее можно сделать безопасной. К позиции , которую необходимо сделать безопасной, добавляется новая позиция . Переходы, в которых используется в качестве входной или выходной, модифицируются следующим образом:
Если и , тогда добавить к .
Если и , тогда добавить к .
Цель введения этой новой позиции - представить условие « пуста». Следовательно, и дополнительны; имеет фишку, только если не имеет фишки и наоборот.
Любой переход, удаляющий фишку из , должен помещать фишку в и наоборот.
Рис.1. Сеть Петри, не являющаяся безопасной |
Рис.2. Безопасная сеть Петри, эквивалентная сети на Рис.1. |
Начальная маркировка так же должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в , либо в . (Мы допускаем, что начальная маркировка безопасна.) Заметим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равно 0 или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске 2 фишки и, следовательно, не может быть безопасной.
Безопасность – частный случай ограниченности.
Некоторые соображения относительно реального ограничения на аппаратную реализацию позиций позволяют прийти к заключению, что безопасность – необязательное требование. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно-реализованный счетчик ограничен по максимальному числу, которое он может представить.
Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.
Определение: Позиция сети Петри с начальной маркировкой является k-ограниченной, если для всех .
Граница k’ по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция может быть 3-ораниченной, тогда как позиция - 8-ограниченной). Однако, если позиция k-ограничена, то она так же и k’- ограничена для всех k’ >k.
Использование сетей Петри для количественных оценок функционирования параллельных КС
- Классификация параллельных кс по структурно-функциональным признакам.
- Классификация параллельных кс по функциональным возможностям кс с точки зрения пользователя
- Проведите сравнительный анализ классификаций компьютерных систем.
- Мультикомпьютеры, кластеры и симметричные мультипроцессоры общая характеристика, схемы построения, особенности каждой из систем, области применения.
- Системы с распределенной и разделяемой памятью, массово-параллельные системы общая характеристика, схема построения, особенности каждой из систем, области применения.
- Преимущества архитектуры
- Недостатки архитектуры
- Основные понятия теории моделирования параллельных кс. Методы моделирования параллельных кс.
- Задачи моделирования параллельных кс.
- Приведите основные принципы моделирования.
- Моделирование параллельных процессов. Применение аппарата сетей Петри.
- Подклассы сетей Петри:
- Применение сетей Петри для синтеза дискретных управляющих устройств.
- Оценочные или е-сети как расширение сетей Петри
- Моделирование конвейерной обработки информации
- Свойства сохранения и активности сети Петри
- Свойство достижимости и покрываемости сети Петри.
- Свойство безопасности и ограниченности сети Петри.
- Анализ сетей Петри матричным методом
- Матричный метод анализа сетей Петри достоинства и недостатки метода
- Задачи достижимости и покрываемости сети Петри.
- Границы возможности моделирования с помощью сетей Петри
- Подклассы сетей Петри:
- Маркированные графы подкласс сетей Петри
- Сети Петри и их особенности
- Разбиения чисел. Основные понятия и определения. Принцип Дирихле.
- Вложимость разбиений.
- Ранговое условие вложимости; пример использования.
- Принцип полного размещения; пример использования.
- Вложимость с ограничениями; пример использования.
- Особенностью распределения памяти в кс с сегментной организацией программ и данных (модель 2). Приведите пример.
- Комбинаторная модель для оценки необходимого размера памяти кс (модель 4). Приведите пример.
- Комбинаторная модель, позволяющая произвести расчет оценки сверху необходимого размера оперативной памяти кс.
- Диаграммы Ферре и инверсия в бинарных последовательностях
- Надежность кольцевой структуры кс (для сети [n,2]).
- Надежность сети кс.
- Связанные случайные величины
- Детерминированные меры живучести для многополюсных сетей
- Матричная теорема о деревьях для графов (пример)
- Теорема Кирхгофа-Трента
- Каркасы в ориентированных графах
- Надежность сети относительно одного источника и многих стоков