第一篇：计算机操作系统 课程设计报告 银行家算法
《计算机操作系统》
课 程 设 计 报 告
题 目： 银行家算法
班 级： XXXXXXXXXXXXXXXX 姓 名： XXM 学 号： XXXXXXXXXXXX 指导老师: XXXXXXXXXXXXXX 设计时间: XXXXXXXXXXXXXXX 一.设计目的
1、掌握死锁概念、死锁发生的原因、死锁产生的必要条件;
2、掌握死锁的预防、死锁的避免;
3、深刻理解死锁的避免：安全状态和银行家算法;
二.银行家算法
1.简介
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
2.数据结构
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].3.算法原理
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
三.算法实现
1.初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
2.银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转（3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
3.安全性检查算法
(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行（3)；否则，执行（4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
4.算法流程图
1)初始化算法流程图
2)银行家算法流程图：
3)安全性算法流程图：
4.代码（C语言）
#include
/*M个进程对N类资源最大资源需求量*/ int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系统可用资源数*/ int AVAILABLE[N]={10,5,7};/*M个进程对N类资源最大资源需求量*/ int ALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};
/*M个进程已经得到N类资源的资源量 */ int
NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*M个进程还需要N类资源的资源量*/ int Request[N]={0,0,0};
void main(){
int i=0,j=0;char flag;
void showdata();void changdata(int);void rstordata(int);int chkerr(int);showdata();enter:{
printf(“请输入需申请资源的进程号（从0到”);
printf(“%d”,M-1);
printf(“）:”);
scanf(“%d”,&i);} if(i<0||i>=M){
printf(“输入的进程号不存在，重新输入!n”);
goto enter;}
err:{
printf(“请输入进程”);
printf(“%d”,i);
printf(“申请的资源数n”);
printf(“类别: A B Cn”);printf(“ ”);
for(j=0;j { scanf(“%d”,&Request[j]); if(Request[j]>NEED[i][j]) { printf(“%d”,i); printf(“号进程”); printf(“申请的资源数 > 进程”); printf(“%d”,i); printf(“还需要”); printf(“%d”,j);printf(“类资源的资源量!申请不合理，出错!请重新选择!n”); goto err; } else { if(Request[j]>AVAILABLE[j]) { printf(“进程 ”); printf(“%d”,i); printf(“申请的资源数大于系统可用”); printf(“%d”,j); printf(“类资源的资源量!申请不合理，出错!请重新选择!n”); goto err; } } } } changdata(i);if(chkerr(i)){ rstordata(i); showdata();} else showdata(); printf(“n”); printf(“按'y'或'Y'键继续,否则退出n”); flag=getch(); if(flag=='y'||flag=='Y'){ goto enter; } else { exit(0);} } /*显示数组*/ void showdata(){ int i,j;printf(“系统可用资源向量:n”);printf(“***Available***n”);printf(“资源类别: A B Cn”);printf(“资源数目:”);for(j=0;j printf(“%d ”,AVAILABLE[j]);} printf(“n”);printf(“n”);printf(“各进程还需要的资源量:n”);printf(“******Need******n”);printf(“资源类别: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“号进程:”); for(j=0;j { printf(“ %d ”,NEED[i][j]); } printf(“n”);} printf(“n”);printf(“各进程已经得到的资源量: n”);printf(“***Allocation***n”);printf(“资源类别: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“号进程:”); /*printf(“:n”);*/ for(j=0;j { printf(“ %d ”,ALLOCATION[i][j]); } printf(“n”); } printf(“n”);} /*系统对进程请求响应，资源向量改变*/ void changdata(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];} } /*资源向量改变*/ void rstordata(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 chkerr(int s){ int WORK,FINISH[M],temp[M];int i,j,k=0; for(i=0;i WORK=AVAILABLE[j]; i=s; printf(“n”); while(i { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { printf(“系统不安全!本次资源申请不成功!n”); printf(“n”); return 1; } } } WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; temp[k]=i;k++;i=0; printf(“n”); printf(“经安全性检查，系统安全，本printf(”n“); printf(” 本次安全序列：n“);printf(”进程依次为“);for(i=0;i printf(”%d“,temp[i]); 次分配成功。n”);} else { i++;} } for(i=0;i printf(“-> ”);} printf(“n”);return 0;四．程序运行截图 0号进程申请资源{1,2,3},各向量发生变化 0和进程继续申请资源{2,2,0}，各向量变化 2号进程申请资源，由于NEED[2]={9,0,2},前两次申请不合理，系统处于不安全状态太。第三次2号申请资源向量为{1,0,2}，系统回到安全状态，并得出新的安全序列3-0-1-2-4。 五．心得体会 从此次的课程设计中，我收获很多。首先也是最重要的一点是对处理机调度与死锁有了深入的理解；其次，再次巩固了C语言编程。 在用C语言设计和编写银行家算法和安全性检查算法时遇到了一些困难都克服了。在使程序界面美观、能够持续循环运行时用了很多方法，花了比较多的时间。最后选择用goto语句控制，我觉得在此实验中比较好，代码阅读起来更加方便。 《操作系统》课程设计报告 课题： 银行家算法 专业 计算机科学与技术 学生姓名 班级 计算机 学号 指导教师 信息工程学院 一、实验要求和实验目的实验目的：本课程设计是学生学习完《操作系统原理》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 实验要求：从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：两人一组，每组从所给题目中任选一个（如自拟题目，需经指导教师同意），每个学生必须独立完成课程设计，不能相互抄袭，同组者文档不能相同；设计完成后，将所完成的工作交由指导教师检查；要求写出一份详细的设计报告。 二、设计内容： 课题一、编制银行家算法通用程序，并检测所给状态的系统安全性。 1）银行家算法中的数据结构： 可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj 类资源K个。 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。 1.分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资料当前已分配给没一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵存在如下关系： Need[i,j]= Max[i，j]- Allocation[i，j] 2）银行家算法 设Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Request[i，j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 三、设计思路 设计思路A、设计进程对各在资源最大申请表示及初值确定。B、设定系统提供资源初始状态。C、设定每次某个进程对各类资源的申请表示。D、编制程序，依据银行家算法，决定其申请是否得到满足。 四、详细设计 1、初始化：由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。 2、银行家算法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。 银行家算法的数据结构 假设有M个进程N类资源，则有如下数据结构: #define W #define R 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]; //请求资源个数 3.“安全性检测“算法 1)先定义两个变量,用来表示推算过程的数据.F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.J[n]=False表示推算过程中各进程是否假设“已完成“ 系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i]; 4、安全性检查算法 1)设置两个工作向量Work=AVAILABLE;FINISH 2)从进程集合中找到一个满足下述条件的进程，FINISH==false; NEED<=Work; 如找到，执行(3)；否则，执行(4) 3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION; Finish=true; GOTO 4)如所有的进程Finish= true，则表示安全；否则系统不安全。 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j 最大需求 尚需 P1 P2 P3 4 2 在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.银行家算法的数据结构.五、代码清单 #include #include #include #include #include #include const int MAX_P=20; const int MAXA=10; //定义A类资源的数量 const int MAXB=5; const int MAXC=7; typedef struct node{ int a; int b; int c; int remain_a; int remain_b; int remain_c; }bank; typedef struct node1{ char name[20]; int a; int b; int c; int need_a; int need_b; int need_c; }process; bank banker; process processes[MAX_P]; int quantity; //初始化函数 void initial() { int i; banker.a=MAXA; banker.b=MAXB; banker.c=MAXC; banker.remain_a=MAXA; banker.remain_b=MAXB; banker.remain_c=MAXC; for(i=0;i strcpy(processes[i].name,““); processes[i].a=0; processes[i].b=0; processes[i].c=0; processes[i].need_a=0; processes[i].need_b=0; processes[i].need_c=0; } } //新加作业 void add() { char name[20]; int flag=0; int t; int need_a,need_b,need_c; int i; cout< cout<<“新加作业“< cout<<“请输入新加作业名:“; cin>>name; for(i=0;i if(!strcmp(processes[i].name,name)){ flag=1; break; } } if(flag){ cout<<“错误,作业已存在“< } else{ cout<<“本作业所需A类资源:“; cin>>need_a; cout<<“本作业所需B类资源:“; cin>>need_b; cout<<“本作业所需C类资源:“; cin>>need_c; t=1; cout< if(need_a>banker.remain_a){ cout<<“错误,所需A类资源大于银行家所剩A类资源“< t=0; } if(need_b>banker.remain_b){ cout<<“错误,所需B类资源大于银行家所剩B类资源“< t=0; } if(need_c>banker.remain_c){ cout<<“错误,所需C类资源大于银行家所剩C类资源“< t=0; } if(t){ strcpy(processes[quantity].name,name); processes[quantity].need_a=need_a; processes[quantity].need_b=need_b; processes[quantity].need_c=need_c; quantity++; cout<<“新加作业成功“< } else{ cout<<“新加作业失败“< } } } //为作业申请资源 void bid() { char name[20]; int i,p; int a,b,c; int flag; cout< cout<<“要申请资源的作业名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ cout<<“该作业要申请A类资源数量:“; cin>>a; cout<<“该作业要申请B类资源数量:“; cin>>b; cout<<“该作业要申请C类资源数量:“; cin>>c; flag=1; if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){ cout<<“错误,所申请A类资源大于银行家所剩A类资源或该进程还需数量“< flag=0; } if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){ cout<<“错误,所申请B类资源大于银行家所剩B类资源或该进程还需数量“< flag=0; } if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){ cout<<“错误,所申请C类资源大于银行家所剩C类资源或该进程还需数量“< flag=0; } if(flag){ banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processes[p].a+=a; processes[p].b+=b; processes[p].c+=c; cout<<“为作业申请资源成功“< } else{ cout<<“为作业申请资源失败“< } } else{ cout<<“该作业不存在“< } } //撤消作业 void finished() { char name[20]; int i,p; cout< cout<<“要撤消作业名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ banker.remain_a+=processes[p].a; banker.remain_b+=processes[p].b; banker.remain_c+=processes[p].c; for(i=p;i processes[i]=processes[i+1]; } strcpy(processes[quantity-1].name,““); processes[quantity-1].a=0; processes[quantity-1].b=0; processes[quantity-1].c=0; processes[quantity-1].need_a=0; processes[quantity-1].need_b=0; processes[quantity-1].need_c=0; quantity--; cout<<“撤消作业成功“< } else{ cout<<“撤消作业失败“< } } //查看资源情况 void view() { int i; cout< cout<<“银行家所剩资源(剩余资源/总共资源)“< cout<<“A类:“< cout<<“ B类:“< cout<<“ C类:“< cout< if(quantity>0){ for(i=0;i cout<<“作业名:“< cout<<“A类:“< cout<<“ B类:“< cout<<“ C类:“< cout< } } else{ cout<<“当前没有作业“< } } //显示版权信息函数 void version() { cout< cout<<“ 银行家算法 “< cout< } void main() { int chioce; int flag=1; initial(); version(); while(flag){ cout<<“1.新加作业 2.为作业申请资源 3.撤消作业“< cout<<“4.查看资源情况 0.退出系统“< cout<<“请选择:“; cin>>chioce; switch(chioce){ case 1: add(); break; case 2: bid(); break; case 3: finished(); break; case 4: view(); break; case 0: flag=0; break; default: cout<<“选择错误“< } } } 六、使用说明 运行环境C-FREE4.0，新建任务。将编制好的代码输入此运行环境中。 按F5：出现如上图所示窗口。按照提示，新建一个作业：wujun。为作业分配资源，A：3；B：4；C：5。输入2，为作业分配资源。三种资源的数量分配分别为:A:3;B:5;C:4。输入4，查看资源情况。出现出错提示，所申请的B类资源超过银行家所剩B类资源或作业申请资源失败。输入0，退出系统。 重新加入一个作业：wujun1.并为作业分配资源分别为A:3;B:3;C:3，为该作业分配资源A:3;B:2;C:2.输入4查看资源情况。 显示输出，银行家算法所剩资源（剩余资源、总共资源）。 七、实验心得 八、参考文献 汤子瀛等.计算机操作系统.西安电子科技大学出版社.2001年5月 蒋静 徐志伟.操作系统原理•技术与编程『M』.北京:机械工业出版社,2004 实验四 死锁 一、实验目的 当系统的总资源数m小于或等于所有进程对对资源的最大需求时，就可能产生 死锁。死锁会引起计算机系统的瘫痪。银行家算法是在实现资源分配时避免死锁的一个著名算法，该算法是在能确保系统处于安全状态时才把资源分配给申请者。通过本实验使学生能进一步理解死锁的概念，并能选择一个算法来避免死锁。 二、实验题目 系统中有m个同类资源被n个进程共享，每个进程对资源的最大需求数分别为S1, S2,…,Sn，且 Max(Si)<=m,(i=1,2,…n)。进程可以动态地申请资源和释放资源。编写一个程序，现银行家算法，当系统将资源分配给某一进程而不会死锁时，就分配之。否则，推迟分配，并显示适当的信息。 三、数据结构 主要数据结构: Struct aa { void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 }； 四、银行家算法的流程图 开始初始化资源类数c=3，进程数t=5初始化Available[c]，Max[t][c]，Allocation[t][c]，Need[t][c]，Request[c]输入进程数iInt f=0f 五、源代码 #include void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 //定义初始化数组 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用户选择的进程号 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化数据如下：”< cout<<“试分配完成!”< cout<<“需要继续实验吗?（y-继续 n终止）”;} else if(ch=='N'||ch=='n'){ cout<<“感谢您的使用，祝您愉快!”< void Print(){ int i,j;cout<<“ 进程个数 ： ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全检测函数 void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三类资源A B C，一条进程下面的安全性检测只检测了A类。如果A类通过了，那么还要判断B类，C类。否则不用 { for(i=0;i } i=s;//s传递进来赋给i，s是用户输入的进程号（有主函数里的in传递进来）while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、执行结果： 七、实验总结 通过本次实验了解到用银行家算法来预防死锁是可靠的，但也是非常保守的，因为它限制了进程对资源的存取，从而降低了进程的并发运行程度。死锁检测并不限制进程对资源的申请，只要有，就分配，但这也可能造成死锁。但由于死锁并不是经常发生的，故大大提高了系统运行的效率。 总之，通过本实验，使我进一步加深理解和掌握银行家算法。 操作系统课程设计 （银行家算法的模拟实现） 一、设计目的 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类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： ①如果Requesti[j]<=Need[i,j]，便转向步骤②；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。 ②如果Requesti[j]<=Allocation[i,j]，便转向步骤③；否则表示尚无足够资源，Pi需等待。 ③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。 Available[j]=Available-Requesti[j]； Allocation[i,j]=Allocation[i,j]+Requesti[j]； Need[i,j]=Need[i,j]-Requesti[j]； ④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，已完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。 （2）安全性算法 系统所执行的安全性算法可描述如下： ①设置两个向量：一个是工作向量Work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=Available；另一个是Finish；它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true； ②从进程集合中找到能满足下述条件的进程： 一是Finish[i]==false；二是Need[i,j]<=Work[j]；若找到，执行步骤③，否则，执行步骤④； ③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]=Work[j]+Allocation[i,j]； Finish[i]=true； go to step②； ④如果所有进程的 Finish[i]==true都满足，则表示系统处于安全状态，否则系统处于不安全状态。 五、设计思路 1、进程一开始向系统提出最大需求量； 2、进程每次提出新的需求（分期贷款）都统计是否超出它事先提出的最大需求量； 3、若正常，则判断该进程所需剩余量（包括本次申请）是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。 六、程序运行调试结果 1、程序初始化 2、检测系统资源分配是否安全结果 七、小结 “银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过程中我们遇到过许多问题也学到了很多东西。通过这周的课程设计，我加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。并且在编程时将主要的操作都封装在函数中，这样使程序可读性增强，使程序更加清晰明了。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考了很多网络资料也参考了一些别人写的的程序综合这些算法思想和自己的思路对程序做了很好的设计方式对一些算法的优越性等也作了一些考虑。当然，在编写和调试过程中我遇到了许多的问题，通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多，相信在今后的生活中也有一定帮助。 附：程序源代码： #include int 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 for(j=0;j scanf(“%d”,&max[i][j]);//输入已知进程最大资源需求量 printf(“请输入Allocation矩阵:n”);for(i=0;i for(j=0;j scanf(“%d”,&allocation[i][j]);//输入已知的进程已分配的资源数 for(i=0;i for(j=0;j need[i][j]=max[i][j]-allocation[i][j];//根据输入的两个数组计算出need矩阵的值 printf(“请输入Available矩阵n”);for(i=0;i scanf(“%d”,&available[i]);//输入已知的可用资源数 print();//输出已知条件 check();//检测T0时刻已知条件的安全状态 if(r==1)//如果安全则执行以下代码 { do{ q=0;p=0;printf(“n请输入请求资源的进程号(0~4)：n”); for(j=0;j<=10;j++) { scanf(“%d”,&i); if(i>=no1) { printf(“输入错误，请重新输入：n”); continue; } else break; } printf(“n请输入该进程所请求的资源数request[j]:n”); for(j=0;j scanf(“%d”,&request[j]); else //请求满足条件 { for(j=0;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]+=request[j]; need[i][j]=need[i][j]-request[j];//系统尝试把资源分配给请求的进程 } print(); check();//检测分配后的安全性 if(r==0)//如果分配后系统不安全 { for(j=0;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”); //判断是否继续进行资源分配 for(j=0;j if(p) printf(“请求资源超过该进程资源需求量，请求失败！n”);else { for(j=0;j if(request[j]>available[j])q=1;//判断请求是否超过可用资源数 if(q) printf(“没有做够的资源分配，请求失败！n”); c=getche(); }while(c=='y'||c=='Y');} } void check()//安全算法函数 { int k,f,v=0,i,j;int work[m],a[m];bool finish[m];r=1;for(i=0;i finish[i]=false;// 初始化进程均没得到足够资源数并完成for(i=0;i k=no1;do{ for(i=0;i { if(finish[i]==false) { f=1; for(j=0;j if(need[i][j]>work[j]) f=0; if(f==1)//找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i;//记录安全序列号 for(j=0;j work[j]+=allocation[i][j];//释放该进程已分配的资源 } } } k--;//每完成一个进程分配，未完成的进程数就减1 }while(k>0);f=1;for(i=0;i if(finish[i]==false) { f=0; break; } } if(f==0)//若有进程没完成，则为不安全状态 { printf(“系统处在不安全状态！”); r=0;} else { printf(“n系统当前为安全状态，安全序列为：n”); for(i=0;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”); （程序结束） 课程设计报告书 课程名称： 操作系统原理 题 目： 编程序模拟银行家算法 系 名： 信息工程系 专业班级： 软件 姓 名： 学 号： 指导教师: 2013年 X 月 X 日 学院信息工程系 课 程 设 计 任 务 书 课程名称： 操作系统原理课程设计 指导教师： 班级名称： 软件 开课系、教研室： 软件与信息安全 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 编程序模拟银行家算法 2、课程设计内容 本课程设计要求在Linux操作系统，GCC编译环境下开发。 银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 3、设计报告撰写格式要求： 1设计题目与要求 设计思想 3系统结构 数据结构的说明和模块的算法流程图 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 自我评价与总结 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 三、课程设计步骤及时间进度和场地安排 本课程设计将安排在第15周,教育技术中心。具体安排如下： 第一天 下发任务书，学生查阅资料 第二天 系统设计和原型开发 第三，四天 系统功能实现 第五天 系统调试 测试 打包和验收 四、课程设计考核及评分标准 课程设计考核将综合考虑学生考勤和参与度，系统设计方案正确性，系统设计和开发效果以及课程设计报告书的质量。具体评分标准如下： 设置六个评分点 （1）设计方案正确，具有可行性、创新性； 25分 （2）系统开发效果较好； 25分 （3）态度认真、刻苦钻研、遵守纪律； 10分 （4）设计报告规范、课程设计报告质量高、参考文献充分 20分 （5）课程设计答辩概念清晰，内容正确 10分 （6）课程设计期间的课堂考勤、答疑与统筹考虑。 10分 按上述六项分别记分后求和，总分按五级记分法记载最后成绩。 优秀（100～90分），良好（80～89分），中等（70～79分），及格（60～69分），不及格（0～59分） 1.题目要求与实验目的1.1 实验目的： 1.1.1进一步理解利用银行家算法避免死锁的问题； 1.1.2在了解和掌握银行家算法。 1.1.3理解和掌握安全序列、安全性算法 1.2 设计题目: 编程序模拟银行家算法 1.3 要求 ： 本实验要求用用 c/c语言在Linux 操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 1.4 实验内容 ： 1.4.1编写安全性算法； 1.4.2编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。 设计思想 将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。 用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 3.需求分析 3.1问题描述：利用银行家算法模拟计算机系统分配资源的过程。 3.2要求： 3.2.11、以课本例题中数据为例，模拟资源分配过程。 3.2.2、系统中资源种类，各类资源数目，进程申请资源数目可任意输入，模拟资源分配过程。 4.系统结构 初始化函数init（）开始 输入进程的数目m 输入资源种类n 输入每个进程最多所需的各种资源数 输入每个进程分配的资源数 输入各个资源现有数目 初始化函数init（）结束 输入提示： 输入有误重新输入 图 5.数据结构的说明和模块的算法流程图 5.1 数据结构： ①可利用资源向量 Available 是个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果 AvailablejK，则表示系统中现有 Rj 类资源 K 个。 ②最大需求矩阵 Max 这是一个 n×m的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 MaxijK，则表示进程 i 需要 Rj 类资源的最大数目为 K。 ③分配矩阵 Allocation 这也是一个 n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 AllocationijK，则表示进程 i 当前已分得 Rj 类资源的数目为 K。 ④需求矩阵 Need。 这也是一个 n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果NeedijK，则表示进程 i 还需要 Rj 类资源 K 个，才可以完成其任务。 5．2 程序流程图： ①、系统主要过程流程 预分配 安全？ 实际分配打印输出 退出系统 Request[i]>Available[i]? Request[i]>need[i]? 提出申请 打印输出此时刻资源分配情况 进入系统 输入： 1.继续分配 2.退出 进入初始化 ②、安全性算法流程图 调用safty()函数 Work[]=Available[],Finish[]=False Need[]<=work[]且Finsh[]=Falsse? Work[]=work[]+Alloccation[],Finish[]=Ture 所有进程的Finsh[]=Ture? 实际分配输出安全序列并打印出 输出提示系统不安全 调用结束 用户手册 6.1 首先在终端中使用 vi 编辑器建立 c的源文件 6.2 然后使用 gcc 编辑器编译生成可执行文件 6.3 使用命令./当前名字，来执行 7.运行结果和结果分析 7．1 运行结果： 申请成功如图 2，申请失败如图 3： 图 申请金额在需求范围之内同意 图 申请金额在需求范围之外拒绝 7.2 结果分析 首先是自己定义 个用户所需的金额数，银行可以给用户贷款的总金额数是100，用户 Id 号的范围是在0 到 4，超过 之后的id 请求贷款，会显示拒绝提示信息，每个客户的贷款数量必须是在之前定义的范围之内，如果超出，也会出现错误提示，只有在规定的用户 id 和在客户所要求金额的范围之内请求，才会给予贷款，并且输出安全序列号。 8.自我评价与总结 一周的课程设计结束了。在这一周里，我收获很多，以前都是在自己的教室由我们自己的老师进行讲课，这次学校没有这样做，而是请的校外的老师给我们做课程设计，让我们体会一下真正的公司是怎样做业务的。在这一周里我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。 课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。这次的课程设计使我进一步了解了调度与死锁的问题。以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。 经过本周的课程设计，我对操作系统的掌握又进了一步，收获了很多知识。，终于我了由于对 c 语言不够熟练，在试验过程中，进行了反复的修改和调试，解银行家算法的基本原理，并且在此次的课程设计中我又复习了一下 c 语言，加深了对它的了解，而且在课程设计的过程中我们同样学会了如何简单的操作与使用 Linux 操作系统，学习到了许多 Linux 操作系统中常用的一些密令。 这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列看系统是否安全.再利用安全性算法检查此时系统是否安全。 操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。 通过这次实验，我体会到银行家算法的重要性，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我来学习借鉴。 附录： 主要源程序 参考文献 [1] 张尧学主编．计算机操作系统教程（第三版）．北京:清华大学出版社，2006 [2] 张尧学编．计算机操作系统教程（第三版）习题解答与实验指导．北京:清华大学出版社，2006 [3] 汤子瀛主编．计算机操作系统（第三版）．西安:西安电子科技大学出版社，2001 [4] 张坤等编．操作系统实验教程．北京:清华大学出版社，2008 [5] 张丽芬等编．操作系统实验教程．北京:清华大学出版社，2006 [6] 屠祁等编.操作系统基础（第三版）．北京:清华大学出版社，2000 [7] 冯耀霖等编.操作系统.西安:西安电子科技大学出版社，2001 [8] 左万历．计算机操作系统教程（第二版）．北京：高等教育出版社，2004 [9]谭浩强.《C语言程序设计》.北京：清华大学出版社2003 [8] 庞丽华.《操作系统原理》（第四版）.北京.华中科技大学出版社 2002 设计过程中质疑（或答辩）记载： 1.银行家算法的主要思想是什么？ 答：一个进程进入系统时分配资源之前,判断系统是否是安全的，即看它所请求的资源是否大于它的最大需求量，若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待。 2.银行家算法的主要问题是什么？ 答：要求每个进程必须事先知道资源的最大需求量，而且，在系统运行过程中，考查每个进程对各类资源的申请需花费较多的时间。 3.在银行家算法中各个资源存在什么关系？ 答：该进程所需要的资源数NEED[m][n]=MAX[m][n](该进程所需要的最多的资源数)-----ALLOCATION[m][n](该进程所占有的资源数) 指导教师评语： 签名： ****年**月**日第二篇：银行家算法《操作系统》课程设计报告
第三篇：操作系统银行家算法实验报告
第四篇：操作系统课程设计(银行家算法的模拟实现)
第五篇：操作系统课程设计编程序模拟银行家算法
点击咨询 