最近在講解 lock-free 使用到 Double Word CAS 避免 ABA 問題時 ,
發現在 ABA 上頭 , 似乎 朋友 臉上都有三條線 ...
讓我不禁懷疑是我哪裡沒有說好 ???
現在我 implement lock-free queue 有兩種方式 , 一種是 bounded buffer ,
另一種就是...unbounded buffer , bounded buffer 方式簡單的多 ,
Multi Producer Multi Consumer 使用重複的 buffer 運用 CAS 就行了 ,
unbouded buffer 使用時機像是台股好了 , 台股有一萬兩千筆股票代碼 ,
你要 implement 一個 bounded buffer lock-free queue 到這樣的環境 ,
會有機會浪費很多 記憶體 , 使用 unbounded buffer lock -free queue 才是硬道理 !!!!
unbounded buffer queue 使用 list 結構來 implement , 舉例 ,
當此 list top node 是 A , A 下面是 B , 這時候 Thread1 and Thread2
同時要將 從 queue 拿出 top 的 node , 也就是 node A ,
所以程式就進行 : 如果 CAS 比較 head 記憶體 是 A 記憶體 的話 ,
那麼將 head 指向 B , 把 A 拿出來 !!! T1 and T2 同時做 CAS 必然只有一個成功 ,
失敗的那個抓到 head 已經是 node B 了 , 再重新做一次 CAS , 到這裡看來似乎很理想 ！！
來看下面的這個例子 , 一樣 T1 , T2 都同時要做 pop 的動作, 此時 T1 開始要進行 CAS
前的準備動作 : 記錄 head 指向 node A 的記憶體位址 , 記錄 A 下個 node B ,
如果 CAS 成功的話 , A 拿出來 , head 指向 B ,..... 但是 T1 來不及做 CAS 就被 context switch 出去 ,
此時 T2 不但 pop A 出來 , 而且還 push C 進去, 然後再 push A 進去 , 所以, 此時 queue 應該是
A->C->B , 此時 T1 被 OS 喚醒執行 , 要死不死 , 此時 node A 的記憶體位址如果跟 T1 被 switch out
前記錄的位址一模一樣的話 , CAS 就會成功 , T1 把 head 指向 B , 糟糕 , C 被遺忘了 !!!!
這就是 ABA 的問題 , "The Art of Multiprocesser Programming" 裡面使用的是 Java 的 solution ,
就是 CAS 除了記憶體位址外 , 再加上一個 counter , 我們常聽到的 Double Words CAS ,
在我使用的 linux gcc 版本並無相對應的 function call , 只好使用 組合語言 ,
google "DWCAS" 可以找到很多 相關 文件 以及 implement lock-free 的 paper !!!!!
http://herbsutter.com/2014/01/13/gotw-95-solution-thread-safety-and-synchronization/
這個網頁提到一個 shared_ptr 裡面的 rerference counter 的觀念 , 想起以前看到的 rwlock ,
read write lock 也有隱藏的 counter , 用來記錄 read , write thread 個數 ,
在使用上 , 因為 這個 counter 你就得注意 false sharing 的問題 ,
false sharing 是容易犯的錯 , 把 控制流程 的 lock 寫在一個 array 結構 ,
你以為只有處理相同合約的threads受到影響 , 其實不是 , lock 已經夠慢了 ,
lock 加上 false sharing 更是慢到破表 ...
留言列表
