Каков практический пример, где порядок получения памяти релиза отличается от последовательной последовательности?

Question

Очевидно, что последовательные согласованные атомарные операции отличаются по своему действительному наблюдаемому поведению от операций только с получением-выпуском в действительной программе на C++. Определения даны в стандарте C++ (начиная с C++11) или здесь.

Однако я никогда не сталкивался с реальным примером алгоритма или структуры данных, в которых семантика получения-выпуска недостаточна и необходима последовательная согласованность.

Что может быть практическим примером алгоритма или структуры данных реального мира, где требуется последовательная согласованность и недостаточно порядка памяти для получения и выпуска?

Обратите внимание, что даже std::mutex не гарантирует последовательную последовательность.

Answer 1

Алгоритм Петерсона является примером чего-то, что требует последовательной последовательности.

Во времена, предшествующие мьютексам, алгоритм использовался, чтобы дать одному потоку доступ к защищенной области. Алгоритм работает только с 2 потоками, каждый из которых управляет флагом, который выражает намерение получить доступ к защищенной области. Если оба установят флаг в (примерно) в одно и то же время, оба отступят и попытаются снова. Реальный алгоритм более продвинутый, так как он использует флаг поворота для управления честным доступом, но чтобы показать разницу между seq/cst и acq/rel, в этом нет необходимости.

Ниже приведена готовая к компиляции упрощенная версия алгоритма Петерсона, которая фактически показывает, что алгоритмы нарушаются, если используется нечто более слабое, чем последовательная согласованность. Интересно, что это не работает даже на X86, поскольку эта платформа позволяет переупорядочивать загрузку магазина.
Проблема с переупорядочением в хранилище состоит в том, что оба потока могут выразить свое намерение получить доступ к защищенной области, установив свои me флаг для trueв то время как оба читают false от him флаг (поскольку значение еще не было распространено в оба потока) и введите защищенную область. Это невозможно при последовательной последовательности.

С gccЯ должен был скомпилировать -O3 оптимизации, чтобы иметь assert огонь, с clang в этом не было необходимости. Оба компилятора используют разные подходы для реализации последовательной согласованности.

#include <thread>
#include <atomic>
#include <assert.h>

std::atomic<bool> flag1{false};
std::atomic<bool> flag2{false};

std::atomic<int> counter{0};

// Change these to memory_order_seq_cst to fix the algorithm
static const auto store_ordering = std::memory_order_release;
static const auto load_ordering  = std::memory_order_acquire;

void busy(int n)
{
    auto &me  = (n==1) ? flag1 : flag2;
    auto &him = (n==1) ? flag2 : flag1;

    for (;;)
    {
        for (;;)
        {
            me.store(true, store_ordering);
            if (him.load(load_ordering) == false)
            {
                // got the 'lock'
                break;
            }

            // retention, no wait period -> busy loop
            me.store(false, store_ordering);
        }

        int tmp = counter.fetch_add(1, std::memory_order_relaxed);
        assert(tmp == 0);

        /*
         * critical area
         */

        tmp = counter.fetch_sub(1, std::memory_order_relaxed);
        assert(tmp == 1);

        me.store(false, store_ordering);
    }
}


int main()
{
    std::thread t1{busy, 1};
    std::thread t2{busy, 2};

    t1.join();
    t2.join();
}