單鏈表插入同步

Question

假設我有一個排序，單鏈接的Ñ整數含有沒有重複，ķ線程（其中ķ < < Ñ），每個試圖插入一些列表整數（大於頭節點）放入列表中。

是否有可能插入同步到這樣的列表，例如：

• 線程只能阻止訪問到它（立即）前一個節點
  （無鎖定「整個列表」）
• 至多O（k）的互斥體和條件變量可用於
• 可能發生

沒有搶佔/中斷嗎？

Answer 1

首先，如果插入到集合中只是一個非常不頻繁的任務，那麼鏈表就不是一個很好的解決方案 - 因爲找到插入點是一個O(N)操作，即使對於排序列表，因此也會去嚴重縮小比例。

如果您仍然需要做它，它是可以進行插入（不像刪除）成排序列表作爲無鎖操作，具有一定的照顧：

1. 查找插入點，cur
2. 創建新節點（分配上/下一個聯動cur/cur->next）
3. 原子OP：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（Read-Copy-Update）。