Логические часыДля синхронизации логических часов Lamport определил отношение "произошло до". Выражение читается как " a произошло до b " и означает, что все процессы согласны, что сначала произошло событие " a ", а затем " b ". Это отношение может в двух случаях быть очевидным: 1. Если оба события произошли в одном процессе. 2. Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом. Отношение является транзитивным. Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения и являются неверными, а эти события называют одновременными. Введем логическое время С таким образом, что если , то . Алгоритм: 1. Часы увеличивают свое значение с каждым событием в процессе : (, обычно равно 1). 2. Если событие a есть посылка сообщения m процессом , тогда в это сообщение вписывается временная метка . В момент получения этого сообщения процессом его время корректируется следующим образом: . Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2). Однако логических часов недостаточно для многих применений (системы управления в реальном времени).
|