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

В Информатика, то случилось раньше связь (обозначается: ${ Displaystyle к ;}$) - это отношение между результатом двух событий, так что если одно событие должно произойти до другого, результат должен отражать это, даже если эти события в действительности выполняются не по порядку (обычно для оптимизации потока программы). Это включает заказ события, основанные на потенциале причинно-следственная связь пар событий в параллельной системе, особенно асинхронный распределенные системы. Его сформулировал Лесли Лэмпорт.^[1] В частности, в Java случается раньше Отношение является гарантией того, что память, в которую записывается оператор A, видна оператору B, то есть этот оператор A завершает свою запись до того, как оператор B начинает чтение.[1]

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

• Если события ${ Displaystyle а ;}$ и ${ displaystyle b ;}$ происходят в одном процессе, ${ Displaystyle от а до Ь ;}$ если наступление события ${ Displaystyle а ;}$ предшествовало наступлению события ${ displaystyle b ;}$.
• Если событие ${ Displaystyle а ;}$ отправка сообщения и события ${ displaystyle b ;}$ получение сообщения, отправленного в случае ${ Displaystyle а ;}$, ${ Displaystyle от а до Ь ;}$.

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

Как и все строгие частичные заказы, отношение "произошло до" переходный, иррефлексивный и антисимметричный, то есть:

• ${ displaystyle forall a, b, c}$, если ${ Displaystyle от а до Ь ;}$ и ${ Displaystyle от б до с ;}$, тогда ${ Displaystyle от до с ;}$ (транзитивность). Это означает, что для любых трех событий ${ displaystyle a, b, c}$, если ${ displaystyle a}$ случилось раньше ${ displaystyle b}$, и ${ displaystyle b}$ случилось раньше ${ displaystyle c}$, тогда ${ displaystyle a}$ должно было случиться раньше ${ displaystyle c}$.
• ${ displaystyle forall a, a nrightarrow a}$ (нерефлексивность). Это означает, что перед собой не может произойти никакое событие.
• ${ displaystyle forall a, b,}$ куда ${ displaystyle a neq b}$, если ${ displaystyle от до b}$ тогда ${ displaystyle b nrightarrow a}$ (антисимметрия). Это означает, что для любых двух различных событий ${ displaystyle a, b}$, если ${ displaystyle a}$ случилось раньше ${ displaystyle b}$ тогда ${ displaystyle b}$ не могло случиться раньше ${ displaystyle a}$.

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

Смотрите также

• Состояние гонки
• Модель памяти Java
• Отметки времени Лэмпорта
• Логические часы

Рекомендации