Взаимоблокировка, условия Коффмана, критерий возникновения взаимоблокировки на графе Холта

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

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

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

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

Ресурсы можно разбить на два класса:

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

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

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

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

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

Необходимые условия возникновения взаимоблокировки — условия Коффмана (Coffman):

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

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

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

Отслеживать возникновение взаимоблокировок удобно на диаграммах Холта (Holt). Диаграмма Холта представляет собой направленный граф[1], имеющий два типа узлов: процессы (показываются кружочками) и ресурсы (показываются квадратиками). Тот факт, что ресурс получен процессом и в данный момент занят этим процессом, указывается ребром (стрелкой) от ресурса к процессу. Ребро, направленное от процесса, к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к соответствующему ресурсу.

Рисунок 2. Диаграмма Холта для примера 3.5 взаимоблокировки

Критерий взаимоблокировки. Взаимоблокировка имеет место быть, тогда и только тогда, когда диаграмма Холта, отражающая состояния процессов и ресурсов, содержит цикл[2].