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

    На этом шаге мы рассмотрим представление блок-схемы сетями Петри.

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

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

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

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

    Программа:

begin
  Writeln('Введите y1');
   Readln(y1);
   Writeln('Введите y2');
   Readln(y2);
    y3:=1;
    while y1>0 do
       begin
           if odd (y1) then
               begin
                    y3:=y3*y2;
                    y1:=y1-1;
                end;
                y2:=y2*y2;
                y1:=y1/2;
        end;
      Writeln('y=',y3);
  end.

    Блок-схема:


Рис.1. Блок-схема программы, приведенной выше

Таблица 1. Интерпретация действий блок-схемы, изображенной на рисунке 1
Действие Интерпретация
a Readln(y1); Readln(y2); y3:=1;
b y1>0 ?
c Odd (y1) ?
d y3:=y3*y2; y1:=y1-1;
e y2:=y2*y2; y1:=y1 /2;
f Writeln(y3);

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


Рис.2. Перевод узлов вычисления и принятия решения в блок-схеме в переходы в сети Петри

    На рисунке 3 показан перевод блок-схемы на рисунке 1 в эквивалентную сеть Петри.


Рис.3. Представление сетью Петри программы на рисунке 1

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

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

    На следующем шаге мы рассмотрим параллельные вычисления и синхронизацию.




Предыдущий шаг Содержание Следующий шаг