死锁(C代码)

建站整整三个月,终于要发第一篇了~

//////////////////////////////////////////////////////////////
//author : superfish
//date : 2015/11/14
//name : deadlock.h
//////////////////////////////////////////////////////////////
#ifndef _DEADLOCK_H
#define _DEADLOCK_H
 
#define TRUE 1
#define FALSE 0
#define WAIT_1 -1
#define WAIT_2 -2
#define BEYOND -3
 
typedef struct
{   //银行结构体
	int *Available;   //长m的向量,表示每种资源现有的实例数量
	int **Max;        //n*m的矩阵,定义每个进程的最大需求
	int **Allocation; //n*m的矩阵,定义每个进程现在所分配的各种资源类型的实例数量
	int **Need;       //n*m的矩阵,表示每个进程还需要的剩余的资源
}BANK;
 
typedef struct
{   //请求状态结构体
	int *Available;   //长m的向量,表示各种资源的可用实例
	int **Allocation; //n*m的矩阵,表示当前各进程的资源非配情况
	int **Request;    //n*m的矩阵,表示当前各进程的资源请求情况
}REQUEST;
 
//vectorfunc.c
int is_zero(int * X, int n);
int is_be(int * X, int * Y, int n);
int * add_vector(int * X, int * Y, int n);
int * minu_vector(int * X, int * Y, int n);
 
//banker.c
BANK * init_bank(int * available, int ** max, int ** allocation, int ** need);
int * is_safe(BANK * pbank);
int allocate_source(BANK * pbank, int * Request, int i);
 
//deadlock_detection.c
REQUEST * init_request(int * available, int ** allocation, int ** request);
int * deadlock_detection(REQUEST * prequest);
#endif
 
 
////////////////////////////////////////////////////////////////
//author : superfish
//date : 2015/11/14
//name : vectorfunc.c
////////////////////////////////////////////////////////////////
 
int is_zero(int * X, int n)
{   //判断向量X是否为零向量
	int i;
	for(i = 0;i < n;i++){
		if(X[i] != 0){
			return FALSE;
		}
	}
 
	return TRUE;
}
 
int is_be(int * X, int * Y, int n)
{   //判断向量X是否小于等于向量Y,n为两者长度
	int i;
	for(i = 0;i < n;i++){
		if(X[i] > Y[i]){
			return FALSE;
		}
	}
 
	return TRUE;
}
 
int * add_vector(int * X, int * Y, int n)
{   //定义向量加法,n为向量长度
	int i;
	int *result = (int *)malloc(n * sizeof(int));
	for(i = 0;i < n;i++){
		result[i] = X[i] + Y[i];
	}
	return result;
}
 
int * minu_vector(int * X, int * Y, int n)
{   //定义向量减法,n为向量长度
	int i;
	int * result = (int *)malloc(n * sizeof(int));
	for(i = 0;i < n;i++){
		result[i] = X[i] - Y[i];
	}
	return result;
}
 
 
////////////////////////////////////////////////////////////////
//author : superfish
//date : 2015/11/14
//name : banker.c
////////////////////////////////////////////////////////////////
 
#include <stdlib.h>
#include "deadlock.h"
 
BANK * init_bank(int * available, int ** max, int ** allocation, int ** need)
{   //初始化BANK结构体
	BANK *pbank;
	pbank = (BANK *)malloc(sizeof(BANK));
 
	pbank->Available = available;
	pbank->Max = max;
	pbank->Allocation = allocation;
	pbank->Need = need;
 
	return pbank;
}
 
int * is_safe(BANK * pbank)
{   //安全性算法,判断系统是否处于安全状态
	int *Work, *Finish, *Result;
	int i, j, n, m, flag;
 
	j = 0;
	flag = 0;
	Work = pbank->Available;
	m = strlen(Work);
	n = strlen(pbank->Max);
	Finish = (int *)malloc(n * sizeof(int));
	Result = (int *)malloc(n * sizeof(int));
	for(i = 0;i < n;i++){
		Finish[i] = FALSE;
	}
 
	while(TRUE){
		for(i = 0;i < n;i++){
			if(!Finish[i] && is_be((pbank->Need)[i], Work, m)){
				Work = add_vector(Work, (pbank->Allocation)[i], m);
				Finish[i] = TRUE;
 
				//把该进程放入结果队列
				Result[j] = i;
				j++;
				break;
			}
			flag = 1; //没找到满足条件的进程
		}
		if(flag) break;
	}
 
	for(i = 0;i < n;i++){
		if(!Finish[i]){ //没有安全的进程序列
			free(Finish);
			free(Result);
			return NULL;
		}
	}
 
	free(Finish);
	return Result;
}
 
int allocate_source(BANK * pbank, int * Request, int i)
{   //资源分配,先试分配然后判断系统是否安全,i为申请资源的进程编号
	int m;
	m = strlen(Request);
 
	if(!is_be(Request, (pbank->Need)[i], m)){ //超过了其最大请求,报错
		return BEYOND;
	}else if(is_be(Request, pbank->Available, m)){ //没有可用的资源,需要等待
		return WAIT_2;
	}else{ 
	    //资源试分配
		pbank->Available = minu_vector(pbank->Available, Request, m);
		(pbank->Allocation)[i] = add_vector((pbank->Allocation[i]), Request, m);
		(pbank->Need)[i] = minu_vector((pbank->Need)[i], Request);
 
		if(!is_safe(pbank)){ //试分配后发现系统不安全,需要等待并恢复原来的分配状态
			pbank->Available = add_vector(pbank->Available, Request, m);
			(pbank->Allocation)[i] = minu_vector((pbank->Allocation[i]), Request, m);
			(pbank->Need)[i] = add_vector((pbank->Need)[i], Request);
 
			return WAIT_1;
		}else{ //分配成功
			return TRUE
		}
	}
}
 
 
//////////////////////////////////////////////////////////////
//author : superfish
//date : 2015/11/14
//name : deadlock_detection.c
//////////////////////////////////////////////////////////////
 
#include <stdlib.h>
#include "deadlock.h"
 
REQUEST * init_request(int * available, int ** allocation, int ** request)
{   //初始化REQUEST结构体
	REQUEST *prequest;
	prequest = (REQUEST *)malloc(sizeof(REQUEST));
 
	prequest->Available = available;
	prequest->Allocation = allocation;
	prequest->Request = request;
 
	return REQUEST;
}
 
int * deadlock_detection(REQUEST * prequest)
{   //死锁检测算法
	int *Work, *Finish, *Result;
	int i, j, n, m, flag, isdead;
 
	isdead = 0;
	flag = 0;
	j = 0;
	Work = prequest->Available;
	m = strlen(Work);
	n = strlen(prequest->Allocation);
	Finish = (int *)malloc(n * sizeof(int));
	Result = (int *)malloc(n * sizeof(int));
	for(i = 0;i < n;i++){
		if(!is_zero((prequest->Allocation)[i], m)){
			Finish[i] = FALSE;
		}else{
			Finish[i] = TRUE;
		}
	}
 
	while(TRUE){
		for(i = 0;i < n;i++){
			if(!Finish[i] && is_be((prequest->Request)[i], Work, m)){
				Work = add_vector(Work, (prequest->Allocation)[i], m);
				Finish[i] = TRUE;
				break;
			}
			flag = 1; //表示没有满足的进程
		}
		if(flag) break;
	}
 
	for(i = 0;i < n;i++){
		if(!Finish[i]){
			isdead = 1; //表明系统是死锁,将返回可能死锁的进程队列
 
			//把该进程添加到可能死锁进程队列中
			Result[j] = i;
			j++;
		}
	}
 
	free(Finish);
 
	if(isdead == 1){
		return Result;
	}else{
		free(Result);
		return NULL; //返回NULL表示系统无死锁
	}
}