操作系统课程设计哲学家就餐问题Word下载.docx
《操作系统课程设计哲学家就餐问题Word下载.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计哲学家就餐问题Word下载.docx（24页珍藏版）》请在冰点文库上搜索。
锻炼我们的自学能力；
培养我们的组队合作能力；
提高学生的科技论文写作能力。
1.2设计要求
✧利用多线程编程模拟5个线程，竞争五个筷子去吃通心面；
✧对临界资源的操作算法要简单易行；
✧程序运行时不会产生死锁；
✧对所设计的各模块系统进行调试；
✧独立完成程序的设计与调试；
✧设计好各个功能模块，合理安排他们的位置；
✧程序结构清晰；
✧程序界面友好直观。
1.3设计环境
Ä
开发程序的操作系统：
WindowsXP（在Windows7/Windows2000里也适用）
编译工具：
visualC++6.0
程序工程：
MFCAppWizard（exe）的对话框工程
第二章需求分析
由Dijkstra提出并解决的哲学家进餐问题（TheDinningPhilosophersProblem）有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。
平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有他拿到两只筷子时才能进餐。
进餐毕，放下筷子继续思考。
经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。
在设计实现与演示该问题时，为了实现对筷子的互斥使用，程序中使用互斥量表示一只筷子，每一支筷子使用一个互斥量，五个筷子总共需要五个互斥量所有信号量。
当哲学家饥饿时，总是先去拿他左边的筷子，成功后再去拿他右边的筷子，如果两次操作都成功便可进餐。
进餐毕，先放下他左边的筷子，然后再放下他右边的筷子。
为了模拟实现五个哲学家的进餐情况，利用操作系统提供的多线程来模拟进程实现哲学家进餐的过程功能，其中一个为主线程，用于为要进餐的哲学家提供场所。
子线程与主线程并行执行，主线程控制着它们的生成。
子线程用于处理要进餐的哲学家，其功能有申请筷子、把申请到筷子的哲学家置为进餐状态、释放筷子。
第三章详细分析
3.1问题定义
在哲学家问题中，我们首先要对哲学家们进餐问题做一些规则，规则如下：
1.互斥解决。
每一把叉子使用一个2元信号量，只有获得信号量的哲学家才能使用叉子，从而避免对叉子的“抢夺”。
2.死琐和饥饿解决。
餐厅只允许最多4名哲学家进入，因为总有一个哲学家可以得到两把叉子，从而可以正常就餐，因此不会有死琐出现。
每为哲学家就餐完毕后，立即离开，放下叉子，以便没有用餐的哲学家可以使用，这也能保证不会有饥饿的存在了。
3.就餐顺序随机。
为了较真实地模拟现实就餐问题，哲学家每次进入餐厅的顺序总是随机的，这个随机顺序在哲学家开始进入之间通过一个函数产生
4.哲学家的各种状态。
思考：
当哲学家没有就座的时候，该位置显示空闲状态。
等待：
当一个哲学家进入餐厅但是没有获得餐具就餐的时候，进入思考等待状态。
吃饭中：
哲学家获得餐具后开始就餐进入就餐状态。
离开：
哲学家就餐完毕就到了离开状态。
每个哲学家的就餐过程通过一个线程函数的调用来实现。
主线程与子线程的通信：
第一种算法:
：
假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。
对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，
即出现饥饿，所有哲学家都吃不上饭。
第二种算法：
规定在拿到左侧的筷子后，先检查右面的筷子是否可用。
如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。
分析：
当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此，这样永远重复下去。
对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。
第三种算法：
至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。
以下将room作为信号量，只允许4个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room的等待队列，根据FIFO的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。
第四种算法：
仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
利用AND型信号量机制实现：
根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。
当某些资源不够时阻塞调用进程;
由于等待队列的存在，使得对资源的请求满足FIFO的要求，因此不会出现饥饿的情形。
第五种算法：
规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;
而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。
而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭。
3.3界面设计
下图（图3.1.1）为程序的启动界面，图中五个卡通人物代表五位吃饭的哲学家，其身边分别搁置了一支白色的筷子。
界面底端搁置了四个Button分别是开始、停止、关闭、说明，还有一个用来控制哲学家用餐的速度的滚动条。
上图（3.3.2）是哲学家正在就餐的截图，从图中我们可以看出有两位哲学家正就餐而其他的哲学家正处于等待中，正在就餐的哲学家分别从他身旁两边拿取筷子从而就餐。
下图（3.3.3）是哲学家在就餐的时候所处的不同的状态的截图，从图中我们可以看到有的哲学家正处于就餐状态，有的出于等待别人释放资源（筷子），有的还处于申请资源（筷子）的状态。
第四章程序部分代码分析
显示控制模块函数：
函数在GradientStatic.cpp文件
voidCGradientStatic:
:
OnPaint（）
{
CPaintDCdc（this）;
//devicecontextforpainting
dc.SetBkMode（TRANSPARENT）;
CBrushBkBrush;
BkBrush.CreateSolidBrush（m_colorBK）;
CPenBkLinePen;
BkLinePen.CreatePen（PS_SOLID,1,m_colorBKLine）;
dc.SelectObject（&
BkBrush）;
BkLinePen）;
CRectrcClient;
GetClientRect（rcClient）;
rcClient.InflateRect（-1,-1,1,1）;
CPointpoint（m_iRadius,m_iRadius）;
dc.RoundRect（rcClient,point）;
CBrushbrush;
brush.CreateSolidBrush（RGB（169,196,255））;
//picturebox控件背景色
dc.SelectObject（brush）;
ScreenToClient（rcClient）;
rcClient.top=rcClient.top+25;
rcClient.bottom=rcClient.top+150;
CDCpMemDc;
pMemDc.CreateCompatibleDC（&
dc）;
pMemDc.SetBkMode（dc.GetMapMode（））;
BITMAPbt;
//位图图片文件变量
for（inti=0;
i<
THINKER_NUM;
i++）
{
if（m_pthinker->
thinkerStatus[i]==THINKING_STATUS）{//思考状态
m_pBmpThink.GetBitmap（&
bt）;
pMemDc.SelectObject（m_pBmpThink）;
}elseif（m_pthinker->
thinkerStatus[i]==EATING_STATUS）{//吃饭状态
m_pBmpEat.GetBitmap（&
pMemDc.SelectObject（m_pBmpEat）;
thinkerStatus[i]==HUNGRY_STATUS）{//饥饿状态
m_pBmpWait.GetBitmap（&
pMemDc.SelectObject（m_pBmpWait）;
}elsem_sTEXT="
"
;
dc.StretchBlt（20+（25+bt.bmWidth）*i,60,bt.bmWidth,bt.bmHeight,&
pMemDc,0,0,bt.bmWidth,bt.bmHeight,SRCCOPY）;
//显示出图片
}
}
开始演示按钮对应的函数：
voidCEatingDlg:
OnBtnBegin（）
inti;
if（!
m_HasInit）
InitStruct（）;
//对5个哲学家结构体的初始化
for（i=0;
{
m_thinker.ThinkerCnt++;
AfxBeginThread（Eating,（PVOID）&
m_thinker）;
//创建5个线程，
//模拟5个哲学家
Sleep（50）;
m_stopBtn.EnableWindow（TRUE）;
m_beginBtn.EnableWindow（FALSE）;
m_okBtn.EnableWindow（FALSE）;
第五章心得体会
通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻的，通过这两个多星期的课设，通过程序的编写发现有了进一步的理解，其中也明白了很多道理，哲学家进餐问题从理论上讲很容易，就5个人只有5个筷子，要实现他们吃通心面的有序性，但要用程序来模拟远非文字的叙述那么简单，但还是可以实现的，尽管不是很容易的实现了。
其中蕴含哲理，只要能用想出来，就可以用程序把他编处理，这就是作为一个计算机专业的使命。
多线程编程对于解决一些并发性的问题是很高效的，而且也很必要，现在学习了使用多线程编程，对于以后解决类似的并发性问题，都会很有用。
虽然我们学习的操作系统理论课里面说多线程间的执行顺序具有随机性和不确定性，但我们毕竟是在一个特定的操作系统平台上实验，Windows的线程调度机制我是不得而知的，所以出现的一些奇怪的问题也很难调试，只好人为地去改变线程间的顺序以求模拟出一定的随机性。
实验得以完成，需要掌握几个核心的内容，API应用程序编程接口函数是重要的，其中很多函数都很有用，用起来很方便；
接着信号量以及互斥，饥饿，死锁的相关知识；
其次是线程函数调用的相关知识；
当然还有MFC工程方面的。
另外，多线程编程对于解决一些并发性的问题是很高效的，而且也很必要，现在学会了使用多线程编程，对于以后解决类似的并发性问题（例如网络编程中经常遇到的多客户线程同时访问的问题），都会很有用。
第六章参考文献
[1]汤小丹梁红兵哲凤屏汤子瀛计算机操作系统（第三版）西安电子科技大学出版社,2007.
[2]李勇，刘恩林.计算机体系结构.长沙：
国防科技大学出版社,1987.
[3]梁红兵汤小丹汤子瀛计算机操作系统学习指导与题解（第二版）西安电子科技大学出版社,2008.
[4]黄祥喜.计算机操作系统实验教程.广州：
中山大学出版社,1994.
[5]屠祁屠立德，等，译.操作系统基础3版.北京：
清华大学出版社,2000.
[6]张绕林史美林.计算机才做系统教程.北京:
[7]尹德淳C函数速查手册人民邮电出版社2009.
附录
//GradientStatic.cpp文件代码
#include"
stdafx.h"
GradientStatic.h"
#ifdef_DEBUG
#definenewDEBUG_NEW
#undefTHIS_FILE
staticcharTHIS_FILE[]=__FILE__;
#endif
CPointta5[5];
//定义五个变量表示哲学家所在位置
CPointtropic5[5];
//筷子闲置时的位置
CPointusetropic[5];
//筷子使用时的位置,每个哲学家用两个筷子
intradius;
CPointCenterPoint;
CGradientStatic:
CGradientStatic（）
m_iLeftSpacing=10;
clLeft=GetSysColor（COLOR_ACTIVECAPTION）;
clRight=GetSysColor（COLOR_BTNFACE）;
clText=GetSysColor（COLOR_CAPTIONTEXT）;
m_bCenter=FALSE;
hinst_msimg32=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.LoadBitmap（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,RGB（255,255,255））;
~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,CStatic）
CRectrect;
GetClientRect（&
rect）;
staticBOOLIsRgn=FALSE;
if（m_bCanDoGradientFill）
TRIVERTEXrcVertex[2];
rect.right--;
//excludethispoint,likeFillRectdoes
rect.bottom--;
rcVertex[0].x=rect.left;
rcVertex[0].y=rect.top;
rcVertex[0].Red=GetRValue（clLeft）<
<
8;
//colorvaluesfrom0x0000to0xff00!
!
rcVertex[0].Green=GetGValue（clLeft）<
rcVertex[0].Blue=GetBValue（clLeft）<
rcVertex[0].Alpha=0x0000;
rcVertex[1].x=rect.right;
rcVertex[1].y=rect.bottom;
rcVertex[1].Red=GetRValue（clRight）<
rcVertex[1].Green=GetGValue（clRight）<
rcVertex[1].Blue=GetBValue（clRight）<
rcVertex[1].Alpha=0;
GRADIENT_RECTrect;
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））;
CPen*oldpen;
intx1,y1,x2,y2;
inttop,left,right,bottom;
IsRgn）
for（i=0;
5;
{
x1=tropic5[i].x;
y1=tropic5[i].y;
x2=tropic5[i].x-（tropic5[i].x-CenterPoint.x）/4;
y2=tropic5[i].y-（tropic5[i].y-CenterPoint.y）/4;
left=min（x1,x2）;
top=min（y1,y2）;
right=max（x1,x2）;
bottom=max（y1,y2）;
m_pthinker->
Idlerect[i].SetRect（left,top,right,bottom）;
Idlerect[i].InflateRect（5,5）;
}
x1=usetropic[i].x;
y1=usetropic[i].y;
x2=usetropic[i].x-（usetropic[i].x-CenterPoint.x）/4;
y2=usetropic[i].y-（usetropic[i].y-CenterPoint.y）/4;
userect[i].SetRect（left,top,right,bottom）;
userect[i].InflateRect（5,5）;
IsRgn=TRUE;
CDCmemDC;
memDC.CreateCompatibleDC（&
CBitmap*oldbitmap;
BITMAPbmpInfo;
oldbitmap=memDC.SelectObject（&
maskbmp1）;
maskbmp1.GetBitmap（&
bmpInfo）;
dc.BitBlt（ta5[0].x-bmpInfo.bmWidth/2,30,bmpInfo.bmWidth,bmpInfo.bmHei
升级会员 