Сети Петри. Анализ дискретных систем с помощью сетей Петри, страница 4

3. «Семафоры» Дейкстры. На использовании данного механизма базируются некоторые конструкции современных операционных систем. Семафор содержит некоторое целое число фишек S, под которыми понимаются ресурсы операционной системы. Основу работы данного механизма синхронизации составляет процедура использования двух операций P, V для анализа и изменения содержимого семафора. Операция Р уменьшает содержимое семафора на единицу, если его значение больше нуля. В противном случае данная операция не выполняется. Таким образом, эта операция означает занятие одной единицы ресурса, например занятие одного центрального процессора в вычислительном комплексе, занятие памяти в общем поле памяти и др. Операция V увеличивает содержимое семафора на единицу. Это соответствует освобождению ресурса. Следовательно, согласованное использование этих двух операций будет описывать процедуру обработки с использованием для этого ресурсов вычислительной системы.

Рис. 1.11. Граф сети Петри, моделирующий использование памяти

ограниченного размера

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

            Рис. 1.12. Пример графа сети Петри, использующего семафор

1.4. Примеры построения сетей Петри

Так как сеть Петри создавалась для моделирования вычислительных процессов, то наиболее просто с ее помощью описывается аппаратное и программное обеспечение ЭВМ. При описании алгоритмов каждый блок алгоритма изображается переходом.  Представление основных управляющих конструкций алгоритма фрагментами сети Петри показано на рис. 1.13. Используя данные типовые структуры, представим в виде сети Петри алгоритм, блок-схема которого приведена на рис. 1.14.

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

readln (x,y);

z:= x+y;

k:= 2;

if z > = 10

then writeln («z больше 10»)

else writeln («z меньше 10»);

z:= y/k;

Представление этого фрагмента сетью Петри показано на рис. 1.15. Такая сеть показывает последовательно-параллельный процесс, в отличие от записи строками программы. Представление программы сетью Петри позволяет исключить некоторые ограничения в структуре, вызванные последовательной записью текста программы строка за строкой. Так, например оператор присваивания k: = 2 в приведенном выше фрагменте программы на языке Паскаль может выполняться раньше, чем операторы, написанные ранее него. Это можно учесть в сети.

Последовательность:

Выбор:

Цикл:

Рис. 1.13. Представление основных управляющих конструкций алгоритма фрагментами сетей Петри

Из сети видно, что оператор k: = 2 может выполняться в любое время до оператора z: = y/k. В этой структуре снято ограничение на время выполнения k: = 2. Процесс из последовательного преобразовался в последовательно-параллельный.

Рис. 1.14. Представление блок-схемы алгоритма сетью Петри: а) блок-схема;

б) сеть Петри

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