哲学家进餐问题
哲学家进餐问题是由荷兰学者Dijkstra提出的经典的同步问题之一。
- 中文名称 哲学家进餐问题
- 产生背景 一大类并发控制问题的典型例子
- 约束条件 只有拿到两只筷子哲学家才能吃饭
- 信号量机制 筷子是临界资源
产生背景
由荷兰学者Dijkstra提出的哲学家进餐问题(The Dinning Philosophers Problem)是经典的同步问题之一。哲学家进餐问题是一大类并发控制问题的典型例子，涉及信号量机制、管程机制以及死锁等操作系统中关键问题的应用，在操作系统文化史上具有非常重要的地位。对该问题的剖析有助于深刻地理解计算机系统中的资源共享、进程同步机制、死锁等问题，并能熟练地将该问题的解决思想应用于生活中的控制流程。
问题描述
有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，该哲学家进餐完毕后，放下左右两只筷子又继续思考。
约束条件
(1)只有拿到两只筷子时，哲学家才能吃饭。
(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。
(3)任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子。
信号量机制
筷子是临界资源，一段时间只允许一位哲学家使用。为了表示互斥，用一个信号量表示一只筷子，五个信号量构成信号量数组。本文中算法用类C语言描述伪码算法。算法描述如下:n用五支筷子的信号量构成信号量数组:
Semaphore chopstick[5]={1，1，1，1，1};
p(stick[i]);
p(stick[(i+1) % 5]);
进餐;
v(stick[i]);
v(stick[(i+1) % 5]);
思考;
当哲学家饥饿时，总是先去拿他左边的筷子，执行wait(chopstick[I])，成功后，再去拿他右边的筷子，执行wait(chopstick[I+1]%5);成功后便可进餐。进餐毕，先放下他左边的筷子，然后再放下右边的筷子。当五个哲学家同时去取他左边的筷子，每人拿到一只筷子且不释放，即五个哲学家只得无限等待下去，引起死锁。
死锁问题
(1)破坏请求保持条件
利用原子思想完成。即只有拿起两支筷子的哲学家才可以进餐，否则，一支筷子也不拿。
解法一:利用AND机制实现第1位哲学家的活动描述为:
philosopher (int I)
{
while(true)
{
思考;
swait(chopstick[(I+1)]%5，chopstick[I]);
进餐;
Ssignal(chopstick[I]，chopstick[(I+i)%5]);
}
}
解法二:利用记录型信号量机制实现在初始化中增加一个信号量定义:semaphore mutex=1:
第1位哲学家的活动描述:
philosopher (int I)
{
while(true)
{
思考;
wait(mutex);
wait(stiCk[I]);
wait(Stick[(I+1)%5]);
Signal(mutex);
进餐;
signal(stick[I]);
Signal(Stick[(I+1)%5]);
}
}
该方法将拿两只筷子的过程作为临界资源，一次只允许一个哲学家进入。
(2)破坏环路等待条件
在上述死锁问题中，哲学家对筷子资源的申请构成了有向环路，如图2所示。
图2环路等待
解法一:奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。按此规定，将是1、2号哲学家竞争I号筷子;3、4号哲学家竞争4号筷子。两种算法描述如下:
1)第1个哲学家的活动:
philosopher (int I)
{
while(true)
{
思考;
If I%2==1 then
wait(Stick[I]);
wait(stick[(I+1)%5]);
进餐;
Signal(stick[I J);
signal(stick[(I+1)%5]);
e1Se
wait(stick[(I+1)%5]);
wait(stick[I]);
进餐;
signal(stick[(I+1)%5]);
Signal(stick[I]);
}
}
(2)第1个哲学家的活动:
philosopher(int I)
{
while(true)
{
思考;
wait(chopstick[I+(I%2)];
wait(chopstick[(I+(I+1)%2)%5])
进餐;
signal(chopstick[I+(I%2)]);
Signal(chopstick[(I+(I+1)%2)%5]);
}
}
解法二:至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。最终能保证有一位哲学家能进餐，用完释放两只筷子，从而使更多的哲学家能够进餐。增加一个信号量定义semaphore count=4:算法描述第1个哲学家的活动:
philosopher (int I)
{
while(true)
思考;
wait(count);
wait(chopstiok[I]);
wait(chopstick[I+1]mod 5);
进餐;
signal(chopstick[I]);
signal(chopstick[I+1]mod 5)
signal(count);
}
}
解法三:哲学家申请资源总是按照资源序号先大后小的顺序，这样0.3号哲学家先右后左，但是4号哲学家
先左后右，改变方向，破坏了环路。算法描述第1个哲学家的活动:
philosopher(int I)
{
while(true)
{
思考;
if I>(I+1)%5 then
wait(chopstick[I]);
wait(chopstick[I+1]mod 5);
else
wait(chopstick[T+1]mod 5);
wait(chopstick[T]);/*哲学家总是先取最
大序号的筷子*/
进餐;
signal(chopstick[I]);
signal(chopstick[I+1]mod5);
}
}
管程机制
在用信号量机制解决同步问题时，往往比较繁琐，采用面向对象的思想，将资源及资源的共享操作封装起来，用管程来管理，实现哲学家进餐问题，使用起来更加方便。
算法实现描述如下:
1)建立管程
monitor PC
{
semaphore chopstick[5]=11，1，1，1，1);
X:condition;/*定义条件变量*/
void Get:(int T) /*定义取筷子过程*/
{
Tf chopstick[I]=1 and chopstick[(i+1)%5]=1 then
get the chopstick[I]and chopstick[(i+1)%5];
else X.wait;/*左右筷子没有，则等待*/
)
void Put(int i) /*定义放下筷子过程*/
{
put:the chopstick[I]and chopstick
(i+1)%5];
Tf X.quene then X.signal;/*唤醒等待筷子的哲学家*/
)
}
2)使用管程
第1个哲学家的活动:
void philosopher(int I)
{
while(true)
{
思考;
get:(I);
进餐;
put(I);
}
}