实验目的
- 理解银行家算法
- 掌握进程安全性检查的方法与资源分配的方法
实验原理
银行家算法
银行家算法最初级为银行系统设计，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS设计中，用它来避免死锁。
为实现银行家算法，每个新进程在进入系统时它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当某一进程请求时，系统会自动判断请求量是否小于进程最大所需，同时判断请求量是否小于当前系统资源剩余量。若两项均满足，则系统试分配资源并执行安全性检查算法。
算法流程图如下
安全性检查算法
.安全性检查算法用于检查系统进行资源分配后是否安全，若安全系统才可以执行此次分配；若不安全，则系统不执行此次分配。
安全性检查算法原理为：在系统试分配资源后，算法从现有进程列表寻找出一个可执行的进程进行执行，执行完成后回收进程占用资源；进而寻找下一个可执行进程。当进程需求量大于系统可分配量时，进程无法执行。当所有进程均可执行，则产生一个安全执行序列，系统资源分配成功。若进程无法全部执行，即无法找到一条安全序列，则说明系统在分配资源后会不安全，所以此次分配失败。
算法流程图如下
实验内容
算法实现
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
| #include <stdio.h>
#include<iostream>
using namespace std;
int res, pro;
int need[10][10], maxr[10][10], allocation[10][10], available[10],request[10];
int Compare(int m[], int n[]) {
for (int i = 0; i < res; i++)
{
if (m[i] < n[i])return 0;
}
return 1;
}
void Print() {
cout << " allocation need avilable" << endl;
for (int i = 0; i < pro; i++) {
cout << '\n' << "进程" << i<< '\t';
for (int j = 0; j < res; j++)
printf(" %2d ", allocation[i][j]);
cout << " ";
for (int j = 0; j < res; j++)
printf(" %2d ", need[i][j]);
if (!i)
{
cout << " ";
for(int j=0;j<res;j++)
printf(" %2d ", available[j]);
}
}
cout << endl;
}
void init() {
cout << "请输入最大需求矩阵maxr\n";
for (int i = 0; i < pro; i++) {
for (int j = 0; j < res; j++) {
cin >> maxr[i][j];
}
}
cout << "请输入分配矩阵allocation\n";
for (int i = 0; i < pro; i++) {
for (int j = 0; j < res; j++) {
cin >> allocation[i][j];
need[i][j] = maxr[i][j] - allocation[i][j];
}
}
cout << "请输入可用资源向量available\n";
for (int i = 0; i < res; i++) {
cin >> available[i];
}
}
int Safetytest() {
int work[10], finish[10] = { 0 }, seq[10];
for (int i = 0; i < res; i++)
work[i] = available[i];
int i, k = 0;
while (k < pro) {
for (i = 0; i < pro; i++)
if (!finish[i] && Compare(work,need[i])) break;
if (i == pro)break;
for (int j = 0; j < res; j++)
work[j] += allocation[i][j];
finish[i] = 1;
seq[k] = i; k++;
}
if (k == pro) {
cout << "安全序列为:";
for (int i = 0; i < pro; i++)
cout << seq[i] << '\t';
cout << endl;
return 1;
}
return 0;
}
void Banker(int n){
if (Compare(need[n],request)) {
if (Compare(request, available))cout << "无足够资源" << endl;
else{for (int i = 0; i < res; i++) {
available[i] -= request[i];
allocation[n][i] += request[i];
need[n][i] -= request[i];
}
if (!Safetytest()) {
for (int i = 0; i < res; i++) {
available[i] += request[i];
allocation[n][i] -= request[i];
need[n][i] += request[i];
}
cout << "不安全的状态" << endl;
}
else {
cout << "允许分配资源" << endl;
Print();
}}
}else cout << "请求资源大于所需资源" << endl;
}
int main() {
int n;
cout << "输入进程数和资源数"<<endl;
cin >> pro>>res;
init();
Print();
cout << "输入进程号:" << endl;
cin >> n;
cout << "请求向量:" << endl;
for (int i = 0; i < res; i++)
cin >> request[i];
Banker(n);
}
|
内容演示
实验总结
银行家算法是一种用来避免操作系统死锁出现的有效算法。
死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
死锁的发生必须具备以下四个必要条件：
- 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
- 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
- 不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
- 循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合$\lbrace P_0，P_1，P_2，···，P_n\rbrace$中的$P_0$正在等待一个$P_1$占用的资源；$P_1$正在等待$P_2$占用的资源，……，$P_n$正在等待已被$P_0$占用的资源。
- 银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。
为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列:是指一个进程序列$\lbrace P_1，···，P_n\rbrace$是安全的，即对于每一个进程$P_i (1≤i≤n)$，它以后尚需要的资源量不超过系统当前剩余资源量与所有进程$P_j (j < i )$当前占有资源量之和。
安全状态：如果存在一个由系统中所有进程构成的安全序列$P_1，…，P_n$，则系统处于安全状态。
安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁