題目與背景
你有高併發無鎖堆疊，節點以原子指標連結。執行緒從頭部讀取並 CAS 摘除，但另一執行緒可能同時釋放節點。請用 C++26 hazard_pointer 思路設計安全回收，允許多個讀者並行且不能以全域大鎖包住堆疊。
面試官考察什麼
重點是 hazard pointer 保護「正在讀取的地址」，不是讓節點永久存活。讀者先發布 hazard，再確認原子 head 仍指向該節點；摘除成功後放入退休清單，掃描所有 hazard 後才回收。也要說明 acquire/release、註冊退出、掃描成本，以及 ABA 需獨立處理。
先問清楚的澄清問題
資料結構與進度保證
確認是 Treiber 堆疊、鏈結串列或雜湊桶，要求 lock-free 或 wait-free，以及是否允許執行緒本地退休清單。
執行緒生命週期
確認如何取得 hazard slot，執行緒退出時如何撤銷保護並移交退休節點。崩潰執行緒不能留下永遠不可回收的記錄。
ABA 與標記策略
確認地址能否重用、是否有版本計數或 tagged pointer。Hazard pointer 防止受保護節點釋放，但不自動阻止 ABA。
30 秒回答框架
「讀者先原子讀取 head，把地址發布到 hazard slot，再重新讀取 head；兩次一致才允許解引用。CAS 摘除成功後節點進入退休清單，不立即 delete。定期收集所有 hazard 地址，只回收不在集合中的退休節點。執行緒退出前清除 hazard 並交接退休清單。ABA 要用版本計數或其他方案另外處理。」
深入解答步驟
第一步：定義 hazard slot 與退休清單
每個可能解引用共享節點的執行緒擁有 hazard slot。退休清單保存已摘除但尚未安全回收的節點，slot 生命週期和註冊必須可追蹤。
第二步：建立發布與確認窗口
讀 head 後以 release 或等價順序寫入 hazard，再以 acquire 重新讀 head。只有兩次一致才可讀節點欄位；變化時清除 slot 並重試。這可阻止節點在發布前被回收。
第三步：執行 CAS 並延後回收
讀取 next 後用 compare_exchange 摘除 head。CAS 失敗時清除 hazard 並重試；成功後把舊節點放入退休清單，完成使用後才清除 slot。任何路徑都不能直接 delete 共享節點。
第四步：掃描並回收
掃描所有執行緒 hazard slot，建立受保護地址集合。遍歷退休清單，只回收不在集合中的節點。掃描閾值可按 slot 數量和清單長度調整。
第五步：處理 ABA 與記憶體序
延後回收可降低地址重用，但不等於消除 ABA。若堆疊快速摘除與重新入棧，使用版本計數或 tagged pointer。head、hazard 和節點欄位要有清楚 happens-before 關係。
第六步：處理執行緒退出與例外
執行緒停止讀取前清除 hazard，退休節點交給存活回收者或全域域。註冊表需能偵測 owner 狀態；析構只能在確認沒有讀者後執行。
第七步：測試安全性與效能
用 ThreadSanitizer、隨機排程與壓力測試覆蓋 CAS 失敗、掃描並行、退出、重用和例外路徑。加入延遲釋放哨兵驗證沒有 use-after-free，並量測掃描耗時、清單峰值、吞吐與尾延遲。
高品質示例回答
我會為每個讀者分配 hazard slot。pop 先讀 head、發布 hazard、再次讀 head，只有一致才讀 next 並 CAS；失敗就清除並重試。摘除成功後節點進入退休清單，掃描全部 hazard 後只回收未受保護節點。退出要清除 slot 並移交清單，ABA 用版本計數或 tagged pointer 另行解決。測試高競爭、重用、退出和例外，檢查 use-after-free、掃描成本與尾延遲。
常見錯誤
- 錯誤： 讀 head 後直接存取節點。→ 原因： 發布保護前節點可能已被回收。→ 改進： 發布 hazard 後重新確認 head。
- 錯誤： CAS 成功後立即 delete。→ 原因： 其他讀者仍可能持有保護窗口。→ 改進： 先退休，掃描後回收。
- 錯誤： 認為 hazard pointer 自動解決 ABA。→ 原因： 延後回收不保證邏輯版本不變。→ 改進： 使用版本計數或 tagged pointer。
- 錯誤： 只用 relaxed 原子。→ 原因： 可能缺少發布與確認的可見性。→ 改進： 明確 acquire/release 與 happens-before。
追問與回答
追問 1：為什麼要重新讀 head？
第一次讀取到發布 hazard 之間存在窗口，其他執行緒可能摘除並回收節點。重新確認保證發布時節點仍是 head，否則重試。
追問 2：掃描時新發布 hazard 會被漏掉嗎？
正確協定要求讀者先發布再確認，確認失敗就重試。只要所有讀者遵守協定，退休且不在保護集合的節點才可回收。
追問 3：退休清單會無限增長嗎？
讀者長時間持有 hazard、執行緒停止或掃描太少時可能增長。設定閾值、監控峰值並確保退出清理，必要時由回收執行緒主動掃描。
追問 4：hazard pointer 與 epoch-based reclamation 如何選？
Hazard pointer 精確保護少量地址，適合動態讀路徑，但掃描 slot 成本較高。Epoch 批量回收效率高，卻可能被停頓執行緒拖住。依讀者數量、停頓容忍度和記憶體上限選擇。