一．算法介紹:
**數(shù)據(jù)結(jié)構(gòu):
1.可利用資源向量Available
2.最大需求矩陣Max
3.分配矩陣Allocation
4.需求矩陣Need
  **功能介紹:
模擬實現(xiàn)Dijkstra的銀行家算法以避免死鎖的出現(xiàn).分兩部分組成:
第一部分:銀行家算法(掃描)
1．如果Request<=Need,則轉(zhuǎn)向2;否則,出錯
2．如果Request<=Available,則轉(zhuǎn)向3,否則等待
3．系統(tǒng)試探分配請求的資源給進程
4．系統(tǒng)執(zhí)行安全性算法
第二部分:安全性算法
1.設(shè)置兩個向量
(1).工作向量:Work=Available(表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源數(shù)目)
(2).Finish:表示系統(tǒng)是否有足夠資源分配給進程(True:有;False:沒有).初始化為False
2.若Finish=False&&Need<=Work,則執(zhí)行3;否則執(zhí)行4(I為資源類別)
3.進程P獲得第i類資源,則順利執(zhí)行直至完成!并釋放資源:
Work=Work+Allocation;
Finish=true;
轉(zhuǎn)2
4.  若所有進程的Finish=true,則表示系統(tǒng)安全;否則,不安全! 

二.原代碼及注釋:
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include "windows.h"
#define MAX_PROCESS 32              //最大進程數(shù)
#define MAX_COURCE 64              //最大資源類別

int MAX_FACT_PROCESS;              //實際總進程數(shù)
int MAX_FACT_COURCE;               //實際資源類別數(shù)
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;                       //發(fā)出請求的進程
int Request_COURCE;                        //被請求資源類別
int Request_COURCE_NEMBER;                 //請求資源數(shù)

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[j]=Array[num++];
}
infile.close();
}ww w.china it power.co06sBQ

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;
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[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[j]=Array[num++];
infile.close();
} 

 

void Set_Need(void){                        //設(shè)置需求矩陣
cout<<"設(shè)置需求矩陣"<<'\n';
for(int i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Need[j]=Max[j]-Allocation[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[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=Available;
}
   bool Finish[MAX_PROCESS][MAX_COURCE];
for(i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Finish[j]=false;
COMP Array[32];
for(i=0;i<MAX_FACT_PROCESS;i++)
{
Array.value=Need[Request_COURCE-1];
       Array.num=i;
}
for(i=0;i<MAX_FACT_PROCESS;i++)
for(int j=i+1;j<MAX_FACT_PROCESS;j++){
if(Array.value>=Array[j].value){
int t;
t=Array[j].value;
               Array[j].value=Array.value;
Array.value=t;
t=Array[j].num;
               Array[j].num=Array.num;
               Array.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[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.num==Request_PROCESS-1)
continue;
if(Array.num!=Request_PROCESS-1&&Finish[Array.num][Request_COURCE-1]==false&&Need[Array.num]

[Request_COURCE-1]<=Work[Request_COURCE-1]){
Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Array.num][Request_COURCE-1];
               Finish[Array.num][Request_COURCE-1]=true;
}
}
   for(i=0;i<MAX_FACT_PROCESS;i++)
{
if(Finish[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.num==Request_PROCESS)
continue;
else
cout<<"P"<<Array.num<<"--->";
}
cout<<'\n'<<"已通過安全性測試!"<<endl;
Allocate_Source();
} 

 

void RUN(void){                                        //執(zhí)行銀行家算法

   cout<<"*************************************************"<<'\n'<<"點擊1執(zhí)行!"
<<'\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<<"可是已超出該進程尚需的該類資源的最大數(shù)量,所以不予以分配!!"<<endl;
exit(0);
}
if(Request_COURCE_NEMBER>Available[Request_COURCE-1])
{
cout<<'\n'<<"第"<<Request_PROCESS<<"個進程請求第"<<Request_COURCE<<"類資

源"<<Request_COURCE_NEMBER<<"個"<<endl;
       cout<<"可是系統(tǒng)中尚無足夠的資源,所以進入等待隊列!!"<<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<<'\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[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[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[j]<<'\t';
cout<<endl;
}
   Sleep(m_delay);
cout<<"設(shè)置成功"<<'\n';

   Read_Request();
cout<<'\n'<<"第"<<Request_PROCESS<<"個進程請求第"<<Request_COURCE<<"類資

源"<<Request_COURCE_NEMBER<<"個"<<endl;
cout<<'\n'<<"讀入成功"<<'\n';

RUN();
} 


-----------------------------------------------------

　第 6 樓   

（第六部分）

三．?dāng)?shù)據(jù)測試
注:數(shù)組Array[I]表示第I+1個實際意義量
     需要創(chuàng)建三個txt文本。
1.Initiate.txt文本
 3 3 2      //共有3類資源,Available[0]=3; Available[1]=3; Available[2]=2
5             //當(dāng)前系統(tǒng)中有個進程
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
四．程序說明:
本程序假設(shè)當(dāng)前時刻只有一個進程請求某一類資源n個.
若要滿足某個進程當(dāng)前時刻同時請求不止一類資源,則需要為最大需求矩陣Max,分配矩陣Allocation和需求矩

陣Need增加維數(shù),當(dāng)然代碼量也將大大增加,但是算法邏輯本身并無變化.