同步、互斥与死锁

同步与互斥

• 互斥（mutual exclusion）：同一时刻最多一个执行单元进入临界区访问某共享资源，避免竞态条件。
• 同步（synchronization）：协调多个执行单元的先后顺序，使某个操作在条件满足后才进行，例如“消费者等待生产者放入数据”。

临界区的基本结构：

进入区：获取锁 / 等待条件
临界区：访问共享资源
退出区：释放锁 / 通知等待者

正确的并发程序不只要互斥，还要保证进展性和有限等待，避免死锁、活锁与饥饿。

常用同步原语

互斥锁（mutex）

互斥锁只有“已锁/未锁”两种基本状态，持锁者退出临界区时释放。适合保护共享数据结构。必须用 RAII（如 C++ 的 std::lock_guard、std::unique_lock）保证异常或提前返回时释放锁。

自旋锁（spinlock）

获取不到锁时不睡眠而循环检查。它避免线程休眠/唤醒开销，适合临界区极短且不能睡眠的场景（如内核部分路径）；竞争时间长会浪费 CPU，不宜用于普通长操作或 I/O。

自旋锁通常依赖原子读改写指令（如 CAS）实现，但“用了 CAS”不自动等于应该自旋；std::mutex 的实现也可能先短暂自旋、再通过 futex 等机制睡眠。选择依据是临界区长度、竞争程度、可否睡眠和 CPU 预算，而不是“自旋锁一定更快”。单核系统上，若持锁者不能运行，自旋者只会浪费整个时间片；必须依赖抢占或避免这种设计。

读写锁（RWLock）

多个读者可并行持有读锁；写者独占。读远多于写时可提高吞吐，但需选择读优先、写优先或公平策略，避免一方饥饿。

信号量（semaphore）与 P/V 操作

信号量是非负计数与等待队列的组合：

• P / wait / down：原子地尝试将计数减一；若无可用资源则阻塞；
• V / signal / up：原子地将计数加一，并在需要时唤醒等待者。

计数为 1 的二元信号量可实现互斥；计数为 N 的信号量可表示 N 个同类资源或控制并发量。

条件变量（condition variable）

条件变量不存储“条件本身”，它让线程在某个谓词不满足时原子地“释放互斥锁并睡眠”。被唤醒后必须重新获得锁并在循环中重新检查条件，以应对虚假唤醒和竞争：

std::unique_lock lock(mutex);
cv.wait(lock, [&] { return !queue.empty(); });
auto item = queue.front();

如何选择原语

需求	常用原语	关键边界
单一共享状态的互斥修改	mutex	临界区短；不持锁执行慢 I/O 或回调
等待“队列非空/任务结束”等谓词	mutex + 条件变量	改变谓词时持锁，等待端必须使用谓词循环
限制 N 个并发资源/连接	计数信号量	计数表示可用额度，不替代数据结构本身的互斥
读多写少且读操作确实并行	读写锁	关注写者饥饿和读锁持有时间
极短、不可睡眠的临界区	自旋锁	竞争或持锁时间稍长就会浪费 CPU
单个简单变量	原子类型	仍要设计内存序和复合不变量，不能把多步操作误当原子

死锁

死锁是多个执行单元相互等待对方持有资源，且都不能继续推进的状态。经典 Coffman 必要条件同时成立才可能产生死锁：

1. 互斥：资源不能同时被多个执行单元使用；
2. 请求并保持：持有资源的同时继续申请新资源；
3. 不可剥夺：资源不能被强制收回；
4. 循环等待：形成等待资源的环。

应对方式

• 预防：破坏必要条件，例如按全局固定顺序申请多个锁、一次性申请资源、允许可回收资源。
• 避免：在分配时判断系统是否仍处于安全状态，例如银行家算法（理论/特定场景）。
• 检测与恢复：建立等待图或资源分配图检测环；发生后重试、回滚、抢占资源或终止部分任务。
• 工程实践：缩短临界区；不在持锁时做阻塞 I/O；统一锁顺序；使用 std::scoped_lock 一次锁多个 mutex；设置超时/取消和可观测性。

银行家算法：安全状态而不是“已经死锁”

银行家算法适用于系统知道每个任务最大资源需求的模型。对每类资源维护：

Available：当前可用资源
Allocation：每个任务已持有资源
Max：每个任务声明的最大需求
Need = Max - Allocation：任务完成前还可能需要的资源

做一次安全性检查：从 Work = Available 开始，找一个满足 Need[i] <= Work 的未完成任务；假设它拿到所需资源并运行结束，然后将其已持有资源归还，即 Work += Allocation[i]。若可以依次让全部任务完成，则存在安全序列，系统处于安全状态；否则分配这次请求会使系统进入不安全状态，应延迟或拒绝。

它的价值是解释“分配资源前先验证未来仍能让所有任务完成”。现实通用操作系统通常难以要求任意程序提前声明准确最大需求，因此更常采用锁顺序、超时/取消、资源限额、检测与重试等工程手段。不安全状态只表示存在死锁风险，不等价于已经死锁。

常见并发问题

• 竞态条件：结果依赖不可控的执行交错；用正确同步、原子操作或无锁设计解决。
• 活锁：任务都在响应对方而持续重试，状态不断变化但没有进展；常用随机退避等方式缓解。
• 饥饿：某任务长期得不到资源；需公平策略、优先级老化或限流。