更多优质内容
请关注公众号
请关注公众号
吸烟者问题
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷 起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、 第二个拥有纸、第三个拥有胶水。供应者进程无限地ᨀ供三种材料，供应者每次将两种材料放桌 子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供 应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。
代码如下：
s1 = 0; // 纸
s2 = 0; // 烟草
s3 = 0; // 胶水
finished = 1; // 当前被服务的抽烟者是否已经抽完烟
producer(){
start = 0
while(1){
choice = start % 3
if(choice == 0){ // 提供纸巾和烟草
V(s1);
V(s2);
}
if(choice == 1){
V(s1);
V(s3);
}
if(choice == 3){
V(s2);
V(s3);
}
P(finished); // 提供完材料之后，供应者阻塞，直到其他抽烟者通知唤醒本进程
}
}
consumer1(){ // 自带烟草
while(1){
P(s1); // 请求纸
P(s3); // 请求胶水
从桌子上拿走纸、胶水;
抽烟;
V(finished); // 唤醒供应者
}
}
consumer2(){ // 自带纸
while(1){
P(s2); // 请求烟草
P(s3); // 请求胶水
从桌子上拿走烟草、胶水;
抽烟;
V(finished); // 唤醒供应者
}
}
consumer3(){ // 自带胶水
while(1){
P(s2); // 请求烟草
P(s1); // 请求纸
从桌子上拿走烟草、纸;
抽烟;
V(finished); // 唤醒供应者
}
}
其实，桌子可以看成是一个大小为1的缓冲区，因为缓冲区大小为1，所以可以不用互斥量finished，只需要同步信号量。上面的解法就没有使用互斥信号量。
哲学家进食问题
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一锅海底捞。
哲学 家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时， 才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲 学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
哲学家进食问题是单纯的互斥问题，但可能发生死锁，如何死锁是该问题的关键。
第一版本的答案：
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用
human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子
while(1){
P(chopstick[i]); // 拿起i号筷子
P(chopstick[(i+1)%5]); // 拿起i+1号筷子
进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子
V(chopstick[i]); // 释放i号筷子
V(chopstick[(i+1)%5]); // 释放i+1号筷子
思考;
}
}某一个人在进食时，它相邻的两个人不能进食，但它对面的两个人可以并发进食。
这个解法问题是如果1~5号哲学家分别先后拿起他左边的筷子，就会发生死锁。
为了避免死锁，可以使用一下几种思路：
1. 让哲学家一拿就拿两根筷子，不允许哲学家拿完一根，剩下的一根被其他人拿走。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用
mutex = 1; // 互斥量，使某个人拿2只筷子的过程中，其他哲学家不能拿筷子
human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子
while(1){
P(mutex);
P(chopstick[i]); // 拿起i号筷子
P(chopstick[(i+1)%5]); // 拿起i+1号筷子
V(mutex);
进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子
V(chopstick[i]); // 释放i号筷子
V(chopstick[(i+1)%5]); // 释放i+1号筷子
思考;
}
}该方式的一个小缺点在于任何一个人拿筷子的时候，其他人不能拿筷子（即使它左右两边筷子都空闲），因此哲学家拿筷子是串行的，但拿筷子的时间非常短，因此也不会造成多少性能损失。
2.让最多4个人能用筷子，第5个人如果要用筷子就被阻塞。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用
max = 4; // 最多4个人拿筷子
human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子
while(1){
P(max);
P(chopstick[i]); // 拿起i号筷子
P(chopstick[(i+1)%5]); // 拿起i+1号筷子
进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子
V(chopstick[i]); // 释放i号筷子
V(chopstick[(i+1)%5]); // 释放i+1号筷子
V(max);
思考;
}
}该解法在4个相邻哲学家同时拿起左边筷子时不会死锁，但是会造成这4个哲学家进食是串行的，但4个人同时拿筷子发生几率比较小，可以接受。
3. 让奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子，该方法是3种方法中效率最高的。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用
human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子
while(1){
if(i & 1 == 1){
P(chopstick[i]); // 拿起i号筷子
P(chopstick[(i+1)%5]); // 拿起i+1号筷子
}else{
P(chopstick[(i+1)%5]); // 拿起i号筷子
P(chopstick[i]); // 拿起i+1号筷子
}
进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子
V(chopstick[i]); // 释放i号筷子
V(chopstick[(i+1)%5]); // 释放i+1号筷子
思考;
}
}