7-2 银行家算法--申请资源 (30 分)（思路+详解）Come 乖宝宝们

2023-08-14 13:27:34

一：前言

这道题需要用到前面的一道题 安全性检查 算法知识，所以强烈建议先看前面那道题
7-1 银行家算法–安全性检查 (20 分)

二：题目

输入N个进程(N<=100)，以及M类资源（M<=100），初始化各种资源的总数，T0时刻资源的分配情况。例如： 假定系统中有5个进程{P0，P1，P2，P3，P4}和三类资源{A,B,C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配
7-2 银行家算法--申请资源 (30 分)（思路+详解）Come 乖宝宝们
输入申请资源的进程以及申请各类资源的数目，判断是否分配。若分配，输出”可以找到安全序列，可以分配。“并输出分配后的系统状态。若不分配，输出”找不到安全序列，不予分配。“并输出当前系统状态。

输入格式:
第一行输入进程数量N，第二行输入资源类数M，第三行输入M类资源个类资源的总数，以下N行分别输入每个进程的名字，该进程对M类资源的最大需求以及已分配资源。最后一行输入申请进程的名字和申请各类资源的数目。

输出格式:
若分配，输出”可以找到安全序列，可以分配。“并输出分配后的系统状态。

若不分配，给出不分配的原因：

1.若输入的进程的名字不正确，输出”查无此进程。“并输出当前系统状态。

2.若申请的资源数目大于最大需求，输出”需求不合理，不予分配。“并输出当前系统状态。

3.若申请的资源数目大于剩余资源，输出”剩余资源不足，不予分配。“并输出当前系统状态。

4.若找不到安全序列，输出”找不到安全序列，不予分配。“并输出当前系统状态。

输入样例1:
在这里给出一组输入。例如：

5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P1 1 0 2
结尾无空行

输出样例1:
在这里给出相应的输出。例如：

可以找到安全序列，可以分配。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0
P1 3 2 2 | 3 0 2 | 0 2 0 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |
结尾无空行

输入样例2:
在这里给出一组输入。例如：

5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P5 1 0 2

结尾无空行
输出样例2:
在这里给出相应的输出。例如：

查无此进程。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2
P1 3 2 2 | 2 0 0 | 1 2 2 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |

结尾无空行

三：思路

思路：
1.我相信如果我们AC出来前面安全性检查那到题，那么这道题也会很快做出来
2.前面所求的 need 和 Avaliable是 跟这道题一样的
3.那么接下来我们就是判断 requst 和 need 和 avaliable之间的关系
其中requset 就是 一个进程p1 申请的资源量
1>: 如果这个进程名输入错了 ，那就输出 查无此进程
2>: 如果上诉条件满足，那判断 request 和 Max 关系 request <= Max 就欧克
否则 出输出”需求不合理，不予分配。“并输出当前系统状态。
3>:如果上诉条件满足，那就判断 request 和 avaliable之间的关系 request <= avaliable 就欧克
否则 剩余资源不足，不予分配。“并输出当前系统状态
4>:当上诉条件均满足的话 那么 相应的进程的 allocation 和 need 要做出变化
而且其 系统可利用的资源 avaliable也要做出相应的变化
5>:接下来就是 判断在当前的avaliable下 是否是安全状态，也就是安全性检查
如果找到一条安全序列输出 “可以找到安全序列，可以分配。“并输出分配后的系统状态。
如果找不到就输出”找不到安全序列，不予分配。“并输出当前系统状态。

四:上码：

/**
 	思路：
	 1.我相信如果我们AC出来前面安全性检查那到题，那么这道题也会很快做出来
	 2.前面所求的 need 和 Avaliable是 跟这道题一样的
	 3.那么接下来我们就是判断 requst 和 need 和 avaliable之间的关系
	 	其中requset 就是 一个进程p1 申请的资源量 
	 	1>: 如果这个进程名输入错了 ，那就输出 查无此进程
		2>: 如果上诉条件满足，那判断 request 和 Max 关系 request <= Max 就欧克
			否则 出输出”需求不合理，不予分配。“并输出当前系统状态。 
        3>:如果上诉条件满足，那就判断 request 和 avaliable之间的关系 request <= avaliable 就欧克
			否则 剩余资源不足，不予分配。“并输出当前系统状态
			
		4>:当上诉条件均满足的话 那么 相应的进程的 allocation 和 need 要做出变化
			而且其 系统可利用的资源 avaliable也要做出相应的变化
		5>:接下来就是 判断在当前的avaliable下  是否是安全状态，也就是安全性检查
			如果找到一条安全序列输出 “可以找到安全序列，可以分配。“并输出分配后的系统状态。			 
            如果找不到就输出”找不到安全序列，不予分配。“并输出当前系统状态。 
**/

#include<bits/stdc++.h>
using namespace std;

int N,M;
string str;
vector<int>v1;//用于存放各种的资源总量 
vector<int>v2;//用于代表申请资源的进程申请的  资源量 
vector<int>v3;//用于记录最初的avaliable 

struct Node{
	string processName; 
	int a[100];//Max
	int b[100];//allocation 
	int c[100];//need
	bool finish;
} node[1000];

//用于判断是否有该进程
bool judgeExit(string str){
	
	for(int i = 0; i < N; i++){
		 if(str == node[i].processName){
		 	return true;
		 }
	}
	
	return false;
}

//用于计算此时的request 和 need
bool requestNeed(){
	
	int count  = 0;
	
	for(int i = 0;  i < N; i++){
		
		int count = 0;
		if(str == node[i].processName){
		
			for(int j = 0;  j < M; j++){
				if(v2[j] <= node[i].c[j]){//请求量 小于 need 
					count++;
				}
			}			
		}
		
		if(count == M){
			return true;
		}
	}
	
	return false;
	
}  
//用判断申请的资源数目是否大于剩余资源 
bool requestAvaliable(){
	int count  = 0;
	
	for(int j = 0; j < M; j++){
		if(v2[j] <= v1[j]){ //请求量 小于 avaliabale 
			count++;
		}
	}			
				
	if(count == M){
		return true;
	}
	
	return false;
	
}

//判断当前的安全状态
bool isSafe(){

	int cnt = 0;	
	for(int i = 0; i < N; i++){
	
		int count = 0;
		for(int j = 0; j < M; j++){
			
			if(node[i].c[j] <= v1[j]){
				count++;
			
			}else{
				break;//只要有一个不合适就 break 出去 
			}				
		}
				
		if(node[i].finish == false && count == M) {//count == M说明剩余的各个资源总量大于该进程的所需要的 
					
			for(int j = 0; j < M; j++){
				
				v1[j] += node[i].b[j];//那么此时剩余的资源总量为原来的加上 该进程释放其占有的资源
		 
			}	
			
			node[i].finish = true; 
			
			cnt++;//记录完成进程的个数 
			
		//	cout << node[i].processName << ' ';
				
			//此处牛逼之处在于 只要我们找到满足条件的就从-1开始继续寻找满足条件的 
			i = -1; 
			
			
		}					
	}
	
	if(cnt == N){
		return true;
	}
	
	return false;
} 
 

//用于输出此时系统的状态 
void state(){
	int flag = 0;
    
	cout << "name max allocation need available" << endl;
	
	for(int i = 0; i < N; i++){
		
		cout << node[i].processName << ' ';
		for(int j = 0; j < M; j++){
		 
		 cout << node[i].a[j] << ' ';			
		}			
		
		cout << "| ";
		
		for(int j = 0; j < M; j++){
		 
		 cout << node[i].b[j] << ' ';			
		}
		
		cout << "| ";
		
		for(int j = 0; j < M; j++){
		 
		 cout << node[i].c[j] << ' ';			
		}
		
		cout << "|";
		
		if(flag == 0){
		
           
			for(int j = 0; j < M; j++){
			 
                if(j == 0)
                    cout << ' ' <<v3[j];
                else
			        cout << ' ' <<v3[j] ;				 			
			}	
			
			flag = 1;		
		}	
		
			cout << endl;	
		}
}


int main(){
	
	cin >> N >> M;
	
	for(int i = 0; i < M; i++){
		int nums;
		cin >> nums;
		v1.push_back(nums);	
	} 
	
	for(int i = 0; i < N; i++){
		
		cin >> node[i].processName;
		
		//输入Max 
		for(int j = 0; j < M; j++){
			cin >> node[i].a[j]; 
		}
		//输入allovation  
		for(int j = 0; j < M; j++){

			cin >> node[i].b[j];
			
			v1[j] -= node[i].b[j];//这里是每次减去分配的资源 那么剩下的最后就是  available 
		}
		//计算need
		for(int j = 0; j < M; j++){
			node[i].c[j] = node[i].a[j] - node[i].b[j];
		} 
		
		node[i].finish = false;
	}
	
	cin >> str;
	
	for(int i = 0; i < M; i++){
		int temp;
		cin >> temp;
		v2.push_back(temp);
	} 
	//将最初的avaliable记录下来 
	for(int i = 0; i < M; i++){
		v3.push_back(v1[i]);
	} 
	
	if(judgeExit(str) == false){
		cout << "查无此进程。" << endl;
		state();
	}else if(requestNeed() == false){
		cout << "需求不合理，不予分配。" << endl;
		state();
	}else if(requestAvaliable() == false) {
		cout << "剩余资源不足，不予分配。" << endl;
		state();
	}
	//此时开始将申请的资源赋值给该进程同时进行安全检测 
	else if(judgeExit(str) == true && requestNeed() == true && requestAvaliable() == true){
	 	
	 	for(int i = 0; i < N; i++){
	 		
	 		if(str == node[i].processName){
	 			
	 			for(int j = 0; j < M; j++){
	 				
					 node[i].b[j] += v2[j];//这里是更新 该进程的allocation 
					 node[i].c[j] -= v2[j];//这里是更新 该进程的need
					 v1[j] -= v2[j]; //这里是更新 该进程的avaliable 
					 v3[j] -= v2[j];//存放 最初 avaliable的	
				 }
			 }	 		
		} 
		 
		 if(isSafe() == true){
		 	cout << "可以找到安全序列，可以分配。" << endl;
		 	state();
		 }else{
		 	cout << "找不到安全序列，不予分配。" << endl;
		 	
		 	//如果不满足条件的话 需要将原来 进程的的资源分配形式输出来 
		 	for(int i = 0; i < N; i++){
	 		
		 		if(str == node[i].processName){
		 			
		 			for(int j = 0; j < M; j++){
		 				
						 node[i].b[j] -= v2[j];//这里是更新 该进程的allocation 
						 node[i].c[j] += v2[j];//这里是更新 该进程的need
						 v1[j] += v2[j]; //这里是更新 该进程的avaliable 
						 v3[j] += v2[j];//存放 最初 avaliable的	
					 }
				 }	 		
			} 
		 	
		 	
		 	
		 	
		 	state();
		 } 
		 
		
	}
	
} 



//5
//3
//10 5 7
//P0 7 5 3 0 1 0
//P1 3 2 2 2 0 0
//P2 9 0 2 3 0 2
//P3 2 2 2 2 1 1
//P4 4 3 2 0 0 2
//P1 2 2 2



//name max allocation need available
//P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2
//P1 3 2 2 | 2 0 0 | 1 2 2 |
//P2 9 0 2 | 3 0 2 | 6 0 0 |
//P3 2 2 2 | 2 1 1 | 0 1 1 |
//P4 4 3 2 | 0 0 2 | 4 3 0 |
//找到安全序列，处于安全状态。



//5
//3
//10 5 7
//P0 7 5 3 0 1 0
//P1 3 2 2 2 0 0
//P2 9 0 2 3 0 2
//P3 2 2 2 2 1 1
//P4 4 3 2 0 0 2
//P0 0 1 0

7-2 银行家算法--申请资源 (30 分)（思路+详解）Come 乖宝宝们
宝宝们 加油呀 我们共勉 获得坦然 走的自信 坚持热爱 不负初心！！！！！！！！！！！！！

上一篇：JavaScript雷区：使用[]引用对象必须加双引号


下一篇：【技巧总结】Penetration Test Engineer[3]-Web-Security（SQL注入、XXS、代码注入、命令执行、变量覆盖、XSS）