第一篇：操作系统课程设计实验报告-用C++实现银行家算法
操 作 系 统
实 验 报 告
(2)学院：计算机科学与技术学院 班级：计091 学号：姓名： 时间：2011/12/30
目 录
1.实验名称……………………………………………………3 2.实验目的……………………………………………………3 3.实验内容……………………………………………………3 4.实验要求……………………………………………………3 5.实验原理……………………………………………………3 6.实验环境……………………………………………………4 7.实验设计……………………………………………………4 7.1数据结构设计……………………………………………………………………4 7.2算法设计…………………………………………………………………………6 7.3功能模块设计……………………………………………………………………7 8.实验运行结果………………………………………………8 9.实验心得……………………………………………………9
附录：源代码（部分）…………………………………………………………………9
一、实验名称：
用C++实现银行家算法
二、实验目的：
通过自己编程来实现银行家算法，进一步理解银行家算法的概念及含义，提高对银行家算法的认识，同时提高自己的动手实践能力。
各种死锁防止方法能够阻止发生死锁，但必然会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁。本实验旨在了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生。
三、实验内容：
利用C++,实现银行家算法
四、实验要求：
1.完成银行家算法的设计
2.设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。
五、实验原理：
系统中的所有进程放入进程集合，在安全状态下系统收到进程的资源请求后，先把资源试探性的分配给它。之后，系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较，找出剩余资源能够满足的最大需求量的进程，从而保证进程运行完毕并归还全部资源。这时，把这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多，反复执行上述步骤。最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正执行本次分配，否则，本次资源分配暂不实施，让申请资源的进程等待。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量之和。
安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
(2)顾客可以分期贷款，但贷款的总数不能超过最大需求量；
(3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
(4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
六、实验环境：
Win-7系统
Visual C++ 6.0
七、实验设计：
1.数据结构设计 定义结构体：
struct Process//进程属性构成 { Source claim;//进程最大需求量
Source allocation;//进程占有量
Source claim_allocation;//进程需求量
Source currentAvail;//进程可获得量 };
定义类对象：
class Source //资源的基本构成以及功能 {
private: public: int R1;//定义三类类资源
int R2;int R3;
Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;}
Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;}
void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//设置各类资源
{ R1=r1;R2=r2;R3=r3;}
void add(Source s)//加法
{ R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;}
void sub(Source s)//减法
{ R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;}
bool lower(Source s)//比较
{
if(R1 > s.R1)return false;
if(R2 > s.R2)return false;
if(R3 > s.R3)return false;
return true;} };
class Data//封装所有数据 { public: Process *p;//进程指针
Source sum;//总资源量
Source available;//可获得量
Source ask;//请求量
int pLength;//进程个数
int * ruler;//逻辑尺
void clearProcess()//进程currentAvail清零
{
for(int i=0;i
{ p[i].currentAvail.setSource(0, 0, 0);} } };
class DataInit//封装初始化数据函数类 { private: public: DataInit()//构造函数
{ }
void initLength(Data *db)//设置进程个数
{
int n;
cout<<“输入进程数: ”;
cin>>n;
db->pLength = n;
db->p = new Process[n];
if(!db->p)
{cout<<“error!no enough memory space！”;return;}
db->ruler = new int[n];
if(!db->ruler)
{cout<<“error!no enough memory space！”;return;} }
2.算法设计
class FindSafeList//寻找安全序列 { private: public: FindSafeList()//构造函数
{}
bool checkList(Data *db)//检查一个序列安全性
{
int i=0;//i用于循环
db->p[db->ruler[i]].currentAvail.add(db->available);//将当前系统可用资源量赋给该序列的第一个进程
if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false
{return false;}
for(i=1;i< db->pLength;i++)
{
//当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvail
db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail);
//当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量
db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation);
//若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false
if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))
{ return false;}
//若当前进程currentAvail大于该进程总资源量，返回false
if(!db->p[db->ruler[i]].currentAvail.lower(db->sum))
{ return false;}
}
return true;//该序列进程安全。返回true
}
bool exsitSafeList(Data *db)//判断是否存在安全序列
{
int i = 0;
for(i = 0;i < db->pLength;i++)//设置逻辑尺的刻度值
{ db->ruler[i] = i;}
while(1)
//该循环将检测逻辑尺刻度值的全排列
{
if(checkList(db))
//找到一个安全序列，返回true
{ return true;}
db->clearProcess();//将所有进程的currentAvail清零
if(!next_permutation(db->ruler,db->ruler+db->pLength))
//所有排列完毕后退出生成排列库函数的调用
{ return false;
}
}
return false;}
int findSafeList(Data *db, int i=0)//寻找安全序列
{
//请求值大于系统当前可用资源值，返回0
if(!db->ask.lower(db->available))
{ return 0;}
//请求值大于当前进程需求资源值，返回1
if(!db->ask.lower(db->p[i].claim_allocation))
{ return 1;}
Source s(db->p[i].allocation);//根据请求，分配资源值
db->available.sub(db->ask);
db->p[i].allocation.add(db->ask);
db->p[i].claim_allocation.sub(db->ask);
if(!exsitSafeList(db))//判断是否存在安全序列
{
db->available.add(db->ask);
//不存在安全序列，回滚，恢复分配前状态，并返回2
db->p[i].allocation.sub(db->ask);
db->p[i].claim_allocation.add(db->ask);
return 2;
}
db->ask.setSource(0,0,0);//找到安全序列，将请求资源置零，返回3
return 3;}
};3.功能模块设计
class Data//封装所有数据
class DataInit//封装初始化数据函数类 class Display//封装显示方法
class FindSafeList//寻找安全序列 struct Process//进程属性构成
void main()//主函数
八、实验运行结果：
输入进程数，及相关资源数量分配
选择算法完成的操作：1 查看进程情况 请求分配
2.1分配失败
2.2 分配成功
2.3 继续分配失败，退出
九、实验心得：
通过此次实验，我能够更加深入的理解银行家算法的执行过程，也懂得用银行家算法去防止发生死锁，有效地解决了资源利用率低的问题，保证了系统的安全性。
当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。
附录：源代码（部分）
#include
class Source //资源的基本构成以及功能 {
private: public: int R1;//定义三类类资源
int R2;int R3;
Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;}
Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;}
void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//设置各类资源
{ R1=r1;R2=r2;R3=r3;}
void add(Source s)//加法
{ R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;}
void sub(Source s)//减法
{ R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;}
bool lower(Source s)//比较
{
if(R1 > s.R1)return false;
if(R2 > s.R2)return false;
if(R3 > s.R3)return false;
return true;}
};
struct Process//进程属性构成 { Source claim;//进程最大需求量
Source allocation;//进程占有量
Source claim_allocation;//进程需求量
Source currentAvail;//进程可获得量 };
class Data//封装所有数据 { public: Process *p;//进程指针
Source sum;//总资源量
Source available;//可获得量
Source ask;//请求量
int pLength;//进程个数
int * ruler;//逻辑尺
void clearProcess()//进程currentAvail清零
{
for(int i=0;i
{ p[i].currentAvail.setSource(0, 0, 0);} } };
class DataInit//封装初始化数据函数类 { private: public: DataInit()//构造函数
{ }
void initLength(Data *db)//设置进程个数
{
int n;
cout<<“输入进程数: ”;
cin>>n;
db->pLength = n;
db->p = new Process[n];
if(!db->p)
{cout<<“error!no enough memory space！”;return;}
db->ruler = new int[n];
if(!db->ruler){cout<<“error!no enough memory space！”;return;} }
void setAsk(Data *db)//设置请求资源量 { int r1,r2,r3;r1=0;r2=0;r3=0;
db->ask.setSource(r1,r2,r3);}
void initSum(Data *db)//设置总资源量
{ int r1,r2,r3;cout<<“Available(R1,R2,R3): ”;cin>>r1>>r2>>r3;db->sum.setSource(r1,r2,r3);}
void initAvail(Data *db)//设置可获得量 { int r1,r2,r3;cout<<“输入初始分配 Allocation:n”;cout<<“available[R1,R2,R3]:n ”;
cin>>r1>>r2>>r3;
db->available.setSource(r1,r2,r3);}
void initProcess(Data *db)//设置各进程属性值 { int r1,r2,r3;cout<<“输入t0时分配 Allocation:n”;for(int i=0;i
cout<<'p'< cin>>r1>>r2>>r3; db->p[i].allocation.setSource(r1,r2,r3); cout<<'p'< cin>>r1>>r2>>r3; db->p[i].claim.setSource(r1,r2,r3); r1=db->p[i].claim.R1-db->p[i].claim.R1;//设置进程p[i] 的 claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource(r1, r2, r3); } } }; class Display//封装显示方法 { private: public: Display()//构造函数 { } void displaySource(Source s)//设置基本资源显示方式 {cout< displayAvailable(Source s)//显示可获得资源量 {displaySource(s);} void displayProcess(Process *p,int length)//显示进程基本信息 { for(int i=0;i { cout<<“ p”< displaySource(p[i].claim); cout<<“tt”; displaySource(p[i].allocation); cout< } cout< void displaySafeList(Data *db)//显示安全序列 { for(int i=0;i { cout<<“ p”< ”; displaySource(db->p[db->ruler[i]].currentAvail); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim); cout<<“ ”; displaySource(db->p[db->ruler[i]].allocation); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim_allocation); cout<<“ true”; cout< } } void displayAskResult(Data *db,int n)//显示请求资源结果 { if(n==0) {cout<<“不分配，请求量大于当前可获得量!n”;return;} if(n==1) {cout<<“不分配，请求量大于当前可获得量!n”;return;} if(n==2) {cout<<“不分配，找不到安全序列!n”;return;} if(n==3) { cout<<“存在安全序列:”; for(int i=0;i {cout< cout< char c='N'; cout<<“查看安全序列详情?(Y/N)”; cin>>c; if(c=='Y'||c=='y') { cout<<“ 进程 currentavail claim allocation claim-allocation possiblen”; displaySafeList(db); } return; } } }; class FindSafeList//寻找安全序列 { private: public: FindSafeList()//构造函数 {} bool checkList(Data *db)//检查一个序列安全性 { int i=0;//i用于循环 db->p[db->ruler[i]].currentAvail.add(db->available);//将当前系统可用资源量 赋给该序列的第一个进程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若当前进程currentAvail大于该进程总资源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//该序列进程安全。返回true } bool exsitSafeList(Data *db)//判断是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//设置逻辑尺的刻度值 { db->ruler[i] = i;} while(1) //该循环将检测逻辑尺刻度值的全排列 { if(checkList(db)) //找到一个安全序列，返回true { return true;} db->clearProcess();//将所有进程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完毕后退出生成排列库函数的调用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//寻找安全序列 { //请求值大于系统当前可用资源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //请求值大于当前进程需求资源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根据请求，分配资源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判断是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滚，恢复分配前状态，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，将请求资源置零，返回3 return 3;} }; void main(){ Data *db;db=new Data;if(!db){ cout<<“error!no enough memory space！”;return;} DataInit dataInit;dataInit.initLength(db);//设置进程个数 dataInit.initSum(db);//设置系统总资源量 dataInit.initAvail(db);//设置当前系统可获得资源量 dataInit.initProcess(db);//设置t0时刻进程基本状态 Display display;FindSafeList findSafeList;int r1=0,r2=0,r3=0;int c;db->ask.setSource(r1,r2,r3);//设置请求资源为0，即无请求 c=findSafeList.findSafeList(db,0);//寻找安全序列，返回结果 if(c!=3){ cout<<“t0时刻的进程组不存在安全序列!n”;return;} int choice=1;int pi; while(choice){ cout<<“n 选择操作:n 查看进程情况n 请求分配资源n 0 退出n ”; cin>>choice;switch(choice){ case 1: { } case 2: { } case 0: { default: { } } } cout<<“当前资源量available[R1,R2,R3]:n ”;display.displayAvailable(db->available);cout< 实验四 死锁 一、实验目的 当系统的总资源数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”); （程序结束） 操作系统 课程设计报告 专业 计算机科学与技术 学生姓名 班级 学号 指导教师 完成日期 信息工程学院 题目： 银行家算法的模拟实现 一、设计目的本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 二、设计内容 1）概述 用C或C++语言编制银行家算法通用程序，并检测所给状态的系统安全性。 1.算法介绍：数据结构： 1） 可利用资源向量 Available； 2） 最大需求矩阵Max； 3） 分配矩阵Allocation； 4） 需求矩阵Need 2.功能介绍 模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成： 第一部分：银行家算法（扫描）； 第二部分：安全性算法。 2）设计原理 一．银行家算法的基本概念 1、死锁概念。 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 2、关于死锁的一些结论： Ø 参与死锁的进程最少是两个 Ø （两个以上进程才会出现死锁） Ø 参与死锁的进程至少有两个已经占有资源 Ø 参与死锁的所有进程都在等待资源 Ø 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 3、资源分类。 永久性资源： 可以被多个进程多次使用（可再用资源） l 可抢占资源 l 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式 4、产生死锁的四个必要条件：互斥使用（资源独占）、不可强占（不可剥夺）、请求和保持（部分分配，占有申请）、循环等待。 1) 互斥使用（资源独占） 一个资源每次只能给一个进程使用。 2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放。 3) 请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）。 4) 循环等待 存在一个进程等待队列 {P1,P2,…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。 5、死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 ①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 ②破坏“请求和保持”条件。 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 ③破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 6．安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i)当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。 二．银行家算法 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、银行家算法 设Requesti是进程Pi的请求向量。如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 1）如果 Requesti[j]<=Need[i,j]，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 2）如果Requesti[j]<=Available[j]，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。 3）系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[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; goto step 2； 4）如果所有进程的Finish[i]:=true，则表示系统处于安全状态；否则，系统处于不安全状态。 三．银行家算法之例 假定系统中有五个进程：{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图1所示。 资源情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 0 0 (2 0) P1 0 0 (3 0 2) (0 0) P2 0 0 0 0 P3 0 P4 0 0 图1 T0时刻的资源分配表 (1)T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图2)可知，在T0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。 资源情况 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 true true true true true P3 0 P4 0 0 P2 0 0 0 P0 0 0 图2 T0时刻的安全序列 (2)P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查： ①Request1(1,0,2)<=Need1(1,2,2) ②Request1(1,0,2)<=Available1(3,3,2) ③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成资源变化情况如图1中的圆括号所示。 ④再利用安全性算法检查此时系统是否安全。如图3所示。 资源情况 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 0 0 true true true true true P3 0 P4 0 0 P0 0 0 P2 0 0 0 图3 P1申请资源时的安全性检查 由所进行的安全性检查得知，可以找到一个安全序列｛P1,P3,P4,P2,P0｝。因此系统是安全的，可以立即将P1所申请的资源分配给它。 (3)P4请求资源：P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查： ①Request4(3,3,0)≤Need4(4,3,1); ②Request4(3,3,0)不小于等于Available(2,3,0),让P4等待。 (4)P0请求资源：P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查。 ①Request0(0,2,0) ≤Need0(7,4,3); ②Request0(0,2,0) ≤Available(2,3,0); ③系统暂时先假定可为P0分配资源，并修改有关数据，如图4所示。 资源情况 进程 Allocation Need Available A B C A B C A B C P0 0 0 0 P1 0 0 0 P2 0 0 0 P3 0 P4 0 0 图4 为P0分配资源后的有关资源数据 (5)进行安全性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。 3）详细设计及编码 1）银行家算法流程图 2）程序源代码 #include #include #include #include //定义全局变量 const int x=20,y=20; //常量，便于修改 int Available[x]; //各资源可利用的数量 int Allocation[y][y]; //各进程当前已分配的资源数量 int Max[y][y]; //各进程对各类资源的最大需求数 int Need[y][y]; //尚需多少资源 int Request[x]; //申请多少资源 int Work[x]; //工作向量，表示系统可提供给进程继续运行所需的各类资源数量 int Finish[y]; //表示系统是否有足够的资源分配给进程，1为是 int p[y]; //存储安全序列 int i,j; //i表示进程，j表示资源 int n,m; //n为进程i的数量,m为资源j种类数 int l=0; //l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是安全的int counter=0; //函数声明 void chushihua(); //初始化函数 void safe(); //安全性算法 void show(); //函数show,输出当前状态 void bank(); //银行家算法 //void jieshu(); //结束函数 void chushihua() { cout<<“输入进程的数量: “;//从此开始输入有关数据 cin>>n; cout<<“输入资源种类数: “; cin>>m; cout< 种): “< for (j=0; j j++) { cout<<“输入资源 “< 可利用的数量Available[“< “; cin>>Available[j]; //输入数字的过程...Work[j]=Available[j]; //初始化Work[j]，它的初始值就是当前可用的资源数 } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 输入进程 “< 当前已分配的资源 “< 数量: “; cin>>Allocation[i][j]; } cout< Finish[i]=0;//初始化Finish[i] } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 输入进程 “< 对资源 “< “; cin>>Max[i][j]; if(Max[i][j]>=Allocation[i][j]) //若最大需求大于已分配，则计算需求量 Need[i][j] = Max[i][j]-Allocation[i][j]; else Need[i][j]=0;//Max小于已分配的时候，此类资源已足够不需再申请 } cout< } cout< } //安全性算法函数 void safe() { l=0; for (i=0; i { //i++ if (Finish[i]==0) { //逐个查找Finish[i]==0的进程 条件一 counter=0; //记数器 for (j=0; j j++) { if (Work[j]>=Need[i][j]) counter=counter+1;//可用大于需求，记数 } if(counter==m) //i进程的每类资源都符合Work[j]>=Need[i][j] 条件二 { p[l]=i; //存储安全序列 Finish[i]=1; //i进程标志为可分配 for (j=0; j Work[j]=Work[j]+Allocation[i][j]; //释放资源 l=l+1; //记数,现在有L个进程是安全的，当L=N时说明满足安全序列 i= -1; //从第一个进程开始继续寻找满足条件一二的进程 } } } } //显示当前状态函数 void show() //函数show,输出当前资源分配情况 { int i,j; //局部变量 int All[y]; //各种资源的总数量 cout<<“当前的状态为：“< cout<<“各种资源的总数量:“< for (j=0;j { cout<<“ 资源“< “; All[j]=Available[j]; //总数量=可用的+已分配的for (i=0;i All[j]+=Allocation[i][j]; cout< “; } cout< for (j=0;j cout<<“ 资源“< “< “; cout< “< for (j=0;j cout<<＇＼t＇<<“资源“< cout< for(i=0;i { cout<<“进程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } cout< for (j=0;j cout<<＇＼t＇<<“资源“< cout< for(i=0;i { cout<<“进程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } } //银行家算法函数 void bank() { cout< int k=0; //用于输入进程编号 bool r=false; // 初值为假，输入Y继续申请则置为真 do{//输入请求 cout<<“输入申请资源的进程(0-“< “; cin>>k; cout< while(k>n-1) //输入错误处理 { cout< cout< “; cin>>k; cout< } cout< “< for (j=0; j j++) { do{ //do……while 循环判断申请输入的情况 cout<<“进程 “< 申请资源[“< cin>>Request[j]; cout< if(Request[j]>Need[k][j]) { //申请大于需求量时出错，提示重新输入（贷款数目不允许超过需求数目） cout<<“申请大于需要量!“< cout<<“申请的资源“< 进程“< cout<<“重新输入!“< } else //先判断是否申请大于需求量，再判断是否申请大于可利用量 if(Request[j]>Available[j]) { //申请大于可利用量，应该阻塞等待？…… ？？？ cout<<“＼n没有那么多资源，目前可利用资源“< Finish[k]=0; //该进程等待 goto ppp; //goto语句 跳转，结束本次申请 } }while(Request[j]>Need[k][j]); //Request[j]>Available[j]|| } //改变Avilable、Allocation、Need的值 for (j=0; j j++) { Available[j] = Available[j]-Request[j]; Allocation[k][j] = Allocation[k][j]+Request[j]; Need[k][j] = Need[k][j]-Request[j]; Work[j] = Available[j]; } //判断当前状态的安全性 safe(); //调用安全性算法函数 if (l { l=0; cout<<“＼n试分配后，状态不安全,所以不予分配!恢复原状态“< //恢复数据 for (j=0; j j++) { Available[j] = Available[j]+Request[j]; Allocation[k][j] = Allocation[k][j]-Request[j]; Need[k][j] = Need[k][j]+Request[j]; Work[j] = Available[j]; } for (i=0; i i++) Finish[i]=0; //进程置为未分配状态 } else { l=0; cout<<“＼n申请资源成功！!“< for(j=0;j { if(Need[k][j]==0); else { //有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源 l=1; //置l为1，作为判断标志 break; } } if(l!=1) { //进程可以执行，则释放该进程的所有资源 for (j=0;j { Available[j]=Available[j]+Allocation[k][j]; Allocation[k][j]=0; } cout<<“该进程已得到所有需求资源，执行后将释放其所有拥有资源！“< } l=0; //归零 cout<<“＼n安全的状态!“< cout<<“安全序列为: “; cout<第二篇：操作系统银行家算法实验报告
第三篇：操作系统课程设计(银行家算法的模拟实现)
第四篇：操作系统课程设计银行家算法的模拟实现