題幹與適用場景
你需要實作一個非同步信號量，用於限制連線池或工作執行器的並發數。初始容量為 N，acquire() 沒有 permit 時排隊，release() 歸還一個 permit。等待者可以逾時或被取消；取消不能留下幽靈佇列項，也不能讓其他等待者永遠拿不到 permit。介面還要定義重複 release、關閉信號量和公平順序。
本題適合並發程式、執行時和後端基礎設施面試。Oracle 的 Semaphore API 明確定義 permit、可選公平 FIFO 選擇和可中斷取得；Python asyncio 文件說明信號量計數在 acquire 時遞減、release 時遞增，並區分普通與有界信號量；公開面試討論也把 counting semaphore 和資源並發上限列為作業系統面試主題。這些來源支援代表性，但不能證明某家公司固定使用該題或具體頻率。本題歸入 coding，因為核心考察是狀態不變量、佇列清理、取消競態與可驗證並發實作。
面試官考察點
第一，看候選人是否定義 permit 所有權。成功的 acquire 必須產生一個只能被一次 release 歸還的 token；取消或逾時的請求沒有 token，不能呼叫 release。
第二，看公平性是否真的實作。只要佇列非空，新 release 不能讓後來呼叫的 fast path 越過隊首；否則高負載下可能出現飢餓。公平 FIFO 需要在同一臨界區檢查佇列、分配 permit 和喚醒。
第三，看能否處理取消與喚醒同時發生：請求可能已被 release 選中，隨後 timeout；也可能 timeout 先把自己從佇列移除。實作必須讓兩條路徑競爭同一狀態，並保證最多一條路徑完成 waiter。
最後，看測試是否檢查並發上限、FIFO、逾時回收、取消後繼續前進、重複 release、關閉和工作例外，而不只是順序 acquire/release。
回答前需要釐清的問題
- 公平是嚴格 FIFO 還是盡力而為？ 嚴格 FIFO 會犧牲部分吞吐，卻能避免隊首等待者飢餓。
- acquire 回傳什麼？ 回傳 release token 或 lease 可把 permit 所有權綁定到一次成功取得，減少誤釋放。
- 取消發生在 permit 已分配之後怎麼辦？ 必須定義完成優先級；通常 promise 一旦 resolve，呼叫者擁有 token，取消只影響後續工作。
- release 多於 acquire 是錯誤嗎？ 有界信號量應拋錯或記錄錯誤；靜默增加計數會破壞容量不變量。
- 關閉時等待者如何結束？ 關閉應拒絕新請求，並以明確的 Closed 錯誤結束排隊者；已持有 token 的釋放仍要安全。
30 秒回答框架
「我維護 available、FIFO waiter 佇列和 closed 狀態，所有修改在一個臨界區完成。沒有等待者時 acquire 直接消耗 permit；一旦佇列非空，後來者必須排隊。release 優先從隊首找仍有效的 waiter，轉移一個 permit 並只完成它一次；沒有有效 waiter 才增加 available。每個 waiter 有取消標記和一次性完成狀態，逾時與 release 競爭同一狀態。成功 acquire 回傳 lease，lease 只能 release 一次。測試會強制 FIFO、取消與釋放同時發生、逾時後 permit 回收、重複 release、關閉和並發上限。」
分步深入解答
1. 寫出核心不變量
容量為 N 時，任意時刻必須滿足：available + held + reserved = N。available 是可直接分配的 permit，held 是已交給呼叫者的 lease，reserved 是已從 available 轉移給某個尚未完成回呼的 waiter。
每個 waiter 只有三種終態：pending、fulfilled 或 cancelled；終態只能設定一次。取消的 waiter 不擁有 permit，fulfilled 的 waiter 必須產生一個 lease。關閉不回收 held lease，但會阻止新的 acquire。
2. 公平 fast path 和佇列
當 waiters 為空且未關閉時，acquire 可以立即消耗 available。當佇列非空，即使 available > 0，新呼叫也必須排隊，否則新請求會越過舊請求。release 和 acquire 的佇列檢查必須在同一同步邊界完成。
佇列節點保存 waiter promise、取消狀態、逾時句柄和一次性完成函式。完成或取消後從佇列刪除，或保留 tombstone 由 release 在隊首惰性跳過；兩種策略都要證明不會讓有效 waiter 永久藏在無效節點之後。
3. release 如何轉移 permit
release 先確認 lease 未被釋放，再把 permit 交給隊首有效 waiter。此時 permit 從 held 變為 reserved，呼叫 waiter 的完成函式；不能先把 available 加一再非同步尋找 waiter，否則新 acquire 可能插隊。
如果隊首 waiter 已取消，跳過它並繼續找下一個；每跳過一個都完成清理。沒有有效 waiter 時才 available += 1。有界信號量應拒絕超過 N 的釋放，避免錯誤呼叫掩蓋洩漏或重複歸還。
4. 取消與逾時競態
取消回呼和 release 都可能嘗試結束同一個 waiter。用一次性 CAS、鎖內狀態檢查或等價機制保證只有一個獲勝者。取消獲勝時從佇列移除，不改變 available，因為它從未擁有 permit；如果 release 已經 reserved 給它，取消路徑不能再把 permit 加回並同時讓 release 完成它。
一種簡單規則是：release 在臨界區先把 waiter 標為 fulfilled，之後才 resolve；一旦 fulfilled，timeout 只能記錄「呼叫者放棄後續工作」，呼叫者仍需釋放收到的 lease。另一種規則是支援尚未交付的 reservation 回收，但必須把回收放在同一狀態機中，不能依賴 promise reject 後猜測。
5. lease 和重複 release
成功 acquire 回傳帶 released 標記的 lease，呼叫 lease.release() 時只允許從 false 變為 true。重複呼叫應回傳冪等結果或拋出明確錯誤，不能把兩個 permit 放回池中。把裸 release() 暴露給任意呼叫者會失去所有權關聯，除非介面明確採用計數模型並由呼叫者承擔責任。
6. 關閉、例外與背壓
關閉後拒絕新 acquire，並讓排隊 waiter 以 Closed 錯誤結束。已持有 lease 的工作仍可完成並釋放；release 不能因為 closed 就丟棄 permit，否則監控無法解釋 held 數量。工作例外也必須透過 finally 釋放 lease。
信號量限制並發，不等於限制佇列長度。無限 waiter 佇列會把背壓轉成記憶體增長；生產實作應提供最大等待數、逾時或拒絕策略，並記錄等待時長、取消率和佇列深度。
7. 用排程器控制測試
不要用真實 sleep 證明競態。測試應提供手動時鐘和可控 scheduler，讓場景在 acquire 排隊、release 選中 waiter、timeout 回呼已入隊但未執行等邊界暫停。每個步驟斷言 available、held、佇列有效 waiter 數和 lease 所有權。
至少涵蓋 N=0 的非法初始化、N=1 的嚴格 FIFO、多個 permit、取消隊首和中間 waiter、timeout 與 release 同時到達、重複 release、關閉前後 acquire、工作例外以及長時間等待者不會飢餓。
高品質示範回答
「我把 permit 所有權封裝成 lease。信號量保存 available、FIFO waiters 和 closed 狀態，所有狀態變化在一個同步邊界內完成。佇列為空時 acquire 才能直接扣減 available；只要有等待者，後來的呼叫必須排隊。
release 先確認 lease 只釋放一次，再在隊首尋找有效 waiter，把 permit 從 held 轉成該 waiter 的 reservation，隨後只完成它一次。隊首已取消時跳過並清理；沒有有效 waiter 才增加 available。取消和 timeout 與 release 競爭同一 waiter 狀態，獲勝者由一次性狀態轉換決定。取消前沒有拿到 permit，所以不增加 available；如果已完成 acquire，呼叫者擁有 lease，後續取消不能代替 release。
關閉拒絕新請求並結束排隊者，已持有 lease 仍可釋放。測試使用手動時鐘和排程器，強制 FIFO、隊首取消、中間取消、timeout 與 release 同時發生、重複 release、例外 finally 和並發上限，最後用計數不變量證明沒有遺失或憑空增加 permit。」
常見錯誤
- 佇列非空仍走 fast path → 新請求越過老請求造成飢餓 → 佇列非空時全部排隊。
- 取消 waiter 時直接增加 available → 該 waiter 可能已被 release 預留 → 取消與 release 競爭同一一次性狀態。
- 裸 release 沒有所有權 → 重複呼叫憑空增加 permit → 回傳只能釋放一次的 lease。
- 先增加 available 再喚醒隊首 → 新請求可能插隊 → 在同一臨界區直接轉移給 waiter。
- 把 timeout 當作已交付 lease 的回滾 → 工作仍在執行 → 區分等待取消與已獲得 permit。
- 無限等待佇列 → 並發限制變成記憶體洩漏 → 設定佇列上限、逾時或拒絕策略。
- 只測順序呼叫 → 取消競態和重複 release 沒有涵蓋 → 用可控 scheduler 強制邊界交錯。
- 關閉時丟棄 held permit → 資源計數無法收斂 → 允許已持有 lease 的 finally 釋放。
追問及應對
FIFO 公平一定更好嗎？
不一定。FIFO 防止飢餓且容易解釋，但隊首工作若需要很長時間或即將逾時，可能造成隊頭阻塞。吞吐優先的實作可以允許非公平 fast path，但必須把飢餓、最大等待時間和優先級寫進契約，而不是聲稱所有場景都應公平。
如何支援一次 acquire 多個 permit？
每個 waiter 記錄需求數量，只有 available 足夠時才能 fulfilled。嚴格 FIFO 會讓後面的一個 permit 請求等待前面的多 permit 請求，形成隊頭阻塞；允許跳過則犧牲公平。實作必須選擇一種策略，並在不變量中使用 reserved 的數量而非 waiter 個數。
工作取消後已經執行一半怎麼辦？
信號量只負責 permit，不負責中斷工作。呼叫者收到取消訊號後應停止工作，執行 lease 的 finally release；若工作不可中斷，仍需等待它釋放。不要讓信號量強行回收仍被使用的 permit。
信號量和 mutex 有什麼邊界？
信號量表示可用資源數量，permit 可以由不同執行者取得和釋放；mutex 表示互斥所有權，通常要求持有者解鎖。用初始值為 1 的信號量模擬 mutex 可能遺失所有權檢查和優先級語義，應根據 API 需求選擇。