利用多线程实现哲学家就餐.doc

操作系统课程设计报告题目: 利用多线程机制实现“哲学家就餐”所在学院: 信息工程学院班级: 计科 1102 学号: 111903232 姓名: 王卫其指导教师: 邹姝稚日期: 2014 年1月7日 1. 设计目的 1. 理解“哲学家就餐”模型,掌握基本的同步、互斥算法。 2. 理解操作系统中进程和线程的异同,理解并发过程中的死锁现象。 3. 掌握 Linux 多线程创建及并发机制、线程同步机制。 4. 掌握和使用 Linux POSIX 线程接口实现无死锁的哲学家就餐问题。 2. 需求分析 问题描述有五个哲学家围坐在一圆桌旁, 桌中央有一盘通心粉, 每人面前有一只空盘子, 每两人之间放一只筷子,即共 5 只筷子。每个哲学家的行为是思考和进餐。为了进餐, 每个哲学家必须拿到两只筷子, 并且每个人只能直接从自己的左边或右边去取筷子。思考时则同时将两支筷子放回原处(此图中以叉子代表筷子) 规则: ①只有拿到两只筷子时,哲学家才能吃饭; ②如果筷子已经在他人手上,则该哲学家必须等到他人吃完之后才能拿到筷子; ③任何一个哲学家在自己没有拿到两只筷子吃饭之前,决不放下自己手中的筷子。由此出现的问题: 可能出现死锁问题, 因为当五个哲学家都饥饿时, 都拿着一支筷子, 这样就可能五个哲学家都用不上餐 问题分析该问题可用记录型信号量或者是 AND 型信号量解决。记录型信号量解决: 经分析可知,放在桌子上的筷子是临界资源,在一段时间内只允许一位哲学家使用,为了实现对筷子的互斥使用, 可以用一个信号量表示一只筷子, 由这五个信号量组成信号量数组。当哲学家饥饿时总是先拿其左边的筷子, 成功后, 再去拿右边的筷子, 又成功后方可就餐。进餐完, 又先放下他左边的筷子, 再放下右边筷子。这个算法可以保证不会有两个相邻的哲学家同时就餐,但有可能引起死锁。 AND 型信号量解决: 在哲学家就餐过程中, 要求每个哲学家先获得两个临界资源后方能就餐, 这在本质上就是 AND 同步问题,故用 AND 信号量机制可获得最简洁的解法。 解决方法对于死锁问题可采取这样的几种解决方法: (1) 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家可以进餐,最终总会释放出他所用过的两只筷子,从而可使更多的哲学家进餐; (2) 仅当左右两只筷子均可用时,才允许哲学家拿起筷子就餐(3) 规定奇数号哲学家先拿起右边筷子, 然后再去拿左边筷子, 而偶数号哲学家则相反。(4) 把筷子顺序编号 fk0, fk1, fk2, fk3, fk4 ,给每个哲学家分配筷子时,必须依从小号到大号(或者相反顺序)进行。本实验,我们采用第二种解决方法 3 .程序流程图 主程序流程图程序由开始到定义筷子信号量 tool[5] ,到定义哲学家类对象 P1-P5 ,哲学家的状态改变用 () 来控制,输出当前状态图后判断程序结束开始返回上一菜单。如图 2-1 所示。图3 -1 主程序模块流程图 状态改变模块 chang() 流程图: 其中重要的是状态改变模块 chang(), 开始后先判断哲学家的状态,若哲学家的状态为 1 ,即处于吃饭状态则,执行放下筷子(资源)操作;若处于状态 2 ,则改变哲学家状态为等待,并将哲学家状态设置为 0 ;若哲学家处于状态 0 ,则判断左右手的筷子是否都为空闲,若都为空闲则拿起左右筷子,并将哲学家状态改为 1. 如图 2-2 所示。图3 -2 状态改变模块 Chang() 流程图 哲学家状态模块 print() 流程图: 哲学家状态输出图先定义一个状态数 i, 判断 i 的值, 根据 i 的值来输出哲学家的状态。如图 3 -3 所示。图3 -3 返回哲学家状态模块 print() 流程图 返回餐具状态模块定义一个字符串型的变量 state ,当a 的值为 true 时, state 为“闲”,当a 的值为 fals e 时, state 为“用”。如图 2-4 所示。图3 -4 返回餐具状态模块图 4. 内容与详细设计 开发内容现代操作系统引入并发程序设计技术之后, 程序的执行不再是顺序的, 一个程序为执行完而另一个程序就已经开始执行, 程序外部的顺序特性消失, 程序与计算不再一一对应。于是人们引入进程来描述这种变化。一组进程在执行时间上是重叠的,进程即并发执行。在多个进程并发运行的过程中,进程之间可能是无关的, 也可能是交互的。交互进程之间可能产生的关系, 包括竞争和协作。并发进程中与共享变量有关的程序段成为临界区,共享变量所代表的资源成为临界资源。有多种方法可以实现对临界区、临界资源的管理。