В централизованной однопроцессорной системе, как правило, важно только относительное время и не важный точность времен. В распределенной системе, где каждый процессор имеет собственные времена со своей точностью хода, ситуация резко меняется: программы, которые используют время (например, программы, подобный команде make в UNIX, что используют время создания файлов, или программы, для которых важно время прибытия сообщений и т.п.) становятся зависимыми от того, временами какого компьютера они пользуются. В распределенных системах синхронизация физических времен (показывающих реальное время) является сложной проблемой, но из другой стороны очень часто в этом нет никакой необходимости: то есть процессам не нужно, чтобы во всех машинах было правильное время, для них важно, чтобы оно было везде одинаковое, больше того, для некоторых процессов важный только правильный порядок событий. В этом случае мы имеем дело с логическими временами.

Введем для двух произвольных событий отношения "случилось к". Выражение a об b читается "a случилось к b" и означает, что все процессы в системе считают, что сначала состоялось событие a, а потом - событие b. Отношение "случилось к" имеет свойство транзитивности: если выражение a об b и b об c истинны, то справедливо и выражение a об c. Для двух событий того самого процесса всегда можно установить отношение "случилось к", аналогично может быть установленные это отношение и для событий передачи сообщения одним процессом и приемом его другим, потому что прием не может состояться раньше отправления. Однако, если два произвольных события случились в разных процессах на разных машинах, и эти процессы не имеют между собой никакой связи (даже косвенной через третьи процессы), то нельзя сказать с полной уверенностью, которое из событий состоялось раньше, а которое позднее.

Относится задача создания такого механизма ведения времени, которое бы для каждого события а мог заметить значение времени Т(а), из которых бы были согласные все процессы в системе. При этом должно выполняться условие: если а в b , то Т(а) < Т(b). Кроме того, время может только увеличиваться и, итак, любые корректирования времени могут выполняться только путем добавления положительных значений, и никогда - путем вычитания.

Рассмотрим алгоритм решения этой задачи, который предложил Lamport. Для оценок времени в нем используются события. На рисунке 3.6 показанные три процесса, которые выполняются на разных машинах, каждая с который имеет свои времена, которые идут со своей скоростью. Как очевидно из рисунка, когда времена процесса 0 показали время 6, в процессе 1 времени показывали 8, а в процессе 2 - 10. Предполагается, что все эти времена идут из постоянной для себя скоростью.

В момент времени 6 процесс 0 посылает сообщение А процесса 1. Это сообщение приходит к процессу 1 в момент времени 16 по его временам. В логическом содержании это вполне возможно, потому что 6<16. Аналогично, сообщение В, посланное процессом 1 процесса 2 пришло до последнего в момент времени 40, то есть  его передача заняла 16 единиц времени, которое также есть правдоподобным.

Рис. 3.6.  Синхронизация логических времен
а - три процесса, каждый со своими собственными временами;
бы - алгоритм синхронизации логических времен

Ну а дальше начинаются очень странные вещи. Сообщение С от процесса 2 к процессу 1 было отправлено в момент времени 64, а поступило в место назначения в момент времени 54. Очевидно, что это невозможно. Такие ситуации необходимо предотвращать. Решение Lamport'а вытекает непосредственно из отношений "случилось к". Потому что С было отправлено в момент 60, то оно должно дойти в момент 61 или позднее. Итак, каждое сообщение должно нести с собой время своего отправления по временам машины-отправителя. Если в машине, которая получила сообщение, времена показывают время, которое меньше времени отправления, то эти времена переводятся вперед, так, чтобы они показали время, большее времени отправления сообщения. На рисунке 3.6,бы очевидно, что С поступило в момент 61, а сообщение D - в 70.

Этот алгоритм удовлетворяет сформулированным выше требованиям.

 

Возможно стоит прочитать: