Введение в распределенные

Листинг 3.1. Общая схема алгоритма рекурсивного поиска транзитивных зависимостей.
void DependencyTrack(ProcessID i, EventIndex x) {
/* Построение векторной отметки времени события e_i^x */
/* Результат помещается в массив DTV */ EventIndex DTV[N];
void VisitEvent(ProcessID j, EventIndex y) {
/* Сохраняет зависимости события e_j^y в DTV */
/* Массив D представляет собой отметку времени события e_j^y */
for (int k=0; kif (D[k] > DTV[k])
{ DTV[k] = D[k]; VisitEvent(k, D[k]) }
}

/* Инициализация DTV */ for (int k=0; k
if (k != i) DTV[k] = 0; else DTV[k] = x;

VisitEvent(i, x);

}

Проиллюстрируем работу представленного алгоритма на примере поиска транзитивных зависимостей для четвертого события процесса P₂ (см. рис. 3.8). Вызов функции DependencyTrack происходит с параметрами i = 2, x = 4 и массив DTV приобретает вид (0 4 0 0). Затем вызывается функция VisitEvent(2,4). Для этого события вектор прямых зависимостей D₂ имеет вид (1 4 3 1), поэтому DTV изменяется на

(1 4 0 0) и осуществляется переход к первому событию процесса P₁ с
помощью вызова VisitEvent(1,1). У этого события вектор D₁ = (1 0 0 0). Так как ни один элемент вектора D₁ не превышает соответствующий элемент DTV, то происходит возврат из функции VisitEvent(1,1) и продолжается проверка вектора D₂. На этот раз обнаруживается, что третий элемент вектора D₂ превышает соответствующий элемент DTV (а именно, 3 > 0). Поэтому DTV принимает вид (1 4 3 0), и с помощью VisitEvent(3,3) осуществляется переход к третьему событию процесса P₃. Вектор зависимостей этого события D₃ = (0 0 3 2). Поскольку четвертый элемент D₃ больше, чем соответствующий
элемент DTV (а именно, 2 > 0), DTV изменяется на (1 4 3 2), и вызывается
VisitEvent(4,2). Поскольку ни один элемент D₄ = (0 0 0 2) не превосходит DTV, происходит возврат из VisitEvent(4,2), равно как и из VisitEvent(3,3), т.к. все элементы D₃ оказываются просмотренными. Значение четвертого элемента D₂ оказывается меньше полученного значения четвертого элемента DTV (а именно, 1 < 2), поэтому функция DependencyTrack завершается. Полученное значение векторной отметки времени (1 4 3 2) полностью отражает все транзитивные причинно- следственные зависимости для заданного четвертого события процесса P₂.
Таким образом можно заключить, что механизм часов, фиксирующих прямую зависимость, обладает значительно меньшими накладными расходами на передачу сообщений в сравнении с
традиционными векторными часами, т.к. позволяет передавать с каждым сообщением всего одну скалярную величину. При этом данный механизм предоставляет возможность восстановить все транзитивные причинно- следственные зависимости в режиме off-line с помощью рекурсивного анализа векторов прямой зависимости, зафиксированных процессами.

3.