哲学家就餐问题

Question

规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号 的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即 五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获 得两支筷子而进餐。 按照这种办法为什么是 是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.

Answer 1

设有5个哲学家,共享一张放油把椅子的桌子,每人分得一吧椅子.但是桌子上总共执友支筷子,在每个人两边分开各放一支.哲学家只有在肚子饥饿时才试图分两次从两边拾起筷子就餐.
就餐条件是:
1)哲学家想吃饭时,先提出吃饭的要求;
2)提出吃饭要求,并拿到支筷子后,方可吃饭;
3)如果筷子已被他人获得,则必须等待该人吃完饭之后才能获取该筷子;
4)任一哲学家在自己未拿到2支筷子吃饭之前,决不放下手中的筷子;
5)刚开始就餐时,只允许2个哲学家请求吃饭.
试问:
1)描述一个保证不会出现两个邻座同时要求吃饭的算法;
2)描述一个既没有两邻座同时吃饭,又没有人饿死的算法;
3)在什么情况下,5个哲学家全都吃不上饭?
哲学家进餐问题是典型的同步问题.它是由Dijkstra提出并解决的.该问题是描述有五个哲学家,他们的生活方式是交替地进行思考和进餐.哲学家们共用一张圆桌,分别坐在周围的五张椅子上.在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左右岁靠近他的筷子,只有在他拿到两支筷子时才能进餐.进餐完毕,放下筷子继续思考.
利用记录型信号量解决哲学家进餐问题
经分析可知,筷子是临界资源,在一段时间只允许一个哲学家使用.因此,可以用一个信号量表示一支筷子,由这五个信号量构成信号量数组.其描述如下:
var chopstick:array[0,...,4]of semaphore;
所有信号量被初始化为1,第i个哲学家的活动可描述为:
repeat
wait(chopstick);
wait(chopstick[(i+1) mod 5]);
...
eat;
...
signal(chopstick);
signal(chopstick[(i+1) mod 5]);
...
think;
until false;
在以上描述中,哲学家饥饿时,总是先去拿他左边的筷子,即执行wait(chopstick);成功后,再去拿他右边的筷子,即执行
wait(chopstick[(i+1) mod 5]);,再成功后便可进餐.进餐完毕,又先放下他左边的筷子,然后放下他右边的筷子.虽然,上述解法可保证不会有两个相临的哲学家同时进餐,但引起死锁是可能的.假如五个哲学家同时饥饿而各自拿起右边的筷子时,就会使五个信号量chopstick均为0;当他们试图去拿右边的筷子时,都将因无筷子可拿而无限期地等待.对于这样的死锁问题可采用以下集中解决方法:
(1)至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐.
(2)仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐.
(3)规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐.
看了整整一个上午的操作系统，看得头都大了。
我们老师的算法的大意好像是用一个总的信号量，只有获得信号量的哲学家才可以拿筷子。
具体算法如下（用类c描述）：
#include "所有头文件"
#define N 5
#define left (i-1)%N //i的左邻号码
#define right (i+1)%N //i的右邻号码
#define think 0
#define hungry 1
#define eating 2
typedef int semaphore //信号量是一个特殊的整型变量
int state[N] //记录每个人的状态
semaphore mutex=1; //设置信号量
semaphore s[N]; //每个哲学家一个信号量
void philosopher(int i)
{
while(true) //无限循环
{
think;
take_chopstick(i);
eat;
put_chopstick(i);
}
}
void take_chopstick(int i)
{
p(& mutex); //对信号量的p操作
state=hungry;
test(i); //试图得到两支筷子
v(&mutex); //v操作
p(&s); //得不到筷子则阻塞
}
void put_chopstick(int i)
{
p(& mutex);
state=think; //进餐结束
test(left); //看左邻是否进餐
test(right); //再看右邻
v(&mutex);
}
void test(int i)
{
if（state==hungry&&左邻没进餐&&右邻没进餐）
{
state=eating;
v(&s);
}
}追问

我要问的是第三种方法的结果为什么是那样

追答

要JAVA的么。。。

追问

不是，我要问的是为什么1、2好哲学家竞争1号筷子，3、4号哲学家竞争3号筷子

追答

程序员都能看得懂~~~~

追问

我是菜鸟，刚开始学的，麻烦解释一下吗

Answer 2

因为是一张圆的桌子，桌子坐五个人，每个人的右手边有一支筷子（桌子上共5只），2号坐在1号的左边，那么1号拿左手边的筷子和2号拿右手边的筷子便是取同一支筷子，3，4号同理。

点反对的人是非要我补这张图么？看清楚题主问的什么好伐？有要代码么？一天就知道上网找代码抄不会自己写的也是人才

Answer 3

五位哲学家坐在一张圆桌，桌子中央的一个前空盘通心粉每人，每两个男人之间放一根筷子行为的每一个哲学家的想法，感觉饿了，然后吃通心粉吃面食，每个哲学家必须两根筷子，而且每个人只能直接从左边或右边，拿起筷子
定义N 5
无效哲学家（int i）的
{
而（真）
{
思维;
走岔[我];叉[（i +1）％5];
吃;
把叉[ ，把叉[（i +1）％5];
}
}
为了防止死锁发生时所采取的措施：
最多允许4个哲学家围坐在桌子同时，只有当左，右两侧的哲学家筷子是可以的，只是为了让他的筷子，（？），所有的哲学家数，奇数号的哲学家必须首先走左边的筷子，偶数哲学家，反之亦然，为了避免死锁， ，哲学家分为三种状态，思考，饥饿，吃饭，和时间拿到两筷子，或不采取

在
哲学家就餐问题的解决方案（ 1）
定义N 5
无效哲学家（我）
{
而（真）
{
思想;
走叉[i]的叉（+1）％5];
饮食
把叉[I]，把叉[（I + 1）％5];
}
}
哲学家就餐问题的解决方案（2）
定义N 5
定义的思考0
定义HUNGRY 1
定义吃2 BR />＃的typedef INT信号;
INT状态[N];
信号量互斥= 1;
信号[N];
无效测试（INT I）
> {
（状态[I] == HUNGRY）
&&（州（I-1）％5]！吃）
&&（状态[（i +1）％ 5] = EATING）
{
状态[I] =吃;
V（＆S [I]）;
}
}
无效哲学家（我）
{而（真）
{
思考;
P（互斥体）;
状态[I] =饿了，...... />测试（I）;
V（互斥）;
P（＆S [I]）;
左筷子;
采取正确的筷子; ...... />饮食;
把左边的筷子;
把右边的筷子;
P（互斥）
状态[我] =思??维;
名为test（[我-1]％5）;
测试（[i +1]％5）;
V（互斥）;
}
}
状态[ =思维
[I] = 0

-----------

事实上，我不明白......本回答被网友采纳

Answer 4

两个地方应该是pv操作，pv都是操作元语，不可中断
p操作是将信号量-1
v操作是将信号量+1
pv一定要配对使用
哲学家进餐可以通过信号量机制解决，避免死锁
注释如下：
Void
test(int
i)
//测试哲学家i是否满足eating条件
{
if(state[i]==HUNGRY)
//状态为hungry且左右均未在eating状态，即筷子空闲
&&
(state[(i-1)%5]!=EATING)
&&(state[(i+1)%5]!=EATING)
{
state[i]=EATING;
//设置哲学家i的状态标志为eating
V(&s[i]);（不懂，什么意思）
//s[i]初始化为0，表示能否eating的信号量，V之后s[i]=1，可以
}
//通过P操作后进入eating，否则在P(s[i])处阻塞
}
state[i]=THINKING;
//初始化状态位
s[i]=0;
//初始化s[i]
信号量
Void
philosopher(int
i)
{
while
(true)
{
思考；
P(mutex);（还有这个地方也不太懂）
//对mutex进行P操作，即加锁，防止过
//多进程同时执行造成死锁
state[i]=HUNGRY;
//设置i状态
test
(i);
//测试是否可以进eating，如可以，设置
//相应标志位和信号量
V(mutex);
//释放信号量，其它进程可执行P(mutex)
P(s[i]);
//测试是否可以eating
//以下为哲学家i的eating过程
拿左筷子；
拿右筷子；
进食；
放右筷子；
放左筷子；
}
P(mutex);
//对mutex加锁，防止多个进程同时对state[i]操作
state[i]=THINKING;
//设置i状态
test([i-1]%5);
//为左边和右边测试并设置s状态
test([i+1]%5);
V(mutex);
//释放信号量
}