哲学家就餐问题

1、哲学家就餐问题哲学家就餐问题模拟数学与计算机学院课程设计说明书课程名称:操作系统原理 - 课程设计课程代码:8404061题目:哲学家就餐问题模拟年级/ 专业/ 班: 09级信息与计算科学三班学生姓名:徐磊学号: 312009070102301开始 时 间: 2012年05月 14日完成 时 间: 2012年05月 31日课程设计成绩：学习态度及平时技术水平与实际总 分创新（ 5）说明书撰写质量（ 45 ）成绩（ 30 ）能力（ 20 ）（100 ）I哲学家就餐问题模拟目录1引言 .11.1问题的提出 .11.2任务与分析 .12.总体设计思想及相关知识 .12.1 总体设计思想 .12.2临

2、界区互斥编程原理 .23程序运行平台 .24程序类的说明 .25程序各个模块流程图 .35.1主程序模块 .35.2状态改变模块 .45.3返回哲学家状态图 .56 系统测试 .78结论 .11I哲学家就餐问题模拟1 引言1.1 问题的提出哲学家进餐问题也是一个经典的同步问题， 它是由 Dijkstra 提出并解决的。 哲学家进餐问题是这样的：个哲学家以思考、吃饭交替进行的方式生活，他们共享一张周围有把椅子的圆桌，每人一把椅子， 在桌子上摆有个饭碗和只筷子。当一个哲学家思考时，他不与邻座同事发生联系。当一哲学家饿了，他就试图拿起他左右两边的筷子吃饭。显然，他不能拿起已抓在他的邻座手中的筷子，于

3、是，他可能只拿到一只甚至一只筷子也拿不到。当一个饥饿的哲学家得到了两只筷子，他就可以吃饭。当他用饭毕，就放下筷子并再次开始思考。 5 个哲学家共享 5 支筷子，最多只能不相邻的两个哲学家同时就餐。在多道程序设计环境下，进程同步问题十分重要，其中“哲学家进餐问题”是较有代表性的。通过对该问题的研究学习和实践，可以帮助我们更好的理解和掌握临界资源、进程同步的概念和实现方法。1.2 任务与分析本课题主要的目的通过实现哲学家进餐问题的同步深入了解和掌握进程同步和互斥的原理。总体设计思想及相关知识2.1 总体设计思想哲学家的生活就是思考和吃饭，即思考，饿了就餐，再思考，循环往复。要求是：每一个哲学家只有

4、在拿到位于他左右筷子，才能够就餐；哲学家只能先拿一只筷子，再去拿另一只筷子， 而不能同时去抓他旁边的两只筷子，也不能从其他哲学家手中抢夺筷子；哲学家每次就餐后必须放下他手中的两只筷子后恢复思考， 不能强抓住筷子不放。设计一个程序， 能够显示当前各哲学家的状态和桌上餐具的使用情况， 并能无死锁的推算出下一状态各哲学家的状态和筷子的使用情况。 即设计一个能安排哲学家正常生活的程序。为哲学家设计 3 种状态，即“等待”“进餐”“思考”。每个哲学家重复进行“等待” -“进餐” -“思考”的行动循环。其中：“等待” -“进餐”：只有一个哲学家处于等待进餐状态，且左右手两边的筷子都处于“空闲”状态时，可以

5、发生这种状态改变。此状态改变发生后，哲学家拿起左右手两边的筷子。“进餐” -“思考”：此状态改变发生后，哲学家放下左右手上的筷子。筷子状态1哲学家就餐问题模拟由“使用中”转变为“空闲” 。“思考” -“等待”：哲学家思考结束后，无条件转入等待状态。由上所述，程序中应设置5 个元素的信号量数组，chopsticks5，用来保持哲学家之间的同步。2.2 临界区互斥编程原理不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。每个进程中访问临界资源的那段代码称为临界区（Critical Section ）。每个进程中访问临界资源的那段程序称为临界区（Critical Section

6、）（临界资源是一次仅允许一个进程使用的共享资源） 。每次只准许一个进程进入临界区，进入后不允许其他进程进入。不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。本程序主要使用了EnterCriticalSection(&cs) 和 LeaveCriticalSection(&cs) 两个函数实现临界区互斥。EnterCriticalSection (&cs)用来进入临界区， LeaveCriticalSection (&cs) 用来离开临界区。程序运行平台Visual Studio 2008。具体操作如下：新建项目，添加相应的源文件，再编译，链接，执行等。程序类的说明程序中定

7、义一个哲学家类，包含两个私有对象和四个公有对象。Philosopher-number:int-status:int+Philosopher(in num:int)+find() const:int+getinfo() const:int+Change():void2哲学家就餐问题模拟图 4-1哲学家类的 UML 图Number 对象：哲学家的编号。Status 对象：用于保存当前该哲学家的状态，0 表示正在等待（即处于饥饿状态）1 表示得到餐具正在吃饭， 2 表示正在思考Philosopher(int num) 方法：哲学家类构造函数，参数num 表示哲学家编号find() const 方法：

8、返回该哲学家编号getinfo() const 方法：返回哲学家当前状态Change()方法：根据题目要求改变哲学家的状态（等待-进餐 -思考 -等待）另外，程序中包含一个公有对象， bool 类型数组 chopsticks5 ，用来保存 5 只筷子当前状态： true 表示该餐具当前空闲， false 表示该餐具当前正被使用。程序中还包含两个公有函数： print 和 chopstickstatus 。Print 用来返回一个哲学家的状态， chopstickstatus 用来返回一个餐具的状态。程序各个模块流程图5.1 主程序模块开始定义信号量Chopsticks5定义哲学家类对象p1p5

9、哲学家的生活状态发生改变3哲学家就餐问题模拟输出当前状态图停止程序？否是结束图 5-1 主程序模块流程图5.2状态改变模块开始哲学家 处于进餐状态？Status=1？否是哲学家处于思考放下左右手的筷子状态？status=2 ？否Chopsticksnumber%5=trueChopsticks(number+14哲学家 处于等待状态？Status=0？哲学家就餐问题模拟改变状态为思考status=2改变状态为等待Status=0左右手筷子均空闲？chopsticksnumber%5&chopsticks+1)%5? 否是拿起左右筷子chopsticksnumber%5=falsechopsti

10、cksnumber%5=false改变状态为进餐Status=1结束图 5-2 状态改变模块 Change()流程图5.3返回哲学家状态图5哲学家就餐问题模拟图 5-3 返回哲学家状态模块print() 流程图6哲学家就餐问题模拟5.4 返回餐具状态模块图 5- 4 返回餐具状态模块 chopsticksstatus(bool a) 流程图系统测试首先进入 Visual Studio 2008，进入源程序。生成称解决方案，然后运行。7哲学家就餐问题模拟图 6-1 哲学家开始状态18哲学家就餐问题模拟图 6-2 哲学家状态 29哲学家就餐问题模拟图 6-3 哲学家状态 3图 6-4 哲学家状态

11、410哲学家就餐问题模拟结论对自己完成的题目进行总结，包括程序的功能、创新点（与众不同的地方）及程序存在的问题和修改对策。通过本次课程设计的过程，我了解了金典的同步问题哲学家就餐问题。发现自己对互斥变量把握不太清楚。及在编程过程中自己对 C+语法的不熟悉。本程序通过定义一个哲学家类，模拟了哲学家就餐，思考和等待的不同状态。11哲学家就餐问题模拟附录附录 1源程序清单#include #include #include#include#includeusingnamespacestd;bool chopsticks5;/全局变量，用餐工具CRITICAL_SECTION cs;/信号量 , 在线

12、程中使用，临界区class Philosopherprivate :int number;int status;/*标记当前哲学家的状态,0表示正在等待 (即处于饥饿状态 ),1表示得到两支筷子正在吃饭 ,2表示正在思考 */public :Philosopher(int num=1): status(2), number(num) int find() /定义常成员函数返回该哲学家编号constreturnnumber;int getinfo() /定义常成员函数返回哲学家当前状态constreturn status;void Change() ;/状态改变函数;void Philosoph

13、er:Change()EnterCriticalSection (&cs) ;/进入临界区if (status=1)/正在进餐chopsticks(number)%5= true ; /放下左手工具 chopsticks(number+1)%5= true ; /放下右手工具status=2;/改变状态为思考else if (status=2)/思考中12哲学家就餐问题模拟status=0;/改变状态为等待else if (status=0)/等待中if (chopsticksnumber%5&chopsticks(number+1)%5)/左右手两边筷子均为空闲状态chopsticksnum

14、ber%5= false ; /拿起左边的筷子 chopsticks(number+1)%5= false ; /拿起右边的筷子 status=1;LeaveCriticalSection (&cs) ;/释放临界区string print(Philosopher *pA)/返回哲学家状态/pA-Change();int i=pA-getinfo();string str;if (i=0)str= 等待 ;else if (i=1)str= 就餐 ;else str= 思考 ;returnstr;string chopstickstatus(bool a)/返回筷子状态string state

15、;if (a= true )state= 闲 ;if (a= false )state= 用 ;returnstate;int main()char con = y ; /判断是否继续13哲学家就餐问题模拟for (int i=1;i=5;i+)chopsticksi=true ; /5 根筷子都未使用，初始化Philosopher P1(1),P2(2),P3(3),P4(4),P5(5);InitializeCriticalSection (&cs) ;/初始化初始化临界区cout - 状态说明示意图： - endl;cout 哲学家号的状态 筷子的状态 筷子的状态 哲学家号的状态 end

16、l;cout 筷子的状态 endl;cout 哲学家号的状态 筷子的状态 筷子的状态 哲学家号的状态 endl;cout 哲学家号的状态 endl;cout 筷子的状态， “用”表示使用中， “闲”表示空闲中。 endl;cout -endl;cout 哲学家们开始生活： endl;coutendl;coutendl;while (con= y )P1.Change();P2.Change();P3.Change();P4.Change();P5.Change();/P6.Change();cout 当前状态为： endl;coutP1.find()print(&P1) chopstickstatus(chopsticks1) chopstickstatus(chopsticks2) P2.find()print(&P2)endl;cou