这个无锁 dlist 插入是否安全？
Is this lock-free dlist insertion is safe?
我需要在双重 linked 列表的头部实现子列表的无锁插入。这个列表有一个虚拟头，所以每个线程都试图在头节点之后插入它的部分。这个设计对我来说似乎还可以，但是，我没有足够的专业知识来证明它。
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 是最后更改的 link。所以在它改变之后，没有其他线程（除了remover）可以访问该节点或者它的前一个节点next link。
这个推理有效还是我遗漏了什么？
@peter-cordes 回答后的一些说明。
- 列表不是线性可遍历的，因此从这个角度来看，不一致的列表状态不是问题。
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 有一个单独的节点删除工作列表
- 节点只有在其插入阶段完全完成后才能添加到工作列表
TL:DR：根据读者的操作（没有长期损坏），单独插入是可以的，但是如果没有锁定或更复杂的方法，删除可能是不可能的，绝对是这个简单插入算法的亮点。
这是一个双link编辑列表，所以插入不可避免地需要修改两个其他线程已经可以看到的内存位置：head.next，以及旧的第一个节点中的 .prev 指针。 除非硬件具有 DCAS (double-CAS, two separate non-contiguous locations at once)，否则这不能以原子+无锁方式完成。正如维基百科文章所说，它使无锁双linked 列表变得容易。
m68k 曾经有过 DCAS，但目前的主流 CPU 架构都没有。 ISO C++11 不会通过 std::atomic 公开 DCAS 操作，因为如果不使所有 atomic<T> 非无锁，您就无法在没有它的硬件上模拟它。除了具有事务内存的硬件，可用于 Intel（例如 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 为了效率）。
您选择在 修改 head 之后修改 old-first 的 .prev 指针 很有意义。您实际上是先正向发布，然后反向发布。 但请记住，线程有可能在 任何 点休眠很长时间，因此假设这始终是暂时的不一致并不是 100% 安全的。 想象一下，在此函数内的任何一点停止调试器中的一个线程，甚至单步执行，而其他线程 运行。在这种情况下，只有 2 个有趣的操作，CAS 和无条件存储到旧的第一个非虚拟节点。
如果线程向前遍历并依赖于能够通过跟随 .prev 返回（而不是在局部变量中记住它自己的前一个），这可能看起来像新节点已经又被删了它可以找到指向 head 的 .prev。这是一个人为的例子，因为如果您希望能够再次找到它，那么简单地记住您以前的节点通常会更有效，尤其是在无锁列表中。但也许存在非人为的情况，例如一个线程向前遍历而另一个线程向后遍历，并且可能直接或间接交互，其中不一致是可见的。
只要所有线程都同意修改东西的顺序，我认为插入本身是安全的。只在头部做更容易验证，但我认为允许任意插入点还是安全的。
您当前的代码看起来对于同时插入是安全的（假设没有移除）。前向列表可以比后向列表长（可能有多个插入到后向列表中未完成），但是一旦它们全部完成，列表将是一致的。
如果不删除，每个对 .prev 的待处理写入都有一个有效的目的地，并且该目的地是一个没有其他线程想要写入的节点。 无锁单linked 列表插入很容易，前向列表（.next links）总是最新的。
所以每个插入操作 "claims" 一个节点，它用作反向列表的插入点，当它对 current_next->prev 的存储变得可见时。
A do{}while(!CAS()) 循环是一个很好的习惯用语，通常可以简化代码。我削弱了其他操作的内存排序，尤其是 first 和 last 上的私有操作，因为要求编译器在存储到其他线程还看不到的元素后使用慢速屏障是低效的。在 x86 上，发布存储是 "free"（没有额外的障碍），而 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
}
这为 x86 编译了零个 mfence 指令，而不是你的 on the Godbolt compiler explorer 的 3 个指令。 （asm 的其余部分实际上是相同的，包括 lock cmpxchg。）所以在无竞争的无 RFO 情况下（例如，从同一核心重复插入），它可能快 4 倍。或者更好，因为 mfence 实际上比 Intel CPUs 上的 lock 前缀还要慢。
此外，do{}while(!CAS) 最终存储完全在循环之外，可以说更容易让人们立即阅读和查看逻辑。
删除是一个巨大的并发症
我不知道在有待插入的情况下如何安全地删除。如果您删除插入器要修改的节点（添加向后 link）但尚未删除，则该节点范围将永远从向后列表中丢失。
（另外，如果您为该节点回收内存，则插入器的存储会踩到某些东西。）
这会使前后列表不同步。 如果没有 DCAS（或事务内存，它是 DCAS 的超集），我看不到解决此问题的方法。不过，我不是无锁 dlist 专家，所以也许有窍门。
甚至多个同时删除器可能也是一个问题，因为您最终可能会对另一个线程将要（或已经）删除的节点进行未决修改。或者对一个节点进行多项待定修改，但无法确保正确的修改最后完成。
如果你有一个 inserters/removers 锁（多个插入器/单个移除器，与 readers/writer 锁完全一样），你可以确保在执行 a 时没有挂起的插入移除。 但仍然允许无锁插入。也许把锁放在和 head 相同的缓存行中，因为插入线程总是需要同时修改它和 head。或者可能不是，因为如果核心有时在获取锁后但在提交对 head.
的修改之前失去对该行的所有权，那么您可能最终会对该行产生更多争用
我需要在双重 linked 列表的头部实现子列表的无锁插入。这个列表有一个虚拟头，所以每个线程都试图在头节点之后插入它的部分。这个设计对我来说似乎还可以，但是，我没有足够的专业知识来证明它。
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 是最后更改的 link。所以在它改变之后，没有其他线程（除了remover）可以访问该节点或者它的前一个节点next link。
这个推理有效还是我遗漏了什么？
@peter-cordes 回答后的一些说明。
- 列表不是线性可遍历的，因此从这个角度来看，不一致的列表状态不是问题。
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 有一个单独的节点删除工作列表
- 节点只有在其插入阶段完全完成后才能添加到工作列表
TL:DR：根据读者的操作（没有长期损坏），单独插入是可以的，但是如果没有锁定或更复杂的方法，删除可能是不可能的，绝对是这个简单插入算法的亮点。
这是一个双link编辑列表，所以插入不可避免地需要修改两个其他线程已经可以看到的内存位置：head.next，以及旧的第一个节点中的 .prev 指针。 除非硬件具有 DCAS (double-CAS, two separate non-contiguous locations at once)，否则这不能以原子+无锁方式完成。正如维基百科文章所说，它使无锁双linked 列表变得容易。
m68k 曾经有过 DCAS，但目前的主流 CPU 架构都没有。 ISO C++11 不会通过 std::atomic 公开 DCAS 操作，因为如果不使所有 atomic<T> 非无锁，您就无法在没有它的硬件上模拟它。除了具有事务内存的硬件，可用于 Intel（例如 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 为了效率）。
您选择在 修改 head 之后修改 old-first 的 .prev 指针 很有意义。您实际上是先正向发布，然后反向发布。 但请记住，线程有可能在 任何 点休眠很长时间，因此假设这始终是暂时的不一致并不是 100% 安全的。 想象一下，在此函数内的任何一点停止调试器中的一个线程，甚至单步执行，而其他线程 运行。在这种情况下，只有 2 个有趣的操作，CAS 和无条件存储到旧的第一个非虚拟节点。
如果线程向前遍历并依赖于能够通过跟随 .prev 返回（而不是在局部变量中记住它自己的前一个），这可能看起来像新节点已经又被删了它可以找到指向 head 的 .prev。这是一个人为的例子，因为如果您希望能够再次找到它，那么简单地记住您以前的节点通常会更有效，尤其是在无锁列表中。但也许存在非人为的情况，例如一个线程向前遍历而另一个线程向后遍历，并且可能直接或间接交互，其中不一致是可见的。
只要所有线程都同意修改东西的顺序，我认为插入本身是安全的。只在头部做更容易验证，但我认为允许任意插入点还是安全的。
您当前的代码看起来对于同时插入是安全的（假设没有移除）。前向列表可以比后向列表长（可能有多个插入到后向列表中未完成），但是一旦它们全部完成，列表将是一致的。
如果不删除，每个对 .prev 的待处理写入都有一个有效的目的地，并且该目的地是一个没有其他线程想要写入的节点。 无锁单linked 列表插入很容易，前向列表（.next links）总是最新的。
所以每个插入操作 "claims" 一个节点，它用作反向列表的插入点，当它对 current_next->prev 的存储变得可见时。
A do{}while(!CAS()) 循环是一个很好的习惯用语，通常可以简化代码。我削弱了其他操作的内存排序，尤其是 first 和 last 上的私有操作，因为要求编译器在存储到其他线程还看不到的元素后使用慢速屏障是低效的。在 x86 上，发布存储是 "free"（没有额外的障碍），而 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
}
这为 x86 编译了零个 mfence 指令，而不是你的 on the Godbolt compiler explorer 的 3 个指令。 （asm 的其余部分实际上是相同的，包括 lock cmpxchg。）所以在无竞争的无 RFO 情况下（例如，从同一核心重复插入），它可能快 4 倍。或者更好，因为 mfence 实际上比 Intel CPUs 上的 lock 前缀还要慢。
此外，do{}while(!CAS) 最终存储完全在循环之外，可以说更容易让人们立即阅读和查看逻辑。
删除是一个巨大的并发症
我不知道在有待插入的情况下如何安全地删除。如果您删除插入器要修改的节点（添加向后 link）但尚未删除，则该节点范围将永远从向后列表中丢失。
（另外，如果您为该节点回收内存，则插入器的存储会踩到某些东西。）
这会使前后列表不同步。 如果没有 DCAS（或事务内存，它是 DCAS 的超集），我看不到解决此问题的方法。不过，我不是无锁 dlist 专家，所以也许有窍门。
甚至多个同时删除器可能也是一个问题，因为您最终可能会对另一个线程将要（或已经）删除的节点进行未决修改。或者对一个节点进行多项待定修改，但无法确保正确的修改最后完成。
如果你有一个 inserters/removers 锁（多个插入器/单个移除器，与 readers/writer 锁完全一样），你可以确保在执行 a 时没有挂起的插入移除。 但仍然允许无锁插入。也许把锁放在和 head 相同的缓存行中，因为插入线程总是需要同时修改它和 head。或者可能不是，因为如果核心有时在获取锁后但在提交对 head.