操作系統(tǒng)死鎖檢測算法

　　操作系統(tǒng)中死鎖是可以進(jìn)行檢測的，運(yùn)用相關(guān)的算法我們可以檢測死鎖從而找到解決方法。下面由學(xué)習(xí)啦小編為大家整理了操作系統(tǒng)的死鎖檢測算法的相關(guān)知識，希望對大家有幫助!

　　操作系統(tǒng)死鎖檢測算法

　　模擬死鎖檢測算法

　　1. 輸入：

　　“資源分配表”文件，每一行包含資源編號、進(jìn)程編號兩項(均用整數(shù)表示，并用空格分隔開)，記錄資源分配給了哪個進(jìn)程。

　　“進(jìn)程等待表”文件，每一行包含進(jìn)程編號、資源編號兩項(均用整數(shù)表示，并用空格分隔開)，記錄進(jìn)程正在等待哪個資源。

　　下面是一個示例：

　　資源分配表：

　　1 1

　　2 2

　　3 3

　　進(jìn)程等待表：

　　1 2

　　2 3

　　3 1

　　2. 處理要求：

　　程序運(yùn)行時，首先提示“請輸入資源分配表文件的文件名：”;再提示“請輸入進(jìn)程等待表文件的文件名：”。

　　輸入兩個文件名后，程序?qū)⒆x入兩個文件中的有關(guān)數(shù)據(jù)，并按照死鎖檢測算法進(jìn)行檢測。

　　3. 輸出要求：

　　第一行輸出檢測結(jié)果：有死鎖 或 無死鎖。

　　第二行輸出進(jìn)程循環(huán)等待隊列，即進(jìn)程編號(如果有死鎖)。

　　4. 文件名約定

　　提交的源程序名字：resourceXXX.c或者resourceXXX.cpp(依據(jù)所用語言確定)

　　輸入文件名字：可由用戶指定

　　結(jié)果輸出到resultXXX.txt中

　　其中：XXX為賬號。

　　5. 死鎖檢測算法：當(dāng)任一進(jìn)程Pj申請一個已被其他進(jìn)程占用的資源ri時，進(jìn)行死鎖檢測。檢測算法通過反復(fù)查找進(jìn)程等待表和資源分配表，

　　來確定進(jìn)程Pj對資源ri的請求是否導(dǎo)致形成環(huán)路，若是，便確定出現(xiàn)死鎖。

　　6. 測試說明：測試教師將事先準(zhǔn)備好一組文件(格式為*.txt)，從中為每個程序隨機(jī)指定一至三個作為輸入文件

　　(被測試者需從鍵盤輸入指定文件的文件名)，并查看程序輸出結(jié)果。

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

　　VC++調(diào)試通過

　　(C)copyright by Neo

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

　　#include<stdio.h>

　　#include<iostream.h>

　　#include<string.h>

　　const int MAXQUEUE=100; //定義表的最大行數(shù)

　　typedef struct node{

　　int resource;

　　int process;

　　}cell;

　　cell occupy[MAXQUEUE];

　　int occupy_quantity;

　　cell wait[MAXQUEUE];

　　int wait_quantity;

　　//初始化函數(shù)

　　void initial()

　　{

　　int i;

　　for(i=0;i<MAXQUEUE;i++){

　　occupy[i].process=-1;

　　occupy[i].resource=-1;

　　wait[i].process=-1;

　　wait[i].resource=-1;

　　}

　　occupy_quantity=0;

　　wait_quantity=0;

　　}

　　//讀數(shù)據(jù)文件

　　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<<"請輸入進(jìn)程等待表文件的文件名:"<<e

　　ndl;

　　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++;

　　}

　　}

　　//輸出所讀入的數(shù)據(jù)

　　cout<<endl<<endl<<"輸出所讀入的數(shù)據(jù)"<<endl;

　　cout<<"━━━━━━━━━━━━━━━━━━━━━━━"<<endl;

　　cout<<"資源分配表"<<endl;

　　cout<<"資源編號 進(jìn)程編號"<<endl;

　　for(i=0;i<occupy_quantity;i++){

　　cout<<" "<<occupy[i].resource<<" "<<occupy[i].process<<endl;

　　}

　　cout<<"───────────────────────"<<endl;

　　cout<<"進(jìn)程等待表"<<endl;

　　cout<<"進(jìn)程編號 資源編號"<<endl;

　　for(i=0;i<wait_quantity;i++){

　　cout<<" "<<wait[i].resource<<" "<<wait[i].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[i][j]=0;

　　table1[i][j]=0;

　　}

　　}

　　//先找到進(jìn)程最大編號

　　max_process=-1;

　　for(i=0;i<occupy_quantity;i++){

　　if(occupy[i].process>max_process){

　　max_process=occupy[i].process;

　　}

　　}

　　for(i=0;i<wait_quantity;i++){

　　if(wait[i].process>max_process){

　　max_process=wait[i].process;

　　}

　　}

　　for(i=0;i<wait_quantity;i++){

　　for(j=0;j<occupy_quantity;j++){

　　if(wait[i].resource==occupy[j].resource){

　　table[wait[i].process][occupy[j].process]=1;

　　table1[wait[i].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[i][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[i][j]=table[i][j]||(table[i][k]&&table[k][j]);

　　}

　　}

　　}

　　cout<<"檢測后的等待占用表:"<<endl;

　　for(i=0;i<max_process+1;i++){

　　for(j=0;j<max_process+1;j++){

　　cout<<table[i][j]<<" ";

　　}

　　cout<<endl;

　　}

　　flag=-1;

　　for(i=0;i<max_process+1;i++){

　　if(table[i][i]==1){

　　flag=i;

　　break;

　　}

　　}

　　cout<<endl<<endl<<"檢測結(jié)果"<<endl;

　　cout<<"───────────────────"<<endl;

　　if(flag!=-1){

　　cout<<"存在死鎖"<<endl;

　　cout<<"進(jìn)程循環(huán)等待隊列:";

　　p=flag; //存在進(jìn)程循環(huán)等待隊列的那一進(jìn)程

　　//進(jìn)程循環(huán)等待隊列中的所有進(jìn)程是table表中的這一行是1的進(jìn)程,只是順序要再確定

　　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;

　　}

　　}

　　//顯示版權(quán)信息函數(shù)

　　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();

　　}