信号量解决哲学家吃饭问题

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。

问题介绍

未命名文件

前提假设：

​ 一个哲学家吃饭要同时用到左右两个叉子；

​ 哲学家的行为有：吃、思考。

要求：

​ 合理的安排大家就餐。

最初级的方案

用一组p()\v()信号量 来实现哲学家吃饭的互斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore mutex
void philosopher(int i)
	while(TRUE){
    think();									 //哲学家思考
    P(mutex);     				     //拿到mutex资源。
    	
    	take_fork(i);						 //拿左边叉子		
    	take_fork((i+1)mod N);	 //拿右边叉子
    	eat();									 // 吃
    	put_fork(i);             //放下左边叉子
    	put_fork((i+1) mod N);   //放下右边叉子
    	
    V(mutex);                  // 释放mutex资源。
  }

分析：

​ 每个哲学家互斥了，但是每次只允许一个人进餐。而理论上，5个人，可以同时2人吃饭。把就餐人员看成了“必须互斥的临界资源”（而不是叉子），造成了（叉子）资源的浪费。下面改进方案其实就是用一个 “状态”来代替哲学家作为临界资源，而“状态”是包括【哲学家、叉子】信息组合而成的集合体，包括了叉子资源，因此减少了叉子资源的浪费。

改进方案

基本思想：

​ 要么不拿，要么拿左右2个叉子。

​ 不浪费CPU时间，进程间相互通信，让5个进程并发执行。

步骤：

​ s1 思考

​ s2 进入饥饿

​ s3 如果左右邻居都在进餐，进程进入阻塞状态，否则 s4。

​ s4 拿起左右两个叉子

​ s5 eating

​ s6 放下左边的叉子，看看左边的邻居能否就餐，若能就唤醒

​ s7 放下右边的叉子，看看右边的邻居能否就餐，若能就唤醒

​ s8 回到 s1

程序设计：

​ 1、因为哲学家有吃和思考两种行为，而吃有约束条件思考没有，所以哲学家一定有3种状态——吃、饥饿、思考。

​ 2、用数据结构描述哲学家当前状态。

​ 3、把 状态 视为临界资源，哲学家对它的访问需要 ”互斥“ 。

​ 4、一个人吃饱后，需要唤醒其左右他人，相邻的人之间存在 ”同步” 关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = 5   //5个哲学家
LEFT = （i-1) mod N  // 第i个哲学家左邻居
RIGHT = (i+1) mod N  // 第i个哲学家右邻居
THINKING = 0         // 枚举 制定 的三种状态
HUNGRY = 1
EATING = 2
int state[N]         // 记录每一个人的状态

// “状态” 是一种 临界资源，对其访问需要互斥，设定一个相应的信号量实现 互斥 功能。
mutex = 1
semaphore mutex;

// 一个哲学家吃饱后，有可能 唤醒 邻居，存在着同步关系，用一个信号量实现 同步唤醒 功能。
s[i] = 0
semaphore s[N];
1
2
3
4
5
6
7
8
9
10
void philosopher(int i)
{
  while(TRUE)
  {
    think(i);
    take_forks(i);          //拿两把叉子或者阻塞
    eat();
    put_forks(i);					  //放回两把叉子，试着唤醒邻居。
  }
}
1
2
3
4
5
6
7
8
9
10
void take_forks(int i)           //第i个哲学家
{
  P(mutex);											 //获取临界区资源
  state[i] = HUNGRY;             //饿了
  test_take_left_right_forks(i); //测试能否吃饭。
  V(mutex);											 //释放临界区资源
  
  P(s[i]);											 // 测试不通过，第一次就阻塞。
}
// 因为state和 test_take_left_right_forks都可能改变 state的状态，所以都被mutex 包在了互斥 空间内。
1
2
3
4
5
6
7
8
void test_take_left_right_forks(int i)
{
  if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)      // i自己饿了，而左右邻居都没在吃。
  {
    state[i] = EATING;     //满足吃饭条件，状态。
    V(s[i]);							 //发出信号，让自己通过阻塞。自我唤醒 take_forks 下的P(s[i]) 通过。
  }
}
1
2
3
4
5
6
7
8
void put_forks(int i)
{
  p(mutex)												// 进入临界区，保护住可能修改state变量的代码区。
  state[i] = THINKING;    				//吃完了，进入思考时间
  test_take_left_right_forks(LEFT);  //测试左邻居能否吃饭
  test_take_left_right_forks(RIGHT); //测试右邻居能否吃饭 
  V(mutex)												// 退出临界区
}
1
2
3
4
5
6
void think(int i)
{
  P(mutex)                // 因为有state变量的修改，所以用mutex保护起来。
    state[i] = THINKING;
  V(mutex)
}

以上用信号量实现了5个进程并发执行，可以2个进程一起执行。不会死锁。