考研笔记

经典同步问题

这一节是第 2 章大题的落点。四个经典问题各自演示了一种典型的同步结构，它们的价值在于模式可迁移——考题很少原样考，但几乎总是这几个模式的变形。

按 2.3.4 的三步法读每一段代码：先看有哪些关系，再看设了哪些信号量及其初值，最后看 P/V 放在哪。

机制

生产者-消费者问题

问题：一组生产者和一组消费者共享一个容量为 的缓冲区。生产者往里放产品，消费者从里取。缓冲区满时生产者必须等，空时消费者必须等。

关系分析：

  • 互斥：缓冲区是临界资源，同一时刻只能有一个进程访问 → mutex = 1
  • 同步一：缓冲区满时生产者不能放 → 需要”空位”这个资源 → empty = n
  • 同步二：缓冲区空时消费者不能取 → 需要”产品”这个资源 → full = 0
semaphore mutex = 1;    // 互斥访问缓冲区
semaphore empty = n;    // 空闲缓冲区数量，初值 = n
semaphore full  = 0;    // 产品数量，初值 = 0
 
producer() {
    while (1) {
        生产一个产品;
        P(empty);           // 申请一个空位（同步）
        P(mutex);           // 进入临界区（互斥）
        把产品放入缓冲区;
        V(mutex);           // 离开临界区
        V(full);            // 产品数 +1（同步）
    }
}
 
consumer() {
    while (1) {
        P(full);            // 申请一个产品（同步）
        P(mutex);           // 进入临界区（互斥）
        从缓冲区取出产品;
        V(mutex);           // 离开临界区
        V(empty);           // 空位数 +1（同步）
        消费产品;
    }
}

这段代码有四处必须记牢的要点：

① empty 和 full 是一对此消彼长的量。 任何时刻 empty + full ≤ n。生产者消耗 empty 产出 full，消费者消耗 full 产出 empty。

② 两个 P 的顺序不能换。 必须先 P(empty) 再 P(mutex)。理由见 2.3.4 的”不要抱着锁睡觉”——若先拿 mutex 再发现没空位而阻塞，消费者就永远进不来腾空位，死锁。

③ 两个 V 的顺序可以换。 V(mutex) 和 V(full) 谁先都不会死锁，因为 V 永不阻塞执行者。

④ 生产和消费动作要放在临界区外。 生产一个产品 和 消费产品 都写在 P/V 之外，因为它们不访问缓冲区。放进临界区只会无谓延长互斥时间，降低并发度。

多生产者-多消费者问题

问题（盘子模型）：桌上有一个盘子，只能放一个水果。爸爸放苹果，妈妈放橘子，儿子专吃橘子，女儿专吃苹果。

关键在于识别：这里的”同步关系”是按品类分开的。

semaphore plate  = 1;   // 盘子里的空位，初值 1（盘子只能放一个）
semaphore apple  = 0;   // 盘中苹果数
semaphore orange = 0;   // 盘中橘子数
 
father()   { while(1){ 准备苹果; P(plate);  放苹果; V(apple);  } }
mother()   { while(1){ 准备橘子; P(plate);  放橘子; V(orange); } }
daughter() { while(1){ P(apple);  取苹果; V(plate); 吃; } }
son()      { while(1){ P(orange); 取橘子; V(plate); 吃; } }

为什么这里不需要 mutex？ 因为 plate 的初值是 1，它同时兼任了互斥的角色——任何时刻最多只有一个进程能通过 P(plate) 去访问盘子。

范围提示：这个”省掉 mutex”的简化只在缓冲区容量为 1 时成立。若盘子能放 个水果（plate = n），就必须重新加上 mutex = 1，否则多个进程会同时往盘子里放，产生竞态。这是本题最常见的变形考法。

吸烟者问题

问题：三个吸烟者各自拥有无限的一种原料（烟草 / 纸 / 胶水），供应者每次把另外两种放到桌上，拥有第三种的那个吸烟者才能卷烟抽。

这个问题演示的模式是”一对多的定向通知”——供应者要精确唤醒三者中的某一个。

semaphore offer1 = 0;   // 桌上是"纸+胶水"组合（对应吸烟者1有烟草）
semaphore offer2 = 0;   // 桌上是"烟草+胶水"组合
semaphore offer3 = 0;   // 桌上是"烟草+纸"组合
semaphore finish = 0;   // 吸烟完成的信号
int i = 0;
 
provider() {
    while (1) {
        if      (i == 0) V(offer1);
        else if (i == 1) V(offer2);
        else             V(offer3);
        i = (i + 1) % 3;
        P(finish);          // 等这一轮抽完才放下一组
    }
}
 
smoker1() { while(1) { P(offer1); 拿组合并卷烟; V(finish); 抽烟; } }
smoker2() { while(1) { P(offer2); 拿组合并卷烟; V(finish); 抽烟; } }
smoker3() { while(1) { P(offer3); 拿组合并卷烟; V(finish); 抽烟; } }

要点：finish 保证了供应者不会在上一轮还没抽完时就放下一组，桌子被当作容量为 1 的缓冲区使用。

读者-写者问题

问题：多个进程共享一个文件。读者之间可以同时读，但写者写时不允许任何其他进程（读者或写者）访问。

这个问题的特殊之处在于它不是简单的互斥——读-读之间是允许并发的，只有读-写、写-写才互斥。

版本一：读者优先（基本版）

semaphore rw    = 1;    // 保证读写互斥、写写互斥
semaphore mutex = 1;    // 保护 count 这个变量
int count = 0;          // 当前正在读的读者数量
 
writer() {
    while (1) {
        P(rw);
        写文件;
        V(rw);
    }
}
 
reader() {
    while (1) {
        P(mutex);
        if (count == 0) P(rw);      // 【第一个】读者负责上锁
        count++;
        V(mutex);
 
        读文件;
 
        P(mutex);
        count--;
        if (count == 0) V(rw);      // 【最后一个】读者负责解锁
        V(mutex);
    }
}

核心技巧是”计数 + 首尾负责制”：只有第一个到达的读者去 P(rw) 抢锁，只有最后一个离开的读者去 V(rw) 放锁。中间的读者直接进出，不碰 rw。这样就实现了”读者之间可并发”。

mutex 的作用是保护 count——如果没有它，两个读者可能同时读到 count == 0 从而都去执行 P(rw)，其中一个会被永久阻塞。

这个版本的问题：写者可能饥饿。 只要读者源源不断地到来，count 就永远不会归零，rw 就永远不会被释放，等在 P(rw) 上的写者永远进不去。

版本二：读写公平

疑问点：读写公平法的设计思想

读写公平的实现思路是什么？该方法不易凭直觉想到，其设计动机需要说明。

先看清版本一的漏洞究竟在哪，公平版的设计就自然了。

版本一中，写者在 P(rw) 上阻塞等待。而后来的读者根本不去碰 rw——它们发现 count > 0，就直接 count++ 然后去读了。也就是说：

读者有一条绕过写者的”捷径”，它们从等待的写者身边源源不断地插队进去。

要恢复公平，就得堵掉这条捷径。办法是设一个所有人都必须先通过的”闸门”信号量 w：

semaphore rw    = 1;    // 读写互斥
semaphore mutex = 1;    // 保护 count
semaphore w     = 1;    // 【新增】排队闸门：读者和写者都要先过这一关
int count = 0;
 
writer() {
    while (1) {
        P(w);               // ← 进闸门
        P(rw);
        写文件;
        V(rw);
        V(w);               // ← 出闸门（写完才出）
    }
}
 
reader() {
    while (1) {
        P(w);               // ← 进闸门
        P(mutex);
        if (count == 0) P(rw);
        count++;
        V(mutex);
        V(w);               // ← 出闸门（注意：登记完就出，不等读完）
 
        读文件;
 
        P(mutex);
        count--;
        if (count == 0) V(rw);
        V(mutex);
    }
}

这个设计有两个精心安排的点，缺一不可：

① 写者在整个写入期间一直持有 w。

注意写者的 V(w) 放在写完之后。这意味着：当写者卡在 P(rw) 上等读者退场时，它手里还攥着 w。于是后来的读者全部堵在 P(w) 这一关上，无法再进入去增加 count。捷径被堵死了。

② 读者只在”登记”期间持有 w，登记完立刻释放。

读者的 V(w) 放在 读文件 之前。这样一个读者登记完就把闸门让出来，下一个读者可以立刻进来登记并一起读——读者之间的并发性没有被破坏。

完整走一遍（这是理解该算法最快的方式）：

时刻事件wrwcount说明
1读者 R1 到达R1 持有→释放R1 持有1第一个读者上锁 rw，登记完释放 w，开始读
2写者 W 到达W 持有R1 占着1W 过了闸门，但卡在 P(rw)，并一直攥着 w
3读者 R2 到达被 W 挡住—1R2 堵在 P(w)，无法插队
4R1 读完W 仍持有R1 释放0最后一个读者解锁 rw
5W 获得 rwW 持有W 持有0写者终于开始写
6W 写完W 释放W 释放0R2 的 P(w) 这才通过

写者不会再被饿死。

一句话概括这个设计：w 是一道按到达顺序放行的闸门，它剥夺了读者”从等待的写者身旁溜进去”的特权。 而通过控制 V(w) 放置的位置——写者写完才放、读者登记完就放——同时保住了读者之间的并发。

这个版本严格说是”公平”而非”写者优先”：它只保证了不饿死，先到者先服务，并没有给写者更高的优先级。

版本三：写者优先

疑问点：如何实现真正的写者优先

若要求只要有写者在等待，后续读者一律让路，应当如何实现？

思路是给写者一个更强的武器：不是被动地排队，而是主动地把读者挡在门外。做法是让写者群体共同持有一个专门用来封锁读者的信号量 rd，采用与读者相同的”首尾负责制”：

semaphore rw     = 1;   // 读写互斥
semaphore mutexR = 1;   // 保护 countR
semaphore mutexW = 1;   // 保护 countW
semaphore rd     = 1;   // 写者用来封锁读者的信号量
int countR = 0, countW = 0;
 
writer() {
    P(mutexW);
    if (countW == 0) P(rd);     // 【第一个】写者到来就封锁读者入口
    countW++;
    V(mutexW);
 
    P(rw);
    写文件;
    V(rw);
 
    P(mutexW);
    countW--;
    if (countW == 0) V(rd);     // 【最后一个】写者离开才解封读者
    V(mutexW);
}
 
reader() {
    P(rd);                      // ← 只要有写者在（等待或正在写），这里就过不去
    P(mutexR);
    if (countR == 0) P(rw);
    countR++;
    V(mutexR);
    V(rd);
 
    读文件;
 
    P(mutexR);
    countR--;
    if (countR == 0) V(rw);
    V(mutexR);
}

关键在于 rd 被”写者群体”整体持有：第一个写者一到就 P(rd) 把读者入口封死，此后所有写者陆续进出，直到最后一个写者离开才 V(rd) 解封。只要还有任何一个写者在排队或写入，读者就一律被挡在 P(rd)。

代价是读者可能饥饿——只要写者不断到来，读者就永远进不去。这与版本一恰好互为镜像。

三个版本的实质区别，就在于”谁能插队”：

版本谁能插到对方前面谁可能饿死
一 · 读者优先读者（绕过 rw 直接 count++）写者
二 · 读写公平谁也不能（w 闸门按序放行）无
三 · 写者优先写者（用 rd 封锁读者入口）读者

哲学家进餐问题

问题：5 位哲学家围坐，相邻两人之间放 1 根筷子（共 5 根）。哲学家要同时拿起左右两根才能进餐。

这个问题演示的是死锁：若 5 人同时拿起左边的筷子，每人都持有一根、等待另一根，形成循环等待，全体死锁。这正是 2.4 死锁的经典模型。

三种解法，各自破坏死锁的不同必要条件：

① 限制人数：最多允许 4 位哲学家同时去拿筷子。

semaphore chopstick[5] = {1,1,1,1,1};
semaphore count = 4;                    // 最多 4 人同时尝试
 
Pi() {
    P(count);
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    进餐;
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    V(count);
}

道理：5 根筷子分给 4 个人，必有一人能拿到两根，循环等待就被打破了。

② 奇偶分流：奇数号哲学家先拿左边，偶数号先拿右边。

这样相邻两人会争抢同一根筷子，其中一人必然失败并让出，不会形成首尾相接的环。

③ 把”拿两根”变成原子操作：仅当左右两根筷子都可用时，才允许拿起。

semaphore mutex = 1;                    // 把取筷子过程变成互斥的
 
Pi() {
    P(mutex);
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    V(mutex);                           // 注意 V(mutex) 在两个 P 之后
    进餐;
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
}

道理：mutex 保证同一时刻只有一个人在拿筷子，他要么两根都拿到，要么一根也拿不到（阻塞在临界区内），不会出现”人人各持一根”的中间状态。

边界

各问题考的是什么模式

这四个问题的真正价值是模式，不是题目本身。 考试中出现的都是变形，认出模式就能套：

问题模式迁移场景
生产者-消费者缓冲区 + 一对此消彼长的资源信号量一切”有容量限制的传递”
多生产者-多消费者按品类拆分同步信号量多种数据流共用一个缓冲区
吸烟者一对多定向通知一个进程按轮次唤醒不同的对象
读者-写者计数 + 首尾负责制读读可并发、读写互斥的任何资源
哲学家进餐循环等待与死锁避免需要同时持有多个资源的场景

什么时候可以省掉 mutex

多生产者-多消费者的盘子模型里省掉了 mutex，但这不是通用简化。判据是：

当某个同步信号量的初值为 1，且它已经保证了”同一时刻只有一个进程能访问缓冲区”时，才可以省掉互斥信号量。

一旦缓冲区容量 > 1，同步信号量就不再能兼任互斥职责，必须补回 mutex。这是变形题的高频陷阱。

读者-写者中 mutex 保护的是什么

初学时容易以为 mutex 是用来保护文件的。不是——保护文件的是 rw。

mutex 保护的是 count 这个计数变量。如果不保护，两个读者可能同时读到 count == 0 并都去执行 P(rw)，导致其中一个被永久阻塞（因为只有一个能成功，另一个会阻塞在 rw 上，而它的 count++ 也没执行完）。

凡是”多个进程要读改写同一个计数器”的地方，都需要一个专门的互斥信号量。 这是可迁移的通用规则。

首尾负责制的两种用法互为镜像

读者-写者里出现了两次”首尾负责制”，方向正好相反：

  • 读者用它来共享资源：第一个读者 P(rw) 占住文件，最后一个读者 V(rw) 放开。目的是让同类之间能并发。
  • 写者用它来封锁对手（版本三）：第一个写者 P(rd) 封住读者入口，最后一个写者 V(rd) 解封。目的是把异类挡在外面。

同一个技巧，一个对内、一个对外。

对照速查

生产者-消费者值
mutex1（互斥访问缓冲区）
emptyn（空位数）
full0（产品数）
顺序纪律先同步 P 后互斥 P；V 可换序
读者-写者三版本新增信号量谁可能饿死
读者优先无写者
读写公平w = 1（闸门）无
写者优先rd = 1（封锁读者）读者
哲学家三解法手段
限制人数count = 4
奇偶分流奇数先左、偶数先右
原子取筷mutex 包住两次 P(chopstick)

考点

  • 生产者-消费者的三个信号量及初值，以及两个 P 不可换序
  • 生产/消费动作必须放在临界区之外
  • 读者-写者的计数 + 首尾负责制；mutex 保护的是 count 而非文件
  • 读写公平中 w 的作用：堵住读者绕过写者的捷径；写者写完才 V(w)，读者登记完即 V(w)
  • 三个版本各自谁会饿死
  • 哲学家进餐的三种解法及各自原理
  • 缓冲区容量为 1 时可省 mutex，容量 > 1 时必须补回

链接

反向链接