银行家算法C语言

admin 管理员组

文章数量: 1184232

操作系统实验——银行家算法

相关数据结构:
可利用资源向量Available:这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。
最大需求矩阵Max: 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation: 这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
需求矩阵Need: 这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
满足 Need［i,j］=Max［i,j］-Allocation［i,j］
银行家算法描述
设Request i是进程Pi的请求向量，如果Request i［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Request［j］;
Allocation［i,j］∶=Allocation［i,j］+Request［j］;
Need［i,j］∶=Need［i,j］-Request［j］;
(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

整体思路如下:


(1) 设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true
(2) 从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false; ② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4）
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］∶=Work［i］+Allocation［i,j］;
Finish［i］∶=true;
go to step 2;
(4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态,这里的判断需要技巧。

C语言代码如下

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max 10
int PN;//Process number 进程数量
int RT;//Resource types 资源种类
int Resourse[max];//资源
int Request[max];//申请
int Avaliable[max];//系统剩余资源
int	MAX[max][max];//进程最大资源需求
int Need[max][max];//进程目前资源需求
int Allocation[max][max];//进程已分配资源
int SafeOrder[max];//安全序列
int choice;//进程申请选择
void Menu()
{
	printf( "------------------Banker-----------------------\n");
	printf("*              1.初始化数据                      *\n");
	printf("*              2.检验T0时刻安全性                *\n");
	printf("*              3.资源申请                        *\n");
	printf("*              4.退出                           *\n");
	printf("------------------------------------------------\n");
}
void Input(int a, int b, int c[max][max])
{
	int i;
	for (i = 0; i < b; i++)
		if (i == 0) printf("   R%d ", i + 1);
		else printf("R%d ", i + 1);
		printf("\n");
		for (i = 0; i < a; i++)
		{
			printf("P%d  ", i + 1);
			for (int j = 0; j < b; j++)
				scanf("%d", &c[i][j]);
		}
}
void init()
{
	int i,j;
	printf("初始化: 请输入进程个数和资源总类: ");
	scanf("%d%d", &PN,&RT);
	printf("请输入各类资源数量: \n");
	for (i = 0; i < RT; i++)
		printf("R%d ", i + 1);
	printf("\n");
	for (i = 0; i < RT; i++)
		scanf("%d", &Resourse[i]);
	printf("请输入每个进程对每种资源的最大需求量:\n");
	Input(PN, RT, MAX);
	printf("请输入各类资源已分配量:\n");
	Input(PN, RT, Allocation);
	for (i = 0; i < PN; i++)
		for (j = 0; j < RT; j++)
			Need[i][j] = MAX[i][j] - Allocation[i][j];
	for (i = 0; i < RT; i++)
	{
           int sum[max] = { 0 };
		   for (j = 0; j < PN; j++)
			   sum[i] += Allocation[j][i];
		   Avaliable[i] = Resourse[i] - sum[i];
	}
}
bool  Apply()//进程资源申请
{
	int i;
	printf("选择申请资源的进程: P");
	scanf("%d", &choice);
	printf("输入各类资源申请数量\n");
	for (i = 0; i < RT; i++)
		printf("R%d ", i + 1);
	printf("\n");
	for (i = 0; i < RT; i++)
		scanf("%d",&Request[i]);
	for (i = 0; i < RT;i++)
		if (Request[i]<=Need[choice - 1][i])
		{
			if (Request[i] > Avaliable[i])
			{
				printf("资源不足！"); return false;
			}
		}
		else
		{
          printf("申请超出所需！"); return false;
		}	
	return true;
}
bool IsSafe()
{
	int i,j,k=0,count,Work[max];
	bool Finish[max];
	for (i = 0; i < PN; i++)
		Finish[i] = false;
	for (i = 0; i < RT; i++)
		Work[i] = Avaliable[i];
	for (i = 0; i < PN; i++)
{
		 count=0 ,j=0;
		if (Finish[i] == false)
	    {
			for (j = 0; j < RT; j++)
				if (Need[i][j]<=Work[j])
					count++;
		}
		if (count==RT)
		{
			for (j = 0; j<RT; j ++)
				Work[j] += Allocation[i][j];
			Finish[i] = true;
			SafeOrder[k++] = i+1;
			i = -1;//关键,也可以对i取模
		}

 }
	for (i = 0; i < PN; i++)
		if (Finish[i] == false)
			return false;
	return true;
}
bool banker()
{
	int i = choice - 1, j;
		for (j = 0; j < RT; j++)//试分配
		{
			Avaliable[j] -= Request[j];
			Allocation[i][j] += Request[j];
			Need[i][j] -= Request[j];
		}
		if (IsSafe()) return true;
		else//操作撤回，回复原来状态
		{
		    for(j=0;j<RT;j++)
		    {
			Avaliable[j] += Request[j];
			Allocation[i][j] -= Request[j];
			Need[i][j] += Request[j];
			}
			return false;
		}
		return true;
}
void printOrder()//输出安全序列
{
	int i;
	for ( i = 0; i < PN; i++)
	{
		if (i == 0)
			printf("P%d", SafeOrder[i]);
		else
			printf("->P%d", SafeOrder[i]);
	}
	printf("\n");
}
void print()
{
	int i, j;
	printf("系统剩余: \n");
	for (i = 0; i < RT; i++)
		printf(" R%d", i + 1);
	printf("\n");
	for (i = 0; i < RT; i++)
		printf("%3d",Avaliable[i]);
	printf("\n系统已分配: \n");
	for (i = 0; i < RT; i++)
		if (i == 0) printf("    R%d", i + 1);
		else printf(" R%d", i + 1);
	printf("\n");
	for (i = 0; i < PN; i++)
	{
			printf("P%d", i + 1);
			for ( j = 0; j < RT; j++)
				printf("%3d", Allocation[i][j]);
			printf("\n");
	}
		printf("系统尚需: \n");
		for (i = 0; i < RT; i++)
			if (i == 0) printf("    R%d", i + 1);
			else printf(" R%d", i + 1);
		printf("\n");
		for (i = 0; i < PN; i++)
		{
				printf("P%d", i + 1);
				for ( j = 0; j < RT; j++)
					printf("%3d", Need[i][j]);
				printf("\n");
		}
}
int  main()
{
	bool flag;
	Menu();
Initialization:init();
	if (IsSafe() == false)
	{
		printf("当前系统状态不安全!\n请重新初始化数据");
		goto Initialization;
	}
	else
	{
			printf("当前系统处于安全状态,安全序列为:  ");
			printOrder();
			print();
	}
	Application: flag=Apply();
	if (flag==false)
	{
		printf("申请失败!请重新申请\n");
		goto Application;
	}
	else
	{
		if (banker() == false)
		{
			printf("资源申请造成系统处于死锁状态!申请失败!请重新申请\n");
			goto Application;
		}
		else
		{
			printf("申请成功!安全序列为:  ");
			printOrder();
			print();
		}
	}
	int n;
	printf("是否还有进程申请资源? 是请输入1,否请输入0 :");
	scanf("%d", &n);
	if (n == 1)
		goto Application;
	return 0;
}

本文标签： 银行家 算法 语言