[算法]操作系統進程通信(預防死鎖)算法 Dijkstra銀行家算法 C語言實現

今天完成昨天的算法，銀行家算法，這個大家如果知道操作系統這門課程的話應該會明白，昨天一直忙於複習，今天也是，不過下午還是完成了基本調試，調試環境 GCC 和 TC，現在我把代碼奉獻給大家

銀行家算法說明：最早由算法大師迪傑斯特拉 (Edsger Dijkstra) 提出，銀行家算法，顧名思義，它的原理來源於銀行系統的存貸款發放管理，即銀行（系統）要將一定的款項（資源）貸款（分配）給 N 個人（進程），當然不需要考慮信用問題 < '_'>，在已經發放了一定的金額後，要使得銀行的每一次放款（分配資源）都能使得銀行（系統）的運行安全（預防死鎖）（可以這麼理解吧），因此銀行家要對現有的資金進行合理分配發放，基本要求要銀行必須保留一定的存款不能低於一定的限度（臨界資源），同時又不能不放貸款不然會讓客戶 “餓死”（進程饑餓），客戶在使用完貸款後要返還（釋放）這筆貸款，當然是沒有利息的，然後銀行要再分配給客戶，直到滿足客戶的所有貸款請求

具體可以參照http://baike.baidu.com/view/93075.htm

代碼如下：

/*
* 銀行家算法
*code CG 2008 01 05
*/

#include"stdio.h"

#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int M ; /* 總進程數 */
int N ; /* 資源種類 */

int ALL_RESOURCE [W];/* 各種資源的數目總和 */
int MAX [W][R]; /*M 個進程對 N 類資源最大資源需求量 */
int AVAILABLE [R]; /* 系統可用資源數 */
int ALLOCATION [W][R]; /*M 個進程已經得到 N 類資源的資源量 */
int NEED [W][R]; /*M 個進程還需要 N 類資源的資源量 */
int REQUEST [R]; /* 請求資源個數 */

/*
* 函數名：output
* 功能：輸出資源分配情況
*/
void output()
{
int i,j;
printf("All Resource");
for(j = 0 ; j < N ;j++)
printf("R%d:%dn", j , ALL_RESOURCE[j]);

printf("Resource Available:n");
for(j = 0 ; j < N ; j++)
	printf("R%d:%dn", j , AVAILABLE\[j\]);

printf("Process Resource Needed:n");

printf("| PID |");
for(j = 0 ; j < N ; j++)
	printf(" R%d |", j);
printf("n");

for(i = 0 ; i < M ; i++)
	for(i = 0 ; i < M ; i++)
	{
		printf("|%-5d|", i);
			for(j = 0 ; j < N ; j++)
				printf("%-4d|", NEED\[i\]\[j\]);
		printf("n");
}

printf("Process Resource Allocated:n");

printf("| PID |");
for(j = 0 ; j < N ; j++)
	printf(" R%d |", j);
printf("n");

for(i = 0 ; i < M ; i++)
{
 printf("|%-5d|", i);
	for(j = 0 ; j < N ; j++)
		printf("%-4d|", ALLOCATION\[i\]\[j\]);
 printf("n");
}

}/*output*/

/*
* 函數名：modify
* 功能：改變可用資源和已經拿到資源和還需要的資源的值
* 參數：int k 修改編號為 K 的 P 的數據
*/
void modify(int k)
{
int j;
for (j = 0 ; j < N ; j++){/* 修改數據 */
AVAILABLE [j] = AVAILABLE [j] - REQUEST [j];/* 修改可用資源 */
ALLOCATION [k][j] = ALLOCATION [k][j] + REQUEST [j];/* 修改分配資源 */
NEED [k][j] = NEED [k][j] - REQUEST [j];/* 修改資源需求 */
}
}

/*
* 函數名：undo
* 功能：還原可用資源和已經拿到資源和還需要的資源的值
* 參數：參數：int k 修改編號為 K 的 P 的數據
*/
void undo(int k){
int j;
for (j = 0 ; j < N ; j++){/* 修改數據 */
AVAILABLE [j] = AVAILABLE [j] + REQUEST [j]; /* 修改可用數據 */
ALLOCATION [k][j] = ALLOCATION [k][j] - REQUEST [j]; /* 修改分配的資源 */
NEED [k][j] = NEED [k][j] + REQUEST [j];/* 修改資源需求 */
}
}
/*
* 函數名：chkerr
* 功能：檢查修改操作是否安全
*/
int chkerr(int s){
int WORK , FINISH[W];
int i , j;
for (i = 0 ; i < M ; i++)/* 清空 FINISH*/
FINISH[i] = FALSE;
for (j = 0 ; j < N ; j++){/* 逐一檢查 */
WORK = AVAILABLE[j];
i = s;
do{
if (FINISH [i] == FALSE && NEED [i][j] <= WORK){/* 符合條件？*/
WORK = WORK + ALLOCATION[i][j];
FINISH[i] = TRUE;
i = 0;
}
else
i++;
}while(i
for (i = 0 ; i < M ; i++)/* 只要一個不滿足，不安全 */
if(FINISH[i] == FALSE){
printf("Error : UnSafe Allocation!n");
return 1;
}
}
printf("OK : Allocation OKn");
return 0;
}

/*
* 函數名：bank
* 功能：銀行家算法的實現
*/
void bank()
{
int i , j;
int flag = TRUE;
printf("Use Ctrl+C break..n");
while(TRUE){
i = -1;
while(i < 0 || i >= M)
{
printf("Input Process to Allocat PID=");
scanf("%d", &i);
if(i < 0 || i >= M)
printf("Error: Invalid Input!n");
}
printf("Input Resource Needn");
for (j = 0 ; j < N ; j++)
{
printf("R%d=", j);
scanf("%d", &REQUEST[j]);
if (REQUEST [j] > NEED [i][j]){/* 請求的資源數大於請求資源 */
printf("Error: Invalid Input!n");
flag = FALSE;
}
else{
if (REQUEST [j]>AVAILABLE [j]){/* 若請求的資源數大於可用資源數 */
printf("Error: Invalid Input!n");
flag = FALSE;
}
}/*else*/
}/*for*/

	 if(flag)
	 {
		modify(i); /\*修改資源數\*/
		if(chkerr(i)){/\*安全?\*/
			undo(i); /\*恢復資源數\*/
			output();/\*輸出\*/
		}
		else
			output(); /\*輸出\*/
		}
	 else
		output();
}/\*while\*/

}/*bank*/

/* 主函數 */
int main(){
int i , j , p;
printf ("Input Process Numbers M=");/* 進程數量 */
scanf("%d", &M);
printf ("Input Resource Category N=");/* 資源種類 */
scanf("%d", &N);
printf("Input Number of All Resource each Category");/* 資源數目 */
for(i = 0 ; i < N ; i++)
scanf("%d", &ALL_RESOURCE[i]);
printf("Input Max Resource Process Need");/* 最大資源需求 */
for (i = 0 ; i < M ; i++){
for (j = 0 ; j < N ; j++){
do{
scanf("%d", &MAX[i][j]);
if (MAX [i][j] > ALL_RESOURCE [j])/* 大於最大可用？*/
printf("nError: Invalid Input!n");
}while (MAX[i][j] > ALL_RESOURCE[j]);
}
}/*for*/

printf("Input Resource Process Allocated:n");
for (i = 0 ; i < M ; i++){
	for (j = 0 ; j < N ; j++){
		do{
			scanf("%d", &ALLOCATION\[i\]\[j\]);
			if (ALLOCATION\[i\]\[j\] > MAX\[i\]\[j\])/\*大於最大需求？\*/
				printf("nError: Invalid Input!n");
		}while (ALLOCATION\[i\]\[j\] > MAX\[i\]\[j\]);
	}
 }/\*for\*/

for(j = 0 ; j < N ; j++){
	p = ALL\_RESOURCE\[j\];
	for(i = 0 ; i < M ; i++){
		p -= ALLOCATION\[i\]\[j\];/\*減去已經分配資源\*/
		AVAILABLE\[j\] = p;
		if(AVAILABLE\[j\]<0)
			AVAILABLE\[j\] = 0;/\*清理數據\*/
	}/\*for\*/
 }/\*for\*/
for (i = 0 ; i < M ; i++)
	for(j = 0 ; j < N ; j++)
		NEED\[i\]\[j\] = MAX\[i\]\[j\] - ALLOCATION\[i\]\[j\];/\*求還需要的資源\*/
output();
bank();/\*銀行家算法\*/
return 0;

}/*main*/