yinghangjia.cpp

银行家算法检测安全序列

#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;                 //请求资源数
int *require,*s,k;

void clear();
void Read_Initiate(void);
void Write_Initiate(void);
void Allocated_list(void);
void Set_Need(void);
void Write_Allocation(void);
void Allocate_Source(void);
void set_require();
void Test_Safty();
void RUN(void);

struct COMP{
int value;
int num;
int next;
};
int flag=0;
void clear(){
for(int i=0;i<MAX_PROCESS;i++)
   for(int j=0;j<MAX_COURCE;j++){
     Allocation[i][j]=' ';
     Max[i][j]=' ';
     Need[i][j]=' ';
   }
for(i=0;i<MAX_COURCE;i++)
   Available[i]=' ';
}
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;
for(int i=0;i<MAX_PROCESS*MAX_COURCE*2;i++)
   Array[i]=' ';
while(infile>>ch)
   Array[num++]=ch;
num=0;
MAX_FACT_PROCESS=Array[num++];
MAX_FACT_COURCE=Array[num++];
for(int j=0;j<MAX_FACT_COURCE;j++)
   Available[j]=Array[num++]; 
for( 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];
for(int i=0;i<MAX_PROCESS*MAX_COURCE*2;i++)
   Array[i]=' ';
int num=0;
    Array[num++]=MAX_FACT_PROCESS;
Array[num++]=MAX_FACT_COURCE;
for( i=0;i<MAX_FACT_COURCE;i++)
   Array[num++]=Available[i];
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];
for(int i=0;i<MAX_PROCESS*MAX_COURCE;i++)
   Array[i]=' ';
while(infile>>ch)
   Array[num++]=ch;
num=0;
for( 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 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){                       //开始分配(已通过扫描和安全性检测)

for(int j=0;j<MAX_FACT_COURCE;j++){
   cout<<'\n'<<"开始给第"<<Request_PROCESS+1<<"个进程分配第"<<j+1
   <<"类资源"<<require[j]<<"个"<<endl;
        Available[j]=Available[j]-require[j];
        Allocation[Request_PROCESS][j]=Allocation[Request_PROCESS][j]+require[j];
   Need[Request_PROCESS][j]=Need[Request_PROCESS][j]-require[j];
}
Write_Initiate();
Write_Allocation();
Set_Need();
DWORD m_delay=3000;
Sleep(m_delay);
cout<<'\n'<<"祝贺您，资源分配已成功!"<<endl;
    cout<<"相应进程所需资源如下：\n";
cout<<"              \t";
for( j=0;j<MAX_FACT_COURCE;j++)
   cout<<"第"<<j+1<<"类资源\t";
cout<<endl;
for(int i=0;i<MAX_FACT_PROCESS;i++){
    cout<<"第"<<i+1<<"个进程还需要"<<'\t';
    for(int j=0;j<MAX_FACT_COURCE;j++){
     cout<<Need[i][j]<<"        \t";
     if(Need[i][j]=0) k--;
     cout<<"k="<<k<<endl;
    }
    cout<<endl;
   }
   
g2: cout<<"*************************************************"<<'\n'<<"点击1继续执行!"
   <<'\n'<<"输入2退出!"
   <<'\n'<<"*************************************************"<<endl;
cin>>flag;
if(flag==2) exit(0);
else if(flag==1){
   if(k>0&&Request_PROCESS==MAX_FACT_PROCESS-1){
    cout<<"k="<<k<<endl;
    set_require();
   }
   else{
    cout<<"所有进程已得到满足，退出!\n";
    exit(1);
   }
}
else {
   cout<<"输入错误,请重新输入!"<<'\n';
   goto g2;
}
}
void set_require(){
    for(int i=0;i<MAX_FACT_PROCESS;i++){
     Set_Need();
        Request_PROCESS=i;
    for(int j=0;j<MAX_FACT_COURCE;j++){
     require[j]=0;
     if(Need[Request_PROCESS][j]==0)
      continue;
     cout<<'\n'<<"输入第"<<Request_PROCESS+1<<"个进程\n"<<"第"<<j+1<<"类资源需求数目";
     cin>>Request_COURCE_NEMBER;
           require[j]=Request_COURCE_NEMBER;
    }
    cout<<'\n'<<"第"<<Request_PROCESS+1<<"个进程\n";
    for( j=0;j<MAX_FACT_COURCE;j++)
     cout<<"请求第"<<j+1<<"类资源"<<require[j]<<"个"<<endl;
    j=0;
    RUN();
   }
}
void Test_Safty(){                         //安全性检测
s=new int[MAX_FACT_PROCESS];//存放安全序列
int k=0,q=1;//k确定安全序列位置，q判断是否某进程是否通过安全检测（1，通过，0，没有通过）
cout<<'\n'<<"进入安全性检测!"<<endl;
int Work[MAX_COURCE];
for(int i=0;i<MAX_FACT_COURCE;i++)
   Work[i]=' ';
for(i=0;i<MAX_FACT_COURCE;i++)
   Work[i]=Available[i];
bool Finish[MAX_PROCESS][MAX_COURCE];
for(i=0;i<MAX_PROCESS;i++)
   for(int j=0;j<MAX_COURCE;j++)
    Finish[i][j]=false;
COMP Array[32][64];
    for(i=0;i<MAX_PROCESS;i++)
   for(int j=0;j<MAX_COURCE;j++){
    Array[i][j].num=' ';
    Array[i][j].value=' ';
   }
for(i=0;i<MAX_FACT_PROCESS;i++)
   for(int j=0;j<MAX_FACT_COURCE;j++){ 
    Array[i][j].value=Need[i][j];  
    Array[i][0].num=i;
   }

DWORD m_delay=3000;
Sleep(m_delay);
for(int j=0;j<MAX_FACT_COURCE;j++){
   int m=0;
   if(Finish[Request_PROCESS][j]==false&&Need[Request_PROCESS][j]<=Work[j])
   { 
    Work[j]=Work[j]+Allocation[Request_PROCESS][j];
    Finish[Request_PROCESS][j]=true;
    m=1;
    q*=m;
   }
   else{  
    m=0; 
    q*=m; 
   }
}
    if(q==1){
   s[k]=Request_PROCESS+1;
   k++;
}
else
{
   cout<<"未通过安全性测试1，不与以分配"<<endl;
   exit(0);
}
g3: for(i=0;i<MAX_FACT_PROCESS;i++){
   int m;
   if(Array[i][0].num==Request_PROCESS)
    continue;
   for(int j=0;j<MAX_FACT_COURCE;j++)
    if(Array[i][0].num!=Request_PROCESS&&Finish[Array[i][0].num][j]==false&&Need[Array[i][0].num][j]<=Work[j]){   
     Work[j]=Work[j]+Allocation[Array[i][0].num][j];   
     Finish[Array[i][0].num][j]=true;
     m=1;
     q*=m;
    }
    else{
     m=0;
     q*=m;
    }
   if(q==1){
    s[k]=Array[i][0].num+1;
    k++;
    goto g3;
   }
}
for(i=0;i<MAX_FACT_PROCESS;i++)
   for(int j=0;j<MAX_FACT_COURCE;j++){  
    if(Finish[i][j]==true)   
     continue;  
    else{   
     cout<<"未通过安全性测试2，不与以分配"<<endl;   
     exit(0);
    }
   }
cout<<'\n'<<"找到一个安全序列:";
k=0;
for(i=0;i<MAX_FACT_PROCESS;i++){
    cout<<"P"<<s[k]<<"--->";
    k++;
}
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);
   for(int j=0;j<MAX_FACT_COURCE;j++)
    if(Need[Request_PROCESS][j]==0)
      continue;
   if(require[j]>Need[Request_PROCESS][j])
   {   
    cout<<"\n第"<<Request_PROCESS+1<<"个进程还需要第"<<j+1<<"类资源"<<Need[Request_PROCESS][j]<<"个";
    cout<<'\n'<<"第"<<Request_PROCESS+1<<"个进程请求第"<<j+1<<"类资源"<<require[j]<<"个"<<endl;
    cout<<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!"<<endl;
    cout<<"\n请重新输入第"<<Request_PROCESS+1<<"个进程第"<<j+1<<"类资源数目"<<endl;
    cin>>Request_COURCE_NEMBER;
    require[j]=Request_COURCE_NEMBER;
    RUN();
   }
   if(require[j]>Available[j])
   {
    cout<<'\n'<<"第"<<Request_PROCESS+1<<"个进程请求第"<<j+1<<"类资源"<<require[j]<<"个"<<endl;
    cout<<"可是系统中尚无足够的资源,所以进入等待队列!!"<<endl;
    exit(0);
   }
   else{
   // Available[j]=Available[j]-require[j];
   // Allocation[Request_PROCESS][j]=Allocation[Request_PROCESS][j]+require[j];
   // Need[Request_PROCESS][j]=Need[Request_PROCESS][j]-require[j];
    cout<<"扫描通过"<<endl;
    Sleep(m_delay);
    Test_Safty();
   }
}
else {
   cout<<"输入错误,请重新输入!"<<'\n';
   RUN();
}
}

void main(void){
clear();
cout<<"※※※※※※※※※※※※※※※※※※※※"<<endl;
cout<<"※          欢迎使用本系统！          ※"<<endl;
cout<<"※            作者:邓申贵             ※"<<endl;
cout<<"※====================================※"<<endl;
cout<<"====输入实际总进程数:               ===="<<endl;
cin>>MAX_FACT_PROCESS; 
cout<<"====输入实际资源类别数:             ===="<<endl;
cin>>MAX_FACT_COURCE;
    cout<<"========================================"<<endl;
require=new int[MAX_FACT_COURCE];
cout<<"====输入资源向量:                   ===="<<endl;
for(int i=0;i<MAX_FACT_COURCE;i++){
   cout<<"====第"<<i+1<<"类资源可用数目      ";
   cin>>Available[i];
}
    cout<<"========================================"<<endl;
cout<<"====建立需求矩阵\n"<<"====输入相应进程的需求资源数目:\n";
    for( i=0;i<MAX_FACT_PROCESS;i++){
   cout<<"====输入第"<<i+1<<"个进程\n";
   for(int j=0;j<MAX_FACT_COURCE;j++){
    int m;
    cout<<"====第"<<j+1<<"类资源所需数目:";
    cin>>m;
    if(m>Available[j]){
     cout<<"====所需资源已超出可用资源数目，退出！\n";
     exit(0);
    }
    else
     Max[i][j]=m;
   }
}
for( i=0;i<MAX_FACT_PROCESS;i++){
   cout<<"输入第"<<i+1<<"个进程\n";
   for(int j=0;j<MAX_FACT_COURCE;j++){
    int a;
        g1: cout<<"\n第"<<j+1<<"类资源已分配数目:";
    cin>>a;
    if(a>Max[i][j]) {
     cout<<"超出最大可得资源数目，错误！重新输入！"<<endl;
     goto g1;
    }
    else Allocation[i][j]=a;
    Available[j]=Available[j]-Allocation[i][j];
   }
}
   Write_Initiate();
   Read_Initiate();
   cout<<endl<<"进程数目："<<MAX_FACT_PROCESS<<endl;
   cout<<"资源种类："<<MAX_FACT_COURCE<<'\n';
   cout<<"可用资源数目：\n";
   for( i=0;i<MAX_FACT_COURCE;i++)
    cout<<"第"<<i+1<<"类资源:"<<Available[i]<<'\t';
   DWORD m_delay=3000;
   Sleep(m_delay);
   cout<<"读入成功"<<'\n';
   k=MAX_FACT_PROCESS*MAX_FACT_COURCE;//k>0，还有进程的需求没得到满足，可以继续进行，k==0退出
   Write_Allocation();
   Allocated_list();
   cout<<"              \t";
   for(int j=0;j<MAX_FACT_COURCE;j++)
    cout<<"第"<<j+1<<"类资源\t";
   cout<<endl;
   for(i=0;i<MAX_FACT_PROCESS;i++){
       cout<<"第"<<i+1<<"个进程已分配\t";
    for(int j=0;j<MAX_FACT_COURCE;j++)
     cout<<Allocation[i][j]<<"        \t";
    cout<<endl;
   }

   Sleep(m_delay);
   cout<<"读入成功"<<'\n';

   Set_Need();
   cout<<"              \t";
   for( j=0;j<MAX_FACT_COURCE;j++)
    cout<<"第"<<j+1<<"类资源\t";
   cout<<endl;
   for(i=0;i<MAX_FACT_PROCESS;i++){
    cout<<"第"<<i+1<<"个进程还需要\t";
    for(int j=0;j<MAX_FACT_COURCE;j++)
     cout<<Need[i][j]<<"        \t";
    cout<<endl;
   }
   
   Sleep(m_delay);
   cout<<"设置成功"<<'\n';

   cout<<"开始读入请求向量"<<'\n';
   set_require();
}