获取释放内存顺序与顺序一致性的实际示例是什么？

Question

显然，连续一致的原子操作在其有效的可观察行为上不同于在有效的C++程序中仅获取-释放操作。定义在C++标准(自C++11)或这里中给出。

然而，我从来没有遇到过一个算法或数据结构的真实例子，在这种情况下，获取发布语义不足，并且需要顺序一致性。

什么是一个实际的例子，一个真实世界的算法或数据结构，其中需要顺序一致性和获取释放内存顺序是不够的？

注意，即使是不保证顺序一致性。

Answer 1

Peterson的算法就是一个需要顺序一致性的例子。

在互斥之前的日子里，algoritm被用来让一个线程访问一个受保护的区域。algoritm只使用2个线程，每个线程管理一个表示访问受保护区域的意图的标志。如果两者同时设置标志(大约)，则两者都会后退，然后再试一次。真正的算法更先进，因为它使用了一个“转身”标志来管理公平的访问，但是为了显示seq/cst和acq/rel之间的区别，这是不必要的。

下面是Peterson算法的一个准备编译的简化版本，它实际上表明，如果使用比顺序一致性更弱的方法，算法就会崩溃。有趣的是，即使在X86上也是如此，因为该平台允许重新排序存储负载。

存储负载重新排序的问题是，两个线程都可能表示希望通过将其me标志设置为true来访问受保护区域，而两个线程都从him标志读取false (因为该值尚未传播到两个线程)并进入受保护区域。这是不可能的序贯一致性。

使用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();
}