我需要添加内存屏障到FIFO入队操作吗？

Question

我正在使用链表实现一个非锁定的FIFO。

FIFO的Enqueue基本上是：

void Enqueue(CNode node)
{
  m_tail->m_next = node;

  // Do I need a memory barrier here?

  m_tail = node;
}

我想知道在单线程情况下是否需要添加内存屏障（即，编译器/处理器是否可以重新排列上述两行的顺序？）。如果是多线程，则会怎样（即，像单读单写的情况那样简单）？

编辑：根据这里，这是一种数据反依赖的情况，语句不应该被重新排序。所以我假设CPU应该总是按给定的顺序访问内存。是这样吗？

- Eric Z

---

我怀疑你的代码已经不是线程安全的了。当你的线程在这两个语句之间被暂停任意时间会发生什么？另一个线程安全地覆盖你的工作吗？其中一半有意义而另一半没有意义吗？无锁链表更新通常有一个CAS循环。 - GManNickG

@GManNickG，我提到的多线程是指“单读单写”。 - Eric Z

@EricZ：我的观点仍然成立。 语句之间的状态是否可以被消耗？ - GManNickG

@GManNickG，如果您的意思是说读者可能同时更新同一节点，那不是我的问题。我添加了一个哨兵节点来防止读者、写者同时访问同一节点。但是，无论如何，我的关注点是编译器 / CPU 何时重新排列这两个语句，如果会的话。 - Eric Z

Answer 1

编译器不能更改你的 m_tail 和 m_tail->next 赋值操作的顺序，以使得在设置 m_tail->next 之前就已经将 node 赋给了 m_tail。然而，在多线程解决方案中，你可能需要担心以下问题：

temp = m_tail;
m_tail = node;
temp->next = node;
node->next = NULL; 

通过使用内存屏障，编译器和/或处理器必须在写入m_tail = node;之前完成m_tail->next = node;（以及node->next = NULL;）。但是，这是否足以保证正确执行并不确定，这取决于另一端读取代码的操作。

- Mats Petersson

---

即使编译器没有重新排列这两个赋值语句的顺序，是否有保证其他线程也会按照这个顺序看到这些赋值？它们可能在不同的核心上运行，其本地缓存的更新顺序也不同等。或者这种可能性可以通过某种方式排除吗？ - jogojapan

数据依赖关系将按顺序获取CPU提交的内存访问。这是真的吗？ - Eric Z

现代编译器和现代CPU按照“对它们有意义的顺序”执行操作。例如，处理器会乱序执行指令，因为数据是如何从内存中获取的。编译器可能会发现以不同方式使用寄存器可以使代码更有效率。我承认像上面我的例子那样的情况并不是非常普遍，但是根据寄存器中的内容（以及有多少个“空闲”寄存器），编译器可能会决定重新排列存储和加载以使寄存器的使用更好。考虑到CNode和Enqueue的构造函数是内联的... - Mats Petersson