操作系统实验报告

南通大学计算机科学与技术学院操作系统实验报告实验名称：银行家算法一、实验目的：了解死锁的产生，以及如何防止发生死锁，能够避免死锁的调度方法，称为银行家算法。

从而熟悉银行家算法，用C语言实现该算法。

二、实验内容：小城镇银行家拥有资金，数量为∑，被N个客户共享，银行家对客户提出下列约束条件：（1）每个客户必须事先说明需要的最大资金量；（2）每个客户每次提出部分资金量的申请并获得分配；（3）如果银行满足客户对资金的最大需求量，那么客户在资金运作后，应在有限的时间内全部归还。

只要客户遵守上述条件，银行家将保证做到：若一个客户所要的最大资金量不超过∑，银行一定会接纳此客户，并满足其资金需求；银行在收到一个客户的资金申请时，可能会因资金不足而让客户等待，但保证在有限的时间内让客户获得资金。

银行家算法虽然能避免死锁，但实现时受到种种限制，要求所涉及的进程不相交，即不能有同步要求，事先要知道进程的总数和每个进程请求最大资源数，这些都很难办到。

三、银行家算法数据结构：考虑到一个系统有n个进程和m种不同类型的资源，定义以下向量和矩阵数据结构。

（1）系统中每类资源总数向量Resource=（R1，R2，…，Rm）（2）系统中当前每类资源可用数向量Available=（V1，V2，…,Vm）（3）进程对各类资源的最大需求矩阵（Cij 表示进程Pi需要Rj类资源的最大数目）C 11 C12… C1mC 21 C22… C2mClaim= …C n1 Cn2… Cnm（4）系统中当前资源的已分配情况矩阵（Aij表示进程Pi 已分配到Rj类资源的数目）A 11 A12… A1mA 21 A22… A2mAllocation= …A n1 An2… Anm系统安全性定义：在时刻T0系统是安全的，仅当存在一个进程序列P1，P2，…，P n ，对进程Pk（k=1,2，… n）满足公式：{Cki-Aki<=Vi+∑Aji(j=1...<k-1>)，k=1,2，… ,n;i=1,2, … ,m}此公式为安全序列四、基本思想：系统中的所有进程放入进程集合，在安全状态下系统收到进程的资源请求后，先把资源试探性地分配给它。

现在，系统将剩下的可用资源和进程集合中其他进程还需要的资源数作比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完毕并归还全部资源。

这时，把这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多，反复执行上述步骤。

最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正实施本次分配；否则，只要进程集合非空，系统便处于不安全状态，本次资源分配暂不实施，让申请资源的进程等待。

五、主要代码：void bank(){ int i,j,y;jc x[M]; //进程int a[N];for(i=0;i<M;i++) //初始化max,allocation,need{x[i].num=i;x[i].finish=0;cout<<"分别输入第"<<i<<"个进程所需最大资源"<<endl;for(j=0;j<N;j++){cin>>x[i].max[j];}cout<<"分别输入第"<<i<<"个进程已分配资源"<<endl;for(j=0;j<N;j++){cin>>x[i].allocation[j];x[i].need[j]=x[i].max[j]-x[i].allocation[j];}}cout<<"已有进程分配情况"<<endl; //输出初始化结果cout<<"进程号最大资源已分配资源需要资源"<<endl;for(i=0;i<M;i++){cout<<i<<" ";for(j=0;j<N;j++){cout<<x[i].max[j];}cout<<" ";for(j=0;j<N;j++){cout<<x[i].allocation[j];}cout<<" ";for(j=0;j<N;j++){cout<<x[i].need[j];}cout<<endl;}cout<<"输入每种资源可用数量"<<endl; //输出资源各自数量for(i=0;i<N;i++){cin>>available[i];}cout<<"input request:进程"<<endl; //输入请求进程号cin>>y;cout<<"分别输入第"<<y<<"个进程所请求的资源"<<endl;//输入请求资源数for(i=0;i<N;i++){cin>>a[i];}j=0;for(i=0;i<N;i++) //判断是否满足初始条件request<=need request<=available{if(a[i]<=x[y].need[i] && a[i]<=available[i])continue;else{cout<<"error";j=1;}}if(j==0) // 满足调用银行家算法yhjsf(y,a,x);}六、运行结果：1）输入各个进程的最大需求量和已经分配资源量：2）得到如下情况：3）输入当前每类资源可用数量：4）输入需求进程：5）此时刻是安全状态6）若输入其他进程，不安全状态：七、实验总结：通过本次实验，我知道死锁防止和死锁避免是不同的。

各种死锁防止方法能够防止发生死锁，但必然降低系统的并发性并导致低效的资源利用率。

死锁避免却于此相反，允许系统中同时存在前3个必要条件，通过合适的资源分配算法确保不会出现进程等待链。

死锁避免方法能支持更多的进程并发执行，它不是对进程随意强加规则，而是动态的确定是否分配资源给提出请求的进程。

如果一个进程当前请求的资源会导致死锁，系统将拒绝启动此进程；如果一个资源的分配会导致下一步死锁，系统便拒绝本次分配。

熟练掌握银行家算法的思想和基本步骤，多次练习程序编写，我受益匪浅。

实验名称：页面调度一、实验目的：在多道程序的正常运行过程中，属于不同进程的页面被分散存放在主存页框中，当发生缺页中断时如果已无空闲页框，系统要选择一个驻留页面进行淘汰。

就此运用C++语言编写全局页面替换策略算法，了解如何完成页面替换。

二、实验内容：FIFO先进先出页面替换算法，基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性最大。

LRU最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。

OPT最佳页面替换算法，当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页面。

它所产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用做衡量各种具体算法的标准。

三、主要代码：//最佳页面调度void opt(){int length;int opt[100]={0};int pageLength;int optPage[100]={0};int compare[100]={0};int compares=1;cout<<"*************************欢迎页面最佳调度算法opt***********************"<<endl;cout<<"*********************************0代表空*******************************"<<endl;cout<<"请输入页框数："<<endl;cin>>pageLength;cout<<"请输入页面序列的长度："<<endl;cin>>length;cout<<"请输入页面序列："<<endl;for(int i=1;i<=length;i++){cout<<"请输入第"<<i<<"个的页面号："<<endl;cin>>opt[i];}for(i=1;i<=length;i++){compares=1;for(int ll=1;ll<=100;ll++){compare[ll]=0;}int flag=0;for(int j=1;j<=pageLength;j++){if(opt[i]==optPage[j]){flag=1;j=pageLength+1;}else if(optPage[j]==0){optPage[j]=opt[i];j=pageLength+1;flag=1;}}if(flag==1){}else{for(j=1;j<=pageLength;j++){for(int k=i;k<=length;k++){if(optPage[j]==opt[k]){k=length+1;}else{compare[compares]++;}}compares++;}for(int k=1;k<pageLength;k++){if(compare[k]>=compare[k+1]){compare[k+1]=compare[k];}else{}}flag=compare[pageLength];for(k=1;k<=pageLength;k++){if(flag==compare[k]){flag=k;k=pageLength+1;}}cout<<"淘汰"<<optPage[flag]<<endl;optPage[flag]=opt[i];}cout<<"页框内容为：";for(int s=1;s<=pageLength;s++){cout<<optPage[s]<<" ";}cout<<endl;}}//先进先出页面调度void fifo(){int length;int fifo[100]={0};int pageLength;int fifoPage[100]={0};cout<<"*************************欢迎页面先进先出fifo调度算法***********************"<<endl;cout<<"***********************************0代表空**********************************"<<endl;cout<<"请输入页框数："<<endl;cin>>pageLength;cout<<"请输入页面序列的长度："<<endl;cin>>length;cout<<"请输入页面序列："<<endl;for(int i=1;i<=length;i++){cout<<"请输入第"<<i<<"个的页面号："<<endl;cin>>fifo[i];}for(i=1;i<=length;i++){int flag=0;for(int j=1;j<=pageLength;j++){if(fifo[i]==fifoPage[j]){flag=1;j=pageLength+1;}else if(fifoPage[j]==0){fifoPage[j]=fifo[i];j=pageLength+1;flag=1;}}if(flag==1){}else{cout<<"淘汰"<<fifoPage[1]<<endl;for(j=1;j<=pageLength;j++){fifoPage[j]=fifoPage[j+1];}fifoPage[pageLength]=fifo[i];}cout<<"页框内容为：";for(int s=1;s<=pageLength;s++){cout<<fifoPage[s]<<" ";}cout<<endl;}}//最近最少使用页面调度void lru(){int length;int lru[100]={0};int pageLength;int lruPage[100]={0};cout<<"*************************欢迎页面最近最少使用lru调度算法***********************"<<endl;cout<<"***********************************0代表空**********************************"<<endl;cout<<"请输入页框数："<<endl;cin>>pageLength;cout<<"请输入页面序列的长度："<<endl;cin>>length;cout<<"请输入页面序列："<<endl;for(int i=1;i<=length;i++){cout<<"请输入第"<<i<<"个的页面号："<<endl;cin>>lru[i];}for(i=1;i<=length;i++){int flag=0;for(int j=1;j<=pageLength;j++){if(lru[i]==lruPage[j]){for(int cc=j;cc>0;cc--){lruPage[cc]=lruPage[cc-1];}lruPage[1]=lru[i];flag=1;j=pageLength+1;}else if(lruPage[j]==0){for(int vv=j;vv>0;vv--){lruPage[vv]=lruPage[vv-1];}lruPage[1]=lru[i];j=pageLength+1;flag=1;}}if(flag==1){}else{cout<<"淘汰"<<lruPage[pageLength]<<endl;for(j=pageLength;j>0;j--){lruPage[j]=lruPage[j-1];}lruPage[1]=lru[i];}cout<<"页框内容为：";for(int s=1;s<=pageLength;s++){cout<<lruPage[s]<<" ";}cout<<endl;}}四、执行结果：【页框数为3，页面序列依次为<2，5，2，1，3，5，6，3，6，1>】1）OPT五、实验总结：通过本次实验，我不仅了解了全局页面替换算法的概念，更掌握其核心思想。