特别申明：转载一位大哥的程序
一．算法介绍:
**数据结构:
1.可利用资源向量Available
2.最大需求矩阵Max
3.分配矩阵Allocation
4.需求矩阵Need
**功能介绍:
模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:
第一部分:银行家算法(扫描)
1．如果Request<=Need,则转向2;否则,出错
2．如果Request<=Available,则转向3,否则等待
3．系统试探分配请求的资源给进程
4．系统执行安全性算法
第二部分:安全性算法
1.设置两个向量
(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)
(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False
2.若Finish[i]=False&&Need<=Work,则执行3;否则执行4(I为资源类别)
3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:
Work=Work+Allocation;
Finish[i]=true;
转2
4. 若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!
二.原代码及注释:
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include "windows.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; //请求资源数
struct COMP{
int value;
int num;
int next;
};
int flag=0;
void Read_Initiate(void){ //读入初始化文档
ifstream infile("Initiate.txt");
if(!infile){
cout<<"不能打开输入文件:"<<"Initiate.txt"<<'/n';
exit(1);
}
cout<<"开始读入初始化文档"<<'/n';
int ch;
int Array[MAX_PROCESS*MAX_COURCE*2];
int num=0;
while(infile>>ch)
Array[num++]=ch;
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++){
for(int j=0;j<MAX_FACT_COURCE;j++)
Max[i][j]=Array[num++];
}
infile.close();
}
void Write_Initiate(void){ //写入初始化文档(分配资源
ofstream outfile("Initiate.txt");
if(!outfile){
cout<<"不能打开初始化文档："<<'/n';
exit(1);
}
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];
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<<'/n'<<Array[num++]<<endl;
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
outfile<<Array[num++]<<" ";
outfile<<endl;
}
DWORD m_delay=3000;
Sleep(m_delay);
outfile.close();
cout<<"修改初始化文档成功!"<<endl;
}
void Allocated_list(void){ //读入已分配资源列表
ifstream infile("Allocated_list.txt");
if(!infile){
cout<<"不能打开输入文件:"<<"Allocated_list.txt"<<'/n';
exit(1);
}
cout<<"开始读入已分配资源列表"<<'/n';
int ch,num=0;
int Array[MAX_PROCESS*MAX_COURCE];
while(infile>>ch)
Array[num++]=ch;
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();
}
void Set_Need(void){ //设置需求矩阵
cout<<"设置需求矩阵"<<'/n';
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 Read_Request(void){ //读入请求向量
ifstream infile("Request_list.txt");
if(!infile){
cout<<"不能打开输入文件:"<<"Request_list.txt"<<'/n';
exit(1);
}
cout<<"开始读入请求向量"<<'/n';
int Array[3];
int num=0,ch;
while(infile>>ch)
Array[num++]=ch;
Request_PROCESS=Array[0];
Request_COURCE=Array[1];
Request_COURCE_NEMBER=Array[2];
infile.close();
}
void Write_Allocation(void){ //修改资源分配列表(资源分配)
ofstream outfile("Allocated_list.txt");
if(!outfile){
cout<<"不能打开资源分配列表："<<'/n';
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;
}
DWORD m_delay=3000;
Sleep(m_delay);
cout<<"修改资源分配列表成功!"<<endl;
outfile.close();
}
void Allocate_Source(void){ //开始分配(已通过扫描和安全性检测)
cout<<'/n'<<"开始给第"<<Request_PROCESS<<"个进程分配第"<<Request_COURCE
<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
Write_Initiate();
Write_Allocation();
DWORD m_delay=3000;
Sleep(m_delay);
cout<<'/n'<<"祝贺您，资源分配已成功!"<<endl;
}
void Test_Safty(){ //安全性检测
cout<<'/n'<<"进入安全性检测!"<<endl;
int Work[MAX_COURCE];
for(int i=0;i<MAX_FACT_COURCE;i++){
Work[i]=Available[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;
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;
}
DWORD m_delay=3000;
Sleep(m_delay);
/*for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Need[i][j]<<'/t';
cout<<endl;
}
*/
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];
Finish[Request_PROCESS-1][Request_COURCE-1]=true;
}
else
{
cout<<"未通过安全性测试，不与以分配"<<endl;
exit(0);
}
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][Request_COURCE-1];
Finish[Array[i].num][Request_COURCE-1]=true;
}
}
for(i=0;i<MAX_FACT_PROCESS;i++)
{
if(Finish[i][Request_COURCE-1]==true)
continue;
else
{
cout<<"未通过安全性测试，不与以分配"<<endl;
exit(0);
}
}
cout<<'/n'<<"找到一个安全序列:"<<"P"<<Request_PROCESS<<"--->";
for(i=0;i<MAX_FACT_PROCESS;i++){
if(Array[i].num==Request_PROCESS)
continue;
else
cout<<"P"<<Array[i].num<<"--->";
}
cout<<'/n'<<"已通过安全性测试!"<<endl;
Allocate_Source();
}
void RUN(void){ //执行银行家算法
cout<<"*************************************************"<<'/n'<<"点击1执行!"
<<'/n'<<"点击2退出!"
<<'/n'<<"*************************************************"<<endl;
cin>>flag;
if(flag==2)
exit(0);
if(flag==1)
{
cout<<"开始扫描请求信息!"<<endl;
DWORD m_delay=3000;
Sleep(m_delay);
if(Request_COURCE_NEMBER>Need[Request_PROCESS-1][Request_COURCE-1])
{
cout<<'/n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
cout<<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!"<<endl;
exit(0);
}
if(Request_COURCE_NEMBER>Available[Request_COURCE-1])
{
cout<<'/n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
cout<<"可是系统中尚无足够的资源,所以进入等待队列!!"<<endl;
exit(0);
}
else{
Available[Request_COURCE-1]=Available[Request_COURCE-1]-Request_COURCE_NEMBER;
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;
cout<<"扫描通过"<<endl;
Sleep(m_delay);
Test_Safty();
}
}
else {
cout<<"输入错误,请重新输入!"<<'/n';
RUN();
}
}
void main(void){
Read_Initiate();
cout<<MAX_FACT_COURCE<<'/t';
for(int i=0;i<MAX_FACT_COURCE;i++)
cout<<Available[i]<<'/t';
cout<<endl<<MAX_FACT_PROCESS<<endl;
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Max[i][j]<<'/t';
cout<<endl;
}
DWORD m_delay=3000;
Sleep(m_delay);
cout<<"读入成功"<<'/n';
Allocated_list();
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Allocation[i][j]<<'/t';
cout<<endl;
}
Sleep(m_delay);
cout<<"读入成功"<<'/n';
Set_Need();
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Need[i][j]<<'/t';
cout<<endl;
}
Sleep(m_delay);
cout<<"设置成功"<<'/n';
Read_Request();
cout<<'/n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
cout<<'/n'<<"读入成功"<<'/n';
RUN();
}
三．数据测试
注:数组Array[I]表示第I+1个实际意义量
需要创建三个txt文本。
1.Initiate.txt文本
3 3 3 2 //共有3类资源,Available[0]=3; Available[1]=3; Available[2]=2
5 //当前系统中有个进程
7 5 3 // Max[0][0]=7
3 2 2 //Max[1][1]=3
9 0 2
2 2 2
4 3 3
2.Allocated_list.txt文本
0 1 0 //Allocation[0][1]=1
2 0 0
3 0 2
2 1 1
0 0 2
3.Request_list.txt文本
2 1 1 //第2个进程请求第1类资源1个Request[1][0]=1
四．程序说明:
本程序假设当前时刻只有一个进程请求某一类资源n个.
若要满足某个进程当前时刻同时请求不止一类资源,则需要为最大需求矩阵Max,分配矩阵Allocation和需求矩阵Need增加维数,当然代码量也将大大增加,但是算法逻辑本身并无变化.