操作系统原理课程设计 指导老师：
院 系：
班 级：
学 号：
姓 名：
同 组 者：
时 间：——银行家算法 周敏 唐洪英 杨宏雨 杨承玉 傅由甲 黄贤英 计算机学院计算机科学与技术系 0237-6 2002370608 朱 应 瑜 陈 源 2005/12/22---2005/12/28
目录
一、 设计目的 ..................................................................................................................... 3 二、 设计内容 ..................................................................................................................... 3
三、银行家算法的基本思想 ........................................................................................... 3
（一）死锁 ............................................................................................................................... 3
（二）系统安全状态 ............................................................................................................... 4
（三）银行家算法避免死锁 ................................................................................................... 4
1、银行家算法中的数据结构 ......................................................................................... 4
2、银行家算法 ................................................................................................................. 4
3、安全性算法 ................................................................................................................. 5
四、系统模块间关系图 ..................................................................................................... 6
五、系统子模块结构图 ..................................................................................................... 7
六、输入、输出数据 ........................................................................................................... 9
七、源程序及系统文件使用说明 .............................................................................. 12
（一）源程序 ......................................................................................................................... 12
（二）系统文件使用说明 ..................................................................................................... 25
八、心得体会 ......................................................................................................................... 26
九、参考文献 ......................................................................................................................... 26
银行家算法
一、 设计目的
本课程设计是学习完《计算机操作系统》课程后，进行的一次全面的综合训练。通过这次课程设计，让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。
二、 设计内容
编制银行家算法通用程序，并检测所给状态的系统安全性。
三、银行家算法的基本思想
（一）死锁
在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
产生死锁的原因可归结为如下两点：
（1）竞争资源。
（2）进程间推进顺序非法。
死锁的发生必须具备下列四个必要条件：
（1）互斥条件。
（2）请求和保持条件。
（3）不剥夺条件。
（4）环路等待条件。
（二）系统安全状态
避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。 所谓安全状态，是指系统能按某种进程顺序（P1，P2，……，Pn）（称<P1，P2，……，Pn>序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
（三）银行家算法避免死锁
为实现银行家算法，系统中必须设置若干数据结构。
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、银行家算法
设Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
（1）如果Request[i，j]<= Need[i，j]，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Request[i，j]<= Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j]= Available[j]- Request[i，j]；
Allocation[i，j]= Allocation[i，j]+ Request[i，j]；
Need[i，j]= Need[i，j]- Request[i，j]；
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3、安全性算法
系统所执行的安全性算法可描述如下：
（1）设置两个向量：①工作向量Work：它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。
（2）从进程集合中找到一个能满足下述条件的进程：
①Finish[i]=false；②Need[i，j] <= Work[j]；若找到，执行步骤（3），否则，执行步骤（4）。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j]= Work[i]+ Allocation[i，j]；
Finish[i]=true；
go to step 2；
（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
四、系统模块间关系图
五、系统子模块结构图
六、输入、输出数据
执行程序，输入数据之前：
现在请分别输入对应的进程号、资源号和个数：
现在请选择1或2：
选择了1后：
因为未通过安全性测试，不予以分配，所以一切数据均无变化。点击了1后：
现在又请分别输入其它需要测试的进程号、资源号和个数：
现在请选择1或2：
选择了1后：
因为通过了安全性测试，并找到了一个安全序列，所以分配成功，有关数据均要发生变化。（请对照前后数据及所输入的数据进行比较）
? 资源类型1的可利用资源由4变成3；
? 进程2的资源类型1的已分配资源由2变成3；
? 进程2的资源类型1的已需求资源由1变成0；
点击了1后：
七、源程序及系统文件使用说明
（一）源程序
#include "stdafx.h"
#include<iostream.h>
#include<fstream.h>
#include<windows.h>
#include<stdlib.h>
#define MAX_PROCESS 32 //最大进程数 #define MAX_COURCE 64 //最大资源类别 int MAX_FACT_PROCESS; //实际总进程数 int MAX_FACT_COURCE; //实际资源类别数 int Available[MAX_COURCE]; //可利用资源向量 int Max[MAX_PROCESS][MAX_COURCE]; //最大需求矩阵 int Allocation[MAX_PROCESS][MAX_COURCE]; //分配矩阵 int Need[MAX_PROCESS][MAX_COURCE]; //需求矩阵 int Request_PROCESS; //发出请求的进程 int Request_COURCE; //被请求资源类别 int Request_COURCE_NEMBER; //请求资源数 bool loop = true;
struct COMP
{
};
int flag=0;
第 12 页 共 26 页 int value; int num; int next;
void Read_Initiate(void) //读入初始化文档 {
}
第 13 页 共 26 页 ifstream infile("Initiate.txt"); if(!infile) { } cout<<"开始读入初始化文档"<<endl; int ch; int Array[MAX_PROCESS*MAX_COURCE*2]; int num=0; while(infile>>ch) //初始化文档的第一个数字为长度 Array[num++]=ch; cout<<"不能打开输入文件:"<<"Initiate.txt"<<endl; exit(1); num=0; MAX_FACT_COURCE=Array[num++]; for(int j=0;j<MAX_FACT_COURCE;j++) Available[j]=Array[num++]; MAX_FACT_PROCESS=Array[num++]; for(int i=0;i<MAX_FACT_PROCESS;i++) { } infile.close(); for(int j=0;j<MAX_FACT_COURCE;j++) Max[i][j]=Array[num++];
void Write_Initiate(void) //写入初始化文档(分配资源) {
ofstream outfile("Initiate.txt"); if(!outfile) { } int Array[MAX_PROCESS*MAX_COURCE*2]; int num=0; Array[num++]=MAX_FACT_COURCE; for(int i=0;i<MAX_FACT_COURCE;i++) Array[num++]=Available[i]; cout<<"不能打开初始化文档："<<endl; exit(1); Array[num++]=MAX_FACT_PROCESS; for(i=0;i<MAX_FACT_PROCESS;i++) for(int j=0;j<MAX_FACT_COURCE;j++) Array[num++]=Max[i][j]; num=0; outfile<<Array[num++]<<" "; for(i=0;i<MAX_FACT_COURCE;i++) outfile<<Array[num++]<<" "; outfile<<endl<<Array[num++]<<endl; for(i=0;i<MAX_FACT_PROCESS;i++) { } int m_delay=3000; Sleep(m_delay);
第 14 页 共 26 页 for(int j=0;j<MAX_FACT_COURCE;j++) outfile<<Array[num++]<<" "; outfile<<endl;
}
outfile.close(); cout<<"修改初始化文档成功!"<<endl;
void Allocated_list(void) //读入已分配资源列表 {
}
void Set_Need(void) //设置需求矩阵 ifstream infile("Allocated_list.txt"); if(!infile) { } cout<<"开始读入已分配资源列表"<<endl; int ch; int num=0; int Array[MAX_PROCESS*MAX_COURCE]; while(infile>>ch) Array[num++]=ch; cout<<"不能打开输入文件:"<<"Allocated_list.txt"<<endl; exit(1); num=0; for(int i=0;i<MAX_FACT_PROCESS;i++) for(int j=0;j<MAX_FACT_COURCE;j++) Allocation[i][j]=Array[num++]; infile.close(); {
cout<<"设置需求矩阵"<<endl; for(int i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
}
void Write_Allocation(void) //修改资源分配列表(资源分配)
{
ofstream outfile("Allocated_list.txt");
if(!outfile)
{
cout<<"不能打开资源分配列表："<<endl;
exit(1);
}
for(int i=0;i<MAX_FACT_PROCESS;i++)
{
for(int j=0;j<MAX_FACT_COURCE;j++)
outfile<<Allocation[i][j]<<" ";
outfile<<endl;
}
int m_delay=3000;
Sleep(m_delay);
cout<<"修改资源分配列表成功!"<<endl;
outfile.close();
}
void Allocate_Source(void) //开始分配(已通过扫描和安全性检测) {
cout<<endl<<"开始给第"<<Request_PROCESS<<"个进程分"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl; Write_Initiate();
第 16 页 共 26 页 配第
}
Write_Allocation(); int m_delay=3000; Sleep(m_delay); cout<<endl<<"祝贺您，资源分配已成功!"<<endl;
bool Test_Safty() //安全性检测 {
cout<<endl<<"进入安全性检测!"<<endl; int Work[MAX_COURCE]; for(int i=0;i<MAX_FACT_COURCE;i++) { } bool Finish[MAX_PROCESS][MAX_COURCE]; for(i=0;i<MAX_FACT_PROCESS;i++) for(int j=0;j<MAX_FACT_COURCE;j++) Finish[i][j]=false; Work[i]=Available[i]; COMP Array[32]; for(i=0;i<MAX_FACT_PROCESS;i++) { Array[i].value=Need[i][Request_COURCE-1]; Array[i].num=i; } for(i=0;i<MAX_FACT_PROCESS;i++) for(int j=i+1;j<MAX_FACT_PROCESS;j++) { if(Array[i].value>=Array[j].value) { int t;
} } t=Array[j].value; Array[j].value=Array[i].value; Array[i].value=t; t=Array[j].num; Array[j].num=Array[i].num; Array[i].num=t; else continue; int m_delay=3000; Sleep(m_delay); if(Finish[Request_PROCESS-1][Request_COURCE-1]==false&&Need[Request_PROCESS-1][Request_COURCE-1]<=Work[Request_COURCE-1])
Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Request_PROCESS-1{ ][Request_COURCE-1];
第 18 页 共 26 页 } else { } Finish[Request_PROCESS-1][Request_COURCE-1]=true; cout<<"未通过安全性测试，不与以分配"<<endl; return false; for(i=0;i<MAX_FACT_PROCESS;i++) { if(Array[i].num==Request_PROCESS-1) continue;
if(Array[i].num!=Request_PROCESS-1&&Finish[Array[i].num][Request_COURCE-1]==false&&Need[Array[i].num][Request_COURCE-1]<=Work[Request_COURCE-1])
Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Array[i].num][Reques{ t_COURCE-1];
Finish[Array[i].num][Request_COURCE-1]=true;
} for(i=0;i<MAX_FACT_PROCESS;i++) { } cout<<endl<<"找到一个安全序列:"<<"P"<<Request_PROCESS<<"--->"; for(i=0;i<MAX_FACT_PROCESS;i++) { } cout<<endl<<"已通过安全性测试!"<<endl; Allocate_Source(); return true;
第 19 页 共 26 页 } if(Finish[i][Request_COURCE-1]==true) else { } cout<<"未通过安全性测试，不与以分配"<<endl; return false; continue; if(Array[i].num==Request_PROCESS) else cout<<"P"<<Array[i].num<<"--->"; continue;
}
bool RUN(void) //执行银行家算法
{
行cout<<"*************************************************"<<endl<<"点击1执!"<<endl<<"点击2退出!"<<endl<<"*************************************************"<<endl;
cin>>flag; if(flag==2) { } if(flag==1) { cout<<"开始扫描请求信息!"<<endl; int m_delay=3000; Sleep(m_delay); if(Request_COURCE_NEMBER>Need[Request_PROCESS-1][Request_COURCE-1]) { cout<<endl<<"第"<<Request_PROCESS<<"个进程请求第loop = false; exit(0); "<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
cout<<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!"<<endl;
} if(Request_COURCE_NEMBER>Available[Request_COURCE-1]) { cout<<endl<<"第"<<Request_PROCESS<<"
第 20 页 共 26 页 return false; 个进程请求第
"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
Available[Request_COURCE-1]=Available[Request_COURCE-1]-Request_COURCE_NE } else { cout<<"可是系统中尚无足够的资源,所以进入等待队列!!"<<endl; return false; MBER;
Allocation[Request_PROCESS-1][Request_COURCE-1]=Allocation[Request_PROCESS-1]
[Request_COURCE-1]+Request_COURCE_NEMBER;
Need[Request_PROCESS-1][Request_COURCE-1]=Need[Request_PROCESS-1][Request_COURCE-1]-Request_COURCE_NEMBER;
}
第 21 页 共 26 页 } } cout<<"扫描通过"<<endl; Sleep(m_delay); Test_Safty(); else { } return true; cout<<"输入错误,请重新输入!"<<endl; RUN();
void main(void)
{
cout<<"资源类型 "; for(i=0;i<MAX_FACT_COURCE;i++) { } cout<<endl; for(i=0;i<MAX_FACT_PROCESS;i++)
第 22 页 共 26 页 int tflag; int i; int j; char tch; while(loop) { Read_Initiate(); cout<<endl<<"资源个数："<<MAX_FACT_COURCE<<endl; cout<<"可利用资源"<<endl; cout<<"资源类型 "; for(i=0;i<MAX_FACT_COURCE;i++) { } cout<<endl; cout<<" "; for(i=0;i<MAX_FACT_COURCE;i++) cout<<Available[i]<<" "; cout<<i+1<<" "; cout<<endl<<"进程个数："<<MAX_FACT_PROCESS<<endl; cout<<i+1<<" ";
{ } int m_delay=3000; Sleep(m_delay); cout<<"读入成功"<<endl<<endl; Allocated_list(); cout<<"P"<<i+1<<": "; for(j=0;j<MAX_FACT_COURCE;j++) cout<<Max[i][j]<<" "; cout<<endl; cout<<"资源类型 "; for(i=0;i<MAX_FACT_COURCE;i++) { } cout<<endl; for(i=0;i<MAX_FACT_PROCESS;i++) { } Sleep(m_delay); cout<<"读入成功"<<endl<<endl; Set_Need(); cout<<"资源类型 "; for(i=0;i<MAX_FACT_COURCE;i++) {
第 23 页 共 26 页 cout<<i+1<<" "; cout<<"P"<<i+1<<": "; for(j=0;j<MAX_FACT_COURCE;j++) cout<<Allocation[i][j]<<" "; cout<<endl;
} cout<<i+1<<" "; cout<<endl; for(i=0;i<MAX_FACT_PROCESS;i++) { } Sleep(m_delay); cout<<"设置成功"<<endl; cout<<endl<<"请输入进程号("<<"1~"<<MAX_FACT_PROCESS<<"):"; cin>>Request_PROCESS; cout<<endl<<"请输入资源号("<<"1~"<<MAX_FACT_COURCE<<"):"; cin>>Request_COURCE; cout<<endl<<"请输入个数:"; cin>>Request_COURCE_NEMBER; cout<<endl<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"cout<<"P"<<i+1<<": "; for(j=0;j<MAX_FACT_COURCE;j++) cout<<Need[i][j]<<" "; cout<<endl; 类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
继 cout<<endl<<"读入成功"<<endl; RUN(); cout<<"*************************************************"<<endl<<"点击1续!"<<endl<<"其它则退出!"<<endl<<"*************************************************"<<endl;
}
第 24 页 共 26 页 } cin>>tflag; if(tflag!=1) loop = false;
（二）系统文件使用说明
银行家算法演示程序由一个程序文件和二个文本文件组成。其中Initiate.txt文件中保存的是：（1）当前资源的个数，（2）系统当前可用资源，（3）当前进程的个数，（4）系统当前已分配资源。
例子：
3
2 1 0
5
5 5 3
3 2 2
8 3 2
2 2 2
4 3 3
其中第一行的3表示有3类资源；第二行的2 1 0表示当前系统的可用资源：第一类资源为2，第二类资源为1，第三类资源为0；第三行的5表示有5个进程；从第四行开始，每一行表示一个进程的最大需求，如第四行的5 5 3，表示进程一的第一类资源最大需求为5，第二类资源最大需求为5，第三类资源最大需求为3。
Allocated_list.txt文件中保存的是每个进程的已分配资源。
例子：
0 1 0
3 2 2
3 0 2
2 1 1
0 0 2
如第一行0 1 0，表示进程一已分配第一类资源为0，已分配第二类资源为1，已分配第三类资源为0。
八、心得体会
通过为期一周的操作系统课程设计，让我在学习完《计算机操作系统》课程后，进行了一次全面的综合运用，让我更好地掌握了操作系统的原理及实现方法，加深了对操作系统基础理论和重要算法的理解，加强了动手能力。
我所做的题目是《银行家算法》，在完成过程中，我通过向老师和同学请教，已经完成了题目要求的所有功能。但是在此系统中仍然存在不足之处：输入、输出界面不能直观的反映情况，让使用者在不了解的情况下，感到束手无策。针对这样的缺陷，我编写了一份系统使用说明书来帮助使用者完成他们想要的功能。另一个不足之处是在产生出安全序列时，不能清楚看出安全序列是怎样产生出来的，这一切是系统默默执行的。
总之，在这次理论联系实际的学习过程中，我收获很多，知识的增长，能力的锻炼……在今后的学习生活中，我会继续努力，学以至用。
九、参考文献
1. 张尧学，史美林编著. 计算机操作系统教程（第二版）. 北京：清华大学出版社，2000
2. 汤子瀛，哲风屏，汤小丹编著. 计算机操作系统. 西安：西安电子科技大学出版社，2001