PV原语解决哲学家吃通心面问题之个人观点
PV信号量有互斥信号量,整型信号量还有记录型信号量以及多信号量(如AND信号量、一般信号量集),我们这里采用互斥信号量和整型信号量来解决哲学家吃通心面问题。
我们先用代码(可能不满足具体的某种编程语言规范)来描述哲学家吃面问题的场景。(自然语言描述是五个哲学家围坐在一张圆桌旁,桌子中央一盘通心面(面假设无限),每个人面前有一只空盘,每两个人之间放一把叉子。为了吃面,每个哲学家都必须获得两把叉子,且只能从自己左边或右边取。则叉子就相当于临界资源,我们为每把叉子设置一个互斥信号量Si(i=0,1,2,3,4),初值均为1,表示均为被使用)。
var fork:array[0...4] of mutex; forki := 1; cobegin process Pi //i=0...4 begin while(true){ 思考; P(fork[i]); P(fork[i+1]mod5); 吃通心面; V(fork[i]); V(fork[i+1]mod5); } end; coend
哲学家问题要解决的其实是死锁问题:
在上述情景下,假如五个哲学家同时拿起右手边的叉子,那么五个人都将等待相邻哲学家手中的叉子,出现“死锁”。
要解决这种死锁,有很多方法,我采用的是:至多允许四个哲学家同时吃面。即我增加一个整型信号量,初值设为4,用于记录某一时刻正在吃面的哲学家总数。
则有如下代码:
var fork:array[0...4] of mutex; int count: semaphore; forki := 1; count:=4; cobegin process Pi //i=0...4 begin while(true){ 思考; P(count); //在吃面前先check下当前吃面的哲学家总数,如果为4,则等待 P(fork[i]); P(fork[i+1]mod5); 吃通心面; V(fork[i]); V(fork[i+1]mod5); V(count); } end; coend
上述就解决了哲学家吃面的问题。
具体的采用某种编程语言解决哲学家吃面问题(如JAVA)时,我们可以采用如下办法。
PV 原语由于是不可被中断的“原子操作”。
我们可以借鉴JAVA中的synchronized关键词。
拿互斥信号量来说:
我们可以这样定义它对应的P、V原语操作
boolean binary_semaphore; //定义互斥信号量 synchronized void p(boolean binary_semaphore){ while(!binary_semaphore){ //信号量被占用,此时空等 } binary_semaphore = FALSE; //取得信号量,并将信号量置为占用标识 } synchronized void v(boolean binary_semphore){ binary_semaphore = TRUE; //归还信号量,重新置信号量为可用标识 }
其他单信号量的PV原语操作类似。