c - 单链表插入同步

Question

假设我有一个N个不包含重复项的整数的排序单链表和k个线程（其中k << N），每个线程都试图将一些整数（大于头节点）插入到列表中。

是否可以将插入同步到这样的列表中，以便：

• 线程只能阻止对其（立即）前一个节点的访问
  （不锁定“整个列表”）
• 最多可以使用 O(k) 个互斥锁和条件变量
• 不会发生抢占/中断

?

Answer 1

首先，如果插入集合不是一项非常罕见的任务，那么链表就不是一个很好的解决方案 - 因为找到插入点是一个O(N)操作，即使对于排序列表也是如此，因此最终会严重缩放.

如果您仍然需要这样做，可以将插入（与删除不同）作为无锁操作执行到排序列表中，但要小心：

1. 找到插入点，cur
2. 创建新节点（将 prev/next 链接分配给cur/ cur->next）
3. 原子操作：compare_and_swap(cur->next, new, new->next);
   如果失败：if (new->value == next->value) return; // someone beat us to it
   否则：cur = cur->next并重复舞蹈（列表已排序，有人在我们之前插入）

即尝试链接一个新节点的结果要么是我们成功，要么有人打败我们插入同一个节点（在这种情况下我们没问题 - 它已经在那里），或者有人插入了一个间隙（即现有是N，，N+3我们尝试过N+1，其他人成功N+2）在这种情况下，我们重试直到我们成功或找到其他人完成的“我们的”节点。

同步删除要困难得多；为此查找 RCU（读取-复制-更新）。