操作系统：银行家算法（避免死锁）

红太狼 2022-07-16 10:26 390阅读 0赞

[算法][Link 1]介绍：

![Center][]![Center 1][]![Center 2][]

程序实现：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
2.   
3.              程序：银行家算法实现 
4.              作者：小单 
5.              时间: 2013年11月5日 
6.   
7.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
8.  \#include <iostream>  
9.  \#include <string>  
10. **using** **namespace** std;  
11.   
12. \#define MAXPROCESS  50  //所能执行的进程最大数  
13. \#define MAXRESOURCE 50  //资源最大数  
14.   
15. //银行家算法中的数据结构  
16. **int** Available\[MAXRESOURCE\];  //可用资源向量  
17. **int** Max\[MAXPROCESS\]\[MAXRESOURCE\];   //最大需求矩阵  
18. **int** Allocation\[MAXPROCESS\]\[MAXRESOURCE\];  //分配矩阵  
19. **int** Need\[MAXPROCESS\]\[MAXRESOURCE\];   //需求矩阵  
20. **int** Request\[MAXPROCESS\]\[MAXRESOURCE\];  //请求向量  
21.   
22. //安全性算法中的数据结构  
23. **int** Work\[MAXRESOURCE\];    //工作向量  
24. **bool** Finish\[MAXPROCESS\];    //表示是否有足够的资源分配给进程  
25. **int** SafeSeries\[MAXPROCESS\];  //安全序列  
26.   
27.   
28. **int** n;  //当前系统中的进程数  
29. **int** m;   //当前系统中的资源数  
30.   
31.   
32.   
33. //  
34. //算法初始化  
35. **void** InitAlgorithm()  
36. \{  
37.     cout << "请输入系统所要运行的进程总数:";  
38.     cin >> n;  
39.     cout << "请输入系统中分配的资源种类数：";  
40.     cin >> m;  
41.     **int** i,j;  
42.   
43.     //可利用资源向量的初始化  
44.     cout << "请分别输入" << m << "类资源的当前可利用资源数目:";  
45.     **for**( i = 0; i < m; ++i )  
46.     \{  
47.         cin >> Available\[i\];  
48.     \}  
49.   
50.     //最大需求矩阵的初始化  
51.     cout << "请输入各进程对各资源的最大需求矩阵(按"  
52.         << n << "\*" << m << "矩阵格式输入):" << endl;  
53.     **for**( i = 0; i < n; ++i )  
54.     \{  
55.         **for**( j = 0; j < m; ++j )  
56.         \{  
57.             cin >> Max\[i\]\[j\];  
58.         \}  
59.     \}  
60.   
61.     //分配矩阵的初始化  
62.     cout << "请输入分配矩阵(按"  
63.         << n << "\*" << m << "矩阵格式输入):" << endl;  
64.     **for**( i = 0; i < n; ++i )  
65.     \{  
66.         **for**( j = 0; j < m; ++j )  
67.         \{  
68.             cin >> Allocation\[i\]\[j\];  
69.         \}  
70.     \}  
71.   
72.     //需求矩阵的初始化  
73.     cout << "请输入此刻的需求矩阵(按"  
74.     << n << "\*" << m << "矩阵格式输入):" << endl;  
75.     **for**( i = 0; i < n; ++i )  
76.     \{  
77.         **for**( j = 0; j < m; ++j )  
78.         \{  
79.             cin >> Need\[i\]\[j\];  
80.         \}  
81.     \}  
82.   
83. \}  
84.   
85. //输出资源分配情况  
86. **void** PrintSrcAlloc()  
87. \{  
88.     **int** i,j;  
89.     **for**( i = 0; i < n; ++i )  
90.     \{  
91.         cout << "进程P" << i << "的总体分配情况:" << endl;  
92.         cout << "\\tMax: ";  
93.         **for**( j = 0; j < m; ++j )  
94.         \{  
95.             cout << Max\[i\]\[j\] << " ";  
96.         \}  
97.         cout << endl;  
98.   
99.         cout << "\\tAllocation：";  
100.         **for**( j = 0; j < m; ++j )  
101.         \{  
102.             cout << Allocation\[i\]\[j\] << " ";  
103.         \}  
104.         cout << endl;  
105.   
106.         cout << "\\tNeed：";  
107.         **for**( j = 0; j < m; ++j )  
108.         \{  
109.             cout << Need\[i\]\[j\] << " ";  
110.         \}  
111.         cout << endl;  
112.         cout << endl;  
113.     \}  
114.   
115.     cout << "可利用资源情况：";  
116.     **for**( i = 0; i < m; ++i )  
117.     \{  
118.         cout << Available\[i\] << " ";  
119.     \}  
120.     cout << endl;  
121.     cout << endl;  
122.   
123. \}  
124.   
125. //输出此时进程iProcess利用安全性算法的分析情况  
126. **void** PrintSafeSeries( **int** iProcess )  
127. \{  
128.     **int** j;  
129.     cout << "进程P" << iProcess << "的安全性分析情况:" << endl;  
130.     cout << "\\tWork: ";  
131.     **for**( j = 0; j < m; ++j )  
132.     \{  
133.         cout << Work\[j\] << " ";  
134.     \}  
135.     cout << endl;  
136.       
137.     cout << "\\tNeed：";  
138.     **for**( j = 0; j < m; ++j )  
139.     \{  
140.         cout << Need\[iProcess\]\[j\] << " ";  
141.     \}  
142.     cout << endl;  
143.       
144.     cout << "\\tAllocation：";  
145.     **for**( j = 0; j < m; ++j )  
146.     \{  
147.         cout << Allocation\[iProcess\]\[j\] << " ";  
148.     \}  
149.     cout << endl;  
150.       
151.     cout << "\\tWork + Allocation：";  
152.     **for**( j = 0; j < m; ++j )  
153.     \{  
154.         cout << Work\[j\] + Allocation\[iProcess\]\[j\] << " ";  
155.     \}  
156.     cout << endl;  
157.   
158.     cout << "Finish\[" << iProcess << "\] = " << Finish\[iProcess\] << endl;  
159.     cout << endl;  
160.   
161.   
162. \}  
163.   
164. //判断是否存在安全序列  
165. **bool** IsSafe()  
166. \{  
167.     **int** i;  
168.     **for**( i = 0; i < n; ++i )  
169.     \{  
170.         **if**( !Finish\[i\] )  
171.             **return** **false**;  //不存在安全序列  
172.     \}  
173.     **return** **true**;//存在安全序列  
174. \}  
175.   
176. //界面  
177. **void** Menu()  
178. \{  
179.     cout << "\\t\\t ==========================================="  << endl;  
180.     cout << "\\t\\t|                                           |" << endl;  
181.     cout << "\\t\\t|         程序：银行家算法的模拟实现        |" << endl;  
182.     cout << "\\t\\t|         作者：小单                        |" << endl;  
183.     cout << "\\t\\t|         时间：2013.11.5                   |" << endl;  
184.     cout << "\\t\\t|                                           |" << endl;  
185.     cout << "\\t\\t ==========================================="  << endl;  
186. \}  
187.   
188.   
189. //选出满足条件的进程  
190. //函数返回进程编号  
191. //若不存在满足条件的，则返回false,否则返回true  
192. **bool** SelectProcess( **int** &iProcNum )  
193. \{  
194.     iProcNum = -1;  
195.     **int** i, j;  
196.     **for**( i = 0; i < n; ++i )  
197.     \{  
198.         **if** ( Finish\[i\] )  //Finish\[i\] != false  
199.         \{  
200.             **continue**;  
201.         \}  
202.         **for** ( j = 0; j < m; ++j )  
203.         \{  
204.             **if** ( Need\[i\]\[j\] > Work\[j\] )  
205.             \{  
206.                 **break**;  
207.             \}  
208.         \}  
209.         **if** ( j == m )  //满足条件  
210.         \{  
211.             iProcNum = i;  
212.             **return** **true**;    
213.         \}  
214.     \}  
215.     **return** **false**;  
216. \}  
217.   
218. //安全性算法  
219. **bool** SafeAlgorithm()  
220. \{  
221.     **int** i,j;  
222.   
223.     //初始化Finish向量  
224.     **for**( i = 0; i < n; ++i )  
225.     \{  
226.         Finish\[i\] = **false**;  
227.     \}  
228.   
229.     //初始化工作向量  
230.     **for** ( j = 0; j < m; ++j )  
231.     \{  
232.         Work\[j\] = Available\[j\];  
233.     \}  
234.   
235.     **int** iProcNum;  
236.     //选择满足条件的进程  
237.     i = 0;  
238.     **while**( SelectProcess( iProcNum) )  
239.     \{  
240.         Finish\[iProcNum\] = **true**;  
241.         PrintSafeSeries( iProcNum );  //输出此时利用安全性算法的分析情况  
242.         **int** k;  
243.         **for** ( k = 0; k < m; ++k )  
244.         \{  
245.             Work\[k\] += Allocation\[iProcNum\]\[k\];  
246.         \}  
247.         SafeSeries\[i++\] = iProcNum;  //进程号加入安全序列数组  
248.   
249.           
250.     \}  
251.   
252.     **if**( IsSafe() )  
253.     \{  
254.         **return** **true**;  //存在一个安全序列  
255.     \}  
256.   
257.     **return** **false**;  //不存在一个安全序列  
258.   
259. \}  
260.   
261.   
262. //银行家算法  
263. **void** BankAlgorithm()  
264. \{  
265.     **int** i,j;  
266.     cout << "请输入请求分配的进程号(0 - " << n-1 << "): ";  
267.     cin >> i;  
268.     cout << "请依次输入进程P" << i << "对" << m << "类资源的请求分配量: ";  
269.     **for**( j = 0; j < m; ++j )  
270.     \{  
271.         cin >> Request\[i\]\[j\];  
272.     \}  
273.   
274.     //步骤一  
275.     **for**( j = 0; j < m; ++j )  
276.     \{  
277.         **if**( Request\[i\]\[j\] > Need\[i\]\[j\] )  
278.         \{  
279.             cout << "请求的资源已超过该资源宣布的最大值，请求资源失败!!" << endl;  
280.             **return**;  
281.         \}  
282.     \}  
283.   
284.     //步骤二  
285.     **for**( j = 0; j < m; ++j )  
286.     \{  
287.         **if**( Request\[i\]\[j\] > Available\[j\] )  
288.         \{  
289.             cout << "没有足够的资源，请求资源失败!!" << endl;  
290.             **return**;  
291.         \}  
292.     \}  
293.   
294.     //步骤三  
295.     //系统试探着把资源分配给进程Pi，并修改相应的数值  
296.     **for** ( j = 0; j < m; ++j )  
297.     \{  
298.         Available\[j\] -= Request\[i\]\[j\];  
299.         Allocation\[i\]\[j\] += Request\[i\]\[j\];  
300.         Need\[i\]\[j\] -= Request\[i\]\[j\];  
301.     \}  
302.   
303.     //步骤四  
304.     //系统执行安全性算法  
305.     **if** ( !SafeAlgorithm() ) //检测到不安全，则恢复原来的状态  
306.     \{  
307.         **for** ( j = 0; j < m; ++j )  
308.         \{  
309.             Available\[j\] += Request\[i\]\[j\];  
310.             Allocation\[i\]\[j\] -= Request\[i\]\[j\];  
311.             Need\[i\]\[j\] += Request\[i\]\[j\];  
312.         \}     
313.     \}  
314.   
315. \}  
316.   
317.   
318.   
319. **int** main()  
320. \{  
321.     Menu();  
322.     InitAlgorithm();  
323.     PrintSrcAlloc();  //打印当前资源情况  
324.     system("pause");  
325.     SafeAlgorithm();  
326.     **while**(1)  
327.     \{  
328.         string flag;  
329.         **if**( IsSafe() )  
330.         \{  
331.             //存在安全序列  
332.             cout << "恭喜！！资源分配成功!!" << endl;  
333.             **int** i;  
334.             cout << "此时刻存在的一个安全序列为：";  
335.             **for** ( i = 0; i < n - 1; ++i )  
336.             \{  
337.                 cout << "P" << SafeSeries\[i\] << "-->";  
338.             \}  
339.             cout << "P" << SafeSeries\[i\] << endl;  
340.             cout << "继续操作吗？\[Y/N\]:";  
341.             cin >> flag;  
342.         \}  
343.         **else**  
344.         \{  
345.             cout << "资源分配失败!!" << endl;  
346.             cout << "继续操作吗？\[Y/N\]:";  
347.             cin >> flag;  
348.         \}  
349.   
350.         **if** ( flag == "Y" || flag == "y" )  
351.         \{  
352.             ;  
353.         \}  
354.         **else**  
355.         \{  
356.             **break**;  
357.         \}  
358.         BankAlgorithm(); //执行银行家算法  
359.   
360.     \}  
361.   
362.   
363.     **return** 0;  
364.   
365. \}

程序测试结果如下：

![Center 3][]![Center 4][]![Center 5][]![Center 6][]![Center 7][]![Center 8][]

[Link 1]: http://lib.csdn.net/base/datastructure
[Center]: https://img-blog.csdn.net/20150602093650139?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20150602093659515?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20220716/b2dccc35fb7241b3a266703fb0f8997a.png
[view plain]: http://blog.csdn.net/s634772208/article/details/46324257?locationNum=2#
[Center 3]: https://img-blog.csdn.net/20150602094228553?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: https://img-blog.csdn.net/20150602094358765?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: https://img-blog.csdn.net/20150602094403336?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 6]: https://img-blog.csdn.net/20150602094408032?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 7]: https://img-blog.csdn.net/20150602094248521?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvczYzNDc3MjIwOA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 8]: /images/20220716/c559e99b76bf4d32be0da97ce24be846.png