经典进程同步问题-哲学家进餐问题

发表于 更新于 分类于

经典进程同步问题-哲学家进餐问题

问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

  • 关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。
  • 整理思路。显然这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。解决的方案有以下几种
    • 至多允许四位哲学家同时去拿左边的筷子，保证至少一位哲学家可以拿到两只筷子，并在使用完毕后，释放两只筷子。
    • 仅当哲学家的左右筷子均可用时，才允许他拿起筷子进餐。
    • 规定奇数哲学家先拿左边筷子，偶数哲学家先拿右边筷子，1，2哲学家竞争1号筷子，3，4哲学家竞争3号筷子。进而，所有哲学家先竞争奇数筷子，再竞争偶数筷子。
  • 信号量设置。定义互斥信号量数组chopstick[5] = {1, 1, 1, 1, 1}用于对5个筷子的互斥访问。对哲学家按顺序从0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为(i+l)%5。

可能导致死锁的方案

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

当所有哲学家都只拿到左边的筷子时，将出现死锁的情况。

记录型信号量实现

在思路整理中的三种方案中，我们选取第二种方案（仅当哲学家的左右筷子均可用时，才允许他拿起筷子进餐），用记录型信号量进行实现。

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

以上程序，当某进程不能顺利申请到两只筷子时，没有将mutex释放，也就意味着其他进程都无法再申请筷子了。因此，还可以对P操作进行优化，当申请筷子不成功时，先将mutex设置为1。等到所等待的筷子可用时，再将mutex设置为0，申请此筷子。

1
2
3
4
5
6
7
void S_P(chopstick[i], mutex){  
    if(chopstick[i] <= 0)//申请不到该资源时，释放互斥锁  
        v(mutex);  
    while(chopstick[i] <= 0 ) ;//所申请的资源出现  
    p(mutex);//加上互斥锁  
    p(chopstick[i]);  
}

AND型信号量实现

1
2
3
4
5
6
7
8
9
semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量  
 Pi(){ //i号哲学家的进程  
     do{  
         AND_P (chopstick [i], chopstick[ (i+1) %5]) ; //同时取左右筷子  
         eat;  //进餐  
         AND_V(chopstick [i], chopstick[ (i+1) %5]) ;  //同时放回左右筷子  
         think; // 思考  
     }while(1);  
 }

作者：okbrochure
链接：https://www.jianshu.com/p/4e9ab59d2169