Операционные системы распределенных вычислительных систем

       

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


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

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

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

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

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

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

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

Введем логическое время С таким образом, что если a-->b, то C(a) < C(b)

Алгоритм:

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

Ci = Ci + d      (d > 0, обычно равно 1)

(2)   Если  событие  «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

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

Однако логических  часов  недостаточно  для   многих   применений (системы управления в реальном времени).

Физические часы.

После изобретения  в  17 веке механических часов время измерялось астрономически. Интервал между  двумя  последовательными  достижениями солнцем наивысшей  точки на небе называется солнечным днем.  Солнечная секунда равняется 1/86400(24*3600) части солнечного дня. В 1940-х годах было установлено,  что  период  вращения  земли  не  постоянен - земля замедляет вращение из-за приливов и атмосферы.  Геологи  считают,  что 300 миллионов  лет назад в году было 400 дней.  Происходят и изменения длительности дня  по  другим  причинам.  Поэтому  стали  вычислять  за длительный период среднюю солнечную секунду.

С изобретением в 1948 году атомных  часов  появилась  возможность точно измерять   время  независимо  от  колебаний  солнечного  дня.  В настоящее время 50 лабораторий  в  разных  точках  земли  имеют  часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI),  исчисляемым с 1 июля 1958 года.

Отставание TAI   от   солнечного  времени  компенсируется  добавлением секунды тогда,  когда  разница  становится  больше  800   мксек.   Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При  объявлении  о  добавлении  секунды  к  UTC  электрические компании меняют частоту с 60 Hz на 61  Hz  (c  50  на  51)  на  период времени в 60 (50) секунд.  Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком  (Fort  Collins,  Colorado)  в начале каждой секунды UTC. Есть и другие службы времени.

Алгоритмы синхронизации времени.

Две проблемы  -  часы  не  должны ходить назад (надо ускорять или замедлять их для проведения коррекции) и ненулевое  время  прохождения сообщения о времени (можно многократно замерять  время  прохождения сообщений с показаниями часов туда и обратно,   и брать самую удачную попытку – с минимальным временем прохождения).


Содержание раздела