partial vector clock), представляющими собой множество упорядоченных пар вида (j, x), каждая из которых указывает на то, что текущее состояние Pi находится в псевдо-прямой зависимости от зарегистрированного события ejx с порядковым номером x в процессе Pj. Пара (i, v) определяет текущее логическое локальное время v процесса Pi. Зависимости регистрируемого события ei сохраняются в его отметке
времени, которая определяется показаниями частично-векторных часов на момент наступления ei и обозначается через PV(ei). Исходные показания частично-векторных часов для Pi: PVi = {(i, 0)}.
Пусть PVi = {(i1, v1), … (i, v), … (in, vn)} – текущие показания частично-векторных часов процесса Pi. По методу Жарда-Жордана каждый процесс Pi использует следующие правила для работы со своими логическими часами:
При регистрации очередного (v + 1)-го события eiv+1 процесс Pi вычисляет новое значение своего логического локального времени и записывает его в PVi:
PVi = {(i1, v1), … (i, v + 1), … (in, vn)}.
После этого показания частично-векторных часов процесса Pi сохраняются в отметке времени PV(eiv+1) и затем сбрасываются в состояние зависимости только от события eiv+1:
PVi = {(i, v + 1)}.
При отправке сообщения из Pi в Pj вместе с сообщением передаются текущие показания PVi.
Когда процесс Pi принимает сообщение с отметкой времени PVmsg = {(im1, vm1), (im2, vm2), … (imk, vmk)}, он устанавливает показания своих частично-векторных часов PVi в виде множества следующих пар:
все пары (imx, vmx), такие что (imx, .) не содержатся в PVi;
все пары (ix, vx), такие что (ix, .) не содержатся в PVmsg;
пары (ix, max(vx, vmx)) для всех (ix, .), которые содержатся и в
PVi и в PVmsg.
Пример работы адаптивного метода Жарда-Жордана приведен на рис. 3.9; регистрируемые события отмечены жирным кружочком. Рассмотрим работу процесса P2. Исходные показания логических часов PV2 этого процесса равны (2, 0). При регистрации события e21 процесс P2 вычисляет новое значение своего локального времени и копирует его в отметку времени PV(e21). При получении сообщения от процесса P1 в показания логических часов PV2 добавляется пара (1, 0). Аналогичная ситуация возникает при получении сообщения от процесса P3 с отметкой времени {(3, 1), (4, 0)}. В итоге PV2 = {(1 ,0), (2, 1), (3, 1), (4, 0)}. Когда же
регистрируется событие e 2, процесс P увеличивает свое локальное время,
2 2
и полученные показания логических часов сохраняются в отметке времени PV(e22) данного события. После этого показания PV2 сбрасываются в значение (2, 2). Таким образом легко видеть, что событие e22 напрямую
зависит от событий e 0, e 1 и e 1. Кроме того, данное событие находится в
1 2 3
4
отношении псевдо-прямой зависимости от события e 0.
Рис. 3.9. Пример работы адаптивного метода Жарда-Жордана.
Транзитивные зависимости заданного события ei могут быть восстановлены путем анализа отметок времени событий, c которыми ei связано отношением псевдо-прямой зависимости. Если такой анализ провести рекурсивно, то могут быть найдены все события, произошедшие раньше ei.
Основное преимущество метода Жарда-Жордана заключается в том, что этот метод позволяет настраивать оптимальный размер отметки времени, передаваемой с каждым сообщением. А именно, количество пар, содержащихся в логических частично-векторных часах, может быть ограничено сверху путем регистрации дополнительных событий. Например, если требуется, чтобы размер логического времени не превышал k пар, достаточно, чтобы процесс зарегистрировал дополнительное событие, когда число накопленных им зависимостей достигнет k. Такое свойство адаптивной регистрации событий позволяет гибко контролировать накладные расходы на передачу сообщений при распределенном вычислении.
Do'stlaringiz bilan baham: |