Почему для синхронизации Dekker недостаточно С++ 11 capture_release?

Сбой синхронизации в стиле Dekker обычно объясняется переупорядочением инструкций. I.e, если мы пишем

atomic_int X;
atomic_int Y;
int r1, r2;
static void t1() { 
    X.store(1, std::memory_order_relaxed)
    r1 = Y.load(std::memory_order_relaxed);
}
static void t2() {
    Y.store(1, std::memory_order_relaxed)
    r2 = X.load(std::memory_order_relaxed);
}

Затем нагрузки могут быть переупорядочены с помощью магазинов, что приведет к r1==r2==0.

Я ожидал, что забор_объемки будет использоваться для предотвращения такого переупорядочения:

static void t1() {
    X.store(1, std::memory_order_relaxed);
    atomic_thread_fence(std::memory_order_acq_rel);
    r1 = Y.load(std::memory_order_relaxed);
}
static void t2() {
    Y.store(1, std::memory_order_relaxed);
    atomic_thread_fence(std::memory_order_acq_rel);
    r2 = X.load(std::memory_order_relaxed);
}

Нагрузка не может быть перемещена над ограждением, и магазин не может быть перемещен ниже забора, поэтому следует предотвратить плохой результат.

Однако эксперименты показывают, что r1==r2==0 все еще может возникать. Есть ли объяснение, основанное на переупорядочении? Где ошибка в моих рассуждениях?

Ответы

Ответ 1

Как я понимаю (в основном из чтения Jeff Preshings blog), atomic_thread_fence(std::memory_order_acq_rel) предотвращает любые переупорядочивания, кроме StoreLoad, т.е. он по-прежнему позволяет изменить порядок a Store с последующим Load. Однако это именно переупорядочение, которое должно быть предотвращено в вашем примере.

Более точно, atomic_thread_fence(std::memory_order_acquire) предотвращает переупорядочение любого предыдущего Load с любым последующим Store и любым последующим Load, то есть предотвращает переупорядочивание LoadLoad и LoadStore через ограждение.

An atomic_thread_fence(std::memory_order_release) предотвращает переупорядочение любого последующего Store с любым предыдущим Store и любым предыдущим Load, т.е. предотвращает переупорядочивание LoadStore и StoreStore через забор.

An atomic_thread_fence(std::memory_order_acq_rel) затем предотвращает объединение, т.е. предотвращает LoadLoad, LoadStore и StoreStore, что означает, что все еще может быть только StoreLoad.

Ответ 2

memory_order_acq_rel фактически ведет себя так же, как приобретать и освобождать забор в одном и том же месте. Но проблема в том, что они не предотвращают все возможное переупорядочение, они предотвращают переупорядочивание загружаемых или ранее сохраненных магазинов вокруг ограждения. Таким образом, предыдущие нагрузки и последующие магазины все еще могут проходить через забор.

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

memory_order_seq_cst отлично работает для синхронизации Dekker, поскольку он предотвращает любое переупорядочение по этой точке. Например, tbb использует его алгоритм Деккера и mfence для кражи работы.

Для лучшего понимания см. великолепную анимацию из лекции Херба Саттера " Atomic < > weapon 1/2", в 0:43.