哲学家用餐.docx
《哲学家用餐.docx》由会员分享，可在线阅读，更多相关《哲学家用餐.docx（21页珍藏版）》请在冰点文库上搜索。
哲学家用餐
2010－2011学年第1学期
目录
1.课程设计内容2
2.课程设计目的2
3.背景知识2
4.工具/准备工作3
5.设计步骤与方法3
5.1.步骤1：
分析哲学家用餐时出现的情况3
5.1.1.分析在什么情况下5个哲学家全部吃不上饭（即死锁情况）3
5.1.2.分析一种没有人饿死的情况（即解决死锁方法）4
5.2.步骤2：
编程设计8
5.2.1.经小组商量采用C原理，如下：
8
5.2.2.模块说明9
5.2.3.模块图10
5.3.步骤3：
代码实现以及测试10
5.3.1.代码实现：
10
5.3.2.测试：
15
6.设计结果及分析15
7.设计结论15
8.问题及心得体会15
9.对本设计过程及方法、手段的改进建议16
10.参考文献16
11.课程设计评价（教师）16
哲学家用餐
1.课程设计内容
哲学家就餐问题中，一组哲学家围坐在一个圆桌旁，每个哲学家的左边都只有一只筷子（当然他的右边也有一只筷子，但是这是他右边哲学家的左边的筷子），他们吃完了就思考，思考了一会就会饿，饿了就想吃，然而，为了吃饭，他们必须获得左边和右边的筷子。
我们要设计一个方案来解决哲学家就餐这个问题。
2.课程设计目的
2.1巩固和加深课堂所学的知识；
2.2掌握哲学家用餐涉及到的知识，如死锁，如何消除死锁，信号量的使用等
2.3学习掌握c语言编程及调试
3.背景知识
哲学家就餐问题中，一组哲学家围坐在一个圆桌旁，每个哲学家的左边都只有一只筷子（当然他的右边也有一只筷子，但是这是他右边哲学家的左边的筷子），他们吃完了就思考，思考了一会就会饿，饿了就想吃，然而，为了吃饭，他们必须获得左边和右边的筷子。
假使所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复，对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。
至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放他所使用过的两支筷子，从而可使更多的哲学家就餐。
4.工具/准备工作
工具：
Visualc++6.0
准备工作：
分配任务，分析课题
5.设计步骤与方法
5.1.步骤1：
分析哲学家用餐时出现的情况
5.1.1.分析在什么情况下5个哲学家全部吃不上饭（即死锁情况）
考虑两种实现的方式，如下：
A．
算法描述：
Voidphilosopher（inti）/*i：
哲学家编号，从0到4*/
{
While（true）
{
Think（）;/*哲学家正在思考*/
Take_fork（i）;/*取左侧的筷子*/
Take_fork（i+1）%N）;/*取右侧的筷子；%为取模运算*/
eat（）;/*吃饭*/
put_fork（i）;/*把左侧的筷子放回桌子*/
put_fork（i+1）%N）;/*把右侧的筷子放回桌子*/
}
}
分析：
假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复，对于这种情况，即所有的程序都在无限的运行，但是都是无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。
B．
算法描述：
规定在拿到左侧筷子后，先检查右面的筷子是否可以使用，如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。
分析：
当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可使用，又都放下左侧筷子，等一会儿，又共识拿起左侧筷子。
。
。
如此这样永远重复下去，对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。
5.1.2.分析一种没有人饿死的情况（即解决死锁方法）
考虑了四种实现方式（A.B.C.D）：
A．原理：
至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。
一下将room作为信号量，只允许4个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room的等待队列。
根据FIFO的原则，总会进入就餐。
因此不会出现饿死和死锁的现象。
伪码
Semaphorechopstick[5]={1,1,1,1,1};
Semaphoreroom=4;
Voidphilosopher（inti）
{
while（true）
{
Think（）;
Wait（room）;//请求进入房间进餐
wait（chopstick[i]）;//请求左手边的筷子
wait（chopstick[（i+1）]%5）;//请求右手边的筷子
eat（）;
signal（chopstick[（i+1）]%5）;//释放右手边的筷子
singal（chopstick[i]）;//释放右手边的筷子
singal（room）;
}
}
B．原理：
仅当哲学家的左右筷子都可用时，才允许他拿起筷子进餐。
方法1：
利用AND型信号量机制实现：
根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。
当某些资源不够时阻塞调用进程；由于等待队列的存在，使得对资源的请求满足FIFO的要求，因此不会出现饥饿的情形。
伪码：
Semaphorechopstick[5]={1,1,1,1,1};
Voidphilosopher（intI）
{while（true）
{
Think（）;
Swait（chopstick[（I+1）]%5，chopstick[I]）;
eat（）;
Ssignal（chopstick[（I+1）]%5，chopstick[I]）;
}
}
方法2：
利用信号的保护机制实现，通过信号量mutex对eat（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作这样可以防止死锁的出现。
伪码：
Semaphore=1;
Semaphorechopstick[5]={1,1,1,1,1};
voidphilosopher（intI）
{while（true）
{
think（）;
wait（mutex）;
wait（chopstick[（I+1）]%5）;
wait（chopstick[I]）;
signal（mutex）;
eat（）;
signal（chopstick[（I+1）]%5）;
singal（chopstick[I]）;
}
}
C.原理：
规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则相反。
按此规定，将是1,2号哲学家竞争1号筷子，3,4号哲学家竞争3号筷子。
即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。
而申请不到的哲学家进入阻塞等待队列，跟FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。
伪码：
Semaphorechopstick[5]={1,1,1,1,1};
voidphilosopher（inti）
{
While（true）
{
Think（）;
If（i%2==0）//偶数号哲学家，先右后左
{
Wait（chopstick[i+1]mod5）;
Wait（chopsticl[i]）;
eat（）;
signal（chopstick[（i+1）]mod5）;
singal（chopstick[i]）;
}
else
{
Wait（chopsticl[i]）;
Wait（chopstick[i+1]mod5）;
eat（）;
singal（chopstick[i]）;
signal（chopstick[（i+1）]mod5）;
}
}
D．利用管程机制实现（最终该实现是失败的，见以下分析）：
原理：
不是对每只筷子设置信号量，而是对每个哲学家设置信号量，test（）函数有以下作用：
a.如果当前处理的哲学家处于饥饿状态而两侧哲学家不在吃饭状态，则当前哲学家通过test（）函数试图进入吃饭状态。
b.如果通过test（）进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到其他哲学家进程通过test（）将该哲学家状态设置为EATING。
c.当一个哲学家进程调用put_forks（）放下筷子的时候，会通过test（）测试它的邻居，如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。
如上所述，该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允许转换到进餐状态。
该算法会出现某个哲学家始终无法吃饭的情况，即当该哲学家的左右两个哲学家交替处在吃饭状态的时候，则该哲学家始终无法进入吃饭状态，因此不满足题目要求。
但是该算法能够实现对于任意多哲学家的情况都能获得最大的并行度。
因此具有重要的意义。
伪码：
#defineN5/*哲学家人数*/
#defineLEFT（i-1+N）%N/*i的左邻居号*/
#defineRight（i+1）%N/*i的左邻居号*/
typedefenum{THINKING,HUNGRY,EATING}phil_state;/*哲学家状态*/
monitordp/*管程*/
{
phil_statestate[N];
semaphoremutex=1;
semaphores[N];
voidtest（inti）
{
if（state[i]==HUNGRY&&state[LEFT（I）]!
=EATING&&state[RIGHT]!
=EATING）
{
state[i]=EATING;
V（s[i]）;
}
}
Voidget_forks（inti）
{
P（mutex）
state[i]=HUNGRY;
test（i）;/**试图得到两支筷子?
V（mutex）;
P（s[i]）;/*得不到筷子则阻塞*/
voidput_forks（inti）
{
P（mutex）;
state[i]=THINKING;
test（LEFT（i））;/*看左邻是否进餐*/
test（RIGHT（i））;/*看右邻是否进餐*/
V（mutex）;
}
}
哲学家进餐如下：
Voidphilosopher（intprocess）
{
While（ture）
{
think（）;
tet_forks（process）;
eat（）;
put_forks（process）;
}
}
5.2.步骤2：
编程设计
5.2.1.经小组商量采用C原理，如下：
1．原理：
规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则相反。
按此规定，将是1,2号哲学家竞争1号筷子，3,4号哲学家竞争3号筷子。
即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。
而申请不到的哲学家进入阻塞等待队列，跟FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。
2．选择一种吃肉来模拟此过程，使之更具体
3．实现方式：
1）定义一些需要跟哲学家对应的数
2）定义哲学家三种状态，思考，正在吃饭（包含拿筷子），已经吃饭
3）拿筷子过程奇数号的哲学家先拿起他左边的筷子，而偶数号的哲学家则相反。
4）设定时间，吃肉时间最多为3秒
5）选择哲学家和肉的编号均采用随机数
5.2.2.模块说明
1．intgetkey（inti）函数功能：
此函数用来模拟拿筷子过程
Tman[i-1/i];用于判断筷子是否可用，如果可以，返回0，否则返回1。
（i-1为左边筷子，i为右边筷子）
2．voideat（）函数功能：
此函数用来模拟准备吃肉的过程
want：
想吃肉的哲学家（want=1+rand（）%5;）
Thinking[i];判断第n个哲学家在思考。
（返回1就是在思考，0则不是）
Eating[i];判断第n个哲学家在吃肉。
（返回1在吃，0就不是）
MeatNo[want]:
判断第n个哲学家在吃第n块肉
EatTimeAll[want]：
判断第n个哲学家吃肉共需要几秒
4．voideatting（）函数功能：
此函数用于模拟吃肉过程
MeatNo[i]:
判断第n个哲学家在吃第n块肉
EatTimeAll[i]判断第n个哲学家吃肉共需要n秒
EatTime[i]：
判断吃肉进行到第n秒
5．voidthinking（）函数功能:
判断第n个哲学家是否在思考
Thinking[i]：
返回1表示在思考，0则不是
6．voidmain（）：
主函数用来打印出前面的所有模拟情况
5.2.3.模块图
5.3.步骤3：
代码实现以及测试
5.3.1.代码实现：
#include
#include
#definepeople5
#definemeat10//肉块的数量
staticintTman[people];//用于判断筷子是否可用，如果可以，返回0，否则返回1。
intn=1;//定义n为共吃肉的数量
/////////////////////定义一些需要跟哲学家对应的数组///////////////////////
staticintThinking[people];//第n个哲学家在思考。
如果1为就是真，0就假
staticintEating[people];//第n个哲学家在吃。
1为真，0为假
staticintEatTimeAll[people];//第n个哲学家吃肉的总时间
staticintEatTime[people];//第n个哲学家正吃肉的总时间
staticintMeatNo[people];//第n个哲学家选择第n块肉
intgetkey（inti）
{
//key（）;
if（i!
=1）
{
if（i%2!
=0）//奇数就从左手开始拿筷子,然后再到右手。
{
if（Tman[i-1]==0）//i-1为第i个哲学家的左边的筷子表示该筷子0可用，1表示正在被用
{
Tman[i-1]=1;
if（Tman[i]==0）
{
Tman[i]=1;
return1;
}
else
{
Tman[i-1]=0;
return0;
}
}
else
{
return0;
}
}
else//偶数先从右手开始拿筷子。
{
if（Tman[i]==0）//i-1为第i个哲学家的左边的筷子表示该筷子0可用，1表示正在被用
{
Tman[i]=1;
if（Tman[i-1]==0）
{
Tman[i-1]=1;
return1;
}
else
{
Tman[i]=0;
return0;
}
}
else
{
return0;
}
}
}
else
{
if（Tman[5]==0）
{
Tman[5]=1;
if（Tman[1]==0）
{
Tman[1]=1;
return1;
}
else
{
Tman[5]=0;
return0;
}
}
else
{
return0;
}
}
}
voideat（）//n表示要吃的第n块肉
{
inti;
for（i=1;i<=people;i++）
{
intwant;//想吃肉的哲学家
want=1+rand（）%5;
if（getkey（want）&&n<=meat）
{
Eating[want]=1;
Thinking[want]=0;
printf（"第%d个哲学家开始吃第%d块肉\n",want,n）;
MeatNo[want]=n;
EatTimeAll[want]=1+rand（）%3;//哲学家不会无止境的吃下去的，
//EatTime[i]=EatTimeAll[i];//我设以分钟内的随机时间为
n++;
}
}
}
voideatting（）
{
inti;
for（i=1;i<=5;i++）
{
if（Eating[i]==1）
{
EatTime[i]++;
printf（"第%d个哲学家正在吃第%d块肉,共需%d秒,已用%d秒\n",i,MeatNo[i],EatTimeAll[i],EatTime[i]）;
}
if（EatTime[i]==EatTimeAll[i]&&EatTime[i]!
=0）
{
printf（"第%d个哲学家已经吃完第%d块肉\n",i,MeatNo[i]）;
MeatNo[i]=0;
Tman[i-1]=0;
Tman[i]=0;
Eating[i]=0;
Thinking[i]=1;
EatTime[i]=0;
}
}
}
voidthinking（）
{
inti;
for（i=1;i<=5;i++）
{
if（Thinking[i]）
{
printf（"第%d个哲学家正在思考。
\n",i）;
}
}
}
voidmain（）
{
inti,time;
//初始化
for（i=1;i<=people;++i）
{
Tman[i]=0;
EatTime[i]=0;
Eating[i]=0;
Thinking[i]=1;
}
time=0;
for（;n<=meat;）
{
++time;
printf（"=================这是第%d秒的开始==================\n",time）;
eat（）;
thinking（）;
eatting（）;
printf（"=================这是第%d秒的结束==================\n\n",time）;
}
printf（"哈哈,盘子里已经没有肉了.\n"）;
}
5.3.2.测试：
测试时出现错误有
1．主函数里未初始化哲学家的思考，用餐等的状态
2．那些状态忘了设返回值
6.设计结果及分析
运行结果：
分析：
界面显示出哲学家思考，吃肉状态，有吃肉则表明两支筷子均拿到了，思考的则表明未能拿到两支筷子而在等待。
7.设计结论
1．根据我们所选的方法，达到了使哲学家吃肉的时候不会有人饿死的目的。
2．实现随机的选取第N个哲学家能拿到两支筷子，吃第N块肉，而吃肉时间在3秒内的一个随机数
3．实现了记录吃肉时间
8.问题及心得体会
通过这次课程设计，我们复习并且巩固了进程管理的知识点，在做设计时我们遇到了很多困难，如各模块的代码实现，在编译时总有错误，在网络和书籍的帮助下，我们解决了那些问题，使自己获得曾不懂得知识点。
对信号量的理解还是有些欠缺，但是我们充分的理解了死锁情况，并利用书籍提供的方法解决了这一问题。
总之，每一次课程设计不仅是我们学习的好机会，而且是我们锻炼实际动手能力的平台，虽然有难度的东西总会让人很抵触，比如在课设过程中有很多郁闷的时候，一个小小的错误一不小心就花去了自己一上午的时间，所以在这个过程中能够磨练人的意志与耐心，最后感谢我们小组所有成员的配合默契
9.对本设计过程及方法、手段的改进建议
1．因为所用的工具是vc++6.0，所以界面上不够美观，看的时候也比较麻烦。
可以使用一些有生成窗口语言编写，如C#。
2．最后代码上最好再设计一个模块，使其自动记录每个哲学家用餐，思考，吃肉总数的情况。
使用户便于观察。
10.参考文献
[1]《计算机操作系统》（第三版），汤小丹，梁红兵，哲凤屏，汤子瀛编著，西安电子科技大学出版社
[2]
11.课程设计评价（教师）
1．符合设计内容，达到设计目的，设计步骤与方法正确，设计结果正确。
是（）否（）基本正确（）
2．设计报告格式符合规范，所附图表清晰。
是（）否（）基本符合（）
3．源代码书写正确，按时完成设计报告。
是（）否（）基本正确（）
升级会员 