题目

三个人一起植树：

• 甲：挖树坑（用铁锹）
• 乙：放树苗、填土（用铁锹）
• 丙：浇水（用水桶）

步骤依次为：挖树坑 → 放树苗 → 填土 → 浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑、填土；水桶用于浇水。

当树坑数量 < 3 时，甲才可以挖树坑。设初始坑数 = 0，铁锹和水桶均可用。

请定义尽可能少的信号量，用 wait()/signal() 操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。

解析

关系拆解

同步关系（"先后顺序"约束）

关系	说明	信号量	初值
甲 → 乙	乙必须等甲挖好坑才能放树苗	pit_ready	0
乙 → 丙	丙必须等乙放好树苗填好土才能浇水	tree_ready	0
乙 → 甲（容量限制）	当未处理的坑 ≥ 3 时甲必须等	pit_quota	3

互斥关系（"共用资源"约束）

关系	说明	信号量	初值
铁锹	甲挖坑、乙填土都要铁锹，且只有一把	shovel	1

水桶只有丙用，没人跟他抢，不需要互斥信号量。

总共需要的信号量

4 个：pit_quota（容量）、pit_ready（甲→乙同步）、tree_ready（乙→丙同步）、shovel（铁锹互斥）。

信号量与代码

semaphore pit_quota  = 3;   // 甲还能挖几个坑（最多 3 个未处理）
semaphore pit_ready  = 0;   // 已挖好等待乙处理的坑数
semaphore tree_ready = 0;   // 已种好等待丙浇水的树苗数
semaphore shovel     = 1;   // 铁锹互斥锁

// 甲：挖坑
甲() {
    while (true) {
        wait(pit_quota);     // 等"未处理坑数"降到 < 3
        wait(shovel);        // 占用铁锹
        挖树坑;
        signal(shovel);      // 释放铁锹
        signal(pit_ready);   // 通知乙：又一个坑就绪
    }
}

// 乙：放苗 + 填土
乙() {
    while (true) {
        wait(pit_ready);     // 等有坑可处理
        wait(shovel);        // 占用铁锹（填土用）
        放树苗;
        填土;
        signal(shovel);      // 释放铁锹
        signal(pit_quota);   // 通知甲：可以再挖了
        signal(tree_ready);  // 通知丙：又一棵树要浇水
    }
}

// 丙：浇水
丙() {
    while (true) {
        wait(tree_ready);    // 等有树苗要浇水
        浇水;                 // 水桶专用，无互斥
    }
}

信号量含义说明（答题必写）

信号量	初值	含义
pit_quota	3	甲还能挖坑的额度（未处理坑数 + pit_quota = 3）
pit_ready	0	已挖好但乙还没处理的坑数
tree_ready	0	乙已处理但丙还没浇水的树苗数
shovel	1	铁锹互斥锁，甲挖坑 / 乙填土争用

易错点

编者注（关键设计点）：

1. pit_quota 初值 = 3 而不是 4：题目说"坑数 < 3 时甲才可挖"——意味着系统最多容许 3 个未处理坑（0、1、2 个时甲都可以挖）。把 quota 设为 3 后，甲挖了 3 次后 P(quota) 会阻塞，正好等于"已经有 3 个坑等乙了"。

   如果初值设为 4 会导致最多 4 个未处理坑出现，违反"< 3"约束。如果设为 2 会少挖一个，浪费产能。

2. 铁锹是甲和乙共用——必须互斥。常见错误是只给甲用 shovel、乙不用——会导致同时挖坑和填土冲突使用铁锹，违反"只有 1 把"约束。

3. 水桶不需要信号量：只有丙用水桶，没有第二个进程争抢——加 bucket 信号量是冗余，"未做到尽可能少"会扣分。

4. 乙的 signal(pit_quota) 必须在 signal(tree_ready) 之前？两种顺序都给分。但不能在 wait(pit_ready) 后立刻 signal(pit_quota)——必须等"放树苗、填土"完成后再 signal，否则甲可能把 quota 用光把树苗淹了。

5. 不要把"挖树坑"放在 wait(pit_quota) 前：这相当于"先挖了再问能不能挖"，违反约束语义。P 操作必须在动作前完成。

6. 流水线分工的通用模式：

   上游进程：wait(quota); 干活; signal(item_ready)
   中游进程：wait(item_ready); 干活; signal(quota); signal(next_item_ready)
   下游进程：wait(next_item_ready); 干活;

   任何"上游有产能限制 + 下游消费 + 多级流水"的题（生产者消费者、流水车间、点饭服务等）都套这个模板。本题中"挖坑→放苗→浇水"正是三级流水。