内存屏障与互锁操作

Question

我正在努力提高我对记忆障碍的理解。假设我们有一个弱内存模型，并采用了Dekker's algorithm。是否有可能通过添加内存屏障使其在弱内存模型下正常工作？

我认为答案是一个令人惊讶的不。原因(如果我是正确的)是，尽管可以使用内存屏障来确保读操作不会移过另一个读操作，但它不能确保读操作看不到过时的数据(比如缓存中的数据)。因此，它可以在过去的某个时间看到临界区被解锁(根据CPU的缓存)，但在当前时间，其他处理器可能会将其视为锁定。如果我的理解是正确的，那么必须使用互锁操作，例如通常称为测试和设置或比较和交换的操作，以确保在多个处理器之间的内存位置上的值同步一致。

因此，我们可以正确地期望没有弱内存模型系统只提供内存屏障吗？系统必须提供像测试和设置或比较和交换这样的操作才能有用。

我意识到流行的处理器，包括x86，提供的内存模型比弱内存模型强得多。请将讨论集中在弱内存模型上。

(如果Dekker的算法是一个糟糕的选择，请选择其他互斥算法，如果可能的话，这种算法的内存屏障可以成功地实现正确的同步。)

Answer 1

您说得对，内存屏障不能确保读取器看到最新的值。它所做的是在操作之间强制排序，无论是在单个线程上还是在线程之间。

例如，如果线程A执行一系列存储，然后在最终存储到标志位置之前执行释放屏障，而线程B从标志位置读取，然后在读取其他值之前执行获取屏障，则其他变量将具有由线程A存储的值：

// initially x=y=z=flag=0

// thread A
x=1;
y=2;
z=3;
release_barrier();
flag=1;

// thread B
while(flag==0) ; // loop until flag is 1
acquire_barrier();
assert(x==1);  // asserts will not fire
assert(y==2);
assert(z==3);

当然，您需要确保对flag的加载和存储是原子的(只要变量适当地对齐，这些简单的加载和存储指令就位于最常见的CPU上)。如果没有线程B上的while循环，线程B可以很好地读取flag的陈旧的值(0)，因此您无法保证为其他变量读取的任何值。

因此，栅栏可用于在Dekker算法中强制同步。

下面是一个使用C++ (使用C++0x原子变量)实现的示例：

std::atomic<bool> flag0(false),flag1(false);
std::atomic<int> turn(0);

void p0()
{
    flag0.store(true,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_seq_cst);

    while (flag1.load(std::memory_order_relaxed))
    {
        if (turn.load(std::memory_order_relaxed) != 0)
        {
            flag0.store(false,std::memory_order_relaxed);
            while (turn.load(std::memory_order_relaxed) != 0)
            {
            }
            flag0.store(true,std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_seq_cst);
        }
    }
    std::atomic_thread_fence(std::memory_order_acquire);

    // critical section


    turn.store(1,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release);
    flag0.store(false,std::memory_order_relaxed);
}

void p1()
{
    flag1.store(true,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_seq_cst);

    while (flag0.load(std::memory_order_relaxed))
    {
        if (turn.load(std::memory_order_relaxed) != 1)
        {
            flag1.store(false,std::memory_order_relaxed);
            while (turn.load(std::memory_order_relaxed) != 1)
            {
            }
            flag1.store(true,std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_seq_cst);
        }
    }
    std::atomic_thread_fence(std::memory_order_acquire);

    // critical section


    turn.store(0,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release);
    flag1.store(false,std::memory_order_relaxed);
}

有关完整的分析，请参阅我的博客文章：http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

假设您在每条语句之后放置了一个加载和存储屏障，并且确保编译器不会对您的存储进行重新排序。在任何合理的架构上，这难道不能提供严格的一致性吗？Dekker的工作在顺序一致的架构上。顺序一致性是比严格一致性更弱的条件。

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

即使在具有弱一致性模型的CPU上，您仍然期望高速缓存一致性。我认为事情脱轨的地方是存储缓冲区和推测读取的行为，以及哪些操作可用于刷新存储写入和使推测读取无效。如果没有可以使推测读取无效的加载围栏，或者没有刷新存储缓冲区的写入围栏，那么除了不能实现Dekker之外，您还不能实现互斥！

这就是我的观点。如果您有一个写屏障和一个读屏障，并且CPU之间的高速缓存是一致的，那么您可以通过在每条指令之后刷新写入(存储围栏)，并在每条指令之前刷新推测(读取围栏)来使所有代码按顺序保持一致。所以我声称你不需要原子来做你正在谈论的事情，你可以只用Dekker来做你需要的事情。当然你不会想这么做的。

顺便说一句，Corensic，我工作的公司，编写了调试并发问题的很酷的工具。查看http://www.corensic.com。

Answer 3

一些屏障(例如powerpc isync和ia64上的.acq加载)也会对后续加载产生影响。即:如果加载在isync之前由于预取而可用，则必须将其丢弃。如果使用得当，这可能足以使Dekker的算法在弱内存模型上工作。

您还可以让缓存无效逻辑为您工作。如果您知道由于isync之类的原因，您的加载是当前的，并且如果另一个cpu接触到数据的缓存版本，那么它就会失效，这就足够了吗？

抛开有趣的问题不谈，Dekker的算法在所有实用目的上都是愚蠢的。你会想要在任何实际的应用程序中使用原子硬件接口和内存屏障，所以专注于如何用原子修复Dekker的问题对我来说似乎不值得；)