进程同步与信号量

进程同步题把并发执行中的约束写成程序。先弄清哪些动作可以同时做、哪些必须等待、资源最多允许多少人使用，再选择信号量和锁。银行、信箱、植树等场景会变，但这些约束可以逐条从题干中找出来。

这个板块包含哪些知识

进程与同步图谱从执行主体讲到共享状态，再讲等待和死锁。本页主要展开其中的同步设计：

• 并发与临界区：共享变量、读写冲突、竞态条件，以及一次操作是否需要整体保持一致。
• 同步原语：互斥锁、计数信号量、P/V 的原子性、忙等与阻塞。
• 经典问题：生产者消费者、读者写者、哲学家就餐，以及前趋关系。
• 死锁与推进条件：资源申请顺序、循环等待、限制并发数、安全状态。

设计前先把三种约束分开：互斥解决“不能同时进入”，同步解决“某事发生后才能继续”，计数解决“还剩多少许可”。同一资源可能同时涉及三种约束，不能看到一个共享对象就只设一个 mutex。

进程何时运行、阻塞和被唤醒，配合调度与状态转换；完整建模过程见同步问题设计。

常见考点与题型

综合题可能组合下面几类小问。先看要求求什么，再确定需要调用哪些知识。

解题前要弄清的关系

一、按用途区分信号量，初值由初态决定

对应原理见 信号量、常见信号量类型。

二、缓冲区模型中，避免持有互斥锁等待资源

进入：先 P 资源信号量，再 P 互斥信号量
退出：先 V 互斥信号量，再 V 资源信号量

若持有消费者也需要的 mutex 再等待空位，消费者就无法取出产品释放空位，可能死锁。仅保护共享状态更新，把不需要互斥的生产、消费等动作放在临界区之外，见 整理 P/V 位置。

三、用经典问题识别约束，再处理场景差异

1. 生产者消费者问题 —— 缓冲区、信箱、树坑都是它
2. 读者写者问题 —— 一读一写或两写才互斥，同读不互斥
3. 哲学家就餐问题 —— 附加资源用来防死锁

四、纯前趋关系可用通知与等待实现

一条边一个信号量，初值 0，操作前对所有入边 P、操作后对所有出边 V，见 实现前驱关系。同一个进程或线程内部的先后顺序不设信号量，语句次序已经保证了。

五、机制类小问的固定答法

wait/signal 本身要读写共享变量 S，所以必须原子；实现手段是关中断或 TAS/CAS 这类硬件指令，见 硬件互斥、原子性。开中断、关中断是特权指令，用户程序不能直接用。

六、要求「防死锁」时只查四个必要条件

互斥、占有并等待、不可剥夺、循环等待，它们是死锁的必要条件；预防死锁可破坏其中之一，不能仅凭题面同时可能满足四条就判定当前已死锁，见 死锁产生的必要条件、死锁预防。下面的真题采用限制并发数，其他场景也可按题设选择统一资源申请顺序等方法（2019#43 的 min(m, n−1)），银行家算法 属于死锁避免，需要检查试分配后是否仍有安全序列。

各类题的解法

前两条是所有题共用的落笔顺序，后三条按题型挑一条用。

先写声明段，再写代码

声明段本身就有分。参考答案的句式是固定的两句，一个信号量写一句：

互斥资源是 ____，因此设互斥信号量 mutex，初值 1；
____ 与 ____ 因为 ____ 而同步，设信号量 ____，初值 ____。

2013#45 的评分说明写明「信号量初值给 1 分，说明含义给 1 分」，两个信号量共 4 分——满分 8 分的题，一半在声明段上。若不想单列段落，也可以在每行 semaphore 后写注释交代含义，2015#45 的答案就是这种写法。

初值允许写成表达式，而且必须写成表达式：2015#45 里信箱已有 x 封邮件，空位就是 M − x 而不是 M；2019#43 里碗的数量是 min(m, n−1) 而不是 m。

按母题写骨架，再挂附加条件

semaphore mutex = 1;      // 互斥访问缓冲区
semaphore empty = N;      // 空位数
semaphore full  = 0;      // 产品数

producer() {
    while (true) {
        生产一个产品;      // 非临界动作，放在互斥区外
        P(empty); P(mutex);
        将产品放入缓冲区;
        V(mutex); V(full);
    }
}

附加条件可能改变等待位置、互斥范围或信号量数量，需要逐条重新建模。例如：

• 消费者必须连续取 10 件 → 加一个 consumer_mutex，用 for 包住取货循环（2014#47）
• n 个哲学家 m 个碗 → 加 plate = min(m, n−1)，在拿筷子之前先 P(plate)（2019#43）
• 一个生产者按奇偶唤醒两个消费者 → 加一对方向不同的同步信号量（2009#45）
• 取号之后还要等叫号 → 多一个握手信号量 service（2011#45）

要求防死锁的，答案后面必须补一句理由。2019#43 的口径是：限制至多 n−1 人同时抢筷子，就至少有一人能拿到两根。

前趋关系题只数边

1. 把约束逐条列成边：2020#45 是 A→C、B→C、C→E、D→E 四条；
2. 删掉落在同一执行流内部的边：2022#46 的 B→C 与 E→F 都在同一个线程里，删掉后只剩两条；
3. 剩下每条边一个信号量，初值 0，名字用端点缩写 SAC、SCE；
4. 代码里不写 mutex，也不写 while 循环——这类题是一次性过程。

共享变量冲突题逐格判定

1. 列出「每个线程对每个变量是读还是写」；
2. 套判据：一读一写、或两个都写，才互斥；同读不互斥；
3. 按需要整体保持一致的共享状态划分保护范围；要求最大并发时，避免把无冲突操作合并到大锁中；
4. 临界区收到最小范围，只夹住真正访问该变量的那条语句；
5. 一个线程要同时持有多个锁时，所有线程按同一次序加锁。

2017#46 因此要 3 个信号量，评分标准写明「仅使用一个互斥信号量，互斥代码部分最多给 2 分」。而 2024#46 要「尽可能少的信号量」，就得逐问重算：一读一写要 2 个，两个都只做同一种修改就只要 1 个。

判对错与改错题

1. 先复述这个机制该有的语义（哪几个动作必须原子）；
2. 逐个方案模拟最坏交错，找「谁再也没机会改这个变量」——2021#45 的方法一错在 S ≤ 0 时关着中断空转；
3. 改错要指名语句并守住「不增加语句」：2023#45 两处都要改，进入区 if 改 while，退出区 lock = TRUE 改 lock = FALSE；
4. 比较替代实现是否仍保证原子性；普通函数中相同的读写语句，并不自动具有原子指令的不可分割性；
5. 涉及开关中断就补一句「特权指令，用户态不可用」。

写完后：用等待链检查代码

检查每个 P(s)：许可由谁提供？对方执行到 V(s) 前，是否也在等待我当前持有的锁？例如缓冲区已满时，生产者先 P(mutex) 再 P(empty) 会持锁睡眠，消费者又拿不到 mutex，便无法取走产品，形成互等。

再检查每个许可是否被正确归还：放入产品后通知对应消费者，取出后释放空位；奇偶分流不能随意唤醒错误的一方。最后选“初始为空”“资源刚好耗尽”“两个线程交错执行”各推一次，确认正确性与题目要求的并发程度。

历年题索引

骨架和落笔顺序是通用的，下面这张表用于比较不同场景中的同步与资源约束。

易错清单

• 持有互斥锁等待别人释放资源。缓冲区模型通常先 P 资源再 P 互斥；释放时先解锁再通知，是便于分析且避免不必要竞争的写法，不应泛化为所有同步题的固定顺序。2019#43 里顺序反了就防不住死锁。
• 只用一个大锁把不冲突的操作也串起来。2017#46 中两个线程对同一变量都是读，不能互斥；评分标准直接封顶 2 分。
• 套完经典模型就交卷，漏掉本年的附加条件。2014#47 的评分说明写明「仅给出经典生产者-消费者问题的定义和伪代码最多给 3 分」。
• 初值当常数写。缓冲区里已经有东西、资源要减一防死锁，初值都得写成表达式（2015#45、2019#43）。
• 前趋关系题多设信号量。同一执行流内部的边要删掉，2022#46 只需两个信号量。
• 忙等类改错只改一半。进入区和退出区都有错时改一处得不到全分（2023#45）。
• 互斥范围过大。独立生产通常在加锁前，取出后的独立消费通常在解锁后；位置取决于共享访问发生在哪里。

上一页：I/O 计算；下一页：进程调度与状态转换。