银行家算法实验报告.docx
- 文档编号:10785701
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:14
- 大小:73.96KB
银行家算法实验报告.docx
《银行家算法实验报告.docx》由会员分享,可在线阅读,更多相关《银行家算法实验报告.docx(14页珍藏版)》请在冰点文库上搜索。
银行家算法实验报告
成绩
评阅人
评阅日期
计算机科学与技术系
实验报告
课程名称:
Linux操作系统
实验名称:
银行家算法
2011年月日
实验三银行家算法
实验目的:
(1)进一步理解利用银行家算法避免死锁的问题;
(2)在了解和掌握银行家算法的基础上,编制银行家算法通用程序,将调试结果显示在计算机屏幕上,再检测和笔算的一致性。
(3)理解和掌握安全序列、安全性算法
实验内容:
(1)了解和理解死锁;
(2)理解利用银行家算法避免死锁的原理;
(3)会使用某种编程语言。
实验作业:
安全状态
指系统能按照某种顺序如
银行家算法
假设在进程并发执行时进程i提出请求j类资源k个后,表示为Requesti[j]=k。
系统按下述步骤进行安全检查:
(1)如果Requesti≤Needi则继续以下检查,否则显示需求申请超出最大需求值的错误。
(2)如果Requesti≤Available则继续以下检查,否则显示系统无足够资源,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等待。
安全性算法
(1)设置两个向量:
①工作向量Work:
它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available;
②Finish:
它表示系统是否有足够的资源分配给进程,使之运行完成。
开始时先做Finish[i]∶=false;当有足够资源分配给进程时,再令Finish[i]∶=true。
(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)参考图1-1所示流程图编写安全性算法。
(2)编写统一的输出格式。
每次提出申请之后输出申请成功与否的结果。
如果成功还需要输出变化前后的各种数据,并且输出安全序列。
(3)参考图1-2所示流程图编写银行家算法。
(4)编写主函数来循环调用银行家算法。
算法实现(主要代码)
1.算法涉及的一些数据结构:
#defineMAX_RSC3
#defineMAX_PRO5
#defineFALSE0
#defineTRUE1
structMPEB
{
//进程ID
intpid;
//进程最大资源需求
intMax[MAX_RSC];
//进程占用资源
intAllocation[MAX_RSC];
//进程尚需资源
intNeed[MAX_RSC];
};
classMResource
{
public:
//全局资源.可用数
intAvailable[MAX_RSC];
};
安全性算法
intGetSafeSequence(int*buffer,MPEB**pro,intnPro,MResource&rsc)
{
intcount=0;//进程完成数
intfinish[MAX_PRO]={0};
intnRsc=sizeof(rsc.Available)/sizeof(int);//资源数量
intavailable[sizeof(rsc.Available)/sizeof(int)];
:
:
memcpy_s(available,sizeof(rsc.Available),rsc.Available,sizeof(rsc.Available));
intfloor=0;
inti,j,k;
for(i=0;i { floor=count; for(j=0;j { if(finish[j]==FALSE) { for(k=0;k { if((*(pro+j))->Need[k]>available[k]) { break; } } //现有资源能满足进程 if(k==nRsc) { finish[j]=TRUE; *(buffer+count)=j; count++; //回收进程所占资源 for(k=0;k { available[k]+=(*(pro+j))->Allocation[k]; } } } } //已无法再分配资源 if(floor==count) { break; } } return((count==nPro)? TRUE: FALSE); } 资源申请及主函数 intSendRequest(MPEB**pro,intiPro,intnPro,MResource&rsc,intrscID,intnRsc) { intsequence[MAX_PRO]={0}; intsafe=FALSE; if(nRsc<=(*(pro+iPro))->Need[rscID]) { if(nRsc<=rsc.Available[rscID]) { //尝试分配资源 rsc.Available[rscID]-=nRsc; (*(pro+iPro))->Allocation[rscID]+=nRsc; (*(pro+iPro))->Need[rscID]-=nRsc; if(: : GetSafeSequence(sequence,pro,nPro,rsc)) { cout< "< for(inti=0;i { cout<<">P"<<(*(pro+sequence[i]))->pid; } cout< safe=TRUE; } else { //恢复资源状态 rsc.Available[rscID]+=nRsc; (*(pro+iPro))->Allocation[rscID]-=nRsc; (*(pro+iPro))->Need[rscID]+=nRsc; cout< safe=FALSE; } } else { cout< } } else { cout< } returnsafe; } int_tmain(intargc,_TCHAR*argv[]) { MResource*rsc=newMResource; MPEB*pros[MAX_PRO]; intnPro=0; inti; intselect=0; : : srand((unsigned)time(NULL)); for(i=0;i { rsc->Available[i]=rand()%20+5; } : : ResourceInfo(*rsc); for(;(select=GetSelection())! =0;) { switch(select) { case1: if(nPro>=MAX_PRO) { cout< } else { pros[nPro++]=: : MCreateProcess(); } break; case2: { inttpid=0; inttrid=0; inttnRsc=0; cout< "; for(;! (cin>>tpid);); for(i=0;i { if(pros[i]->pid==tpid) break; } if(i==nPro) { cout< } else { cout< "; for(;! (cin>>trid);); if(trid<0||trid>=MAX_RSC) trid=0; cout< "; for(;! (cin>>tnRsc);); if(tnRsc<1) { cout< } else { if(: : SendRequest(pros,i,nPro,*rsc,trid,tnRsc)) { cout< } } } } break; default: break; } cout< _getch(); cout< : : ResourceInfo(*rsc); : : ProcessInfo(pros,nPro); } return0; } 运行效果 本实验中,假设资源种类数为3,并发进程3个。 各类资源可用数随机,有如下初始运行图。 新建三个进程,并且对三类资源的最大需求分别置为 777,888,999 为进程21申请0号资源6个 依次为 进程22申请1号资源6个 进程23申请2号资源7个 进程21申请1号资源2个 进程22申请2号资源2个 此时资源情况如下 若此时尝试为进程23申请1号资源5个,将有如下结果 分析出现该结果的原因: 按安全性算法的原理,在某一时刻,系统资源至少足以满足一个进程对各类资源的尚需需求,才有可能(不是一定)产生安全序列。 上步若为进程23分配1号资源5个,则系统资源1可用数将为1,而三个进程对资源1的尚需需求分别为5、2、4,三个进程都无法取得足够的资源1以完成任务,视为不安全分配,所以申请失败。 此时为进程23分配1号资源4个,可产生另一个安全序列。 此时资源情况如下: 附完整源码(VS2010_C++): 【思考题】 2.在安全性算法中,为什么不用变量Available,而又定义一个临时变量work? 安全性算法的原理是在一个虚拟的系统空间中假设分配各类资源,期间当前系统空间的资源情况是不变的。 其中Available便代表了当前系统空间的资源情况,而work便代表了虚拟系统空间中的资源情况。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 银行家 算法 实验 报告