操作系统实验四 银行家算法.docx
- 文档编号:15324550
- 上传时间:2023-07-03
- 格式:DOCX
- 页数:15
- 大小:78.55KB
操作系统实验四 银行家算法.docx
《操作系统实验四 银行家算法.docx》由会员分享,可在线阅读,更多相关《操作系统实验四 银行家算法.docx(15页珍藏版)》请在冰点文库上搜索。
操作系统实验四银行家算法
银行家算法
xxx
711103xx
2012年5月21日
一、实验目的
通过实验,加深对多实例资源分配系统中死锁避免方法——银行家算法的理解,掌握Windows环境下银行家算法的实现方法,同时巩固利用WindowsAPI进行共享数据互斥访问和多线程编程的方法。
二、实验内容
1.在Windows操作系统上,利用Win32API编写多线程应用程序实现银行家算法。
2.创建n个线程来申请或释放资源,只有保证系统安全,才会批准资源申请。
3.通过Win32API提供的信号量机制,实现共享数据的并发访问。
三、实验步骤(设计思路和流程图)
最主要的用以实现系统功能的应该有两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。
1、银行家算法
设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。
当Pi发出资源请求后,系统按下述步骤进行检查:
(1)如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Requesti[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。
(3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j]∶=Available[j]-Requesti[j];
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];
Need[i,j]∶=Need[i,j]-Requesti[j];
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
2、安全性算法
(1)设置两个向量:
①Work∶=Available;②Finish
(2)从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false;②Need[i,j]≤Work[j];若找到,执行步骤(3),否则,执行步骤(4)。
(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]∶=Work[i]+Allocation[i,j];
Finish[i]∶=true;
gotostep2;
(4)如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
四、主要数据结构及其说明
(1)可利用资源向量Available。
如果Available[j]=K,则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max。
如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
(3)分配矩阵Allocation。
如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need。
如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
五、程序运行时的初值和运行结果
intAvailable[rCount]={10,5,7};
constintMax[pCount][rCount]={{7,5,3},
{3,2,2},
{9,0,2},
{2,2,2},
{4,3,3}};
第一次申请:
资源不够情况:
Request<=Available
出错的情况:
Requesti<=Need
六、实验体会
通过本次银行家算法实验,加深了我对银行家算法的了解,掌握了如何利用银行家算法避免死锁。
这次实践,我巩固了自己的理论知识。
银行家算法是为了使系统保持安全状态。
如果把操作系统看作是银行家,操作系统管理相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源。
操作系统的一些原理在生活中都可以找到相应的例子。
结合生活中的例子,可以化抽象为具体,我们会更加清楚地了解到其原理与操作过程。
七、源程序并附上注释
thread.cpp
#include
#include
#include
#include
#include
#include
usingnamespacestd;
externconstintrCount=3;
externconstintpCount=5;
externconstintNeed[pCount][rCount];
externconstintAllocation[pCount][rCount];
externHANDLEMutex;
externHANDLEQueue;
inthandleRequest(intRequest[],intpNum);
intrandomRequest(intr,intp){
returnrand()%(Need[p][r]+1);
}
intrandomRelease(intr,intp){
return-(rand()%(Allocation[p][r]+1));
}
intcompleteRelease(intr,intp){
return-Allocation[p][r];
}
DWORDWINAPIrunProcess(void*param){
intpNum=*(int*)param;
srand((unsigned)time(NULL));
boolRUNNING=true;
while(RUNNING){
Sleep(500);
intRequest[rCount];
int(*op)(int,int);
switch(rand()%10){
case0:
case1:
case2:
case3:
case4:
case5:
case6:
op=randomRequest;
break;
case7:
case8:
op=randomRelease;
break;
case9:
op=completeRelease;
RUNNING=false;
break;
}
for(inti=0;i Request[i]=(*op)(i,pNum); while(handleRequest(Request,pNum)){ assert(WAIT_OBJECT_0==WaitForSingleObject(Queue,INFINITE)); } } WaitForSingleObject(Mutex,INFINITE); cout<<"Process"< ReleaseMutex(Mutex); return0; } #include #include #include #include #include #include usingnamespacestd; constintrCount=3; constintpCount=5; intAvailable[rCount]={10,5,7}; constintMax[pCount][rCount]={ {7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3} }; intAllocation[pCount][rCount]; intNeed[pCount][rCount]; DWORDWINAPIrunProcess(void*param); HANDLEMutex; HANDLEQueue; voidprintState(); intmain(){ memcpy(Need,Max,sizeof(int)*pCount*rCount); memset(Allocation,0,sizeof(int)*pCount*rCount); //初始化信号量 Mutex=CreateMutex(NULL,FALSE,NULL); Queue=CreateSemaphore(NULL,0,1,NULL); HANDLEprocess[pCount]; for(inti=0;i process[i]=CreateThread(NULL,0,runProcess,newint(i),0,NULL); } WaitForMultipleObjects(pCount,process,TRUE,INFINITE); return0; } boolnoGreaterThan(constint*ary1,constint*ary2,intlength){ for(inti=0;i if(ary1[i]>ary2[i]) returnfalse; returntrue; } boolequals(constint*ary1,constint*ary2,intlength){ for(inti=0;i if(ary1[i]! =ary2[i]) returnfalse; returntrue; } boolsmallerThan(constint*ary1,constint*ary2,intlength){ if(noGreaterThan(ary1,ary2,length)&&! equals(ary1,ary2,length)) returntrue; returnfalse; } voidaddArrays(int*ary1,constint*ary2,intlength){ for(inti=0;i ary1[i]+=ary2[i]; } voidsubstractArrays(int*ary1,constint*ary2,intlength){ for(inti=0;i ary1[i]-=ary2[i]; } boolinSafeState(){ intWork[rCount]; memcpy(Work,Available,sizeof(int)*rCount); boolFinish[pCount]={false}; boolEXIST; do{ EXIST=false; for(inti=0;i if(! Finish[i]) if(noGreaterThan(Need[i],Work,rCount)){ addArrays(Work,Allocation[i],rCount); Finish[i]=true; EXIST=true; i=pCount; } }while(EXIST); for(inti=0;i if(! Finish[i]) returnfalse; returntrue; } voidprintResources(intr[]){ for(inti=0;i cout< cout< } voidprintMatrix(intm[][rCount]){ for(inti=0;i printResources(m[i]); } voidprintState(){ cout<<"SystemState: "< cout<<"Available: \n"; printResources(Available); cout<<'\n'; cout<<"Allocation: \n"; printMatrix(Allocation); cout<<'\n'; cout<<"Need: \n"; printMatrix(Need); cout< cout<<"****************************************"< } inthandle(intRequest[],intpNum); inthandleRequest(intRequest[],intpNum){ WaitForSingleObject(Mutex,INFINITE); intr=handle(Request,pNum); ReleaseMutex(Mutex); returnr; } inthandle(intRequest[],intpNum){ intzero[rCount]={0}; if(equals(Request,zero,rCount))return0; printState(); cout<<"Process"< "; printResources(Request); //system("pause"); if(! noGreaterThan(Request,Need[pNum],rCount)){ //raiseanerrorcondition(processexceededitsmaximumclaim) cout<<"Processerrorinrequestingresources.\n"; return-1; } if(! noGreaterThan(Request,Available,rCount)){ //notenoughresources,return cout<<"Notenoughresources.\n"; return1; } substractArrays(Available,Request,rCount); addArrays(Allocation[pNum],Request,rCount); substractArrays(Need[pNum],Request,rCount); if(smallerThan(Allocation[pNum],zero,rCount)){ cout<<"Processerrorinreleasingresources.\n"; return-2; } if(smallerThan(Request,zero,rCount)){ cout<<"Releasedetected.\n"; for(inti=0;i ReleaseSemaphore(Queue,1,NULL); }elseif(! inSafeState()){//否则,检查安全性 //undo addArrays(Available,Request,rCount); substractArrays(Allocation[pNum],Request,rCount); addArrays(Need[pNum],Request,rCount); //allocationnotallowed,return cout<<"Allocationdeniedduetosafetyrisk.\n"; system("pause"); return2; } cout<<"Allocationpermitted.\n"; return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统实验四 银行家算法 操作系统 实验 银行家 算法