Случилось-раньше
В информатике произошло -раньше отношение (обозначается: ) — это отношение между результатом двух событий, такое, что если одно событие должно произойти раньше другого события, результат должен это отражать, даже если эти события в действительности выполняются не по порядку (обычно для оптимизации потока программы). Это предполагает упорядочивание событий на основе потенциальной причинно-следственной связи пар событий в параллельной системе, особенно в асинхронных распределенных системах . Его сформулировал Лесли Лэмпорт . [1]
Отношение «произошло до» формально определяется как наименее строгий частичный порядок событий, такой что:
- Если события и происходят в рамках одного и того же процесса, если наступление события предшествовало наступлению события .
- Если событие это отправка сообщения и события это прием сообщения, отправленного в событии , .
Если два события происходят в разных изолированных процессах (которые не обмениваются сообщениями прямо или косвенно через сторонние процессы), то два процесса называются параллельными, что не является ни тем, ни другим. ни это правда. [2]
Если между событиями в данной системе существуют другие причинно-следственные связи, например, между созданием процесса и его первым событием, эти отношения также добавляются в определение.Например, в некоторых языках программирования, таких как Java, [3] В C, C++ или Rust край «происходит до» существует, если память, записанная оператором A, видна оператору B, то есть, если оператор A завершает запись до того, как оператор B начинает чтение.
Как и все строгие частичные порядки, отношение «произошло до» является транзитивным , иррефлексивным (и бессмысленным, асимметричным ), т.е.:
- , если и , затем (транзитивность). Это означает, что для любых трёх событий , если случилось раньше , и случилось раньше , затем должно быть, это произошло раньше .
- (иррефлексивность). Это означает, что ни одно событие не может произойти раньше самого себя.
- если затем (асимметрия). Это означает, что для любых двух событий , если случилось раньше затем не могло случиться раньше .
Заметим, что свойство асимметрии непосредственно вытекает из предыдущих свойств: от противного предположим, что у нас есть и . Тогда по транзитивности имеем что противоречит иррефлексивности.
Процессы, составляющие распределенную систему, не знают об отношении «произошло до», если только они не используют логические часы , такие как часы Лампорта или векторные часы . Это позволяет разрабатывать алгоритмы взаимного исключения и решать такие задачи, как отладка или оптимизация распределенных систем.
См. также
[ редактировать ]Цитаты
[ редактировать ]- ^ Лэмпорт, Лесли (1978). «Время, часы и порядок событий в распределенной системе» , Communications of ACM , 21 (7), 558-565.
- ^ «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.
- ^ Гетц и др. 2006 , стр. 339–342, §16.1.3 Модель памяти Java в 500 словах или меньше.
Ссылки
[ редактировать ]- Гетц, Брайан; Пайерлс, Тим; Блох, Джошуа; Боубир, Джозеф; Холмс, Дэвид; Леа, Дуг (2006). Параллелизм Java на практике . Эддисон Уэсли. ISBN 0-321-34960-1 .