Распределённая взаимная блокировка
Любые алгоритмы управления параллельностью, использующие механизмы блокировок, могут приводить к появлению в системе ситуации взаимной блокировки процессов (тупиковая ситуация, которая может возникнуть, когда 2/более транзакции находятся во взаимном ожидании освобождения блокировок, удерживаемых каждой из них).
Пример.
·
Транзакция Т1 запускается на сайте S1 и создает агента на сайте S2.
· Транзакция Т2 запускается на сайте S2 и создает агента на сайте S3.
· Транзакция Т3 запускается на сайте S3 и создает агента на сайте S1.
Эти транзакции устанавлиают блокировки таким образом, что образуется взаимная блокировка по следующей схеме:
 |
 |
 |
Графы ожидания для сайтов
 |
Комбинированный граф ожидания для сайтов
В СУРБД для выявления ситуаций взаимной блокировки недостаточно использовать обычные (локальные) графы ожидания, необходимо также строить глобальный граф ожидания (объединение всех локальных графов ожидания).
Существует 3 общих метода выявления взаимных блокировок в СУРБД: централизованный, иерархический и распределенный.
Централизованный метод
выявления взаимных блокировок, при этом методе один из сайтов системы назначается координатором выявления взаимных блокировок (DDC). Сайт DDC отвечает за построение и обработку глобального графа ожидания. С определенным интервалом каждый менеджер блокировки в системе направляет в адрес DDC свой локальный граф ожидания. Сайт DDC выполняет построение глобального графа ожидания и проверяет его на наличие циклов, если граф содержит 1/более циклов, DDC должен разрушить их, выбрав те транзакции, которые должны быть отменены с выполнением отката, а затем перезапущены. Для минимизации количества пересылаемых данных каждый менеджер блокировки посылает сведения только об удалении/добавлении ребер в локальном графе ожидания, произошедшие с момента последней отправки сведений. Недостаток данного метода: снижение надежности всей системы, т.к.
отказ центрального сайта может вызвать проблемы в функционировании всей системы.
Иерархический метод
выявления взаимных блокировок, при данном методе сайты в сети образуют некоторую иерархию. Каждый из сайтов для выявления наличия взаимных блокировок посылает свой локальный граф ожидания на сайт, расположенный в иерархии на уровень выше его. Каждый более высокий уровень образует узлы, выполняющие контроль взаимных блокировок на узлах в более низких уровнях. Иерархический подход сокращает зависимость выявления взаимных блокировок от центрального сайта, а также способствует снижению издержек на передачу данных. Однако, его реализация намного сложнее, особенно с учетом возможности отказов отдельных сайтов и линий связи.
Распределенный метод
выявления взаимных блокировок. Существуют различные варианты алгоритмов распределенного выявления взаимных блокировок, рассмотрим наиболее известный. В данном методе к локальному графу ожидания добавляется внешний узел ТEXT, отражающий наличие агента на удаленном сайте. Когда транзакция Т1
на сайте S1
создает агента на другом сайте, например S2, то локальному графу ожидания добавляется ребро, соединяющее узел T1 с узлом ТEXT.
 |
пересылает свой граф ожидания только тому сайту (SK), на котором ожидает соответствующая транзакция (Тк). Если tS(Ti)<tS(TK), то для проверки наличия взаимной блокировки сайт S1
должен переслать свой локальный граф на сайт SK. Сайт SK добавляет полученную информацию к своему локальному графу ожидания и проверяет результат на наличие циклов, не включающих узел ТEXT. Если таких циклов нет, то процесс выполняется или до появления цикла, или до построения полного глобального графа ожидания, не содержащего циклов (взаимные блокировки в системе отсутствуют). Доказано, что если в системе существует глобальная взаимная блокировка, то описанная выше процедура непременно вызовет появление цикла в графе ожидания одного из сайтов.
