利用銀行家算法避免死鎖
一． 課程設(shè)計目的
1. 加深對死鎖概念的理解。
2. 能夠利用銀行家算法，有效避免死鎖的發(fā)生，或檢測死鎖的存在。
二． 課程設(shè)計摘要
銀行家算法：
我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當(dāng)進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。
三． 開發(fā)環(huán)境
系統(tǒng)軟件硬件環(huán)境
軟件：Windows XP; VC++ 6.0
硬件：Pentium(R) 4 CPU 2.40GHz;512MB內(nèi)存
四．課程設(shè)計原理分析
在多道程序系統(tǒng)中，雖可借助于多個進程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險——死鎖。所謂死鎖，是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進程處于這種僵局狀態(tài)時，若無外力作用，它們都將無法再向前推進。為保證系統(tǒng)中諸進程的正常運行，應(yīng)事先采取必要的措施，來預(yù)防死鎖。最有代表性的避免死鎖的方法，是Dijkstra的銀行家算法。
銀行家算法是避免死鎖的一種重要方法，通過編寫一個簡單的銀行家算法程序，加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。死鎖的產(chǎn)生，必須同時滿足四個條件，第一個為互斥條件，即一個資源每次只能由一個進程占用；第二個為請求和保持條件，指進程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放；第三個為非剝奪條件，即在出現(xiàn)死鎖的系統(tǒng)中一定有不可剝奪使用的資源；第四個為循環(huán)等待條件，系統(tǒng)中存在若干個循環(huán)等待的進程，即其中每一個進程分別等待它前一個進程所持有的資源。防止死鎖的機構(gòu)只能確保上述四個條件之一不出現(xiàn)，則系統(tǒng)就不會發(fā)生死鎖。通過這個算法可以用來解決生活中的實際問題，如銀行貸款等。
銀行家算法，顧名思義是來源于銀行的借貸業(yè)務(wù)，一定數(shù)量的本金要應(yīng)多個客戶的借貸周轉(zhuǎn)，為了防止銀行家資金無法周轉(zhuǎn)而倒閉，對每一筆貸款，必須考察其是否能限期歸還。在操作系統(tǒng)中研究資源分配策略時也有類似問題，系統(tǒng)中有限的資源要供多個進程使用，必須保證得到的資源的進程能在有限的時間內(nèi)歸還資源，以供其他進程使用資源。如果資源分配不得到就會發(fā)生進程循環(huán)等待資源，則進程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。把一個進程需要和已占有資源的情況記錄在進程控制中，假定進程控制塊PCB其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當(dāng)進程在處于等待態(tài)時，表示系統(tǒng)不能滿足該進程當(dāng)前的資源申請。“資源需求總量”表示進程在整個執(zhí)行過程中總共要申請的資源量。顯然，，每個進程的資源需求總量不能超過系統(tǒng)擁有的資源總數(shù), 銀行算法進行資源分配可以避免死鎖.
五．銀行家算法流程圖
圖片找不到了，嘿嘿
六．銀行家算法中的數(shù)據(jù)結(jié)構(gòu)
（1） 可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的，每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。
（2） 最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示進程i需要Rj類資源的最大數(shù)目為K。
（3） 分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果Allocation[i,j]=K，則表示進程i當(dāng)前已分得Rj類資源的數(shù)目為K。
（4） 需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)。
七．算法描述
1.銀行家算法:
設(shè)進程i提出請求Request[j]，則銀行家算法按如下規(guī)則進行判斷。
(1) 如果Request[j]≤Need[i,j]，則轉(zhuǎn)向（2），否則認為出錯。
(2) 如果Request[j]≤Available[j]，則轉(zhuǎn)向（3）；否則表示尚無足夠資源，Pi需等待。
(3) 假設(shè)進程i的申請已獲批準，于是修改系統(tǒng)狀態(tài)：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進程等待。
2.安全性檢查
(1) 設(shè)置兩個工作向量Work=Available；Finish[i]=False
(2) 從進程集合中找到一個滿足下述條件的進程，
Finish [i]=False;
Need[i,j]≤Work[j];
如找到，執(zhí)行(3)；否則，執(zhí)行(4)
(3) 設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。
Work[j]=Work[i]+Allocation[i,j];
Finish[i]=True;
go to step 2;
(4) 如所有的進程Finish[i]=true，則表示安全；否則系統(tǒng)不安全。
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(); //判斷是否處于安全狀態(tài)
22
23void input()
24{
25
26 cout<<"請輸入進程數(shù)目:\n";
27 cin>>m;
28 cout<<"請輸入資源數(shù)目:\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<<"請輸入每個進程初始的資源可用數(shù)：\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<<"輸入該進程所請求的資源數(shù)目\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<<"請求的資源數(shù)目大于該進程所需要的數(shù)目\n";
120 return 0;
121 }
122 if(PCB.request[ps][i]>PCB.Available[i])
123 {
124 cout<<"請求的資源數(shù)目大于可用的資源數(shù)目\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