哲学家进餐问题

哲学家就餐问题之解

1. 引言

问题描述: 5个哲学家围坐在一个圆桌上，每两个哲学家之间都有一只筷子，哲学家平时进行思考，只有当他们饥饿时，才拿起筷子吃饭。规定每个哲学家只能先取其左边筷子，然后取其右边筷子，然后才可以吃饭。

2. 求解方法

1. 信号量设置。定义互斥信号量数组chopstick[5] = {1, 1, 1, 1, 1}, 用于对5个筷子的互斥访问。

   对哲学家按顺序从0~4编号，哲学家i左边的筷子编号为i, 哲学家右边的筷子编号为(i+1)%5.

    

   //定义信号量数组chopstick[5],并初始化i号哲学家的进程 semaphore chopstick[5] = {1,1,1,1,1}; Pi() { do { P(chopstick[i]); //取左边筷子 P(chopstick[(i+1)%5]); //取右边筷子 eat; //进餐 V(chopstick[i]); //放回左边筷子 V(chopstick[(i+1)%5]); //放回右边筷子 think; //思考 } while (1); }

    

2. 为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子; 对哲学家顺序编号, 要求奇数号的哲学家先抓起左边的筷子,然后再转他右边的筷子, 而偶数号哲学家则刚好相反。

   正解指定规则如下: 假设采用第二种方法, 当一个哲学家左右两边的筷子都可以用时, 才允许他抓起筷子。

   //初始化信号量 semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; //设置取筷子的信号量 Pi() { //i号哲学家的进程 do { P(mutex); //在取筷子前获得互斥量 P(chopstick[i]); //取左边筷子 P(chopstick[(i+1)%5]); //取右边筷子 V(mutex); //释放取筷子的信号量 eat; //进餐 V(chopstick[i]); //放回左边筷子 V(chopstick[(i+1)%5]); //放回右边筷子 think; //思考 } while(1); }

    

    

3. 结语

• 哲学家进餐问题的思维精髓是: 考虑能不能一次拿起两只筷子才做决定的话，就会避免死锁问题.