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

Сеть Петри не обеспечивает полной общности с вычислительной точки зре­ния. Например, сетью Петри нельзя смоделировать оператор отрицания ("не"). Существует еще одна структура под названием "вычислительная схе­ма", которая эту проблему решает.

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

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

Рис. 3. (a) фрагменты программ А и В, разделяющих принтер и диск;
(б) взаимная блокировка (клинч); (в) очередь к разделяемому диску;
(г) независимое использование ресурсов

В рассмотренных примерах тупик был образован двумя процессами, но взаимно блокировать друг друга могут и большее число процессов.

Необходимые условия возникновения тупиковых ситуаций.

1. Процессы требуют предоставления им права монопольного управления ресурсами, которые им предоставляются (условие взаимоисключения).

2. Процессы удерживают за собой ресурсы, выделенные им, в то же время ожидают выделения дополнительных ресурсов (условие ожидания ресурсов).

3. Ресурсы нельзя отобрать у процесса, удерживающего их, пока эти ресурсы не будут использованы для завершения работы (условия неперераспределенности).

Проблема тупиков включает в себя следующие задачи:

· предотвращение тупиков,

· распознавание тупиков,

· восстановление системы после тупиков.

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. Так, если бы в предыдущем примере процесс А и процесс В запрашивали ресурсы в одинаковой последовательности, то тупик был бы в принципе невозможен. Второй подход к предотвращению тупиков называется динамическим и заключается в использовании определенных правил при назначении ресурсов процессам, например, ресурсы могут выделяться в определенной последовательности, общей для всех процессов. В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.

Для того чтобы обеспечить написание корректных программ, было предложено высокоуровневое средство синхронизации - «монитор» - это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют свойства, позволяющие достичь взаимоисключения процессов, а именно: только один процесс может быть активным по отношению к монитору, это достигается не за счет программирования, а на уровне компилятора. Компилятор обрабатывает вызовы процедур монитора таким образом, что первые несколько инструкций этой процедуры проверяют – не активен ли какой-либо процесс по отношению к монитору. Если «ДА», то вызывающий процесс приостанавливается, пока другой не освободит монитор. Но когда процессы имеют собственную ОП, используется механизм семафорных операций. В таких системах синхронизация реализована с помощью обмена сообщениями.

Методы борьбы с тупиками

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

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

· предотвращение тупика;

· обход тупика;

· распознавание тупика с последующим восстановлением.