（十）死鎖檢測算法 

模擬死鎖檢測算法 
1． 輸入： 
“資源分配表”文件，每一行包含資源編號、進程編號兩項（均用整數表示，并用空格分隔開），記錄資源分配給了哪個進程。 
“進程等待表”文件，每一行包含進程編號、資源編號兩項（均用整數表示，并用空格分隔開），記錄進程正在等待哪個資源。 
下面是一個示例： 
資源分配表： 
1 1 
2 2 
3 3 
進程等待表： 
1 2 
2 3 
3 1 
2． 處理要求： 
程序運行時，首先提示“請輸入資源分配表文件的文件名：”；再提示“請輸入進程等待表文件的文件名：”。 
輸入兩個文件名后，程序將讀入兩個文件中的有關數據，并按照死鎖檢測算法進行檢測。 
3． 輸出要求： 
第一行輸出檢測結果：有死鎖 或 無死鎖。 
第二行輸出進程循環等待隊列，即進程編號（如果有死鎖）。 
4． 文件名約定 
提交的源程序名字：resourceXXX.c或者resourceXXX.cpp（依據所用語言確定） 
輸入文件名字：可由用戶指定 
結果輸出到resultXXX.txt中 
其中：XXX為賬號。 
5． 死鎖檢測算法：當任一進程Pj申請一個已被其他進程占用的資源ri時，進行死鎖檢測。檢測算法通過反復查找進程等待表和資源分配表， 
來確定進程Pj對資源ri的請求是否導致形成環路，若是，便確定出現死鎖。 
6． 測試說明：測試教師將事先準備好一組文件（格式為*.txt），從中為每個程序隨機指定一至三個作為輸入文件 
（被測試者需從鍵盤輸入指定文件的文件名），并查看程序輸出結果。 

本程序包括:死鎖檢測算法 


VC++調試通過 

(C)copyright by Neo 

歡迎大家測試 請問題請Email:sony006@163.com*/ 

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

const int MAXQUEUE=100; //定義表的最大行數 

typedef struct node{ 
int resource; 
int process; 
}cell; 

cell occupy[MAXQUEUE]; 
int occupy_quantity; 
cell wait[MAXQUEUE]; 
int wait_quantity; 


//初始化函數 
void initial() 
{ 
int i; 

for(i=0;i<MAXQUEUE;i++){ 
occupy.process=-1; 
occupy.resource=-1; 

wait.process=-1; 
wait.resource=-1; 
} 
occupy_quantity=0; 
wait_quantity=0; 
} 


//讀數據文件 
int readData() 
{ 
FILE *fp; 
char fname[20]; 
int i; 

cout<<"請輸入資源分配表文件的文件名:"<<endl; 
strcpy(fname,"10trouble1.txt"); 
//cin>>fname; 
if((fp=fopen(fname,"r"))==NULL){ 
cout<<"錯誤,文件打不開,請檢查文件名"<<endl; 
return 0; 
} 
else{ 
while(!feof(fp)){ 
fscanf(fp,"%d %d",&occupy[occupy_quantity].resource,&occupy[occupy_quantity].process); 
occupy_quantity++; 
} 
} 

cout<<"請輸入進程等待表文件的文件名:"<<endl; 
strcpy(fname,"10trouble2.txt"); 
//cin>>fname; 
if((fp=fopen(fname,"r"))==NULL){ 
cout<<"錯誤,文件打不開,請檢查文件名"<<endl; 
return 0; 
} 
else{ 
while(!feof(fp)){ 
fscanf(fp,"%d %d",&wait[wait_quantity].process,&wait[wait_quantity].resource); 
wait_quantity++; 
} 
} 

//輸出所讀入的數據 
cout<<endl<<endl<<"輸出所讀入的數據"<<endl; 
cout<<"━━━━━━━━━━━━━━━━━━━━━━━"<<endl; 
cout<<"資源分配表"<<endl; 
cout<<"資源編號 進程編號"<<endl; 

for(i=0;i<occupy_quantity;i++){ 
cout<<" "<<occupy.resource<<" "<<occupy.process<<endl; 
} 
cout<<"───────────────────────"<<endl; 
cout<<"進程等待表"<<endl; 
cout<<"進程編號 資源編號"<<endl; 

for(i=0;i<wait_quantity;i++){ 
cout<<" "<<wait.resource<<" "<<wait.process<<endl; 
} 
return 1; 
} 


//檢測 
void check() 
{ 
int table[MAXQUEUE][MAXQUEUE]; 
int table1[MAXQUEUE][MAXQUEUE]; 

int i,j,k; 
int flag,t,p; 
int max_process; 


//初始化表格 

for(i=0;i<MAXQUEUE;i++){ 
for(j=0;j<MAXQUEUE;j++){ 
table[j]=0; 
table1[j]=0; 
} 
} 

//先找到進程最大編號 
max_process=-1; 
for(i=0;i<occupy_quantity;i++){ 
if(occupy.process>max_process){ 
max_process=occupy.process; 
} 
} 
for(i=0;i<wait_quantity;i++){ 
if(wait.process>max_process){ 
max_process=wait.process; 
} 
} 

for(i=0;i<wait_quantity;i++){ 
for(j=0;j<occupy_quantity;j++){ 
if(wait.resource==occupy[j].resource){ 
table[wait.process][occupy[j].process]=1; 
table1[wait.process][occupy[j].process]=1; 
} 
} 
} 


cout<<"初始等待占用表:"<<endl; 
for(i=0;i<max_process+1;i++){ 
for(j=0;j<max_process+1;j++){ 
cout<<table[j]<<" "; 
} 
cout<<endl; 
} 

cout<<endl; 

for(i=0;i<max_process+1;i++){ 
for(j=0;j<max_process+1;j++){ 
for(k=0;k<max_process+1;k++){ 
table[j]=table[j]||(table[k]&&table[k][j]); 
} 
} 
} 
cout<<"檢測后的等待占用表:"<<endl; 

for(i=0;i<max_process+1;i++){ 
for(j=0;j<max_process+1;j++){ 
cout<<table[j]<<" "; 
} 
cout<<endl; 
} 

flag=-1; 
for(i=0;i<max_process+1;i++){ 
if(table==1){ 
flag=i; 
break; 
} 
} 
cout<<endl<<endl<<"檢測結果"<<endl; 
cout<<"───────────────────"<<endl; 
if(flag!=-1){ 
cout<<"存在死鎖"<<endl; 
cout<<"進程循環等待隊列:"; 

p=flag; //存在進程循環等待隊列的那一進程 
//進程循環等待隊列中的所有進程是table表中的這一行是1的進程,只是順序要再確定 
t=1; 
while(t){ 
cout<<p<<" "; 
for(j=0;j<max_process+1;j++){ 
if(table1[p][j]==1){ 
if(table[j][flag]==1){ 
p=j; 
break; 
} 
} 
} 
if(p==flag)t=0; 
} 
cout<<flag<<endl; 
} 
else{ 
cout<<"不存在死鎖"<<endl; 
} 
} 
//顯示版權信息函數 
void version() 
{ 
cout<<endl<<endl; 

cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl; 
cout<<" ┃　　　　 　死 鎖 檢 測 算 法　 　　　　　　　┃"<<endl; 
cout<<" ┠───────────────────────┨"<<endl; 
cout<<" ┃　 　(c)All Right Reserved Neo　　　 　　　┃"<<endl; 
cout<<" ┃　　　　　　sony006@163.com　　 　　　　　　　┃"<<endl; 
cout<<" ┃　　　　　version 2004 build 1122　　　　　　┃"<<endl; 
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; 
cout<<endl<<endl; 
} 

void main() 
{ 
int flag; 

version(); 

initial(); 

flag=readData(); 

if(flag)check(); 
}