記憶體回收策略 (Memory Reclamation Strategies)

Overview Table

共同思想:三種技術都是在追蹤「有多少執行緒正在訪問某個節點」,確認為零才真正 delete。刪除節點前必須確認沒有其他執行緒還持有它的指標——這是無鎖結構與有鎖結構最大的差異(有 GC 的語言沒有此問題)。

策略一:執行緒計數 + 待刪鏈(代碼 7.4–7.5)

• std::atomic<unsigned> threads_in_pop:進入 pop() 先 ++,離開時在 try_reclaim() 中 --
• 只有當 threads_in_pop == 1(只有我在 pop)時,才可能安全刪除
• 不能刪的節點以 chain_pending_node() 掛上 to_be_deleted 原子串列(復用節點的 next 指標;掛接用 CAS 迴圈)

try_reclaim(old_head) 的決策流程:

threads_in_pop == 1 ?
 ├─ 是 → nodes = to_be_deleted.exchange(nullptr)  ← 原子「認領」整條待刪鏈
 │        --threads_in_pop 後 == 0 ?
 │         ├─ 是 → delete_nodes(nodes)   ← 無人在 pop,整鏈安全刪除
 │         └─ 否 → 把 nodes 重新掛回待刪鏈(有人半路進來了)
 │        delete old_head               ← 我是唯一 pop 者,剛摘的節點可直接刪
 └─ 否 → chain_pending_node(old_head);--threads_in_pop

• 為何要兩次檢查(先 ==1 再 --後==0):第一次檢查與 exchange 認領之間,可能有新執行緒呼叫 pop() 並已持有待刪鏈上某節點的指標(如圖 7.1 的執行緒 B),此時刪除會造成未定義行為
• exchange(nullptr) 保證只有一個執行緒認領這條鏈,其他執行緒可繼續往(新的空)鏈上掛節點

策略二:hazard pointer(風險指標,代碼 7.6–7.8)

源自 Maged Michael 的研究。核心約定:讀者訪問節點前先設定 hazard pointer 昭告天下;刪除者刪除前檢查所有 hazard pointer,有人引用就延後。(類比:龍舟賽開賽前,任一舵手舉手,裁判就不能鳴槍。)

讀取執行緒 (pop)                           刪除執行緒
----------------                           ----------
old_head = head.load()
   ┌─────────────────────┐
   │ hp.store(old_head)  │──宣告────▶ ┌─────────────────────┐
   │ head 變了?          │            │ hazard pointer 全域表 │
   │  ├ 是 → 重讀並重設hp │            │ [tid | 指標] × N     │
   │  └ 否 → 跳出         │            └─────────────────────┘
   └─────────────────────┘                     ▲
安全解引用 old_head                            │掃描
CAS 摘下節點成功                               │
hp.store(nullptr)  ←── 解除宣告        欲刪 p:表中有 p?
                                        ├ 有 → reclaim_later(p)  → 待回收鏈
                                        └ 無 → delete p
                                       之後呼叫 delete_nodes_with_no_hazards()
                                       重掃待回收鏈,能刪的刪、不能刪的放回

• 設定必須用「store 後重驗」迴圈:hp.store(old_head) 之後重新載入 head,不相等就重來——防止「讀到 head 與設定 hp 之間」節點已被摘除刪掉(舊 head 被刪時 head 必已改變,重驗即可察覺)
• pop 主迴圈改用 compare_exchange_strong:CAS 失敗會重設 hazard pointer(成本高),不能容忍 weak 的偽失敗
• 摘下節點後 hp.store(nullptr) 清除宣告;刪除前呼叫 outstanding_hazard_pointers_for(p) 掃表,有引用 → reclaim_later(p),無引用 → 直接 delete;最後 delete_nodes_with_no_hazards() 清待回收鏈

get_hazard_pointer_for_current_thread() 的實作(代碼 7.7):

unsigned const max_hazard_pointers = 100;
struct hazard_pointer {                       // 全域固定長度表
    std::atomic<std::thread::id> id;
    std::atomic<void*> pointer;
};
hazard_pointer hazard_pointers[max_hazard_pointers];

std::atomic<void*>& get_hazard_pointer_for_current_thread() {
    thread_local static hp_owner hazard;      // 每執行緒一個槽位擁有者
    return hazard.get_pointer();
}

• hp_owner 建構子:走訪全域表,用 compare_exchange_strong 把空槽(預設 std::thread::id())換成自己的 id 以認領槽位;找不到空槽就拋 std::runtime_error
• thread_local 保證每執行緒只認領一次,之後存取免掃表(指標已在快取)
• 解構子:先 pointer.store(nullptr) 再把 id 還原為 std::thread::id(),槽位可被復用
• reclaim_later() 用 data_to_reclaim 節點包裝待刪物件:模板建構子記下 std::function<void(void*)> 型別安全的刪除器(do_delete<T> 把 void* 轉回 T* 再 delete)——因為 hazard pointer 是以 void* 通用儲存

成本與改良:

• 樸素版每次 pop() 都要掃 max_hazard_pointers 個原子變數(檢查待回收鏈上每個節點)→ pop 成為效能瓶頸
• 改良:待回收鏈累積到 2 × max_hazard_pointers 個節點才回收——此時至少 max_hazard_pointers 個可刪,平均「每檢查兩個節點就能回收一個」;代價是記憶體占用升高
• 再改良:改用每執行緒本地(thread_local)待回收鏈,免去對鏈長的原子計數;執行緒退出時把本地鏈移交全域

策略三:引用計數(代碼 7.9–7.12)

hazard pointer 把「使用中的節點」記在全域表;引用計數則在每個節點上統計訪問它的執行緒數。

捷徑:std::shared_ptr<>——若平台的 std::atomic_is_lock_free(&some_shared_ptr) 回傳 true,直接用 std::shared_ptr<node> + std::atomic_load/atomic_compare_exchange_weak 寫出的堆疊(代碼 7.9)就是無鎖的,回收全自動。並行技術規範擴展另提供 std::experimental::atomic_shared_ptr<T>(代碼 7.10),語義更直覺。

外部/內部雙計數器設計(split reference count):

struct counted_node_ptr {      // 跟著「指標」走的外部計數
    int external_count;
    node* ptr;
};
struct node {
    std::shared_ptr<T> data;
    std::atomic<int> internal_count;   // 跟著「節點」走的內部計數
    counted_node_ptr next;
};
std::atomic<counted_node_ptr> head;    // 整個結構體做原子 CAS

• 為何要拆兩個:「讀指標 +1」必須和「讀指標」是同一個原子動作(CAS 整個 counted_node_ptr),否則計數增加前節點就可能被刪、指標懸空——把計數放進指標結構裡,才能一起 CAS
• push:新節點 external_count = 1(head 這一個引用)、internal_count = 0
• pop 成功摘下節點者:internal_count.fetch_add(external_count - 2)——−2 是因為(a)節點已離開串列,head 不再引用它;(b)本執行緒也即將不再訪問。若 fetch_add 後總和歸 0(fetch_add 回傳 -count_increase)→ 由本執行緒 delete
• pop 競爭失敗者:internal_count.fetch_sub(1),若自己減掉最後一個引用(回傳 1)→ 由自己 delete

三策略比較

Exam/Test Patterns

Related Notes

• 07-Lock-Free-Data-Structures/01-Lock-Free-Concepts-and-Tradeoffs
• 07-Lock-Free-Data-Structures/02-Lock-Free-Stack
• 07-Lock-Free-Data-Structures/04-Lock-Free-Queue-and-Memory-Ordering
• 07-Lock-Free-Data-Structures/05-Lock-Free-Design-Guidelines
• 07-Lock-Free-Data-Structures/Practice-Lock-Free-Data-Structures
• 05-Memory-Model-and-Atomics/02-Atomic-Types-and-Operations
• 12-Appendix/01-Cpp11-Language-Features