计算机操作系统实验-银行家算法

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：操作系统课程类型：必修实验项目名称：银行家算法实验题目：采用银行家算法防止死锁班级：实验学院一班学号：6040310110姓名：张元竞设计成绩报告成绩指导老师一、实验题目设计一个n个并发进程共享m个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法防止死锁。二、实验目的死锁会引起计算机工作僵死，造成整个系统瘫痪。因此，死锁现象是操作系统特别是大型系统中必须设法防止的。通过本次实验，使学生掌握死锁的概念和产生死锁的原因和必要条件，预防和避免死锁的方法，死锁的检测与解除。通过本次实验，使学生加深了对死锁概念的理解和掌握，深刻领会银行家算法的实质及实现过程。三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1．程序流程图安全（safe）函数框图如下：开始结束承认已假定分配给现行进程的资源，输出完成信息，置ADVANCE=true收回假定分配给现行进程的资源，输出失败信息，置ADVANCE=true收回假定分配给现行进程的资源输出信息资源不足采用死锁预防算法如已有进程死锁置ADVANCE=false如不采用死锁预防算法，将现行进程死锁位置1否否否是是是剩余资源能否满足现行进程？当前分配状态安全吗？（safe）采用死锁预防算法？承认已假定分配给现行进程的资源，输出完成信息，置ADVANCE=true2．逻辑设计用结构体数组表示3个进程，其中包括使用数组形式的线性表表示某个进程申请资源的列表（队列），以及进程需要的总资源数、开始结束未完成进程的T标志为1置已完成进程的T标志为0Change是否为‘true’置局部变量Change为‘true’（即是否有进程标志位T从1变0）置change为‘false’全部进程已经完成？即各进程T标志都为0剩余资源与新完成资源之和是否超过某进程还需要的资源？置局部变量PROGRESS为true改变对应的T值判定是否还存在不能完成的进程，若不存在，置SAFE为‘true’，否则为‘false’是是是否否否前i个申请共计占用的资源，进程当前已经运行到的位置等信息。模拟分配的程序部分，采用循环队列对各进程进行调度。3、物理设计全局变量的结构定义如下：boolavoid;structinfo//进程信息{longtot,n;//最大占用资源,申请次数longlist[16];//申请资源列表longpre[16];//已占用资源数longp;//已分配状况的指针}pro[4];longLeftRes;程序的结构定义如下：intmain()//主函数{init();allot();}voidinit()//函数功能:输入和初始化voidallot()//函数功能:模拟资源分配过程allot()使用以下函数模拟分配过程：boolrequire(longx)//函数功能:尝试分配资源给进程xboolsafe(longx)//函数功能:检查分配是否安全可以处理3种资源的程序全局变量结构如下：//共有3种资源，3个进程boolavoid;structinfo//进程信息{longtot[4];//最大占用资源数longp[4];//已经占有的资源数}pro[5];longLeftRes[4];//剩余资源数longqu[4];四、测试结果对于一组会导致死锁的数据，分别选择采用和不采用避免算法，结果如下：Avoiddeadlock?(Y/N)YPleaseinputtheresourse-requirelistsofthese3processes,onelistsinaline:23423331=================================================================Process1:234(Sum=9)Process2:233(Sum=8)Process3:31(Sum=4)=================================================================Process1require2unit(s)resourse......Success!LeftResourse=8Process2require2unit(s)resourse......Success!LeftResourse=6Process3require3unit(s)resourse......Success!LeftResourse=3Process1require3unit(s)resourse......Denied!NotsafeProcess2require3unit(s)resourse......Denied!NotsafeProcess3require1unit(s)resourse......Success!LeftResourse=2Process3finish.LeftResourse=6Process1require3unit(s)resourse......Denied!NotsafeProcess2require3unit(s)resourse......Success!LeftResourse=3Process1require3unit(s)resourse......Denied!NotsafeProcess2require3unit(s)resourse......Success!LeftResourse=0Process2finish.LeftResourse=8Process1require3unit(s)resourse......Success!LeftResourse=5Process1require4unit(s)resourse......Success!LeftResourse=1Process1finish.LeftResourse=10Finish如果不避免死锁：Avoiddeadlock?(Y/N)NPleaseinputtheresourse-requirelistsofthese3processes,onelistsinaline:23423331=================================================================Process1:234(Sum=9)Process2:233(Sum=8)Process3:31(Sum=4)=================================================================Process1require2unit(s)resourse......Success!LeftResourse=8Process2require2unit(s)resourse......Success!LeftResourse=6Process3require3unit(s)resourse......Success!LeftResourse=3Process1require3unit(s)resourse......Success!LeftResourse=0Process2require3unit(s)resourse......Denied!NoenoughresourseProcess3require1unit(s)resourse......Denied!NoenoughresourseProcess1require4unit(s)resourse......Denied!NoenoughresourseAlreadyDeadlockFinish改进版本（可以使用3种资源的程序）测试结果如下：五、系统不足与经验体会系统不能处理多种不同资源的情况，也缺乏处理大规模数据的能力。safe函数的编写是程序成功的关键，其中利用Change标记的思乡值得仔细体会。六、附录：源代码（带注释）//*******************************************************//*操作系统实验三死锁*//*实验学院一班（0436101）张元竞(6040310110)*//*2006-10-15*//******************************************************/#includecstdio#includecstring#includecstdlib#includectime//共有3种资源，3个进程boolavoid;structinfo//进程信息{longtot[4];//最大占用资源数longp[4];//已经占有的资源数}pro[5];longLeftRes[4];//剩余资源数longqu[4];voidinit()//函数功能:输入和初始化{chartmp[128];longi,j;//以下由用户选择是否采用避免死锁算法printf(是否采用避免死锁算法?(Y/N));gets(tmp);avoid=(tmp[0]=='Y'||tmp[0]=='y');//输入各进程的资源信息printf(请输入各进程的资源信息:\n);printf(依次输入各进程所需要的最大资源数量:\n);for(i=1;i=3;i++){for(j=1;j=3;j++){scanf(%ld,&pro[i].tot[j]);}}printf(依次输入各进程已经占据的资源数量:\n);for(i=1;i=3;i++){for(j=1;j=3;j++){do{scanf(%ld,&pro[i].p[j]);if(pro[i].p[j]pro[i].tot[j])printf(\n占有资源超过了声明的最大资源,请重新输入\n);}while(pro[i].p[j]pro[i].tot[j]);}}//初始化资源数量for(i=1;i=3;i++){LeftRes[i]=10;//初始化总资源数为10for(j=1;j=3;j++){LeftRes[i]-=pro[j].p[i];//减去已经被占据的资源}}//以下输出资源状况表printf(\n===============================================================\n);printf(%-20s,当前剩余资源);for(i=1;i=3;i++){printf(%8ld,LeftRes[i]);}for(i=1;i=3;i++){printf(\n%s%ld%-15s,进程,i,(占用/最大));for(j=1;j=3;j++){printf(%4ld/%3ld,pro[i].p[j],pro[i].tot[j]);}}printf(\n===============================================================\n\n);}boolsafe(longx)//函数功能:检查分配是否安全{longi,j,y[4];boolchange=1;boolT[4];longstack[4],top=0;memset(T,0,sizeof(T));for(i=1;i=3;i++){y[i]=LeftRes[i]-qu[i];pro[x].p[i]+=qu[i];}while(change){change=0;for(i=1;i=3;i++){if(T[i])continue;if(y[1]=pro[i].tot[1]-pro[i].p[1]&&y[2]=pro[i].tot[2]-pro[i].p[2]&&y[3]=pro[i].tot[3]-pro[i].p[3]){for(j=1;j=3;j++){y[j]+=pro[i].p[j];}T[i]=1;change=1;stack[++t