前言

昨天聊到原子操作時提到了2個名詞, 有些人可能不熟, 會在今天簡單說明。明天會有相應的實作。

lock-free 的意義

是一種分類, 在描述某類演算法在處理 multi-Threading 的問題時, 沒有為了保證執行順序令所有 thread 在有限時間內停滯。

換句話說 :

當某個 multi-Threading data structure , 用一用會為了保證執行順序卡住, 那他就不是 lock-free。

再換句話說 :

當 multi-Thread 對某個 lock-free data structure 操作, 無論任何原因, 最後一定有至少一條 thread 有進度。

為甚麼要 lock-free

原因很多舉以下兩個

• 避免 thread 被阻塞，無法實時響應。
• dead lock。

這兩個原因對非同步框架而言都是需要被克服的。

甚麼是 CAS (compare and swap)

維基百科是這樣說的

比較並交換(compare and swap, CAS)，是原子操作的一種，可用於在多執行緒編程中實現不被打斷的數據交換操作，從而避免多執行緒同時改寫某一數據時由於執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。 該操作通過將內存中的值與指定數據進行比較，當數值一樣時將內存中的數據替換為新的值。

說白了他指的是一種由底層提供的 atomic 指令, 其具備 RMW ( read and write ) 的特性, 表示CPU會幫我們確保在read和write的中間不會有其他指令介入。而我們也可以利用這種特性來實作 atomic 的資料結構。

明天會藉由相應的實作來幫助理解該怎麼進行操作。

明天進度

實作一個 lock-free 的 stack 來讓大家簡單的理解 CAS 的使用。

明天見 !