第 45 题
三个人一起植树，甲挖坑，乙放树苗入坑并填土，丙负责为新种树苗浇水。步骤依次为：挖树坑，放树苗，填土和浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑，填土。水桶用于浇水。当树坑数量小于 3 时，甲才可以挖树坑。设初始坑 = 0，铁锹水桶均可用，定义尽可能少的信号量，用 wait() 和 signal() 操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。
[tag_link]
这题是一个近似于流水线的结构，其过程为：挖树坑（甲）→ 放树苗、填土（乙）→ 浇水（丙）。不过甲最多可以同时挖三个树苗，也就是说不允许同时存在 4 个未被乙使用的树坑，这是比较复杂的一点。实现甲和乙之间的同步需要使用到 pits 和 empty 这两个信号量，同时还需要一个 water 信号量来实现乙和丁的同步，代码实现如下：
semaphore mutex = 1; // 对铁锹的使用需要互斥
semaphore pits = 3; // 甲还能挖洞的数量
sempahore empty = 0; // 可以使用的树坑数量
sempahore water = 0; // 需要浇水的水苗数量
甲() {
while (1) {
wait(pits); // 最多只能挖三个未被乙使用的坑
wait(mutex); // 占用铁锹
挖树坑；
signal(mutex); // 释放铁锹
signal(empty); // 通知乙可以放树苗和填土了
}
}
乙() {
while (1) {
wait(empty); // 等待到有树坑为止
wait(mutex); // 占用铁锹
放树苗、填土；
signal(mutex); // 释放铁锹
signal(pits); // 通知甲可以继续挖坑了
signal(water); // 通知丙可以浇水了
}
}
丙() {
while (1) {
wait(water);
浇水；
}
}