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

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

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

Рис. 7.7. Пример вычислительной схемы: а – граф потока данных;

б – граф управления

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

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

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

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

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

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

Рис. 7.8. Пример недетерминированной вычислительной схемы

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