14. Сети Петри для моделирования. Моделирование программного обеспечения сетями Петри (блок-схемы, обеспечение параллелизма).

События и условия.

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

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

Особенности сетей Петри и систем, моделируемых с их помощью:

- параллелизм, или одновременность (сети Петри удобны для моделирования систем с распределенным управлением).

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

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

Запуск перехода и соответствующего события рассматривается как мгновенное событие, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным, примитивные события мгновенны и неодновременны.

Примитивные и непримитивные события

Непримитивныминазываются такие события, длительность которых не равна 0. Они не являются неодновременными и, следовательно, могут пересекаться во времени.

Непримитивное событие можно представить в виде двух примитивных событий: ”начало не примитивного события”, “конец не примитивного события”, и условия “не примитивное событие происходит”.

Моделирование программного обеспечения ЭВМ

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

Блок–схемы

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

Отдельный процесс описывается программой:

Программа (вычисление и управление)→ блок–схема → сеть Петри

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

Различие между сетью Петри и блок–схемой.

В сети Петри действие моделируется переходами, а в блок-схеме – узлами. Кроме того, движение фишки по блок-схеме приостанавливается не в узлах, а на дугах. Таким образом, перевод блок-схемы в сеть Петри заменит узлы блок-схемы на переходы сети Петри, а дуги – на позиции сети Петри. Каждая дуга блок-схемы соответствует точно одной позиции. Узлы блок-схемы представляются по-разному в зависимости от типа узла: вычисления или принятие решения.

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

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

Параллелизм

Существует много способов введения параллелизма, рассмотрим два из них.

1. Введение параллелизма в процесс ВС путем использования операций Fork и Join, (Деннис, Ван Хорн).

Операция Fork j выполнимая в предложении i, приводит к одновременномувыпол-нению текущего процесса, начиная с предложения (i + 1), и вновь созданного процесса, начиная с j.

Join соединяет два процесса в один.

2. Подход основан на операциях pаrbegin и parend и имеет вид:

parbegin S₁, S_2, ..., S_n parend,

где S_i – предложение.

Смысл структуры parbegin / parend заключается в параллельном выполнении каж-дого из предложений S₁, S₂, ..., S_n.

Введение параллелизма полезно только в том случае, когда компоненты процессов могут взаимодействовать при получении решения задачи. Такое взаимодействие требует распределения ресурсов между процессами. Распределением надо управлять! Масса проблем синхронизации!