Взаимоблокировка

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

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

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

- выгружаемые ресурсы – ресурсы, которые могут забираться у владеющего им процесса, например, память;

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

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

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

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

Для некоторых видов ресурсов, таких как записи в базе данных, управление использованием ресурсов зависит от пользовательских процессов. Один из способов управления заключается в присоединении семафора или мьютекса к каждому из ресурсов. Все семафоры в исходном состоянии равны 1. Действия выполняются в следующем порядке: производится запрос ресурса с помощью вызова down, примененного к семафору, далее процесс использует ресурс, после чего выполняется вызов up для его освобождения. Иногда процессы нуждаются в двух и более ресурсах, их можно получать последовательно.

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

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

В. Коффман (Coffman) и другие исследователи доказали, что для возникновения ситуации взаимоблокировки должны выполняться четыре условия:

- условие взаимного исключения – каждый ресурс в данный момент доступен или отдан одному процессу;

- условие удержания и ожидания – процессы, удерживающие полученные ресурсы, могут запрашивать новые ресурсы;

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

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

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

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

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

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

- восстановление после тупиков;

- игнорирование проблемы тупиков.

1.Игнорирование проблемы в целом. Любая операционная система, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Таблица открытых файлов, таблица процессов, фактически каждая таблица являются ограниченными ресурсами. Заполнение всех записей таблицы процессов может привести к тому, что очередной запрос на создание процесса может быть отклонен. При неблагоприятном стечении обстоятельств несколько процессов могут выдать такой запрос одновременно и оказаться в тупике. Подход большинства популярных операционных систем (Unix, Windows и др.) состоит в том, чтобы игнорировать данную проблему в предположении, что маловероятный случайный тупик предпочтительнее, чем правила, заставляющие пользователей ограничивать число процессов, открытых файлов и т.п.

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

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

- предположим, что у системы в наличии n устройств;

- операционная система принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n;

- пользователь гарантирует, что если операционная система в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени;

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

- в соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

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

- число пользователей и число ресурсов фиксировано;

- число работающих пользователей должно оставаться постоянным;

- клиенты должны гарантированно возвращать ресурсы;

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

Способ 2. Предотвращение тупиков за счет нарушения условий возникновения тупиков:

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

Нарушение условия ожидания дополнительных ресурсов. Условия ожидания ресурсов можно избежать, потребовав выполнения стратегии двухфазного захвата:

- в первой фазе процесс сразу должен запрашивать все необходимые ему ресурсы и до тех пор, пока они не предоставлены, процесс не может продолжать выполнение;

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

Модель применяется в пакетных мэйнфреймах (mainframe), которые требуют от пользователей перечислить все необходимые его программе ресурсы; в СУБД, где имеется механизм двухфазной локализации записей. Данный подход приводит к неэффективному использованию компьютера, так как перечень будущих запросов к ресурсам редко удается спрогнозировать, кроме того, он противоречит парадигме модульности в программировании, поскольку приложение должно знать о предполагаемых запросах к ресурсам во всех модулях.

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

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

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

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

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

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

- процесс А1 ожидает ресурс R1;

- процесс А2 удерживает ресурс R2 и ожидает ресурс R1;

- процесс А3 удерживает ресурс R1 и ожидает ресурс R3;

- процесс А4 ожидает ресурс R2;

- процесс А5 удерживает ресурс R3 и ожидает ресурс R2.

Вопрос заключается в том, является ли ситуация тупиковой. Если ситуация тупиковая, то какие процессы в ней участвуют. Из рисунка 3.10. видно, что имеется цикл, моделирующий условие кругового ожидания и что процессы А2, А3, А5 находятся в тупиковой ситуации. Существует достаточно большое количество алгоритмов, обнаруживающие циклы в направленных графах.

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

- в большинстве систем нет достаточно эффективных средств, чтобы приостановить процесс, вывести его из системы и возобновить впоследствии с того места, где он был остановлен;

- если такие средства имеются, то их использование требует затрат и внимания оператора;

- восстановление после тупика может потребовать значительных усилий.

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

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

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

Дата добавления: 2014-01-07