Шпаргалка по "Программированию и компьютерам"

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

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

Моде лирование последовательных процессов.

 

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

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

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

В сети Петри (рисунок 4.6), моделирующей блок-схему, узлы блок-схемы представляются переходами сети Петри как показано ниже, а дуги блок-схемы — позициями сети Петри. Фишка в сети Петри представляет счетчик команд блок-схемы.

Моделирование взаимодействия процессов.

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

 

31. Свойства сетей Петри, примеры решения задач

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

Позиция сети Петри c начальной маркировкой является безопасной, если она является 1-ограниченной. Сеть Петри безопасна, если безопасны все позиции сети.

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

.

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

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

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

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

Сеть Петри называется живой, если все её переходы являются живыми.

Задача достижимости: Для данной сети Петри с маркировкой и маркировки определить: ?

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

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

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

Сеть Петри  с начальной маркировкой и сеть Петри с начальной маркировкой эквивалентны, если справедливо .

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

Более слабым, по сравнению с эквивалентностью, является свойство включения, определение которого совпадает с определением эквивалентности, с точностью до замены = на Í.

32.Методы борьбы  с тупиками

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

• предотвращение тупика;
• обход тупика;
• обнаружение (распознавание) тупика с последующим восстановлением.

Стратегии предотвращения тупиков

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

• Условие взаимоисключения можно подавить путем разрешения неограниченного разделения ресурсов.
• Условие ожидания можно подавить, предварительно выделяя ресурсы.
• Условие отсутствия перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы.
• Условие кругового ожидания можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выделения ресурсов.

Обход тупиков

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

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

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

Имя процесса	Выделено	Запрос	Max потребность	Остаток потребностей
А	2	3	6	1
B	3	2	7	2
C	2	3	5	0

 

Обнаружение тупиков. Графы распределения ресурсов. Обнаружение тупика - это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию.

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

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