程式設計面試：如何實作帶序號槽位的有界 MPMC 環形佇列？
題干與適用場景
多個生產者和消費者共享固定容量的記憶體佇列。生產者不能覆蓋尚未消費的元素，消費者不能讀取尚未發布的元素；高併發時希望快路徑不依賴互斥鎖，佇列滿或空時允許等待。請設計槽位布局、入佇列出佇列索引、記憶體序和關閉行為。
面試官考察什麼
- 能否用單調位置和每槽位序號區分「空」「已保留」「已發布」「已消費」。
- 能否正確使用 CAS、acquire/release 與非原子資料的可見性。
- 能否處理容量不是二次冪、生產者競爭、消費者競爭和偽共享。
- 能否說明等待、逾時、關閉、記憶體回收和 ABA 相關邊界。
回答前要釐清的問題
- 佇列元素是否固定大小，是否允許移動或存放指標？
- 滿載和空佇列是阻塞、逾時返回，還是立即返回失敗？
close後允許已入佇列元素繼續消費嗎？- 執行環境是否提供 C++20
atomic::wait/notify？ - 是否需要跨程序共享，還是只在一個程序內使用？
30 秒回答框架
我會讓入佇列和出佇列位置單調遞增，每個槽位保存一個與位置對應的序號。生產者用 CAS 取得入佇列位置後寫入非原子 payload，再用 release 發布序號；消費者用 acquire 觀察序號，讀取 payload 後以 release 標記槽位可供下一輪使用。位置差異決定槽位空滿，滿載和空佇列透過 atomic::wait 或有界退避等待，並把關閉狀態納入返回值。
分步驟深入解答
第一步：設計槽位和位置
容量為 N 的佇列使用單調 enqueuePos 和 dequeuePos，槽位索引為位置對 N 的映射。每個槽位保存 sequence 和 payload；序號攜帶該槽位屬於哪一輪，避免只看索引時把舊資料誤認為新資料。若容量不是二次冪，使用安全取模而不是位元遮罩。
第二步：生產者保留位置
生產者讀取候選位置對應槽位的序號。如果序號等於該位置，表示槽位可寫；透過 CAS 競爭 enqueuePos，失敗則重新讀取。若序號落後於期望值，表示佇列可能已滿，應返回滿載、等待或按逾時退出；不能繼續遞增位置搶佔未來槽位。
第三步：發布 payload
取得位置後，生產者獨佔該槽位並寫入 payload。寫入完成後用 release store 把 sequence 更新為「該位置已發布」。消費者必須用 acquire load 讀取序號，確認發布後再讀取非原子 payload；否則即使索引是原子的，仍可能看到未完成寫入。
第四步：消費者取出並釋放
消費者以類似方式 CAS 取得 dequeuePos。只有當槽位序號等於「該位置已發布」的期望值時才能讀取。讀取完成後用 release store 把序號設定為下一輪可寫的值；下一位生產者用 acquire load 觀察到它後才能覆蓋槽位。
第五步：定義記憶體序和偽共享
位置 CAS 需要保證索引更新的原子性，發布和釋放序號需要 release/acquire 建立 payload 的 happens-before。只使用 relaxed 會讓消費者讀到未發布資料。將生產者、消費者位置和熱點序號分散到不同快取行，減少並發寫入造成的偽共享。
第六步：處理等待與關閉
快路徑失敗時可用 atomic::wait 等待位置或序號變化，並由成功入佇列或出佇列執行緒呼叫 notifyone 或 notifyall。等待必須支援逾時和虛假喚醒。關閉狀態要原子發布：關閉後生產者拒絕新元素，消費者可選擇排空已發布元素後返回結束。
第七步：測試競爭和生命週期
測試容量為 1、非二次冪容量、生產者或消費者數量大於容量、長時間空滿交替和隨機延遲。用序列號驗證無遺失、無重複、FIFO 範圍和關閉排空；用 ThreadSanitizer 與壓力測試檢查資料競爭。若 payload 是指標，必須明確物件所有權和回收時機。
高品質示範回答
我會為每個槽位保存 payload 和單調 sequence，佇列維護單調入佇列、出佇列位置。生產者只有在序號等於本輪可寫值時才用 CAS 保留位置；寫完 payload 後 release 發布序號。消費者用 acquire 觀察發布序號，讀取後 release 寫入下一輪可寫序號。序號而非單純索引區分空滿和槽位輪次，容量不為二次冪時用取模。位置與序號分開對齊減少偽共享，快路徑失敗用 atomic::wait 加逾時和虛假喚醒循環。關閉後拒絕新生產，消費者按約定排空已發布元素；壓力測試、ThreadSanitizer 和序列校驗覆蓋競爭與生命週期。
常見錯誤
- 只用 head/tail 索引判斷空滿，無法區分槽位輪次和舊資料。
- 生產者 CAS 成功後還未寫完 payload，消費者就讀取資料。
- 用 relaxed 讀寫發布狀態，卻沒有 acquire/release 的可見性保證。
- 佇列滿時繼續遞增保留位置，導致覆蓋未消費元素。
atomic::wait不處理虛假喚醒、逾時和關閉，造成永久等待。- 忽略非二次冪容量、快取行偽共享和指標 payload 的回收。
追問及應對
追問一：為什麼每個槽位需要序號？
同一索引會被多個輪次重用。序號把槽位與絕對位置綁定，可區分本輪可寫、本輪已發布和下一輪狀態，避免舊值被誤判。
追問二：為什麼不能只給 payload 加原子類型？
payload 可能是複合物件，原子化索引不等於物件初始化完成。發布序號的 release 與讀取序號的 acquire 才能建立完整物件寫入的可見性。
追問三：CAS 競爭失敗應該自旋多久？
沒有固定值。短暫競爭可有限自旋，持續失敗應讓出 CPU 或等待序號通知；策略要按核心數、佇列容量和延遲目標壓測校準。
追問四：佇列關閉時如何保證不丟資料？
關閉先阻止新生產，再用 acquire 觀察並排空已發布槽位。只有入佇列位置追平出佇列位置且沒有保留中的生產者時，消費者才返回結束。
追問五：這一定是無鎖的嗎？
快路徑不使用互斥鎖，但 atomic::wait 可能由執行時阻塞執行緒。應準確描述為無鎖資料結構加可選阻塞等待，而不是承諾所有路徑都 lock-free。
追問六：如何驗證 ABA 風險？
讓位置單調遞增並在槽位保存輪次序號，使相同索引的不同輪次具有不同狀態。測試長時間 wraparound、延遲執行緒和重複 CAS，確認舊觀察值不能重新獲得有效資格。