首页 > 其他 > 详细

哲学家进餐问题

时间:2020-04-01 17:36:16      阅读:76      评论:0      收藏:0      [点我收藏+]

哲学家进餐问题:
五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐毕,放下筷子继续思考技术分享图片
分析:放在桌子上的筷子是临界资源,在一段时间内只允许一位哲学家使用,为了实现对筷子的互斥访问,可以用一个信号量表示筷子,由这五个信号量构成信号量数组。

技术分享图片
 1 semaphore chopstick[5] = {1,1,1,1,1};
 2 while(true)
 3 {
 4     /*当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子*/
 5     wait(chopstick[i]);
 6     wait(chopstick[(i+1)%5]);
 7 
 8     // 吃饭
 9  
10     /*当哲学家进餐完成后,总是先放下左边的筷子,再放下右边的筷子*/
11     signal(chopstick[i]);
12     signal(chopstick[(i+1)%5]);
13 }
View Code
  • 上述的代码可以保证不会有两个相邻的哲学家同时进餐,但却可能引起死锁的情况。假如五位哲学家同时饥饿而都拿起的左边的筷子,就会使五个信号量chopstick都为0,当他们试图去拿右手边的筷子时,都将无筷子而陷入无限期的等待。

为避免死锁,可以使用以下三种策略

策略一:至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。定义信号量count,只允许4个哲学家同时进餐,这样就能保证至少有一个哲学家可以就餐。

技术分享图片
 1 semaphore chopstick[5]={1,1,1,1,1};
 2 semaphore count=4; // 设置一个count,最多有四个哲学家可以进来
 3 void philosopher(int i)
 4 {
 5     while(true)
 6     {
 7         think();
 8         wait(count); //请求进入房间进餐 当count为0时 不能允许哲学家再进来了
 9         wait(chopstick[i]); //请求左手边的筷子
10         wait(chopstick[(i+1)%5]); //请求右手边的筷子
11         eat();
12         signal(chopstick[i]); //释放左手边的筷子
13         signal(chopstick[(i+1)%5]); //释放右手边的筷子
14         signal(count); //离开饭桌释放信号量
15     }
16 }
View Code

策略二:仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。可以利用AND 型信号量机制实现,也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。描述如下:

  1. 用记录型信号量实现:
    技术分享图片
     1 semaphore mutex = 1; // 这个过程需要判断两根筷子是否可用,并保护起来
     2 semaphore chopstick[5]={1,1,1,1,1};
     3 void philosopher(int i)
     4 {
     5     while(true)
     6     {
     7         /* 这个过程中可能只能由一个人在吃饭,效率低下,有五只筷子,其实是可以达到两个人同时吃饭 */
     8         think();
     9         wait(mutex); // 保护信号量
    10         wait(chopstick[(i+1)%5]); // 请求右手边的筷子
    11         wait(chopstick[i]); // 请求左手边的筷子
    12         signal(mutex); // 释放保护信号量
    13         eat();
    14         signal(chopstick[(i+1)%5]); // 释放右手边的筷子
    15         signal(chopstick[i]); // 释放左手边的筷子
    16     }
    17 }
    View Code
    1. 用AND型信号量实现:
      技术分享图片
      1 semaphore chopstick[5]={1,1,1,1,1};
      2 do{
      3     //think()
      4     Swait(chopstick[(i+1)%5],chopstick[i]);
      5     //eat()
      6     Ssignal(chopstick[(i+1)%5],chopstick[i]);
      7 }while(true)
      View Code

      策略三:规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则先拿起他右边的筷子,然后再去拿他左边的筷子。按此规定,将是1、2号哲学家竞争1号筷子,3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。

      技术分享图片
       1 semaphore chopstick[5]={1,1,1,1,1};
       2 void philosopher(int i)
       3 {
       4     while(true)
       5     {
       6         think();
       7         if(i%2 == 0) //偶数哲学家,先右后左。
       8         {
       9             wait (chopstick[(i + 1)%5]) ;
      10             wait (chopstick[i]) ;
      11             eat();
      12             signal (chopstick[(i + 1)%5]) ;
      13             signal (chopstick[i]) ;
      14         }
      15         else //奇数哲学家,先左后右。
      16         {
      17             wait (chopstick[i]) ;
      18             wait (chopstick[(i + 1)%5]) ;
      19             eat();
      20             signal (chopstick[i]) ;
      21             signal (chopstick[(i + 1)%5]) ;
      22         }
      23     }
      24 }
      View Code

      感谢神犇:https://blog.csdn.net/Yun_Ge/article/details/89177918

哲学家进餐问题

原文:https://www.cnblogs.com/pangbi/p/12613769.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!