《操作系统课程设计哲学家就餐问题》由会员分享，可在线阅读，更多相关《操作系统课程设计哲学家就餐问题（17页珍藏版）》请在金锄头文库上搜索。
1、摘 要2第一章 课程设计的目的及要求31.1 设计目的31.2 设计要求31.3 设计环境3第二章 需求分析42.1 问题描述：42.2 问题分析：4第三章 详细分析53.1 问题定义53.2 算法分析：53.3 界面设计6第四章 程序部分代码分析8第五章 新得体会10第六章 参考文献11附录 11摘要在多道程序环境下,进程同步问题十分重要,也是相当有趣的问题,因而吸引 了不少学者对它进行研究,由此而产生一系列经典的进程同步问题.其中较有代 表性的是哲学家进餐问题等等,通过这些问题的研究和学习,可以帮助我们列好 地理解进程同步概念及实现方法.由Dijks tra提出并解决的哲学家进餐问题(Th
2、e Dinning Philosophers Problem)是典型的同步问题，该问题是描述有五个哲学家共用一张圆桌,分别坐 在周围的五张椅子上,在圆桌上有五个碗和五只筷子,他们的生活方式是交替地 进行思考和进餐, 平时, 一个哲学家进行思考, 饥饿时便试图取用其左右最靠近他 的筷子,只有在他拿到两只筷子时才能进餐,进餐毕,放下筷子继续思考.由于筷子数目有限，不能让五个哲学家同时进餐，而且甚至只能让其中的少 数哲学家进餐，其他的哲学家只能轮流享用，这非常类似多线程之间的同步互斥 问题，所以采用windows的多线程及一些API函数实现了对这个经典算法的模拟.第一章 课程设计的目的及要求1.1设
3、计目的通过本次课设，对本学期的操作系统课程的学习理论知识的一次应用。是理 论结合实际的一次应用。让我们学会对竞争资源的操作，控制，同时锻炼我们的 编程水平。使我们掌握多线程编程的方法； 掌握MFC程序设计和API应用程序编程；培养我们基本控制程序的安全性及避免死锁的方法；培养我们分析、解决问题的能力；锻炼我们的自学能力；培养我们的组队合作能力；提高学生的科技论文写作能力。1.2设计要求利用多线程编程模拟5个线程，竞争五个筷子去吃通心面;对临界资源的操作算法要简单易行； 程序运行时不会产生死锁； 对所设计的各模块系统进行调试； 独立完成程序的设计与调试； 设计好各个功能模块，合理安排他们的位置；
4、 程序结构清晰； 程序界面友好直观。1.3设计环境开发程序的操作系统：WindowsXP (在Windows 7/Windows 2000里也适用) 编译工具： visual C+ 6.0程序工程：MFC AppWizard(exe)的对话框工程第二章 需求分析2.1 问题描述：由 Dijkstra 提出并解决的哲学家进餐问题 (The Dinning Philosophers Problem) 有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和 五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思 考，饥饿时便试图取用其左右最靠近他的筷子，只有他拿到两只
5、筷子时才能进餐。 进餐毕，放下筷子继续思考。2.2 问题分析：经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学 家使用。在设计实现与演示该问题时，为了实现对筷子的互斥使用，程序中使用 互斥量表示一只筷子，每一支筷子使用一个互斥量，五个筷子总共需要五个互斥 量所有信号量。当哲学家饥饿时，总是先去拿他左边的筷子，成功后再去拿他右边的筷子， 如果两次操作都成功便可进餐。进餐毕，先放下他左边的筷子，然后再放下他右 边的筷子。为了模拟实现五个哲学家的进餐情况，利用操作系统提供的多线程来模拟进 程实现哲学家进餐的过程功能，其中一个为主线程，用于为要进餐的哲学家提供 场所。子线程与主线程并
6、行执行，主线程控制着它们的生成。子线程用于处理要进 餐的哲学家，其功能有申请筷子、把申请到筷子的哲学家置为进餐状态、释放筷 子。第三章 详细分析3.1 问题定义在哲学家问题中，我们首先要对哲学家们进餐问题做一些规则，规则如下：1. 互斥解决。每一把叉子使用一个 2 元信号量，只有获得信号量的哲学家才能 使用叉子，从而避免对叉子的“抢夺”。2. 死琐和饥饿解决。餐厅只允许最多 4 名哲学家进入，因为总有一个哲学家可 以得到两把叉子，从而可以正常就餐，因此不会有死琐出现。每为哲学家就餐完 毕后，立即离开，放下叉子，以便没有用餐的哲学家可以使用，这也能保证不会 有饥饿的存在了。3. 就餐顺序随机。为
7、了较真实地模拟现实就餐问题，哲学家每次进入餐厅的顺 序总是随机的，这个随机顺序在哲学家开始进入之间通过一个函数产生4. 哲学家的各种状态。 思考：当哲学家没有就座的时候，该位置显示空闲状态。 等待：当一个哲学家进入餐厅但是没有获得餐具就餐的时候，进入思考等待状 态。吃饭中：哲学家获得餐具后开始就餐进入就餐状态。 离开：哲学家就餐完毕就到了离开状态。每个哲学家的就餐过程通过一个线程函数的调用来实现。 主线程与子线程的通信：3程3.2 算法分析：第一种算法:：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用 又都放下左侧筷子， 等一会儿，又同时拿起左侧筷子，如此这般，永远重复。 对于这种情况
8、，即所有的程序都在 无限期地运行，但是都无法取得任何进展， 即出现饥饿，所有哲学家都吃不上饭。第二种算法：规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果 不可用，则先放下左侧筷子，等一段时间再重复整个过程。 分析：当出现以下 情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而 看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子 如此，这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得 进展，即出现饥饿，所有的哲学家都吃不上饭。第三种算法：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够 进餐,最终总会释放出他所使用过的两支筷子,
9、从而可使更多的哲学家进餐。以下 将 room 作为信号量，只允 许 4 个哲学家同时进入餐厅就餐，这样就能保证至 少有一个哲学家可以就餐，而申请进入 餐厅的哲学家进入 room 的等待队列， 根据 FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。第四种算法：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。 利用 AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时 需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死 锁的情形。当某些资源不够时阻塞调用进程 ;由于等待队列的存在，使得对资源 的请求满足 FIFO 的要求，因此不会出现
10、饥饿的情形。第五种算法： 规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边 的筷子;而偶数号的哲学家则相反.按此规定,将是 1,2 号哲学家竞争 1 号筷子,3,4 号哲学家竞争 3 号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数 号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进 入阻塞等待队列，根 FIFO 原则，则先申请的哲学家会较先可以吃饭。3.3 界面设计下图（图 3.1.1）为程序的启动界面，图中五个卡通人物代表五位吃饭的哲 学家，其身边分别搁置了一支白色的筷子。界面底端搁置了四个 Button 分别是 开始、停止、关闭、说明，还有一个用来控制
11、哲学家用餐的速度的滚动条。还没开贻呢还没开始呢奸香呀！（就餐奸香呀！（就緩丁背学靈进餐何蛊哲学蠢进鑒同题我饿喔!等待1速度调节说明我餓喔！（等待y我饿喔！等待）还没开始呢还没开始呢还没开始呢图3.3.1程序初启动界面停止图3.32哲学家就餐中上图（3.3.2）是哲学家正在就餐的截图，从图中我们可以看出有两位哲学 家正就餐而其他的哲学家正处于等待中，正在就餐的哲学家分别从他身旁两边 拿取筷子从而就餐。下图（3.3.3）是哲学家在就餐的时候所处的不同的状态的截图，从图中我 们可以看到有的哲学家正处于就餐状态，有的出于等待别人释放资源（筷子）， 有的还处于申请资源（筷子）的状态。图3.3.3哲学家就
12、餐时处于不同状态截图第四章 程序部分代码分析显示控制模块函数：函数在 GradientStatic.cpp 文件void CGradientStatic:OnPaint()CPaintDC dc(this); / device context for painting dc.SetBkMode(TRANSPARENT);CBrush BkBrush;BkBrush.CreateSolidBrush(m_colorBK);CPen BkLinePen;BkLinePen.CreatePen(PS_SOLID, 1, m_colorBKLine); dc.SelectObject(&BkBrush
13、);dc.SelectObject(&BkLinePen);CRect rcClient;GetClientRect(rcClient); rcClient.InflateRect(-1,-1,1,1);CPoint point(m_iRadius,m_iRadius); dc.RoundRect(rcClient,point);CBrush brush; brush.CreateSolidBrush(RGB(169,196,255);/picture box 控件背景色 dc.SelectObject(brush);ScreenToClient(rcClient);rcClient.top
14、= rcClient.top + 25; rcClient.bottom = rcClient.top + 150; dc.RoundRect(rcClient,point);CDC pMemDc; pMemDc.CreateCompatibleDC(&dc); pMemDc.SetBkMode(dc.GetMapMode();BITMAP bt;位图图片文件变量for(int i = 0;ithi nkerStatusi = THINKING_STATUS)/思考状态 m_pBmpThink.GetBitmap(&bt); pMemDc.SelectObject(m_pBmpThink);e
15、lse if(m_pthi nker-th in kerStatusi = EATING_STATUS)/吃 饭状态 m_pBmpEat.GetBitmap(&bt); pMemDc.SelectObject(m_pBmpEat);else if(m_pthi nker-thi nkerStatusi = HUNGRY_STATUS)/饥饿状态 m_pBmpWait.GetBitmap(&bt); pMemDc.SelectObject(m_pBmpWait);else m_sTEXT = ; dc.StretchBlt(20 + ( 25 + bt.bmWidth ) *i ,60,bt.bmWidth,bt.bmHeight,&pMemDc,0,0,bt.bmWidth,bt.bmHeight,
