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


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


 

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

В 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

<


Начало  Назад  Вперед



Книжный магазин