本科毕业论文---银行家算法模拟实现.doc

计算机操作系统程序设计
课程考核报告
银行家算法模拟实现

班 级： 09软件（1）
学 号：
姓 名：
指导老师：

目录
1. 课程设计简介------------------------------------------------3
1.1课程设计题目------------------------------------------------------------- 3
1.2课程设计目的-----------------------------------------3
1.3 课程设计要求----------------------------------------3
2 实验原理分析-------------------------------------------4
2.1 算法的来源及基本思想---------------------------------4
2.2 死锁产生的条件---------------------------------------4
2.3 模拟进程申请资源-------------------------------------5
3 概要设计------------------------------------------------5
4 详细设计------------------------------------------------7
5 代码设计------------------------------------------------8
6 调试分析----------------------------------------------- 14
7 心得体会------------------------------------------------21
8 参考文献------------------------------------------------21

1 课程设计简介：
1.1 课程设计题目
银行家算法的模拟实现。应用银行家算法验证进程安全性检查及分配资源。
1.2 课程设计目的
本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。
A、了解进程产生死锁的原因，了解为什么要进行死锁的避免。
B、掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。
1.3 课程设计要求
设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。
(1) 初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于等待态。资源需求总量表示进程运行过程中对资源的总的需求量。
已占资源量表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。
(2) 银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。
(a) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程。如果能，则转b)。
(b) 将资源分配给所需的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。
重复第a)步和第b )步，直到所有进程都标记为终止进程，或直到一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则假定的分配作废，让其等待。

2 实验原理分析：
2.1 算法的来源及基本思想
银行家算法，顾名思义是来源于银行的借贷业务，通过这个算法可以用来解决生活中的实际问题，如银行贷款等。一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。
2.2 死锁产生的条件
银行家算法是用来避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。
死锁的产生，必须同时满足四个条件：
A、即一个资源每次只能由一个进程使用；
B、第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；
C、第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；
D、第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。
防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

2.3 模拟进程申请资源
把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.

3 概要设计：
银行家算法可分为个主要的功能模块，其描述如下：
1.初始化
由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量赋值。
2.安全性检查算法
(1)设置两个工作向量Work=AVAILABLE;FINISH=false;
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行(3)；否则，执行(4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION;
Finish=true;
(4).如所有的进程Finish= true，则表示安全；否则系统不安全。
3. 银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。
设进程j提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1).如果REQUEST [j] [i]<= NEED[j][i]，则转(2)；否则，出错。
(2).如果REQUEST [j] [i]<= AVAILABLE[j][i]，则转(3)；否则，出错。
(3).系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[j][i];
ALLOCATION[j][i]+=REQUEST[j][i];
NEED[j][i]-=REQUEST[j][i];
用到的数据结构：
实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：
1).Available是一个长度为m的向量，它表示每类资源可用的数量。Available [j]=k，表示j类资源可用的数量为k。
2).Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max [i，j]=k，表示进程pi至多可以申请k个j类资源单位。
3).Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation [i，j]=k，表示进程i当前分到k个j类资源。
4).Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i，j]=k，表示进程pi尚需k个j类资源才能完成其任务。显然Need[i，j]= Max [i，j]- Allocation [i，j]。

4 详细设计：
1主函数main（）
要求在主函数中输入运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量，并对这些数据进行有效性检验，不符合条件的数据要进行重新输入。
2函数showdata( )
Showdata()函数用来输出资源的分配情况。对各进程资源的总数量、系统目前可利用的资源数量、各进程还需要的资源数量及各进程已分配的资源数量进行输出。
3函数bank( )
Bank()函数为银行家算法，对需申请资源的进程号j和所要申请的资源数量Request[j]进行输入,并分别将Request[j]与Need[i][j]和Available[j]进行比较，观察所要申请的资源数目是否合理。如合理，则判断此时系统是否安全，若安全则输出资源的分配情况，否则输出原来的系统资源分配情况，重新输入申请资源的数量。
4函数changdata( )
Changdata()函数用来改变可用资源和已经拿到资源和还需要的资源的值。当申请的资源数目合理时，对现在的系统资源分配情况进行刷新。
5函数chkerr（）
Chkerr（）函数用来检查系统此时的安全性。如果系统能够找到一个安全执行的序列，则各进程能正常运行终结，否则，此进程进入阻塞状态。
6函数 rstordata（ ）
Changdata（）函数,改变可用资源和已经拿到资源和还需要的资源的值。若判断出申请资源后系统是安全的，则要改变系统现在的资源分配情况：
Available[j]= Available[j]+Request[j];
Allocation[k][j]= Allocation [k][j]-Request[j];
Need[k][j]=Need[k][j]+Request[j]

5 代码设计：
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int M ; //总进程数
int N ; //资源种类
int ALL_RESOURCE[W];//各种资源的数目总和
int MAX[W][R]; //M个进程对N类资源最大资源需求量
int AVAILABLE[R]; //系统可用资源数
int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量
int NEED[W][R]; //M个进程还需要N类资源的资源量
int Request[R]; //请求资源个数
void showdata() //函数showdata,输出资源分配情况
{
int i,j;
printf("\n\n各种资源的总数量(all):\n");
for (j=0;j<N;j++)
printf(" 资源 %d: %d\n",j+1,ALL_RESOURCE[j]);
printf("\n\n");
printf("系统目前各种资源可用的数为(available):\n");
for (j=0;j<N;j++)
printf(" 资源 %d: %d\n", j+1, AVAILABLE[j]);
printf("\n\n");
printf("各进程还需要的资源量(need):\n\n");
printf(" 进程 ");
for(i=0;i<N;i++)
printf(" 资源%d ",i+1);
printf("\n");
for (i=0;i<M;i++)
{
printf("进程p%d：",i+1);
for (j=0;j<N;j++)
printf(" %d ",NEED[i][j]);
printf("\n");
}
printf("\n\n");
printf(" 各进程已经得到的资源量(allocation): \n\n");
printf(" 进程 ");
for(i=0;i<N;i++)
printf(" 资源%d ",i+1);
printf("\n");
for (i=0;i<M;i++)
{
printf("进程p%d: ",i+1);
for (j=0;j<N;j++)
printf(" %d ",ALLOCATION[i][j]);
printf("\n");
}
printf("\n");
}
void changdata(int k) //函数changdata,改变可用资源和已经拿到资源和还需要的资源的值
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];}}
void rstordata(int k) //函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值
{int j;
for (j=0;j<N;j++)
{ AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];}}
int chkerr(int s) //函数chkerr,检查是否安全
{ int WORK,FINISH[W];
int i,j,k=0;
for(i=0;i<M;i++)
FINISH[i]=FALSE;
for(j=0;j<N;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(i<M);
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
printf("\n");
printf(" 系统不安全!!! 本次资源申请不成功!!!\n");
printf("\n");
return 1;
}
}
printf("\n");
printf(" 经安全性检查，系统安全，本次分配成功。\n");
printf("\n");
return 0;
}
void bank() //银行家算法
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
printf(" 请输入需申请资源的进程号（从P1到P%d，否则重输入!）:",M);
printf("p");
scanf("%d",&i);
if(i<1||i>M)
printf(" 输入的进程号不存在，重新输入!\n");
}
printf(" 请输入进程P%d申请的资源数:\n",i);
for (j=0;j<N;j++)
{
printf(" 资源%d:",j+1);
scanf("%d",&Request[j]);
if(Request[j]>NEED[i-1][j]) //若请求的资源数大于进程还需要i类资源的资源量j
{
printf(" 进程P%d申请的资源数大于进程P%d还需要%d类资源的资源量!",i,i,j);
printf("申请不合理，出错!请重新选择!\n\n");
flag='N';
break;
}
else
{
if(Request[j]>AVAILABLE[j]) //若请求的资源数大于可用资源数
{
printf("进程P%d申请的资源数大于系统可用%d类资源的资源量!",i,j);
printf("申请不合理，出错!请重新选择!\n\n");
flag='N';
break;
}
}
}
if(flag=='Y'||flag=='y')
{
changdata(i-1); //调用changdata(i)函数，改变资源数
if(chkerr(i-1)) //若系统安全
{
rstordata(i-1); //调用rstordata(i)函数，恢复资源数
showdata(); //输出资源分配情况
}
else //若系统不安全
showdata();
} //输出资源分配情况
else //若flag=N||flag=n
showdata();
printf("\n");
printf("是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: ");
scanf("%c",&flag);
}
}
void main() //主函数
{
int i=0,j=0,p;
printf(" *************************************** \n");
printf(" 银行家算法的模拟实现 \n");
printf(" 20090307143 吴天一 \n");
printf(" *************************************** \n\n");
printf("请输入总进程数:");
scanf("%d",&M);
printf("请输入总资源种类:");
scanf("%d",&N);
printf("请输入总资源数(all_resource):");
for(i=0;i<N;i++)
scanf("%d",&ALL_RESOURCE[i]);
printf("依次输入各进程所需要的最大资源数量(max):\n");
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
scanf("%d",&MAX[i][j]);
if (MAX[i][j]>ALL_RESOURCE[j])
printf("\n占有资源超过了声明的该资源总数,请重新输入!\n");
}while (MAX[i][j]>ALL_RESOURCE[j]);
}
}
printf("依次输入各进程已经占据的资源数量(allocation):\n");
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
scanf("%d",&ALLOCATION[i][j]);
if (ALLOCATION[i][j]>MAX[i][j])
printf("\n占有资源超过了声明的最大资源,请重新输入\n");
}while (ALLOCATION[i][j]>MAX[i][j]);
}
}//初始化资源数量
for (j=0;j<N;j++)
{
p=ALL_RESOURCE[j];
for (i=0;i<M;i++)
{
p=p-ALLOCATION[i][j];//减去已经被占据的资源
AVAILABLE[j]=p;
if(AVAILABLE[j]<0)
AVAILABLE[j]=0;
}
}
for (i=0;i<M;i++)
for(j=0;j<N;j++)
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
showdata();
bank();
}
6 调试分析：
输出结果如下图所示：
当输入进程数和资源种类数及总资源量、所需最大资源数量Max和已分配资源量时，系统调用后showdata（）函数，显示现在系统的资源分配情况。当输入需要申请的进程号和其所需的资源数目时，系统调用bank()函数，在进行安全性检验，若此时系统安全，则系统为其分配资源，若此时系统没有通过安全性检验，则显示提示语句，恢复系统原来的资源分配情况，再重新进行选择。
下图所显示的程序运行结果所输入的数据都是有效的，无效数据的输入这里因为篇幅的原因没有给出。当输入的结果大于其范围时，程序会输出提示语句，此后再重新输入数据。
以课本P110银行家算法之例为例

资源不足时

资源足够时

资源足够且请求分配资源足够时

资源足够但请求资源不足时

7 心得体会
一周的操作系统课程设计，我学到了很多课本上没有的知识。想要完成模拟银行家算法的C语言程序，首先就是要彻底熟悉算法，了解算法的基本原理，才能开始着手程序设计在程序设计设计过程中，遇到了一些困难，通过向同学询问，翻阅资料等，问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和避免死锁的算法，并用C语言程序真正模拟出安全性检查和银行家算法过程，复习了之前所学C语言和数据结构的知识；在编程过程中虽然遇到很多困难，解决问题的过程中，同时也锻炼了我不怕困难，勇于迎接挑战的精神，为以后的挑战磨练了必胜的信心。
8 参考文献
[1] 计算机操作系统（第三版） 作者：汤子瀛