获取发布内存顺序与顺序一致性不同的实际示例是什么？

Question

显然,顺序一致的原子操作的有效可观察行为与有效C++程序中的仅获取释放操作不同.定义在C++标准(自C++ 11以来)或此处给出.

但是,我从来没有遇到过一个算法或数据结构的真实例子,其中获取 - 释放语义不足并且需要顺序一致性.

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

注意,即使std::mutex不保证顺序一致性.

Answer 1

彼得森的算法是一个需要顺序一致性的例子.

在互斥体之前的日子里,算法用于给单个线程访问受保护区域.该算法仅适用于2个线程,每个线程管理一个表示访问受保护区域的意图的标志.如果两者都在(大约)同时设置标志,则两者都将退避并再次尝试.真正的算法更先进,因为它使用'turn'标志来管理公平访问,但是为了显示seq/cst和acq/rel之间的区别,这不是必需的.

下面是Peterson算法的一个易于编译的简化版本,它实际上表明如果使用弱于顺序一致性的算法,则算法会被破坏.有趣的是,即使在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();
}