62操作系统课程设计

银行家算法课程设计班级：110613学号：110613120姓名：袁超课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等）技术参数：WindowsXP系统，VC++6.0开发工具。设计要求：1．设计银行家算法的核心数据结构、安全性检查算法；2．画出银行家算法流程图；3．编程实现算法功能；4．编写课程设计说明书。工作量要求：完成以上设计要求中的所有算1功能介绍我设计的银行家算法实现系统是一个进程动态请求资源的模拟系统，实现系统为进城随机产生请求资源的数量，系统通过资源安全性检查，检查是否满足安全要求。若安全，则才分配资源；不安全时，系统恢复申请前的状态；只有当进程满足全部的资源需求时，该进程执行结束，释放所占的资源。内容介绍我设计的银行家算法系统主要实验对进程资源的动态分配，对进程尚需的资源再分配，直到进程已获得全部的所需资源时，系统收回对该进程的分配的所有资源。在系统每次分配时，都要通过安全性的检查，只有在安全的状态下，系统才会给进程分配资源，否则，恢复到原来的进程状态。设计目的通过银行家算法设计与实现，可以加深学生对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法—银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。设计要求系统在进行资源分配的过程中，允许进程动态的申请资源，为了避免发生死锁，在分配资源前要进行安全性检查，若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则，进程等待。设计一个进程动态请求资源的模拟系统，实现随机产生进程请求资源的数量；资源安全性检查算法；资源的分配算法；以及输出显示每次请求的结果和系统资源的状态2设计思想开始时，输入当前进程资源的状态以及整个系统的资源使用情况，即进行初始化安全性检查；如果是不安全状态，重新初始化系统；否则，给进程分配资源，并使用银行家算法进行检测，输出当前系统的状态和安全序列；如果是安全状态，系统继续从等待队列中提取等待进程进行检查，并且再分配所需的资源，当所需的资源已经满足进程所需资源时，便释放所占的资源；如果是不安全状态，进程恢复到原先的状态。程序流程图程序流程图包括：主程序流程图和各功能模块的流程图。主程序流程图如下图：开始结束输入进程数和资源输入系统资源调用动态分配资源函数安全性判断可在申请资源申请是否满足条件执行分配函数重新请求分配执行恢复函数不安全安全否是是否结束是3图2主程序模块图各功能模块的流程图：简略的展示部分函数模块的流程图，我采用简洁的叙述算法的流程过程，实际的应用参照程序清单，以下为：银行家算法的流程图，安全性检查算法流程图，释放资源算法流程图等。银行家算法的流程图：图3银行家算法安全性检查算法流程图开始结束ERRORERRORRequest[i]=Need?Request[i]=Available?Available[i]-=Request[i];Allocation[i]+=Request[i];Need[i]-=Request[i];SafetyCheck()是否安全分配资源Request[i]=Available?是是是否否否开始结束Work=Available;Finish[i]=pid;Finish[i]!=-1&&Need[i]=WorkWork+=AllocationFinish[i]=-1系统状态安全所有进程的Finish[i]=-1系统状态不安全是否是否4图4安全检查算法释放资源算法流程图图5释放资源算法开始结束Need[i]==NULL&&mark[i]==NULLAvailable[i]+=p-Allocation[i]p-mark[i]=1是否5实验运行结果实验结果达到了实验要求和预期的结果，实验运行结果截图如下：图7初始化资源信息图7为刚开始执行程序时进程数和资源种类确定，以及系统可利用资源的初始化。图8系统给进程随机分配资源图8系统给进程0、1随机分配资源，显示所需的资源数。6图9随机分配资源后进程信息图9为进程随机分配资源后信息的显示包括：进程状态，还需资源，已分配资源，最大资源，可利用资源。图10安全检查图10为安全信息检查，输出安全序列号。图11进程再申请资源图11为给进程0再次分配资源，当满足所需资源时，进程执行完，释放系统所占的资源。7图12分配资源超过可利用资源图12分配资源超过可利用资源，系统处于不安全状态，本次申请作废，恢复原来的资源分配状态。总结遇到的问题由于使用进程编程较少，所以也遇到了一些问题，无论是哪种算法或问题首先要有自己的思路，接下来就是通过语言的实现。遇到的最大的问题就是不了解银行家算法和安全性算法，所以刚开始无从下手，还有问题就是编译调试中的问题。解决方法我通过网上和图书馆查阅相关的资料，对这两种算法有了初步的了解，然后提出自己的设计思路，确定采用单链表的数据结构实现，对于一些自己模糊和不清楚自己又解决不了的问题那就问老师和同学。收获体会通过这次实验，让我更加全面的复习C语言，也让我加深了操作系统的知识，知道了系统给进程分配资源时解决死锁的方法，对安全算法和银行家算法有了一定的了解。以前的自己C语言的编程还是有些基础，也做了大量的编程题，所以，编程不是主要的问题。主要的问题就是对于操作系统系统分配资源的不熟8悉，以及试验中所遇到的算法的了解不够，致使在编程中出现了一些错误，之后，通过借阅图书馆的书籍，查阅相关的资料，弄懂了算法的含义，解决了相关的问题，让我收获不少。程序清单#includestdio.h#includestdlib.h#includestring.h#defineMaxResource10//最大系统资源类#defineNULL0structpcb//定义进程控制块PCB{intpid;//进程标号intMax[MaxResource];//表示某个进程对某类资源的最大需求intAllocation[MaxResource];//表示某个进程已分配到某类资源的个数intNeed[MaxResource];//表示某个进程尚需要某类资源的个数intmark[MaxResource];//在使用FreeRecourse是以确定是否释放资源pcb*next;};voidInitialize(pcb*&head,intm,intn,intAvailable[MaxResource])//初始化进程资源值{inti,j=0;voidAddPcb(pcb*&head,pcbnode);pcbnode;printf(\t**请输入%d进程的%d个最大资源数**\t\n,n,m);do{node.pid=j;printf(请输入第%d个进程最大需求资源数:\n,node.pid);for(i=0;im;i++)scanf(%d,&node.Max[i]);printf(系统给进程%d随机分配资源数为:\n,node.pid);for(i=0;im;i++){node.Allocation[i]=rand()%node.Max[i];printf(%10d,node.Allocation[i]);Available[i]=Available[i]-node.Allocation[i];}9printf(\n);printf(进程%d还所需的资源数为:\n,node.pid);for(i=0;im;i++){node.Need[i]=node.Max[i]-node.Allocation[i];printf(%10d,node.Need[i]);}for(i=0;im;i++)node.mark[i]=0;printf(\n);AddPcb(head,node);j++;}while(jn);//+-`-+-}voidAddPcb(pcb*&head,pcbnode)//增加进程链表块{pcb*p=(pcb*)malloc(sizeof(pcb));pcb*last=NULL;memcpy(p,&node,sizeof(pcb));p-next=NULL;if(head==NULL)head=p;else{last=head;while(last-next!=NULL)last=last-next;last-next=p;}}voidShowPcb(pcb*head,int*avail,intm)//显示进程初始化的资源值{pcb*p=NULL;intj;p=head;if(p==NULL){printf(当前没有进程，请重新输入进程!\n);exit(0);}else{printf(进程号最大资源值已分配资源还需资源可利用的资源10状态\n\n);while(p!=NULL){printf(p[%d],p-pid);for(j=0;jm;j++){printf(\t%4d%4d%4d%4d,p-Max[j],p-Allocation[j],p-Need[j],avail[j]);if(p-mark[j])printf(已执行\n);elseprintf(等待\n);}p=p-next;}}}pcb*Seek(pcb*head,intpid)//查找进程在链表中的位置{pcb*p=NULL;p=head;if(p==NULL){printf(没有进程，进程链表空！\n);returnp;}else{while(p!=NULL){if(p-pid==pid)break;elsep=p-next;}if(NULL==p){printf(没有这个进程！\n);returnp;}elsereturnp;}}11voidFreeResource(pcb*&head,intAvailable[MaxResource],intm)//若进程所需资源已全部分配，则释放该进程占据的全部系统资源{pcb*p=NULL;inti;p=head;if(!p)printf(没有进程，请先初始化进程！);else{for(i=0;im;i++){if((p-Need[i]==NULL)&&(p-mark[i]==NULL)){printf(进程%d的第%d个已经执行完，释放所占系统资源！\n,p-pid,i);Available[i]+=p-Allocation[i];p-mark[i]=1;}}}}pcb*Application(pcb*head,int*request,int*avail,intm)//再次给进程分配资源{intpid,i;pcb*p=NULL;printf(请输入进程pid号:\n);printf(p);scanf(%d,&pid);p=Seek(head,pid);if(p==NULL){printf(没有这个进程！\n);returnp;}printf(请输入给该进程再次分配的资源数:\n);for(i=0;im;i++)scanf(%d,&request[i]);for(i=0;im;i++)if(request[i]p-Need[i]){printf(分配进程的资源数超过最大资源数！\n);returnNULL;}12for(i=0;im;i++)if(request[i]avail[i]){printf(分配进程的资源数超过可利用的资源数！\n);returnNULL;}for(i=0;im;i++){avail[i]=avail[i]-request[i];p-Allocation[i]=p-Allocation[i]+request[i];p-Need[i]=p-Need[i]-request[i];}FreeResource(p,avail,m);returnp;}pcb*Reasonable(pcb*head,int*finish,int*work,intm,intn)//找到当前安全可执行的进程返回{inti=0,j=0,count=0;pcb*p=NULL;while(1){if(finis