利用银行家算法避免死锁
一． 课程设计目的
1. 加深对死锁概念的理解。
2. 能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在。
二． 课程设计摘要
银行家算法：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
三． 开发环境
系统软件硬件环境
软件：Windows XP; VC++ 6.0
硬件：Pentium(R) 4 CPU 2.40GHz;512MB内存
四．课程设计原理分析
在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防死锁。最有代表性的避免死锁的方法，是Dijkstra的银行家算法。
银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，第一个为互斥条件，即一个资源每次只能由一个进程占用；第二个为请求和保持条件，指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。
银行家算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.
五．银行家算法流程图
图片找不到了，嘿嘿
六．银行家算法中的数据结构
（1） 可利用资源向量Available。这是一个含有m个元素的数组，其中的，每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。
（2） 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
（3） 分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
（4） 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
七．算法描述
1.银行家算法:
设进程i提出请求Request[j]，则银行家算法按如下规则进行判断。
(1) 如果Request[j]≤Need[i,j]，则转向（2），否则认为出错。
(2) 如果Request[j]≤Available[j]，则转向（3）；否则表示尚无足够资源，Pi需等待。
(3) 假设进程i的申请已获批准，于是修改系统状态：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
2.安全性检查
(1) 设置两个工作向量Work=Available；Finish[i]=False
(2) 从进程集合中找到一个满足下述条件的进程，
Finish [i]=False;
Need[i,j]≤Work[j];
如找到，执行(3)；否则，执行(4)
(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work[j]=Work[i]+Allocation[i,j];
Finish[i]=True;
go to step 2;
(4) 如所有的进程Finish[i]=true，则表示安全；否则系统不安全。
1
#include<iostream>
2#include<cstdlib>
3#define maxn 100
4using namespace std;
5
6typedef struct process_control_blank
7
{
8
int finsh[maxn];
9 int Max[maxn][maxn];
10 int Allocation[maxn][maxn];
11 int need[maxn][maxn];
12 int request[maxn][maxn];
13 int Available[maxn];
14 int process[maxn];
15
}Pcb;
16Pcb PCB;
17int work[maxn];
18int l;
19char Flag;
20int m,n;
21int safe(); //判断是否处于安全状态
22
23void input()
24{
25
26 cout<<"请输入进程数目:\n";
27 cin>>m;
28 cout<<"请输入资源数目:\n";
29 cin>>n;
30 cout<<"请输入Available矩阵\n";
31 for(int i=0;i<m;i++)
32 for(int j=0;j<n;j++)
33
{
34 cin>>PCB.Allocation[i][j];
35
}
36 cout<<"请输入Max矩阵\n";
37 for(int i=0;i<m;i++)
38 for(int j=0;j<n;j++)
39 {
40 cin>>PCB.Max[i][j];
41 }
42 for(int i=0;i<m;i++)
43 for(int j=0;j<n;j++)
44 {
45 PCB.need[i][j]=PCB.Max[i][j]-PCB.Allocation[i][j];
46 }
47 cout<<"请输入每个进程初始的资源可用数：\n";
48 for(int i=0;i<n;i++)
49 cin>>PCB.Available[i];
50
51 // cout<<"need 矩阵如下:\n";
52// for(int i=0;i<m;i++)
53// {for(int j=0;j<n;j++)
54// cout<<PCB.need[i][j]<<" ";
55// cout<<endl;
56// }
57
58}
59
60int safe()
61{
62 int i,j,k;
63 l=0;
64 for(i=0;i<n;i++)
65 work[i]=PCB.Available[i];
66 for(i=0;i<m;i++)
67 PCB.finsh[i]=0;
68
69 for(i=0;i<m;i++)
70 {
71 if(PCB.finsh[i]==1)
72 continue;
73 else
74 {
75 for(j=0;j<n;j++)
76 {
77 if(PCB.need[i][j]>work[j])
78 break;
79 }
80 if(j==n) //可分配
81 {
82 PCB.finsh[i]=1;
83 for(k=0;k<n;k++)
84 work[k]+=PCB.Allocation[i][k];
85 PCB.process[l++]=i;
86 i=-1; //重新开始
87 }
88 else
89 continue;
90 }
91 if(l==m)
92 {
93 cout<<"安全序列如下:\n";
94 for(k=0;k<l;k++)
95 { cout<<"P"<<PCB.process[k];
96 if(k!=l-1)
97 cout<<"-->";
98 }
99 cout<<endl;
100 return 1;
101 }
102 } //for
103 // return 0;
104}
105int Request()
106{
107 int i,j;
108 while(1)
109 {
110 cout<<"输入你要请求资源的进程(下标从0开始)\n";
111 int ps;
112 cin>>ps;
113 cout<<"输入该进程所请求的资源数目\n";
114 for(i=0;i<n;i++)
115 {
116 cin>>PCB.request[ps][i];
117 if(PCB.request[ps][i]>PCB.need[ps][i])
118 {
119 cout<<"请求的资源数目大于该进程所需要的数目\n";
120 return 0;
121 }
122 if(PCB.request[ps][i]>PCB.Available[i])
123 {
124 cout<<"请求的资源数目大于可用的资源数目\n";
125 return 0;
126 }
127 }
128 for(i=0;i<n;i++)
129 {
130 PCB.need[ps][i]-=PCB.request[ps][i];
131 PCB.Available[i]-=PCB.request[ps][i];
132 PCB.Allocation[ps][i]+=PCB.request[ps][i];
133 }
134 if(safe())
135 {
136 cout<<"同意分配请求\n";
137 }
138 else
139 {
140 cout<<"SORRY~~~~~你的请求被拒绝~~~\n";
141 for(i=0;i<n;i++)
142 {
143 PCB.need[ps][i]+=PCB.request[ps][i];
144 PCB.Available[i]+=PCB.request[ps][i];
145 PCB.Allocation[ps][i]-=PCB.request[ps][i];
146 }
147 }
148 for(i=0;i<n;i++)
149 PCB.finsh[i]=0;
150 cout<<"是否再次请求分配？是请按Y/y，否请按N/n";
151 while(1)
152 {
153 cin>>Flag;
154 if(Flag=='Y' || Flag=='y' || Flag=='N' || Flag=='n')
155 break;
156 else
157 {
158 cout<<"请按要求重新输入:\n";
159 continue;
160 }
161 }
162 if(Flag=='Y' || Flag=='y')
163 continue;
164 else
165 break;
166
167 }//while
168}
169int main()
170{
171 input();
172 safe();
173 Request();
174 system("pause");
175 return 0;
176}
177