2015-06-20 4 views
6

В настоящее время я пытаюсь понять временные метки Lamport. Рассмотрим два процесса P1 (производство событий a1, a2, ...) и P2 (продуцирующих события b1, b2, ...). Пусть C (e) обозначает временную метку Lamport, связанную с событием a e. Я создал временные метки для каждого события, как описано в Wikipedia article about Lamport timestamps:Логические часы: Lamport Timestamps

enter image description here

Согласно Википедии, следующее соотношение верно для всех событий e1, e2:

Если e1 произошло раньше e2, затем C (e1) < C (e2).

Давайте посмотрим на a1 и b2. Ясно, что а1 произошло до b2, и так как C (a1) = 1 и C (b2) = 3, то имеет место соотношение: С (а1) < С (б2).

Проблема: Отношение не относится к b3 и a3. Очевидно, b3 произошло до a3. Однако C (b3) = 4 и C (a3) ​​= 3. Таким образом, C (b3) < C (a3) ​​ делает не применяется.

Что я неправильно понял? Помощь очень ценится!

ответ

1

Я заметил свою ошибку.Я писал:

Если e1 произошло до е2, то C (e1) < С (е2).

Тем не менее, Lamport определен как «произошло раньше» как частичный заказ. Вот что говорит Википедия о частично упорядоченных множествах:

Такого отношение называется частичным порядком, чтобы отразить тот факт, что не каждая пара элементов должна быть связана: для некоторых пар, это может быть, что ни один элемент предшествует другой в poset.

Согласно определению Лампорта из «произошло раньше», b3 и a3 не связаны, таким образом b3 «не произойдет до» a3, таким образом, equasion указано в вопросе не обязательно.

1

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

P1 и P2 увеличить свои часы независимо. Когда происходит событие, инициирующий процесс отправляет свое текущее значение целевому процессу, который проверяет, меньше ли полученное значение, чем его текущее значение. Если это так, он изменяет свое текущее значение на принятое значение + 1, иначе он отбрасывает полученное значение. В вашем случае, P1 и P2 не посылают их события a3 и b3.

3

Да, это определение может быть немного запутанным. Правильно, что все остальные сказали до сих пор, однако, возможно, нет единого слова, чтобы лучше понять систему. - одновременно

Если вы обрабатывает p1 и p2 работают на той же машине, там на самом деле не слишком много необходимости использовать Лампорт часов (возможно, некоторые весьма специфична случай). Вместо этого вы можете просто использовать часы, предоставляемые вашей ОС. Но что, если p1 и p2 находятся на компьютерах, которые разделены медленной и ненадежной сетью?

Lamport предполагает, что вы не можете доверять своим местным часам, и у вас нет глобального состояния распределенной системы, в котором произошли события порядка на двух отдельных компьютерах. Именно тогда вы вызываете те события, происходящие одновременно.

Когда вы будете отлаживать выполнение распределенной системы, и вы увидите события a3 и b3 естественно, вы бы предположить, a3 произошло до b3. В вашем конкретном случае вы теперь заявляете: да, но это неправильно. Однако, поскольку события не связаны друг с другом, поскольку они не взаимодействуют друг с другом, порядок обычно считается параллельным, и в этом случае не имеет значения, какое из них произошло первым или вторым, для всего выполнения система.

Поскольку компьютеры и сети работают так быстро и по-прежнему очень точно, что иногда трудно понять, давайте посмотрим на то же самое несколько иначе:

p1 и p2 два человека, живущие несколько 100 лет назад в двух разных долинах. Они общаются вместе, используя pidgins и никогда не говорят о том, когда они выполняли определенную задачу, только то, что они сделали. Таким образом, никто не мог знать, кто, если a3 произошло до b3 или наоборот, поэтому они произошли одновременно. Может быть, не кто-то, бог смотрел сверху на p1 и p2 мог его видеть.

К сожалению, когда у вас есть распределенная система, вы не можете быть богом и смотреть p1 и p2 в то же время, только из той причине, что сообщения от p1 может занять больше времени, чем от p2. Поэтому, несмотря на то, что ваша система мониторинга (бог) получила информацию от b3, прежде чем она получила информацию о a4, это не означает, что они произошли в этом порядке, возможно, пакеты, содержащие информацию о , a4 заняли больше времени или медленный путь.

В конце концов, есть еще одна вещь, называемая vector clocks. Каждый процесс имеет тактовые импульсы для каждого процесса в системе. Ключевым моментом здесь является, событие будет происходить только до события б если все Лампорт тактовые были меньше или равны те б. Если вы попробуете это на своем маленьком примере, вы увидите, что ничего другого не произошло до другого => они являются параллельными.

 Смежные вопросы

  • Нет связанных вопросов^_^