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

Опишем входные и выходные функции:

В начальный момент времени все ресурсы свободны, операции для выполнения еще нет. Поэтому начальная маркировка будет следующая: . Граф построенной сети Петри представлен ниже:

Данная схема проста и не учитывает таких факторов как:

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

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

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

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

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

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

Задача достижимости является одной из важнейших при анализе сетей Петри. Многие другие задачи анализа можно сформулировать в ее терминах.

Для сети Петри с рис. 4.6 тупик может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

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

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

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

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

Безопасность – очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.

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

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

Если и , тогда добавить к .

Если и , тогда добавить к .

Цель введения этой новой позиции - представить условие « пуста». Следовательно, и дополнительны; имеет фишку, только если не имеет фишки и наоборот.

Любой переход, удаляющий фишку из , должен помещать фишку в и наоборот.

Рис.1. Сеть Петри, не являющаяся безопасной

Рис.2. Безопасная сеть Петри, эквивалентная сети на Рис.1.

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

Безопасность – частный случай ограниченности.

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

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

Определение: Позиция сети Петри с начальной маркировкой является k-ограниченной, если для всех .

Граница k’ по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция может быть 3-ораниченной, тогда как позиция - 8-ограниченной). Однако, если позиция k-ограничена, то она так же и k’- ограничена для всех k’ >k.

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

Синхронизация.

Взаимосисключение – это метод создания таких программ, что одновременно не более чем 1 ресурс имеет доступ к разделяемому объекту.

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

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

.

В задаче о производителе/потребителе также присутствует совместно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель cоздает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и использует. Такая ситуация может быть промоделирована сетью Петри так, как показано на рис. 3.29. Позиция В представляет буфер, каждая фишка соответствует элементу данных, который произведен, но еще не использован. Один из вариантов этой задачи — это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис. 3.30 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис. 3.29, Существует несколько вариантов задачи о чтении/записи, однако основная структура их остается неизменной. Имеются процессы двух типов: процессы чтения и процессы записи. Все процессы совместно используют общий файл или переменную или элемент данных. Процессы чтения не изменяют объект в отличие от процессов записи. Таким образом, процессы записи должны взаимно исключать все другие процессы чтения и записи, в то время как несколько процессов чтения могут иметь доступ к разделяемым данным одновременно. Задача состоит в определении структуры управления, которая не приведет к тупику и не допустит нарушения критерия взаимного исключения.

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

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

Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к определению сети Петри в виде (Р, T, I, O) является определение двух матриц D+ и D-, представляющих входную и выходную функции. (Они эквивалентны функциям F и В определения Хэка сетей Пет - Петри, см. разд. 2.6.) Каждая матрица имеет m строк (по одной на переход) и n столбцов (по одному на позицию). Определим D-[j, i]= , a , D- определяет входы в переходы, D+ — выходы.

Матричная форма определения сети Петри (Р, T, D- , D+) эквивалентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть e[j] — m-вектор, содержащий нули везде, за исключением j-й компоненты. Переход tj представляется m-вектором e[j]2). Теперь переход tj в маркировке μ разрешен, если μ > e[j] • D-, а результат запуска перехода tj в маркировке μ записывается как

D - составная матрица измененй, тогда для последовательности запусков имеем

Вектор называется вектором за - запусков последовательности i-и элемент вектора , — это число запусков перехода ti в последовательности . Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами.

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

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

Поскольку это должно быть верно для всех , имеем . Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный вектор w, что D • w = 0. Это обеспечивает простой алгоритм проверки сохранения, а также позволяет получать вектор взвешивания w. Развитая матричная теория сетей Петри является инструментом для решения проблемы достижимости. Предположим, что маркировка ' достижима из маркировки . Тогда существует последовательность (возможно, пустая) запусков переходов а, которая приводит из к '. Это означает, что является неотрицательным целым решением следующего матричного уравнения для х: . Следовательно, если достижима из тогда уравнениеимеет решение в неотрицательных целых; если уравнение ) не имеет решения, тогда ' недостижима из .

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

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

21. Маркированные графы – подкласс сетей Петри

Маркированный граф – сеть Петри

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

22. P - и V- операции над семафорами, моделирование P/ V - систем сетью Петри

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

Большинство задач синхронизации не могут быть решены непосредственно сетями Петри, но они разрешимы на основе известных механизмов синхронизации. В частности, одним из самых популярных механизмов синхронизации являются P и V операции над семафором. Семафор это элемент данных, который может принимать только неотрицательное целое значение. V операция увеличивает значение семафора на единицу, а P операция уменьшает. P операцию можно применять только в том случае, когда значение семафора остается в результате неотрицательным. Если же значение семафора равно нулю, то P операция должна ждать, пока другой процесс не выполнит V операцию. P и V операции определены как примитивные, то есть никакая другая операция не может изменять значение семафора одновременно с ними. P и V операции легко моделируются сетью Петри. Это показано на рисунке:

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

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

Границы возможности моделирования с помощью сетей Петри

Дейкстра определил свои Р - и V-операции над семафорами для обеспечения инхронизации и связи в системах взаимодействующих процессов [78]. Семафор может рассматриваться как целочисленная переменная, которая принимает только нтрицательные значения.

V-операция над семафором S увеличивает значение семафора на единицу: S = S + 1. Р-операция, наоборот, уменьшает S на едиединицу до тех пор, пока результат не становится равным нулю; при S = 0 процесс, прежде чем продолжать свою работу, должен ждать

момента, когда S можно будет уменьшить. Связь между семафорами и сетями Петри была выявлена в разд. 3.4.8.

Поскольку Р - и V-операции были предложены как механизм для решения всех задач синхронизации программ, то естественно возникает вопрос о полноте, т. е. об их способности к решению всех задач координации. Патил в 1971 г. [233] предложил доказательство того, что Р - и V-операции недостаточно мощное средство для решения всех задач координации. Его подход был весьма прост: он сформулировал задачу синхронизации, которая не может быть решена с помощью Р - и V-операций, — это задача о курильщиках сигарет.

Задача о курильщиках сигарет включает (по меньшей мере) четыре процесса, которые моделируют агента и трех курильщиков. Каждый курильщик непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы три составные части: татабак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой — табак, а третий — спички. Агент обладает бесконечными запасами всех трех составных частей. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех инградиентов, и цикл повторяется.

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

Соответствующий процесс курильщика уменьшает два семафора (с помощью Р-операций), а затем, произведя действия «сделать сигарету» и «закурить сигарету», увеличивает семафор, указывая «сделано». Задача заключается в том, чтобы разработать программу процессов курильщиков для того, чтобы определить, какой из трех процессов должен действовать в очередной момент. Действия агента фиксированны и не могут быть изменены.

Рис. 7.3 иллюстрирует очевидное «решение». Предположим, агент кладет табак и бумагу [V(t), V(p)]. Тогда курильщик с бумагой может взять табак [P(t)], а курильщик с табаком может взять бумагу [Р(р)], что в результате приводит к тупику. Патил доказал, что никакая последовательность Р - и V-операций не может корректно решить эту задачу. Это было показано с помощью доказательства того, что все Р- и V-«peшeния» могут быть промоделированы сетями Петри определенного вида (каждый переход имеет не более двух входов), но что решением является сеть Петри другого вида, и нет способа преобразовать сеть одного вида в сеть другого вида, не допуская возможности возникновения тупика.

Более конкретно ограничение на моделирование с помощью сетей Петри состоит в неспособности проверить на наличие точно определенной маркировки в некоторой неограниченной позиции и осуществить действие в зависимости от результатов проверки. Это ограничение общеизвестно как неспособность к проверке на нулевую маркировку в некоторой позиции, и поэтому это свойство известно как проверка на нуль [150]. Сети Петри не могут проверить неограниченную позицию на нуль. [Если позиция ограниченна, то нуль может быть выявлен. Для ограниченной позиции pi с границей k мы можем создать дополнительную позицию рi — такую, что сумма является константой, равной k для всех достижимых маркировок. Это позволяет нам проверить,

равняется ли нулю, проверяя, равно ли k (см. разд. 5.6).]

23. Сети Петри и их особенности

Def. Сеть Петри – четверка С=(P,T,I,O), где P – множество позиций, T – множество переходов, I – является входной функцией (отображением из переходов в комплекты позиций), O – выходная функция (отображения из переходов в позиции).

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

Возможно несколько подходов к использованию сетей Петри при проектировании и анализе ВС:

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

Ответы на вопросы №31,32,33 (для всех один и тот же рисунок)

Матрицы, представляющие входную и выходную функцию:

Составная матрица изменений:

24. Покажите, используя матричный метод анализа сетей Петри, что маркировка (0, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке.

Решение:

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

( должны быть неотрицательными целыми) Получим систему уравнений, которая не имеет решения

Маркировка недостижима.

25. Дана последовательность запусков переходов s = t3 t2 t3 t2 t1 сети Петри, изображенной на рисунке. Определите вектор запуска и маркировку m’ сети Петри.

Решение:

Последовательность s = t3 t2 t3 t2 t1 представляется вектором запусков t1 в s встречается 1 раз, t2 – 2 раза, t3 тоже 2 раза, тогда.

Из рисунка начальная маркировка . Маркировка

26. Определите является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке. Найдите последовательность запусков переходов s.

Решение:

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

( должны быть неотрицательными целыми) Получим систему уравнений:

,

Что соответствует последовательности запусков s = t3 t2 t3 t2 t3 t2 t3 t2 t3. Маркировка достижима.

Понятия множества и мультимножества и операции со множествами и мультимножествами.

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

Атрибутными свойствами множества являются:

1.  различимость всех частей множества

2.  неупорядоченность частей множества

3.  целостность множества

Различают 2 типа частей множества:

1.  элементы – неделимые и непустые части множества

2.  подмножества – остальные его части

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

Отказ от различимости элементов приводит к понятию мультимножества или комплекта.

Мультимножество – совокупность элементов, среди которых могут быть одинаковые (неразличимые).

Всякое мультимножество можно представить:

1.  его основанием, т е множеством всех его различимых элементов

2.  кратностями – числами повторений каждого элемента основания этого мультимножества.

В теории множетсв основным понятием является включение – это отношение связывает элементы и мн-ва и определяет, какие эл-ты являются членами какого мн-ва.

Основным понятием мультимножеств является функция числа экземпляров. Эта функция определяет число экземпляров элемента в комплекте.

Обозначим число экземпляров X в комплекте B как

Над комплектами можно производить 4 операции:

Ниже перечислены основные операции над множествами:

пересечение:

объединение:

Если множества A и B не пересекаются: то их объединение обозначают также:

дополнение:

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):

разность:

симметрическая разность:

Декартово или прямое произведение:

27. Понятие о монотонной структуре.

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

1)

2)

3) , если X > Y – совокупность n условий, что , при , причём хотя бы одно неравенство выполняется строго.