操作系统实验报告
银行家算法的实现
学 生: 杨康宁 学 号: 201006090128 学 院: 电气与信息工程学院 系 别: 计算机系 专 业: 网络工程 实验时间: 2012 年 报告时间: 20xx年1月1日
实验:
实验二 银行家算法的实现
1、实验目的:
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。通过编写一个模拟动态资源分配的银行家算法程序,帮助学生进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法。
2、实验内容:
银行家算法的实现。
3,实验题目:
银行家算法的实现过程
源程序名:yinhangjiasuanfa.cpp
执行程序名:yinhangjiasuanfa.exe
4,程序流程图:
1. 主函数void main()函数流程图
2. int check_distribution(int* p,int k)
流程图
3.银行家算法int check_safe()流程图
4.输出函数print()流程图
5,源程序:
#include<stdio.h>
#define N 5 //进程个数
#define M 3 //资源种类数
void print();
int check_safe();
int check_distribution(int* p,int k);
char processnema[N]; //进程名
int Request[M]; //请求向量
int Finish[N]; //标记某一个进程是否可以执行
int Work[N][M]; //初始为Available[][],随寻找安全序列而变化,防止安全序列未找到而丢了初始状态的值
int Available[M]; //资源清单——系统中现有各资源空闲个数
int Work_Allocation[N][M];
int Max[N][M]; //最大需求矩阵——每个进程对各类资源的最大需求数 int Allocation[N][M];//分配矩阵——系统给每个进程已分配的各类资源数 int Need[N][M]; //需求矩阵——每个进程还需要每种资源的个数 int sequence[N]={0};//存放安全序列号
void main()
{
int i=0,j=0,k=0;//记录申请资源的进程的序列号
int flag=0; //标记输入的进程名是否存在
int safe=0; //标志系统是否出于安全状态,0表示不安全,1表示安全
int distribution=0; //标志是否可以进行试分配0表示可以,1表示不可以 char flag1; //标记是否有进程申请资源
//Need[N][M]=Max[N][M]-Allocation[N][M];
char name; //要请求资源的进程名
printf("~~~~~~~~~~~银行家算法~~~~~~~~~~~~~\n");
printf(" 请分别初始化各矩阵信息 \n");
printf("*请输入各进程的进程名\n"); //进程名连续输入
for(i=0; i<N; i++)
{
}
printf("请输入现有各资源空闲个数\n");
for(i=0; i<M; i++)
{
}
printf("请分别输入每个进程对各类资源的最大需求数\n");
for(i=0; i<N; i++)
{
}
printf("请分别输入系统给每个进程已分配的各类资源数\n");
for(i=0; i<N; i++) for(j=0; j<M; j++) { } scanf("%d",&Max[i][j]); scanf("%d",&Available[i]); scanf("%c",&processnema[i]);
{
}
//printf("请分别输入每个进程还需要每种资源的个数\n"); for(i=0; i<N; i++)
{
}
printf("信息输入完毕\n");
for(i=0; i<N; i++)
{
}
print();
safe=check_safe(); //检查初始状态是否安全
if(0 == safe)
{
}
else if(1 == safe)
{
}
while(1)
{
safe=0; printf("是否有进程请求系统资源...? (Y/N) \n"); getchar(); printf("系统处于安全状态,可以为进程分配资源。\n"); printf("系统现处于不安状态,不能为进程分配资源,进入死锁状态。。。\n"); exit(0); sequence[i]=i; for(j=0; j<M; j++) { } Need[i][j]=Max[i][j]-Allocation[i][j]; for(j=0; j<M; j++) { } scanf("%d",&Allocation[i][j]);
flag1=getchar(); //scanf("%c",&flag1); if('Y' == flag1 || 'y' == flag1) { } else if('N' == flag1 || 'n' == flag1) { } else if('N' != flag1 && 'Y' != flag1 && 'n' != flag1 && 'y' != flag1) printf("进程执行完毕,退出系统。\n"); break; printf("请输入进程名:"); while(1) { } scanf("%c",&name); for(i=0; i<N; i++) //检查进程名输入是否正确 { } getchar();//将在此之前的一个回车接收了,不然会影响输入 if( flag != 1 )//进程名输入不合法 { } else { } break;//进程名输入合法,则执行下面操作 printf("你输入的进程不存在,请重新输入:"); continue; if(name == processnema[i] ) { } flag=1; //输入的进程名存在 k=i; break;//找到申请资源的进程序列号跳出 getchar(); //name=;
{ { } for(i=0; i<M; i++) { } distribution=check_distribution(Request,k); //检查是否可以试分配 if(1 == distribution) { safe=check_safe(); //可以试分配,则求安全序列 if(1 == safe) //试分配成功 { } else //试分配失败 printf("试分配成功,可以为该进程分配资源。\n"); //distribution //是否给申请资源的进程分配资源 for(i=0; i<M; i++) { } printf("分配后各资源数量如下:\n"); print(); printf("分配成功!\n"); printf("系统剩余资源数各为: "); for(i=0; i<M; i++) { } printf("\n"); continue; printf("%d ",Available[i]); Allocation[k][i]=Allocation[k][i]+Request[i]; //为进程分Need[k][i]=Need[k][i]-Request[i]; scanf("%d",&Request[i]); printf("你的输入有误,请重新输入: "); continue; printf("请输入该进程请求各类资源的数量\n"); //*****************************************检查 配资源后修改该进程的有关资源数
}
} } } printf("试分配失败,有可能进入死锁状态,请等待。。。\n");//未求continue; 出安全序列 else //试分配失败 { } printf("该进程申请的资源太多,无法分配,请等待。。。\n"); continue;
void print()
{
int i,j;
printf(" 资源 Work Need\tAllocation\tWork+Allocation\t Finish\n\n");
printf(" 进程名 A B C A B C \t A B C \t A B C\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
for(i=0; i<N; i++)
{
printf(" %c ",processnema[sequence[i]]); for(j=0; j<M; j++) { } printf(" "); for(j=0; j<M; j++) { } printf(" "); for(j=0; j<M; j++) { printf("%d ",Work[sequence[i]][j]); printf("%d ",Need[sequence[i]][j]);
}
} } printf("%d ",Allocation[sequence[i]][j]); printf(" "); for(j=0; j<M; j++) { } printf(" "); printf("%d",Finish[i]); printf("\n\n"); printf("%d ",Work_Allocation[sequence[i]][j]);
int check_distribution(int* p,int k) {
int i=0;
int safe1=0,safe2=0;
for(i=0; i<M; i++)
{
}
if(M == safe1 && M == safe2) {
}
else
{
}
}
int check_safe() //检查是否安全,求安全序列 return 0; return 1; if(p[i] <= Need[k][i]) { } if(p[i] <= Available[i]) { } safe2=safe2+1; safe1=safe1+1;
{
int i=0,j=0,k=0,m=0;
int finish=0;
for(i=0; i<M; i++)
{
}
for(m=0; m<N; m++)//N个进程最多找N趟 {
值
}
} for(i=0; i<N; i++)//检查是否所有进程都执行完了 { } if(1 == finish) { } break; finish=finish*Finish[i]; } if(1 != finish) { finish=1; for(i=0; i<N; i++) //找Need小于Work的进程 { if(0 == Finish[i] && Need[i][0] <= Work[k][0] && Need[i][1] <= { sequence[k]=i;//找到一个满足条件的进程,记录其序号 k++; Finish[i]=1; //执行该进程 for(j=0; j<M; j++) { Work[k][j]=Work[k-1][j]+Allocation[i][j]; //更新WOrkWork[k][i]=Available[i];//-Request[i];//初始化WOrk[][]矩阵 Work[k][1] && Need[i][2] <= Work[k][2])
} } else { } continue; //else //{ // break; // }
for(i=0; i< N; i++)
{
}
for(i=0; i<M; i++)
{
}
return finish;
}
/*
输入进程信息:
请分别输入每个进程对各类资源的最大需求数 7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
请分别输入系统给每个进程已分配的各类资源数 0 1 0
2 0 0
3 0 2 Available[i]=Available[i]-Request[i]; } for(j=0; j<M; j++) { Work_Allocation[i][j]=Work[i][j]+Allocation[i][j];
2 1 1
0 0 2
请分别输入每个进程还需要每种资源的个数
7 4 3
1 2 2
6 0 0
0 1 1
4 3 1
信息输入完毕
*/
6运行结果和程序调试:
函数的书写分模块进行,每完成一个模块进行调试、测试直到该函数运行无误。
1、进程信息的输入与输出调试
(1) 能正确无误的输入进程名向量processnema[N],输入系统现有各类资源数量Available[M]向量,输入每个进程对各类资源的最大需求数Max[N][M]矩阵,输入系统给每个进程已分配的各类资源数Allocation[N][M]矩阵。输出程序过程如下图所示:
(2) 在进程信息输入中没有出现多大问题,在进程信息输出时,按设计要求输出的话应该是一个表格形式,在输出函数设计最初,由于有些部分分割或空格没有填充好,导致输出表格比较乱,没有达到设计要求,经过修改后输出形式才符合了设计要求,进程信息输入完成后,初始状态各进程信息输出如下:
2、进程请求资源输入出错提示信息处理
在系统询问是否有进程申请资源时,如果有输入信息出错,系统会给与出错提示,如果输入信息正确则系统将继续执行下面操作,执行如下:
3、 判断是否可以试分配函数int check_distribution(int* p,int k) 在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件Request []<=need[]或Request []<=available[],如果不满足将打出提示信息,如果满足,则返回1继续执行下面程序,执行结果如下:
4、求安全序列函数
int check_safe()
如果申请资源的进程申请的资源数目满足试分配条件,则再用这个函数来求试分配后的安全序列,如果可以求出安全序列,则说明这次分配不会使系统进入不安全状态,正式将资源分配给该进程,修改系统资源信息。如果求不出安全序列,说明这次分配后系统会进入不安全状态,不能给该进程分配资源,系统恢复初始状态,打印出提示信息,执行结果如下:
7,总结和心得:
经过几天的操作系统课程设计,我学习到了很多东西。首先,这次课程设计的内容是银行家算法,我用的编程工具是VC++,语言使用的是C语言,目的是模拟实现处理机避免死锁;其次,通过模拟实现算法,我更进一步地学习了C语言,这使我的编程能力得到了提高。当然最重要的是我更深地理解了对于死锁
的避免,死锁是会影响并发执行的,是操作系统最需要解决得问题。解决死锁,
我们要检测一个安全状态,虽然并非所有的不安全状态都会产生死锁状态,但系统进入不安全状态时,便可能进而进入死锁状态后,当系统在进行资源管理时,如果对进城申请的资源分配不当,可能会使系统进入死锁状态,因而后面到来的进程也无法顺利执行。银行家算法中,要对当前申请资源的进程申请资源的数目进行判断,如果可以试分配,则试求出一个安全序列,如果可以求出,则说明给这个进程分配资源后系统不会进入不安全状态,将该进程申请的资源分配给他,若求不出安全序列,则说明将资源分配给该进程后系统会进入不安全状态,所以就使该进程进入阻塞状态,等待以后可以分配资源时再执行该进程,然后系统继续服务其它进程。通过这样一个过程,可以有效避免系统进入死锁状态。反之,只要系统处于安全状态,系统便可避免进入死锁状态。因此,避免死锁的实质在于——如何使系统不进入不安全状态。很明显这些概念在操作系统上是非常重要的东西,我相信这对我以后的学习也有很大的帮助。