2022q1 Homework5 (quiz5)
contributed by < Korin777
>
測驗二
程式研讀
程式運作
- reader 會透過
load 函式
來讀 shared_config
並透過 list_insert_or_append 函式
將正在使用的 config 插入 config_dom->pointer
(即為 hazard pointer) , reader 印出 config 後在透過 drop 函式
將 config 從 hazard pointer 移除
- writer 透過
swap 函式
更新 shared_config
, 並將舊的 config 透過 cleanup_ptr 函式
釋放
- 只有一個 writer 時 , updating config 到 updated config 中間 , read config 會印出兩種不同的 config , 一個是舊的一個新的 config , 等到 updated config 後 read config 所印出的 config 才會一致
load
list_remove
list_remove
不會將 node 從 link list 移除 , 而是將該 node 變為空的 node 讓其他人可以使用
drop
__builtin_unreachable
能讓 compiler 改變 branch 的順序(e.g. if 先往外面執行) 及消除 dead code (e.g. if 內的 ret
) , 這裡的 list_remove 函式
也不該 return false (因為 hazard pointer 的移出不該失敗) , 若走到 __builtin_unreachable()
也能讓我們得知在 drop 函式
發生錯誤了
swap
cleanup_ptr
- 若
flag
為 0 則 writer 一直等到 hazard pointer 沒此 config 在釋放它
- 若
flag
為 1 則 writer 將此 config 插入 config_dom->retired
(即 retired list , 之後在透過 cleanup 函式
來釋放) , 因此 writer 不須等待 reader 繼續更新 config
改進
發現
雖然程式有實做 retire list , 但 writer_thread
傳入 cleanup_ptr 函式
的 flags 為 0 , 因此不會將要移除的 config 插入 retire list 而會用 busy waiting 的方式來釋放舊的 config
實做
- 原本的 retired list 是 global 的 , 所有 writer 都能存取到 , 但這裡我將 retired list 改為 local 的 。 每個 writer 需要將自己替換掉的
shared_config
加入自己的 local_retired
並負責釋放此 config
- writer 結束前必須確保自己負責的 config 都已經釋放了
- retired list 改為 local 的好處有讓對 retired list 操作不再需要用 atomic operation ; 而每個 config 被唯一一個 writer 保存 , 因此 traverse retired list 的路徑也可以減少
- 傳入 writer 的 local retired list 及更換操作 retired list 的函式
independent_list_remove
、independent_list_append
- 因為 retired list 改為 local 的 , 在插入及移除可以不用 atomic operation
比較 retired list 與 busy waiting
N_ITERS 固定為 10000
writer 固定為 4 個 , 增加 reader 數量

- 使用 busy wating 和 retired list 的執行時間差異不大
reader 固定為 4 個 , 增加 writer 數量

- 當 writer 為 8 個時 busy waiting 的時間大幅增加 (註:有時當 writer 為 8 個時 busy waiting 的時間還是可以跟 retired list 差不多)
- 執行程式並透過 perf 來觀察程式熱點
- 使用 retired list 時 , 在各函式所佔的百分比大致相差不多 , 佔比較多的有
list_insert_or_append
、list_remove
、syscall_exit_to_user_mode
、__random
, 其random
tex
- 使用 busy waiting 時 , 可以發現在
list_contains
佔了 90% 以上 , 而 cleanup_ptr
則佔了 5% 左右 。 會卡在這裡的原因就是要等 reader 及其他 writer drop 掉插入 hardzrad pointer 的 config , 因此 writer 一直透過 list_contains
來查看 hardzrad pointer
- retired list 和 busy wating 還有一個不同的地方是 , retired list 的 print config 和 updating/updated config 的交錯會比較頻繁 , 因為 writer 不用等 reader
開啟多個 writer 無法通過 ThreadSanitizer
問題
- 原本只有一個 writer ,
new_config
並不會被動到 , 而當開啟多個 writer new_config
就有可能受到其他 writer 的操作
- e.g.
- writer1 在
print_config("updated config ", new_config)
前停下換 writer2 執行
- writer2 經過
swap 函式
換掉 shared_config
並取得 old_obj
(即 writer1 的 new_config
) 在透過 cleanup_ptr 函式
查看是否能釋放它 , 這時要是剛好沒有 reader 在使用它 , writer2 就能將它釋放 , writer2 停下換 writer1 執行
- writer1 此時要印出
new_config
就會發生問題
解決方法
- 在進入
swap 函式
前 , 先將 new_config
插入 hazard pointer 讓其他 writer 必須等待而無法將它釋放 , 等 writer 不用使用到 new_config
後在透過 drop 函式
將它從 hazard pointer 移除 , 這時其他 writer 便能將它釋放
比較 RCU 和 hazard pointer (HP)
RCU
- reader
- 透過
rcu_read_lock
、rcu_read_unlock
所建立的 critical section 來保護資料
rcu_read_lock
: 通知 reclaimer 自己進入 crtical section
- rcu_read_unlock : 通知 reclaimer 自己離開 crtical section
- updater
- removal
- 透過 spinlock 確保同時只有一個 writer 在更新資料
- writer 先複製一份舊的資料並更新它 , 接著用此替換掉舊的資料
- reclamation
- 透過
synchronize_rcu
、call_rcu
來釋放資料
synchronize_rcu
: block updater 直到 pre-existing RCU
read-side critical sections 都完成
call_rcu
: updater 不會被 block , pre-existing RCU
read-side 都完成才會執行註冊的 callback function
RCU 和 HP 的差異
- 在 reader 方面 RCU 不會用到 lock 及 atomic operation ; HP 則需要在使用到 shared data 及 hazard pointer 時使用 atomic operation , 若拿到的 shared data 為舊的就要重新讀取。
- 在 writer 方面 , RCU 透過 spinlock 來確保同時只有一個 writer 在更新 shared data ; HP 則是透過 atomic operation
- RCU 透過 crical section 來保護 reader 正在使用的 shared data ; HP 則透過 hazard pointer 來保護
題目連結
對照研讀 hp_list 程式碼,這是測驗題後續改進的實作
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
程式運作
- thread 間共享一個 key 值遞增且唯一的 link list
- 每個 thread 有自己的 hazard pointer 及 retired list
- insert thread 負責新增節點 ; delete thread 負責移除節點(logically delete) 並嘗試將它 physically delete 。 兩者皆會透過
__list_find 函式
嘗試將經過的 logically delete 節點 physically delete
- logically delete: 將欲移除 node 的 next 所指向的地址的最後一個 bit 改為 1 (因記憶體對齊的緣故 , 原本記憶體位置的最後一個 bit 為 0)
- physically delete: 將 node 從 link list 上移除(尚未釋放) 並加到 retired list
- 並行程式設計: Lock-Free Programming 提到 concurrent linked list 會發生的問題

原本的 delete 過程中並不會更動到 node_10->next , 所以 insert 如期執行而產生錯誤的結果 ; 而 logically delete 就是透過改變 node_10->next 來避免上述問題
__list_find
- par_curr: 持有的 key 大於等於所要尋找的 key 的 node
- par_prev: node->next 為 par_curr 的 pointer 地址
- par_next: par_curr->next 的值
- return value: 若 key 存在回傳 true , 反之回傳 false
- 會將 par_curr 及其前後一個 node 插入 hp , 這 3 個 node 就是 thread 正在使用的 data , 用完後透過 list_hp_clear 從 hazard pointer 移除
list_insert
list_delete
TODO: 討論上述實作是否能避免 ABA Problem?
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
討論 ABA 問題
- 根據 ABA Problem 所舉的例子
- 假設 link list 一開始為 (head,0) -> (0x4,1) -> (0x8,2) -> (0xc,3) -> (tail,UINTPTR_MAX)
- (address,data)
thread1 先執行
thrad1 在執行 CAS(&curr->next, &tmp, get_marked(next))
前被 thread2 中斷
回到 thread1 執行
- 此時的 curr 為 thread2 插入的 , curr->next 為 0xc , 所以第一個 CAS 不會將 curr logically delete , 在這個狀況下會重新執行 list_delete
- 如果 thread2 不只新增了 0x4 還新增了 0x8 , 則 link list 為
head -> 0x4 -> 0x8 -> 0xc -> tail
, 這時第一個 CAS 就可以將 curr logically delete 並執行第二個 CAS , 而第二個 CAS 也可以將 curr physically delete , 就會產生先執行的 delete 去移除後面 insert 近來的 node 的情況 。 不過實際上 thread1 會將 head,0x4,0x8
插入 harzard pointer 來延緩 physically delete , 因為記憶體還沒被釋放 , 所以 thread2 所新增的節點記憶體位置應該不會在 0x4 及 0x8 , 因此上述的情況應該也不會發生。
- 就上述情況 , 此實做能避免 wekipedia 所舉出的 ABA 問題
參考資料 :
What optimizations does __builtin_unreachable facilitate?
What is RCU? – "Read, Copy, Update"