操作系统经典问题

操作系统经典问题"/>

操作系统经典问题

问题描述

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

错误解法

如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

#define N 5
void philosopher(int i) {while(TRUE) {think();take(i); // 拿起左边的筷子take((i+1)%N); // 拿起右边的筷子eat();put(i);put((i+1)%N);}
}

正确解法

为了防止死锁的发生，可以设置两个条件：

• 必须同时拿起左右两根筷子；
• 只有在两个邻居都没有进餐的情况下才允许进餐。

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N // 右邻居
#define THINKING 	0
#define HUNGRY 		1
#define EATING 		2
typedef int semaphore;
int state[N]; // 跟踪每个哲学家的状态
semaphore mutex = 1; // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N]; // 每个哲学家一个信号量
void philosopher(int i) {while(TRUE) {think(i);take_two(i);eat(i);put_two(i);}
}
void take_two(int i) {down(&mutex);state[i] = HUNGRY;check(i);up(&mutex);down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}
void put_two(i) {down(&mutex);state[i] = THINKING;check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了check(RIGHT);up(&mutex);
}
void eat(int i) {down(&mutex);state[i] = EATING;up(&mutex);
}
// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) { if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {state[i] = EATING;up(&s[i]);}
}