3.3.4. Обнаружение и устранение взаимоблокировок

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

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

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

3.3.5. Предотвращение взаимоблокировок

Как мы видели, уклонение от взаимоблокировок, в сущности, невозможно, так как оно требует наличия никому не известной информации о будущих процессах. Тогда возникает справедливый вопрос: как же реальные системы избегают попадания в тупики? Для того чтобы ответить на этот вопрос, вернемся назад к четырем условиям, сформулированным в [11] (см. раздел Условия взаимоблокировки данной главы), и посмотрим, дадут ли они нам ключ к разрешению проблемы. Если мы сумеем гарантировать, что хотя бы одно из этих условий никогда не будет выполнено, тогда взаимоблокировки станут конструктивно невозможными [41].

Сначала попробуем атаковать условие взаимного исключения. Если в системе нет ресурсов, отданных в единоличное пользование одному процессу, мы никогда не попадем в тупик. Но в равной степени понятно, что если позволить двум процессам одновременно печатать данные на принтере, воцарится хаос. Используя подкачку выходных данных для печати, несколько процессов могут одновременно генерировать свои выходные данные. В такой модели только один процесс, который фактически запрашивает физический принтер, является демоном принтера. Так как демон не запрашивает никакие другие ресурсы, для принтера тупики исключаются.

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

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

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

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

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

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

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

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

Другой способ уклонения от циклического ожидания заключается в поддержке общей нумерации всех ресурсов, как показано на рис. 3.7, а. Тогда действует

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

1. Фотонаборное устройство

2. Сканер

3. Плоттер

4. Накопитель на магнитной ленте

5. Устройство для чтения компакт-дисков

Рис. 3.7. а - пронумерованные ресурсы; б - граф ресурсов

При выполнении такого соглашения граф распределения ресурсов никогда не будет иметь циклов. Покажем, что это так, в случае двух процессов (рис. 3.7, б). Мы попадаем в тупик, только если процесс А запросит ресурс j, а процесс В обратится к ресурсу i. Предположим, что ресурсы i и j различны, значит, они имеют разные номера. Если i > j, тогда процессу А не позволяется запрашивать ресурс j, потому что его номер меньше, чем номер уже имеющегося у него ресурса. Если же i < j, процесс В не может запрашивать ресурс i, так как этот номер меньше номера уже занятого им ресурса. Так или иначе, взаимоблокировка исключена.

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

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

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

В табл. 3.3 подведены итоги различных методов для предотвращения тупиков.