哲学家进餐问题

有五个哲学家围在一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和物质筷子,他们的生活方式是交替的进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐完毕后,放下筷子继续思考。

​ 我们可以从上面的题目中得出,筷子是临界资源,同一根筷子同一时刻只能有一个哲学家可以拿到。

哲学家进餐问题

1.问题分析

由问题描述我们可以知道,一共有五个哲学家,也就是五个进程;五只筷子,也就是五个临界资源;因为哲学家想要进餐,必须要同时获得左边和右边的筷子,这就是要同时进入两个临界区(使用临界资源),才可以进餐。

2.信号量设置

因为是五只筷子为临界资源,因此设置五个信号量即可。

3.错误的示例

semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking			//思考
    P(mutex[i]);//判断哲学家左边的筷子是否可用
    P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
    //...
    //eat		//进餐
    //...
    V(mutex[i]);//退出临界区,允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
  }while(true);
}

但是如果考虑到并发问题,五个哲学家同时拿起了左边的筷子,此时,五只筷子立刻都被占用了,没有可用的筷子了,当所有的哲学家再想拿起右边筷子的时候,因为临界资源不足,只能将自身阻塞,而所有的哲学家全部都会阻塞,并且不会释放自己手中拿着的左边的筷子,因此就会一直处于阻塞状态,无法进行进餐并思考。

​ 因为,为了解决五个哲学家争用的资源的问题,我们可以采用以下几种解决方法:

4.解决方案

4.1 方案一

至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用餐完毕后能释放他占用的筷子,从而使别的哲学家能够进餐;

我们可以简单的通过增加一个信号量实现,通过这个信号量限定哲学家并发去进餐的数量。

semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
semaphore count = 4;	//控制最多允许四位哲学家同时进餐

void philosopher(int i){
  do {
    //thinking		//思考
    p(count);		//判断是否超过四人准备进餐
    P(mutex[i]);	//判断缓冲池中是否仍有空闲的缓冲区
    P(mutex[(i+1)%5]);//判断是否可以进入临界区(操作缓冲池)
    //...
    //eat			//进餐
    //...
    V(mutex[i]);//退出临界区,允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
    V(count);//用餐完毕,别的哲学家可以开始进餐
  }while(true);
}

4.2 方案二

仅当哲学家的左、右两支筷子可用时,才允许他拿起筷子;第二种方法,也就是使用AND型信号量,同时对哲学家左右两边的筷子同时申请

semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking		//思考
    Swait(mutex[i], mutex[(i+1)%5]);//判断哲学家左边和右边的筷子是否同时可用
    //...
    //eat		
    //...
    Ssignal(mutex[i], mutex[(i+1)%5]);//进餐完毕,释放哲学家占有的筷子
  }while(true);
}

4.3 方案三

规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;而偶数号哲学家则相反。​ 对于第三种,需要在代码中添加个判断,来决定获取左、右筷子的顺序

semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking	
    if(i%2 == 1){
      P(mutex[i]);//判断哲学家左边的筷子是否可用
      P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
    }else{
      P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
      P(mutex[i]);//判断哲学家左边的筷子是否可用
    }
    //...
    //eat
    //...
    V(mutex[i]);//退出临界区,允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
  }while(true);
}

上一篇:经典进程同步问题


下一篇:FreeRTOS信号量