E_同步与死锁

E — 同步与死锁

多线程/多进程共享数据时，需要同步机制确保数据一致性。

临界区与互斥

临界区（Critical Section）是访问共享资源的代码段。互斥（Mutual Exclusion）保证同一时刻只有一个线程在临界区中。实现互斥需要：

互斥性：最多一个线程在临界区
前进性：如果没有线程在临界区，想进去的线程要能进去
有限等待：等待进入的线程不会被无限期阻塞

锁

自旋锁（Spinlock）

线程不断循环检查锁是否可用。适合临界区极短的情况，因为避免了上下文切换的开销：

// 伪代码
void spin_lock(int *lock) {
 while (atomic_test_and_set(lock, 1) == 1)
 /* 自旋等待 */;
}
 
void spin_unlock(int *lock) {
 *lock = 0;
}

缺点：在单核上自旋锁毫无意义（占用 CPU 无法释放锁），在多核上若临界区较长则浪费 CPU。

对数据结构的应用：无锁数据结构（如无锁队列、无锁栈）用 CAS 指令替代自旋锁，减少忙等。实现的复杂度远高于加锁，但高竞争场景下性能更优。有兴趣深挖见跳表和现代 C++ 中的 std::atomic。

互斥锁（Mutex）

若锁已被占用，调用线程进入睡眠（阻塞态），让出 CPU。锁被释放后唤醒等待线程：

// 伪代码
void mutex_lock(Mutex *m) {
 if (atomic_test_and_set(&m->locked, 1))
 block_current_thread(); // 阻塞，让出 CPU
}
 
void mutex_unlock(Mutex *m) {
 m->locked = 0;
 wake_one_waiting_thread();
}

用户态 mutex（如 Linux 的 futex）：仅在发生竞争时才进入内核态做阻塞/唤醒，无竞争时在用户态用原子操作完成，极快。

信号量（Semaphore）

支持多个线程同时进入受保护区域（计数信号量），或作为锁使用（二进制信号量）：

操作	描述
`sem_wait` (P)	若计数 > 0，减 1 继续；否则阻塞
`sem_post` (V)	计数加 1，若有等待线程则唤醒一个

经典应用：生产者-消费者模型中用信号量控制缓冲区满/空状态。

条件变量（Condition Variable）

配合 mutex 使用，让线程等待”某个条件成立”：

// 伪代码：生产者-消费者
mutex_lock(&m);
while (buffer_is_full())
 cond_wait(&cond, &m); // 释放 mutex 并阻塞，被唤醒后重新获取 mutex
buffer_add(item);
cond_signal(&cond); // 唤醒一个等待者
mutex_unlock(&m);

死锁（Deadlock）

四个必要条件（Coffman，1971）：

条件	含义
互斥	资源一次只能被一个线程持有
占有且等待	持有某个锁的线程在等待另一个锁
不可剥夺	锁不能被强行拿走，只能由持有者释放
循环等待	线程 A 等线程 B 的锁，B 等 C 的锁，…，最终回到 A

破坏任一条件即可预防死锁：

破坏”占有且等待”：一次性申请所有需要的锁
破坏”循环等待”：给所有锁定义全序，始终按固定顺序加锁（Lock Ordering）

对数据结构的应用：在需要同时操作两个容器（如从一个 list splice 到另一个 list）时，锁定顺序很重要。如果锁的顺序不一致，死锁潜伏在代码中。

本章与其他模块的链接

原子操作 CAS → C_线程与并发 > 原子操作
信号量在生产——消费模式中的应用 → 队列 Queue
死锁在并发数据结构中的实例 → 并发树的锁策略

RootStack

探索