银行家算法模拟

操作系统课程设计（银行家算法的模拟实现）一、设计目的1、进一步了解进程的并发执行。

2、加强对进程死锁的理解。

3、用银行家算法完成死锁检测。

二、设计内容给出进程需求矩阵C、资源向量R以及一个进程的申请序列。

使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。

三、设计要求1、初始状态没有进程启动。

2、计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列。

3、每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V。

4、每次申请情况应可单步查看，如：输入一个空格，继续下个申请。

四、算法原理1、银行家算法中的数据结构(1)、可利用资源向量Available，这是一个含有m个元素的数组，其中的每个元素代表一类可利用资源的数目，其初始值是系统中所配置的该类全部资源的数目，其数值随该类资源的分配和回收而动态改变。

如果Available[j]=K，则表示系统中现有Rj类资源K个。

（2）、最大需求矩阵Max，这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。

如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

（3）、分配矩阵Allocation。

这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。

如果Allocation[i,j]=K，则表示进程i当前已经分得Rj类资源的数目为K。

（4）、需求矩阵Need。

这也是一个n*m的矩阵，用以表示每个进程尚需要的各类资源数。

如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵间存在以下关系：Need[i,j]=Max[i,j]-Allocation[i,j]2、银行家算法应用模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法（扫描）；二是安全性算法。

（1）银行家算法（扫描）设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。

项目四银行家算法模拟1.设计原理银行家算法基本原理：操作系统在每一次分配之前都要进行以下操作，判断当前的资源请求是否安全，如果安全则实施分配，否则不予分配。

第1步：操作系统对提出资源请求的进程按所请求的资源数目实施预分配，修改剩余资源数组、资源分配矩阵和剩余资源请求矩阵；第2步：将剩余资源数组代入剩余需求矩阵中与各元素进行比较，找到可以满足其所有资源需求的某个进程将它加入到安全序列中；第3步：将该进程运行结束后释放的资源累加到剩余资源数组中；第4步：再重复第2、3两步。

若所有进程都能够进入安全序列<Pi,Pj,……>，则此次分配可以实施，否则系统将会处于不安全状态，因而不能实施分配。

如果不能实施分配，则将系统还原到预分配之前的状态。

2．设计步骤和方法（1）设计数据结构：剩余资源数组available，如available[j] = k 表示资源Rj现有k个。

（2）设计数据结构：最大资源请求矩阵max，如max [i][j] = k表示进程Pi最多可申请k个类型为Rj的资源。

（3）设计数据结构：资源分配矩阵allocation，定义每个进程现在所分配的各种资源类型的数量，如allocation [i][j] = k表示进程Pi现在分配了k个类型为Rj的资源。

（4）设计数据结构：剩余资源请求矩阵claim，定义每个进程还需要的剩余的资源数，如claim [i][j] = k表示进程Pi还需要申请k个类型Rj的资源。

其中，claim [i][j] = max[i][j] -allocation[i][j]。

（5）设计函数完成功能：系统内资源总数已知、各进程对各类资源最大需求数目已知、已分配资源数目已知的前提下，某进程提出各类资源的需求量时能判断状态是否安全，以决定是否予以分配。

实验报告附录3程序源代码：#include<string.h>#include<stdio.h>#include<stdlib.h># define m 50# define false 0#define true 1int no1; //进程数int no2; //资源数int r;int allocation[m][m],need[m][m],available[m],max[m][m];char name1[m],name2[m]; //定义全局变量void main(){void check();void print();int i,j,p=0,q=0;char c;int request[m],allocation1[m][m],need1[m][m],available1[m];printf("**********************************************\n");printf("* 银行家算法的设计与实现*\n");printf("**********************************************\n");printf("请输入进程总数:\n");scanf("%d",&no1);printf("请输入资源种类数:\n");scanf("%d",&no2);printf("请输入Max矩阵:\n");for(i=0;i<no1;i++)for(j=0;j<no2;j++)scanf("%d",&max[i][j]); //输入已知进程最大资源需求量printf("请输入Allocation矩阵:\n");for(i=0;i<no1;i++)for(j=0;j<no2;j++)scanf("%d",&allocation[i][j]); //输入已知的进程已分配的资源数for(i=0;i<no1;i++)for(j=0;j<no2;j++)need[i][j]=max[i][j]-allocation[i][j]; //根据输入的两个数组计算出need矩阵的值printf("请输入Available矩阵\n");for(i=0;i<no2;i++)scanf("%d",&available[i]); //输入已知的可用资源数print(); //输出已知条件check(); //检测T0时刻已知条件的安全状态if(r==1) //如果安全则执行以下代码{do{printf("\n请输入请求资源的进程号(0~4)：\n");for(j=0;j<=no2;j++){scanf("%d",&i);if(i>=no1){printf("输入错误，请重新输入：\n");continue;}else break;}printf("\n请输入该进程所请求的资源数request[j]:\n");for(j=0;j<no2;j++)scanf("%d",&request[j]);for(j=0;j<no2;j++)if(request[j]<=need[i][j]) p=0;//判断请求是否超过该进程所需要的资源数if(p)printf("请求资源超过该进程资源需求量，请求失败！\n");else{for(j=0;j<no2;j++)if(request[j]<=available[j]) q=0; //判断请求是否超过可用资源数if(q)printf("没有做够的资源分配，请求失败！\n");else //请求满足条件{for(j=0;j<no2;j++){available1[j]=available[j];allocation1[i][j]=allocation[i][j];need1[i][j]=need[i][j];//保存原已分配的资源数，仍需要的资源数和可用的资源数available[j]=available[j]-request[j];allocation[i][j]=allocation+request[j];need[i][j]=need[i][j]-request[j];//系统尝试把资源分配给请求的进程}print();check(); //检测分配后的安全性if(r==0) //如果分配后系统不安全{for(j=0;j<no2;j++){available[j]=available1[j];allocation[i][j]=allocation1[i][j];need[i][j]=need1[i][j];//还原已分配的资源数，仍需要的资源数和可用的资源数}printf("返回分配前资源数\n");print();}}}printf("\n你还要继续分配吗？Y or N ?\n");//判断是否继续进行资源分配c=getchar();}while(c=='y'||c=='Y');}}void check() //安全算法函数{int k,f,v=0,i,j;int work[m],a[m];int finish[m];r=1;for(i=0;i<no1;i++)finish[i]=false; // 初始化进程均没得到足够资源数并完成for(i=0;i<no2;i++)work[i]=available[i];//work[i]表示可提供进程继续运行的各类资源数k=no1;do{for(i=0;i<no1;i++){if(finish[i]==false){f=1;for(j=0;j<no2;j++)if(need[i][j]>work[j])f=0;if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程{finish[i]=true;a[v++]=i; //记录安全序列号for(j=0;j<no2;j++)work[j]+=allocation[i][j]; //释放该进程已分配的资源}}}k--; //每完成一个进程分配，未完成的进程数就减1}while(k>0);f=1;for(i=0;i<no1;i++) //判断是否所有的进程都完成{if(finish[i]==false){f=0;break;}}if(f==0) //若有进程没完成，则为不安全状态{printf("系统处在不安全状态！");r=0;}else{printf("\n系统当前为安全状态，安全序列为：\n");for(i=0;i<no1;i++)printf("p%d ",a[i]); //输出安全序列}}void print() //输出函数{int i,j;printf("\n");printf("*************此时刻资源分配情况*********************\n");printf("进程名/号| Max | Allocation | Need |\n");for (i = 0; i < no1; i++){printf(" p%d/%d ",i,i);for (j = 0; j < no2; j++){printf("%d ",max[i][j]);}for (j = 0; j < no2; j++){printf(" %d ",allocation[i][j]);}for (j = 0; j < no2; j++){printf(" %d ",need[i][j]);}printf("\n");}printf("\n");printf("各类资源可利用的资源数为:");for (j = 0; j < no2; j++){printf(" %d",available[j]);}printf("\n");}（程序结束）附录 4程序运行调试结果：1、程序初始化2、检测系统资源分配是否安全结果。

OS模拟银行家算法分享一下最近的劳动成果，事无巨细，勿以细小而不为。

1：作业流程1.1 阅读算法，得出问题的求解方法；1.2 作程序流程图；1.3 构造所需的数据模型；1.4 开始敲代码啦，伴随着漫长的纠错排错调试过程，当error:100变成error:0的时候会很爽；1.5 功能基本实现了，可以再完善一下，美化一下界面；1.6 测试程序：回归测试，黑盒测试各种测试，代码写得好，测试要求就可以相对严格一些；1.7 通过测试一般就算完成作业了，其实还可以写一些相关的文档。

在Readme中写一些开发总结，用户帮助，修复bug和改进方案等信息。

2：银行家算法程序实现流程图：3：bankers_ALG.cpp CODE:--------------------------------------------------------------------------------------------------------------------------------------------------#include<iostream>using namespace std;int *one_array_malloc(int n); //一维数组分配int **two_array_malloc(int n,int m); //二维数组分配int compare21(int b,int m,int **Li,int *Bi);//向量比较函数=0->Li<=Bi Li是二维数组int compare11(int b,int m,int *Li,int *Bi);//向量比较函数=0->Li<=Bi Li是一维数组int compare12(int b,int m,int *Li,int **Bi);//向量比较函数=0->Li<=Bi Li是一维数组void print(int n,int m,int **Max,int **Allocation,int **Need,int *Available);//输出函数void print_space(int n);//输出n个空格函数int security_check(int n,int m,int *xl,int *work,int **Allocation,int **Need,int *Available);//安全性检查函数void allocation(int b,int m,int *Request,int *Available_temp,int **Allocation_temp,int **Need_temp);//试分配void copy1(int n,int *s1,int *s2);//转储函数s2->s1 一维数组void copy2(int n,int m,int **s1,int **s2);//转储函数s2->s1 二维数组int in(int n,int i,int *xl);//判断进程是否在安全序列中void main(){int n,m,i,j;int *Available,*xl; int **Max;int **Allocation;int **Need;FILE *fp;if((fp=fopen("input53.txt","r"))==NULL){printf("cannot open this file!\n");return;}fscanf(fp,"%d%d",&n,&m);Available=one_array_malloc(m);xl=one_array_malloc(n);Max=two_array_malloc(n,m);Allocation=two_array_malloc(n,m);Need=two_array_malloc(n,m);for(i=0;i<m;i++){fscanf(fp,"%d",&Available[i]);}for(i=0;i<n;i++)for(j=0;j<m;j++){fscanf(fp,"%d",&Max[i][j]);}for(i=0;i<n;i++)for(j=0;j<m;j++){fscanf(fp,"%d",&Allocation[i][j]);Need[i][j]=Max[i][j]-Allocation[i][j];}fclose(fp);print(n,m,Max,Allocation,Need,Available);int *work,*Request;int *Available_temp,**Allocation_temp,**Need_temp;int jc,p; work=one_array_malloc(n);Available_temp=one_array_malloc(m);Allocation_temp=two_array_malloc(n,m);Need_temp=two_array_malloc(n,m);copy1(m,Available_temp,Available);copy2(n,m,Allocation_temp,Allocation);copy2(n,m,Need_temp,Need);Request=one_array_malloc(n);if(security_check(n,m,xl,work,Allocation,Need,Available)==0)cout<<"载入数据正确,系统处于安全状态。

操作系统课程设计报告专业计算机科学与技术学生姓名班级计算机科学与技术学号指导教师完成日期2014.3.20题目：银行家算法的模拟实现一、设计目的本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。

二、设计内容1）概述用C或C++语言编制银行家算法通用程序，并检测所给状态的系统安全性。

1.算法介绍：数据结构：1）可利用资源向量 Available；2）最大需求矩阵Max；3）分配矩阵Allocation；4）需求矩阵Need2.功能介绍模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：第一部分：银行家算法（扫描）；第二部分：安全性算法。

2）设计原理一．银行家算法的基本概念1、死锁概念。

在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。

所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

2、关于死锁的一些结论：参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。

3、资源分类。

永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源不可抢占资源临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式4、产生死锁的四个必要条件：互斥使用（资源独占）、不可强占（不可剥夺）、请求和保持（部分分配，占有申请）、循环等待。

《银行家算法的模拟实现》 --实验报告题目: 银行家算法的模拟实现专业:班级:组员:指导老师:一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。

本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。

二、实验内容模拟实现银行家算法实现死锁避免。

要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。

三、实验分析过程1、整个银行家算法的思路。

先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。

1)进程一开始向系统提出最大需求量.2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待2、算法用到的主要数据结构和C语言说明。

（1）、可利用资源向量INT A V AILABLE[M] M为资源的类型。

（2）、最大需求矩阵INT MAX[N][M] N为进程的数量。

（3）、已分配矩阵INT ALLOCA TION[N][M]（4）、还需求矩阵INT NEED[N][N]（5）、申请各类资源数量int Request[x]; //（6）、工作向量int Work[x];（7）、int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是3、银行家算法（主程序）（1）、系统初始化。

输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数量等（2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。

（3）、检查用户的请求是否小于还需求的数量，条件是K<=NEED[I,J]。

实验四银行家算法模拟【实验目的】（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

（3）理解和掌握安全序列、安全性算法【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。

【实验原理】一、安全状态指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。

二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。

系统按下述步骤进行安全检查：（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

三、安全性算法（1）设置两个向量：①工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m 个元素，在执行安全算法开始时，Work∶=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。

开始时先做Finish ［i］∶=false; 当有足够资源分配给进程时，再令Finish［i］∶=true。

操作系统实验银行家算法模拟实现（强烈推荐）银行家算法模拟实现一．实验目的1) 理解死锁避免相关内容；2) 掌握银行家算法主要流程；3) 掌握安全性检查流程。

二．实验描述本实验主要对操作系统中的死锁预防部分的理论进行实验。

要求实验者设计一个程序，该程序可对每一次资源申请采用银行家算法进行分配。

三．实验内容1) 设计多个资源（≥3）；2) 设计多个进程（≥3）；3) 设计银行家算法相关的数据结构；4) 动态进行资源申请、分配、安全性检测并给出分配结果。

四．实验要求1) 编写程序完成实验内容；2) 画出安全性检测函数流程图；3) 小组派1人上台用PPT演讲实现过程；4) 撰写实验报告。

测试要求1) 进行Request请求，输入参数为进程号、资源号和资源数；2) 进行3次以上的Request请求；3) 至少进行1次资源数目少于可用资源数，但不安全的请求。

五．实验设备PC机1台，要求安装DOS7.1、Turbo C3.0、Windows2000。

六．实验结果七.实验思考1）针对死锁有哪些可行方案？2）死锁解除的难点是什么？八.银行家算法介绍8.1银行家算法的数据结构1) 可利用资源向量Available。

其中每个元素代表每类资源的数目。

2) 最大需求矩阵Max。

其中每个元素代表每个进程对于每类资源的最大需求量。

Max[i，j]=K表示i进程对于j类资源的最大需求量为K。

3) 分配矩阵Allocation。

其中每个元素代表每个进程已得到的每类资源的数目。

4) 需求矩阵Need。

其中每个元素代表每个进程还需要的每类资源的数目。

8.2银行家算法Request i [j]=K表示进程Pi需要K个j类资源。

1）如果Request i [j]≤Need[i , j]，便转向步骤2，否则认为出错。

2）如果Request i [j]≤Available[j]，便转向步骤3，否则表示无足够资源，Pi需等待；3）系统尝试分配资源给Pi；4）系统进行安全性检查，检查此次资源分配后，系统是否安全。

精品课程银行家算法的模拟实现1 课设简介：1.1 课程设计题目银行家算法的模拟实现1.2 课程设计目的通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。

1.3 课程设计内容模拟实现动态资源分配。

同时要求编写和调试一个系统动态资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。

2 实验原理分析：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程张勇；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。

防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。

通过这个算法可以用来解决生活中的实际问题，如银行贷款等。

3 程序结构分析：3.2 程序模块划分3.2.1.银行家算法:设进程i提出请求Request[n]，则银行家算法按如下规则进行判断。

(1)如果Request[n]>Need[i，n]，则报错返回。

(2)如果Request[n]>Available，则进程i进入等待资源状态，返回。

(3)假设进程i的申请已获批准，于是修改系统状态：Available=Available-RequestAllocation=Allocation+RequestNeed=Need-Request(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

3.2.2.安全性检查(1)设置两个工作向量Work=Available；Finish[M]=False(2)从进程集合中找到一个满足下述条件的进程，Finish [i]=FalseNeed<=Work如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。