哲学家就餐问题华科操作系统.doc

操作系统实验报告实验名称：哲学家就餐问题 院系：电子与信息工程系班级：通信1004学号：U201013086姓名：张建佳 2012-6-20一.实验目的1、读懂mfc编写的科学家就餐程序，对C语言加深理解。 2、理解哲学家就餐问题中出现的问题，进而掌握死锁的必要条件。 3、理解源程序中产生和防止的算法，及相关窗口操作。二.实验原理：1、问题描述 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两 人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心 粉， 每个哲学家必须拿到两只筷子， 并且每个人只能直接从自己的左边或右边去取筷子。2、本程序防止死锁发生采取的措施仅当一个哲学家左右两边的筷子都可用时， 才允许他拿筷子。 这样要么一次占有两只 筷子（所有线程需要的资源）进行下一步的吃通心粉，然后释放所有的资源；要么不占 用资源，这样就不可能产生死锁了。 3、产生死锁的分配方式当筷子（资源）可用时，先分配左边的筷子，等待一会后再分配右边的筷子，由于这 个过程中，左边的筷子一直没有释放，就有可能产生死锁了。 4、程序运行说明 程序运行过程中会弹出一个 MessageBox 提示操作者操作： 1）第一个对话框用于选择运行模式 a选择 yes 表示采用的是运行的防止死锁的方式，这样的话整个程序可以一直运 行下去，不会产生死锁。 b选择 no 表示运行产生死锁的方式会弹出第二个对话框。 2）第二个对话框用于选择运行时，线程运行的时间 a. 选择 res 线程时间比较短，很快就可以死锁 b选择 no 线程时间跟选择 yes 时候的时间差不多，产生死锁的时间稍微长一点。三.实验过程及分析：1、伪代码： (1) 不发生死锁的方式（要么一下占用两支筷子，要么不占用 ） var mutexleftchopstick,mutexrightchopstick;beging: resting; waiting;p(mutexleftchopstick); /先改变左手筷子信号量p(mutexrightchopstick); /马上改变右手筷子信号量 GetResource(leftchopstick,rightchopstick);eating; v(mutexleftchopstick); v(mutexrightchopstick);end (2) 发生死锁的方式（一旦可以占用筷子，就马上占用） var mutexleftchopstick,mutexrightchopstick;beging: resting; waiting; p(mutexleftchopstick); /改变左手筷子信号量 GetResource(leftchopstick); /获取左手筷子 p(mutexrightchopstick); /改变右手筷子信号量 GetResource(rightchopstick); /获取右手筷子 eating; v(mutexleftchopstick); v(mutexrightchopstick); end 2、代码分析 (1）不发生死锁的方式：先确定两只筷子均没被占用才获取筷子，这样就打破了死锁 的必要条件。 (2） 发生死锁的方式： 有筷子即占用， 看似效率很高， 但因为资源有限， 且不可抢占， 很容易发生死锁。四.思考题：其他解决死锁的方案 1. 引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁2. 为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。3. 编号可以是任意的。(1).对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。 (2).当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。 (3).当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。 (4).当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。 这个解法允许很大的并行性，适用于任意大的问