1 Напомним, что деревом в теории графов называют граф, не имеющий циклов.

Примеру тупиковой ситуации, возникающему при работе с ресурсами типа SR, который мы также уже рассматривали ранее (см. рис. 7.3), соответствует сеть Петри, показанная на рис. 7.6.

В этой сети номера переходов соответствуют отмеченным номерам операторов, которые выполняют процессы ПР1 и ПР2, а позиции/?j пр_г — семафорам S_t и S₂, над которыми выполняются Р- и V-операции. Сеть на рис. 7.6 также не является живой, хотя для нее и существуют такие последовательности срабатывания пе­реходов, что тупиковой ситуации не наступит.

Алгоритм построения дерева достижимости изложен, например, в работе [64].

Вычислительные схемы

Вычислительная схема — это представление в графической форме асинхронной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистов» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления [89].

Граф потока данных (информационный граф) определяет входные и выходные данные для каждого оператора [18]. Дуга (Rj S_k) от регистра rj к оператору S_k означает, что данные R, являются элементом входных данных этого оператора; дуга (S_k rj) определяет данные rj как выходные. Очевидно, что некоторые дан­ные R могут являться выходными для оператора Sj и входными для оператора Sj. Пример графа потока данных для некоторой вычислительной схемы представ­лен на рис. 7.7, а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.

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

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

Такая последовательность операторов S^ S₂ S_n, ..., что каждый оператор Sj

определен (то есть его входные счетчики не равны нулю) при тех значениях счетчиков, которые получаются в результате выполнения предшествующих опе­раторов, называется последовательностью исполнения схемы. Поскольку с опе­раторами не связано никакого особого отсчета времени (подобно сетям Петри¹), то порядок, в котором операторы будут выполняться, не всегда может быть пред­сказан. Любая допустимая последовательность исполнения является возможной последовательностью событий. Как мы уже знаем, для системы взаимодействую­щих параллельных процессов результаты вычислений зависят от последователь­ности исполнения, если не обеспечить взаимное исключение для критических интервалов. В случае когда вычислительная схема вырабатывает одинаковые результаты для всех допустимых последовательностей исполнения, говорят, что она детерминирована. Схема на рис. 7.7 является детерминированной.

Рассмотрим вычислительную схему на рис. 7.8. Операторы Sj и S₂, как это видно из графа управления, выполняются параллельно и асинхронно. Очевидно, что значение регистра R₃ будет различным в зависимости от того, выполняется ли оператор Sj раньше или позже оператора S₂. Поскольку граф управления здесь допускает последовательности исполнения, которые приводят к различным ре­зультатам, то эта схема не детерминирована.

Говорят, что два оператора соперничают в регистре R, если один из них изменяет R, а другой либо изменяет R, либо обращается к нему. Если два оператора, которые

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

соперничают в некотором регистре, могут быть выполнены в одно и то же время, то говорят, что в схеме существует условие соперничества и такая схема являет­ся недетерминированной. Одна из возможных форм недетерминированного ис­полнения заключается в том, что схема может «зависнуть» (попасть в тупиковую ситуацию).

К сожалению, вычислительные схемы, как и сети Петри, не являются конструк­тивной моделью (с точки зрения борьбы с тупиковыми ситуациями, возникаю­щими в операционных системах), несмотря на свою интуитивную привлекатель­ность и возможность сделать вывод о возможности существования тупиков в той или иной системе [89]. Мы знаем, что возможность существования тупиковой ситуации в большинстве ОС существует. Но ведь это же не означает, что эти ОС нельзя использовать. Важнее уметь обнаружить существование тупиковой си­туации в конкретный момент времени и поправить ситуацию (насколько это возможно). Поэтому гораздо более продуктивной с этой точки зрения является модель Холта.