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

操作系统课程设计报告
题目: 利用多线程机制实现“哲学家就餐”
所在学院: 信息工程学院
班级: 计科1102
学号: 111903232
姓名: 王卫其
指导教师: 邹姝稚
日期: 2014 年 1 月 7日

“哲学家就餐”模型,掌握基本的同步、互斥算法。
,理解并发过程中的死锁现象。
、线程同步机制。
POSIX线程接口实现无死锁的哲学家就餐问题。


有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子,即共5只筷子。
每个哲学家的行为是思考和进餐。为了进餐,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子。思考时则同时将两支筷子放回原处
(此图中以叉子代表筷子)
规则:
①只有拿到两只筷子时,哲学家才能吃饭;
②如果筷子已经在他人手上,则该哲学家必须等到他人吃完之后才能拿到筷子;
③任何一个哲学家在自己没有拿到两只筷子吃饭之前,决不放下自己手中的筷子。
由此出现的问题:
可能出现死锁问题,因为当五个哲学家都饥饿时,都拿着一支筷子,这样就可能五个哲学家都用不上餐

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

对于死锁问题可采取这样的几种解决方法:
(1)至多只允许四个哲学家同时进餐,以保证至少有一个哲学家可以进餐,最终总会释放出他所用过的两只筷子,从而可使更多的哲学家进餐;
(2)仅当左右两只筷子均可用时,才允许哲学家拿起筷子就餐
(3)规定奇数号哲学家先拿起右边筷子,然后再去拿左边筷子,而偶数号哲学家则相反。
(4)把筷子顺序编号 fk0, fk1, fk2, fk3, fk4,给每个哲学家分配
筷子时,必须依从小号到大号(或者相反顺序)进行。
本实验,我们采用第二种解决方法


程序由开始到定义筷子信号量tool[5],到定义哲学家类对象P1-P5,()来控制,输出当前状态图后判断程序结束开始返回上一菜单。如图2-1所示。

图3-1 主程序模块流程图
状态改变模块chang()流程图:
其中重要的是状态改变模块chang(),开始后先判断哲学家的状态,若哲学家的状态为1,即处于吃饭状态则,执行放下筷子(资源)操作;若处于状态2,则改变哲学家状态为等待,并将哲学家状态设置为0;若哲学家处于状态0,则判断左右手的筷子是否都为空闲,若都为空闲则拿起左右筷子,-2所示。
图3-2 状态改变模块Chang()流程图
哲学家状态模块print()流程图:
哲学家状态输出图先定义一个状态数i,判断i的值,根据i的值来输出哲学家的状态。如图3-3所示。
图3-3 返回哲学家状态模块print()流程图
返回餐具状态模块
定义一个字符串型的变量state,当a的值为true时,state为“闲”,当a的值为false时,state为“用”。如图2-4所示。

图3-4返回餐具状态模块图


现代操作系统引入并发程序设计技术之后,程序的执行不再是顺序的,一个程序为执行完而另一个程序就已经开始执行,程序外部的顺序特性消失,程序与计算不再一一对应。于是人们引入进程来描述这种变化。
一组进程在执行时间上是重叠的,进程即并发执行。在多个进程并发运行的过程中,进程之间可能是无关的,也可能是交互的。交互进程之间可能产生的关系,包括竞争和协作。
并发进程中与共享变量有关的程序段成为临界区,共享变量所代表的资源成为临界资源。
有多种方法可以实现对临界区、临界资源的管理。其中最基本的方法是设置相应的信号量和P、V操作。
在并发进程执行的过程中,对共享资源的竞争可能产生死锁问题,既一个进程集合中的每个进程都在等待只能由此集合