|
В рассмотренном выше механизме логических часов зависимость между процессами устанавливается с помощью передачи одной единственной скалярной величины, что позволяет зафиксировать только прямую зависимость событий одного процесса от событий в других процессах. Поэтому для определения транзитивной причинно- следственной зависимости между событиями возникает необходимость для каждого процесса регистрировать каждое событие получения сообщения, т.е. обновлять и сохранять вектор прямых зависимостей в момент наступления такого события (или, по крайней мере, до наступления следующего события отправки сообщения в этом процессе). В противном случае транзитивную зависимость между событиями будет невозможно восстановить, т.к. цепочка прямых зависимостей окажется разорванной. Если в ходе распределенного вычисления процессы активно обмениваются сообщениями, требование регистрации каждого события получения сообщения может привести к необходимости сохранения большого объема данных и дополнительной нагрузке на процессы.
Метод Жарда-Жордана позволяет адаптивно регистрировать только часть событий, т.е. сохранять информацию об их зависимостях, обеспечивая при этом возможность определять транзитивную причинно- следственную зависимость между зарегистрированными событиями. Другими словами, данный метод позволяет выделять непустое подмножество существенных (регистрируемых) событий ER E и фиксировать причинно-следственный порядок →R, индуцированный исходным порядком → на множестве E. Для этого процессы по ходу своего выполнения должны отслеживать не только прямую зависимость, но и более длинные цепочки зависимостей между любыми двумя регистрируемыми событиями. Это приводит к необходимости пересылать в сообщениях больше информации, нежели несет в себе одна скалярная величина. Поэтому метод Жарда-Жордана можно рассматривать как промежуточное решение между отслеживанием только прямой зависимости (когда с каждым сообщением передается всего один скаляр, но требуется регистрировать каждое событие получения) и отслеживанием полной транзитивной зависимости в векторных часах (когда с каждым сообщением передается вся векторная отметка времени, полностью описывающая все зависимости передающего процесса).
В основе метода Жарда-Жордана лежит следующее наблюдение: если вместе с регистрацией события ei сохраняется вся информация обо всех его зависимостях, то последующие регистрируемые события смогут определить свои транзитивные зависимости, используя информацию, сохраненную при наступлении ei. Поэтому, когда событие ei регистрируется, вся информация о зависимостях, накопленная процессом Pi к этому моменту, сохраняется вместе с этим событием, а соответствующие структуры данных процесса Pi, поддерживающие эту информацию, сбрасываются в состояние зависимости только от события ei. В дальнейшем, когда процесс Pi распространяет информацию о зависимостях, он распространяет только информацию о зависимостях между событиями, произошедшими после ei. При этом следующее регистрируемое событие (в этом или в любом другом процессе) сможет "узнать" о других зарегистрированных событиях, произошедших раньше ei, с помощью информации, сохраненной вместе с ei. Данный метод по- прежнему не позволяет определять транзитивную причинно-следственную зависимость непосредственно по ходу выполнения процессов в режиме on-line, однако, в отличие от механизма логических часов, фиксирующих только прямую зависимость, позволяет избежать необходимости сохранения длинной истории событий.
Для реализации представленного подхода по аналогии с отношением прямой зависимости, рассмотренным в предыдущем пункте, вводится отношение псевдо-прямой зависимости << между событиями распределенного вычисления. А именно, любые два зарегистрированных события ei и ej', происходящие в различных процессах Pi и Pj, связаны отношением псевдо-прямой зависимости, ei << ej', тогда и только тогда, когда между ei и ej' имеется цепочка из взаимосвязанных событий отправки и получения сообщений, не содержащая других зарегистрированных событий. Более формально: ei << ej', тогда и только тогда, когда i = j и ei →i ej', или когда i ≠ j и существуют цепочка s1, r1, s2, r2, … sn, rn взаимосвязанных событий sk и rk отправки и получения сообщений, такая что (ei →i s1) ˅ (ei = s1), события rk и sk+1 происходят в одном и том же процессе, и rk наступает раньше sk+1, (ej' = rn) ˅ (rn →j ej'), и на этой цепочке не встречается ни одного другого зарегистрированного события.
Для отслеживания этой зависимости между событиями каждый процесс Pi поддерживает работу с так называемыми частично-векторными часами PVi (англ.
Do'stlaringiz bilan baham: |
