【操作系统】进程调度之银行家算法的实现

1 创作的小心思

该作旨在完成老师布置的实验任务,也借此机会系统的将银行家算法再学一遍。也可以蹭一波大家的热度,嘻嘻🤭,欢迎来访🎉🎉🎉

2 追根溯源

银行家算法(Banker’s Algorithm) 是一个避免死锁(Deadlock) 的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。(来源:百度百科)

3 算法设计

3.1 银行家算法

3.1.1 所需维护的数据结构

1、可利用资源向量 A v a i l a b l e Available Available。这是一个含有 m m m个元素的一维数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态的改变。若
A v a i l a b l e [ j ] = K Available[j] = K Available[j]=K,则表示系统中现有 R j R_j Rj 类资源 K K K 个。

2、最大需求矩阵 M a x Max Max。这是一个 n × m n×m n×m 的矩阵,它定义了系统中 n n n 个进程中的每个进程对 m m m 类资源的最大需求。若 M a x [ i ] [ j ] = K Max[i][j] = K Max[i][j]=K ,则表示进程 i i i 需要 R j R_j Rj 类资源的最大数目为 K K K

3、分配矩阵 A l l o c a t i o n Allocation Allocation。这是一个 n × m n×m n×m 的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。若 A l l o c a t i o n [ i ] [ j ] = K Allocation[i][j] = K Allocation[i][j]=K ,则表示进程 i i i 当前已分得 R j R_j Rj 类资源的数目为 K K K

4、需求矩阵 N e e d Need Need。这是一个 n × m n×m n×m 的矩阵,用以表示每一个进程尚需的各类资源数。若 N e e d [ i ] [ j ] = K Need[i][j] = K Need[i][j]=K ,则表示进程 i i i 还需要 R j R_j Rj 类资源 K K K个方能完成其任务。

3.1.2 算法执行步骤

R e q u e s t [ i ] Request[i] Request[i] 是进程 P i P_i Pi 的请求向量, 如果 R e q u e s t [ i ] [ j ] = K Request[i][j]=K Request[i][j]=K, 表示进程 P i P_i Pi 需要 K K K R j R_j Rj类型的资源。
P i P_i Pi 发出资源请求后,系统按下述步骤进行检查:
(1)、如果 R e q u e s t [ i ] [ j ] ≤ N e e d [ i ] [ j ] Request[i][j]≤Need[i][j] Request[i][j]Need[i][j],便转向步骤(2); 否则认为出错,因为它所需要的资源数已经超过它所宣布的最大值。
(2)、如果 R e q u e s t [ i ] [ j ] ≤ A v a i l a b l e [ j ] Request[i][j]≤Available[j] Request[i][j]Available[j] ,便转向步骤(3); 否则,表示尚无足够资源, P i P_i Pi 须等待。
(3)、系统试探着把资源分配给进程 P i P_i Pi ,并修改下面数据结构中的值:
A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t [ i ] [ j ] A l l o c a t i o n [ i ] [ j ] = A l l o c a t i o n [ i ] [ j ] + R e q u e s t [ i ] [ j ] N e e d [ i ] [ j ] = N e e d [ i ] [ j ] − R e q u e s t [ i ] [ j ] Available[j]=Available[j]-Request[i][j] \ Allocation[i][j]=Allocation[i][j]+Request[i][j] \ Need[i][j]=Need[i][j]-Request[i][j] Available[j]=Available[j]Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]Request[i][j]
(4)、系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程 P i P_i Pi ,以完成本次分配;否则,将本次试探分配作废,恢复原来资源分配状态,让进程 P i P_i Pi 等待。

3.1.3 流程图

【操作系统】进程调度之银行家算法的实现

3.2 安全性算法

3.2.1 所需维护的数据结构

1、工作向量 W o r k Work Work, 这是一个含有 m m m 个元素的一维数组,它表示系统可提供给进程继续运行所需的各类资源的数目,在执行安全算法开始时, W o r k = A v a i l a b l e Work=Available Work=Available。(其实和 A v a i l a b l e Available Available 所维护的内容一样)
2、进程状态向量 F i n i s h Finish Finish,这是一个含有 n n n 个元素的一维数组,它表示每一个进程是否运行完成,用布尔值来表示进程的状态, F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True 表示进程 P i P_i Pi 已经运行完成,否则运行未完成。

3.2.2 算法执行步骤

(1) 从进程集合中找到一个能满足下述条件的进程:
F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False;
N e e d [ i ] [ j ] ≤ W o r k [ j ] Need[i][j]≤Work[j] Need[i][j]Work[j];(注意:此处需要所有 m m m 类资源都满足该条件)
若找到,执行步骤(2),否则,执行步骤(3)。
(2) 当进程 P i P_i Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源:
W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i ] [ j ] ; F i n i s h [ j ] = T r u e ; g o   t o   s t e p   1 ; Work[j]=Work[j]+Allocation[i][j]; \ Finish[j]=True; \ go to step 1; Work[j]=Work[j]+Allocation[i][j];Finish[j]=True;go to step 1;
(4) 如果所有进程的Finish[i]=True都满足,则表示处于安全状态;否则,系统处于不安全状态。

3.2.3 流程图

【操作系统】进程调度之银行家算法的实现

4 算法示例

4.1 示例题目

【操作系统】进程调度之银行家算法的实现

4.2 例题求解

【操作系统】进程调度之银行家算法的实现
【操作系统】进程调度之银行家算法的实现

5 C++代码实现

5.1 C++源代码(全)

1.0版本,后续有时间了可能会再回来加强一波。请求资源方面,目前只能一次性分配一个,不能同时得到请求,需要改进,其他的基本功能算是实现了。执行过程的状态,比交好实现,加个输出就OK,比较简单,代码中就没实现。

#include<cstdio> #include<queue> #include<vector> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; const int N = 1010, M = 1010; int n, m; int Max[N][M], Allocation[N][M], Need[N][M]; int Available[M], Finish[N]; int Work[M], Request[M]; int Sum[M];//系统中m类资源的总量 void Init() { 	cout << "请输入合法的矩阵" << endl; 	cout << "初始化Max矩阵" << endl; 	cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl; 	for (int i = 1;i <= n;i++) 		for (int j = 1;j <= m;j++) 			cin >> Max[i][j];  	cout << "初始化Allocation矩阵" << endl; 	cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl; 	for (int i = 1;i <= n;i++) 		for (int j = 1;j <= m;j++) 			cin >> Allocation[i][j];  	cout << "初始化Available向量" << endl; 	cout << "请输入一行" << m << "个元素表示当前可用资源的数量:" << endl; 	for (int i = 1;i <= m;i++) cin >> Available[i];  	/*初始化Need矩阵*/ 	for (int i = 1;i <= n;i++) 	{ 		for (int j = 1;j <= m;j++) 		{ 			Need[i][j] = Max[i][j] - Allocation[i][j]; 		} 	} 	/*初始化Sum矩阵*/ 	for (int j = 1;j <= m;j++) 	{ 		for (int i = 1;i <= n;i++) 		{ 			Sum[j] += Allocation[i][j]; 		} 		Sum[j] += Available[j]; 	} 	cout << "初始化成功>^V^<" << endl; } /*判断初始化矩阵的合法性*/ bool Judge() { 	for (int i = 1;i <= n;i++) 	{ 		for (int j = 1;j <= m;j++) 		{ 			if (Allocation[i][j] > Max[i][j]) return false; 		} 	} 	return true; } /*判断当前work向量是否大于Need[i]向量*/ bool Judge(int k) { 	for (int j = 1;j <= m;j++) 	{ 		if (Need[k][j] > Work[j]) return false; 	} 	return true; } /*安全性检查的时候虚拟处理*/ void VirtureDeal(int k) { 	for (int j = 1;j <= m;j++) 	{ 		Work[j] += Allocation[k][j]; 	} 	Finish[k] = true; } /*安全性检查*/ bool SecurityCheck(queue<int>& q) { 	memcpy(Work, Available, sizeof Available); 	memset(Finish, false, sizeof Finish); 	for(int k = 1;k <= n;k++) //n次迭代 	{ 		bool flag = false; 		for (int i = 1;i <= n;i++) 		{ 			if (!Finish[i] && Judge(i)) 			{ 				flag = true; 				q.push(i); 				VirtureDeal(i); 				break; 			} 		} 		if (!flag) return false; 	} 	return true; } /*试探性分配资源*/ void Alloc(int k) { 	for (int j = 1;j <= m;j++) 	{ 		Allocation[k][j] += Request[j]; 		Need[k][j] -= Request[j]; 		Available[j] -= Request[j]; 	} } /*恢复原状*/ void Recover(int k) { 	for (int j = 1;j <= m;j++) 	{ 		Allocation[k][j] -= Request[j]; 		Need[k][j] += Request[j]; 		Available[j] += Request[j]; 	} } /*请求资源*/ void Query() { 	int ID; 	cout << "请输入进程ID(1 -- " << n << "):" << endl; cin >> ID; 	cout << "请输入请求向量(输入" << m << "个有效整数):" << endl; 	for (int j = 1;j <= m;j++) cin >> Request[j]; 	for (int j = 1;j <= m;j++) 	{ 		if (Request[j] > Need[ID][j]) 		{ 			cout << "出错,请求的资源大于需求资源" << endl; 			return; 		} 		else if (Request[j] > Available[j]) 		{ 			cout << "进程无法得到资源,继续处于等待状态!" << endl; 			return; 		} 	} 	Alloc(ID);//试探性分配 	queue<int> q; 	if (SecurityCheck(q)) 	{ 		cout << "分配资源成功!" << endl; 		cout << "其中的一个安全序列是:"; 		bool mark = false; 		while (q.size()) 		{ 			if (mark) cout << "->"; 			cout << q.front();q.pop(); 			mark = true; 		} 		cout << endl; 	} 	else { 		cout << "无法执行分配任务!" << endl; 		Recover(ID);//无法执行分配,恢复原状 	} } int main() { 	cout << "请输入进程个数: "; cin >> n; 	cout << "请输入资源的种类数: "; cin >> m; 	Init(); 	system("pause"); 	while (1) 	{ 		system("cls"); 		cout << "1、请求资源" << endl; 		cout << "2、检查当前状态的安全性" << endl; 		cout << "0、退出主程序" << endl; 		while (1) 		{ 			int op; cin >> op; 			if (op < 0 || op > 2) { 				cout << "操做错误,请重新输入!!!" << endl; 				system("pause"); 			} 			else { 				if (op == 0) exit(0); 				else if (op == 1) { 					Query(); 					system("pause"); 				} 				else if (op == 2) 				{ 					queue<int> q; 					if (SecurityCheck(q)) 					{ 						cout << "当前状态安全" << endl; 						cout << "其中的一个安全序列是:"; 						bool mark = false; 						while (q.size()) 						{ 							if (mark) cout << "->"; 							cout << q.front();q.pop(); 							mark = true; 						} 						cout << endl; 					} 					else { 						cout << "当前状态不安全,极有可能进入死锁状态" << endl; 					} 					system("pause"); 				} 			} 			break; 		} 	} 	return 0; } /* Max 3 2 2 6 1 3 3 1 4 4 2 2 Allocation 1 0 0 4 1 1 2 1 1 0 0 2 Available 2 1 2 */ 

5.2 测试截图

5.2.1 初始化

【操作系统】进程调度之银行家算法的实现

5.2.2 进程1发出资源请求(1,0,1)

【操作系统】进程调度之银行家算法的实现

5.2.3 进程2发出资源请求(1,0,1)

【操作系统】进程调度之银行家算法的实现

5.2.4 检查当前状态安全性

【操作系统】进程调度之银行家算法的实现
欢迎大家在评论区提出自己的疑问,我会在评论区进行回复。
也欢迎批评我写的不足之处,能力范围之内我会进行加强,我们一起共勉👊。

版权声明:玥玥 发表于 2021-05-06 0:29:53。
转载请注明:【操作系统】进程调度之银行家算法的实现 | 女黑客导航