操作系統(tǒng)之銀行家算法—詳解流程及案例數(shù)據(jù)

操作系統(tǒng)之進(jìn)程調(diào)度——優(yōu)先權(quán)法和輪轉(zhuǎn)法（附上樣例講解）

操作系統(tǒng)之銀行家算法—詳解流程及案例數(shù)據(jù)

操作系統(tǒng)之多線程編程—讀者優(yōu)先/寫者優(yōu)先詳解

操作系統(tǒng)之存儲(chǔ)管理——FIFO算法和LRU算法

操作系統(tǒng)之磁盤調(diào)度——SCAN實(shí)例講解

要求

銀行家是操作系統(tǒng)比較經(jīng)典的算法之一，他比較好的防止死鎖情況的出現(xiàn)，增加了系統(tǒng)的安全性.在編寫銀行家算法的過(guò)程中，對(duì)操作系統(tǒng)的銀行家算法有了深入了解和心得。

一、實(shí)驗(yàn)?zāi)康?/p>

死鎖會(huì)引起計(jì)算機(jī)工作僵死，因此操作系統(tǒng)中必須防止。本實(shí)驗(yàn)的目的在于讓學(xué)生獨(dú)立的使用高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，了解死鎖產(chǎn)生的條件和原因，并采用銀行家算法有效地防止死鎖的發(fā)生，以加深對(duì)課堂上所講授的知識(shí)的理解。

二、實(shí)驗(yàn)要求

設(shè)計(jì)有n個(gè)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)，進(jìn)程可動(dòng)態(tài)的申請(qǐng)和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。

系統(tǒng)能顯示各個(gè)進(jìn)程申請(qǐng)和釋放資源，以及系統(tǒng)動(dòng)態(tài)分配資源的過(guò)程，便于用戶觀察和分析；

三、數(shù)據(jù)結(jié)構(gòu)

1．可利用資源向量Available ，它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源的數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available（j）=k，標(biāo)是系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。

2．最大需求矩陣Max，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max（i，j）=k，表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。

3．分配矩陣Allocation，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中的每類資源當(dāng)前一分配到每一個(gè)進(jìn)程的資源數(shù)。如果Allocation（i，j）=k，表示進(jìn)程i當(dāng)前已經(jīng)分到Rj類資源的數(shù)目為k。Allocation i表示進(jìn)程i的分配向量，有矩陣Allocation的第i行構(gòu)成。

4．需求矩陣Need，這是一個(gè)n×m的矩陣，用以表示每個(gè)進(jìn)程還需要的各類資源的數(shù)目。如果Need（i，j）=k，表示進(jìn)程i還需要Rj類資源k個(gè)，才能完成其任務(wù)。Need i表示進(jìn)程i的需求向量，由矩陣Need的第i行構(gòu)成。

上述三個(gè)矩陣間存在關(guān)系：Need（i，j）=Max（i，j）-Allocation（i，j）；

四、安全性算法

1．設(shè)置兩個(gè)向量。

Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目，它包含m個(gè)元素，開(kāi)始執(zhí)行安全性算法時(shí)，Work = Available。

Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開(kāi)始Finish（I）=false；當(dāng)有足夠資源分配給進(jìn)程Pi時(shí)，令Finish（i）=true；

2．從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程。

Finish（i）= = false；

Need i ≤work；

如找到則執(zhí)行步驟3；否則，執(zhí)行步驟4；

3．當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行

Work = work Allocation i

Finish（i）=true；轉(zhuǎn)向步驟2；

4．若所有進(jìn)程的Finish（i）都為true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

流程圖：

個(gè)人覺(jué)得。總的來(lái)說(shuō)，銀行家算法就是一個(gè)模擬借錢。判斷假如借錢是否安全然后考慮借不借的問(wèn)題。

先放代碼，和數(shù)據(jù)再說(shuō)分析：

代碼

import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class bank { static Scanner sc=new Scanner(System.in); static int n; static int m; static int available[]; static int max[][];//最大需求矩陣 static int allocation[][];//當(dāng)前分配到每一個(gè)進(jìn)程的 static int need[][];//需求矩陣 static boolean isrelesed[];//資源是否已經(jīng)釋放 public static void main(String[] args) { // TODO 自動(dòng)生成的方法存根 System.out.println("請(qǐng)輸入資源種類m："); m=sc.nextInt();//系統(tǒng)資源 initm(m);//初始相關(guān) System.out.println("輸入進(jìn)程數(shù)量"); n=sc.nextInt();//進(jìn)程數(shù)量 initn(n);//初始相關(guān)矩陣 //getstatus();//輸出當(dāng)前狀態(tài) while(true) { applyresouse();//申請(qǐng)資源 } } static void applyresouse()//申請(qǐng)資源 { getstatus();//輸出狀態(tài) int request[]=new int[m];//需求量 為了節(jié)省空間寫成全部變量 System.out.println("輸入你想申請(qǐng)資源的編號(hào)"); int index=sc.nextInt(); while(0>index||index>=n) {System.out.println("輸入的編號(hào)不在編號(hào)范圍之內(nèi)，請(qǐng)重新輸入");index=sc.nextInt(); } while(isrelesed[index]) {System.out.println("改編號(hào)已經(jīng)完成資源的釋放，無(wú)法再請(qǐng)求資源，請(qǐng)重新輸入");index=sc.nextInt(); while(0>index||index>=n) {System.out.println("輸入的編號(hào)不在編號(hào)范圍之內(nèi)，請(qǐng)重新輸入");index=sc.nextInt(); }} System.out.println("請(qǐng)輸入"+m+"個(gè)資源申請(qǐng)的個(gè)數(shù)（不申請(qǐng)的資源用0替代）"); int team=0; while(team==0) { for(int i=0;iavailable[i]) {team=1;} if(request[i]>max[index][i]) {team=2;} } if(team==1) {System.out.println("您的請(qǐng)求量超出 了系統(tǒng)提供量，請(qǐng)重新輸入");team=0;}//重新循環(huán) else if(team==2) {System.out.println("您的請(qǐng)求量超出 了最大請(qǐng)求量max，請(qǐng)重新輸入");team=0;} else team=3;//退出循環(huán)用 } //賦值成功后開(kāi)始 boolean isfinish= ifallocate(index,request); if(isfinish) {System.out.println("所有進(jìn)程完成資源分配，分配結(jié)束");System.exit(0);} } private static boolean ifallocate(int index,int[] request) {//假設(shè)分配 /* * 首先要將真的數(shù)組克隆，模擬已經(jīng)給資源，然后判斷這個(gè)資源是否安全 */ int work[]=available.clone(); boolean finish[]=isrelesed.clone();//克隆初始狀態(tài) int need2[][]=new int[n][m];int allocate2[][]=new int[n][m]; for(int i=0;iq1=new ArrayDeque();//如果能完成的隊(duì)列 int time=0; while(true) { boolean loop=true; for(int i=0;in) {return false;} } //return false; } static void initm(int m) { System.out.println("請(qǐng)輸入"+m+"種資源的最大量"); available=new int[m]; isrelesed=new boolean[m]; //request=new int[m]; for(int i=0;iavailable[j]) {jud=true;} } if(jud) {System.out.println("最大需求輸入有誤，請(qǐng)重新賦值（m個(gè)數(shù)）");i--;}//i自減滿足條件 } System.out.println("n個(gè)線程m種資源最大需求賦值完成\n請(qǐng)輸入當(dāng)前進(jìn)程已分配資源情況");//初始max for(int i=0;imax[i][j]){jud=true;} } if(jud) {System.out.println("輸入有誤，請(qǐng)重新輸入");i--;}//輸入有錯(cuò)誤 } System.out.println("allocate(當(dāng)前已分配矩陣已經(jīng)分配完畢)"); } static void getstatus()//輸出狀態(tài) { for(int i=0;i

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

分析

A還—>借B—>B還—>C—這樣可以到最后。但是很多情況下客戶是分期借的，這就要考慮安全性問(wèn)題，比如A借6，6，6還剩4，4，4那么這個(gè)銀行做多最多只能借2，2，2給其他人，因?yàn)橐坏┙瓒嗔薃也無(wú)法釋放，那么就造成死鎖。那么這種情況就不能夠借錢。所以在借錢的時(shí)候需要一個(gè)模擬的過(guò)程。

還有比較重要的是明白銀行加算法各個(gè)矩陣的意義和作用非常的重要，我剛開(kāi)始看銀行家算法的時(shí)候因?yàn)閷?duì)一些基礎(chǔ)概念和數(shù)組矩陣的屬性不夠了解，茫然了很久，也走了很多的坑。那么就先介紹一下吧。

對(duì)于全局變量，我的代碼中有：

這些變量是在安全狀態(tài)下的真實(shí)變量其中:

(1)n是線程的數(shù)量，m是資源的種類。

Available[]是當(dāng)前還可以使用的資源。也就是銀行家手中被借出去錢，手中還剩余各種錢的數(shù)量。只跟資源有關(guān)

Max[][]是最大需求矩陣，也可以理解為最終終態(tài)矩陣，因?yàn)檫@個(gè)max的狀態(tài)就是客戶想達(dá)到和滿足的狀態(tài)。也就是線程可以釋放的狀態(tài)。

Allocate[][]是已分配矩陣。就是客戶已經(jīng)借到的錢。也就是線程已經(jīng)占有的資源量

Need[][]是還需要資源情況，由max和allcate決定。

Isrelese[]這個(gè)數(shù)組和線程有關(guān)和資源無(wú)關(guān)，它記錄的就是線程是否達(dá)到終態(tài)，完成資源釋放的情況，，一旦完成借錢就不需要借錢。

3：最后在具體實(shí)現(xiàn)的過(guò)程中。由于需要模擬過(guò)程，還是會(huì)遇到挺多坎的，在理清思路之后。在代碼上還是由挺多要注意的。

第一：對(duì)象克隆（深淺拷貝），在模擬的過(guò)程中擁有初始化和真實(shí)數(shù)據(jù)一樣的數(shù)組。但是如果直接賦值那么新對(duì)象指向的還是老數(shù)組的地址，會(huì)造成數(shù)據(jù)紊亂。那么對(duì)象克隆就一定要保證只賦值數(shù)據(jù)，不復(fù)制地址。

第二：模擬數(shù)值的改變，無(wú)論在申請(qǐng)資源，還是釋放資源的時(shí)候，模擬的數(shù)值都會(huì)改變。但是不過(guò)如果模擬成功，真實(shí)數(shù)組會(huì)增加多少。這個(gè)需要尤其注意，同時(shí)，如果發(fā)現(xiàn)數(shù)值和預(yù)期不符合可以打斷點(diǎn)單步調(diào)試。

附上我自己的流程圖：

初始化：

借錢：

ps:本人有點(diǎn)菜，這里面可能有挺多的是錯(cuò)誤的。。如果有大佬發(fā)現(xiàn)請(qǐng)指正。

如果對(duì)后端、爬蟲(chóng)、數(shù)據(jù)結(jié)構(gòu)算法等感性趣歡迎關(guān)注我的個(gè)人公眾號(hào)交流：bigsai

任務(wù)調(diào)度 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。