利用线程机制实现“哲学家进餐”问题.doc

扬州大学《操作系统》课程设计说明书 1 /9 操作系统课程设计题目进程同步模拟设计—哲学家就餐学院信息工程专业计算机科学与技术班级 1102 姓名王卫其指导教师邹姝稚 20014 年1月7日利用线程机制实现“哲学家进餐”问题 1. 设计目的 “哲学家就餐”模型,掌握基本的同步、互斥算法。 ,理解并发过程中的死锁现象。扬州大学《操作系统》课程设计说明书 2 /9 Linux 多线程创建及并发机制、线程同步机制。 Linux POSIX 线程接口实现无死锁的哲学家就餐问题。 2. 需求分析 问题描述(1) 有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子,即共 5只筷子。每个哲学家的行为是思考和进餐。为了进餐,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子。思考时则同时将两支筷子放回原处(此图中以叉子代表筷子) (2) 规则: ①只有拿到两只筷子时,哲学家才能吃饭; ②如果筷子已经在他人手上,则该哲学家必须等到他人吃完之后才能拿到筷子; ③任何一个哲学家在自己没有拿到两只筷子吃饭之前,决不放下自己手中的筷子。(3) 由此出现的问题: 可能出现死锁问题,因为当五个哲学家都饥饿时,都拿着一支筷子,这样就可能五个哲学家都用不上餐 问题分析该问题可用记录型信号量或者是 AND 型信号量解决。记录型信号量解决: 经分析可知,放在桌子上的筷子是临界资源,在一段时间内只允许一位哲学家使用,为了实现对筷子的互斥使用,可以用一个信号量表示一只筷子,由这五个信号量组成信号量数组。当哲学家饥饿时总扬州大学《操作系统》课程设计说明书 3 /9 是先拿其左边的筷子,成功后,再去拿右边的筷子,又成功后方可就餐。进餐完,又先放下他左边的筷子,再放下右边筷子。这个算法可以保证不会有两个相邻的哲学家同时就餐,但有可能引起死锁。 AND 型信号量解决: 在哲学家就餐过程中,要求每个哲学家先获得两个临界资源后方能就餐,这在本质上就是 AND 同步问题,故用 AND 信号量机制可获得最简洁的解法。 解决方法对于死锁问题可采取这样的几种解决方法: (1) 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家可以进餐,最终总会释放出他所用过的两只筷子,从而可使更多的哲学家进餐; (2) 仅当左右两只筷子均可用时,才允许哲学家拿起筷子就餐(3) 规定奇数号哲学家先拿起右边筷子,然后再去拿左边筷子,而偶数号哲学家则相反。(4) 把筷子顺序编号 fk0, fk1, fk2, fk3, fk4 ,给每个哲学家分配筷子时,必须依从小号到大号(或者相反顺序)进行。本实验,我们采用第二种解决方法 3. 功能设计 数据结构及模块说明主要的数据结构及模块有: class ChopStick (筷子类) class Philosopher (哲学家类) (1) class ChopStick {数据成员: int ID; //筷子编号 bool available //筷子是否可用函数成员: Bool takeup( )//筷子拿起操作{While(!available){ return false;} //判断筷子现在是否可用 Available =