一、银行家算法

课本伪代码的实现,避免死锁

二、代码实现

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
285
286
287
288
289
290
291
292
#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义全局变量
const int x=50,y=50; //x为进程个数 y为资源种类数
int Available[y]; //各资源可利用的数量
int Allocation[x][y]; //各进程当前已分配的资源数量
int Max[x][y]; //各进程对各类资源的最大需求数
int Need[x][y]; //尚需多少资源
int Request[y]; //申请多少资源
int Work[y]; //工作向量,表示系统可提供给进程继续运行所需的各类资源数量
int Finish[x]; //表示系统是否有足够的资源分配给进程,1为是
int p[x]; //存储安全序列
int i,j; //i表示进程,j表示资源
int n,m; //n为进程i的数量,m为资源j种类数
int l=0; //l用来记录有几个进程是Finish[i]=1的,当l=n是说明系统状态是安全的
int counter=0; //记数器,记录可执行的进程数
//函数声明
void chushihua(); //初始化函数
void safe(); //安全性算法
void show(); //函数show,输出当前状态
void bank(); //银行家算法
void jieshu(); //结束函数
void chushihua()
{
cout<<"输入进程的数量: ";//从此开始输入有关数据
cin>>n;
cout<<"输入资源种类数: ";
cin>>m;
cout<<endl<<"输入各种资源当前可用的数量( "<<m<<" 种): "<<endl;
for (j=0; j<m; j++)//m为资源数
{
cout<<"输入资源 "<<j<<" 可利用的数量Available["<<j<<"]: ";
cin>>Available[j]; //输入数字的过程
Work[j]=Available[j]; //初始化Work[j],它的初始值就是当前可用的资源数
}
cout<<endl<<"输入各进程当前已分配的资源数量Allocation["<<n<<"]["<<m<<"]: "<<endl;
for (i=0; i<n; i++) //n为进程数
{
for (j=0; j<m; j++)//m为资源数
{
cout<<" 输入进程 "<<i<<" 当前已分配的资源 "<<j<<" 数量: ";
cin>>Allocation[i][j];
}
cout<<endl;
Finish[i]=0;//初始化Finish[i]
}
cout<<endl<<"输入各进程对各类资源的最大需求Max["<<n<<"]["<<m<<"]: "<<endl;
for (i=0; i<n; i++)//n为进程数
{
for (j=0; j<m; j++)//m为资源数
{
cout<<" 输入进程 "<<i<<" 对资源 "<<j<<" 的最大需求数: ";
cin>>Max[i][j];
if(Max[i][j]>=Allocation[i][j]) //若最大需求大于已分配,则计算需求量
Need[i][j] = Max[i][j]-Allocation[i][j];
else
Need[i][j]=0;//Max小于已分配的时候,此类资源已足够不需再申请
}
cout<<endl;
}
cout<<endl<<"初始化完成"<<endl;
}
//安全性算法函数
void safe()
{
l=0;//l用来记录有几个进程是Finish[i]=1的,当l=n是说明系统状态是安全的
for (i=0; i<n;i++)//n为进程数
{
if (Finish[i]==0)
{ //逐个查找Finish[i]==0的进程 条件一
counter=0; //记数器,记录有多少个进程已经执行
for (j=0; j<m; j++)//m为资源数
{
if (Work[j]>=Need[i][j])
counter=counter+1;//可用大于需求,记数,该进程可以执行
}
if(counter==m) //i进程的每类资源都符合Work[j]>=Need[i][j] 条件二
{
p[l]=i; //存储安全序列
Finish[i]=1; //i进程标志为可分配
for (j=0; j<m;j++)
Work[j]=Work[j]+Allocation[i][j]; //释放资源
l=l+1; //记数,现在有l个进程是安全的,当l=n时说明满足安全序列
i= -1; //从第一个进程开始继续寻找满足条件一二的进程
}
}
}
}
//显示当前状态函数
void show() //函数show,输出当前资源分配情况
{
int i,j; //局部变量,i表示进程,j表示资源
int All[y]; //各种资源的总数量
int L1; //局部变量L1
cout<<"当前的状态为:"<<endl;
cout<<"各种资源的总数量:"<<endl;
for (j=0;j<m;j++)//m为资源数
{
cout<<" 资源"<<j<<": ";
All[j]=Available[j]; //总数量=可用的+已分配的
for(i=0;i<n;i++) //n为进程数
All[j]+=Allocation[i][j];
cout<<All[j]<<" ";
}
cout<<endl<<"当前各种资源可用的量为(available):"<<endl;
for(j=0;j<m;j++)//m为资源数
cout<<" 资源"<<j<<": "<<Available[j]<<" ";
cout<<endl<<"各进程所需的最大资源量(Max): "<<endl;
for(i=0;i<m;i++)//m为资源数
{
cout<<" 资源"<<i<<" ";
}
cout<<endl;
for(L1=0;L1<n;L1++)//n为进程数
{
cout<<"进程"<<L1<<": ";
for (j=0;j<m;j++)
cout<<Max[L1][j]<<" ";
cout<<endl;
}
cout<<endl<<"各进程已经得到的资源量(allocation): "<<endl;
for(i=0;i<m;i++)//m为资源数
{
cout<<" 资源"<<i<<" ";
}
cout<<endl;
for(L1=0;L1<n;L1++)//n为进程数
{
cout<<"进程"<<L1<<": ";
for (j=0;j<m;j++)
cout<<Allocation[L1][j]<<" ";
cout<<endl;
}
cout<<endl<<"各进程还需要的资源量(need):"<<endl;
for(i=0;i<m;i++)//m为资源数
{
cout<<" 资源"<<i<<" ";
}
cout<<endl;
for(L1=0;L1<n;L1++)
{
cout<<"进程"<<L1<<": ";
for (j=0;j<m;j++)
cout<<Need[L1][j]<<" ";
cout<<endl;
}
}
//银行家算法函数
void bank()
{
cout<<endl<<"进程申请分配资源:"<<endl;
int k=0; //用于输入进程编号
bool r=false; // 初值为假,输入Y继续申请则置为真
do{//输入请求
cout<<"输入申请资源的进程(0-"<<n-1<<"): ";
cin>>k;//进程编号
cout<<endl;
while(k>n-1) //输入错误处理
{
cout<<endl<<"无该进程号,重新输入:"<<endl;
cout<<endl<<"输入申请资源的进程(0--"<<n-1<<"): ";
cin>>k;//进程编号
cout<<endl;
}
cout<<endl<<"输入该进程申请各类资源的数量: "<<endl;
for (j=0; j<m; j++)//m为资源数
{
do{ //do……while 循环判断申请输入的情况
cout<<"进程 "<<k<<" 申请资源["<<j<<"]的数量:";
cin>>Request[j];//输入请求进程数
cout<<endl;
if(Request[j]>Need[k][j]){ //申请大于需求量时出错,提示重新输入 cout<<"申请量大于需要量!"<<endl;
cout<<"申请的资源"<<j<<"的数量为"<<Request[j]<<",大于进程"<<k<<"对该资源需求量"<<Need[k][j]<<"。"<<endl;
cout<<"重新输入!"<<endl;
}
//先判断是否申请大于需求量,再判断是否申请大于可利用量
else if(Request[j]>Available[j]){ //申请大于可利用量, 应该阻塞等待
cout<<"\n没有那么多资源,目前可利用资源"<<j<<"数量为"<<Available[j]<<",本次申请不成功,进程等待!"<<endl;
Finish[k]=0; //该进程等待
goto error; //goto语句跳转,结束本次申请
}
}while(Request[j]>Need[k][j]); //Request[j]>Available[j]
}
//改变Available、Allocation、Need的值
for (j=0; j<m; j++) {//m为资源数
Available[j] = Available[j]-Request[j];//可用的资源数=可用的资源数-请求分配的资源数
Allocation[k][j] = Allocation[k][j]+Request[j];//已分配的资源数=已分配的资源数+请求的资源数
Need[k][j] = Need[k][j]-Request[j];//还需要的资源数=还需要的资源数-请求的资源数
Work[j] = Available[j];
}
safe(); //调用安全性算法函数,判断当前状态的安全性
if (l<n)//l用来记录有几个进程是Finish[i]=1的,当l=n是说明系统状态是安全的
{
l=0;
cout<<"\n试分配后,状态不安全,所以不予分配!恢复原状态"<<endl;
//恢复数据
for (j=0; j<m; j++)//m为资源数
{
Available[j] = Available[j]+Request[j];
Allocation[k][j] = Allocation[k][j]-Request[j];
Need[k][j] = Need[k][j]+Request[j];
Work[j] = Available[j];
}
for (i=0; i<n; i++)//n为进程数
Finish[i]=0; //进程均置为未分配状态
}
else//l=n,即所有的Finish[i]=1,每一个进程均能执行
{
l=0;//判断标志
cout<<"\n申请资源成功!!!"<<endl;
for(j=0;j<m;j++)//m为资源数
{
if(Need[k][j]==0);
else { //有一种资源还没全部申请到,则该进程不可执行,不能释放拥有的资源
l=1; //置l为1,作为判断标志
break;
}
}
if(l!=1){ //进程可以执行,则释放该进程的所有资源
for (j=0;j<m;j++){//m为资源数
Available[j]=Available[j]+Allocation[k][j];
Allocation[k][j]=0;
}
cout<<"该进程已得到所有需求资源,执行后将释放其所有拥有资源!"<<endl;
}
l=0; //归零
cout<<"\n安全的状态!"<<endl;
cout<<"安全序列为: ";
cout<<endl<<"进程"<<"("<<p[0]<<")"; //输出安全序列,考虑显示格式,先输出第一个
Finish[0]=0;
for (i=1; i<n; i++){
cout<<"==>>"<<"进程"<<"("<<p[i]<<")";
Finish[i]=0; //所有进程置为未分配状态
}
cout<<endl<<endl;
}
show(); //显示当前状态
error: //申请大于可利用量, 应该阻塞等待,结束本次资源申请,GOTO 语句跳转至此
cout<<endl<<"是否继续申请资源(y/n)或(Y/N)?";
char* b=new char; //输入y/n,判断是否继续申请 <<endl
cin>>b;
cout<<endl;
cout<<"-------------------------------------------"<<endl<<endl;
cout<<endl;
if(*b=='y'||*b=='Y')
r=true;//继续申请
else{
r=false; //不继续申请
jieshu(); //调用结束函数
}
} while (r==true);
}
//结束函数
void jieshu()
{
cout<<endl<<endl;
cout<<"\t\t 演示计算完毕"<<endl;
cout<<endl<<endl;
}
//主函数
int main()
{
cout<<endl<<endl<<"\t\t\t\t模拟银行家算法"<<endl<<endl;
chushihua(); //初始化函数调用
cout<<endl;
show(); //输出当前状态
safe(); //判断当前状态的安全性
if (l<n) //l在safe中是用来记录安全的进程的个数的
{
cout<<"\n当前状态不安全,拒绝申请!"<<endl;
cout<<endl;
return 0;
}
else
{
int i; //局部变量
l=0;
cout<<endl<<"\n当前的状态是安全的!安全序列为:"<<endl;
cout<<"进程"<<"("<<p[0]<<")"; //输出安全序列
for (i=1; i<n; i++)
cout<<"->>"<<"进程"<<"("<<p[i]<<")";
for (i=0; i<n; i++)
Finish[i]=0; //所有进程置为未分配状态
cout<<endl;
}
bank(); //调用银行家算法函数
cout<<"\t\t 演示计算完毕"<<endl;
return 0;
}

留言评论区

小伙伴可以登录GitHub账号使用utteranc评论,也可以使用valine评论✨