[算法]操作系统进程通信(预防死锁)算法 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*/