8

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

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

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

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

（如果 Dekker 算法是一个糟糕的选择，如果可能，请选择另一个内存屏障可以成功实现正确同步的互斥算法。）

4

3 回答 3

5

你是对的，内存屏障不能确保读取看到最新的值。它所做的是在单个线程上和线程之间强制执行操作之间的排序。

例如，如果线程 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 很可能会为 读取一个陈旧的值 (0) flag，因此您无法保证为其他变量读取的任何值。

因此，栅栏可用于在 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上的博客条目

于 2010-07-26T21:24:55.603 回答
1

假设您在每条语句之后都放置了一个加载和存储屏障，此外您还确保编译器不会重新排序您的存储。在任何合理的架构上，这不会提供严格的一致性吗？Dekker 的作品是关于顺序一致的架构。顺序一致性是比严格一致性更弱的条件。

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

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

所以这是我的主张。如果您有一个可用的写屏障和一个读屏障，并且缓存在 CPU 之间是一致的，那么您可以通过在每条指令之后刷新写入（存储栅栏）并在每条指令之前刷新推测（读取栅栏）来轻松地使所有代码顺序一致操作说明。所以我声称你不需要原子来做你正在谈论的事情，你可以只用 Dekker's 做你需要的事情。你肯定不想。

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

于 2010-07-24T20:00:55.227 回答
0

一些障碍（例如 powerpc isync 和 ia64 上的 .acq 加载）也对后续加载有影响。即：如果由于预取而在 isync 之前加载可用，则必须丢弃它。如果使用得当，这可能足以使 Dekker 的算法在弱内存模型上工作。

您还可以使用缓存失效逻辑。如果您知道由于 isync 之类的负载是当前负载，并且如果另一个 cpu 触摸它，数据的缓存版本将失效，这是否足够？

抛开有趣的问题不谈，Dekker 的算法实际上是愚蠢的。您将希望对任何实际应用程序使用原子硬件接口和内存屏障，因此专注于如何使用原子修复 Dekker 对我来说似乎不值得；）

于 2010-07-23T17:07:09.370 回答