最近在講解 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 更是慢到破表  ...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

創作者介紹
創作者 hedgezzz 的頭像
hedgezzz

hedgezzz的部落格

hedgezzz 發表在 痞客邦 留言(0) 人氣()