Тупиковые ситуации. Предотвращение тупиков. Обход тупиков. Обнаружение тупиков. Восстановление после тупиков

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

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

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

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

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

Для тупика необходимо выполнение всех четырех условий.

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

Итак, основные направления борьбы с тупиками: 1)Предотвращение тупиков. 2) Обход тупиков. 3) Обнаружение тупиков. 4) Восстановление после тупиков

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

Hарушение условия ожидания дополнительных ресурсов. Хавендер в 1968 г. предложил следующую стратегию: 1)Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены. 2) Если же процесс, удерживает определенные ресурсы и получает отказ в выделении ему дополнительных ресурсов, то он должен освободить свои первоначальные ресурсы и, при необходимости, запросить их снова вместе с дополнительными.

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

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

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

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

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

Алгоритм банкира. Можно избежать тупиковой ситуации, если рациональным образом использовать ресурсы, придерживаясь определенных правил. Наиболее известен среди алгоритмов такого рода - алгоритм банкира, предложенный Дейкстрой. Он, как бы имитирует действия банкира, который, располагая определенным источником капитала, принимает ссуды и выдает платежи. Предположим, что у системы в наличии n устройств, например лент. Суть алгоритма состоит в следующем: 1) ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n. 2) Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени. 3) Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени. 4) В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

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

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

Сложность восстановления обусловлена рядом факторов: 1)в большинстве систем нет достаточно эффективных средств для приостановки процесса, вывода его из системы и возобновления впоследствии; 2) если даже такие средства есть, то их использование требует затрат и внимания оператора; 3) восстановление после серьезного тупика может потребовать много работы.

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

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

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

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