Jump to content

Случилось-раньше

(Перенаправлено с заказа Лампорта )

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

Отношение «произошло до» формально определяется как наименее строгий частичный порядок событий, такой что:

  • Если события и происходят в рамках одного и того же процесса, если наступление события предшествовало наступлению события .
  • Если событие это отправка сообщения и события это прием сообщения, отправленного в событии , .

Если два события происходят в разных изолированных процессах (которые не обмениваются сообщениями прямо или косвенно через сторонние процессы), то два процесса называются параллельными, что не является ни тем, ни другим. ни это правда. [2]

Если между событиями в данной системе существуют другие причинно-следственные связи, например, между созданием процесса и его первым событием, эти отношения также добавляются в определение.Например, в некоторых языках программирования, таких как Java, [3] В C, C++ или Rust край «происходит до» существует, если память, записанная оператором A, видна оператору B, то есть, если оператор A завершает запись до того, как оператор B начинает чтение.

Как и все строгие частичные порядки, отношение «произошло до» является транзитивным , иррефлексивным (и бессмысленным, асимметричным ), т.е.:

  • , если и , затем (транзитивность). Это означает, что для любых трёх событий , если случилось раньше , и случилось раньше , затем должно быть, это произошло раньше .
  • (иррефлексивность). Это означает, что ни одно событие не может произойти раньше самого себя.
  • если затем (асимметрия). Это означает, что для любых двух событий , если случилось раньше затем не могло случиться раньше .

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

Процессы, составляющие распределенную систему, не знают об отношении «произошло до», если только они не используют логические часы , такие как часы Лампорта или векторные часы . Это позволяет разрабатывать алгоритмы взаимного исключения и решать такие задачи, как отладка или оптимизация распределенных систем.

См. также

[ редактировать ]
  1. ^ Лэмпорт, Лесли (1978). «Время, часы и порядок событий в распределенной системе» , Communications of ACM , 21 (7), 558-565.
  2. ^ «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.
  3. ^ Гетц и др. 2006 , стр. 339–342, §16.1.3 Модель памяти Java в 500 словах или меньше.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0ccb8c52ec312804657f861da4f0b2d4__1705827540
URL1:https://arc.ask3.ru/arc/aa/0c/d4/0ccb8c52ec312804657f861da4f0b2d4.html
Заголовок, (Title) документа по адресу, URL1:
Happened-before - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)