22. Тупики и методы борьбы с ними

Выполняющийся процесс оказывается в тупике, если он ожидает наступления события, которое никогда не произойдёт.

Причины возникновения тупиков многообразны. Решения про­блемы тупиков в общем случае не существует.

Классическим (но далеко не единственным) примером тупика яв­ляется следующий. Предположим, что процессам А и Б, работающим в системе, для выполнения своей работы необходимы ресурсы Р1 и Р2, причём каждый из этих ресурсов не может разделяться между процессами и, кроме того, является оперативно неперераспределя-емым.

Пусть процесс А запросил и получил в своё распоряжение ресурс Р1. После этого закончился его квант времени, и управление получил процесс Б.

Процесс Б запросил и получил в своё распоряжение ресурс Р2. После этого процесс Б запрашивает ресурс Р1, но не может его по­лучить, так как ресурс уже занят процессом А, и должен ожидать освобождения ресурса Р1.

Получив управление, процесс А запрашивает ресурс Р2, но не может его получить, так как ресурс уже занят процессом Б.

Оба процесса будут ожидать освобождения необходимых им ре­сурсов, но это событие никогда не наступит.

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

1. Условие взаимоисключения. Одновременно использовать ре­сурс может только один процесс.

2. Условие ожидания ресурсов. Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости. Ресурс, выделенный ранее, не может быть принудительно отобран у процесса. Он может быть освобождён только процессом, который его удерживает.

4. Условие кругового ожидания. Существует кольцевая цепь процессов, в которой каждый процесс ждёт доступа к ресурсу, удер­живаемому другим процессом цепи.

Тупик возникает в системе только при одновременном выполне­нии всех четырёх условий.

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

Рассматриваются следующие методы:

• игнорирование проблемы в целом;

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

• обход тупиков;

• обнаружение тупиков;

• восстановление после тупиков.

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

Однако не во всех системах эту проблему можно игнорировать. Например, возникновение тупиков недопустимо в системах реального времени.

23. Методы предотвращения тупиков

Предотвращение тупиков предполагает исключение самой воз­можности возникновения тупиков в системе. Предотвращение ту­пиков возможно только за счёт нарушения условий возникновения тупиков.

Нарушение условия взаимоисключения

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

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

Нарушение условия оэюидания дополнительных ресурсов

В этом случае система требует, чтобы каждый процесс запраши­вал все требуемые ему ресурсы сразу, перед началом выполнения.

Если какой-либо ресурс не может быть предоставлен, процесс просто не может начать выполняться, и должен ждать освобожде­ния всех необходимых ему ресурсов, не удерживая при этом за собой никаких ресурсов.

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

Кроме того, применение этого метода ведёт к непроизводитель­ному расходованию ресурсов, так как не все ресурсы, выделенные процессу в начале работы, будут нужны ему в течение всего времени работы.

Нарушение принципа отсутствия перераспределения

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

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

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

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

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

Нарушение условия кругового оэюидания

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

На практике эта схема трудно реализуема и ведёт к неэффек­тивности использования ресурсов и существенному услоленению про­граммирования.

Реально такая схема может быть применена лишь к ограничен­ному классу ресурсов.