Представление блок-схемы сетями Петри

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

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

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

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

{

cin>>y₁; cin>>y₂;

y₃ = 1;

while (y₁ > 0 )

{
if (y₁ % 2 = =0)

{

y₃ = y₃ * y₂ ;

y₁ = y₁ – 1;

}

y₂ = y₂ * y₂;

y₁ = y₁ – 2;

}

cout<< y₃;

}

Рис. 2.8. Простая программа

Рис. 2.9. Блок-схема программы

Действие Интерпретация

a cin>>y₁; cin>>y₂ ; y₃ = 1;

b y₁ > 0 ?

c y₁ % 2 = =0 ?

d y₃ = y₃ * y₂ ; y₁ = y₁ – 1;

e y₂ = y₂ * y₂ ; y₁ = y₁ – 2;

f cout<< y₃ ;

Рис. 2.10. Интерпретация действий блок-схемы на рис. 3.2

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

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

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

Рис. 2.11. Перевод узлов блок-схемы в переходы сети Петри. Рис. 2.11.Сеть Петри

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

Указание: для построения сети Петри по блок-схеме необходимо выполнить следующие действия:

а) по условию задачи написать программу ;

б) по (а) построить абстрактную блок-схему;

в) по (а) и (б) написать интерпретацию каждого блока;

г) по (б) нарисовать граф сети Петри

Упражнения

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

2. Построить блок-схему и сеть Петри для вычисления факториала N!

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

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

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

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

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

8. Построить блок-схему и сеть Петри для задачи вычисления суммы минимальных элементов столбцов двумерного массива.