14.4. Распределенная взаимоблокировка

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

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

Взаимоблокировка, связанная с распределением ресурсов

В главе 6, "Взаимоблокировка и голодание", сказано, что взаимоблоки­ровка в распределении ресурсов возникает только при соблюдении всех пере­численных условий.

- Взаимоисключение. Одновременно использовать ресурс может только один процесс.

- Удержание и ожидание. Процесс может удерживать выделенные ресурсы во время ожидания других ресурсов.

- Отсутствие перераспределения. Ресурс не может быть принудительно отобран у удерживающего его процесса.

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

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

Одной из сложностей, возникающих при управлении распределенными взаимоблокировками, является явление фиктивной взаимоблокировки (phantom deadlock). Пример такой взаимоблокировки проиллюстрирован на рис. 14.11. Запись P₁->P₂->P₃ означает, что процесс P₁ приостановлен в ожидании ресурса, которым владеет процесс Р₂, а процесс P₂ приостановлен в ожидании ресурса, которым владеет процесс Р₃. Пусть вначале процесс Р₃ обладает ресурсом R_a, a процесс P₁ — ресурсом R_b. Предположим, что процесс Р₃ сначала генерирует со­общение, освобождающее ресурс R_a, а затем — сообщение с запросом ресурса R_b. Если процесс выявления циклов сначала получит первое сообщение, а затем вто­рое, возникнет цепочка, изображенная на рис. 14.11,а. В противном случае будет зарегистрирована взаимоблокировка (рис. 14.11,б). На самом деле никакой взаимоблокировки не возникает; будет зарегистрирована ложная взаимоблоки­ровка, вызванная отсутствием информации о глобальном состоянии.

Предотвращение взаимоблокировок

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

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

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

При использовании обоих методов нужно, чтобы процесс заранее мог ука­зать свои требования к ресурсам. Это не всегда возможно; примером является приложение типа базы данных, в которую можно динамически добавлять новые элементы. В качестве варианта подхода, при котором предварительные сведения такого рода не нужны, рассмотрим два алгоритма, предложенные в [ROSE78].

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

В предложенных методах используются временные метки. В каждой тран­закции на протяжении ее времени жизни хранится временная метка, соответст­вующая времени ее создания. Таким образом, среди транзакций устанавливается строгий порядок. Если ресурс R, который используется транзакцией Т1, запра­шивается другой транзакцией Т2, конфликт разрешается с помощью сравнения их временных меток. Соблюдение этого условия позволяет предотвратить обра­зование циклического ожидания. Авторы предложили две разновидности этого базового метода и назвали их методом "ожидания-перезапуска" ("wait-die") и ме­тодом "прекращения-ожидания" ("wound-wait").

Предположим, что в текущий момент транзакция Т1 владеет ресурсом R, a транзакция Т2 генерирует запрос на этот ресурс. Алгоритм метода ожидания-перезапуска, который используется распределителем ресурсов, показан в лис­тинге 14,2,а. Временные метки двух транзакций обозначены как е (Т1) и е (Т2). Если транзакция Т2 старше, она блокируется до тех пор, пока транзакция Т1 не освободит ресурс R — либо сгенерировав запрос, либо в результате того, что она будет "убита" при запросе другого ресурса. Если транзакция Т2 моложе, то она перезапускается с той же временной меткой, что и раньше.

Листинг 14.2. Методы предотвращения взаимоблокировок

if (e(T2) < е(Т1))

halt_T2 ('wait');

else

kill_T2 ('die');

а) Метод ожидания-перезапуска

if (e(T2) < е(Т1))

kill_Tl ('wound');

else

halt_T2 ('wait');

б) Метод прекращения-ожидания

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

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

Избежание взаимоблокировок

Избежание взаимоблокировок — это метод динамического принятия реше­ния о том, может ли предоставление данного ресурса по запросу привести к взаимоблокировке. В [SING94b] отмечено, что избежание распределенных взаи­моблокировок является непрактичным по таким причинам.

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

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

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

Выявление взаимоблокировок

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

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

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

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

При распределенном управлении все процессы выявляют взаимоблокировку сообща. Вообще говоря, это означает необходимость интенсивного обмена инфор­мацией, включающей временные метки; в результате возникают значительные на­кладные расходы. В [RAYN88] можно найти несколько ссылок на алгоритмы рас­пределенного управления, а в [DATT90] приводится подробное изучение одного из таких подходов.

Таблица 14.1. Стратегии выявления распределенных взаимоблокировок

Централизованные алгоритмы		Иерархические алгоритмы		Распределенные алгоритмы
Достоинства	Недостатки	Достоинства	Недостатки	Достоинства	Недостатки
• Алгоритмы просты для понимания и реализации • Центральный узел обладает полной информацией и может оптимально раз­решать взаимоблокировки	• Значительные накладные рас- ходы на обмен информацией; каждый узел должен пересы­лать централь- ному узлу ин- формацию о своем состоянии • Центральный узел является уязвимым звеном	• Неуязвим по отношению к отказу одного узла • Достаточность малых действий при относительной локализации потенциальных взаимоблокировок	Трудность настройки системы так, чтобы большинство потенциальных взаимоблокировок были локализованы; в противном случае этот подход может приво­дить к большим накладным расходам	• Неуязвим по отношению к отказу одного из узлов • Ни один узел не перезагружен действиями по разрешению взаимо­блокировок	• Разрешение взаимоблокировок может оказаться сложным в силу того, что одна и та же взаимоблокировка может быть обнаружена не­сколькими узла­ми, которые могут не знать друг о друге • Из-за временных вопросов усложнена разработка алгоритмов

Приведем пример алгоритма, предназначенного для выявления распреде­ленных взаимоблокировок ([DATT92, JOHN91]). Этот алгоритм работает с рас­пределенной базой данных, в которой на каждом узле поддерживается некоторая часть базы данных; транзакции могут инициироваться каждым узлом. В каждой транзакции может быть не больше одного запроса ресурса. Если транзакция ну­ждается в нескольких объектах данных, второй объект данных можно запраши­вать только после того, как будет предоставлен первый объект данных.

С каждым объектом данных i на узле связаны два параметра: уникальный идентификатор D, и переменная Locked__by (D_i), Эта переменная имеет нулевое значение, если объект данных не заблокирован ни одной транзакцией. В против­ном случае ее значение равно идентификатору блокирующей транзакции.

С каждой транзакцией j на узле связано четыре параметра:

- уникальный идентификатор Т_j;

- переменная Held_by(Т_j), значение которой равно нулю, если транзакция Т_j находится в состоянии выполнения или готовности; в противном случае ее значение равно идентификатору транзакции, которая удерживает объект данных, требующийся транзакции Т_j;

- переменная Wait_for (Т_j), значение которой равно нулю, если транзакция Т_j не ожидает никаких других транзакций; в противном случае ее значение равно идентификатору транзакции, которая находится во главе упорядоченного списка блокированных транзакций;

- очередь Request_Q(Т_j), в которой содержатся все необработанные запросы объектов данных, удерживаемых транзакцией Т_j; каждый элемент очереди имеет вид (Т_k, D_k, где Т_k — запрашивающая транзакция, a D_k — объект данных, удерживаемый транзакцией Т_j.

Предположим, например, что транзакция Т₂ ожидает предоставления объ­екта данных, закрепленного за транзакцией Т₁ которая, в свою очередь, ожида­ет предоставления объекта данных, закрепленного за транзакцией Т₀. При этом параметры имеют такие значения:

Транзакция	Wait_for	Held_by	Request Q
Т0	0	0	T1
T1	Т0	Т0	Т2
Т2	Т0	Т1	0

Этот пример дает возможность понять разницу между параметрами Wait_for (Т_i) и Held_by (Т_i) . Ни один процесс не может продолжаться, пока Т₀ не освободит объект данных, нужный для T₁ который после этого сможет вы­полнить необходимые действия с этим объектом данных и освободить его для Т₂.

В листинге 14.3 приведен алгоритм, использующийся для выявления взаи­моблокировок. Когда транзакция делает запрос на блокировку объекта данных, связанный с этим объектом данных обслуживающий процесс либо удовлетворяет запрос, либо отказывает в его удовлетворении. Если требуемый ресурс не пре­доставляется, обслуживающий процесс возвращает идентификатор транзакции, удерживающей этот объект данных.

Листинг 14.3. Алгоритм выявления распределенных взаимоблокировок

/* Получение объектом данных d_j запроса lock_request (Т_i) */

if (Locked_by(Dj) == null)

send(granted);

else {

send (отказ транзакции) для Т_i;

send (Locked_by(Dj) ) для T_i

}

/* Транзакция Ti выполняет блокирующий запрос объекта данных Dj */

send (lock_request(Tj ) для D_j;

ожидание предоставления/отказа;

if (granted)

{

Locked_by(Dj) = Ti

Held_by(Ti) = 0;

}

else /* Считаем, что Dj используется транзакцией Tj */

{

Held_by(Ti) =Tj;

Enqueue (Ti, Request_Q{Tj));

if (Wait_for(T_j) == null)

Wait_for (T_i) = T_j;

else

Wait_for(Ti) = Wait_for(Tj) ;

update(Wait_for(Ti) , Request_Q(T_i) ;

}

/* Получение транзакцией Tj обновляющего сообщения */

if (Wait_for (Tj) != Wait_for (T_i))

Wait_for{Tj) = Wait__for(Ti);

if (intersect(Wait_for(Tj) , Request_Q(Tj) ) = null)

update(Wait_for(Ti) , Request_Q(Tj) ) ;

else

{

Объявление взаимоблокировки

/* начало разрешения взаимоблокировки */

/* выбирается Tj, которая должна быть прекращена */

/* Т_j освобождает все удерживаемые ею объекты данных */

send_clear (Т_j , Held_by (Tj) ) ;

каждый освобожденный объект данных D_i предоставляется транзакции T_k, находящейся во главе очереди Request_Q(Tj) ;

fог(каждой транзакции Т_n из очереди Request_Q(Tj) ,

запрашивающей объект данных, которых находится в Т_j)

{

Enqueue(T_n, Request_Q(T_k) ) ;

}

}

/* Получение транзакцией T_k сообщения clear(Tj, T_k) */

удаление транзакции Tj из очереди Request_Q (T_k) ;

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

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

На рис. 14.12 приведен пример работы описанного алгоритма. Когда тран­закция Т₀ запрашивает объект данных, содержащийся в транзакции Т₃, возни­кает цикл. Транзакция Т₀ отправляет обновляющее сообщение, которое переда­ется от T₁ к Т₂ и от Т₂ к Т₃. В этот момент транзакция Т₃ обнаруживает, что пе­ресечение ее переменных Wait_for и Request_Q отлично от нуля. Транзакция Т₃ отправляет транзакции Т₂ сообщение об освобождении своих объектов дан­ных, вследствие чего Т₃ удаляется из очереди Request_Q (Т₂), и освобождает свои объекты, активизируя транзакции Т₄ и Т_б.

Транзакция	Wait_for	Held by	Request Q
Т0	0	0	T1
T1	Т0	Т0	Т2
Т2	Т0	T1	Т3
Т3	Т0	Т2	Т4, Т6
Т4	Т0	Т3	Т5
Т5	Т0	Т4	0
Т6	Т0	Т3	0
а) Состояние системы до запроса
Транзакция	Wait_for	Held_by	Request Q
Т0	Т0	Та	T1
T1	Т0	Т0	Т2
Т2	Т0	T1	Т3
Т3	Т0	Т2	Т4, Т6, Т0
Т4	Т0	Т3	Т5
Т5	Т0	Т4	0
Т6	Т0	Т3	0

б) Состояние системы после того, как запрос транзакции Т₀ будет получен транзакцией Тз

Взаимоблокировки, возникающие при обмене сообщениями

Взаимное ожидание

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

Чтобы проанализировать эту ситуацию подробнее, определим понятие множества зависимости (dependence set — DS) процесса. Для процесса Р,, ко­торый не может выполняться из-за ожидания сообщения, множество DS(PJ состоит из всех процессов, от которых процесс Р_; ждет сообщения. Обычно процесс Р( сможет продолжить свою работу после получения любого из сооб­щений. Возможна также ситуация, когда процесс может продолжать работу только после получения всех ожидаемых сообщений. Однако наиболее рас­пространенной является первая ситуация, поэтому в данной книге рассмат­ривается именно она.

Опираясь на приведенное выше определение, можно сформулировать опре­деление взаимоблокировки множества процессов S. Взаимоблокировка возникает при таких условиях.

1. Все процессы множества S находятся в ожидании сообщений.

2. S содержит множества зависимости всех процессов, входящих в S.

3. В каналах нет ни одного сообщения, передаваемого от одного члена множе­ства S другому.

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

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

Это положение проиллюстрировано на рис. 14.13. На рис. 14.13,а процесс P₁ ожидает сообщения либо от процесса Р₂, либо от процесса Р₅; процесс Р₅ не ожидает никаких сообщений, поэтому он может отправить сообщение процессу P₁, тем самым выводя его из состояния ожидания. В результате звенья (P₁, Р₅) и (Р₁,Р₂) удаляются. На рис. 14.13,б добавлена еще одна зависимость: процесс Р₅ ожидает сообщения от процесса Р₂, который ждет сообщения от процесса Р₃, ожидающего сообщения от процесса Р₁ , который, в свою очередь, ждет сообще­ния от процесса Р₂. В результате возникает взаимоблокировка.

Проблему взаимоблокировки сообщений, как и проблему взаимоблокировки ресурсов, можно решить, предотвращая ее возникновение или выявляя образо­вание взаимоблокировки. Некоторые примеры можно найти в [RAYN88].

Недоступность буферов сообщений

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

Самым простым видом взаимоблокировки в сети передачи данных является непосредственная блокировка хранения и передачи сообщений (store-and-forward deadlock). Она может возникнуть в том случае, когда узел пакетной коммутации использует единый буферный пул, буфера которого по мере необходимости пре­доставляются пакетам. На рис. 14.14,а показана ситуация, в которой все буфер­ное пространство на узле А занято пакетами, предназначенными для узла В. То же справедливо и для узла В. Ни один из узлов не может принять ни одного пакета, поскольку их буфера заполнены. Таким образом, ни один из них не может передать или получить сообщение.

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

На рис. 14.14,б проиллюстрирована более сложная разновидность взаимо­блокировки — косвенная блокировка хранения и передачи сообщений. Она воз­никает, если образуется замкнутый цикл узлов, на каждом из которых очередь сообщений, передаваемых на соседний узел, до отказа заполнена пакетами, предназначенными для узла, находящегося за соседним. Одним из простых способов предотвращения взаимоблокировки подобного типа является использова­ние структурированного буферного пула (рис. 14.15). Такие буфера имеют ие­рархическую организацию. Использование пула памяти на нулевом уровне не ограничивается никакими правилами; там может храниться любой входящий пакет. Буфера, которые находятся на уровнях с первого по N-n (где N — это максимальное количество промежуточных узлов при передаче пакета по сети), резервируются следующим образом: буфера на уровне k зарезервированы для па­кетов, которые до этого подверглись не менее k транзитным пересылкам. Таким образом, при большой загрузке сети буфера заполнены от нулевого до N-го уров­ня. Если заполнены все уровни до k-гo включительно, то не принимается ни од­но входящее сообщение, прошедшее менее k транзитных пересылок. Можно по­казать (см. [GOPA85]), что при соблюдении такой стратегии удается избежать как прямых, так и косвенных взаимоблокировок.

С описанной выше проблемой взаимоблокировок можно столкнуться в контек­сте коммуникационной архитектуры, обычно на сетевом уровне модели OSI. Про­блема такого же рода может возникнуть и в распределенной операционной системе, в которой межпроцессное взаимодействие происходит с помощью обмена сообще­ниями. В частности, если операция отправки не является блокирующей, то для хра­нения исходящих сообщений нужен буфер. Буфер, который используется для хране­ния сообщений, отправленных процессом X процессу Y, можно рассматривать как канал обмена информацией между процессами X и Y. Если емкость этого канала ог­раничена (конечным размером буфера), то операция отправки сообщения может привести к приостановке процесса. Другими словами, если емкость буфера — п со­общений, и в процессе передачи (т.е. еще не получены адресатом) находятся п сооб­щений, то попытка отправить еще одно сообщение приведет к блокированию процес­са до тех пор, пока в буфере не освободится место.

На рис. 14.16 проиллюстрировано, как может возникнуть взаимоблокиров­ка при использовании конечного числа каналов. На рисунке показаны два кана­ла, каждый из которых обладает емкостью в четыре сообщения. Если в каждом из каналов (из X в Y и из Y в X) находится ровно по четыре сообщения и оба узла попытаются передать еще по одному сообщению, прежде чем получат хотя бы одно имеющееся, то оба они приостановят свою работу, в результате чего возникнет взаимоблокировка.

Если есть возможность ограничить сверху количество сообщений, переда­ваемых между каждой парой процессов системы, то очевидная стратегия предот­вращения взаимоблокировок состоит в том, чтобы предоставить каждому каналу необходимое количество слотов в буфере. Этот способ может оказаться чрезмерно расточительным и, конечно же, требует некоторых предварительных сведений. Если требования нельзя предугадать или если выделение буферов, размер кото­рых оценивается по верхней границе, является слишком расточительным, для оптимизации объема буферов нужно применять методы оценки. Можно пока­зать, что в общем случае эта проблема является неразрешимой. Некоторые эври­стические методы решения задачи предложены в [BARB90].