这个无锁双向链表插入操作是安全的吗？

Question

这个无锁双向链表插入操作是安全的吗？

c++concurrencylinked-listatomiclock-free

3

我需要实现一个无锁（lock-free）算法，将一个子列表插入到双向链表的头部。该链表有一个哑节点作为头部，每个线程都试图在该节点之后插入它的一部分。这个设计对我来说看起来没问题，但是我没有足够的专业知识来证明它是否正确。

struct Node {
  std::atomic<Node*> next;
  std::atomic<Node*> prev;
};
Node head;

// concurrently insert `first`..`last` sublist after `head`
void insertSublist(Node* first, Node* last) {
  first->prev = &head;
  Node* current_next = head.next;

  while (true) {
    last->next = current_next;
    if (head.next.compare_exchange_weak(current_next, first)) {
      current_next->prev = last;
      return;
    }
  }
}

我需要在以下情况下验证这个设计：

变体1

不执行任何列表删除操作，所有线程都只是循环插入。

变体2

有1个线程以随机顺序从列表中删除节点，但它永远不会删除紧接在头节点后面的节点。

for (auto* node : nodes_to_be_removed) {
  if (node->prev == &head)
    continue;
  // perform removal 
}

当插入完成后，node->prev是最后一个被更改的链接。因此，在它被更改之后，除了移除者之外，没有其他线程可以访问节点或其前一个节点的next链接。这种推理是否有效，还是我遗漏了什么？

@peter-cordes回答后的一些澄清。

该列表不可线性遍历，因此从这个角度来看不一致的列表状态不是一个问题。
如果您删除了插入器将要修改（以添加向后链接）但尚未修改的节点

我希望检查node->prev == &head可以防止这种情况。 是真的吗？
在这些条件下，移除是否安全？
- 只有1个移除者线程
- Remover有一个单独的节点工作列表用于删除
- 只有在完全完成其插入阶段后才能将节点添加到工作列表中

- Viacheslav Kroilov

但它永远不会删除紧跟在头节点后面的节点 - 如果它是列表中唯一的节点呢？ - Aconcagua

还有一个虚拟的尾节点，所以这不是问题。 - Viacheslav Kroilov

1

我认为检查 node->prev == &head 可以防止这种情况发生。这是真的吗？哦，是的，我想是这样的。尚未修改的元素都将其 prev 指针指向 head。这意味着对于部分插入的元素，remove 操作会失败，而我们肯定只能在头部插入。（否则，我们将失去避免挂起修改的方法。） - Peter Cordes

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

TL:DR: 插入操作还算可以，具体取决于读者的操作（没有长期损坏），但是删除操作可能需要锁定或更高级的技术才能实现，对于这种简单的插入算法来说，绝对是一个难以解决的问题。

更新：@davidhigh在评论中指出了->prev链接存在潜在问题，即使在一些并发插入之后，某些节点可能仍然缺失。

否则，如果另一个写入者在CAS和存储到current_next -> prev之间插入子列表，这个新的子列表在向后遍历时就永远丢失了，不是吗？

使用CAS（针对早期读取的值...？）进行此操作可能会检测到此问题，在失败的情况下，我们可以通过向前遍历列表查找last来解决吗？这是一个非平凡的问题，我没有答案。

这是一个双向链表，因此插入操作不可避免地需要修改其他线程可能已经看到的两个内存位置：head.next和旧第一个节点中的.prev指针。除非硬件有DCAS（双重CAS，同时处理两个不连续的位置），否则无法原子+无锁地完成。正如维基百科文章所说，它使得无锁双向链表变得容易。

m68k曾经拥有DCAS，但目前没有任何主流CPU架构支持它。ISO C++11通过std::atomic不公开DCAS操作，因为如果在没有DCAS的HW上模拟它，则必须使所有atomic<T>非锁定。除非在某些最近的Intel x86 CPU上提供了事务性内存（例如Broadwell及更高版本），但AMD不支持。已经进行了一些工作，以添加用于C++的TM语法，请参见https://en.cppreference.com/w/cpp/language/transactional_memory。

当然，如果没有事务性内存或类似的DCAS，观察者也不可能同时原子地观察两个位置。因此，任何读取列表的线程都需要预期它在发生变化，特别是如果该列表还应支持删除操作。

在发布新节点之前设置其内部指针（尚未发布到其他线程）显然是很好的做法，而您正在这样做。first->prev和last->next在尝试CAS发布这些新节点之前都已正确设置。CAS具有顺序一致的内存排序，因此它确保那些先前的存储对其他线程可见，然后才对自己可见。（因此，为了提高效率，那些“私有”存储可以是std::memory_order_relaxed）。

在修改.prev指针之后再修改head，这种方式是有道理的。你实际上是先向前发布，然后再向后发布。但请记住，线程可能在任何时候睡眠很长时间，因此不能百分之百地假定这将始终是短暂的不一致性。想象一下，在函数内部的任何点停止一个线程，并单步执行，而其他线程则运行。在这种情况下，只有两个有趣的操作，CAS和对旧的第一个非虚拟节点的无条件存储。

如果一个线程正在向前遍历，并依赖于通过跟随.prev（而不是记住其自己的前一个节点在本地变量中）来返回，那么对它来说，新节点似乎已被删除。它可以找到指向head的.prev。这是一个人为的例子，因为如果您想要能够再次找到它，特别是在无锁列表中，通常更有效地记住您的上一个节点。但也许有非人为的情况，比如一个线程向前遍历，另一个线程向后遍历，也许直接或间接地相互作用，其中会出现不一致性。

只要所有线程都同意修改顺序，我认为至少对于前向链接而言插入本身是安全的。只在头部进行插入使其更容易验证，但我认为允许任意插入点仍然是安全的。

您当前的代码看起来对于同时插入是安全的（假设没有删除）。前向列表可以比后向列表更长（可能有多个插入到后向列表中），但一旦它们全部完成，列表将保持一致。

更正一下，前向列表将保持一致，但后向列表可能会失去节点或子列表的跟踪。

如果没有删除，每个待处理的写入到.prev都有一个有效的目标，并且该目标是其他线程不想写入的节点。无锁单向链表插入很容易，而前向列表（.next链接）始终是最新的。

因此，每个插入操作都会“声明”一个节点，将其用作反向列表中插入点，其中其对current_next->prev的存储变得可见。

或者呢？我认为在同一点上进行多次插入可以在任何一个节点完成其后向CAS之前成功地完成其前向CAS（->prev存储），因此我们并没有声称对节点拥有独占所有权。

一个 do{}while(!CAS()) 循环是一个不错的习惯用法，通常可以简化代码。我削弱了其他操作的内存顺序，特别是对于 first 和 last 的私有操作，因为要求编译器在存储到其他线程尚未看到的元素后使用缓慢的屏障是低效的。在 x86 上，release-stores 是“免费”的（没有额外的屏障），而 seq-cst stores 则更加昂贵。（在无争用情况下）在 x86 上进行 seq-cst 存储的成本与原子读取-修改-写入大致相同。

// no change in logic to yours, just minimize memory ordering
// and simplify the loop structure.
void insertSublist(Node* first, Node* last)
{
  first->prev.store(&head, std::memory_order_relaxed);
  Node* current_next = head.next.load(std::memory_order_relaxed);

  do {
    // current_next set ahead of first iter, and updated on CAS failure
    last->next.store(current_next, std::memory_order_relaxed);
  }while (!head.next.compare_exchange_weak(current_next, first));
   // acq_rel CAS should work, but leave it as seq_cst just to be sure.  No slower on x86

  current_next->prev.store(last, std::memory_order_release);  // not visible before CAS
}

这个可以在x86上编译，而你的则需要3个mfence指令，在Godbolt编译器资源管理器上（其余的汇编完全一致，包括lock cmpxchg）。所以在无竞争且没有远程写入缓存（RFO）的情况下（例如从同一核心进行重复插入），它可能会快4倍左右。甚至更好，因为mfence在英特尔CPU上比lock前缀还要慢。

此外，do{}while(!CAS) 循环中的最终存储完全在循环之外，这可以说更容易让人阅读并立即看到逻辑。

移除是一个巨大的问题

如果您有待处理的插入操作，我不知道如何安全地进行删除。如果您删除了一个插入者将要修改（添加反向链接）但尚未修改的节点，则该节点范围将永远从后向列表中消失。

（此外，如果您回收该节点的内存，则插入者的存储会覆盖某些内容。）

这将使前向和后向列表不同步。我没有看到解决此问题的方法，除非使用DCAS（或事务性内存，它是DCAS的超集）。不过，我不是无锁dlist专家，也许有什么诀窍。

可能甚至多个同时删除者也是一个问题，因为您可能会遇到对另一个线程将要（或已经）删除的节点进行待处理修改的情况。或者对一个节点进行多个待处理修改，没有办法确保正确的修改最后完成。

如果你有插入/删除锁（多个插入器/单个删除器，就像读写锁一样），你可以确保在执行删除操作时没有未处理的插入。但仍允许无锁插入。也许将锁放在与`head`相同的高速缓存行中，因为插入线程始终需要同时修改它和`head`。也许不是这样，因为如果核心在获取锁之后但在提交对`head`的修改之前失去了该行的所有权，则可能会导致该行的争用增加。