进程同步与信号量

18 套卷子里这一支考了 13 道，是操作系统两道综合题里最稳定的一道，也是全卷最容易靠模板拿满分的一道——答案的形式几乎是固定的：一段信号量声明 + 一段伪代码。

设计方法本身（怎么找进程、找互斥、找同步、找资源数量）已经单独成页：同步问题设计。本页只讲考场上的落笔顺序和这 13 道题的分类。

知识框架概要

一、信号量只有三种，初值一眼就能定

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

二、P/V 的位置只有一条规矩

进入：先 P 资源信号量，再 P 互斥信号量
退出：先 V 互斥信号量，再 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 操作次序颠倒。永远是先 P 资源、再 P 互斥；先 V 互斥、再 V 资源。2019#43 里顺序反了就防不住死锁。
• 只用一个大锁把不冲突的操作也串起来。2017#46 中两个线程对同一变量都是读，不能互斥；评分标准直接封顶 2 分。
• 套完经典模型就交卷，漏掉本年的附加条件。2014#47 的评分说明写明「仅给出经典生产者-消费者问题的定义和伪代码最多给 3 分」。
• 初值当常数写。缓冲区里已经有东西、资源要减一防死锁，初值都得写成表达式（2015#45、2019#43）。
• 前趋关系题多设信号量。同一执行流内部的边要删掉，2022#46 只需两个信号量。
• 忙等类改错只改一半。进入区和退出区都有错时改一处得不到全分（2023#45）。
• 非临界动作留在互斥区里。生产、消费、参观、思考都应该在 V(mutex) 之后。

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