GoProg

 
Топ хэштегов


Архив

Один из отличительных признаков распределенных систем — отсутствие глобальных физических часов. В централизованной системе события можно упорядочить в зависимости от времени их осуществления. В распределенных системах вследствие того, что таймеры на каждом из входящих в систему компьютеров работают с несколько отличающейся частотой, возникает рассинхронизация физических часов. Поэтому представление о физическом времени как о способе упорядочивания событий не совсем подходит для распределенных систем.

Часы Лэмпорта позволяют процессам присваивать порядковые номера («временные метки») сообщениям и другим событиям, чтобы все взаимодействующие процессы могли согласовать порядок связанных событий. Нет никакого предположения о центральном источнике времени и нет понятия о том, когда произошли события. События причинно связаны, если одно событие потенциально может повлиять на результат другого события. Например, события в одном процессе причинно связаны. Если процесс A отправляет сообщение процессу B, все события, произошедшие в процессе A до отправки сообщения, причинно предшествуют всем событиям, которые происходят в B после того, как B получил сообщение.

Центральным понятием логических часов является отношение «произошло до»: a → b представляет событие a, которое произошло до события b. Этот порядок накладывается на последовательные события в процессе, а также на сообщение, отправляемое до того, как оно будет получено другим процессом. Помимо этого, мы можем использовать транзитивное свойство отношения для определения причинности: если a → b и b → c, то a → c.

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

Алгоритм Лэмпорта утверждает, что каждое событие имеет отметку времени (ему присваивается порядковый номер), и каждое сообщение содержит отметку времени часов отправителя (порядковый номер). Сообщение состоит из двух событий: (1) у отправителя есть событие отправки сообщения и (2) у получателя есть событие получения сообщения. Часы - это счетчик всего процесса (например, глобальная переменная) и всегда увеличиваются перед каждым событием. Когда приходит сообщение, если часы получателя меньше или равны отметке времени сообщения, часы устанавливаются на отметку времени сообщения +1. Это гарантирует, что отметка времени, отмечающая событие полученного сообщения, всегда будет больше, чем отметка времени сообщения. что отправил сообщение.

Каждый процесс поддерживает единственный счетчик отметок времени Лэмпорта. Каждое событие в процессе помечается значением этого счетчика. Счетчик увеличивается до того, как будет назначена временная метка события. Если процесс имеет четыре события, a, b, c и d, события получат временные метки Лэмпорта 1, 2, 3, 4 соответственно. Давайте посмотрим на пример. На рисунке ниже показана группа событий для трех процессов. Некоторые из этих событий представляют собой отправку сообщения, другие - получение сообщения, а третьи - просто локальные события (например, запись некоторых данных в файл). С этими назначениями приращения для каждого процесса мы получаем значения часов, показанные на рисунке.

Простой инкрементальный счетчик не дает результатов, согласующихся с причинными событиями. Если событие a произошло до события b, мы ожидаем, что clock(a) < clock(b).

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

На рисунке ниже событие i в процессе P1 - это получение сообщения, отправленного событием b в P0. Если бы событие i было обычным локальным событием, P1 назначил бы ему отметку времени 2. Однако, поскольку полученная отметка времени равна 2, что больше или равно 2, счетчик отметок времени устанавливается на 2 + 1 или 3 Событие i получает метку времени 3. Это сохраняет отношение b → i, то есть b произошло до i. Локальное событие после того, как я получил метку времени 4, потому что счетчик процесса P1 был установлен на 3, когда метка времени для i была скорректирована.

С помощью меток времени Лэмпорта мы уверены, что два причинно-связанных события будут иметь метки времени, отражающие порядок событий. Например, событие h произошло до события m в причинном смысле Лэмпорта. Цепочка причинных событий: h → c, c → d и d → m. Поскольку отношение «произошло до» является транзитивным, мы знаем, что h → m (h произошло до m). Временные метки Лэмпорта отражают это. Отметка времени для h (1) меньше отметки времени для m (7). Однако, просто глядя на временные метки, мы не можем сделать вывод о наличии причинно-следственной связи. Например, поскольку отметка времени для k (1) меньше отметки времени для i (3), это не означает, что k произошло до i. Эти события происходят одновременно, но мы не можем различить это, глядя на временные метки Лэмпорта. Нам нужно использовать другую технику, чтобы определить это. Этот метод заключается в использовании векторных меток времени.

Одним из результатов использования метода Лэмпорта является то, что несколько событий в разных процессах могут быть помечены одной и той же меткой времени. Мы можем сделать каждую метку времени уникальной, добавив к ней глобально уникальный номер процесса. Хотя эти новые временные метки не будут иметь отношения к упорядочиванию в реальном времени, каждая будет уникальным номером, который можно использовать для последовательного сравнения временных меток между несколькими процессами (например, если нам нужно принять решение о том, кто получает доступ к ресурсу на основе сравнения две отметки времени).

Второй недостаток меток времени Лэмпорта заключается в том, что, глядя на метки времени, нельзя определить, существует ли причинно-следственная связь между двумя событиями. Например, только потому, что событие a имеет отметку времени 5, а событие b имеет отметку времени 6, это не означает, что событие a произошло до события b. Таким образом метод Лэмпорта вводит понятие условной упорядоченности.

#IT #логическоевремя #методлэмпорта #распределенныесистемы #часылэмпорта



Новый комментарий: