Классификация параллельных КС по структурно-функциональным признакам (стр. 3 )

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

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

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

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

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

Сеть Петри 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, поскольку, как только запустится , больше запустить будет нельзя.

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

16. Задачи достижимости и покрываемости сети Петри.

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

Для сети Петри С с маркировкой μ, маркировка μ’ называется непосредственно достижимой из μ, если существует переход tj такой, что δ(μ ,tj)=μ’.

Задача достижимости. Для заданной сети Петри C с маркировкой μ и маркировки μ’ определить, верно ли, что. μ’R(C, μ), где R(C, μ) – множество достижомсти сети Петри С с маркировкой μ.

Пример:

Для сети изображенной на рисунке и маркировке μ =(1,0,0) непосредственно достижимыми являются две маркировки (1,0,1) и (0,1,0). Из маркировки (1,0,1) можно получить маркировку (0,1,1) и (0,1,2). Из (0,1,0) нельзя достичь не одной маркировки, так как ни один переход не разрешен. Можно показать, что множество достижимостей имеет следующий вид для этой сети R(C,μ)={(1,0,n),(0,1,n)|n>=0}

Задача покрываемости. Для данной сети Петри C с начальной маркировкой и маркировки определить, существует ли такая достижимая маркировка , что .

Отношение m"³m’ истинно, если каждый элемент маркировки m" не меньше соответствующего элемента маркировки m’.

17. Задача безопасности и ограниченности сети Петри

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

Формальное определение безопасности позиции: позиция PiP в сети Петри С=(P, T, I, O) с начальной маркировкой µ является безопасной, если µ'(Pi)<=1 для любой µ'.

Безопасность очень важное свойство для устройств аппаратного обеспечения. Позицию можно реализовать одним триггером, если она безопасна. Если позиция не является кратной входной или выходной для перехода ее можно сделать безопасной добавляя новые позиции Pi'.

Небезопасная сеть:

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

если Pi I(tj) и PiO(tj) тогда P’ к O(tj)

если Pi O(tj) и PiI(tj) тогда P’ к I(tj)

Безопасная сеть:

Цель введения новой позиции P1' - представить условие P1 пусто, следовательно P1 и P1' дополнительны: P1 имеет фишку только если P1’ не имеет фишки и наоборот. Любой переход, удаляющий фишку из P1 должен помещать фишку в P1'. Начальная маркировка также должна быть модифицирована, для обеспечения того, чтобы точно одна фишка была либо в P1 либо P1'.

Для моделей реальных систем анализ на безопасность позволяет проверить возможность работы системы в некотором стационарном режиме. При анализе на безопасность могут быть выявлены требования к накопительной системе (внутренним буферам).

Ограниченность сети Петри.

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

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

Формальное определение: позиция PiP в сети Петри С=(P, T, I, O) с начальной маркировкой µ является К-безопасной, если µ(Pi)<=K для всех µ'R(C, µ).

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

19. Моделирование сетями Петри задач синхронизации при взаимодействии процессов в КС

Взаимосисключение – это метод создания таких программ, что одновременно не более чем 1 ресурс имеет доступ к разделяемому объекту. Для предотвращения проблем такого рода необходимо обеспечить механизм взаимного исключения. Взаимное исключение это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому объекту данных. Участок кода, в котором осуществляется доступ к разделяемому объекту и который требует защиты от вмешательства других процессов, называется критической секцией. Идея состоит в том, что когда процесс готов выполнить свою критическую секцию, он сначала ждет, пока другой процесс не выполнит свою собственную критическую секцию. Затем он «блокирует» доступ к критической секции, не давая возможности никакому другому процессу войти в свою критическую секцию. Он входит в критическую секцию, выполняет ее и, выйдя из нее, освобождает ее для доступа со стороны других процессов.

Эта задача может быть решена сетью Петри, как показано на рисунке слева. Позиция m представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в р1 или в р2 соотв-нно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в m, дающая раз - разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит переход t2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m

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

P - и V-системы.

Большинство задач синхронизации не могут быть решены непосредственно сетями Петри, но они разрешимы на основе известных механизмов синхронизации. В частности, одним из самых популярных механизмов синхронизации являются P - и V - операции над семафором.

Семафор это элемент данных, который может принимать только неотрицательное целое значение.

V - операция увеличивает значение семафора на единицу, а P - операция - уменьшает.

P - операцию можно применять только в том случае, когда значение семафора остается в результате неотрицательным. Если же значение семафора равно нулю, то P операция должна ждать, пока другой процесс не выполнит V операцию.

P и V операции определены как примитивные, то есть никакая другая операция не может изменять значение семафора одновременно с ними. P и V операции легко моделируются сетью Петри. Это показано на рисунке:

Каждый семафор моделируется позицией. Количество фишек в семафоре показывает значение семафора. Р операция использует позицию семафора в качестве входа, V – в качестве выхода.

P и V операции являются основной связью между процессами.

P - операция – вход

V - операция – выход

Преимущество такого описание заключается в том, что PV-система описывается с помощью PV-операций.

20. Задача активности сетей Петри

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

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

Система включает 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, поскольку, как только запустится , больше запустить будет нельзя.

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

21. Анализ сетей Петри матричным методом

Анализ сетей Петри основывается на матричном способе представления сетей Петри. Матричный способ основывается на работах Хека. Альтернативным способом по отношению к определении сети Петри в виде С=(P, T, I, O) является определение двух матриц D+, D-. Причем матрица D+ представляет входную функцию, а D - выходную. C=(P, T, D+, D-). C=(P, T, F, B) – представление Хека.

Определим матрицы:

D-(j, i) = #(Pi, I(tj))

D+(j, i) = #(Pi, O(tj))

То есть D- определяет входы переходов, а D+ выходы. Матричная форма представления сети Петри C=(P, T, D+, D-) эквивалентна стандартному, но позволяет дать определение в терминах векторов и матриц.

Пусть e[j] – m-вектор, содержащий нули везде, кроме j-ой компоненты. Переход tj представляется m-вектором e[j], причем e[j] – это вектор строка. Переход tj в маркировке μ разрешен, если μ >=e[j]*D-, а результат запуска перехода tj в маркировке μ записывается следующим образом: , где D=D+-D-.

Тогда для последовательности запусков переходов можно получить

Вектор называется вектором запуска последовательности переходов . i-ый элемент вектора - это число запусков перехода tj в последовательности . Является вектором с неотрицательным целым компонентом. Вектор - это отображение Париха.

Отображение Париха.

Пусть дана конечная область D={d1, d2, …, dn}. Существует естественное соответствие между каждым комплектом B на областью D и n-вектором F={f1, f2, … ,fn}, определяемым соотношением fi=#(di, B) – отображение Париха.

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

Необходимо найти ненулевой весовой вектор, для которого взвешенная сумма во всех достижимых маркировках постоянна. Пусть W размерности (nx1) – вектор-столбец. Тогда если μ - начальная маркировка, а μ' произвольно достижима маркировка необходимо, чтобы μW=μ'W. Поскольку μ' достижима, то существует последовательность запусков , которая переводит сеть Петри из μ в μ'. Поэтому:

.

, но т. к.

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

Это обеспечивает простой алгоритм проверки свойства сохранения, а также позволяет получить вектор взвешивания W. Тогда существует последовательность, возможно пустая, запусков переходов , которая приводит μ в μ’. Это значит, что является неотрицательным целым решением следующего матричного уравнения: .

Следовательно, если μ' достижима из μ, то уравнение имеет решение в неотрицательных целых. Если же уравнение не имеет решения, то маркировка μ' не достижима из маркировки μ.

Пример.

Выбираем начальную маркировку μ0=(1, 0, 1, 0).

Переход t3 ( f(σ)=(0,0,1) ) разрешен и приводит к маркировке:

μ’=(1, 0, 1, 0)+(0, 0, 1)* =(1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).

22. Матричный метод анализа сетей Петри- достоинства и недостатки метода.

Достоинства:

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

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