操作系统-银行家算法模拟

本文从WordPress迁移而来, 查看全部WordPress迁移文章

借博客做个记录,以后方便查看

银行家算法,Dijstra发明的一种死锁避免算法,算法的思想本质忽略不讲,各种书籍博客有资料可看(话说看书看了1个小时就开始写,该不会自己把算法理解错了吧,汗,应该不会的)。

我个人模拟银行家算法的算法流程如下

第一步:先确定进程数n和资源数m,从而得到了P和R的二维矩阵,接下来的数据就随机生成即可

第二步:发起一次资源申请,即某个进程对系统申请资源,在这里,为了方便演示和测试,写了两个函数,一个是随机生成,一个是手动输入,手动输入是为了方便调试和演示,因为随机生成的话半天生成不了一个比较靠谱的数据

第三步:资源分配算法,系统查看这次申请是否合法,若不合法,直接返回ERROR,如果合法,则检查这次申请有没有导致系统发生死锁的可能性,即测试安全算法(算法的思想,不一定真的死锁了,但是如果导有导致死锁的可能性,这次申请都是不允许的),有可能则阻塞,否则的话,说明是个安全状态,可以找到至少一个安全序列,输出一种安全序列即可

第四步:找出一个安全序列,其实这步就是测试安全性的时候做了的,但是代码实现方面不好写,我单独写出来了(水平有限…)

先用c++写的,控制台程序,没图形界面,但是用来演示的话也够了,打算用python写过一个图形界面的学习一下python的GUI工具包(好像作业要交图形界面的?)

深感自己的代码很幼稚…..真的要找些工程代码来看看才行啊…….

my_Banker.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "my_Status.h"
#include "my_Request.h"
#include "my_Sequence.h"
#define NUM_RESOURCE 6 //最大资源数
#define NUM_PROCESS 6 //最大进程数
#define MAX_RESOURCE 20 //资源最大数值
#define ILLEGAL_REQUEST -1 //非法的请求
#define DEADLOCK_REQUEST 0 //会导致死锁的请求
#define SAFE_REQUEST 1 //安全的请求

class Banker{//银行家算法
public:
void create_random_status(Status &GS); //生成随机数据
Request create_random_request(const int n,const int m); //随机发起一次请求,n=进程数,m=资源数
Request set_request(const int n,const int m); //用户手动设置一次请求(方便测试,演示),n=进程数,m=资源数
bool check(int m,const int *a,const int *b); //检查一个进程在现有资源下能否运行完,该函数是个检验函数,被safe调用
bool safe(Status S);
int allot_resource(const Request &req,Status &GS); //分配资源算法,得到请求后,分配资源给进程,若是安全请求,更新系统状态
Sequence find_sequence(const Status &S); //系统状态GS是安全的,找出其中一个安全序列并返回
};

my_Status.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define NUM_RESOURCE 6        //最大资源数
#define NUM_PROCESS 6 //最大进程数
#define MAX_RESOURCE 20 //资源最大数值

class Status{//系统状态
public:
int num_resource; //资源数量
int num_process; //进程数量
int resource[NUM_RESOURCE]; //总资源数组
int available[NUM_RESOURCE]; //可用资源数组
int claim[NUM_PROCESS][NUM_RESOURCE]; //进程最大需求矩阵
int allocation[NUM_PROCESS][NUM_RESOURCE]; //当前进程使用资源的状态
int need[NUM_PROCESS][NUM_RESOURCE]; //需求矩阵,即claim - allocation
void output_data(); //输出数据
};

my_Request.h

1
2
3
4
5
6
7
8
9
#define NUM_RESOURCE 6        //最大资源数

class Request{ //一次进程请求
public:
int PID; //进程号
int num_resource; //资源数
int request[NUM_RESOURCE]; //该进程对每种资源的需求量
void output_request();
};

my_Sequence.h

1
2
3
4
5
6
7
8
#define NUM_PROCESS 6         //最大进程数

class Sequence{ //一个合法的安全序列
public:
int num_process;
int sequence[NUM_PROCESS];
void output_sequence();
};

Banker.cpp

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
#include "my_Banker.h"
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <set>
using namespace std;

/************************Banker**************************/
void Banker::create_random_status(Status &GS){
for(GS.num_resource = 0; GS.num_resource <= 1; )
GS.num_resource = rand() % 5 + 1;
for(GS.num_process = 0; GS.num_process <= 1; )
GS.num_process = rand() % 5 + 1;
for(int i = 0; i < GS.num_resource; i++)
GS.resource[i] = rand() % MAX_RESOURCE + 1;
for(int i = 0; i < GS.num_resource; i++)
for(int j = 0; j < GS.num_process; j++)
GS.claim[j][i] = rand() % (GS.resource[i]+1);
for(int i = 0; i < GS.num_resource; ){
int sum = 0;
for(int j = 0; j < GS.num_process; j++){
GS.allocation[j][i] = rand() % (GS.claim[j][i]+1);
sum += GS.allocation[j][i];
}
if(sum <= GS.resource[i])
GS.available[i] = GS.resource[i++] - sum;
}
for(int i = 0; i < GS.num_process; i++)
for(int j = 0; j < GS.num_resource; j++)
GS.need[i][j] = GS.claim[i][j] - GS.allocation[i][j];
}

Request Banker::create_random_request(const int n,const int m){
Request req;
req.PID = rand() % n;
req.num_resource = m;
for(int i = 0; i < m; i++)
req.request[i] = rand() % (MAX_RESOURCE+1);
return req;
}

Request Banker::set_request(const int n,const int m){ //该函数比较脆弱,没有做错误处理
Request req;
req.num_resource = m;
cout << "进程数" << n << " 资源数" << m << endl;
cout << "输入进程号:";
cin >> req.PID;
cout << "输入对每种资源的需求:";
for(int i = 0; i < m; i++)
cin >> req.request[i];
return req;
}

int Banker::allot_resource(const Request &req,Status &GS){
Status new_gs = GS;
int PID = req.PID;
for(int j = 0; j < new_gs.num_resource; j++){
new_gs.allocation[PID][j] += req.request[j];
new_gs.need[PID][j] -= req.request[j];
if(new_gs.allocation[PID][j] > new_gs.claim[PID][j])
return ILLEGAL_REQUEST; //非法请求
if(req.request[j] > new_gs.available[j])
return DEADLOCK_REQUEST; //申请的资源已经超过可用资源,阻塞该进程
new_gs.available[j] -= req.request[j];
}
if(safe(new_gs)){//安全
GS = new_gs; //更新系统状态
return SAFE_REQUEST;
}
else //可能导致死锁
return DEADLOCK_REQUEST;
}

bool Banker::check(int m,const int *a,const int *b){
for(int i = 0; i < m; i++)
if(a[i] > b[i])
return false;
return true;
}

bool Banker::safe(Status S){
set<int>rest;
int cur_available[NUM_RESOURCE];

rest.clear();
for(int i = 0; i < S.num_resource; i++)
cur_available[i] = S.available[i];
for(int i = 0; i < S.num_process; i++)
rest.insert(i);
bool SAFE = true;
while(SAFE && !rest.empty()){
set<int>::iterator it;
for(it = rest.begin(); it != rest.end(); it++){
int PID = *it;
if(check(S.num_resource,S.need[PID],cur_available))
break;
}
if(it != rest.end()){ //找到一个可以执行完的资源
int PID = *it;
for(int i = 0; i < S.num_resource; i++)
cur_available[i] += S.allocation[PID][i]; //该进程执行完,释放资源
rest.erase(it); //该进程已经执行完,删除它
}
else SAFE = false;
}
return SAFE;
}

Sequence Banker::find_sequence(const Status &S){ //该函数和safe是一样的,本来想整合到一起,但是传参,返值挺麻烦的就算了
Sequence seq;
set<int>rest;
int cur_available[NUM_RESOURCE],cnt = 0;

seq.num_process = S.num_process;
rest.clear();
for(int i = 0; i < S.num_resource; i++)
cur_available[i] = S.available[i];
for(int i = 0; i < S.num_process; i++)
rest.insert(i);
while(!rest.empty()){
set<int>::iterator it;
for(it = rest.begin(); it != rest.end(); it++){
int PID = *it;
if(check(S.num_resource,S.need[PID],cur_available))
break;
}
//找到一个可以执行完的资源
int PID = *it;
seq.sequence[cnt++] = PID; //保存序列
for(int i = 0; i < S.num_resource; i++)
cur_available[i] += S.allocation[PID][i]; //该进程执行完,释放资源
rest.erase(it); //该进程已经执行完,删除它
}
return seq;
}

Status.cpp

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
#include "my_Status.h"
#include <iostream>
#include <cstdio>
using namespace std;

/************************Status***************************/
void Status::output_data(){
cout << "Resource" << endl;
for(int i = 0; i < num_resource; i++)
printf("%5d",resource[i]); //右对齐
cout << endl;
cout << "Available" << endl;
for(int i = 0; i < num_resource; i++)
printf("%5d",available[i]); //右对齐
cout << endl;
cout << "Claim" << endl;
for(int i = 0; i < num_process; i++){
for(int j = 0; j < num_resource; j++)
printf("%5d",claim[i][j]);
cout << endl;
}
cout << "Allocation" << endl;
for(int i = 0; i < num_process; i++){
for(int j = 0; j < num_resource; j++)
printf("%5d",allocation[i][j]);
cout << endl;
}
cout << "Need" << endl;
for(int i = 0; i < num_process; i++){
for(int j = 0; j < num_resource; j++)
printf("%5d",need[i][j]);
cout << endl;
}
/*
for(int i = 0; i < num_resource; i++)
printf("%-5d",resource[i]); //左对齐
cout << endl;
for(int i = 0; i < num_resource; i++)
printf("%05d",resource[i]); //补充前导0
cout << endl;
*/
}

Request.cpp

1
2
3
4
5
6
7
8
9
10
11
12
#include "my_Request.h"
#include <iostream>
#include <cstdio>
using namespace std;

/*************************Request************************/
void Request::output_request(){
printf("PID:%5d\n",PID);
for(int i = 0; i < num_resource; i++)
printf("%5d",request[i]);
cout << endl;
}

Sequence.cpp

1
2
3
4
5
6
7
8
9
10
11
#include "my_Sequence.h"
#include <iostream>
#include <cstdio>
using namespace std;

/************************Sequence************************/
void Sequence::output_sequence(){
for(int i = 0; i < num_process; i++)
printf("%5d",sequence[i]);
cout << endl;
}

main.cpp

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
#include "my_Banker.h"
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <string>
using namespace std;

void App(){
Status GStatus;
Banker GBanker;
Sequence GSequence;
Request GRequest;

cout << "第一步:生成数据" << endl;
GBanker.create_random_status(GStatus);
GStatus.output_data();

cout << "第二步:随机发起一次请求" << endl;
while(true){
cout << "输入create发起,输入set手动申请,输入show显示当前系统状态,输入exit退出" << endl;
string command;
getline(cin,command);
if(command == "create" || command == "set"){
if(command == "create")
GRequest = GBanker.create_random_request(GStatus.num_process,GStatus.num_resource);
else
GRequest = GBanker.set_request(GStatus.num_process,GStatus.num_resource);
GRequest.output_request();
cout << "第三步:分配资源" << endl;
int result_of_allot = GBanker.allot_resource(GRequest,GStatus);
if(result_of_allot == ILLEGAL_REQUEST)
cout << "非法的资源请求" << endl;
else if(result_of_allot == DEADLOCK_REQUEST)
cout << "可导致死锁的请求,阻塞进程" << endl;
else{
cout << "安全的请求,安全序列:" << endl;
GSequence = GBanker.find_sequence(GStatus);
GSequence.output_sequence();
}
}
else if(command == "show") GStatus.output_data();
else if(command == "exit") return ;
else cout << "非法输入" << endl;
}
}

int main(){
srand((int)time(0));
while(true){
cout << "进入系统,输入go启动" << endl;
cout << "进入系统,输入exit退出" << endl;
string command;
getline(cin,command);
if(command == "exit") break;
else if(command == "go") App();
else cout << "非法输入" << endl;
}
return 0;
}