Министерство образования и науки Украины

Одесса 2016

Методические указания к практическим занятиям по дисциплине “Параллельное программирование“/ Сост. О. Н. Паулин. – Одесса: ОНПУ, 2016. – 10 с.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  

Для студентов специальности 7. 080403.

Составитель: О. Н. Паулин, доктор техн. наук, доц.

ВВЕДЕНИЕ

Одним из наиболее общих понятий кибернетики и информатики     является понятие дискретной динамической системы. Примеры таких систем: ЭВМ, их устройства, программы и операционные системы, системы обработки данных, производственные системы дискретного характера (сборочные линии и цеха), социально-экономические структуры и т. п. Особую роль в теории дискретных систем сыграло понятие автомата. Автомат является математической абстракцией системы переработки дискретной информации или процесса её переработки. Конечный автомат имеет конечное число состояний. Понятие конечного автомата существенно связано с понятием алгоритма и последовательной алгоритмической системы. Для последней характерен последовательный способ функционирования: система (автомат) последовательно переходит из состояния в состояние в соответствии с определённой функцией перехода и осуществляет очередной (последовательный) шаг алгоритма.

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

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

     В теории сетей Петри сложилось три основных направления исследования:

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

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

     - приложения сетей к конкретным задачам анализа и синтеза дискретных систем.

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

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

1. Свойства и особенности сетей Петри

Сети Петри [1] находят применение как инструмент анализа и синтеза вычислительных схем и устройств; при помощи сетей Петри описывается поведение параллельной асинхронной системы.

   Сеть Петри - двудольный ориентированный граф, множество вершин которого состоит из позиций p_i Î P и переходов t_j Î T. Дуги соединяют позиции с переходами или переходы с позициями. Позиции обозначаются кружками, переходы - черточками, дуги - стрелками (рис. 1).

    В содержательном плане переходам соответствуют события (операторы), а позициям - условия. Дуги между позициями и переходами выражают связи двух типов:

			1) позиция pi - входная для данного перехода tj. Для появления события, соответствующего переходу tj, необходимо выполнение условия, соответствующего позиции pi; 2) позиция pi - выходная для данного перехода tj. При появлении события, соответствующего переходу tj, формируется условие, соответствующее позиции pi.

Рис. 1.

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

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

     Разметка сети Петри - это функция, которая ставит в соответствие позициям неотрицательные целые числа, равные числу точек в позициях. Если N - сеть Петри, P - множество позиций в N, а n(P) - число позиций в P, то каждая позиция имеет номер из набора {1, 2,..., n(P)}. Разметка M представляется в виде вектора, состоящего из n(P) элементов, в которой i-й элемент означает число точек в i-й позиции.

Пример 1. Для сети Петри, представленной на рис. 1, P={р₁, р₂, р₃}; n(P)=3 и начальная разметка М(0)=[2, 0, 0]. Переходы a и b являются запускаемыми, а c и d - незапускаемыми. В результате запуска перехода a получается новая разметка: a: М(1)=[1, 1, 0]. Теперь уже запускаемыми являются переходы a, b и c. Запустив c и затем b, мы получbм новые разметки: c: М(2)=[1, 0, 0]; b: М(3)=[0, 0, 1].  Легко убедиться, что далее не может запуститься ни один переход, - сеть зависла. Особенностью рассмотренной сети является неизбежное исчерпание точек в позиции р₂.

В сетях Петри единственное ограничение на совместное выполнение переходов налагается на число меток в позиции. То, что переходы являются запускаемыми, не означает, что они могут быть запущены совместно. Например, при разметке на рис. 1 М=[1, 0, 0] оба перехода a и b являются запускаемыми, но не могут быть запущены одновременно.

Пример 2. На рис. 2 представлена сеть Петри с другой конфигурацией. Особенностью этой сети является наличие петли обратной связи для позиции р₁, что позволяет накапливать точки в позиции р₂ при многократном срабатывании перехода a. Однако и эта сеть зависает после срабатывания переходов b и c.

              a                    P₂              c

                                                              b

              P₁                                                 d                      P₃

Рис. 2. Пример сети Петри

Последовательность исполнения N - это последовательность разметок M(0), M(1),... M(i), в которой M(i) получается из М(i-1) в результате запуска некоторого перехода. Для данной сети Петри с начальной разметкой существует много возможных последовательностей исполнения.

Сценарием функционирования сети Петри будем называть последовательность срабатываний переходов; собственно срабатывание определяется внешней относительно сети средой.

     Живучей называется такая разметка, при которой каждый из переходов может быть запущен бесконечное число раз. Если достигнута такая разметка, что ни один из переходов не может быть запущен, то говорят, что сеть Петри " зависла" (попала в тупик). На рис. 1 при начальной разметке М(0)=[2, 0, 0], если выполнен сценарий a, c, a, то достигается разметка M(1)=[0, 1, 0] - сеть Петри мертва. Следовательно, разметка M(0) не является живучей.

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

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

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

Для описания сети Петри используется следующая информация: а) матрица F (p®t); б) матрица H (t®p); в) начальная разметка М(0)=[... ]. В матрицах единицей отмечается наличие связей “позиция-переход” для матрицы F и “переход-позиция” – для матрицы H.

Сеть Петри, представленная на рис. 2, может быть описана следующим образом (рис. 3).

Рис. 3

На рис. 4 представлены особые случаи параллелизма.

a) параллелизм конвейерного типа.

б) недетерминизм параллельных,                г) конфликтные

независимых событий                                взаимодействия.

(асинхронность - в определении

сетей не существует время).

Рис. 4.

Задания для самостоятельной работы

Для двух таблиц H_i и F_i, выбранных в соответствии с номером варианта (N_вар=N_сп. _гр. mod12) выполнить следующее:

- построить сеть Петри (без пересечения линий!!! );

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

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

Литература

1. В. Е. Котов. Сети Петри. – М.: Наука, 1984. – 160с.