Логические часы

Синхронизация времени

Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте.

В 1978 году Лэмпорт (Lamport) показал, что синхронизация времени возможна, и предложил алгоритм для такой синхронизации. При этом он указал, что абсолютной синхронизации не требуется. Если два процесса не взаимодействуют, то единого времени им не требуется. Кроме того, в большинстве случаев согласованное время может не иметь ничего общего с астрономическим временем, которое объявляется по радио. В таких случаях можно говорить о логических часах.

Для синхронизации логических часов Lamport определил отношение "произошло до". Выражение читается как " a произошло до b " и означает, что все процессы согласны, что сначала произошло событие " a ", а затем " b ". Это отношение может в двух случаях быть очевидным:

1. Если оба события произошли в одном процессе.

2. Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом.

Отношение является транзитивным.

Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения и являются неверными, а эти события называют одновременными.

Введем логическое время С таким образом, что если , то .

Алгоритм:

1. Часы увеличивают свое значение с каждым событием в процессе : (, обычно равно 1).

2. Если событие a есть посылка сообщения m процессом , тогда в это сообщение вписывается временная метка . В момент получения этого сообщения процессом его время корректируется следующим образом: .

Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2). Однако логических часов недостаточно для многих применений (системы управления в реальном времени).

Дата добавления: 2015-04-25