c++ - 这种无锁的dlist插入安全吗？

Question

我需要在双向链接列表的开头实现子列表的无锁插入。该列表有一个虚拟头，因此每个线程都尝试在头节点之后插入其部分。这种设计对我来说似乎还可以，但是，我没有足够的专业知识来证明它。

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回答后的一些说明。

列表不是线性可遍历的，因此从此 Angular 来看，不一致的列表状态不是问题。

If you remove a node that an inserter was going to modify (to add the backward link) but hasn't yet

我希望检查node->prev == &head可以防止这种情况。是真的吗

在这种情况下清除安全吗？

只有1个卸妆线程

Remover有一个单独的节点工作 list ，用于删除

只有在节点的插入阶段完全完成后，才能将节点添加到工作 list 中。

Answer 1

TL:DR :取决于读者的操作(没有长期损坏)，仅插入一项是可以的(但不能进行长期删除)，但是如果没有锁定或更加复杂的话，则删除是不可能的，并且对于这种简单的插入算法而言，无疑是最出色的选择。

这是一个双向链接的列表，因此插入不可避免地需要修改其他线程已经可以看到的两个内存位置:head.next和旧的第一个节点中的.prev指针。 除非硬件具有DCAS (double-CAS, two separate non-contiguous locations at once)，否则无法原子+无锁地完成此操作。如Wikipedia文章所述，它使无锁的双向链接列表变得容易。

m68k在某一点上具有DCAS，但是目前没有主流的CPU体系结构。 ISO C++ 11不会通过std::atomic公开DCAS操作，因为您必须在没有将所有atomic<T>设为非锁定的情况下无法在没有该功能的硬件上进行模拟。除了具有事务性内存的硬件以外，英特尔(例如Broadwell和更高版本)在某些最近的x86 CPU上可用，但AMD不可用。在将TM的语法添加到C++方面已有一些工作，请参见https://en.cppreference.com/w/cpp/language/transactional_memory

当然，如果没有事务性内存或DCAS之类的东西，观察者不可能一次原子地观察两个位置。 因此，所有读取列表的线程都应期望它会从列表中更改出来，尤其是在该列表也应支持删除的情况下。

在发布之前在新节点(尚未发布到其他线程)中设置指针显然是一件好事，而您正在这样做。在CAS尝试发布这些新节点之前，first->prev和last->next都已正确设置。 CAS具有顺序一致性内存排序，因此可以确保以前的存储对其他线程而言是可见的，而不是它本身。 (因此，出于效率考虑，最好将这些“私有(private)”存储区设置为std::memory_order_relaxed)。

您选择在修改.prev之后修改旧优先的head指针很有意义。实际上，您首先要在正向发布，然后在反向发布。 但是请记住，线程在任何时候都可能长时间睡眠，因此假设这始终是暂时的不一致并不是100％安全的。 想象一下，在该函数内部的任何时候都停止在调试器中的一个线程，甚至是单步执行，而其他线程正在运行。在这种情况下，只有两个有趣的操作，CAS和无条件存储到旧的第一个非虚拟节点。

如果线程正在向前遍历，并且取决于能够通过遵循.prev来返回(而不是在局部变量中记住它自己的前一个)，则它看起来就像是再次删除了新节点。它可以找到指向.prev的head。这是一个人为的示例，因为如果您想再次找到它，通常记住一个上一个节点通常会更有效，特别是在无锁列表中。但是，也许存在一些非人为的情况，例如一个线程向前移动而另一个线程向后移动，并且可能直接或间接地进行交互，从而可以看到不一致的情况。

只要所有线程都同意修改顺序，我认为插入本身是安全的。仅在头部执行此操作就更易于验证，但我认为允许任意插入点仍然是安全的。

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

如果不删除，则对.prev的每个未决写操作都有一个有效的目的地，并且该目的地是其他线程都不想写入的节点。 无锁单链接列表的插入很容易，并且转发列表(.next链接)始终是最新的。

因此，每个插入操作在可见到current_next->prev的存储时，都会将其用作插入点的节点“声明”到反向列表中。
do{}while(!CAS())循环是一个很好的习惯用法，通常可以简化代码。我削弱了其他操作的内存顺序，尤其是在第一个操作和最后一个操作中，由于要求编译器在存储到其他线程看不到的元素之后使用慢速屏障效率低下，因此降低了它们的内存排序。在x86上，发布存储区是“免费的”(没有额外的障碍)，而seq-cst存储区则失去了更高的价格。 (在无竞争的情况下，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
}

这将使用零 mfence指令为x86编译，而不是您的 on the Godbolt compiler explorer 3指令。 (asm的其余部分实际上是相同的，包括一个 lock cmpxchg。)因此，在无竞争的无RFO的情况下(例如，从同一内核重复插入)，速度可能快4倍。或更好，因为 mfence实际上比Intel CPU上的 lock前缀还要慢。

此外，最终存储区完全位于循环外部的 do{}while(!CAS)可以使人们立即更容易阅读和看到逻辑。

去除是一个巨大的并发症

我看不到在等待插入时如何安全删除。如果您删除插入程序将要修改的节点(以添加向后链接)，但尚未删除，则该节点范围将永远从反向列表中丢失。

(此外，如果您回收该节点的内存，则插入程序的存储将继续执行操作。)

它将使前进和后退列表不同步。 如果没有DCAS(或事务性内存，这是DCAS的超集)，我看不到解决该问题的方法。不过，我不是无锁的dlist专家，所以也许有个窍门。

可能甚至有多个同时的删除器也是一个问题，因为您可能最终要对另一个线程将要删除(或已经删除)的节点进行修改。或对一个节点的多个待定修改，无法确保正确的修改最后完成。

如果您具有插入器/删除器锁(多个插入器/单个删除器，与读取器/写入器锁完全一样)，则可以确保进行删除时没有待处理的插入。 但仍允许无锁插入。也许将锁与 head放在同一缓存行中，因为插入线程将始终需要同时修改它和 head。也许不是，因为如果核心在获得锁定之后但在将其修改提交给 head之前有时失去了对该行的所有权，那么您可能最终会对该行产生更多争用。