操作系统实验二（银行家算法）

admin 管理员组

文章数量: 887019

实验二 银行家算法
一、实验目的
用高级语言编写和调试一个银行家算法程序，并可以利用银行家算法模拟分配资源以及进行安全性检查。加深对银行家算法的理解。
二、实验指导

1. 银行家算法中的数据结构
   (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。
   (2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
   (3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
   (4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
   Need［i,j］=Max［i,j］-Allocation［i,j］
2. 银行家算法
   设Requesti是进程Pi的请求向量，如果Requesti［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］-Requesti［j］;
   Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
   Need［i,j］∶=Need［i,j］-Requesti［j］;
   (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3. 安全性算法
   (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都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

银行家算法我用到了回溯，将所有的序列找出来

#include<bits/stdc++.h>
using namespace std;
struct PCB
{
	string name;
	int Work[3];
	int Max[3];
	int Allo[3];
	int Need[3];
	int WA[3];
	bool Finish;
} pcb[5];
int num = 3;
PCB safe[5];
int top = 0;
int ifsafe;
int Avalia[3]= {3,3,2};
void menu()
{
	printf("1.初始化\n");
	printf("2.查看当前资源分配表\n");
	printf("3.请求资源\n");
	printf("4.退出\n");
}
void init()
{
	pcb[0]= {"P0",{0,0,0},{7,5,3},{0,1,0},{7,4,3},{0,0,0},false};
	pcb[1]= {"P1",{0,0,0},{3,2,2},{2,0,0},{1,2,2},{0,0,0},false};
	pcb[2]= {"P2",{0,0,0},{9,0,2},{3,0,2},{6,0,0},{0,0,0},false};
	pcb[3]= {"P3",{0,0,0},{2,2,2},{2,1,1},{0,1,1},{0,0,0},false};
	pcb[4]= {"P4",{0,0,0},{4,3,3},{0,0,2},{4,3,1},{0,0,0},false};
}

void output()
{
	printf("\tMax          Allo\t     Need  \t\n");
	for(int i=0; i<5; i++)
	{
		cout<<pcb[i].name;
		for(int j=0; j<3; j++)
		{
			printf("%3d",pcb[i].Max[j]);
		}
		printf("\t");
		for(int j=0; j<3; j++)
		{
			printf("%3d",pcb[i].Allo[j]);
		}
		printf("\t");
		for(int j=0; j<3; j++)
		{
			printf("%3d",pcb[i].Need[j]);
		}
		printf("\n");
	}
	printf("\n\t\t\t\t\tAvalia: ");
	for(int j=0; j<3; j++)
	{
		printf("%3d",Avalia[j]);
	}
	printf("\n");
}
void safeoutput()
{
	printf("    Work          Need\t          Allo            W+A           Finish\t\n");
	for(int i=0; i<5; i++)
	{
		cout<<safe[i].name;
		for(int j=0; j<3; j++)
		{
			printf("%3d",safe[i].Work[j]);
		}
		printf("\t");
		for(int j=0; j<3; j++)
		{
			printf("%3d",safe[i].Need[j]);
		}
		printf("\t");
		for(int j=0; j<3; j++)
		{
			printf("%3d",safe[i].Allo[j]);
		}
		printf("\t");
		for(int j=0; j<3; j++)
		{
			printf("%3d",safe[i].WA[j]);
		}
		printf("\t");
		printf("%3d",safe[i].Finish);
		printf("\n");
	}
	printf("\n");
}
void Run(PCB backup[],int avalia[],int index)
{
	//如果全部都安全，则打印
	int cnt = 0;
	for(int i=0; i<5; i++)
		if(backup[i].Finish == true)
			cnt++;
	if(cnt == 5)
	{
		for(int i=0; i<top; i++)
			cout<<safe[i].name<<" ";
		printf("请求成功!\n");
		safeoutput();
		system("pause");
		ifsafe = 1;
		return ;
	}
	//开始递归寻找
	for(int i = 0; i<5; i++)
	{
		//如果Finish是true或者需要的资源大于已有的资源，则跳过
		int f=1;
		for(int j=0; j<3; j++)
		{
			if(backup[i].Finish == true || backup[i].Need[j]>avalia[j])
			{
				f=0;
				break;
			}
		}
		if(f == 0)
			continue;
		//否则就将当前的Avalia全部给Work，并计算 W+A
		for(int j=0; j<3; j++)
		{
			backup[i].Work[j] = avalia[j];
			backup[i].WA[j] = backup[i].Work[j]+backup[i].Allo[j];
		}
		//置Finish为 true
		backup[i].Finish = true;
		// 压栈
		safe[top++] = backup[i];
		// 递归
		Run(backup,backup[i].WA,i);
		// 回溯
		top--;
		backup[i].Finish = false;

	}
}


void RunBefore(int index,int re[])
{
	int i;
	//请求数是否大于Need
	for(i=0; i<3; i++)
		if(re[i]>pcb[index].Need[i])
			break;
	if(i != 3)
	{
		printf("请求资源数量大于Need数量，分配失败！\n\n");
		return ;
	}
	//请求数大于现有资源数
	for(i=0; i<3; i++)
		if(re[i]>Avalia[i])
			break;
	if(i != 3)
	{
		printf("请求资源数量大于Aailable数量，分配失败！\n\n");
		return ;
	}
	//执行安全性检查算法
	//1.备份
	PCB backup[5];
	int bAvalia[3];
	for(int i=0; i<5; i++)
		backup[i]=pcb[i];
	for(int i=0; i<3; i++)
		bAvalia[i]=Avalia[i];
	//2.成功请求
	for(int i=0; i<3; i++)
	{
		backup[index].Allo[i]+=re[i];
		bAvalia[i]-=re[i];
		backup[index].Need[i]-=re[i];
	}
	//3.安全性检查
	ifsafe = 0;
	Run(backup,bAvalia,0);
	if(ifsafe == 0)
		printf("\n\n请求失败！系统将进入不安全状态！\n\n");
	else
	{
		//4.如果安全，则真实分配
		for(int i=0; i<3; i++)
		{
			pcb[index].Allo[i]+=re[i];
			Avalia[i]-=re[i];
			pcb[index].Need[i]-=re[i];
		}

	}

}

void Request()
{
	int re[num];
	int n;
	printf("\n输入请求资源的进程号(0 ~ 4 数字)：");
	scanf("%d",&n);
	printf("\n输入请求资源的数量(3类资源,空格隔开)：");
	for(int i=0; i<num; i++)
		scanf("%d",&re[i]);
	//安全性算法之前的检查
	RunBefore(n,re);
}

void input()
{
	for(int i=0; i<5; i++)
	{
		printf("输入进程");
		cout<<pcb[0].name;
		printf("的资源分配情况(3类资源,空格隔开):\n\n");
		printf("Max: ");
		scanf("%d%d%d",&pcb[i].Max[0],&pcb[i].Max[1],&pcb[i].Max[2]);
		printf("\nAllocation: ");
		scanf("%d%d%d",&pcb[i].Allo[0],&pcb[i].Allo[1],&pcb[i].Allo[2]);
		for(int j=0;j<3;j++)
			pcb[i].Need[j] = pcb[i].Max[j] - pcb[i].Allo[j];
	}
	printf("输入当前可用资源数量(3类资源,空格隔开)\n\n");
	printf("Avaliable: ");
	scanf("%d%d%d",&Avalia[0],&Avalia[1],&Avalia[2]);

}
int main()
{
	int n;
	init();
	while(1)
	{
		menu();
		scanf("%d",&n);
		switch (n)
		{
			case 1:
				input();
				break;
			case 2:
				output();
				break;
			case 3:
				Request();
				break;
			case 4:
				exit(0);
				break;
			default :
				printf("请输入有效选项!\n");
				break;
		}
	}
}

本文标签： 银行家 算法 操作系统