我需要在双链表的头中实现子列表的无锁插入。此列表有一个伪头，因此每个线程都会尝试在头节点的正后方插入其部分。这个设计对我来说似乎还可以，但是，我没有足够的专业知识来证明它
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
有一个线程，它以随机顺序从列表中删除节点，但它永远不会删除头部节点后面的节点。
for (auto* node : nodes_to_be_removed) {
if (node->prev == &head)
continue;
// perform removal
}
插入完成后，node->prev是最后更改的链接。因此，在它被更改后，除了remover之外，没有其他线程可以访问该节点或其前一个节点next链路。这个推理有效吗？还是我遗漏了什么？
在@peter cordes回答后的一些澄清
- 列表不是线性可遍历的，因此从这个角度来看，不一致的列表状态不是问题
如果你删除了一个插入器要修改的节点(添加反向链接)，但还没有
我希望检查
node->prev == &head可以防止这种情况这是真的吗- 在这种情况下清除是否安全？
- 只有一个拆卸器螺纹
- Remover有一个单独的用于删除的节点工作列表
- 只有在插入阶段完全完成后，才能将节点添加到工作列表中
TL:DR：根据阅读器的操作，单独插入是可以的(没有长期损坏)，但如果没有锁定或更复杂的操作，删除可能是不可能的，而且对于这个简单的插入算法来说，这绝对是一个亮点。
更新：@davidhigh(在评论中)发现了->prev链接的一个潜在问题，即使在一些并发插入尘埃落定之后，反向遍历顺序中也可能缺少一些节点。
否则，如果另一个编写器在CAS和
current_next -> prev的存储之间插入子列表，那么这个新的子列表将在向后遍历中永远丢失，不是吗？
使用CAS(针对在某个较早点读取的值…？)执行此操作可能会检测到此问题，在失败的情况下，我们可能会向前遍历列表以查找last？这不是小事，我没有答案。
这是一个双链表，因此插入不可避免地需要修改其他线程已经可以看到的两个内存位置：head.next和旧的第一个节点中的.prev指针除非硬件有一个DCAS(双CAS，同时有两个独立的非连续位置)，否则这不能以原子+无锁定的方式完成。正如维基百科的文章所说，它使无锁定的双链接列表变得容易。
m68k曾经有DCAS，但目前主流的CPU架构都没有。ISO C++11没有通过std::atomic公开DCAS操作，因为如果不使所有atomic<T>非锁定，就无法在没有DCAS的硬件上模拟它。除了在具有事务性内存的硬件上，Intel最近的一些x86 CPU(例如Broadwell和更高版本)上都有，但AMD没有。在向C++添加TM语法方面已经做了一些工作，请参阅https://en.cppreference.com/w/cpp/language/transactional_memory
当然，如果没有事务内存或类似DCAS的东西，观察者也不可能同时原子地观察到两个位置因此，任何读取列表的线程都需要期望它从它们下面变出来，特别是如果列表也应该支持删除的话。
在发布之前在新节点(尚未发布到其他线程)中设置指针显然是很好的，您正在这样做。在CAS尝试发布这些新节点之前，CCD_ 11和CCD_。CAS具有顺序一致性内存排序，因此它确保之前的存储在它本身之前对其他线程可见。
在修改head之后，您选择修改旧的第一个的.prev指针非常有意义。您基本上是先向前发布，然后再反向发布但请记住，线程在任何点都有可能长时间睡眠，因此不能100%安全地认为这总是暂时的不一致想象一下，当其他线程运行时，在该函数内的任何时候停止调试器中的一个线程，甚至停止单步执行。在这种情况下，只有两个感兴趣的操作，CAS和对旧的第一个非伪节点的无条件存储。
如果线程向前遍历，并且依赖于能够通过遵循.prev返回(而不是在局部变量中记住它自己的前一个)，那么在它看来，这可能就像新节点再次被删除一样。它可以找到一个指向CCD_ 17的CCD_。这是一个人为的例子，因为如果你想再次找到上一个节点，特别是在无锁定列表中，通常只记住它会更有效。但也许也有一些非人为的情况，比如一个线程向前遍历，另一个线程向后遍历，或者直接或间接地交互，在这些情况下，不一致是显而易见的。
只要所有线程都同意修改事物的顺序，我认为插入本身是安全的，至少对前向链接是安全的。只在头部进行验证会更容易，但我认为允许任意插入点仍然是安全的。
您当前的代码看起来可以安全地同时插入(假设没有删除)。前向列表可能比后向列表长(可能会有多次插入后向列表)，但一旦它们都完成，列表将保持一致。
更正，正向列表将是一致的，但反向列表可能会丢失对节点或子列表的跟踪。
如果不删除，每个挂起的对.prev的写入都有一个有效的目标，并且该目标是其他线程不想写入的节点。无锁定单链表插入很容易，并且转发列表(.next链接)始终是最新的
因此，每次插入操作"；权利要求"；它用作反向列表中插入点的节点，在反向列表中它对current_next->prev的存储变为可见。
还是这样？我认为在同一点上的多个插入可以在任何一个完成其后向(->prev存储)之前成功地完成其前向CAS，因此我们毕竟不是声称对节点的独占所有权
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
}
这在Godbolt编译器资源管理器上为x86编译时使用零mfence指令，而不是您的3指令。(asm的其余部分实际上是相同的，包括一个lock cmpxchg。)因此，在无争议的无RFO情况下(例如，从同一核心重复插入)，它可能会快4倍。或者更好，因为mfence实际上比英特尔CPU上的lock前缀还要慢。
此外，最终存储完全在循环之外的do{}while(!CAS)可以说更容易让人类立即阅读和查看逻辑。
清除是一个巨大的并发症
我看不出在有挂起的插入时如何安全地删除。如果删除插入器要修改(添加反向链接)但尚未修改的节点，则该节点范围将永远从反向列表中丢失。
(此外，如果您回收该节点的内存，插入器的存储就会踩到一些东西。)
这将使前向和后向列表不同步如果没有DCAS(或事务内存，它是DCAS的超集)，我看不到解决这个问题的方法。不过，我不是一个无封锁的数据主义专家，所以也许有一个诀窍
甚至可能同时有多个remover也是一个问题，因为您最终可能会对另一个线程将要删除(或已经删除)的节点进行挂起的修改。或者对一个节点进行多个挂起的修改，无法确保正确的节点最后完成。
如果您有插入器/移除器锁(多个插入器/单个移除器，与读取器/写入器锁完全相同)，则在执行移除时可以确保没有挂起的插入但仍允许无锁定插入。也许将锁放在与head相同的缓存行中，因为插入线程总是需要修改它和head。或者可能不是因为如果核心有时在获取锁之后但在将修改提交给head之前失去了对该行的所有权，那么您可能会对该行产生更多的争用。