这种无锁的 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是最后更改的链接。所以改变后，其他线程（除了reminder）都不能访问该节点或其前一个节点next链接。这个推理有效还是我遗漏了什么？

---

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

• 该列表不是线性可遍历的，因此从这个角度来看，不一致的列表状态不是问题。

• 如果删除插入器要修改（以添加反向链接）但尚未修改的节点

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

• 在这些条件下搬迁安全吗？
  • 只有 1 个拆卸线
  • 删除器有一个单独的节点工作列表用于删除
  • 节点只有在插入阶段完全完成后才能添加到工作列表中

Answer 1

TL:DR：单独插入是可以的，具体取决于读者的行为（不会长期损坏），但如果没有锁定或更复杂的操作，删除可能是不可能的，并且对于这种简单的插入算法来说绝对是一个阻碍。

更新： @davidhigh（在评论中）发现了链接的潜在问题->prev，即使在某些并发插入尘埃落定之后，某些节点也可能从向后遍历顺序中丢失。

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

使用 CAS 执行此操作（针对较早某个时刻读取的值...？）可能会检测到此问题，并且在失败的情况下，我们可能会向前遍历列表以查找last? 这很重要，我没有答案。

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

m68k曾经有DCAS，但目前主流CPU架构没有它。ISO C++11 不会公开 DCAS 操作，std::atomic因为如果不使所有操作都成为atomic<T>非无锁，则无法在没有该操作的硬件上模拟它。除了具有事务内存的硬件外，可在 Intel 的一些最新 x86 CPU（例如 Broadwell 及更高版本）上使用，但在 AMD 上不可用。已经有一些工作将 TM 语法添加到 C++ 中，请参阅https://en.cppreference.com/w/cpp/language/transactional_memory

当然，如果没有事务内存或 DCAS 之类的东西，观察者也不可能以原子方式同时观察两个位置。 因此，任何读取列表的线程都需要预期列表会从它们下面发生变化，特别是如果列表也应该支持删除的话。

在发布之前在新节点（尚未发布到其他线程）中设置指针显然是好的，并且您正在这样做。 在 CAS 尝试发布这些新节点之前，first->prev并且都已正确设置。last->nextCAS 具有顺序一致性内存排序，因此它确保那些先前的存储在其本身之前对其他线程可见。（因此，为了提高效率，那些“私有”存储也可能是 std::memory_order_relaxed ）。

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

如果一个线程向前遍历并且依赖于能够通过跟随 a 返回.prev（而不是在局部变量中记住它自己的前一个），这可能看起来就像新节点已被再次删除。它可以找到一个.prev指向head. 这是一个人为的示例，因为如果您希望能够再次找到它，尤其是在无锁列表中，那么简单地记住您的前一个节点通常会更有效。但也许存在非人为的情况，例如一个线程向前遍历，另一个线程向后遍历，并且可能直接或间接交互，在这种情况下会出现不一致的情况。

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

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

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

如果不进行删除，对 a 的每个挂起写入.prev都会有一个有效的目的地，并且该目的地是没有其他线程想要写入的节点。 无锁单链表插入很容易，并且转发列表（链接.next）始终是最新的。

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

或者确实如此？我认为在同一点进行多次插入可以在完成向后 (->prev存储) 之前成功其前向 CAS，因此我们毕竟不主张节点的独占所有权。

循环do{}while(!CAS())是一个很好的习惯用法，通常可以简化代码。我削弱了其他操作的内存排序，尤其是第一个和最后一个的私有操作，因为要求编译器在存储其他线程还看不到的元素后使用慢速屏障是低效的。在 x86 上，release-store 是“免费的”（没有额外的障碍），而 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
}

在 Godbolt 编译器资源管理器上，这会使用 0mfence条指令（而不是 3 条指令）针对 x86 进行编译。（asm 的其余部分实际上是相同的，包括那个。）因此，在无争用的无 RFO 情况下（例如，从同一核心重复插入），它可能会快 4 倍左右。或者更好，因为实际上比 Intel CPU 上的前缀还要慢。lock cmpxchgmfencelock

另外，do{}while(!CAS)最终存储完全在循环之外可以说更容易让人们立即阅读和查看逻辑。

拆除是一个巨大的并发症

我不知道在有待插入的情况下如何安全地删除。如果删除插入器要修改（以添加反向链接）但尚未修改的节点，则该范围的节点将永远从反向列表中丢失。

（另外，如果您回收该节点的内存，插入器的存储就会踩到某些东西。）

它会使前进列表和后退列表不同步。 我看不出没有 DCAS（或事务内存，它是 DCAS 的超集）来解决这个问题的方法。不过，我不是无锁列表专家，所以也许有一个技巧。

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

如果您有插入器/删除器锁（多个插入器/单个删除器，与读取器/写入器锁完全相同），则可以确保在执行删除时没有挂起的插入。 但仍然允许无锁插入。也许将锁放在与 相同的缓存行中head，因为插入线程总是需要修改它 和head。或者也许不是，因为如果核心有时在获取锁定之后但在将修改提交到head.