Введение

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

1. Необходимо определить действительное наличие блокировки (то есть, является ли объект мусором, взаимозаблокированы ли объекты, всё ли объекты завершили исполнение).

2. Состояние стационарно: без внешнего воздействия на систему, состояние останется заблокированным.

Далее будут рассмотрены эти две задачи и эффективные их решения. Затем мы рассмотрим задачу построения группового решения проблемы обнаружения стационарного состояния зацикливания, независимо от характера задачи.

8.2 Обнаружение взаимоблокировки (deadlock detection)

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

Взаимоблокировка (deadlock), также известна как циклическое ожидание (circular wait) или deadly embrace, означает ситуацию, когда множество объектов, без возможности действия во время ожидания, постоянно заблокирован, ожидая события, которое может сгенерировать только другой объект.

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

Тот факт, что на протяжении работы системы некоторые объекты заблокированы и ожидают наступления какого-либо события – опасен, но не всегда ведёт к взаимоблокировке. К примеру, в протоколе выборов MegaMerger любые сообщения Outside? в город с более низким уровнем блокируются, ожидая увеличение уровня города. Наш протокол был разработан таким образом, поскольку было доказано, что взаимоблокировка здесь не произойдёт. Другими словами, наш протокол был разработан со встроенной защитой от взаимоблокировки. К сожалению, во многих приложениях механизм предотвращения взаимоблокировки не выполним по причине связанных с этим затрат: увеличение технических затрат, замедление работы системы, уменьшение производительности, и так далее. Фактически, в большинстве ситуаций нет встроенного механизма, обеспечивающего уверенность в том, что объекты не будут взаимозаблокированы, таким образом, взаимоблокировка может произойти и происходит. Поэтому необходимо иметь механизм обнаружения сформировавшихся взаимоблокировок и их ликвидации. В то время, как фаза разрешения целиком зависит от специфики приложения и от ситуации, задача обнаружения имеет сходный характер, поэтому мы сосредоточимся на её эффективном решении.

Задача обнаружение взаимоблокировки (deadlock detection) – одно из определений, означающих анализ на присутствие взаимоблокировки в системе. Протокол принятия решения запускается любым объектом, подозревающим, что он вовлечён во взаимоблокировку. Задача может решаться следующими методами:

• Персональное обнаружение: в пределах конечного времени каждый объект должен определять, находится ли он в состоянии блокировки.
• Компонентное обнаружение: в пределах конечного времени каждый объект должен определять, находится ли он в состоянии блокировки. Если это так, все объекты должны быть об этом оповещены.
• Системное обнаружение: если в системе произошла взаимоблокировка, по крайней мере один объект должен об этом знать.

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

8.2.2 Обнаружение взаимоблокировок: граф ожидания (Wait-For)

Прежде всего, опишем задачу состояния взаимоблокировки более строго.

Множество S = {s1, ..., sk} <= E из k > 1 объекта заблокировано при одновременном выполнении следующих двух условий:

1. Каждый элемент si S ожидает событие (называемого разрешением), которое должно быть сгенерировано другим элементом множества.

2. нет элемента si S способного сгенерировать разрешение в процессе ожидания.

При соблюдении этих условий элементы множества буду постоянно в ожидании, независимо от природы разрешения и причины ожидания «разрешения»; например это может быть потому, что si необходим ресурс, заблокированный sj.

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

описать статус объектов в течение исполнения, относительно их ожидания

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

Каждый узел в графе ожидания представляет объект; если элемент x заблокирован ожиданием события, которое может быть сгенерировано только объектами y1, y2, ..., yk, то будут управляющие связи (x, y1), (x, y2), ..., (x, yk) в W. Другими словами, соседи с исходящими связями, направленными к элементу x – все элементы, разрешения которых ожидает x, соседи со входящими от x связями – элементы, ожидающие разрешения от x. Далее примем, что W принадлежит G.

ВАЖНО. В некоторых системах элемент x может ожидать разрешения от элемента y, не являющегося элементом сети. Это означает наличие связей (x,y) в W, не содержащихся в G. В этом случае мы предполагаем механизм управления, обеспечивающий связь между любыми двумя элементами.

Согласно определению, мы имеем следующие простые свойства:

Свойство 8.2.1 Все элементы бикомпоненты графа W взаимозаблокированы

Свойство 8.2.2 Если в W содержится цикл, каждый элемент цикла заблокирован

Свойство 8.2.2 Пусть С – бикомпонента W. Если есть направленный путь в W из x в C, то x заблокирован.

Другими словами, не только бикомпоненты (например, циклы), но и те, которые могут достигнуть такого компонента – заблокированы.

В отличие от этого, при отсутствии взаимоблокировок W состоит исключительно из направленных нециклических графов.

Свойство 8.2.3 Если каждый подграф графа W – направленный нециклический граф, взаимоблокировки нет.

Иными словами, при отсутствии взаимоблокировок W(t) не содержит циклов. Это означает, что для обнаружения взаимоблокировок в системе эквивалентно обнаружению циклов в графе ожидания. По этой причине обнаружение взаимоблокировок иногда относят к задачам обнаружения циклов.

Однако, этого не достаточно для персонального и компонентного обнаружения. В этом случае фактически мы должны определить вовлечён ли инициатор во взаимоблокировку; это означает (согласно свойствам 8.2.1, 8.2.2 и 8.2.3), что мы должны определить входит ли элемент в бикомпоненту или может ли достичь элемент бикомпоненты в графе ожидания.

Рисунок 18.1 - граф ожидания

Теорема 8.2.1 Объект x заблокирован тогда и только тогда, когда существует направленный путь от x к бикомпоненте в W.

Рассмотрим пример графа ожидания W (рис. 8.1). Граф W содержит бикомпоненту {f, g, h, i}, и только d имеет направленную связь с ней. Согласно теореме 8.2.1, объекты d, f, g, h и i – взимозаблокированы, в то время как a, b, c и e – нет.

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

8.2.3 Системы с одиночным запросом (Single-Request Systems)

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

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

Свойство 8.2.4 В модели с одиночными запросами компонента связности графа W также является корневым деревом или кроной.

Крона – направленный граф, состоящий из направленных циклов, в которых каждый элемент – корень корневого дерева; цикл называется каркасом кроны. Граф ожидания, изображённый на рис. 8.2 состоит из трёх подграфов, два из которых – корневые деревья, и один – крона.

Свойство 8.2.5 В модели с одиночным запросом,

(а) все узлы кроны взаимозаблокированы;

(б) если не заблокированы, W не содержит кроны.

Рисунок 2 - Граф ожидания, состоящий из кроны и 2-х корневых деревьев

Другими словами, при отсутствии взаимоблокировок, граф W является лесом корневых деревьев. Это следует из свойств 8.2.4 и 8.2.5,

Теорема 8.2.2 В модели с одиночными запросами объект x заблокирован тогда и только тогда, когда он является частью кроны графа W.

Таким образом, для определения вхождения объекта во взаимоблокировку необходимо только знать входит ли он в крону или дерево.

Посмотрим, как это может быть достигнуто. Простое тривиальное решение – собрать все данные о графе ожидания и проверить, цикличен он или нет. Хотя и простое, это решение заведомо неэффективно. Рассмотрим альтернативное решение, где DFlood заполняет направленный граф.

Простая проверка

1. Пусть объект x0 производит широковещательный опрос на состояние взаимоблокировки

2. Если объект x0 не состоит в группе взаимозаблокированных объектов, компонента связности графа W, к которой он принадлежит – корневое дерево; таким образом, сообщение от x0 будет передаваться до тех пор, пока не достигнет корня, скажем r; в этом случае объект r посылает объекту x0 сообщение об отсутствии бзаимоблокировки в данной компоненте.

3. В случае, когда x0 заблокирован. Это значит, что связный компонент, к которому принадлежит объект – крона. Как следствие, сообщение, сгенерированное x0 прежде всего достигнет каркаса, а затем будет циркулировать по кругу; это значит, что в определённый момент объект r получит это сообщение снова. Тогда станет известно, что этот компонент заблокирован. Заметьте, что r, делающий это открытие сам x0, если он – часть каркаса, иначе – это узел в каркасе, самый близкий к x0. В этом случае, в зависимости от политики прерывания состояния блокировки, r осведомит об этом x0 (персональное обнаружение) или произведёт широковещательное осведомление используя Flood в W (коллективное обнаружение).

Оценим стоимость стратегии. Если компонента связности W(x0) графа ожидания к которой принадлежит x0 – дерево, общее число сообщений для x0, чтобы определить, что он сейчас не заблокирован составляет 2 d(x0,r), где r – корень. Если W(x0) – крона, то для обнаружения взаимоблокировки необходимо d(x0,r) + c(x0) сообщений, где r – объект в каркасе, наиболее близкий к x0, а c(x0) – размер каркаса (например, длин цикла); заметим, что в этом случае только r узнает о блокировке. В зависимости от политики разрешения блокировок, это может стать началом широковещательного сообщения (если сообщения необходимы) или запуском протокола разрешения блокировки. Таким образом, в худшем случае будут разосланы положительные сообщения O(|N(x0)|), где N(x0) – множество объектов в W(x0). Мы будем активизировать протокол, реализующий стратегию «простой проверки» (задача 8.6.1).

В случае множественной инициации, как мы условились, объекты имеют уникальные идентификаторы (id), мы можем использовать id для различия инициаторов проверки; таким образом каждый из них независимо может производить «простую проверку». Однако мы можем уменьшить общее число сообщений. Можно, например, позволить это только объекту с наименьшим id в компоненте связности (до тех пор, пока блокировка не будет обнаружена). Результирующий протокол «простая проверка+» показана на рисунках 8.3 и 8.4, где in N(x) и out N(x) обозначают смежные объекты со входящими и исходящими связями соответственно.

Общая стоимость остаётся высокой. Положим, k обозначает количество инициаторов проверки в определённой компоненте связности. В худшем случае, сообщение от каждого из k инициаторов попадёт в каркас и сделает круг (если будет возможность закончить проход по каркасу), произведя возможно O(n) передач, для общего количества O(kn) сообщений.

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

8.2.4 Системы с множественным запросом

В предыдущем разделе мы ознакомились со случаем, когда каждый объект ожидал в определённое время только одно разрешение. Что будет, если снять это ограничение? В общем случае, объект может ожидать несколько других объектов и не сможет продолжить работу до тех пор, пока не получит разрешения от всех них; такая ситуация иногда называется моделью запроса-И (AND-request model). Эта модель сложнее модели с одиночным запросом, поскольку объект может быть вовлечён в несколько взаимоблокировок сразу, и может относиться к более, чем одной бикомпоненте.

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

Простое решение: общая простая проверка. Простое и эффективное решение – обобщение простой проверки; оно состоит из инициатора x0, посылающего в систему

PROTOCOL SimpleCheck.
_ States: S = {INITIATOR, IDLE, ACTIVE, DEAD};
SINIT = {INITIATOR, IDLE};
STERM = {IDLE,DEAD}.
_ Restrictions: RI, Message Ordering.
IDLE
Spontaneously
begin
if outN(x) = then /* I am waiting */
send("Check", id) to outN(x);
checker-links:= I;
checker-id:= id;
become ACTIVE;
end
Receiving("Check", value)
begin
if outN(x) = then /* I am a root */
send("NoDeadlock", value) to sender;
else
checker-links:={sender};
checker-id:= value;
send("Check", value) to outN(x);
become ACTIVE;
endif
end
Receiving("Deadlock", value)
begin
send("Deadlock", value) to inN(x);
become DEAD;
end

При отсутствии блокировки: сначала рассмотрим случай, когда x0 не вовлечён во взаимоблокировку; по свойству 8.2.3 это означает, что компонента связности графа W, в которую включен x0 является дегом , скажем D. Напомним, что в дэге 3 типа узлов: источники, приёмники и двунапраленные (имеют входящие и исходящие связи). Понятно, что приёмники не заблокированы.

Каждый двунаправленный узел y получает сообщение отправителя и данные из сообщения, добавляя к данным сообщения свой id, направляет его соседним объектамс исходящими связями и ожидает ответа от всех их. Это сообщение в конечном счёте достигнет всех приёмников в D; когда приёмник получает такое сообщение, поскольку он не заблокирован, он ответит отрицанием на запрос о блокировке.

ACTIVE
Receiving("Check", value)
begin
if value = checker-id then
/* I have already received this message */
send("Deadlock", value) to outN(x) : inN(x);
become DEAD;
else
checker-links:= checker-links {sender};
if value < checker-id then
checker-id:= value;
send("Check", value) to outN(x);
endif
end
Receiving("Deadlock", value)
begin
send("Deadlock", value) to outN(x) : inN(x) - {sender};
become DEAD;
end
Receiving("NoDeadlock", value)
begin
send("NoDeadlock", value) to checker-links;
become IDLE;
end

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

При наличии взаимоблокировки: Теперь рассмотрим случай, когда x0 вовлечён во взаимоблокировку. Это означает (Теорема 8.2.1), что x0 также входит в бикомпоненту графа W или соединена с ней связью.

В этом случае проверочное сообщение, разосланное широковещательно объектом x0 достигнет их всех.

Двунаправленный узел (имеющий как входящие, так и исходящие связи) y получит проверочное сообщение, проверит, включён ли он в список уже посещённых этим сообщением узлов; если это так – во взаимоблокировку включен как x0, так и y. Иначе, y производит собственное сообщение, добавляя к полученному сообщению свой id, рассылает его всем соседним узлам с исходящими связями и ожидает ответа от всех их. Как и раньше, если все ответы отрицают наличие блокировки, y отправит такое же сообщение всем отправителям проверочного сообщения, сгенерированного узлом x0.

Это означает, что в пределах конечного времени каждый из узлов отправит сообщение, содержащее его собственный id в списке посещённых узлов.

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

Эффективное решение: LockGrant Рассмотрим, как используя некоторые из этих идей получить эффективное решение определения принадлежности инициатора x0 к блокировке.

Рассмотрим компоненту связности с x0. В этой компоненте каждый не ожидающий объект, очевидно – не заблокирован. По определению, такие объекты – приёмники (то есть, не имеют соседей, от которых ожидается разрешение); каждый из таких объектов точно знает, что он не заблокирован. Рассмотрим теперь ожидающий узел, разрешения к которому приходят только от приёмников: этот объект также не заблокирован. Действительно, любой объект, ожидающий разрешения только от незаблокированных объектов – не заблокированы.

Этот факт даёт нам стратегию для обнаружения незаблокированных объектов.

Стратегия Grant:

1. Инициатор инициирует проверку в объектах, включенных в компоненту связности.

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

3. Если объект зарегистрирован как такой, что все его соседи ожидают разрешения (то есть, это объект со входящими связями), то такой объект не заблокирован.

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

Прежде всего, мы построим дерево охвата с корнем в x0 компоненты связности x0 в графе ожидания; мы будем формировать его на этапе подготовки и использовать это дерево для того, чтобы позволить определить x0, когда проверка закончится. Задача легко решается при использовании Shout в графе ожидания. (Проверка связей на двунаправленность: направление только логическое). Однако узел будет ожидать, чтобы отправит ответ, своих родителей до тех пор, пока те не получат ответы от всех своих соседей.

Стратегия Grant встроена в замедленный Shout. Когда приёмник получает «Shout»-сообщение впервые, в дополнение к сообщению «Shout», y будет информировать о факте, что он не заблокирован посылкой сообщения «Grant» всем своим соседям с исходящими связями. Для удачного завершения, приёмник y пошлёт ответ своим родителям только после того, как получит не только ответы от всех своих соседей, для всех собственных «Grant» сообщений (заметьте, что это будет происходить всегда).

Для того, чтобы знать о том, что он не заблокирован, не приёмник объект z должен получить сообщение «Grant» от всех соседей с входящими связями; до тех пор, пока это не случится (заметьте, что это может не случится никогда), z будет посылать подтверждение в ответ каждому принятому сообщению «Grant». Если это случается, то есть, z получает сообщение «Grant» от всех соседей с входящими связями, объект z заключает, что он не заблокирован; после этого он пошлёт сообщение «Grant» всем своим соседям с исходящей связью. Для успешного завершения, z подтвердит последнее принятое им сообщение «Grant» не немедленно, а только после того, как получит подтверждение от всех собственных сообщений «Grant» (заметьте, что это будет происходить всегда).

В этом случае общая ликвидация Shout будет происходить после всех передач «Grant» и «Grant-Acks». Кроме того, общая ликвидация взаимоблокировок по всем действиям совпадает с локальной ликвидацией Shout инициатора.

Подведём итог локальной ликвидации Shout, инициатор знает своё состояние: он не заблокирован только в том случае, когда получил сообщение «Grant» от всех своих соседей с входящими связями.

Однако, другие объекты не могут знать, находятся ли они в состоянии блокировки. К примеру, рассмотрим объект не приёмник получивший первое «Shout» сообщение, он отправит его всем своим соседям, получи от каждого из них ответ, а затем отправит собственный ответ своему родителю; другими словами, все действия «Shout» для x прекратятся. Всё же, x ещё может получить сообщение «Grant» (оно может поступить от его собственного родителя: задача 8.6.3). Таким образом, инициатору необходимо реализовать механизм «голосования» (например, оповещение от всех объектов о завершении) даже если решается только проблема собственного обнаружения блокировки.

В случае персонального обнаружения блокировки, набор передаваемых данных, называемых протоколом LockGrant, показан на рисунках 8.5 и 8.6. В протоколе механизм голосования реализован в процедуре RESOLVE (которая оставлена неописанной); заметьте, что если инициатор не приёмник, он даже не запустит Shout, так как он знает, что он не заблокирован.

Теперь докажем работоспособность протокола; прежде всего сфокусируемся на его завершении.

Для завершения, инициатор должен завершить все исполнения Shout, то есть, должен получить «Replay» от всех своих соседей. Как уже было сказано, если узел посылает сообщение «Grant», это задерживает отправку его «Reply» его родителю до тех пор, пока он не получит «Grant-Ack» от всех его соседей с входящей связью. Следующие теоремы дают уверенность, что все подтверждения будут отправлены, задержанные Reply будут отправлены, и таким образом инициатор получит данные о блокировке в пределах конечного времени (задачи 8.6.4 и 8.6.5).

Свойство 8.2.6 Если объект отправил сообщение «Grant» соседнему объекту, то он получит «Ack» от него в пределах конечного времени.

Свойство 8.2.7 Каждый объект y != x0 отправит «Reply» своему родителю в пределах конечного времени.

Свойство 8.2.8 Если объект посылает сообщение «Shout» соседнему объекту, то он получит сообщение «Reply» от соседа в пределах конечного времени.

Из этих теорем следует:

Лемма 8.2.1 инициатор x0 будет исполнять RESOLVE в пределах конечного времени.

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

Следующие две теоремы показывают, что когда инициатор прекращает проверку, все остальные действия также прекращаются и механизм Grant, встроенный в Shout действительно корректно функционирует (задачи 8.6.6-8.6.8).

PROTOCOL LockGrant
_ States: S = {INITIATOR, IDLE, ACTIVE};
SINIT = {INITIATOR, IDLE};
_ Restrictions: RI, Single Initiator, Message Ordering.
INITIATOR
Spontaneously
begin
if |outN(x)| > 0 then
initiator:=true; INITIALIZE;
send("Shout") to outN(x) : inN(x);
become ACTIVE;
else
alive:=true;
RESOLVE;
endif
end
IDLE
Receiving("Shout")
begin
INITIALIZE
parent:= sender;
send("Shout") to outN(x) : inN(x) ? {sender};
if |outN(x)| = 0 then /* I am a sink */
alive:= sink:= true;
send("Grant") to inN(x);
waiting-for-ack:= true;
else
if all = 0 then /* I am a leaf */
send("Reply") to sender
sent-last-reply:= true;
endif
endif
become ACTIVE;
end
Procedure INITIALIZE
begin
granted:= count-reply := count-ack := 0;
alive:= waiting-for-ack := sent-last-reply:= false;
all:= |inN(x) : ourN(x)| ? 1;
if initiator then all:= all +1 endif
end

Свойство 8.2.9 Если сообщение «Grant» не было подтверждено во время t, то инициатор x0 ещё не получил «Reply» от всех его соседей.

Свойство 8.2.10 Объект получает сообщение «Grant» от всех соседних объектов с входящими связями только в том случае, если он не заблокирован.

То есть

Лемма 8.2.2 Инициатор проверки x0 не заблокирован только тогда, когда он исполняет RESOLVE, alive(x0) = true.

ACTIVE
Receiving("Shout")
begin
send("Reply") to sender;
end
Receiving("Grant")
begin
granted:= granted+1;
if granted < requests then
send("Grant-Ack") to sender;
else /* I am not deadlocked */
alive:=true;
grant-link:= sender;
if inN(x) = then /* somebody is blocked on me */
send("Grant") to inN(x);
waiting-for-ack:= true;
else
send("Grant-Ack") to grant-link;
endif
endif
end
Receiving("Grant-Ack")
begin
count-ack := count-ack+1;
if count-ack = |inN(x)| then /* received all acknowledgments */
if not(sink) then
send("Grant-Ack") to grant-link;
endif
if (count-reply=all and not(sent-last-reply)) then
send("Reply") to parent;
endif
endif
end
Receiving("Reply")
begin
count-reply:= count-reply+1;
if (count-reply=all and not(waiting-for-ack)) then
if (initiator) then
RESOLVE
else
send("Reply") to parent;
sent-last-reply:= true;
endif
endif
end

Из лемм 8.2.1 и 8.2.2 следует:

Теорема 8.2.3 протокол LockGrant решает задачу персонального обнаружения ситуации взаимоблокировки.

В случае коллективного обнаружения, достаточно соответственно определить процедуру RESOLVE.

Стоимость протокола LockGrant не трудно оценить. Есть два базовых действия: shouting и granting. Shouting использует одно «Shout» сообщение для каждой связи построенного дерева и два «Shout» для всех остальных связей, и он использует «Reply» для каждого «Shout»; таким образом, общее их количество не более 4|E(x0)| - 2|N(x0)| + 2 сообщений, где E(x0) и N(x0)| означают количество двунаправленных связей и узлов соответственно, в компоненте связности W(x0) в которой x0 – принадлежит W. В случае granting будет самое большее один «Grant» для каждого входа, каждой генерации «Ack», всего 2|E(x0)| сообщения. Следовательно, всего перед заключительным уведомлением 6|E(x0)| - 2|N(x0)| + 2.

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

M[LockGrant] <= 6|E(x0)| - |N(x0)| + 1 (8.1)