https://hackmd.io/@sysprog/concurrency 注意 lock-free
將需要用到的標頭檔複製出來,並且將所需要的額外巨集另外定義。
已撰寫程式確認可運行於 userspace。
之前比較少接觸 static function,故遇到一些問題,例如以下程式碼:
原先預期是只有在 while 迴圈內會將節點鎖定,等到目前節點處理完畢後便直接解除鎖定,因為 node 指向的記憶體位置會不斷改變,為了正確的將節點解鎖,額外使用變數 parent_lock
紀錄父節點的 lock,但在編譯時期出現以下錯誤:
後來改成以下形式規避此編譯警告:
最一開始嘗試很粗暴的在所有操作前加上 LOCK
、並在操作結束後 UNLOCK
,但在後續的測試中發現程式很常會卡在一些奇怪的地方。
後來發現是重複對於同一個節點做 LOCK
,導致某些情況下程式會卡住,後來改為 top down 的方式新增 LOCK
。
這邊的 top down 是指,先從每個大操作(如
rb_insert
,rb_erase
)開始時將整顆紅黑樹LOCK
起來,等到整個操作都處理完畢時再UNLOCK
。
等確認此操作無其他執行上的問題時,再將這些大操作的LOCK
/UNLOCK
下放置下一層的函數中。
並行程式設計
mfrw/urb
Linux 核心的紅黑樹
Lock-Free Red-Black Trees Using CA