进程同步模拟设计——哲学家就餐问题.doc

1、武汉理工大学操作系统课程设计说明书学 号： 01201034课 程 设 计题 目进程同步模拟设计哲学家就餐学 院计算机科学与技术专 业计算机科学与技术班 级计算机姓 名指导教师20011年1月19日课程设计任务书学生姓名： 专业班级： 计算机 指导教师： 工作单位： 计算机科学与技术学院 题 目: 进程同步模拟设计哲学家就餐问题 初始条件：1预备内容：阅读操作系统的进程管理章节内容，对进程的同步和互斥，以及信号量机制度有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟用信号量机制实现哲学家就餐问题。2

2、设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：

3、年 月 日系主任（或责任教师）签名： 年 月 日进程同步模拟设计哲学家就餐问题1. 需求分析1.1问题描述(1) 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，即共5只筷子。每个哲学家的行为是思考和进餐。为了进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。思考时则同时将两支筷子放回原处（此图中以叉子代表筷子）(2) 规则：只有拿到两只筷子时，哲学家才能吃饭；如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子； 任何一个哲学家在自己没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。(3) 由此出现的问题

4、：可能出现死锁问题，因为当五个哲学家都饥饿时，都拿着一支筷子，这样就可能五个哲学家都用不上餐1.2问题分析该问题可用记录型信号量或者是AND型信号量解决。记录型信号量解决：经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量组成信号量数组。当哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，又成功后方可就餐。进餐完，又先放下他左边的筷子，再放下右边筷子。这个算法可以保证不会有两个相邻的哲学家同时就餐，但有可能引起死锁。AND型信号量解决：在哲学家就餐过程中，要求每个哲学家先获得两个临界资源后方

5、能就餐，这在本质上就是AND同步问题，故用AND信号量机制可获得最简洁的解法。1.3解决方法 对于死锁问题可采取这样的几种解决方法： (1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐； (2)仅当左右两只筷子均可用时，才允许哲学家拿起筷子就餐 (3)规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反。(4)把筷子顺序编号 fk0, fk1, fk2, fk3, fk4，给每个哲学家分配 筷子时，必须依从小号到大号（或者相反顺序）进行。 本实验，我们采用第二种解决方法2. 功能设计 2.1数据结构

6、及模块说明 主要的数据结构及模块有： class ChopStick （筷子类） class Philosopher （哲学家类）(1) class ChopStick数据成员：int ID; /筷子编号bool available /筷子是否可用函数成员：Bool takeup() /筷子拿起操作While(!available) return false;/判断筷子现在是否可用Available=false; /筷子被拿起之后就不可用了Return true;Void Putdown() /筷子放下操作Available=true; /放下之后就可用了(2) class Philosoph

7、er数据成员：Int ID; /哲学家编号ChopStick left,right; /左右筷子函数成员：Bool eat() /进餐函数Void Think() /思考函数Void Finish() /进餐结束函数 3. 开发平台及源程序的主要部分int main()ChopStick chopsticks5=ChopStick(0),ChopStick(1),ChopStick(2),ChopStick(3),ChopStick(4);Philosopher philos5=Philosopher(0, chopsticks0, chopsticks4),Philosopher(1, ch

8、opsticks1, chopsticks0),Philosopher(2, chopsticks2, chopsticks1),Philosopher(3, chopsticks3, chopsticks2),Philosopher(4, chopsticks4, chopsticks3);bool b5;int i,j; L:srand(time(0); j = rand()%5; /产生-4之间的随机数for(i = j; i j+5; i +)bi%5=philosi%5.eat(); /保留eat()的返回值coutendl-endl;for(i=j;i5+j;i+)if(bi%5)

9、 philosi%5.finish(); /在i哲学家吃完了以后要考虑他的左右两个哲学家是否吃过饭了if(!bi%5+1) bi%5+1=philosi%5+1.eat(); /左边的if(!b(i%5+4)%5) b(i%5+4)%5=philos(i%5+4)%5.eat(); /右边的else bi%5=philosi%5.eat();if(bi%5) continue; /如果还吃不上怎么办呢？else cout哲学家i%5还需等待endl;coutendl-endl;couttemp;if(temp=y | temp=Y) goto L;Sleep(2000);system(pasu

10、e);return 0;4. 测试用例及运行结果以及分析产生了一个随机数1，并依次加1对每个哲学家进行分析。分析时首先看左筷子是否可用，然后看右筷子，若有一个不可用则输出来。然后再下一时间段对每个哲学家再次分析，如下：5. 自我评价与总结5.1多线程编程对于解决一些并发性的问题是很高效的，而且也很必要，现在学会了使用多线程编程，对于以后解决类似的并发性问题（例如网络编程中经常遇到的多客户线程同时访问的问题），都会很有用。 5.2虽然我们学习的操作系统理论课里面说多线程间的执行顺序具有随机性和不确定性，但我们毕竟是在一个特定的操作系统平台上实验，Windows 的线程调度机制我是不得而知的，所以

11、出现的一些奇怪的问题也很难调试，只好人为地去改变线程间的顺序以求模拟出一定的随机性。 5.3由于编写的线程函数philosopherProc需要参数传递，因此在创建线程CreateThread时没有将参数写上，采用默认的NULL 值，造成参数param 赋值给哲学家myid 时出现错误。后来在CreateThread()的第四个形参改为(void*)&i 正确执行。其余的参考吃苹果问题并没有很大的问题。6. 附件筷子类代码：(ChopStick.h)#includeusing namespace std;class ChopStickprivate:int id; bool available

12、;public: ChopStick(int i=0) id=i; available=true; /可以拿起 bool takeup() /拿起动作 while(!available) return false; available=false; return true; void putdown() /放下动作 available=true; ;哲学家类代码：(Philosopher.h)#includechopstick.h#includeclass Philosopherprivate: ChopStick &left, &right; int philo_num; /哲学家编号pub

13、lic:Philosopher (int num, ChopStick &c1, ChopStick &c2):left(c1),right(c2) philo_num = num; bool eat() bool br,bl; bl=left.takeup(); if(!bl) cout哲学家philo_num在等待左筷子endl;Sleep(1000); return false; br=right.takeup(); if(!br) cout哲学家philo_num在等待右筷子endl; left.putdown(); /不能拿右筷子时，要把左筷子放下Sleep(1000); retur

14、n false; cout哲学家philo_num 正在进餐endl; Sleep(1000); return true; void think() left.putdown(); right.putdown(); cout哲学家philo_num 正在思考endl; Sleep(1000); void finish() Sleep(1000); cout哲学家philo_num进餐结束！endl; think(); ;主程序代码：（Main.cpp）#includephilosopher.h#include#includeusing namespace std; int main()Chop

15、Stick chopsticks5=ChopStick(0),ChopStick(1),ChopStick(2),ChopStick(3),ChopStick(4);Philosopher philos5=Philosopher(0, chopsticks0, chopsticks4),Philosopher(1, chopsticks1, chopsticks0),Philosopher(2, chopsticks2, chopsticks1),Philosopher(3, chopsticks3, chopsticks2),Philosopher(4, chopsticks4, chops

16、ticks3);bool b5;int i,j; L:srand(time(0); j = rand()%5; /产生-4之间的随机数for(i = j; i j+5; i +)bi%5=philosi%5.eat(); /保留eat()的返回值coutendl-endl;for(i=j;i5+j;i+)if(bi%5) philosi%5.finish(); /在i哲学家吃完了以后要考虑他的左右两个哲学家是否吃过饭了if(!bi%5+1) bi%5+1=philosi%5+1.eat(); /左边的if(!b(i%5+4)%5) b(i%5+4)%5=philos(i%5+4)%5.eat(); /右边的else bi%5=philosi%5.eat();if(bi%5) continue; /如果还吃不上怎么办呢？else cout哲学家i%5还需等待endl;coutendl-endl;couttemp;if(temp=y | temp=Y) goto L;Sleep(2000);system(pasue);return 0; 10 / 10