银行家算法的C++模拟

实验五 银行家算法

实验题目：银行家算法的模拟

提示1

  • 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。
  • 当进程在执行中申请资源时，先检查该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过，则再测试系统现存的资源能否满足该进程申请的资源量，若能满足则按当前的申请量分配资源，否则也要拒绝分配。

提示2

  • 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态
    一定是没有死锁发生。
  • 不安全状态：不存在一个安全序列。不安全状态一定导致死锁。
  • 安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

提示3

设request为进程p[i]的请求向量，如果request[j]=K，表示进程p[i]需要K个R[j]资源。当系统发出请求后，系统按下述步骤开始检查：
1）如果request[j]<=need[i][j],转向步骤2；否则报告出错，申请的资源已经大于它需要的最大值。
2）如果request[j]<=available[j]，转向步骤3；否则报告出错，尚无足够的资源。
3）系统试探着把资源分配给p[i]，并修改下列数据结构中的值：

1
2
3
available[j]=available[j]-request[j]
allocation[i][j]=allocation[i][j]+request[j]
need[i][j]=need[i][j]request[j]

4）系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程p[i]；否则，恢复原来的资源分配状态，让进程p[i]等待

提示4

安全性算法：
int work[RESOURCE_NUMBER]；
bool finish[PROCESS_NUMBER]；

  1. Work=Available;
    Finish=false;
  2. 寻找满足条件的i：
    A、Finish[i]=false;
    B、Need[i]≤Work;
    如果不存在，则转4；
  3. Work:=Work+Allocation[i]； Finish[i]:=true； 转2；
  4. 若对所有i，Finish[i]=true，则系统处于安全状态，否则处于不安全状态。

提示5(银行家算法的程序流程图)

image-20211128214359127

程序中使用的数据结构及符号说明

  • 数组（数据结构），保存进程、资源的各类信息以及安全序列
1
2
3
4
5
6
7
8
9
string resource[1000];		//资源名
int available[1000];		//各资源的刚开始的可用数量
int work[1000];				//工作时各资源的可用数量
int Max[1000][1000];		//进程的最大所需资源
int allocation[1000][1000]; //进程的已分配资源
int need[1000][1000];		//进程当前需要的资源
bool Finish[1000];			//进程是否完成
int request[1000];			//请求资源
int safe[1000];	//安全序列
  • 整型变量
1
2
int processNum = 0;			//进程数
int resourceNum = 0;		//资源类型数
  • 函数说明：
    • void Init()：输入信息。
    • void display()：显示当前所有进程分配状态。
    • bool isSafe()：安全性检查算法，安全返回true，不安全返回false。

源程序并附上注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
#include<iostream>
#include<iomanip>

using namespace std;

int processNum = 0;			//进程数
int resourceNum = 0;		//资源类型数
string resource[1000];		//资源名
int available[1000];		//各资源的刚开始的可用数量
int work[1000];				//工作时各资源的可用数量
int Max[1000][1000];		//进程的最大所需资源
int allocation[1000][1000]; //进程的已分配资源
int need[1000][1000];		//进程当前需要的资源
bool Finish[1000];			//进程是否完成
int request[1000];			//请求资源
int safe[1000];	//安全序列

//初始化
void Init()
{
	int i, j;
	cout << "请输入进程数量：";
	cin >> processNum;
	cout << "请输入资源类型数量：";
	cin >> resourceNum;
	cout << "请依次输入各资源的名称（不超过6个字符）和可用数目：" << endl;
	cout << "例：A 3 B 3 C 2" << endl;
	for (i = 0; i < resourceNum; i++)
	{
		cin >> resource[i] >> available[i];
	}
	//最大需求的矩阵Max：
	cout << "请输入最大需求的矩阵：" << endl;
	cout << "（进程顺序为从0到processNum，资源顺序为：";
	for (j = 0; j < resourceNum; j++)
	{
		cout << resource[j] << " ";
	}
	cout << "）" << endl;
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cin >> Max[i][j];
		}
	}
	//分配矩阵allocation：
	cout << "请输入当前分配各资源类型数量的矩阵"<<endl;
	cout << "（进程顺序为1-processNum，资源顺序为：";
	for (j = 0; j < resourceNum; j++)
	{
		cout << resource[j]<<" ";
	}
	cout << "）" << endl;
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cin >> allocation[i][j];
		}
	}
	//根据Max和allocation算出需求矩阵need：
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			need[i][j] = Max[i][j] - allocation[i][j];
		}
	}
}
//显示当前所有进程分配状态
void showInfo()
{
	int i, j;
	int len = 8 * resourceNum;
	cout << "当前系统状态如下：" << endl;
	//第1行：根据资源数的不同，居左输出
	cout << "        ";
	cout << left << setw(len) << "Max";
	cout << left << setw(len) << "Allocation";
	cout << left << setw(len) << "Need";
	cout << left << setw(len) << "Available";
	cout << left << endl;
	//第2行：资源名
	cout << "        ";
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cout << left << setw(8) << resource[j];
		}
	}
	cout << endl;
	//后面processNum行：各进程的资源情况
	for (i = 0; i < processNum; i++)
	{
		cout << "P" << i<<"      ";
		for (j = 0; j < resourceNum; j++)
		{
			cout << left << setw(8) << Max[i][j] ;
		}
		for (j = 0; j < resourceNum; j++)
		{
			cout << left << setw(8)<< allocation[i][j];
		}
		for (j = 0; j < resourceNum; j++)
		{
			cout << left << setw(8) << need[i][j];
		}
		//第三行输出多一项可用资源数
		if (i == 0)
		{
			for (j = 0; j < resourceNum; j++)
			{
				cout << left << setw(8) << available[j];
			}
		}
		cout << endl;
	}
}
//安全性检查算法
bool isSafe()
{
	int i, j, k;
	int round= 0; //循环轮数
	int FinishNum = 0; //已完成的进程数
	//work初始化
	for (i = 0; i < resourceNum; i++)
	{
		work[i] = available[i];
	}
	//Finish初始化
	for (i = 0; i < processNum; i++)
	{
		Finish[i] = false;
	}
	i = 0;
	int temp = 0;
	while (FinishNum < processNum) //有进程未完成
	{
		j = 0; //每次检查前，j需要初始化为0
		//当前进程i是否满足Finish==false并且need<work
		if (Finish[i] == false)
		{
			for (j = 0; j < resourceNum; j++)
			{
				if (need[i][j] > work[j])
				{
					break;
				}
			}
		}
		//满足上面的条件则进行第3步：分配并释放资源，完成进程，记录于安全序列
		if (j == resourceNum)
		{
			Finish[i] = true;
			for (k = 0; k < resourceNum; k++)
			{
				work[k] += allocation[i][k];
			}
			//输出当前可用资源数
			cout << "进程" << i << "执行完成，释放资源。" << "当前可用资源数如下：" << endl;
			for (k = 0; k < resourceNum; k++)
			{
				cout << left << setw(8) << resource[k];
			}
			cout << endl;
			for (k = 0; k < resourceNum; k++)
			{
				cout << left << setw(8) << work[k];
			}
			cout << endl;
			safe[FinishNum] = i;
			FinishNum++;
		}
		i++; //检查下一个进程
		if (i >= processNum) //循环了一轮
		{
			i %= processNum;
			if (temp == FinishNum && round > 0) //再次循环后进程完成数没有变化，则没有可以完成的进程了
				break;
			round++;
			temp = FinishNum; //记录本次循环的FinishNum
		}
	}
	if (FinishNum == processNum)
	{
		cout << "系统安全，安全序列为：";
		for (i = 0; i < processNum; i++)
		{
			cout << "P" << safe[i] << " ";
		}
		cout << endl;
		return true;
	}
	else
	{
		cout << "剩余进程无法完成，系统不安全！"<<endl;
		return false;
	}
}
//主函数
int main()
{
	int i, j;
	Init();
	showInfo();
	//初始化后检查安全性，若不安全则程序结束。
	cout << "开始检查系统安全性：" << endl;
	if (!isSafe())
	{
		cout << "程序结束" << endl;
		return 0;
	}
	while (true)
	{
		cout << "---------------------------------------------------------" << endl;
		cout << "请输入要分配的进程：";
		cin >> i;
		cout << "请输入要分配给进程P" << i << "的资源：" << endl;
		cout<< "资源顺序为：";
		for (j = 0; j < resourceNum; j++)
		{
			cout << resource[j] << " ";
		}
		cout << endl;
		for (j = 0; j < resourceNum; j++)
		{
			cin >> request[j];
		}
		//按步骤开始检查
		for (j = 0; j < resourceNum; j++)
		{
			if (request[j] <= need[i][j])
				continue;
			else
			{
				cout << "错误！申请的资源已经大于它需要的最大值" << endl;
				break;
			}
		}
		if (j == resourceNum)
		{
			for (j = 0; j < resourceNum; j++)
			{
				if (request[j] <= available[j])
					continue;
				else
				{
					cout << "错误！尚无足够的资源" << endl;
					break;
				}
			}
		}
		if (j == resourceNum)
		{
			//尝试分配，修改数据结构的值
			for (j = 0; j < resourceNum; j++)
			{
				available[j] -= request[j];
				allocation[i][j] += request[j];
				need[i][j] -= request[j];
			}
			cout << "开始检查系统安全性：" << endl;
			if (isSafe())
			{
				cout << "分配成功！\n";
				showInfo();
			}
			else
			{
				//分配失败，则恢复数据结构的值
				for (j = 0; j < resourceNum; j++)
				{
					available[j] += request[j];
					allocation[i][j] -= request[j];
					need[i][j] += request[j];
				}
				cout << "分配失败！\n";
				showInfo();
			}
		}
	}
}

程序运行时的初值和运行结果

  • 已结合思考题要求

初值

  1. 初始化

image-20211128215453437

  1. 三次申请资源

    ①

    image-20211128215606893

    ②

    image-20211128215732054

    ③

    image-20211128215819214

运行结果

image-20211128221739018

![image-20211128221042945](第五次实验 银行家算法/image-20211128221042945.png)

image-20211128221106632

image-20211128221952657

思考题

设计本实验时，就尽可能的将设计人性化和考虑全面。如：能不断地进行资源分配；能修改资源的初始状态；提示信息就能充分反映算法过程等。

  • 不断进行资源分配、提示信息就能充分反映算法过程等，在前文的代码中已经实现。为了能够在中途修改资源的状态，增加自定义函数change()置于检查安全性的算法isSafe()中，改变的部分如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    //修改资源分配的函数
    bool change()
    {
    	bool flag = false;
    	int i,j;
    	char ch;
    	while (1)
    	{
    		cout << "是否要改变资源分配状态（Y：是，N：否）：" << endl;
    		cin >> ch;
    		if (ch == 'Y')
    		{
    			flag = true;
    		}
    		else
    		{
    			break;
    		}
    		cout << "请选择需要改变的进程：" << endl;
    		cin >> i;
    		cout << "请输入它最新的最大需求矩阵Max：" << endl;
    		for (j = 0; j < resourceNum; j++)
    		{
    			cin >> Max[i][j];
    		}
    		cout << "请输入它最新的分配矩阵allocation：" << endl;
    		for (j = 0; j < resourceNum; j++)
    		{
    			cin >> allocation[i][j];
    		}
    		//更新需求矩阵
    		for (j = 0; j < resourceNum; j++)
    		{
    			need[i][j] = Max[i][j] - allocation[i][j];
    		}
    	}
    	if (flag)
    	{
    		cout << "请依次输入各资源的名称（不超过6个字符）和可用数目：" << endl;
    		cout << "例：A 3 B 3 C 2" << endl;
    		for (i = 0; i < resourceNum; i++)
    		{
    			cin >> resource[i] >> available[i];
    		}
    	}
    	return flag;
    }

    //安全性检查算法
    bool isSafe()
    {
    	int i, j, k;
    	int round= 0; //循环轮数
    	int FinishNum = 0; //已完成的进程数
    	//work初始化
    	for (i = 0; i < resourceNum; i++)
    	{
    		work[i] = available[i];
    	}
    	//Finish初始化
    	for (i = 0; i < processNum; i++)
    	{
    		Finish[i] = false;
    	}
    	i = 0;
    	int temp = 0;
    	while (FinishNum < processNum) //有进程未完成
    	{
    		j = 0; //每次检查前，j需要初始化为0
    		//当前进程i是否满足Finish==false并且need<work
    		if (Finish[i] == false)
    		{
    			for (j = 0; j < resourceNum; j++)
    			{
    				if (need[i][j] > work[j])
    				{
    					break;
    				}
    			}
    		}
    		//满足上面的条件则进行第3步：分配并释放资源，完成进程，记录于安全序列
    		if (j == resourceNum)
    		{
    			Finish[i] = true;
    			for (k = 0; k < resourceNum; k++)
    			{
    				work[k] += allocation[i][k];
    			}
    			//输出当前可用资源数
    			cout << "进程" << i << "执行完成，释放资源。" << "当前可用资源数如下：" << endl;
    			for (k = 0; k < resourceNum; k++)
    			{
    				cout << left << setw(8) << resource[k];
    			}
    			cout << endl;
    			for (k = 0; k < resourceNum; k++)
    			{
    				cout << left << setw(8) << work[k];
    			}
    			cout << endl;
    			safe[FinishNum] = i;
    			FinishNum++;
    		}
    		i++; //检查下一个进程
    		if (i >= processNum) //循环了一轮
    		{
    			i %= processNum;
    			if (temp == FinishNum && round > 0) //再次循环后进程完成数没有变化，则没有可以完成的进程了
    				break;
    			round++;
    			temp = FinishNum; //记录本次循环的FinishNum
    		}
    	}
    	if (FinishNum == processNum)
    	{
    		cout << "系统安全，安全序列为：";
    		for (i = 0; i < processNum; i++)
    		{
    			cout << "P" << safe[i] << " ";
    		}
    		cout << endl;
    		return true;
    	}
    	else
    	{
    		cout << "剩余进程无法完成，系统不安全！"<<endl;
    		if (change())
    		{
    			cout << "将重新进行检查系统安全性：";
                display();
    			return isSafe();
    		}
    		else
    			return false;
    	}
    }

运行结果

image-20211204171631704

image-20211204171738177

实验总结和心得

  • 设计本实验，如何设计得更人性化，考虑得更全面是值得注意的。要用打印的提示信息尽量美观且反映算法过程，这使得我和cout纠缠不清了一段时间。整个实验过程中，我也是在不断地发现问题、观察调试、解决问题，好在最后效果不错。
  • 整个实验逻辑比较清晰，具体流程在实验指导书中都有说明。将算法思想转化为实际代码去实现，让我对银行家算法的算法思想和设计有了更加深刻的了解，较好地锻炼了我的逻辑思维和编程能力。
操作系统课程实验
操作系统实验

本博客所有文章除特别声明外，均为博客作者本人编写整理，转载请联系作者！