<style> .reveal .slides { text-align: left; font-size:30px } </style> # ABA problem by 01157116 劉元楷 --- ## problem 在多線程的同步處理中，ABA problem 是一個比較常見的問題 (a)兩個同步處理的線程，在什麼情況下可能會發生ABA？ (b)提出其中一種解決方法 --- ## 背景故事: 共享memory - **Threads** 可以： - 使用**共享記憶體**向另一個執行緒傳遞訊息 - **競爭相同的記憶體資源** - **記憶體存取**需要**同步(synchronisation)**，透過`lock`機制達成： - **Mutex** - **Semaphore** ---- ## lock 缺點 傳統的lock機制有時無法滿足效能需求，因為： - Deadlocks - Priority Inversion - Convoying ---- ## lock free 定義：在任何執行緒排程決策下都不應發生鎖死 可以理解成：只要給定足夠多的時間，保證程式中的某些執行序能夠有進展(call return) ---- ## how to do lock free? => `Atomic Operations` 將lock的作用域缩小到僅包含一個CPU指令 如: - Load/Store - Increment/Decrement - `Compare-And-Swap(CAS)` ---- ## 舉例 把 `X` 的值從 `a` 變成 `b` ### lock-base ```clike acquire(mutex_X) if X == a: X = b release(mutes_X) ``` ### lock free ```clike compare_and_swap(X,a,b) ``` --- ABA problem 發生在有多個線程對同一個記憶體位置進行寫操作時。 - 線程 1 從記憶體位置 `X` 讀取值 `A` - 線程 2 將值 `B` 存入 `X` - 線程 2 再將值 `A` 存入 `X` - 線程 1 從 `X` 讀取值 `A`，並假設未發生任何修改 ---- ## 舉例： lock free stack **Node:**  - head: `atomic` Node * - push(data) - pop() ---- ## Lock free stack - Push 步驟 1. 創建新節點 2. 把next指標指到目前的head 3. 把head指到新節點的位置 ---- Thread A ```clike= Create a new node node.next = head head = &node ``` Thread B ```clike= Create a new node node.next = head head = &node ``` 問題: `head` 變了但是Thread A 不知道! ---- lock free push ```clike= function push(data): Node new_node = new Node(data) while True: new_node.next = head Node* old_head = new_node.next //不可從head拿因為可能被其他thread更改 if compare_and_swap(head,old_head,&new_node): break ``` 每次迴圈CAS若失敗，則代表head被更改，會重新執行pop邏輯 ---- ## Lock free stack - Pop 步驟 1. 讀取並檢查head的值 若為NULL則 等待其他thread push/return noting/throw exception 2. 把 head 設為 head -> next 3. 回傳 data 4. delete data --- lock free pop ```clike= function pop(): Node* old_head, new_head while True: old_head = head if old_head == NULL: continue new_head = old_head->next//這邊會導致ABA problem if compare_and_swap(head, old_head, new_head): break data_cpy = old_head->data free old_head return data_copy ``` 若在`new_head = old_head->next`時其它thread pop了，就會導致segmentation fault ---- 再回頭看: ABA problem 發生在有多個線程對同一個記憶體位置進行寫操作時。 - 線程 1 從記憶體位置 `X` 讀取值 `A` - 線程 2 將值 `B` 存入 `X` - 線程 2 再將值 `A` 存入 `X` - 線程 1 從 `X` 讀取值 `A`，並假設未發生任何修改 ---- ## 由範例來看ABA problem 假設目前有兩個Threads A, B 目前Stack: C <- B <- A (head is A). ABC為addresses ### Thread1 ```clike!= execute pop() read A from head read A -> next CAS(head,A,B) succeeds head is B which is already freed => corrupt ``` ### Thread2 ```clike= pop()// A is popped. Stack: C<-B pop()// B is popped. Stack: C push(data)// memory reuses address A Stack becomes C<-A ``` --- ## 解決方法 ---- ## Deferred reclamation(延遲回收) ### 核心思想 僅在確定没有其他threads引用某Node時，才回收(free)該Node ### 解决問题 通過避免過早釋放內存，防止其他threads存取已釋放的内存，解决 ABA problem 潛在的錯誤 ---- ### 實作方式 Hazard pointers 其基本的概念是允許 hazard pointer 可以被一個 thread 寫而多個 thread 讀，當存在 reader thread 正在操作該 hazard pointer 時，hazard pointer 會被標註，於是 writer thread 可得知此訊息並延遲對其釋放 ---- 在 hazard pointer 架構中，每個 thread 首先需要各自維護的兩個關鍵集合是: hazard pointer: 儲存此 thread 正在存取的指標，因此該指標不能直接被釋放 retire list: 被這個 thread 要求釋放的指標，但實際尚未釋放  ---- 因此要安全的釋放記憶體，其基本想法就是: 每個執行緒放在 hazard pointer 中的指標尚不能被釋放 每個執行緒要求釋放的指標先放在 retire list 中 掃描 retire list 可以得知所有執行緒皆不使用的指標，則可將其真正的釋放給作業系統 --- ## 參考資料 https://www.youtube.com/watch?v=Yl8Or0afcfg&t=237s https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-hazard-pointer