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

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

Существует 2 вида параллельных процессов (ПП):

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

- Синхронные – состояния которых зависят от состояния других ПП. Пример синхронного ПП — работа торговой организации и доставка товара со склада.

В рамках синхронных ПП выделяют:

- подчиненный ПП – создается и управляется другим процессом;

- независимый ПП – процесс, не являющийся подчиненным ни для одного процесса.

Способ организации параллельных процессов в системе зависит от физической сущности этой системы. Реализация параллельных процессов в вычислительных системах (ВС) имеет свои особенности:

- на уровне задач вычислительные процессы могут быть истинно параллельными только в многопроцессорных ВС или вычислительных сетях;

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

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

В силу перечисленных особенностей для организации взаимодействия параллельных процессов в ВС используются три основных подхода:

- на основе «взаимного исключения»;

- на основе синхронизации посредством сигналов;

- с использованием специализированных протоколов и сообщений.

Эти механизмы реализуются в ВС на двух уровнях — системном и прикладном.

Механизм взаимодействия между ПП на системном уровне определяется на этапе разработки ВС и реализуется средствами операционной системы (частично — с использованием аппаратных средств).

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

Сети Петри (основные понятия).

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

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

Рисунок 4.1 – Изображение компонент сети Петри: позиций, переходов, дуг

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

Основные понятия.

Виды позиций:

- входная позиция некоторого конкретного перехода – позиция, из которой исходят дуги, входящие в данный переход.

- выходная позиция некоторого конкретного перехода – позиция, в которую входят дуги, исходящие из данного перехода.

Фишка (маркер). Фишки изображаются точками, расположенными внутри позиций. Каждой позиции сети ставится в соответствие натуральное число, указывающее количество фишек в данной позиция. Это число называют разметкой позиции, а совокупность таких чисел для всех позиций сети называют разметкой сети. Структура сети Петри приведена на рис. 4.2.

Рисунок 4.2 – Структура сети Петри

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

Рисунок 4.3 – Процесс срабатывания перехода

Определения.

- Позиция может и не содержать фишек, т.е. иметь нулевую разметку.

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

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

- Завершение процесса функционирования приводит сеть к разметке, называемой конечной.

Виды сетей Петри:

- Временные сети Петри – каждый переход описывается своей задержкой во времени. Моделируются динамические характеристики системы.

- Цветные сети – используются несколько видов маркеров. Каждый из видов имеет свой цвет.

- Стохастические сети – предполагают наличие случайных факторов в сети (случайная задержка позиции, направление перехода)

- Сети Петри с ингибиторными дугами.

Преимущества использования сетей Петри в моделировании и анализе:

- большие выразительные способности в представлении параллельных асинхронных систем;

- способность представления локального управления, параллельных, конфликтных, недетерминированных и асинхронных событий;

- графическое и аналитическое представление сети;

- понятность модели и легкость ее изучения;

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

- возможность описания системы на различных уровнях абстракции;

- возможность представления системной иерархии;

- возможность машинной поддержки в проектировании.

Свойства сетей Петри:

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

- Сохранение.

- Активность.

- Достижимость и покрываемость.

- Эквивалентность и включение.

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

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

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

Если известны емкости всех позиций, и наибольшая из них kmax, то сеть называют kmax-ограниченной.

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

Рисунок 4.4 – Пример ограниченной (слева) и неограниченной (справа) сетей Петри.

Сохранение.

Сеть Петри называют сохраняющей, если число циркулирующих в ней объектов постоянно (см. рис. 4.5).

Активность.

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

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

- Активность уровня 1, если существует состояние (достижимое из начального), в котором он активирован.

- Активность уровня 2, если для всякого целого n существует последовательность срабатывания переходов, в которой данный переход присутствует по крайней мере n раз.

- Активность уровня 3, если существует бесконечная последовательность срабатывания переходов, в которой данный переход присутствует неограниченно часто.

- Активность уровня 4, если для любого достижимого состояния существует последовательность срабатываний, приводящая в такое состояние, в котором этот переход активирован (активный переход).

Рисунок 4.6 – Пример сети, всегда приходящей к тупиковой разметке

Рисунок 4.7 – Пример сети, которая никогда не "попадает в тупик"

Рисунок 4.8 – Пример сети, которая может остановиться, а может и нет

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

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

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

Сеть СП1, включается в сеть СП2, если поведение СП1 является подмножеством поведения СП2.