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

Часы, фиксирующие прямую зависимость

Механизм логических часов, фиксирующих только прямую зависимость между процессами, позволяет снизить накладные расходы на передачу сообщений путем пересылки всего одной скалярной величины с каждым сообщением. В этой связи "полноценное" векторное время, позволяющее отслеживать причинно-следственный порядок событий распределенного вычисления, становится недоступным для процессов непосредственно во время их выполнения, т.е. в режиме on-line. Вместо этого, каждый процесс поддерживает лишь информацию, позволяющую выявлять только прямую зависимость его событий от событий в других процессах. При этом говорят, что событие e_j' процесса P_j находится в прямой зависимости от события e_i другого процесса P_i, если между наступлением событий e_i и e_j' состоялась прямая передача сообщения из P_i в P_j. Более формально: событие e_j' оказывается в прямой зависимости от события e_i тогда и только тогда, когда i = j и e_i →_i e_j', или когда i ≠ j и существуют взаимосвязанные события s и r отправки и получения одного и того же сообщения, такие что (e_i →_i s) ˅ (e_i = s) и (e_j' = r) ˅ (r →_j e_j'). При учете только прямых зависимостей векторная отметка времени любого события, позволяющая определить его транзитивные зависимости, может
быть рекурсивно вычислена в режиме off-line при помощи алгоритма, который исследует ранее зафиксированную процессами информацию о прямой зависимости их событий.
В механизме логических часов, фиксирующих прямую зависимость, каждый процесс P_i вместо вектора V_i поддерживает работу с так называемым вектором прямых зависимостей (англ. direct dependency vector) D_i[1..N]. В компоненте D_i[k] этого вектора хранится локальное время процесса P_k на момент отправки последнего сообщения из P_k в P_i. Отметка времени события e_i определяется всеми компонентами D_i на момент наступления e_i и обозначается через D(e_i). Компоненты D_i[k] инициализируется нулем, 1 ≤ k ≤ N, и каждый процесс P_i использует следующие правила для работы с D_i.

• 
  Перед выполнением любого события процесс P_i вычисляет новое значение своего логического локального времени и записывает его в компонент D_i[i], т.е. D_i[i] = D_i[i] + 1.
  
• 
  Когда процесс P_i отправляет сообщение процессу P_j, вместе с сообщением передается только значение его локального времени D_i[i].
  
• 
  Когда процесс P_j получает от процесса P_i сообщение, содержащее значение времени d, он обновляет i-й компонент своего вектора зависимостей согласно следующему правилу:
  

D_j[i] = max(D_j[i], d).
Отметим, что новое значение D_j[i] вычисляется именно как максимум из старого значения D_j[i] и времени d на случай канала, не обладающего свойством FIFO, т.е. когда сообщение от процесса P_i с большим значением d может опередить предшествующее ему сообщение с меньшим значением d.
Из представленных выше правил работы с вектором D_i видно, что D_i характеризует только прямые зависимости текущего состояния процесса P_i от событий в других процессах. Другими словами, в любой момент значение D_i[j] соответствует порядковому номеру последнего события в процессе P_j, от которого текущее состояние процесса P_i зависит напрямую. Важно отметить, что такое событие процесса P_j могло наступить раньше другого события в P_j, от которого текущее состояние P_i зависит согласно отношению причинно-следственного порядка.
Пример работы часов, фиксирующих прямую зависимость, приведен на рис. 3.8. На этом рисунке, когда процесс P₄ отправляет сообщение процессу P₃, вместе с этим сообщением он передает только значение своего логического времени, равное двум, что позволяет отследить прямую
зависимость второго события e ² процесса P от второго события e ²
3 3 4
процесса P₄. Затем процесс P₃ отправляет сообщение в процесс P₂, тем
самым устанавливая прямую зависимость P₂ от P₃. Таким образом, в
действительности, четвертое событие e ⁴ процесса P становится
2 2
зависимым от второго события e₄² процесса P₄ согласно отношению причинно-следственного порядка. Однако, процесс P₂ не получал об этом никакой информации и непосредственно по ходу своего выполнения установить эту зависимость не может. Более того, в четвертом элементе вектора зависимостей процесса P₂, D₂[4], содержится информация о более раннем событии e₄¹ процесса P₄, от которого e₂⁴ зависит напрямую.

Рис. 3.8. Пример работы часов, фиксирующих прямую зависимость.

Этот пример наглядно демонстрирует тот факт, что рассматриваемый механизм логических часов сам по себе не сохраняет транзитивные зависимости причинно-следственной связи между событиями. Такие зависимости могут быть определены только в режиме off-line с помощью рекурсивного поиска на множестве векторов прямых зависимостей, зафиксированных процессами для своих событий. Очевидно, такой поиск приводит к дополнительным вычислительным затратам и задержкам определения векторного времени того или иного события. Поэтому данный механизм логических часов применяется только для решения таких задач, которые не требуют выявления транзитивной причинно-следственной зависимости между событиями непосредственно "на лету" по ходу выполнения процессов. К таким задачам, например, можно отнести отладку распределенных программ (англ. distributed debugging), когда анализ причины, по которой программа ведет себя не так, как этого ожидают, проводится в режиме off-line, исходя из результатов, полученных при ошибочном выполнении.

Все множество событий, от которых заданное событие e_i зависит транзитивно, может быть определено исходя из определения свойства транзитивности, т.е. путем последовательного объединения информации о событиях e_j', от которых зависит e_i, с информацией о событиях e_k'', от которых в свою очередь зависят события e_j'. Для иллюстрации данного принципа обратимся к рис. 3.8. Здесь вывод о транзитивной зависимости четвертого события e₂⁴ процесса P₂ от второго события e₄² процесса P₄ можно сделать, объединяя зафиксированную в D(e₂⁴) информацию о
зависимости e ⁴ от третьего события e ³ процесса P и зафиксированную в
2 3 3

3

4
D(e₃³) информацию о зависимости e ³ от e ².
Общая схема рекурсивного алгоритма, определяющего множество событий, произошедших раньше x-го по порядку события e_i^x процесса P_i, приведена в Листинге 3.1. Данный алгоритм находит события других процессов из поверхности конуса прошлого события e_i^x, то есть, по сути, формирует векторную отметку времени для e_i^x и сохраняет ее в массиве DTV. Функция DependencyTrack(i,x) инициализирует i-й элемент массива DTV порядковым номером x заданного события e_i^x. Это же значение является логическим локальным временем события e_i^x в процессе P_i и хранится в i-ом компоненте отметки времени D(e_i^x), зафиксированной для e_i^x. Остальные элементы DTV инициализируются нулем. Затем алгоритм анализирует отметку времени каждого события, указанного в каждом элементе DTV, при необходимости рекурсивно вызывая функцию VisitEvent(j,y), где j – идентификатор процесса, а y – порядковый номер события в этом процессе. Каждый раз, когда VisitEvent(j,y) находит в векторе D(e_j^y) значение, превосходящее порядковый номер, хранящийся в соответствующем элементе DTV, в этот элемент DTV записывается найденное новое значение. После этого с помощью VisitEvent осуществляется переход к новому найденному (более позднему) событию и сравнение его отметки времени с DTV. Таким образом, функция VisitEvent рекурсивно проходит события из конуса прошлого события e_i^x. При окончании поиска массив DTV будет содержать порядковые номера всех последних событий, произошедших раньше заданного события e_i^x.