1.4 - 进程（线程）同步

一篇围绕进程与线程同步展开的学习笔记。

在 进程（线程）调度 中已讨论多执行实体如何共享 CPU。本篇聚焦多执行实体共享数据与资源时的执行次序约束。实践部分位于 POSIX同步 API。

同步的动机 ​

1. 共享资源的竞争条件 ​

同步首先处理共享资源上的竞争条件（race condition）。当多个进程或线程并发访问同一份数据，而结果又依赖于具体交错顺序时，程序就可能得到错误结果。

counter++ 是最典型的例子。它在底层往往会被拆成下面三个步骤：

mov eax, [counter]
add eax, 1
mov [counter], eax

如果两个线程都在第一条指令时读到了相同的旧值，最后就只会写回一次加一后的结果。问题不在于语句看起来只有一行，而在于这三个步骤之间允许被别的执行流插入。同步在这里解决的是互斥访问：同一时刻只允许一个执行流修改这份共享状态。

2. 线程执行的先后顺序 ​

同步不只处理“不能同时做”，还处理“必须按顺序做”。

例如，一个线程负责初始化全局配置、连接池或缓冲区，另一个线程负责真正使用这些对象。即使两者并不同时修改同一块内存，后者也必须等前者完成初始化之后才能继续。

同步机制 ​

1. 硬件同步原语 ​

同步的最底层依赖硬件提供的原子读改写操作。常见抽象包括 test_and_set、compare_and_swap 等。它们的共同点是：读取旧值与写入新值作为一个不可分割的操作完成，因此不会在中间被别的 CPU 插入。

高层同步工具几乎都建立在这类原语之上。用户程序通常不会直接围绕这些原语手写同步逻辑，而是通过它们构造锁、信号量和其他同步对象。

2. 锁 ​

锁的作用是为临界区提供互斥。一个线程获取锁之后，其他线程在锁释放前不能进入同一段受保护代码。

如果获取失败后持续轮询，这就是忙等待，也就是自旋锁（spinlock）；如果获取失败后睡眠并让出 CPU，这就是阻塞式锁。前者适合极短临界区，后者适合等待时间不可忽略的场景。

3. 信号量 ​

信号量（semaphore）是一个通过原子操作维护的计数器，核心操作通常记为 wait 和 signal。

当信号量用于互斥时，它往往初始化为 1；当信号量用于资源计数时，它的初值可以大于 1，表示系统中同时可用的资源实例数；当信号量用于表达顺序时，它的初值常为 0，表示条件尚未满足。相较于锁，信号量更适合表达“有多少个资源可用”以及“某个事件是否已经发生”。

例如

sem_t mutex; 
void init()
{
    sem_init(&mutex, 0, 1);
}

void* consume(void* arg)
{
    sem_wait(&mutex);
    /* critical section */
    sem_post(&mutex);
}

4. 条件变量 ​

条件变量（condition variable）用来表达“条件不满足就等待，条件满足再继续”。它本身不提供互斥，因此通常与锁一起使用。

典型场景是生产者消费者模型。消费者拿到锁之后发现队列为空，此时它不应该继续自旋，也不应该在持锁状态下等待，而是应当睡眠，等生产者放入数据后再被唤醒。条件变量正是用来表达这种等待条件的工具。具体 API 位于后文的 POSIX同步 API。

同步的副作用 ​

1. 忙等待与阻塞等待 ​

忙等待（busy waiting）要求线程反复检查条件是否成立，在等待期间仍然占用 CPU。阻塞等待（blocking）则会把线程挂起，让调度器切换到其他可运行线程。

前者避免了睡眠和唤醒的开销，因此只适合等待极短、持锁时间极短的临界区；后者能够避免空转，更适合用户态程序中的一般同步场景。很多同步设计的改进，本质上就是把“自旋等”改成“条件不满足时阻塞等”。

2. 饥饿 ​

饥饿（starvation）是指线程虽然没有进入死锁，但长期拿不到锁、资源或 CPU，从而一直得不到执行机会。

它通常不是由互斥本身引起，而是由不公平的调度或不公平的唤醒策略引起。例如，读者持续到来时，作者可能长期得不到写锁；高优先级线程频繁抢占时，低优先级线程也可能长期推进缓慢。

3. 优先级反转 ​

优先级反转（priority inversion）是更具体的一类同步问题。低优先级线程持有锁，高优先级线程等待这把锁，而中优先级线程又不断抢占低优先级线程，结果是高优先级线程被间接拖住。

它的关键不在于高优先级线程直接被谁阻塞，而在于锁把调度层的优先级关系传递到了资源依赖关系中。常见缓解方式是优先级继承协议（ priority inheritance）：低优先级持锁者临时继承更高优先级，直到释放锁为止。

死锁 ​

1. 死锁的形成条件 ​

死锁是指一组进程或线程互相等待对方占有的资源，最终都无法继续推进。

死锁形成通常要求同时满足四个条件： 互斥、占有并等待、非抢占、循环等待。

最典型的例子是线程 T1 先拿到锁 L1 再等待 L2，线程 T2 先拿到 L2 再等待 L1。两者都持有一部分资源，又都等待对方释放，于是系统停在原地。

2. 死锁检测 ​

死锁检测的思路不是事先阻止资源分配，而是在系统运行过程中判断当前是否已经形成等待环。

资源分配图（resource-allocation graph ）是最常见的描述工具。若每类资源都只有一个实例，图中出现环就意味着死锁（充要条件）；若某些资源有多个实例，图中有环只说明系统可能死锁（必要不充分条件）。 资源分配图的画法可以压缩为下面几条：

其中，P 表示进程或线程节点集合，R 表示资源类型节点集合。

表示申请边（request edge），即执行实体 $P_i$ 正在等待资源 $R_j$ 的某个实例。

表示分配边（assignment edge），即资源 $R_j$ 的某个实例已经分配给 $P_i$。

如果某类资源有多个实例，通常会在资源节点旁画出多个小圆点，分别表示不同实例。下面三张图分别对应：单实例资源形成环并死锁、多实例资源形成环并死锁、多实例资源形成环但未死锁。

单一实例包含环死锁

多实例包含环死锁

多实例包含环但未死锁

3. 死锁避免：银行家算法 ​

银行家算法（banker's algorithm）属于死锁避免，而不是死锁检测。它的核心做法是在每次资源分配前检查：分配完成后，系统是否仍然处于安全状态；如果答案是否定的，就拒绝这次分配。

这部分推演较长，本篇不展开，直接给出参考文章：银行家算法。

4. 死锁预防 ​

死锁预防的思路是主动破坏四个必要条件中的至少一个：

工程上最常见的方法是统一加锁顺序，因为它直接针对循环等待条件，而且实现成本最低。

5. 死锁恢复 ​

如果系统选择“允许死锁发生，再检测并处理”，那么最后就需要恢复。最直接的方法是终止一个或多个死锁进程，让它们释放资源；另一类做法是回滚到某个安全状态后重新执行。

小结 ​

同步处理的其实是两类约束：共享资源上的互斥访问，以及执行流之间的先后顺序。硬件同步原语提供基础能力，锁、信号量和条件变量把这些能力组织成可用的同步工具；而忙等待、饥饿、优先级反转和死锁，则是同步引入的典型副作用。

接下来的 POSIX同步 API 会把这些概念与 pthread_mutex_t、pthread_cond_t、 sem_t 和 pthread_rwlock_t 等具体接口相结合。