Подклассы сетей Петри:

    Простой сетью Петри называется набор , где

1.  - множество мест;

2.  - множество переходов таких, что .

3.  - отношение инцидентности такое, что:

a. 

b. 

    Регулярные сети (вводится алгебра регулярных сетей, строятся операции над сетями и классы элементарных сетей). Чистые сети (переход не может иметь позицию Pi в качестве входной и выходной). Сети свободного выбора (этот подкласс допускает и конфликты автоматных сетей Петри, и параллельность маркированных графов, но в более ограниченном виде, чем в обычных сетях Петри. Сеть Петри со свободным выбором есть сеть Петри С = (Р, Т, I, О) — такая, что для всех Важность этого определения заключается в том способе, которым оно допускает управляемые конфликты. Конфликт появляется только тогда, когда одна позиция является входом нескольких переходов. По определению сетей Петри со свободным выбором, если позиция является входом для нескольких переходов (потенциальный конфликт), то она является единственным входом всех этих переходов. Следовательно, либо все эти конфликтующие переходы одновременно являются разрешенными, либо ни один из них. Это позволяет свободно осуществлять выбор (разрешение конфликта) запускаемого перехода, присутствие фишек в других позициях не влияет на выбор запускаемого перехода. Сети, свободные от конфликтов, если Pi принадлежит I( tj), то Pi принадлежит О( tj), иначе Pi должна иметь <= 1 выходной переход. Устойчивые сети ( для такой сети маркировка принадлежит множеству допустимых маркировок, если 2 любых перехода оказываются в возбужденном состоянии, то срабатывает один из них не исключая возможности срабатывания другого ) Автоматные графы ( каждый переход может иметь точно один выход и один вход) Маркированный граф – сеть Петри

НЕ нашли? Не то? Что вы ищете?

Расширение сетей Петри.

·  Е-сети

·  Сети Мерлина

·  Временные сети

·  Раскрашенные сети

·  Приоритеные сети

·  Сети с проверкой на ноль

·  Обобщенные сети.

Применение сетей Петри для синтеза дискретных управляющих устройств.

Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События - это действия, имеющие место в системе. Возникновением событий управляет состояние системы Состояние системы может быть описано множеством условий Условие — есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь». Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий, постусловий.

В качестве примера рассмотрим задачу моделирования простого автомата-продавца. Автомат-продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиями для такой системы являются:

а) автомат-продавец ждет;

б) заказ прибыл и ждет;

в) автомат-продавец выполняет заказ;

г) заказ выполнен.

Событиями будут:

1. Заказ поступил.

2. Автомат-продавец начинает выполнение заказа.

3. Автомат-продавец заканчивает выполнение заказа.

4. Заказ посылается на доставку.

Предусловия события 2 (автомат-продавец начинает выполнение заказа) очевидны:

(а) автомат-продавец ждет; (б) заказ прибыл и ждет.

Постусловие для события 2:

(в) автомат-продавец выполняет заказ.

Аналогично мы можем определить предусловия и постусловия для других событий и составить следующую таблицу событий и их пред - и постусловий:

Событие

Предусловие

Постусловие

1

нет

б

2

а, б

в

3

в

г, а

4

г

нет

Такое представление системы легко моделировать сетью Петри.

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

Можно моделировать и более сложную систему. Система автомат-продавец состоит из трех различных автоматов M1 , М2 и М3 и двух операторов Fx и F2. Оператор F1 воздействует на автоматы М1 и М2, а оператор F2 — на М1 и М3. Заказы требуют двух стадий обработки. Сначала они должны быть обработаны автоматом М1 затем либо автоматом М2 либо М3. Эта более сложная система будет иметь следующие условия:

а) заказ прибыл и ждет обработки автоматом М1

б) заказ обработан автоматом М1 и ждет обработки либо автоматом М2, либо М3;

в) заказ выполнен;

г) автомат M1 незанят;

д) автомат М2 незанят;

е) автомат М3 незанят;

ж) оператор F1незанят;

з) оператор F2 незанят;

и) автомат М{ находится под воздействием оператора F1

к) автомат М1{ находится под воздействием оператора F2,

л) автомат М2 находится под воздействием оператора F1,

м) автомат М3 находится под воздействием оператора F2.

При этом могут происходить следующие события:

1. Поступление заказа.

2. Оператор F1 начинает выполнение заказа на автомате M1

3. Оператор F1 закончил выполнение заказа на автомате М1.

4. Оператор F2 начинает выполнение заказа на автомате М1.

5. Оператор F2 закончил выполнение заказа на автомате М1.

6. Оператор F1 начинает выполнение заказа на М2.

7. Оператор F1 закончил выполнение заказа на М2.

8. Оператор F2 начинает выполнение заказа на М3.

9. Оператор F2 закончил выполнение заказа на М3.

10. Заказ посылается на доставку.

12.  Оценочные или Е-сети как расширение сетей Петри

Е-сети (

P – множество позиций,

Pp множество периеритных позиций

PR множество решающих позиций

T – множество переходов причем ti = ( ρS, t(ti) )

S – тип перехода (, t(ti) время перехода, ρ(ti) – функция перехода, функция преобразования атрибута меток.

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

Типы переходов:

1. простой переход, срабатывает при наличии фишки в P1 и отсутсвии в P2, моделирование некоторого устройства обработки инф.

2. разветвление потока транзактов в ВС.

3. объединение наличие фишек P2, P3 и отстутсвие в P1

4. управляющие разветвление изменяет направление потока транзактов.

5. приоритетность одних потоков к другим

Моделирование конвейерной обработки информации

На протяжении последних лет было предпринято множество шагов направленных на увеличение производительности ВС. Результатом одного из таких шагов было появление ВС с конвейерной обработкой информации. Конвейер состоит из набора операций которые могут выполняться параллельно. Когда операция k завершена, она передает свой результат (k+1)-й операции и ждет данных от (k-1)-й.

В качестве примера рассмотрим сложение 2 чисел с плавающей точкой. Основные шаги этой операции предполагают:

Выделить экспоненты этих 2 чисел Сравнить эти экспоненты, и если необходимо изменить их должным образом Сдвинуть точку в числе с меньшей экспонентой для их уравнения Сложить дроби Нормализовать результат Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата

Конвейеры (по способу управления) можно разделить на 2 группы: синхронные и асинхронные. Синхронные конвейеры каждый такт передают данные на следующий шаг обработки. Но это не эффективно, т. к. действие, выполняемое на данном шаге, может занимать времени больше/меньше чем 1 такт. Рассмотрим k-й блок конвейера. Для управления им нужно знать когда выполняются следующие условия:

    Входной регистр заполнен Входной регистр пуст Выходной регистр заполнен Выходной регистр пуст Блок занят Блок свободен Пересылка осуществлена

13.  Задачи сохранения и активности сети Петри

Сохранение

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

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

Def. Сеть Петри C=(P,T,I,O) с начальной маркировкой называется строго сохраняющей, если для всех имеет место .

Строгое сохранение – это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов . Если бы это было не так, запуск перехода изменил бы число фишек в сети.

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

Def. Сеть Петри C=(P,T,I,O) с начальной маркировкой называется сохраняющей по отношению к вектору взвешивания , если для всех имеет место

Строго сохраняющая сеть Петри является сохраняющей по отношению в вектору взвешивания (1, 1, … ,1).

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

Активность

Причиной рассмотрения сохранения в сети Петри было распределение ресурсов в операционной системе ЭВМ. Другая задача. Которая может возникнуть при распределении ресурсов вычислительной системы – тупики.

Рассмотрим простой пример.

Система включает 2 различных ресурса q и r и два процесса a и b. Если оба процесса нуждаются в обоих ресурсах, им необходимо будет совместно использовать ресурсы. Для выполнения этого потребуем чтобы каждый процесс запрашивал ресурс, а затем освобождал его. Теперь предположим, что процесс a сначала запрашивает ресурс q, а затем ресурс r и наконец освобождает и q и r. Процесс b работает аналогично, но сначала запрашивает ресурс r, а потом q.

Начальная маркировка помечает ресурсы и доступными и указывает на готовность процессов a и b. Одним выполнением этой сети является ; другим - . Ни одно из этих выполнений не приводит к тупику. Однако рассмотрим последовательность, которая начинается переходами : процесс a обладает ресурсом q и хочет получить ресурс r, а процесс b обладает ресурсом r и хочет получить ресурс q. Система заблокирована; никакой процесс продолжаться не может.

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

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

Другие понятия, связанные с изучением тупиков, можно разбить на категории по уровню активности и определить для сетей Петри С с маркировкой следующим образом:

Уровень 0: Переход обладает активностью уровня 0, если он никогда не может быть запущен.

Уровень 1: Переход обладает активностью уровня 1, если он потенциально запустим, т. е. если существует такая , что разрешен в .

Уровень 2: Переход обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой присутствует неограниченно часто.

Уровень 3: Переход обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой присутствует неограниченное число раз.

Уровень 4: Переход обладает активностью уровня 4, если для всякой существует такая последовательность запусков , что разрешены в

Переход, обладающий уровнем активности 0, называется пассивным; активностью 4, называется активным. Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.

Переход не может быть запущен никогда, он пассивен. Переход может быть запущен ровно 1 раз, он обладает активностью уровня 1. Переход может быть запущен произвольное число раз, но это число зависит от числа запусков перехода . Если мы хоти запустить 5 раз, то мы запускаем 5 раз , затем и после этого 5 раз . Однако, как только запустится число запусков станет фиксированным. Следовательно обладает активностью уровня 2. Переход может быть запущен неограниченное число раз, и поэтому обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится , больше запустить будет нельзя.

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

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

Пример:

2 блока умножения , блок сложения и блок деления .

Регистры с по .

Проследим выполнение на такой системе следующих операций:

умножить на , результат поместить в . умножить на , результат поместить в . сложить с , результат поместить в . сложить с , результат поместить в . разделить на , результат поместить в .

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

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

Вторая операция сложения требует наличия свободного блока сложения, исходных данных из и . Ни один из ресурсов не получен, поэтому необходимо ожидать выполнения операции 3 для освобождения блока сложения, операции 2 для получения корректных данных из и операции 1 для получения корректных данных из .

Последняя операция (деление) может быть выполнена только при свободном блоке деления (выполнено), корректных данных в (необходимо ждать выполнения операции 1), корректных данных в (необходимо ждать выполнения операции 3) и свободного регистра (выполнено).

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

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

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

Проведем моделирование работы части системы с помощью сети Петри. Пусть дан функциональный блок и регистры . Поставим функциональному блоку и каждому из регистров позицию, указывающую на занятость ресурса (данные позиции дублируют элементы таблицы резервирования). Если в позиции есть фишка, то ресурс свободен, иначе – занят. Для обеспечения связи с внешними воздействиями (декодирована очередная инструкция, которая будет выполнена на блоке и использующая регистры ; инструкция поступила на выполнение и необходимо декодировать следующую инструкцию) введем две дополнительные позиции.

В результате получим следующее множество позиций:

·  - декодирована инструкция, использующая блок и регистры .

·  - блок свободен.

·  - регистр свободен.

·  - регистр свободен.

·  - регистр свободен.

·  - инструкция поступила на выполнение, готовность декодировать следующую инструкцию.

·  - инструкция поступила на выполнение, функциональный блок работает с регистрами .

События:

·  Выдача очередной инструкции на выполнение. Происходит при выполнении условий: есть инструкция, использующая и ; блок свободен; регистр свободен; регистр свободен; регистр свободен. Результатом события являются: выборка инструкции и готовность декодирования следующей; поступление инструкции на выполнение, которое влечет резервирование и .

·  Окончание выполнения инструкции. Естественно, для наступления данного события необходимо поступление инструкции на выполнение в предыдущий момент времени. Результатом события будет освобождение ранее зарезервированных ресурсов.

Описанные события соответствуют переходам и .

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5