contributed by < fwfly
>
建立 n 個 thread 去對一個 list 做 insert key
然後 n 個 thread 去同一個 list 做 delete key
這樣會同時對一個 list 做新增,刪除跟搜尋(find)而導致 race condition 的問題
最後再用 hp 的方式達到 lock-free 的解法
程式用了 2 維 array 去產生 key.
這個 array 可以記錄給個 insert thread 產生的 key
在 delete 的時候, delete thread 也可以根據拿到的 tid 從 array 中找到 key
在 main 裡面可以看到 thread 是輪流去產生 delete 跟 insert thread,
所以 delete 跟 insert thread 會有同樣的數目,理想上兩邊剛好可以抵消
但是問題出在這邊
從上面可以知道 key 是 elements 中每一個 cell 的 address
最後產生的 elements 會是下圖
可以看到 delete 跟 insert 是交錯的關係, 所以 delete 永遠不會刪到在 list 中的任何一個 key, 可以簡單地補上 printf 驗證
然後會發現程式都只會印出 False 直到最後一段把 list 全部清除時才會印到 True
這時候才會做到真正的刪除.
所以如果加上這段 printf, 會發現 True 全部集中在最後一段
用兩個 tid_base 分別計算 insert thread 跟 delete thread
因為 elements 是用 idx 去找 key, 所以並不影響原本的程式.
Patch 的程式碼
經過上面的 patch 後的程式,兩種 thread 確實產生了 race condition, 但是觸發了 ThreadSanitizer: data race 的 error.
問題會發生在做 retire node 的部分,要先理解 retire 跟整個 hp 的設計,才能知道為什麼這邊會發生
在 atomic 跟 hp 的幫助下,有點難看出來 atomic 跟 hp 解決了什麼事情,
所以把全部的 atomic 跟 hp 拿掉來實驗看看程式會出現什麼結果.
( To do )
( To do )
這次作業的 list.c 裡面的 hazard pointer 的機制是用 c11 的 atomic 去進行實作.所以再踏入 hazard pointer 前,要先了解一下 atomic 怎麼使用.
這次的實作有用到以下幾個 atomic 的 function
atomic_store : 把值給寫進去 atomic object
atomic_store_explicit : 跟 atomic_store 但是可以選擇怎麼處理 memory order
atomic_load : 把 atomic 值從 atomic object 中讀出來
atomic_compare_exchange_strong : 比較 atomic object atomic 跟另一個參數,如果比較大就把 desired 值存到 atomic object 中
get_unmarked ?
get_unmarked_node ?