操作系统第二次银行家算法

1、软 件 学 院上 机 实 验 报 告课程名称： 操作系统原理 实验项目： 实验二银行家算法 实 验 室： 耘慧402 姓 名： 王欣鸿 学 号： 1320010724 专业班级： 软件13-7班 实验时间： 2015-12-12 实验成绩评阅教师一、 实验目的及要求1.进一步理解利用银行家算法避免死锁的问题；2.在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性；3.理解和掌握安全序列、安全性算法。二、 实验性质验证性三、 实验学时4学时四、 实验环境Linux系统开发环境五、实验内容及步骤内容：1. 了解和理解死锁；2. 理解利用银行家

2、算法避免死锁的原理；3. 会使用某种编程语言。步骤：1.安全状态指系统能按照某种顺序如(称为序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。2. 银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：（1）如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-R

3、equestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.安全性算法（1）设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finis

4、hi=false; 当有足够资源分配给进程时， 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2; （4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态4. 实验步骤（1）参考图2-1所示流程图编写安全性算法。（2）编写统一

5、的输出格式。每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。（3）编写主函数来循环调用银行家算法。六、实验数据及结果分析1详细记录在调试过程中出现的问题及解决方法；在调试过程中发现进程数少输一个但仍然能运行，经过一番研究后发现其默认为0，解决了这个bug；最后按照书上的进程数输入，结果显示能够安全运行。2记录实验执行的结果（运行结果截图）。七、实验总结包含以下内容: 这次的银行家算法相比于上次更加的复杂，但是通过仔细的钻研，我明白此次实验的目的是懂得银行家算法避免死锁的思路，这个算法有效的避免死锁，属于避免发生死锁。这个算法有效的避免死锁，提高了

6、系统运行的效率，得到了很多版本的os编写者的青睐，除了会运行此程序外，也应该对其思路有一定的了解，以后才能够编写更好的算法，或者能够根据此算法解决一些实际问题。附录 源程序清单sy.cinclude malloc.h #include stdio.h #include stdlib.h #define alloclen sizeof(struct allocation) #define maxlen sizeof(struct max) #define avalen sizeof(struct available) #define needlen sizeof(struct need) #de

7、fine finilen sizeof(struct finish) #define pathlen sizeof(struct path) struct allocation int value; struct allocation *next; ; struct max int value; struct max *next; ; struct available /*可用资源数*/ int value; struct available *next; ; struct need /*需求资源数*/ int value; struct need *next; ; struct path i

8、nt value; struct path *next; ; struct finish int stat; struct finish *next; ; int main() int row,colum,status=0,i,j,t,temp,processtest; struct allocation *allochead,*alloc1,*alloc2,*alloctemp; struct max *maxhead,*maxium1,*maxium2,*maxtemp; struct available *avahead,*available1,*available2,*workhead

9、,*work1,*work2,*worktemp,*worktemp1; struct need *needhead,*need1,*need2,*needtemp; struct finish *finihead,*finish1,*finish2,*finishtemp; struct path *pathhead,*path1,*path2; printf(n请输入系统资源的种类数:); scanf(%d,&colum); printf(请输入现时内存中的进程数:); scanf(%d,&row); printf(请输入已分配资源矩阵:n); for(i=0;irow;i+) for (

10、j=0;jnext=alloc2-next=NULL; scanf(%d,&allochead-value); status+; else alloc2=(struct allocation *)malloc(alloclen); scanf(%d,%d,&alloc2-value); if(status=1) allochead-next=alloc2; status+; alloc1-next=alloc2; alloc1=alloc2; alloc2-next=NULL; status=0; printf(请输入最大需求矩阵:n); for(i=0;irow;i+) for (j=0;j

11、next=maxium2-next=NULL; scanf(%d,&maxium1-value); status+; else maxium2=(struct max *)malloc(maxlen); scanf(%d,%d,&maxium2-value); if(status=1) maxhead-next=maxium2; status+; maxium1-next=maxium2; maxium1=maxium2; maxium2-next=NULL; status=0; printf(请输入现时系统剩余的资源矩阵:n); for (j=0;jnext=available2-next=

12、NULL; work1-next=work2-next=NULL; scanf(%d,&available1-value); work1-value=available1-value; status+; else available2=(struct available*)malloc(avalen); work2=(struct available*)malloc(avalen); scanf(%d,%d,&available2-value); work2-value=available2-value; if(status=1) avahead-next=available2; workhe

13、ad-next=work2; status+; available1-next=available2; available1=available2; work1-next=work2; work1=work2; available2-next=NULL; work2-next=NULL; status=0; alloctemp=allochead; maxtemp=maxhead; for(i=0;irow;i+) for (j=0;jnext=need2-next=NULL; need1-value=maxtemp-value-alloctemp-value; status+; else n

14、eed2=(struct need *)malloc(needlen); need2-value=(maxtemp-value)-(alloctemp-value); if(status=1) needhead-next=need2; status+; need1-next=need2; need1=need2; maxtemp=maxtemp-next; alloctemp=alloctemp-next; need2-next=NULL; status=0; for(i=0;inext=finish2-next=NULL; finish1-stat=0; status+; else fini

15、sh2=(struct finish*)malloc(finilen); finish2-stat=0; if(status=1) finihead-next=finish2; status+; finish1-next=finish2; finish1=finish2; finish2-next=NULL; /*Initialization compleated*/ status=0; processtest=0; for(temp=0;temprow;temp+) alloctemp=allochead; needtemp=needhead; finishtemp=finihead; wo

16、rktemp=workhead; for(i=0;istat=0) for(j=0;jnext,worktemp=worktemp-next) if(needtemp-valuevalue) processtest+; if(processtest=colum) for(j=0;jvalue+=alloctemp-value; worktemp1=worktemp1-next; alloctemp=alloctemp-next; if(status=0) pathhead=path1=path2=(struct path*)malloc(pathlen); path1-next=path2-n

17、ext=NULL; path1-value=i; status+; else path2=(struct path*)malloc(pathlen); path2-value=i; if(status=1) pathhead-next=path2; status+; path1-next=path2; path1=path2; finishtemp-stat=1; else for(t=0;tnext; finishtemp-stat=0; else for(t=0;tnext; alloctemp=alloctemp-next; processtest=0; worktemp=workhead; fini