什麼是不鎖定無阻塞算法的例子？

Question

所以鎖定自由是當你有保證整個系統進展，雖然有些線程可能會餓死。所以基於CAS的實現將提供這種保證。

然後無阻塞是當一個線程保證完成，如果所有其他線程都掛起。

你能給出一個簡單的無鎖定算法的例子嗎？

謝謝！

Answer 1

我推薦閱讀introduced the term - 主要作者Herlihy在25年前推出等待自由的概念時啓動了整個業務。

鎖定自由和梗阻自由之間的核心區別是，如果兩個或多個線程運行後並不能保證取得進展（但如果只有一個正在運行）。

本文的肉給你要你想要的，出隊是梗阻免費的，但不是無鎖的例子。

爲了使它更簡單，我將只描述一個基於數組的堆棧，它以相同的方式運行，並且無阻塞但不鎖定空閒。

想象一下，在一個數組頂部實現一個堆棧，這樣堆棧的零個或多個元素將連續存儲在數組的開頭，然後在所有剩餘位置中都是「null」元素。堆棧中的每個元素都存儲爲元組：(val, seq)，其中val是用戶提供的值，seq是對算法很關鍵的序列號（並且還避免了ABA問題）。

爲推動元件壓入堆棧，首先定位堆棧中的最後一個元素（位置A[k-1]），這是直接在第一空元件（在A[k]位置）之前。您嘗試增量，使用CAS的A[k-1]的序列號（元素沒有變化），如果成功，你試圖同時替換值null元素在A[k]位置，並增加它的序列號。如果任一CAS失敗，則重試。

彈出算法類似，但處理以相反的順序（遞增拳頭空元素的序列號，然後努力使最後一個元素null，並且遞增的序列號）的元素。

該結構的正確性在上面的文章中有更詳細的描述，但基本上通過成功增加第012個元素，你確保在那一刻它仍然是列表中的最後一個元素，並且你通知任何同時參加的比賽通過使他們的初始CAS失敗來推動你「獲得下一個鏡頭」的操作。如果第二個CAS成功，您成功添加了一個元素。

注意併發push和pop操作會導致對方失敗，無限期。在推進螺紋增量A[k-1]，並在彈出的增量A[k]，然後當他們看到其他的增量每個失敗。沖洗並重復。這是活鎖的一個例子。

請注意，如果只有一個線程正在運行，問題就會消失，這是阻塞自由中的關鍵觀察。

---

...這也避免了出隊的完整版「環繞」的問題，但我不認爲在堆棧的情況下發生的。

Answer 2

我不確定是否有可能給出簡單的示例。簡單的事情通常是無等待的（例如RCU的閱讀器側）或無鎖（例如，不可能存在活鎖的CAS重試循環），或者甚至不阻塞。

請參閱Lock-free Progress Guarantees分析無鎖定多寫入器多讀取器隊列，其中即使在中等運行情況下睡覺的寫入器可以阻塞整個隊列，即使它是高性能/低爭用並且在實踐中有用。

---

我認爲是阻礙自由而不無鎖是唯一可能的，如果線程可以被其它線程取消部分完成的操作。 （並且因此處理當他們喚醒時取消他們自己的操作的情況）。我可能錯了;也許還有其他方法算法可以是非阻塞的，但不是無鎖的。

這不是我會考慮簡單，但https://en.wikipedia.org/wiki/Non-blocking_algorithm說：

一些無障礙的算法，數據結構使用一對「一致性標記」。讀取數據結構的過程首先讀取一個一致性標記，然後將相關數據讀入內部緩衝區，然後讀取另一個標記，然後比較標記。如果兩個標記相同，數據是一致的。當讀取被另一個更新數據結構的進程中斷時，標記可能不相同。在這種情況下，進程會丟棄內部緩衝區中的數據並再次嘗試。

如果用於爭用的退避算法不好，這可能會活鎖。由於線程太多，他們可能會在任何事情完成之前不斷取消對方。這是什麼使它不鎖定。