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

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

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

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

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

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

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

Ресурсы бывают двух типов: выгружаемые и невыгружаемые. Выгружаемыйресурсможно беспрепятственно забирать у владеющего им процесса. Таким ресурсом является память. Рассмотрим систему с пользовательской памятью 32 Мбайт, одним принтером и двумя процессами по 32 Мбайт, каждому из которых нужна печать. Процесс Aзапрашивает и получает принтер, готовит данные для печати. Еще не закончив подготовку, он превышает выделенное ему время и выгружается на диск в область подкачки. Начинает работать процесс Bи пытается обратиться к принтеру. Но принтер занят процессом A. Возникает потенциальная тупиковая ситуация, потому что процесс A использует принтер, а процесс Взанимает память, и ни один из них не может продолжать работу без ресурса, удерживаемого другим. Однако можно забрать память у процесса В, переместив его на диск в область подкачки, и скачать с диска в память процесс А. Теперь процесс Аможет закончить подготовку, выполнить печать и освободить принтер. Взаимоблокировки не происходит.

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

Последовательность событий, необходимых для использования ресурса, имеет следующий вид:

Запрос ресурса.

Использование ресурса.

Возврат ресурса.

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

Установлено, что для возникновения взаимоблокировки должны выполняться 4 условия:

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

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

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

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

Для того, чтобы произошла взаимоблокировка, должны выполниться все эти 4 условия. Если хоть одно из них отсутствует, взаимоблокировка невозможна. Каждое из приведенных условий относится к стратегии определения, что в ОС разрешается, а что – нет. Может ли ресурс быть отдан одновременно больше, чем одному процессу? Может ли процесс удерживать один ресурс и запрашивать второй? Можно ли отнять ресурс у процесса? Может ли существовать циклическое ожидание? Исходя из этого, можно разрушать взаимоблокировки с помощью принудительного невыполнения некоторых из этих условий.

Для исключения взаимоблокировок используются четыре стратегии.

Пренебрежение проблемой в целом. При использовании этой стратегии могут произойти неприятности.

Обнаружение и восстановление. При возникновении взаимоблокировки предпринимают какие-либо действия.

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

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