7.4 Синхронизация времени
7.4.1. Проблема синхронизации времени
В распределенных системах достигнуть согласия относительно времени совсем непросто. Важность наличия единого времени можно оценить на примере программы make в ОС UNIX. Главные теоретические проблемы - отсутствие глобальных часов и невозможность зафиксировать глобальное состояние (для анализа ситуации - обнаружения дедлоков, для организации промежуточного запоминания).
Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте. Поэтому при организации работы РПС встает задача синхронизации времени компонентов распределенных по разным компьютерам.
7.4.2. Алгоритм синхронизации времени
В 1978 году Лэмпорт (Lamport) показал, что синхронизация времени возможна, и предложил алгоритм для такой синхронизации. При этом он указал, что абсолютной синхронизации не требуется. Если два процесса не взаимодействуют, то единого времени им не требуется. Кроме того, в большинстве случаев согласованное время может не иметь ничего общего с астрономическим временем, которое объявляется по радио. В таких случаях можно говорить о логических часах.
Для синхронизации логических часов Lamport определил отношение "произошло до". Выражение a->b читается как "a произошло до b" и означает, что все процессы согласны, что сначала произошло событие "a", а затем "b". Это отношение может в двух случаях быть очевидным:
Если оба события произошли в одном процессе.
Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом.
Отношение -> является транзитивным.
Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными.
Введем логическое время С таким образом, что если a->b, то C(a) < C(b)
Алгоритм:
Часы Ci увеличивают свое значение с каждым событием в процессе Pi: Ci=Ci+d (d > 0, обычно равно 1)
Если событие a есть посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом: Cj = max(Cj,tm+d)
Поясним на примере, как осуществляется эта коррекция.
|
||
Логическое время без коррекции. |
|
Логическое время с коррекцией. |
|
||
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
6 |
>- |
8 |
|
10 |
|
6 |
>- |
8 |
|
10 |
12 |
|
16 |
|
20 |
|
12 |
|
16 |
|
20 |
18 |
|
24 |
>- |
30 |
|
18 |
|
24 |
>- |
30 |
24 |
|
32 |
|
40 |
|
24 |
|
32 |
|
40 |
30 |
|
40 |
|
50 |
|
30 |
|
40 |
|
50 |
36 |
|
48 |
-< |
60 |
|
36 |
|
48 |
-< |
60 |
42 |
|
56 |
|
70 |
|
42 |
|
61 |
|
70 |
48 |
-< |
64 |
|
80 |
|
48 |
-< |
69 |
|
80 |
54 |
|
72 |
|
90 |
|
70 |
|
77 |
|
90 |
60 |
|
80 |
|
100 |
|
76 |
|
85 |
|
100 |
Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2). Однако логических часов недостаточно для многих применений (системы управления в реальном времени).