2009年第45题
三个进程 P 1 P_1 P1、 P 2 P_2 P2、 P 3 P_3 P3 互斥使用一个包含 N ( N ﹥ 0 ) N~(N﹥0) N (N﹥0) 个单元的缓冲区。 P 1 P_1 P1 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中； P 2 P_2 P2 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数； P 3 P_3 P3 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
解析
本题主要考查操作系统中进程同步与互斥的知识，具体涉及以下核心概念：
-
信号量机制：
- 信号量是一种整数变量，用于控制多个进程对共享资源的访问，支持两个原子操作：
P()（也称为wait()，用于申请资源）和V()（也称为signal()，用于释放资源）。P操作减少信号量值，如果值小于 0 则阻塞进程；V操作增加信号量值，唤醒等待进程。 - 类型：
- 互斥信号量（二进制信号量）：确保只有一个进程进入临界区，初始值为 1。
- 计数信号量：表示可用资源的数量，初始值通常为资源总数（如空缓冲区单元数）。
- 作用：实现进程间的同步（协调执行顺序）和互斥（防止同时访问共享资源）。
- 信号量是一种整数变量，用于控制多个进程对共享资源的访问，支持两个原子操作：
-
互斥：
- 确保共享资源（如缓冲区）在任何时刻只被一个进程访问，防止数据竞争（race condition）。例如，当 (P_1) 写入缓冲区时，(P_2) 或 (P_3) 不能同时读取或写入。
- 实现方式：使用互斥信号量（如
mutex）包裹临界区代码。
-
同步：
- 协调进程的执行顺序，以满足特定条件。本题涉及两类同步：
- 生产者-消费者同步： P 1 P_1 P1（生产者）只能在有空位时放入数据； P 2 P_2 P2 和 P 3 P_3 P3（消费者）只能在有数据时取出数据。
- 数据类型条件同步： P 2 P_2 P2 只能取出奇数， P 3 P_3 P3 只能取出偶数，这要求额外的条件检查。
- 实现方式：使用计数信号量（如
empty、odd、even）表示资源可用性，进程通过P()和V()操作等待或通知。
- 协调进程的执行顺序，以满足特定条件。本题涉及两类同步：
-
生产者-消费者问题及其变种：
- 经典模型：一个生产者和一个消费者共享固定大小缓冲区，使用
empty和full信号量同步。 - 本题变种：多个消费者（ P 2 P_2 P2 和 P 3 P_3 P3）根据数据类型（奇偶）区分，需要扩展信号量（如
odd和even）来处理类型条件。 - 关键点：同步操作必须在互斥保护外执行（如先
P(empty)再P(mutex)），以避免死锁。
- 经典模型：一个生产者和一个消费者共享固定大小缓冲区，使用
-
死锁与饥饿避免：
- 死锁：进程互相等待而无法推进（如循环等待资源）。本题需确保信号量操作顺序合理（如先申请同步信号量，再申请互斥信号量）。
- 饥饿：某个进程长期得不到资源（如 P 2 P_2 P2 或 P 3 P_3 P3 因无奇/偶数而阻塞）。信号量的公平唤醒机制可缓解饥饿。
应用上述基本知识，再结合本题内容，可知：
- 互斥需求：缓冲区是共享资源，
put()、getodd()和geteven()操作需互斥执行。 - 同步需求：
- P 1 P_1 P1 受
empty限制（空单元不足时阻塞）。 - P 2 P_2 P2 受
odd限制（无奇数时阻塞）。 - P 3 P_3 P3 受
even限制（无偶数时阻塞）。
- P 1 P_1 P1 受
- 数据类型处理： P 1 P_1 P1 放入数据后需根据奇偶性通知对应消费者（通过
V(odd)或V(even)）。 - 统计操作：
countodd()和counteven()可能涉及共享计数器，需在互斥保护下执行。
有了上述分析之后，就可以按照如下步骤解题：
步骤 1: 定义信号量及其含义
mutex：互斥信号量，初始值为 1。确保任何时候只有一个进程访问缓冲区（临界区）。empty：计数信号量，初始值为 N N N。表示缓冲区中空单元的数量。 P 1 P_1 P1 在放入数据前执行P(empty)申请空单元； P 2 P_2 P2 或 P 3 P_3 P3 取出数据后执行V(empty)释放空单元。odd：计数信号量，初始值为 0。表示缓冲区中可用的奇数数量。 P 1 P_1 P1 放入奇数后执行V(odd)通知 P 2 P_2 P2； P 2 P_2 P2 取出前执行P(odd)等待奇数。even：计数信号量，初始值为 0。表示缓冲区中可用的偶数数量。 P 1 P_1 P1 放入偶数后执行V(even)通知 P 3 P_3 P3； P 3 P_3 P3 取出前执行P(even)等待偶数。
步骤 2: 伪代码实现
伪代码使用类 Pascal 语法，P() 和 V() 为信号量操作。假设 put()、getodd()、geteven()、countodd() 和 counteven() 函数已实现，其中：
put(num)：将正整数num放入缓冲区空单元。getodd()：从缓冲区取出一个奇数（需确保存在奇数）。geteven()：从缓冲区取出一个偶数（需确保存在偶数）。countodd()：增加全局奇数计数器（需互斥）。counteven()：增加全局偶数计数器（需互斥）。
// 初始化信号量
semaphore mutex = 1; // 互斥访问缓冲区
semaphore empty = N; // 空单元数量
semaphore odd = 0; // 可用奇数数量
semaphore even = 0; // 可用偶数数量// 全局缓冲区（假设已实现）
Buffer buffer; // 进程 P1: 生产者
void P1() {while(1) {int num = produce(); // 生成正整数P(empty); // 等待空单元（若无空位则阻塞）P(mutex); // 申请进入临界区（互斥）put(&buffer, num); // 将num放入缓冲区if(num % 2 == 1) // 判断奇偶性V(odd); // 通知有奇数可用（唤醒 P2）elseV(even); // 通知有偶数可用（唤醒 P3）V(mutex); // 释放临界区（互斥）}
}// 进程 P2: 奇数消费者
void P2() {while(1) {P(odd); // 等待有奇数可用（若无则阻塞）P(mutex); // 申请进入临界区（互斥）int num = getodd(&buffer); // 取出奇数V(empty); // 释放一个空单元countodd(); // 统计奇数V(mutex); // 释放临界区（互斥）}
}// 进程 P3: 偶数消费者
void P3() {while(1) {P(even); // 等待有偶数可用（若无则阻塞）P(mutex); // 申请进入临界区（互斥）int num = geteven(&buffer); // 取出偶数V(empty); // 释放一个空单元counteven(); // 统计偶数V(mutex); // 释放临界区（互斥）}
}// 主初始化函数
int main() {sem_init(&mutex, 0, 1); // 初始化互斥信号量sem_init(&empty, 0, N); // 初始化空位信号量sem_init(&odd, 0, 0); // 初始化奇数信号量sem_init(&even, 0, 0); // 初始化偶数信号量// 创建并启动三个进程（伪代码）create_process(P1);create_process(P2);create_process(P3);return 0;
}
步骤 3: 关键逻辑解释
- 同步顺序：
- P 1 P_1 P1 先
P(empty)（确保有空位），再P(mutex)（进入临界区）。 - P 2 P_2 P2 和 P 3 P_3 P3 先
P(odd)或P(even)（确保有奇/偶数），再P(mutex)。这避免了死锁（同步信号量在互斥信号量外申请）。
- P 1 P_1 P1 先
- 互斥保护：所有缓冲区操作（
put()、getodd()、geteven()）和统计操作（countodd()、counteven()）都在P(mutex)和V(mutex)之间执行，确保数据一致性。 - 数据类型处理： P 1 P_1 P1 在放入数据后根据奇偶性执行
V(odd)或V(even)，直接通知对应消费者。 - 资源管理：
- P 1 P_1 P1 执行
V(odd)或V(even)后，odd或even信号量值增加，唤醒等待的消费者。 - P 2 P_2 P2 或 P 3 P_3 P3 取出数据后执行
V(empty)，允许 P 1 P_1 P1 继续生产。
- P 1 P_1 P1 执行
步骤 4: 正确性保障
- 无死锁：信号量申请顺序一致（先同步后互斥），且无循环等待。
- 无饥饿：信号量的 FIFO 唤醒机制确保所有进程公平执行（假设信号量实现公平）。
- 缓冲区安全：
empty信号量防止溢出；odd和even信号量确保消费者只在有对应数据时执行。
本题是经典生产者-消费者问题的变种，旨在测试学生对并发编程中复杂同步场景的理解。现实应用中，类似场景包括：
- 多线程数据处理（如事件驱动系统，消费者根据事件类型过滤）。
- 资源池管理（如数据库连接池，不同类型任务使用不同资源）。
- 操作系统内核（如 I/O 缓冲区管理，多个设备读写不同类型数据）。
出题者通过引入“数据类型条件”（奇偶区分），增加了传统模型的复杂度，考察学生能否灵活扩展信号量机制。
这样出题的目的在于：
- 核心概念掌握：
- 是否理解信号量的原理（互斥与同步）。
- 能否识别生产者-消费者模型的变种需求（多消费者、类型条件）。
- 问题分析与设计能力：
- 能否正确定义信号量（如引入
odd和even处理数据类型）。 - 能否设计合理的信号量操作顺序（避免死锁）。
- 能否正确定义信号量（如引入
- 实践应用能力：
- 能否用伪代码实现并发控制（临界区保护、条件通知）。
- 能否处理边界情况（如空缓冲区、无奇/偶数时的阻塞）。
- 深层原理理解：
- 是否意识到共享计数器的互斥需求（
countodd()和counteven()需在mutex保护下）。 - 是否理解同步与互斥的分离（同步信号量在互斥信号量外操作）。
- 是否意识到共享计数器的互斥需求（
本题强调在并发系统中，资源访问不仅需要互斥，还需满足动态条件（如数据类型）。学生需掌握：
- 信号量作为低级原语的灵活性（可构建复杂同步逻辑）。
- 设计并发程序时，需考虑所有可能状态（如缓冲区满/空、无奇/偶数）。
- 避免常见错误（如错误顺序导致死锁、忽略数据类型条件）。
最终，试题培养学生的系统思维和并发编程能力，为操作系统、分布式系统等高级课程打下基础。
