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




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


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

В 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

<


Содержание  Назад  Вперед