锁定自由链表插入

Question

假设有一个多线程应用程序，其中一个线程正在将元素插入循环链表，而多个工作线程正在遍历该链表以执行实际处理。

假设节点类型类似于：

struct Node
{
    // ...
    std::atomic< Node * > next;
};

并且在执行插入的方法中，有如下代码片段：

auto newNode = new Node( ); // (A)

newNode->next.store( previousNode->next.load( std:memory_order_relaxed ) ,
    std::memory_order_relaxed ); // (B)

previousNode->next.store( newNode , std::memory_order_relaxed ); // (C)

其中 previousNode 已被确定为列表中的 newNode 之前。

工作线程以类似于此的方式遍历列表：

// ...
while ( true )
{
    ProcessNode( * currentNode );
    currentNode = currentNode.next.load( std::memory_order_relaxed );
}

在 (A) 行刚刚创建的节点被工作线程跳过，直到它的前一个节点在 (C) 中被更新，这没有问题。

这样的设计有什么问题吗？我担心在汇编级别为 (B) 和 (C) 生成的代码可能是这样的：

LOAD( R1 , previousNode->next ) // (1) loads previousNode->next into register R1
WRITE( newNode->next , R1 ) // (2) writes R1 to newNode->next
WRITE( previousNode->next , newNode ) // (3) writes newNode to previousNode->next

然后一些优化可以将其重新排序为：

LOAD( R1 , previousNode->next ) // (1)
WRITE( previousNode->next , newNode ) // (3)
WRITE( newNode->next , R1 ) // (2)

这会破坏工作线程，因为它现在可以在其 next 成员初始化之前访问 newNode。

这是合理的担忧吗？标准对此有何规定？

Answer 1

是的，这是合理的担忧。宽松的内存顺序不会强制执行栅栏，它只是保证操作的原子性。代码可以由编译器重新排序，或者，为了达到类似的效果，通过 CPU 本身，或者，为了达到非常相似的效果，通过在 CPU.

上使用的缓存重新排序

您选择放宽顺序有什么实际原因吗？我实际上还没有看到该订单的任何合法用途。

Answer 2

您有合理的顾虑。

正如您所说，编译器可以合法地 re-order 您的商店：

auto temp = previousNode->next.load( std:memory_order_relaxed )
previousNode->next.store( newNode , std::memory_order_relaxed ); // (C)
newNode->next.store(  temp, std::memory_order_relaxed ); // (B)

您现在已经在其值被初始化之前插入了您的节点！这是否会发生是一个错误的问题。编译器这样做是完全合法的。

这里有一个 weakly-ordered CPU 可以做同样事情的例子：

auto temp = previousNode->next.load( std:memory_order_acquire );
// previousNode->next is now hot in cache

newNode->next.store( temp, std::memory_order_release); // (B)
// Suppose newNode is in the cache, but newNode->next is a cache miss

previousNode->next.store( newNode , std::memory_order_release ); // (C)
// while waiting for cache update of newNode->next, get other work done.
// Write newNode into previousNode->next, which was pulled into the cache in the 1st line.

这不会发生在 x86 上，因为它有总商店订单。但是，ARM...您在其值初始化之前再次插入了您的节点。

最好坚持 acquire/release。

auto temp = previousNode->next.load( std:memory_order_acquire );
newNode->next.store( temp, std::memory_order_release); // (B)
previousNode->next.store( newNode , std::memory_order_release ); // (C)

relavent 版本是 C 行，因为它阻止 B 行在它之后移动。 B 行对第 1 行有数据依赖性，因此实际上，它不会被 re-ordered。但是对第 1 行使用 acquire，对第 B 行使用 release，因为它在语义上是正确的，它不会伤害任何东西，并且它可能会阻止一些模糊的系统或未来的优化破坏你的代码。

锁定自由链表插入

Lock free linked list insert

c++

multithreading

concurrency

atomic

lock-free