【良师408】计算机考研408真题解析（2025-45 操作系统同步互斥：植树问题信号量算法深度解析）
特别提醒：【良师408】所收录真题根据考生回忆整理，命题版权归属教育部考试中心所有
操作系统同步互斥：基于2025年408真题的植树问题信号量算法深度解析
摘要：本文基于2025年计算机考研408操作系统真题（植树问题），深入剖析了多级生产者-消费者模型与资源互斥的复杂同步问题。通过设计五大信号量，并提供完整的C语言多线程实现，旨在帮助读者掌握复杂场景下的进程同步与互斥机制。
1. 真题重现与问题建模
【2025-45】 三个人一起植树，甲挖坑，乙放树苗入坑并填土，丙负责为新种树苗浇水。步骤依次为：挖树坑，放树苗，填土和浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑，填土。水桶用于浇水。当树坑数量小于 3 时，甲才可以挖树坑。设初始坑 = 0，铁锹水桶均可用，定义尽可能少的信号量，用 wait() 和 signal() 操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。
(1) 给出算法的基本设计思想：
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释：
(3) 说明你所设计算法的时间复杂度和空间复杂度。
2025年408真题第45题提出了一个经典的同步互斥问题：甲（挖坑）、乙（填土）、丙（浇水）三人协同植树。
同步关系：甲→乙→丙的工序依赖。互斥资源：铁锹（甲、乙共用）、水桶（丙独占）。容量限制：树坑数量 ≤3le 3≤3。
本题的本质是扩展的生产者-消费者模型，形成了三级流水线：
甲：生产“已挖坑”资源（
stage1
stage2
empty
2. 信号量机制设计与初值确定
根据同步、互斥和资源限制的需求，我们定义了五个信号量：
| 信号量名称 | 作用（类型） | 初值 | 关联进程 | 核心操作 |
|---|---|---|---|---|
|
铁锹互斥 | 1 | 甲、乙 | 互斥访问 |
|
水桶互斥 | 1 | 丙 | 互斥访问 |
|
空闲坑位 | 3 | 甲、乙 | 资源限制 |
|
已挖坑数 | 0 | 甲、乙 | 同步控制 |
|
已填土数 | 0 | 乙、丙 | 同步控制 |
设计思想：
互斥信号量初值为 111，确保资源独占。资源信号量（
empty
stage1
stage2
3. 进程同步互斥算法实现（C语言）
以下是基于 POSIX 信号量 和 Pthread 多线程 实现的植树同步算法核心代码。
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
// 信号量定义
sem_t mutex_spade; // 铁锹互斥信号量，初值1
sem_t bucket; // 水桶互斥信号量，初值1
sem_t empty; // 空闲坑位，初值3
sem_t stage1; // 已挖坑数，初值0
sem_t stage2; // 已填土数，初值0
// 甲：挖坑进程
void* person_A(void* arg) {
while (1) {
// 1. 限制坑位数量（同步/资源）
sem_wait(&empty);
// 2. 获取铁锹（互斥）
sem_wait(&mutex_spade);
// 3. 挖坑操作 (临界区)
printf("甲：挖坑完成
");
// 4. 释放铁锹
sem_post(&mutex_spade);
// 5. 通知乙有坑可用（同步）
sem_post(&stage1);
}
return NULL;
}
// 乙：种树进程（放树苗+填土）
void* person_B(void* arg) {
while (1) {
// 1. 等待有坑可种（同步）
sem_wait(&stage1);
// 2. 获取铁锹（互斥）
sem_wait(&mutex_spade);
// 3. 填土操作 (临界区)
printf("乙：填土完成
");
// 4. 释放铁锹
sem_post(&mutex_spade);
// 5. 通知丙可浇水（同步）
sem_post(&stage2);
// 6. 释放一个坑的容量（资源）
sem_post(&empty);
}
return NULL;
}
// 丙：浇水进程
void* person_C(void* arg) {
while (1) {
// 1. 等待有树需要浇水（同步）
sem_wait(&stage2);
// 2. 获取水桶（互斥）
sem_wait(&bucket);
// 3. 浇水操作 (临界区)
printf("丙：浇水完成
");
// 4. 释放水桶
sem_post(&bucket);
}
return NULL;
}
// 主函数省略初始化和销毁信号量部分
// ...
4. 算法复杂度与性能分析
4.1 时间复杂度
本算法中的所有操作，包括
sem_wait()
sem_post()
时间复杂度：O(1)O(1)O(1) per操作。
4.2 空间复杂度
算法仅使用了固定数量的信号量变量和进程控制块（PCB）等系统资源，这些资源数量不随植树任务的规模（如要种的树的数量）变化。
空间复杂度：O(1)O(1)O(1)（常量空间）。
5. 易错点与优化策略
5.1 死锁预防：资源申请顺序
在多资源竞争场景下，死锁是最大的风险。本题中，甲进程必须遵循以下资源申请顺序：
同步资源 (
) →
empty
ightarrow→ 互斥资源 ()
mutex_spade
如果顺序颠倒，即先申请互斥资源，后申请同步资源，则可能导致循环等待，引发死锁。
5.2 关键的资源释放操作
乙进程在完成填土后，必须执行
sem_post(&empty)
错误后果：若遗漏此操作，当 333 个坑位全部被占用后，甲进程将永久阻塞，导致饥饿或活锁。
5.3 拓展与优化
如果题目扩展为“有 MMM 把铁锹和 NNN 个水桶”，则只需将
mutex_spade
bucket
标签：#计算机考研 #操作系统 #信号量 #进程同步 #408真题 #算法实现
版权声明：
【良师408】所收录真题根据考生回忆整理，命题版权归属教育部考试中心所有。本文内容为作者原创，仅供学习交流使用，严禁用于商业用途。
作者简介
周忠良，男，1968 年 10 月生，安徽桐城人，退役军官。现为资深高校教师、研究员，兼具金融科技与人工智能领域丰富实践经验。
教学领域：主讲《计算机学科专业基础（408）》《大数据分析》《JavaEE 开发》《云安全原理》《机器学习》等课程，覆盖本科至研究生层次。院校合作：曾执教于中国人民大学、大连理工大学、东北大学、北京外国语大学、北京石油化工学院、苏州大学、常州大学、盐城工学院等国内二十多所高校，累计授课超 50 门次，涵盖大数据、人工智能、金融科技等前沿方向。实践教学：主导“智慧云平台”“分布式系统架构”“金融大数据计量”等企业实训项目，注重产教融合。学术指导：指导学生获全国水下机器人大赛一等奖、算法竞赛奖项，并获“优秀指导教师”称号。
跨领域专长
技术能力：精通 Python、Java、C++等编程语言，擅长类脑计算、深度学习、大数据分析及云计算安全。金融科技：持有证券、基金执业资格，深耕量化交易、智能投顾及区块链技术研究。
荣誉与成果
军队科技进步一等奖（国家 863 项目）、二、三等奖等多项奖励曾任中国传媒大学特聘教授、清华大学 AI 项目研究员
联系方式 :
微信（goodteacher408）E-mail:243969453@qq.com
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
