Виды декомпозиций. Декомпозиция без потерь


Распределённая взаимная блокировка - часть 2


отказ центрального сайта может вызвать проблемы в функционировании всей системы.

Иерархический метод

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

Распределенный метод

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

на сайте S1

создает агента на другом сайте, например S2, то локальному графу ожидания добавляется ребро, соединяющее узел T1 с узлом ТEXT.

 

 

 

 

 

 




Если локальный граф ожидания содержит цикл, не включающий узел ТEXT, то на сайте существует локальная ситуация взаимной блокировки. Если цикл включает узел ТEXT, то потенциально в системе может присутствовать ситуация глобальной взаимной блокировки. Если для сайта S1 потенциально возможна глобальная взаимная блокировка, то его локальный граф ожидания имеет вид: ТEXT -> Тi-> Тj->…-> ТK-> ТEXT. Для избежания данной ситуации используется следующий алгоритм: каждой из транзакций присваивается временная отметка и устанавливается правило, по которому сайт S1

пересылает свой граф ожидания только тому сайту (SK), на котором ожидает соответствующая транзакция (Тк). Если tS(Ti)<tS(TK), то для проверки наличия взаимной блокировки сайт S1

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

 




Начало  Назад  Вперед



Книжный магазин