banker.c

操作系统课程设计

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

typedef int BOOL;
#define TRUE 1
#define FALSE 0

int ResCnt, PsCnt;
int * Available = NULL;
int ** Max = NULL;
int ** Allocation = NULL;
int ** Need = NULL;
int * Request = NULL;
int * Work = NULL;
BOOL * Finish = NULL;
int * SafeSeq = NULL;

void Init(char *);
void Clear();
BOOL Banker(int);
BOOL SafeAlg();

int main()
{
	int pi, res;
	int i, j;
	Init("res.txt");

	printf("请输入要申请资源的进程号:(%d~~%d)\n", 0, PsCnt - 1);
	do{
		printf(">");
		res = scanf("%d", &pi);
		rewind(stdin);
		printf("\n");
	}while(res == 0 || pi < 0 || pi >= PsCnt);

	printf("当前可用资源数:\n");
	for(i = 0; i < ResCnt - 1; ++i)
	{
		printf("%d ", Available[i]);
	}
	printf("%d\n", Available[i]);

	printf("请输入请求的资源数:\n");
	for(j = 0; j < ResCnt; ++j)
	{
		printf("请求资源 %d : ", j);
		do{
			printf(">");
			res = scanf("%d", &Request[j]);
			rewind(stdin);
			printf("\n");
		}while(res == 0 || Request[j] < 0);
	}

	Banker(pi);

	Clear();
}

/* 银行家算法 */
BOOL Banker(int pi)
{
	int i, j;

	for(j = 0; j < ResCnt; ++j)
	{
		if(Request[j] > Need[pi][j])
		{
			printf("进程: %d 需要的资源超过了它所宣布的最大值\n");
			return FALSE;
		}
	}

	for(j = 0; j < ResCnt; j++)
	{
		if(Request[j] > Available[j])
		{
			printf("尚没有足够的资源，进程: %d 将等待\n", pi);
			return FALSE;
		}
	}

	printf("系统尝试将资源分配给进程: %d\n", pi);

	for(j = 0; j < ResCnt; ++j)
	{
		Available[j] -= Request[j];
		Allocation[pi][j] += Request[j];
		Need[pi][j] -= Request[j];
	}

	if(SafeAlg())
	{
		printf("此次分配是安全的，安全序列为:\n");
		for(i = 0; i < PsCnt; ++i)
			printf("%d ", SafeSeq[i]);

		printf("\n");

		return TRUE;
	}
	else
	{
		printf("此次资源分配不安全，请求失败\n");

		for(j = 0; j < ResCnt; ++j)
		{
			Available[j] += Request[j];
			Allocation[pi][j] -= Request[j];
			Need[pi][j] += Request[j];
		}

		return FALSE;
	}
}

/* 安全性算法 */
BOOL SafeAlg()
{
	int i, j, k;

	k = 0;

	for(i = 0; i < PsCnt; ++i)
		Finish[i] = FALSE;
	for(j = 0; j < ResCnt; ++j)
		Work[j] = Available[j];

	for(i = 0; i < PsCnt; ++i)
	{
		if(Finish[i] == TRUE)
			continue;
		else
		{
			for(j = 0; j < ResCnt; ++j)
			{
				if(Need[i][j] > Work[j])
					break;
			}
			if(j == ResCnt)
			{
				for(j = 0; j < ResCnt; ++j)
					Work[j] += Allocation[i][j];
				Finish[i] = TRUE;
				SafeSeq[k++] = i;
				i = -1; /* 从头开始查找 */
			}
		}

		/* 已找到安全序列 */
		if(k == PsCnt)
			break;
	}	/* End of for */

	if(k == PsCnt)
		return TRUE;
	else
		return FALSE;
}

void Init(char * file)
{
	int i, j;

	FILE * fp = NULL;
	fp = fopen(file, "r");
	if(NULL == fp)
	{
		printf("Open file: %s failed: %s\n", file, strerror(errno));
		exit(1);
	}

	printf("Reading total count of resource...\n");
	fscanf(fp, "%d", &ResCnt);
	printf("Resource count: %d\n", ResCnt);

	Available = (int *)malloc(ResCnt * sizeof(int));
	Request = (int *)malloc(ResCnt * sizeof(int));
	Work = (int *)malloc(ResCnt * sizeof(int));
	
	printf("Reading initialize available count of resource...\n");
	for(i = 0; i < ResCnt; ++i)
		fscanf(fp, "%d", &Available[i]);
	printf("Initialize count: ");
	for(i = 0; i < ResCnt - 1; ++i)
	{
		printf("%d ", Available[i]);
	}
	printf("%d\n", Available[i]);

	printf("Reading the count of process(s)...\n");
	fscanf(fp, "%d", &PsCnt);
	printf("Process count: %d\n", PsCnt);

	Max = (int **)malloc(PsCnt * sizeof(int *));
	Allocation = (int **)malloc(PsCnt * sizeof(int *));
	Need = (int **)malloc(PsCnt * sizeof(int *));
	Finish = (int *)malloc(PsCnt * sizeof(BOOL));
	SafeSeq = (int *)malloc(PsCnt * sizeof(int));

	for(i = 0; i < PsCnt; ++i)
	{
		Max[i] = (int *)malloc(ResCnt * sizeof(int));
		Allocation[i] = (int *)malloc(ResCnt * sizeof(int));
		Need[i] = (int *)malloc(ResCnt * sizeof(int));
	}

	printf("Reading max needed and allocated resource of all process...\n");
	for(i = 0; i < PsCnt; ++i)
	{
		for(j = 0; j < ResCnt; ++j)
			fscanf(fp, "%d", &Max[i][j]);
		for(j = 0; j < ResCnt; ++j)
			fscanf(fp, "%d", &Allocation[i][j]);
	}

	for(i = 0; i < PsCnt; ++i)
	{
		for(j = 0; j < ResCnt; ++j)
			Need[i][j] = Max[i][j] - Allocation[i][j];
	}

	printf(" Process Max  Allocation  Need\n");
	printf("----------------------------------\n");
	for(i = 0; i < PsCnt; ++i)
	{
		printf("Process: %d  ", i);
		for(j = 0; j < ResCnt; ++j)
			printf("%d ", Max[i][j]);
		printf("  ");
		for(j = 0; j < ResCnt; ++j)
			printf("%d ", Allocation[i][j]);
		printf("  ");
		for(j = 0; j < ResCnt; ++j)
			printf("%d ", Need[i][j]);
		printf("\n");
	}
	printf("----------------------------------\n");

	fclose(fp);
}

/* 释放申请的内存 */
void Clear()
{
	int i;

	if(NULL != Available)
	{
		free(Available);
		Available = NULL;
	}
	if(NULL != Request)
	{
		free(Request);
		Request = NULL;
	}
	if(NULL != Work)
	{
		free(Work);
		Work = NULL;
	}
	if(NULL != Finish)
	{
		free(Finish);
		Finish = NULL;
	}
	if(NULL != SafeSeq)
	{
		free(SafeSeq);
		SafeSeq = NULL;
	}

	for(i = 0; i < PsCnt; ++i)
	{
		if(NULL != Max)
		{
			if(NULL != Max[i])
				free(Max[i]);
		}

		if(NULL != Allocation)
		{
			if(NULL != Allocation[i])
				free(Allocation[i]);
		}

		if(NULL != Need)
		{
			if(NULL != Need[i])
				free(Need[i]);
		}
	}

	if(NULL != Max)
	{
		free(Max);
		Max = NULL;
	}
	if(NULL != Allocation)
	{
		free(Allocation);
		Allocation = NULL;
	}
	if(NULL != Need)
	{
		free(Need);
		Need = NULL;
	}
}