作業系統 實驗二 死鎖的避免-銀行家算法

//************************************************************************//
//*                  實驗二 死鎖的避免――銀行家算法                      	 *//
//*																  	     *//
//*本程式需要預先設定三個檔案：Available_list.txt，Max_list.txt，Allocation_list.txt *//
//*  各檔案格式如下：      					    					     *//
//*  Available_list.txt		 											 *//
//*  3        //表示共有3類資源					   					     *//
//*  10 5 7   //表示各類資源的初始可用個數，即Available[0]=10, Available[1]=5        *//
//*																	     *//
//*																         *//
//*  Max_list.txt		  												 *//
//*  5        //表示共有5個程序		 								     *//
//*  7 5 3   //表示各個程序需要各類資源的最大數目，即Max[0][0]=7, Max[0][1]=5	*//
//*  3 2 2																  	*//
//*  9 0 2																  	*//
//*  2 2 2																  	*//
//*  4 3 3																  	*//
//*	  																	  	*//
//*	  																	  	*//
//*  Allocation_list.txt													*//
//*  0 1 0 //表示各個程序已配置設定各類資源的數目                               	*//
//*  2 0 0																  	*//
//*  3 0 2																  	*//
//*  2 1 1																  	*//
//*  0 0 2																  	*//
//*  																	  	*//
//*	  																      	*//
//***************************************************************************//

#include <iostream>
#include <stdio.h>
#include <windows.h>

#define MAX_PROCESS 32              	//最大程序數
#define MAX_RESOURCE 64             	//最大資源類别

int PROCESS_NUM;              							//實際總程序數
int RESOURCE_NUM;              							//實際資源類别數
int Available[MAX_RESOURCE];                 			//可利用資源向量
int Max[MAX_PROCESS][MAX_RESOURCE];          			//最大需求矩陣
int Allocation[MAX_PROCESS][MAX_RESOURCE];   			//配置設定矩陣
int Need[MAX_PROCESS][MAX_RESOURCE];         			//需求矩陣

int Request_PROCESS;                       				//送出請求的程序
int Request_RESOURCE_NEMBER[MAX_RESOURCE];     			//請求資源數

void Read_Available_list();      						//讀入可用資源Available
void Read_Max_list();           						//讀入最大需求矩陣Max
void Read_Allocation_list();    						//讀入已配置設定矩陣Allocation
void PrintInfo();               						//列印各資料結構資訊
void Read_Request();									//輸入請求向量
void Allocate_Source();         						//開始正式配置設定資源（修改Allocation_list.txt）
void Recover_TryAllocate();     						//恢複試配置設定前狀态
int Test_Safty();               						//安全性檢測
void RunBanker();               						//執行銀行家算法

using namespace std; 

//讀入可用資源Available
void Read_Available_list()      
{
	FILE *fp;
	if((fp=fopen("Available_list.txt","r"))==NULL)			//檢查檔案是否存在
	{ 
		cout<<"錯誤,檔案打不開,請檢查檔案名"<<endl; 
		exit(0);
	}
	fscanf(fp,"%d",&RESOURCE_NUM);							//讀入可配置設定的資源類别的數目
	int i=0;
	while(!feof(fp))										//讀入各個可配置設定資源的數目
	{
		fscanf(fp,"%d",&Available[i]);
		i++;
	}	
	fclose(fp);												//關閉檔案
}

//讀入最大需求矩陣Max
void Read_Max_list()      
{
	FILE *fp;
	if((fp=fopen("Max_list.txt","r"))==NULL)			//檢查檔案是否存在
	{ 
		cout<<"錯誤,檔案打不開,請檢查檔案名"<<endl; 
		exit(0);
	}
	fscanf(fp,"%d",&PROCESS_NUM);						//讀入總程序數
	for(int i=0;i<PROCESS_NUM;i++)						//讀入每個程序
		for(int j=0;j<RESOURCE_NUM;j++)					//讀入每個程序總的所需的各個資源的數目
			fscanf(fp,"%d",&Max[i][j]);
	fclose(fp);											//關閉檔案
}

//讀入已配置設定矩陣Allocation
void Read_Allocation_list()      
{
	FILE *fp;
	if((fp=fopen("Allocation_list.txt","r"))==NULL)		//檢查檔案是否存在
	{ 
		cout<<"錯誤,檔案打不開,請檢查檔案名"<<endl; 
		exit(0);
	}
	for(int i=0;i<PROCESS_NUM;i++)						//讀入每個程序
		for(int j=0;j<RESOURCE_NUM;j++)
			fscanf(fp,"%d",&Allocation[i][j]);			//讀入每個程序已經配置設定的資源數
	fclose(fp);
}

//設定需求矩陣Need
void Set_Need_Available()					
{                 
	for(int i=0;i<PROCESS_NUM;i++)						//每個程序
		for(int j=0;j<RESOURCE_NUM;j++)
		{
			Need[i][j]=Max[i][j]-Allocation[i][j];				//計算每個程序完成還需要的資源數
			Available[j]=Available[j]-Allocation[i][j];		//計算可利用資源與完成該程序還需要的資源數，用于判斷能否安全配置設定
		}
}

//列印各資料結構資訊
void PrintInfo()
{
	cout<<"程序個數： "<<PROCESS_NUM<<"\t"<<"資源個數： "<<RESOURCE_NUM<<endl;	//列印程序個數和資源類别數
	cout<<"可用資源向量Available："<<endl;
	int i,j;
	for(i=0;i<RESOURCE_NUM;i++)						//列印剩餘可用資源
		cout<<Available[i]<<"\t";
	cout<<endl;
	cout<<"最大需求矩陣Max："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//列印各個程序所需的最大資源數
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Max[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"已配置設定矩陣Allocation："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//列印每個程序已經配置設定的資源數
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Allocation[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"需求矩陣Need："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//列印每個程序完成還需要的資源數
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Need[i][j]<<"\t";
		cout<<endl;
	}
}

//輸入請求向量
void Read_Request()			 
{                          
	cout<<"輸入發起請求的程序（0－"<<PROCESS_NUM-1<<")：";
	cin>>Request_PROCESS;							//輸入發起資源請求的程序号

	cout<<"輸入請求資源的數目：按照這樣的格式輸入 x x x：";
	for(int i=0; i<RESOURCE_NUM; i++)				//輸入該程序請求的各個資源的數目
		cin>>Request_RESOURCE_NEMBER[i];
}

//開始正式配置設定資源（修改Allocation_list.txt）
void Allocate_Source()
{                       
	cout<<'\n'<<"開始給第"<<Request_PROCESS<<"個程序配置設定資源..."<<endl;
	FILE *fp;
	if((fp=fopen("Allocation_list.txt","w"))==NULL)			//檢查檔案是否存在
	{ 
		cout<<"錯誤,檔案打不開,請檢查檔案名"<<endl; 
		exit(0);
	}
	for(int i=0;i<PROCESS_NUM;i++)
	{
		for(int j=0;j<RESOURCE_NUM;j++)						//修改
			fprintf(fp,"%d  ",Allocation[i][j]);
		fprintf(fp,"\n");
	}
	cout<<"配置設定完成，已更新Allocation_list.txt"<<endl;
	fclose(fp);
}

//恢複試配置設定前狀态
void Recover_TryAllocate()
{
	for(int i=0;i<RESOURCE_NUM;i++)				//不安全，将該程序的資源從預配置設定（試配置設定）狀态退回未配置設定（配置設定前）狀态
	{
		Available[i]=Available[i]+Request_RESOURCE_NEMBER[i];				//可配置設定資源增加（資源退回）
		Allocation[Request_PROCESS][i]=Allocation[Request_PROCESS][i]-Request_RESOURCE_NEMBER[i];	//該程序所請求的對應的資源類别的數目置為預配置設定前的狀态
	   	Need[Request_PROCESS][i]=Need[Request_PROCESS][i]+Request_RESOURCE_NEMBER[i];		//該程序完成所需的資源數置為預配置設定前的狀态
	}
}

//安全性檢測
//傳回值：0：未通過安全性測試； 1：通過安全性測試
int Test_Safty()
{                        
	//請完成安全性檢測算法的程式設計
	int i,j;
	int Work[MAX_RESOURCE];	//定義工作向量
	for(i=0;i<RESOURCE_NUM;i++){
		Work[i]=Available[i];
	}
	bool Finish[MAX_PROCESS];	// 定義布爾向量
	for(i=0;i<PROCESS_NUM;i++){
		Finish[i]=false;
	} 
	int safe[MAX_RESOURCE];	// 用于儲存安全序列
	bool found=false;	//判斷在一輪查找中是否找到符合條件的程序 
	int FinishCount=0;		//找到滿足條件的程序	i 的數目 
	while(FinishCount<5){
		for(i=0;i<PROCESS_NUM;i++){
			if(Finish[i]==true){ //	檢查是否滿足條件		Finish[i]==false 
				continue;
			} 
			bool HasResource=true;
			for(j=0;j<RESOURCE_NUM;j++){	// 檢查是否滿足條件	Need[i]<=Work 
				if(Need[i][j]>Work[j]){
					HasResource=false;
				} 
				if(HasResource){
					for(j=0;j<RESOURCE_NUM;j++){
						Work[j]=Work[j]+Allocation[i][j];
					} 
					Finish[i]=true;
					safe[FinishCount]=i;
					FinishCount++; 
					found=true;
				}
			} 
		}
		if(found){
			found=false;
		}
		else{
			break;
		} 	
	}
	for(i=0;i<PROCESS_NUM;i++){	// 判斷是否所有程序滿足	Finish[i]==true
		if(Finish[i]==true){
			continue;
		} 
		else{
			cout<<" 未通過安全性測試，不配置設定	"<<endl;
			return 0;
		}
	}
	cout<<'\n'<<" 找到一個安全序列	:";
	for(i=0;i<PROCESS_NUM;i++){		//列印安全序列
		cout<<"P"<<safe[i]; 
		if(i!=PROCESS_NUM-1){
			cout<<"--->";
		} 	
	}
	cout<<'\n'<<" 已認證安全性測試	!"<<endl;
	return 1;
}


void RunBanker(){              //執行銀行家算法
	cout<<endl;
	cout<<"開始執行銀行家算法..."<<endl;


	for(int i=0;i<RESOURCE_NUM;i++)  //檢查是否滿足條件Request<=Need
		if(Request_RESOURCE_NEMBER[i]>Need[Request_PROCESS][i])
		{
			cout<<"\n第"<<Request_PROCESS<<"個程序請求資源不成功"<<endl;
			cout<<"原因：超出該程序尚需的資源的最大數量!"<<endl;
			return;
		}
	for(int i=0;i<RESOURCE_NUM;i++)   //檢查是否滿足條件Request<=Available
		if(Request_RESOURCE_NEMBER[i]>Available[i])
		{
			cout<<"\n第"<<Request_PROCESS<<"個程序請求資源不成功"<<endl;
			cout<<"原因：系統中無足夠的資源!"<<endl;
			return;
		}
		else{
			//試配置設定，更新各相關資料結構
			Available[i]=Available[i]-Request_RESOURCE_NEMBER[i];
		    Allocation[Request_PROCESS][i]=Allocation[Request_PROCESS][i]+Request_RESOURCE_NEMBER[i];
	   	    Need[Request_PROCESS][i]=Need[Request_PROCESS][i]-Request_RESOURCE_NEMBER[i];
		}
	cout<<endl<<"試配置設定完成..."<<endl;

	if(Test_Safty())    //使用安全性算法檢查，若滿足，則正式配置設定
		Allocate_Source();
	else                //否則恢複試配置設定前狀态
		Recover_TryAllocate();
}


 
int main()
{
	char c;
	Read_Available_list();
	Read_Max_list();
	Read_Allocation_list();
	Set_Need_Available();
	PrintInfo();
	while(1)
	{
		Read_Request();
		RunBanker();
		cout<<"\n\n需要繼續嗎？（y-繼續；n-終止）";
		cin>>c;
		if(c=='n')
			break;
		cout<<endl<<endl;
		PrintInfo();
	}
	return 0;
}