1、操作系统课程设计哲学家就餐问题目 录摘要 3第一章 课程设计的目的及要求 41.1设计目的 41.2设计要求 41.3设计环境 4第二章 需求分析 52.1问题描述： 52.2问题分析： 5第三章 详细分析 63.1 问题定义 63.2算法分析： 63.3 界面设计 7第四章 程序部分代码分析 9第五章 新得体会 11第六章 参考文献 12附录 12摘要在多道程序环境下,进程同步问题十分重要,也是相当有趣的问题,因而吸引了不少学者对它进行研究,由此而产生一系列经典的进程同步问题.其中较有代表性的是哲学家进餐问题等等,通过这些问题的研究和学习,可以帮助我们列好地理解进程同步概念及实现方法.由Di
2、jkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题,该问题是描述有五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和五只筷子,他们的生活方式是交替地进行思考和进餐,平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐,进餐毕,放下筷子继续思考.由于筷子数目有限，不能让五个哲学家同时进餐，而且甚至只能让其中的少数哲学家进餐，其他的哲学家只能轮流享用，这非常类似多线程之间的同步互斥问题，所以采用windows的多线程及一些API函数实现了对这个经典算法的模拟.第一章
3、课程设计的目的及要求1.1设计目的通过本次课设，对本学期的操作系统课程的学习理论知识的一次应用。是理论结合实际的一次应用。让我们学会对竞争资源的操作，控制，同时锻炼我们的编程水平。 使我们掌握多线程编程的方法； 掌握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.2算法分析： 第一种算法:：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子， 等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在
8、 无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。 第二种算法：规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。 分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子如此，这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。 第三种算法：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以
9、下将room 作为信号量，只允 许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入 餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。 第四种算法： 仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。 利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。 第五种算法： 规定奇数号的哲学家先拿
10、起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭。3.3 界面设计 下图（图3.1.1）为程序的启动界面，图中五个卡通人物代表五位吃饭的哲学家，其身边分别搁置了一支白色的筷子。界面底端搁置了四个Button分别是开始、停止、关闭、说明，还有一个用来控制哲学家用餐的速度的滚动条。 上图（3.3.2）是哲学家正在就餐的截图，从图中我们
11、可以看出有两位哲学家正就餐而其他的哲学家正处于等待中，正在就餐的哲学家分别从他身旁两边拿取筷子从而就餐。下图（3.3.3）是哲学家在就餐的时候所处的不同的状态的截图，从图中我们可以看到有的哲学家正处于就餐状态，有的出于等待别人释放资源（筷子），有的还处于申请资源（筷子）的状态。第四章 程序部分代码分析显示控制模块函数：函数在GradientStatic.cpp文件void CGradientStatic:OnPaint() CPaintDC dc(this); / device context for painting dc.SetBkMode(TRANSPARENT); CBrush BkB
12、rush; BkBrush.CreateSolidBrush(m_colorBK); CPen BkLinePen; BkLinePen.CreatePen(PS_SOLID, 1, m_colorBKLine); dc.SelectObject(&BkBrush); dc.SelectObject(&BkLinePen); CRect rcClient; GetClientRect(rcClient); rcClient.InflateRect(-1,-1,1,1); CPoint point(m_iRadius,m_iRadius); dc.RoundRect(rcClient,point
13、); CBrush brush; brush.CreateSolidBrush(RGB(169,196,255);/picture box控件背景色 dc.SelectObject(brush); ScreenToClient(rcClient); rcClient.top = rcClient.top + 25; rcClient.bottom = rcClient.top + 150; dc.RoundRect(rcClient,point); CDC pMemDc; pMemDc.CreateCompatibleDC(&dc); pMemDc.SetBkMode(dc.GetMapMod
14、e(); BITMAP bt;/位图图片文件变量 for(int i = 0;ithinkerStatusi = THINKING_STATUS)/思考状态 m_pBmpThink.GetBitmap(&bt); pMemDc.SelectObject(m_pBmpThink); else if(m_pthinker-thinkerStatusi = EATING_STATUS)/吃饭状态 m_pBmpEat.GetBitmap(&bt); pMemDc.SelectObject(m_pBmpEat); else if(m_pthinker-thinkerStatusi = HUNGRY_ST
15、ATUS)/饥饿状态 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,SRCCOPY);/显示出图片 开始演示按钮对应的函数：void CEatingDlg:OnBtnBegin() int i; if(!m_HasInit) InitStruct();/ 对5个哲学家结构体的初始化
16、 for(i = 0;iTHINKER_NUM;i+) m_thinker.ThinkerCnt+; AfxBeginThread(Eating,(PVOID)&m_thinker);/创建5个线程，/模拟5个哲学家 Sleep(50); m_stopBtn.EnableWindow(TRUE); m_beginBtn.EnableWindow(FALSE); m_okBtn.EnableWindow(FALSE);第五章 心得体会 通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而
17、提高自己的实际动手能力和独立思考的能力。在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻的，通过这两个多星期的课设，通过程序的编写发现有了进一步的理解，其中也明白了很多道理，哲学家进餐问题从理论上讲很容易，就5个人只有5个筷子，要实现他们吃通心面的有序性，但要用程序来模拟远非文字的叙述那么简单，但还是可以实现的，尽管不是很容易的实现了。其中蕴含哲理，只要能用想出来，就可以用程序把他编处理，这就是作为一个计算机专业的使命。多线程编程对于解决一些并发性的问题是很高效的，而且也很必要，现在学习了使用多线程编程，对于以后解决类似的并发性问题，都会很有用。虽然我们学习的操作系统理论
18、课里面说多线程间的执行顺序具有随机性和不确定性，但我们毕竟是在一个特定的操作系统平台上实验，Windows 的线程调度机制我是不得而知的，所以出现的一些奇怪的问题也很难调试，只好人为地去改变线程间的顺序以求模拟出一定的随机性。实验得以完成，需要掌握几个核心的内容，API应用程序编程接口函数是重要的，其中很多函数都很有用，用起来很方便；接着信号量以及互斥，饥饿，死锁的相关知识；其次是线程函数调用的相关知识；当然还有MFC工程方面的。另外，多线程编程对于解决一些并发性的问题是很高效的，而且也很必要，现在学会了使用多线程编程，对于以后解决类似的并发性问题（例如网络编程中经常遇到的多客户线程同时访问的
19、问题），都会很有用。虽然我们学习的操作系统理论课里面说多线程间的执行顺序具有随机性和不确定性，但我们毕竟是在一个特定的操作系统平台上实验，Windows 的线程调度机制我是不得而知的，所以出现的一些奇怪的问题也很难调试，只好人为地去改变线程间的顺序以求模拟出一定的随机性。第六章 参考文献1汤小丹 梁红兵 哲凤屏 汤子瀛 计算机操作系统（第三版） 西安电子科技大学出版社, 2007.2李勇，刘恩林.计算机体系结构.长沙：国防科技大学出版社 ,1987.3梁红兵 汤小丹 汤子瀛 计算机操作系统学习指导与题解（第二版） 西安电子科技大学出版社,2008.4黄祥喜. 计算机操作系统实验教程.广州：中山
20、大学出版社,1994.5屠祁 屠立德， 等，译. 操作系统基础3版.北京：清华大学出版社,2000.6张绕林 史美林.计算机才做系统教程.北京:清华大学出版社,2000.7尹德淳 C函数速查手册 人民邮电出版社 2009.附录/GradientStatic.cpp文件代码#include stdafx.h#include GradientStatic.h#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endifCPoint ta55; /定义五个变量表示哲学家所在位置CPoint
21、 tropic55; /筷子闲置时的位置CPoint usetropic5;/筷子使用时的位置,每个哲学家用两个筷子int radius;CPoint CenterPoint;CGradientStatic:CGradientStatic() m_iLeftSpacing = 10; clLeft = GetSysColor(COLOR_ACTIVECAPTION); clRight = GetSysColor(COLOR_BTNFACE); clText = GetSysColor(COLOR_CAPTIONTEXT); m_bCenter = FALSE; hinst_msimg32 =
22、LoadLibrary( msimg32.dll ); m_bCanDoGradientFill = FALSE; pFont = NULL; if(hinst_msimg32) m_bCanDoGradientFill = TRUE; dllfunc_GradientFill = (LPFNDLLFUNC1) GetProcAddress( hinst_msimg32, GradientFill ); m_RunBrush.CreateSolidBrush(RGB(255,0,0); m_IdleBrush.CreateSolidBrush(RGB(255,255,255); bmp1.Lo
23、adBitmap(IDB_BITMAP31); bmp2.LoadBitmap(IDB_BITMAP21); bmp3.LoadBitmap(IDB_BITMAP11); maskbmp1.LoadBitmap(IDB_BITMAPm31); maskbmp2.LoadBitmap(IDB_BITMAPm21); maskbmp3.LoadBitmap(IDB_BITMAPm11); zuomianbmp.LoadBitmap(IDB_BITMAPZM); m_back.CreatePatternBrush(&zuomianbmp); m_pen.CreatePen(PS_SOLID,4,RG
24、B(255,255,255);CGradientStatic:CGradientStatic() FreeLibrary( hinst_msimg32 ); bmp1.DeleteObject(); bmp2.DeleteObject(); bmp3.DeleteObject(); maskbmp1.DeleteObject(); maskbmp2.DeleteObject(); maskbmp3.DeleteObject(); m_back.DeleteObject(); m_pen.DeleteObject()BEGIN_MESSAGE_MAP(CGradientStatic, CStat
25、ic)void CGradientStatic:OnPaint() CPaintDC dc(this); / device context for painting CRect rect; GetClientRect(&rect); static BOOL IsRgn = FALSE; if(m_bCanDoGradientFill) TRIVERTEX rcVertex2; rect.right-; / exclude this point, like FillRect does rect.bottom-; rcVertex0.x=rect.left; rcVertex0.y=rect.to
26、p; rcVertex0.Red=GetRValue(clLeft)8; / color values from 0x0000 to 0xff00 ! rcVertex0.Green=GetGValue(clLeft)8; rcVertex0.Blue=GetBValue(clLeft)8; rcVertex0.Alpha=0x0000; rcVertex1.x=rect.right; rcVertex1.y=rect.bottom; rcVertex1.Red=GetRValue(clRight)8; rcVertex1.Green=GetGValue(clRight)8; rcVertex
27、1.Blue=GetBValue(clRight)8; rcVertex1.Alpha=0; GRADIENT_RECT rect; rect.UpperLeft=0; rect.LowerRight=1; dllfunc_GradientFill( dc,rcVertex,2,&rect,1,GRADIENT_FILL_RECT_H); :SetTextColor(dc,clText); else :SetTextColor(dc,GetSysColor(COLOR_BTNTEXT); int i; CPen *oldpen; int x1,y1,x2,y2; int top,left,ri
28、ght,bottom; if(!IsRgn) for(i = 0;iIdlerecti.SetRect(left,top,right,bottom); m_pthinker-Idlerecti.InflateRect(5,5); for(i = 0;iuserecti.SetRect(left,top,right,bottom); m_pthinker-userecti.InflateRect(5,5); IsRgn = TRUE; CDC memDC; memDC.CreateCompatibleDC(&dc); CBitmap *oldbitmap; BITMAP bmpInfo; oldbitmap = memDC.SelectObject(&maskbmp1); maskbmp1.GetBitmap(&bmpInfo); dc.BitBlt(ta50.x-bmpInfo.bmWidth/2,30,bmpInfo.bmWidth,bmpInfo.bmHei
