На этом шаге мы рассмотрим представление блок-схемы сетями Петри.
Вырожденным случаем параллельной системы обработки является система с одним процессом. Рассмотрим, как сетью Петри может быть представлен отдельный процесс.
Отдельный процесс описывается программой. Эта программа может быть написана на многих языках. Программа представляет два различных аспекта процесса: вычисление и управление. Вычисление связано с текущими арифметическими и логическими операциями, вводом и выводом, обычными манипуляциями над участками памяти и их содержимым. Управление связано с порядком выполнения выполняемых вычислений.
Сети Петри удачно представляют структуру управления программ. Сети Петри предназначены для моделирования упорядочения инструкций и потока информации, но не для действительного вычисления самих значений. Модель системы является абстракцией моделируемой системы. Поэтому она игнорирует все возможные специфические детали.
Стандартный способ представления структуры управления программ - это блок-схемы. Блок-схема представляет поток управления в программе. Например, программа представляется блок-схемой на рисунке 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. Блок-схема программы, приведенной выше
| Действие | Интерпретация |
|---|---|
| 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
Рассмотрим интерпретацию фишек блок-схемы счетчиком команд. Фишка, находящаяся в позиции, означает, что счетчик команд установлен на готовность выполнения следующей инструкции. Каждая позиция имеет единственный выходной переход, за исключением позиции, которая предшествует принятию решения; такие позиции имеют по два выходных перехода, соответствующих истинному и ложному значению предиката.
Переходы связываются с действиями программы: вычислениями и принятиями решений. Для интерпретации сети Петри необходимо интерпретировать каждый переход. Переходы для вычислений имеют один вход и один выход.
На следующем шаге мы рассмотрим параллельные вычисления и синхронизацию.
