操作系统课程设计银行家算法

银行家算法,可运行的,完整的论文

《操作系统--课程设计报告》

银行家算法

姓 名：

学 号：专 业：

指导老师：

银行家算法,可运行的,完整的论文

目录

一、设计目的 ............................................................................................................... 1

二、设计要求 ............................................................................................................... 1

三、设计内容和步骤 ................................................................................................... 1

四、算法描述 ............................................................................................................... 4

五、实验结果 ............................................................................................................. 11

六、实验心得 ............................................................................................................. 12

银行家算法,可运行的,完整的论文

一、设计目的

银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

二、设计要求

在了解和掌握银行家算法的基础上，能熟练的处理课本例题中所给状态的安全性问题，能编制银行家算法通用程序，将调试结果显示在计算机屏幕上。

具体程序的功能要求：

1．设定进程对各类资源最大申请表示及初值确定。

2．设定系统提供资源初始状况（已分配资源、可用资源）。

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

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

三、设计内容和步骤

设计内容

银行家算法的思路：先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

设计步骤

1、为实现银行家算法，系统中需要设置若干数据结构，用来表示系统中各进程的资源分配及需求情况。

假定系统中有M个进程，N类资源。进程数和资源数由程序中直接定义 #define M 5 //总进程数

#define N 3 //总资源数

银行家算法中使用的数据结构如下：

（1）可利用资源Available。这是一个含有m个元素的数组，其中的每

银行家算法,可运行的,完整的论文

一个元素代表一类资源的空闲资源数目，其初值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=k，表示系统中Rj类资源有k个。

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

（3）分配矩阵Allocation。这是一个n*m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源。如果Allocation[i,j]＝k, 表示进程Pi当前已分到 Rj类资源有k个。

（4）需求矩阵Need。这是一个n*m的矩阵，它定义了系统中每一个进程还需要的各类资源的数目。如果Need [i，j]=k，表示进程Pi需要Rj类资源有k个，才能完成任务。

int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//每个进程对每类资源的最大需求

int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已分配资源

int Avaliable[3]={3,3,2}; //系统可利用资源

int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//还需要资源

int Request[3];

2、实现过程

主函数

void main()//主函数

{ int choice;

showdata(); safeAlgorithm();

do

{ printf("\n输入接下来你要进行的操作 1：分配资源 2:显示资源 否则按任意键退出");

银行家算法,可运行的,完整的论文

} scanf("%d",&choice); switch(choice) { case 1: bankerAlgorithm(); break; case 2: showdata(); break; default: break; } }while((choice==1)||(choice==2));

其中用到的函数操作有三个

showdata();//显示资源矩阵 safeAlgorithm();//安全性检测算法

bankerAlgorithm();//利用银行家算法对申请资源对进行判定

3、安全性检查

程序中安全性算法的描述如下：

（1） 设置如下两个工作向量：

Work：表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有m个元素，执行安全性算法开始时，Work＝Available。

Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish[i]＝false；当有足够的资源分配给进程Pi时，令Finish[i]＝true。

（2） 从进程集合中找到一个能满足下列条件的进程：

Finish[i]＝＝false；

Need i<= Work；，

如果找到了就执行步骤（3），否则执行步骤（4）。

（3） 当进程Pi获得资源后，可执行直到完成，并释放出分配给它的资源，故应执行

Work = Work + Allocation;

Finish[i]＝false；

然后转向第（2）步骤。

（4） 若所有进程中的Finish[i]都是true，则表示系统处于安全状态；否

银行家算法,可运行的,完整的论文

则，系统处于不安全状态。

此过程由一个安全性检测函数实现：safeAlgorithm();//安全性检测算法

4、对进程申请资源的处理

当某一进程提出资源申请时，系统须做出判断，能否将所申请资源分配给该进程。设request为进程i的请求向量，如果request[j]=K，表示进程i需要K个j资源。当系统发出请求后，系统按下述步骤开始检查：

（1） 如果request[j]<=need[i][j],转向步骤2；否则报告出错，申请的资源大于它需要的最大值。

（2） 如果request[j]<=available[j],转向步骤3；否则报告出错，尚无足够的资源。

（3）系统试探着把资源分配给p[i]，并修改下列数据结构中的值： available[j]=available[j]-request[j]

allocation[i][j]=allocation[i][j]+request[j]

need[i][j]=need[i][j]-request[j]

（4）系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程i；否则，恢复原来的资源分配状态，让进程i等待。 整个过程由银行家算法实现：bankerAlgorithm()//利用银行家算法对申请资源对进行判定

四、算法描述

#include<string.h>

#include<stdio.h>

#define M 5 //定义进程数

#define N 3 //定义资源数 s

#define False 0

#define True 1

int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; //每个进程对每类资源的最大需求

int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//

银行家算法,可运行的,完整的论文

系统已分配资源

int Avaliable[3]={3,3,2}; //系统可利用资源

int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//还需要资源

int Request[3];

void showdata()//显示资源矩阵

{

int i,j;

printf("系统目前可利用的资源数量:\n A,B,C\n");

printf("resouce: ");

for (j=0;j<N;j++)

printf("%d,",Avaliable[j]);//输出分配资源

printf("\n");

printf("各进程的资源需求:\n");

for (i=0;i<M;i++)

{

printf("pr%d: ",i); for (j=0;j<N;j++) { printf("%d,",Max[i][j]);//输出最大需求资源数 } printf("\n");

}

printf("各进程得到资源:\n");

for (i=0;i<M;i++)

{

printf("pr%d: ",i);

for(j=0;j<N;j++)

printf("%d,",Allocation[i][j]);//输出已分配资源数

银行家算法,可运行的,完整的论文

printf("\n");

}

printf("各进程还需求资源:\n");

for (i=0;i<M;i++)

{

printf("pr%d: ",i); for(j=0;j<N;j++) printf("%d,",Need[i][j]);//输出还需要资源数 printf("\n");

}

}

void release(int i)//判断是否安全，若不安全则释放第j类资源

{

int j;

for (j=0;j<N;j++)

{

Avaliable[j]=Avaliable[j]+Request[j];

Allocation[i][j]=Allocation[i][j]-Request[j];

Need[i][j]=Need[i][j]+Request[j];

}

}

void distribute(int i)//若符合条件则对第j类资源进行分配

{

int j;

for (j=0;j<M;j++)

{

Avaliable[j]=Avaliable[j]-Request[j];

Allocation[i][j]=Allocation[i][j]+Request[j];

Need[i][j]=Need[i][j]-Request[j];

银行家算法,可运行的,完整的论文

}

}

void safeAlgorithm()//安全性算法

{

int Work[3],Finish[M]={0},result[M],run; /* work：表示系统可提供给进程继续运行的所需的各类资源数目 finish： 表示系统是否有足够的资源分配给进程 result用来存放依次执行成功的线程 */

int i,j,k=0,m,demand;

for(i=0;i<3;i++) { } for(i=0;i<M;i++) { demand=0; for(j=0;j<N;j++) { if (Finish[i]==False&&Need[i][j]<=Work[j]) { demand++; if(demand==3)//只有ABC三类资源都满足才把相应的线程 Work[i]=Avaliable[i]; //开始的时候work=available 记入数组result中

{ for(m=0;m<N;m++) Work[m]=Work[m]+Allocation[i][m];//重新分配第i类线程的当前可利用资源

Finish[i]=True; result[k]=i; i=-1; k++;

银行家算法,可运行的,完整的论文

安全

} else if(Finish[i]==False) { if(i==M-1) { printf("系统不安全\n");//如果不成功，输出系统不 } } run=False; } break; }

printf("系统资源分配成功!");//如果安全，输出成功

printf("分配的序列:\n");

for(i=0;i<M;i++)//输出运行进程数组

{

printf("pr%d ",result[i]);

}

void bankerAlgorithm()//利用银行家算法对申请资源对进行判定

{

int i,j,OK=1,run=True; printf("\n请输入第一个要求分配的资源进程号从(0 to 4):"); } scanf("%d",&i);//输入须申请的资源号

printf("请输入进程 %d 申请的资源:\n",i);

for(j=0;j<3;j++) {

银行家算法,可运行的,完整的论文

错

} scanf("%d",&Request[j]);//输入需要申请的资源 for (j=0;j<N;j++) { if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出 { printf("进程 %d 申请的资源大于它需要的资源",i);

printf(" error!\n");

OK=0;

break;

} else { if(Request[j]>Avaliable[j]) //判断申请是否大于当前资源，若大于则出错

} if(OK==1) //若都符合条件，则进行分配 { distribute(i); showdata(); //根据进程请求分配资源 } { printf("进程 %d 申请的资源大于当前可利用资源",i); printf(" error!\n"); } OK=0; break; //显示变换后的资源 safeAlgorithm(); //通过安全算法判断该序列是否安全

银行家算法,可运行的,完整的论文

}

} } { release(i);

void main()//主函数

{ int choice;

showdata(); safeAlgorithm();

do

{ printf("\n输入接下来你要进行的操作 1：分配资源 2:显示资源 否则按任意键退出");

} scanf("%d",&choice); switch(choice) { case 1: bankerAlgorithm(); break; case 2: showdata(); break; default: break; } }while((choice==1)||(choice==2));

银行家算法,可运行的,完整的论文

五、实验结果

银行家算法,可运行的,完整的论文

六、实验心得

在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。银行家算法是死锁避免算法中的一种，通过上面这个例子，我们看到银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。本次实验为时两天多，总体上来说实验是比较成功的。由于时间仓促，做的不是很完美，敬请老师谅解。

本文来源：https://www.bwwdw.com/article/pmi4.html