2.3.8 同步与互斥【2009 统考真题】

好的，我们来详细解析这道经典的操作系统同步与互斥问题。这是一道非常典型的“生产者-消费者”问题的变种，理解了它，就等于掌握了一大类题目的解法。

第一步：重述题目原文

【2009 统考真题】三个进程 P₁, P₂, P₃ 互斥使用一个包含 N (N>0) 个单元的缓冲区。P₁ 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元；P₂ 用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数；P₃ 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义（要求用伪代码描述）。

第二步：知识体系是什么？

这道题的核心知识点是 “进程的同步与互斥”，具体考察的是操作系统中最经典的进程协作模型之一——“生产者-消费者问题”。

基本模型：

生产者 (Producer)：负责生产数据（资源）并放入一个共享的缓冲区。消费者 (Consumer)：负责从缓冲区中取出数据（资源）并使用它。缓冲区 (Buffer)：一个有限大小的共享数据区域，用于解耦生产者和消费者的速度差异。

本题的变种：

一个生产者 (P₁)：它生产所有类型的数据（整数）。两个专门的消费者 (P₂ 和 P₃)：P₂ 只消费“奇数”这种特定资源，而 P₃ 只消费“偶数”这种特定资源。这种“一对多”且“消费者有偏好”的模式是本题的关键。

核心工具：信号量 (Semaphore)

信号量是一个特殊的整型变量，用于管理对公共资源的访问。它只能通过两个原子操作来访问：
P操作 (wait 或 down)：申请一个资源。如果信号量值 > 0，则将其减1并继续执行。如果信号量值 = 0，则进程阻塞，直到有其他进程释放资源。V操作 (signal 或 up)：释放一个资源。将信号量值加1。如果有进程因该信号量而阻塞，则唤醒其中一个。

第三步：解题套路是什么？

解决所有这类问题，都有一个清晰、固定的思考套路。

套路一：识别角色和资源

生产者：P₁消费者：P₂, P₃共享资源：大小为N的缓冲区。

套路二：分析关系，定义信号量

分析进程之间存在哪几种制约关系，并为每种关系定义一个信号量。

互斥关系 (Mutual Exclusion)：

关系描述：缓冲区是临界资源，任何时候只允许一个进程对它进行物理操作（put, getodd, geteven）。解决方案：定义一个互斥信号量 mutex，初值为1。1表示临界区可用，0表示临界区被占用。semaphore mutex = 1; // 用于保证对缓冲区的互斥访问

同步关系 (Synchronization)：

关系描述1：生产者 vs. 缓冲区

P₁ 想要放入数据，必须得有空闲的缓冲区单元。解决方案：定义一个资源信号量 empty，用于统计“空闲缓冲区”的数量。初值为N，因为一开始所有缓冲区都是空的。semaphore empty = N; // 记录空闲缓冲区的数量

关系描述2：消费者 vs. 生产者 (本题核心)

P₂ 想要取奇数，必须得缓冲区里有奇数。P₃ 想要取偶数，必须得缓冲区里有偶数。注意：这里不能使用一个简单的 full 信号量（代表缓冲区中产品的总数），因为它无法区分产品是奇数还是偶数。如果 P₂ 被 full 唤醒，但缓冲区里全是偶数，它还是得继续等待，这不符合同步的要求。解决方案：必须把产品分类计数！定义两个资源信号量 odd 和 even。semaphore odd = 0; // 记录缓冲区中奇数的数量semaphore even = 0; // 记录缓冲区中偶数的数量它们的初值都是0，因为一开始缓冲区是空的，没有任何产品。

套路三：梳理流程，安排P/V操作

为每个进程设计伪代码，并在正确的位置插入P、V操作。

P₁ (生产者)：

produce() 一个数 x。缓冲区有空位吗？申请一个空位：P(empty)。准备操作缓冲区，加锁：P(mutex)。put(x) 把 x 放入缓冲区。操作完毕，解锁：V(mutex)。通知对应的消费者。如果 x 是偶数，就 V(even)；如果是奇数，就 V(odd)。

P₂ (奇数消费者)：

缓冲区有奇数吗？申请一个奇数：P(odd)。准备操作缓冲区，加锁：P(mutex)。getodd() 取出一个奇数。操作完毕，解锁：V(mutex)。通知生产者，我消费完了一个，多出了一个空位：V(empty)。countodd() 统计。

P₃ (偶数消费者)：

逻辑与 P₂ 完全对称，只是把 odd 换成 even。

第四步：为什么是这样？（深度剖析）

为什么需要三个同步/资源信号量 (empty, odd, even)？

因为这道题存在三种不同的资源需要被“计数”和“等待”：空槽位、奇数产品、偶数产品。每一种需要被等待的资源，都应该有一个与之对应的信号量。这是设计信号量的核心原则。

为什么 P 操作的顺序至关重要？（P(odd) 必须在 P(mutex) 之前）

这是本题最关键、最容易出错的地方，也是**“黄金法则”**：同步P操作永远在互斥P操作之前。假设顺序反了：消费者 P₂ 先执行 P(mutex)，成功锁住了缓冲区。然后它执行 P(odd)，发现 odd 是0，于是 P₂ 阻塞。灾难发生：P₂ 现在既占着锁 (mutex)，又在等待奇数 (odd)。此时，唯一能生产奇数来唤醒它的 P₁ 却无法执行，因为它在 put 之前需要先 P(mutex) 获取锁，但这个锁被阻塞的 P₂ 占着。结果：P₁ 和 P₂ 互相等待对方持有的资源，形成死锁 (Deadlock)。正确顺序：先 P(odd)，确认有奇数资源后，再去 P(mutex) 申请对缓冲区的独占访问，这样就永远不会发生死锁。

为什么 V 操作的顺序相对不那么重要？

V(mutex) 应该尽早执行，以尽快释放临界区，让其他进程可以进入。在 V(mutex) 之后执行 V(empty) 或 V(odd) 等，不会引发死锁问题，只是会稍微降低一点并发性，但在考研题目中通常不作区分。标准答案的写法（先 V(mutex)）是最佳实践。

第五步：考试怎么解决？（实战指南）

拿到题目，不要慌，按以下步骤写在草稿纸上：

第一分钟：定角色，定资源。

写下：P1=生产(奇/偶)，P2=消费(奇)，P3=消费(偶)，共享资源=缓冲区(N)。

第二分钟：定信号量。

问自己：“需要互斥吗？” -> 是，访问缓冲区 -> semaphore mutex = 1;问自己：“生产者需要等什么？” -> 等空位 -> semaphore empty = N;问自己：“消费者需要等什么？” -> P2等奇数，P3等偶数 -> semaphore odd = 0;, semaphore even = 0;

第三分钟：搭框架。

写出 cobegin ... coend 结构，以及三个进程的 while(true) 循环框架。

第四、五分钟：填代码。

生产者P1：按“生产->P(空位)->P(锁)->放入->V(锁)->V(产品)”的模板填空。注意V(产品)要根据奇偶性选择。消费者P2/P3：按“P(产品)->P(锁)->取出->V(锁)->V(空位)->消费”的模板填空。

第六分钟：检查与注释。

检查死锁：仔细检查每个进程，确保所有的 P(同步) 都在 P(mutex) 之前。这是最重要的得分/丢分点。写注释：按照题目要求，在定义每个信号量时写上一句注释，说明其含义。这是白送的分，不能丢。

遵循这个流程，你就能在考场上冷静、快速、准确地解决这类问题。

好的，遵照您的要求，在详细讲解了知识体系、解题套路和背后原理之后，这里为您呈现这道题目的完整、规范的“标准答案”。这可以作为您在考试中书写的范本。

【标准答案】

1. 信号量定义及含义

为了实现三个进程的同步与互斥，需要定义四个信号量，含义如下：

互斥信号量 mutex：

含义：用于保证 P₁, P₂, P₃ 对共享缓冲区的互斥访问。初值：1。表示在初始状态下，允许一个进程访问缓冲区。

资源信号量 empty：

含义：用于记录共享缓冲区中空闲单元的数目。初值：N。表示在初始状态下，缓冲区全部为空。

资源信号量 odd：

含义：用于记录共享缓冲区中奇数的数目。初值：0。表示在初始状态下，缓冲区中没有奇数。

资源信号量 even：

含义：用于记录共享缓冲区中偶数的数目。初值：0。表示在初始状态下，缓冲区中没有偶数。

2. 进程同步与互斥的伪代码实现


// 信号量定义及初始化
semaphore mutex = 1;      // 缓冲区互斥访问信号量
semaphore empty = N;      // 缓冲区空闲单元数
semaphore odd = 0;        // 缓冲区中奇数个数
semaphore even = 0;       // 缓冲区中偶数个数
int x;                    // 临时存放生成的整数

// 三个并发进程
cobegin {

    // 生产者进程 P1
    Process P1() {
        while (True) {
            x = produce();          // 生产一个正整数

            P(empty);               // 申请一个空闲缓冲区单元
            P(mutex);               // 申请进入临界区
            put(x);                 // 将x放入缓冲区
            V(mutex);               // 释放临界区

            if (x % 2 == 0) {
                V(even);            // 唤醒P3，通知有一个偶数可取
            } else {
                V(odd);             // 唤醒P2，通知有一个奇数可取
            }
        }
    }

    // 奇数消费者进程 P2
    Process P2() {
        while (True) {
            P(odd);                 // 等待缓冲区中有奇数
            P(mutex);               // 申请进入临界区
            getodd();               // 从缓冲区取出一个奇数
            V(mutex);               // 释放临界区
            V(empty);               // 释放一个空闲缓冲区单元

            countodd();             // 统计奇数个数
        }
    }

    // 偶数消费者进程 P3
    Process P3() {
        while (True) {
            P(even);                // 等待缓冲区中有偶数
            P(mutex);               // 申请进入临界区
            geteven();              // 从缓冲区取出一个偶数
            V(mutex);               // 释放临界区
            V(empty);               // 释放一个空闲缓冲区单元

            counteven();            // 统计偶数个数
        }
    }

} coend