3.4.1.       Блок-схемы

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

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

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

Стандартный способ представления структуры управления программ — это блок-схемы. Блок-схема представляет поток управления в программе. Например, программа на рис. 3.21 представляется блок-схемой на рис. 3.22. Заметим, что блок-схема на рис. 3.22 не указывает конкретные вычисления, которые надо произвести, а только определяет структуру программы. Такая блок-схема является абстрактной. Рис. 3.23 показывает, как можно проинтерпретировать блок-схему (рис. 3.22) программы, представленной на рис. 3.21. Каждая последовательная программа может быть представлена в виде блок-схемы. Таким образом, показывая, как

блок-схема может быть представлена сетью Петри, мы дадим представление сетью Петри программы.

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

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

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

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

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