题干与适用场景
你需要实现一个异步信号量，用于限制连接池或任务执行器的并发数。初始容量为 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。
- 把 Abort 或 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 需要选择。