利用銀行家算法避免死鎖
一． 課程設計目的
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