《操作系统实验》C++实现银行家算法

妖狐艹你老母 2023-01-10 14:42 111阅读 0赞

### 银行家算法 ###

*  一、实验内容及要求
 *  二、实验环境
 *  三、基本思想
 *  四、数据结构
 *  五、源代码
 *  六、运行结果

# 一、实验内容及要求 #

1.  模拟银行家算法；
2.  程序要添加适当的注释，程序的书写要采用缩进格式；
3.  程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应；
4.  程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

# 二、实验环境 #

windows 10,Visual Studio 2019

# 三、基本思想 #

1.  由用户输入进程的个数、每个进程最多所需的各资源数、每个进程已分配的各资源数以及各个资源现有的数目；
2.  T0时刻进行安全性检查，若系统安全则执行第3步；
3.  由用户输入请求资源的进程以及请求的资源数量，执行银行家算法：  
    \[1\] 如果请求资源数不超过宣布的最大量，便转向步骤\[2\]，否则认为出错；  
    \[2\] 如果请求资源数不超过各资源现有数目，便转向步骤\[3\]，否则等待；  
    \[3\] 试探把资源分配给进程；  
    \[4\] 执行安全性算法，检查此次资源分配后系统是否处于安全状态，若安全则分配，不安全则恢复原来的状态。
4.  安全性算法：  
    \[1\] 设置两个向量work和finish，初始化work为各个资源未分配数目、初始化finish为false；  
    \[2\] 从进程集合中找到一个能满足下finish\[i\]=false、need\[i,j\]≤work\[j\]的进程。若找到，更改work向量，将finish变为true，重复此步骤；否则，执行步骤\[3\]：  
    \[3\] 如果所有进程的finish均为true，则系统处于安全状态，否则处于不安全状态。

# 四、数据结构 #

定义一个bank类：

class bank {
        
    private:
    	int max[max_process][max_source]; 
    	int allocation[max_process][max_source]; 
    	int need[max_process][max_source]; 
    	int available[max_source]; 
    	int p[max_process]; 
    	int request[max_process][max_source]; 
    	int m; 
    	int n; 
    public:
    	void initialize();
    	void bankalg();
    	int safealg();
    };

私有成员包括：

1.  最大需求矩阵max：二维数组，它定义了系统中m个进程中的每一个进程对n类资源的最大需求。
2.  分配矩阵allocation：二维数组，它定义了系统中每一类资源当前已分配给每一进程的资源数。
3.  需求矩阵need：二维数组，表示每一个进程尚需的各类资源数。
4.  可利用资源向量available：一维数组，其中的每一个元素代表一类可利用的资源数目。
5.  数组request记录各进程请求资源的数量，p记录安全序列。

公有成员函数可以执行初始化、银行家算法及安全性算法。

# 五、源代码 #

1.  定义头文件bank.h

#ifndef BANK_H
    #define BANK_H
    const int max_process = 50;
    const int max_source = 50;
    class bank {
        
    private:
    	int max[max_process][max_source];          //最大需求矩阵
    	int allocation[max_process][max_source];   //分配矩阵
    	int need[max_process][max_source];         //需求矩阵
    	int available[max_source];                 //可利用资源向量
    	int p[max_process];                        //安全序列
    	int request[max_process][max_source];      //需要资源数
    	int m;                                     //进程数
    	int n;									   //资源数
    public:
    	void initialize();       //初始化
    	void bankalg();          //银行家算法
    	int safealg();           //安全性算法
    };
    #endif

1.  定义文件bank.cpp

#include"bank.h"
    #include<iostream>
    
    using namespace std;
    
    void bank::initialize() {
        
    	cout << "输入进程数：";
    	cin >> m;
    	cout << "输入资源数：";
    	cin >> n;
    	//初始化最大需求矩阵
    	cout << "请输入每个进程最多所需的各资源数：" << endl;
    	for (int i = 0; i < m; i++) {
        
    		cout << "第" << i << "号进程：";
    		for (int j = 0; j < n; j++)
    			cin >> max[i][j];
    	}
    	//初始化分配矩阵、需求矩阵
    	cout << "\n请输入每个进程已分配的各资源数：" << endl;
    	for (int i = 0; i < m; i++) {
        
    		cout << "第" << i << "号进程：";
    		for (int j = 0; j < n; j++)
    		{
        
    			cin >> allocation[i][j];
    			need[i][j] = max[i][j] - allocation[i][j];
    			if (need[i][j] < 0)
    			{
        
    				cout << "请重新输入第" << i << "号进程的资源数";
    				j--;
    				continue;
    			}
    		}
    	}
    	//初始化可利用资源
    	cout << "\n请输入各个资源现有的数目：" << endl;
    	for (int i = 0; i < n; i++)
    	{
        
    		cin >> available[i];
    	}
    }
    
    void bank::bankalg() {
        
    	int no;
    	bool flag=1,flag2=1;
    	//判断T0时刻安全性
    	if (!safealg()) {
        
    		flag = 0;
    	}
        while (flag){
        
    		//进程请求资源
    		flag2 = 1;
    		cout << "\n输入要申请资源的进程序号：";
    		cin >> no;
    		if (no >= m || no < 0)
    		{
        
    			cout << "序号错误，重新输入：";
    			continue;
    		}
    		cout << "请输入进程所请求的各资源数：";
    		for (int i = 0; i < n; i++)
    			cin >> request[no][i];
    		for (int i = 0; i < n; i++)
    		{
        
    			//银行家算法step1
    			if (request[no][i] > need[no][i])
    			{
        
    				cout << "请求资源数超过宣布的最大量，请重新输入" << endl;
    				flag2 = 0;
    				break;
    			}
    			//银行家算法step2
    			if (request[no][i] > available[i])
    			{
        
    				cout << "尚无足够资源，请重新输入" << endl;
    				flag2 = 0;
    				break;
    			}
    		}
    		if (!flag2)
    			continue;
    		//银行家算法step3
    		for (int i = 0; i < n; i++)
    		{
        
    			available[i] -= request[no][i];
    			allocation[no][i] += request[no][i];
    			need[no][i] -= request[no][i];
    		}
    		//银行家算法step4
    		if (!safealg()) {
        
    			for (int i = 0; i < n; i++)
    			{
        
    				available[i] += request[no][i];
    				allocation[no][i] -= request[no][i];
    				need[no][i] += request[no][i];
    			}
    		}
    		char choise;
    		cout << "\n继续分配请输入Y，停止分配请输入N：" ;
    		cin >> choise;
    		if (choise == 'N')
    			flag = 0;
    	}
    }
    
    int bank::safealg() {
        
    	int i, j, l = 0;
    	//安全性算法step1
    	int work[max_source];
    	for (int i = 0; i < n; i++)
    		work[i] = available[i];
    	bool finish[max_process];
    	for (int i = 0; i < m; i++)
    		finish[i] = false;
    	//安全性算法step2,3,4
    	for (i = 0; i < m; i++) {
        
    		int flag = 0;
    		if(!finish[i]){
        
    			for (j = 0; j < n; j++) {
        
    				if (need[i][j] > work[j]) {
        
    					flag = 1;
    				}
    			}
    			if (!flag) {
        
    				for (j = 0; j < n; j++) {
        
    					work[j] += allocation[i][j];
    				}
    				finish[i] = true;
    				p[l++] = i;
    				i = -1;
    			}
    		}
    	}
    	if (l == m)
    	{
        
    		cout << "系统安全!" << endl;
    		cout << "安全序列：" ;
    		for (int i = 0; i < l; i++)
    		{
        
    			cout << p[i]<<" ";
    		}
    		cout << endl;
    		return 1;
    	}
    	else {
        
    		cout << "系统不安全，不分配资源!" << endl;
    		return 0;
    	}
    }

1.  定义文件exp.cpp

#include"bank.h"
    #include<iostream>
    
    using namespace std;
    
    int main() {
        
    	bank a;
    	a.initialize();
    	a.bankalg();
    	return 0;
    }

# 六、运行结果 #

![实验结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]: /images/20221119/8430bf2d60d54acd9fceef679827821d.png