操作系统银行家算法实验报告

实验五 银行家算法

一、实验目的和要求

①理解死锁概念，银行家算法及安全检测算法。 ②在Linux操作系统下用C++进行编程。 ③利用C++设计实现银行家算法的基本过程。 ④验证银行家算法对于避免死锁的作用。

二、实验方法内容

①算法设计思路

1．设计进程对各类资源最大申请表示及初值确定。 2．设定系统提供资源初始状况。

3．设定每次某个进程对各类资源的申请表示。

4．编制程序，依据银行家算法，决定其申请是否得到满足。

②算法流程图如下：

开 始 输入资源数m,及各类资源总数,初始化Available向量 输入进程数n，i=1 Y i≤n N 输入进程i的最大需求向量max。 N Max≤资源总数 提示错误重新输入 Y i 加1 初始化Need矩阵 Y 所有进程运行都结束 Need矩阵为0 N END 任选一进程作为当前进程 Y 该进程的Need向量0 该进程已运行结束 N 输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或给出提示

③算法中用到的数据结构说明

1. 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=k，标是系统中现有Rj类资源k个。

2. 最大需求矩阵P，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果P（i，j）=k，表示进程Pi需要Rj类资源的最大数目为k。

3. 分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程Pi当前已经分到Rj类资源的数目为k。Allocation i表示进程Pi的分配向量，有矩阵Allocation的第i行构成。

4. 需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程Pi还需要Rj类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。 上述三个矩阵间存在关系：Need（i，j）=P（i，j）－ Allocation（i，j）；

5. Request i 是进程Pi 的请求向量。Request i （j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查： ①.如果Request i ≤Need，则转向步骤2；否则出错。

②如果Request i ≤R，则转向步骤3；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。

③系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值： R = R － Request i

Allocation I = Allocation I + Request i Need I = Need i － Request i

④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待

6. 主要的常量变量

#define W 10 //最大进程数W=10

#define R 20 //最大资源总数R=20 int AVAILABLE[R]; //可利用资源向量 int MAX[W][R]; //最大需求矩阵 int ALLOCATION[W][R]; //分配矩阵 int NEED[W][R]; //需求矩阵

int Request[R]; //进程请求向量

void changdata(int k); //进程请求资源数据改变 int chksec(int s); //系统安全性的检测

7.主要模块（函数和数据）

void inputdata(); //数据输入 void showdata(); //数据显示

void changdata(int k); //进程请求资源数据改变 void restoredata(int k); //数据恢复

int chksec(int s); //系统安全性的检测 int chkmax(int s); //检测最大需求

void bank(); //检测分配的资源是否合理

四、实验代码 Banker.cpp

#include #include using namespace std; #define FALSE 0 #define TRUE 1

#define W 10 //最大进程数W=10 #define R 20 //最大资源总数R=20 int M ;

int N ; int ALL_RESOURCE[W];

int AVAILABLE[R]; //可利用资源向量 int MAX[W][R]; //最大需求矩阵 int ALLOCATION[W][R]; //分配矩阵 int NEED[W][R]; //需求矩阵

int Request[R]; //进程请求向量 void inputdata(); //数据输入 void showdata(); //数据显示

void changdata(int k); //进程请求资源数据改变 void restoredata(int k); //数据恢复

int chksec(int s); //系统安全性的检测 int chkmax(int s); //检测最大需求

void bank(); //检测分配的资源是否合理 void main() { int i,j;

inputdata(); for(i=0;iif (i>=M)

cout<<\"错误提示：经安全性检查发现，系统的初始状态不安全\\n\"<{ cout<<\"提示：经安全性检查发现，系统的初始状态安全！\"<} }

void inputdata() { int i=0,j=0,p;

cout<<\"请输入总进程数: \"; do{

cin>>M;

if (M>W) cout<W); cout<cout<<\"请输入资源的种类数: \"; do {cin>>N; if (N>R)

cout<while (N>R); cout<cout<<\"请依次输入各类资源的总数量，即设置向量all_resource: \"; for(i=0;i>ALL_RESOURCE[i]; cout<cout<<\"请依次输入各进程所需要的最大资源数量，即设置矩阵max: \"<for (j=0;jdo { cin>>MAX[i][j];

if (MAX[i][j]>ALL_RESOURCE[j])

cout<while (MAX[i][j]>ALL_RESOURCE[j]); } }

cout<cout<<\"请依次输入各进程已经占据的各类资源数量，即设置矩阵allocation: \"<for (i=0;ifor (j=0;jdo{ cin>>ALLOCATION[i][j];

if (ALLOCATION[i][j]>MAX[i][j])

cout<}while (ALLOCATION[i][j]>MAX[i][j]); } }

cout<NEED[i][j]=MAX[i][j]-ALLOCATION[i][j]; for (j=0;j{ p=ALL_RESOURCE[j]; for (i=0;i{ p=p-ALLOCATION[i][j]; AVAILABLE[j]=p; if(AVAILABLE[j]<0) AVAILABLE[j]=0; } } }

void showdata() { int i,j;

cout<<\"各种资源的总数量，即向量all_resource为:\"<for (j=0;jcout<<\" 资源\"<cout<<\"当前系统中各类资源的可用数量，即向量available为:\"<for (j=0;jcout<<\" 资源\"<cout<<\"各进程还需要的资源数量，即矩阵need为:\"<{ cout<<\"进程P\"<cout<cout<cout<<\"各进程已经得到的资源量，即矩阵allocation为: \"<{ cout<<\"进程P\"<cout<} cout<void changdata(int k) { int j;

for (j=0;jAVAILABLE[j]=AVAILABLE[j]-Request[j];

ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j]; } }

void restoredata(int k) {

int j;

for (j=0;j{ AVAILABLE[j]=AVAILABLE[j]+Request[j];

ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; } }

int chksec(int s) {

int WORK,FINISH[W]; int i,j,k=0; for(i=0;iFINISH[i]=FALSE; for(j=0;j{ WORK=AVAILABLE[j]; i=s; do

{ if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) {

WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; }else { i++; }

}while(ifor(i=0;iif(FINISH[i]==FALSE) { return 1; }

} return 0; }

int chkmax(int s) { int j,flag=0; for(j=0;jif (MAX[s][j]==ALLOCATION[s][j]) { flag=1;

AVAILABLE[j]=AVAILABLE[j]+MAX[s][j]; MAX[s][j]=0; }

} return flag; }

void bank() {

int i=0,j=0;

char flag='Y';

while(flag=='Y'||flag=='y') {

i=-1;

while(i<0||i>=M) { cout<<\"请输入需申请资源的进程号（从P0到P\"<>i;

if(i<0||i>=M)

cout<<\"输入的进程号不存在，重新输入!\"<cout<<\"请输入进程P\"<{ cout<<\" 资源\"<>Request[j];

if(Request[j]>NEED[i][j])

{ cout<<\"进程P\"<cout<<\"申请不合理，出错!请重新选择!\"<else

{ if(Request[j]>AVAILABLE[j])

{ cout<<\"进程P\"<cout<<\"申请不合理，出错!请重新选择!\"<if(flag=='Y'||flag=='y') { changdata(i); if(chksec(i)) { cout<cout<<\"该分配会导致系统不安全 本次资源申请不成功，不予分配\"<cout<restoredata(i); }

else { cout<cout<<\"经安全性检查，系统安全，本次分配成功，且资源分配状况如下所示：\"<cout<{cout<<\"在资源分配成功之后，由于该进程所需的某些资源的最大需求量已经满足，\"<cout<<\"因此在进程结束后系统将回收这些资源！\"<cout<<\"在资源收回之后，各进程的资源需求和分配情况如下所示：\"<cout<cout<<\" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: \"; cin>>flag; } }

五、实验结果

六、实验总结

通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。实验中遇到点问题，通过查阅资料,询问老师顺利解决。通过这次的实践，使我的理论知识更加的牢固，使自己在学习以后的知识及编程语言更加具有信心了。操作系统是计算机系统中必不可少的系统软件。它是计算机系统中的各种资源的管理者和各种活动的组织者、指挥者。银行家算法是为了使系统保持安

全状态。我们可以把操作系统看作是银行家，操作系统管理相当与银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。通过你上面的例子，我们看到银行家算法确实能保证系统时时刻刻都能处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需要花费较多的时间。这次的实验，让我深有体会。