操作系统实验_银行家算法

1、。学号P71514032专业计算机科学与技术姓名实验日期2017.11.9教师签字成绩实验报告【实验名称】银行家算法【实验目的】掌握银行家算法，用银行家算法模拟操作系统避免死锁的方法【实验原理】银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程， 从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。 反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处

2、于安全状态， 可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待用 C 语言编写一个简单的银行家算法模拟程序， 用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。 进程可动态地申请资源， 系统按各进程的申请动态地分配资源。 要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况【数据结构和符号说明 】。1。可利用资源向量Available最大需求矩阵 Max分配矩阵 Allocation需求矩阵 Need工作向量 Work标记向量 Finishchar

3、 name10010;/定义最大 100 个进程，每个大小为 10int Max100100;/定义int Allocation100100;/可利用资源向量资源数int Need100100;/需求矩阵int avaiable100;/系统可利用资源int avaiable1100;int state100; /进程状态数组char name110010;/进程名int bigger;/是否大于int N;/进程数int n;/资源数int counter;函数：void Input()/输入函数void Init()/初始化void output()/输出安全序列或等待void inser

4、t_pcb()/请求进程或更新进程void show()/显示界面与选择 int CmpRequestAvailable(int Pos,int n)/比较 Request 和 Available 的大小int CmpRequestNeed(int Pos,int n)/比较 Request 和 Need的大小void Reset(intn,intPos)/ 更新 request 之后的 Need，Allocation，Available的值 void Banker()/银行家算法【实验流程图及算法实现】用 C 语言编写一个简单的银行家算法模拟程序， 用银行家算法实现资源分配。程序能模拟多个进

5、程共享多种资源的情形。 进程可动态地申请资源， 系统按各进程的申请动态地分配资源。 要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。2【流程图 】否输出信息。开始输入进程数目与资源个数输入现有的资源个数及各进程信息计算每个进程所需的资源数是进程状态释放与否否是否满足当前进程需求当前资源个数等于自身加上该进程所拥有进程数目，标记状态已扫描到最后一否转向下一个进程个进程是输出所有安全序列结束。3。代码：#includeusing namespace std;char name10010;定义最大100

6、个进程，每个大小为10int Max100100;/定义int Allocation100100;/可利用资源向量资源数int Need100100; /需求矩阵int avaiable100;/int state100;/进程状态数组int dayu;是否大于int N;int n;void input ()cout输入进程个数N;cout输入资源个数n;cout系统现有的各资源的个数endl;for(int i=0; iavaiablei;for(int i=0; iN; i+)/输入cout输入第 i 个进程的名字namei;cout输入第 i 所需要各进程的最大资源数endl;for(

7、int j=0; jMaxij;cout输入第 i 现在所拥有的资源个数endl;for(int j=0; jAllocationij;statei=0;for(int i=0; iN; i+)for(int j=0; jn; j+) /寻找需求矩阵Needij=Maxij-Allocationij;void yinhangjia()int i,j,k;for( i=0; iN; i+)。4。for( j=0; jN; j+)if(statej=1)continue;dayu=0;for( k=0; k=Needjk)dayu=1;elsedayu=0;break;if(dayu=1)/判断状

8、态statej=1;coutnamejendl;for(int m=0; mn; m+)avaiablem+=Allocationjm;break;int main()input();/输入yinhangjia();截图：。5。6。带有 resquest请求更新的银行家算法：描述：1）如果 Requesti是进程 Pi 的请求向量，如果 Requesti ，j=K, 表示进程 Pi需要 K 个 Rj 类型的资源。当发出资源请求后，系统按下述步骤进行检查：如果Requestij= Needi,j ，便转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2）如果 Request

9、ij=Availablej,便转向步骤 3，否则，表示尚无足够资源，进程 Pi 须等待。3）系统试探着把资源分配给进程，并修改下面数据结构中的数值。4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进 i ，以完成本次分配； 否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程等待。7流程图：开始输入进程、资源数目， max、allocationAvailable 矩阵计算 need矩阵初始化 work 、 finish向量Finish=false&Need=work ？否是Work=work+allocationFinishi=true;。输出

10、安全序列进入银行家算法输入请求资源的信息否Resquestneed是Resquestavaila否ble进入安全性检查算法是是Finish=true输出等待进程否输出无安全序列结束代码：#include#includeusing namespace std;char name10010;/定义最大100 个进程，每个大小为10int Max100100;/定义int Allocation100100;/可利用资源向量资源数。8。int Need100100; /需求矩阵int avaiable100;/int avaiable1100;int state100;/进程状态数组char name

11、110010;int bigger;/是否大于int N;int n;int counter;void input ()/输入函数cout输入进程个数N;cout输入资源个数n;cout系统现有的各资源的个数endl;for(int i=0; iavaiablei;avaiable1i=avaiablei;for(int i=0; iN; i+)/输入cout输入第 i+1 个进程的名字 namei;cout输入第 i+1 所需要各进程的最大资源数endl;for(int j=0; jMaxij;cout输入第 i+1 现在所拥有的资源个数endl;for(int j=0; jAllocati

12、onij;statei=0;for(int i=0; iN; i+)for(int j=0; jn; j+) /寻找需求矩阵Needij=Maxij-Allocationij;void Banker()/银行家算法int i,j,k;counter=0;。9。for(i=0; iN; i+)statei=0;for( i=0; iN; i+)/循环次数for( j=0; jN; j+)/每次从头越查找if(statej=1)continue;bigger=0;for( k=0; k=Needjk)/每一个大于需求bigger =1;elsebigger=0;break;/跳出需求循环if( b

13、igger=1)/判断状态，此时该进程所有need= avaiablestatej=1;strcpy(name1counter+,namej);for(k=0; kn; k+)avaiablek+=Allocationjk;/ 更新 avaiable 向量 break;void output()/输出安全序列或等待int i;if (counter=N)cout安全序列为 :;for(i=0; iN-1; i+)cout name1i ;cout nameiendlendl;else cout不存在安全序列, 插入失败 endl;。10。void insert_pcb()/请求进程或更新进程c

14、har name110;int choose;int add100;cout1、增加新的进程endl;cout2、对原有进程增加资源申请choose;if(choose=1)int bigger=0;cout输入插入进程的名字nameN;cout输入该进程拥有的资源个数endl;for(int j=0; jAllocationNj;stateN=0;cout输入该所需要各资源最大数目endl;for(int j=0; jMaxNj;NeedNj=MaxNj-AllocationNj;stateN=0;for( int k=0; k=NeedNk)/每一个大于需求bigger =1;elsebi

15、gger=0;break;/跳出需求循环if(bigger=1)cout插入成功 endl;N=N+1;。11。Banker();output();elsecout插入失败，进程等待！endl;elseint pos;/找到需更新进程的位置cout输入原有进程的名字name110;for(int i=0; iN; i+)if(!strcmp(name1,namei)pos=i;break;cout输入该进程还需要的各资源数endl;for(int j=0; jaddj;for( int k=0; k=addk)/每一个大于需求bigger =1;elsebigger=0;break;/跳出需求

16、循环if(bigger=1)cout插入成功 endl;for(int m=0; mn; m+)Maxposm+=addm;Needposm+=addm;avaiablem=avaiable1m;。12。Banker();output();else cout插入失败，进程等待！endl;void show()/显示界面与选择int i,j;coutendl*最大需求矩阵*endl;cout进程名 t;for(i=0; in; i+)coutmaxit;coutendl;for(i=0; iN; i+)coutnameit;for(j=0; jn; j+)coutMaxijt;coutendl;

17、cout*endlendl;cout*各进程已有资源数*endl;cout进程名 t;for(i=0; in; i+)coutAllocationit;coutendl;for(i=0; iN; i+)coutnameitt;for(j=0; jn; j+)coutAllocationijtt;coutendl;cout*endlendl;cout*各进程需求资源数*endl;cout进程名 t;for(i=0; in; i+)cout Needit;coutendl;for(i=0; iN; i+)coutnameitt;。13。for(j=0; jn; j+)cout Needijtt;c

18、outendl;cout*endlendl;int main()int select;cout银行家算法 endl;cout初始化 endl;input();/输入show();Banker();output();docout1、更新 endl;cout2、查看各进程的信息endl;cout3、结束 select;if(select=3)break;else if(select=1)insert_pcb();else show();while(1);截图：输入资源种类数目，输入最大需求矩阵，输入分配矩阵， 输入可用资源数目，得到安全序列。14。对进程 P1进行请求，此时会形成一个新的安全序列,

19、p1 进程的 need 和 max发生相应的变化。15。继续修改进程4，插入各需求3 3 0 ，不存在安全序列，此时需要等待。16。请求一个新进程，所需求的最大资源为3 34，现有为2 2 3，形成新的安全序列。17。查看各进程信息，并输出安全序列。再请求一个新的大进程，此时资源不足，需要等待。资源数为4：。18。19。更新 P1 进程，程序阻塞，进程等待。请求一个新进程，P5。插入成功，此时有安全序列。20。【小结或讨论】1、 银行家算法名字源于该算法实际上是用于确保银行系统不会用尽系统资源，因为当银行系统不再满足所有客户的需求，系统将不会分配钱（看作资源）给客户，银行必须确保对钱的请求不会导致银行系统处于不安全状态。 如果上述情况不会发生， 则该情况下请求是被允许的， 否则，客户必须等到其他客户往银行存进足够银行分配的资金。2、银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁， 若发生死锁则让进程等待。 这次实验的核心问题在于试探分配，若试探分配得到的结果是系统不安全则分配作废， 恢复原先资源分配状态，转而寻找其