1、哲学家就餐问题描述
哲学家就餐问题是由Dijkstra在1965年提出的，5个哲学家围绕一张圆桌坐，桌子上放有5支叉子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边的叉子和右边的叉子，思考时则同时将两支叉子放回原处。问如何保证哲学家们的动作有序进行？如不出现有人永远不能拿到叉子。哲学家就餐问题的示意图如下图所示。
设计原则：某个哲学家要么不拿叉子，要么拿两把叉子。
S1：思考中... S2：进入饥饿状态 S3：如果左邻居或者右邻居正在进餐，等待；否则转到S4； S4：拿起两把叉子； S5：吃面条... S6：放下左边的叉子 S7：放下右边的叉子 S8：开始新的循环，转到S1
2、思路设计
首先必须要有一个数据结构，来描述每个哲学家的当前状态；
#define N 5 //哲学家的个数 #definde LEFT i //第i个哲学家的左邻居 #define RIGHT (i+1)%N //第i个哲学家的右邻居 #define THINKING 0 //思考状态 #define HUNGRY 1 //饥饿状态 #define EATING 2 //进餐状态 int state[N]; //记录每个人的状态
该状态是一个临界资源，对它的访问应该互斥地进行
semaphore mutex; //互斥信号量，初值为1
一个哲学家吃饱之后，可能要唤醒邻居，存在同步关系
semaphore s[N]; //同步信号量，初值为0
3、实现
函数philosopher的定义如下所示：
void philosopher(int i) { while(true) { think(); //思考中，S1 take_forks(i); //拿到两把叉子或者被阻塞，S2-S4 eat(); //吃面条中...S5 put_forks(i); //把两把叉子放回到原处S6-S7 } }
函数take_forks的定义
void take_forks(int i) //i的取值为：0 ~ N-1 { P(mutex); //进入临界区 state[i] = HUNGRY; //将状态置为饥饿 test_take_left_right_forks(i); //试图拿两把叉子 V(mutex); //退出临界区 P(s[i]); //没有叉子便阻塞 }
函数test_take_left_right_forks的定义
void test_take_left_right_forks(int i) { if(state[i] == HUNGRY) && //i是哲学家自己或者其他哲学家 state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; V(S[i]); //通知第i个人可以吃饭了 } }
函数put_forks的定义
//功能：把两把叉子放回到原处，并在需要的时候取唤醒左邻右舍 void put_forks(int i) { P(mutex); //进入临界区 state[i] = THINKING; //交出两把叉子 test_take_left_right_forks(LEFT); //判断左邻居是否能够吃饭 test_take_left_right_forks(RIGHT); //判断右邻居是否能够吃法 V(mutex); //退出临界区 }
其他两个函数think()和eat()，eat()函数不需要加互斥锁，think()函数需要加互斥锁。
void think() { P(mutex); i_am_thinking(); //思考的动作 V(mutex); }
