操作系統(tǒng)課程設(shè)計(jì)---銀行家算法 (2)

1、<p>　　操作系統(tǒng)課程設(shè)計(jì)報(bào)告</p><p><b>　　題目：銀行家算法</b></p><p>　　院 （系）： 計(jì)算機(jī)科學(xué)與工程</p><p>　　專(zhuān) 業(yè)： 軟件工程 </p><p>　　班 級(jí)： </p><p>　

2、　學(xué) 生： </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p><b>　　2013年 1月</b></p><p><b>　　目 錄</b></p&

3、gt;<p><b>　　摘要3</b></p><p><b>　　一、問(wèn)題描述4</b></p><p><b>　　二、概要設(shè)計(jì)4</b></p><p><b>　　2.1算法思路4</b></p><p>　　2.2銀行家算

4、法步驟4</p><p>　　2.3安全性算法步驟5</p><p>　　2.3各模塊間的調(diào)用關(guān)鍵5</p><p><b>　　三、詳細(xì)設(shè)計(jì)5</b></p><p>　　3．1主要函數(shù)的核心代碼5</p><p>　　3．2程序流程圖6</p><p>　　

5、四、測(cè)試結(jié)果及分析9</p><p>　　4.1用例測(cè)試a9</p><p>　　4.2用例測(cè)試b9</p><p>　　4.3用例測(cè)試c9</p><p>　　4.4用例測(cè)試d9</p><p>　　4.5用例測(cè)試e10</p><p><b>　　五、總結(jié)10<

6、/b></p><p>　　六、附錄——源代碼12</p><p><b>　　銀行家算法</b></p><p>　　(西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西西安，710021）</p><p><b>　　摘 要</b></p><p>　　銀行家算法是避免死鎖的

7、重要算法，本文介紹了銀行家酸價(jià)的包括算法思路、步驟，以及要用到的主要數(shù)據(jù)結(jié)構(gòu)、函數(shù)模塊及其之間的調(diào)用關(guān)系等。在概要設(shè)計(jì)的基礎(chǔ)上，又給出了詳細(xì)的算法設(shè)計(jì)，實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有函數(shù),對(duì)每個(gè)函數(shù)寫(xiě)出核心算法，并畫(huà)出了流程圖。接著對(duì)編碼進(jìn)行了測(cè)試與分析（并在最后附上Java編寫(xiě)的程序代碼）。最后對(duì)整個(gè)設(shè)計(jì)過(guò)程進(jìn)行了總結(jié)。</p><p>　　關(guān)鍵詞：安全狀態(tài) 銀行家算法 安全性算法 安全序列 流程圖。</p&g

8、t;<p>　　Banker 's Algorithm</p><p><b>　　Abstract</b></p><p>　　Bankers to avoid deadlock algorithm is an important algorithm, this paper introduces the bankers algorithm, i

9、ncluding the steps of acid value, and to use the main data structure, function module and between the call relation. In the summary of the design basis, and gives a detailed algorithm design, design outline to achieve th

10、e definition of all functions, each function to write the core algorithms, and draw the flow chart. Then the coding are tested and analyzed ( and attached in the last Java</p><p>　　Key Words: safety securit

11、y sequence bankers algorithm security algorithm flow chart.</p><p><b>　　1、問(wèn)題描述</b></p><p>　　銀行家算法是一種最具有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)的安全狀態(tài)和不安全狀態(tài)。所謂安全狀態(tài)，是指系統(tǒng)能按照某種進(jìn)程順序{P1,P2,…，Pn}（稱(chēng)

12、{P1,P2,…，Pn }序列為安全序列），來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿(mǎn)足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可以順利完成。安全狀態(tài)一定沒(méi)有死鎖發(fā)生。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)。么，什么是安全序列呢？如果對(duì)每一個(gè)進(jìn)程Pi(1<i<n)，它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前可利用的資源量與所有的進(jìn)程Pj(j<n)所占有的資源量之和，則稱(chēng)此進(jìn)程序列{P1,P2,…，Pn}是安全的，稱(chēng)

13、作安全序列。</p><p><b>　　2、概要設(shè)計(jì)</b></p><p><b>　　2．1算法思路：</b></p><p>　　先對(duì)用戶(hù)提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求是否大于需要的，是否大于可利用的。若請(qǐng)求合法，則進(jìn)行預(yù)分配，對(duì)分配后的狀態(tài)調(diào)用安全性算法進(jìn)行檢查。若安全，則分配；若不安全，則拒絕申請(qǐng)，恢復(fù)到

14、原來(lái)的狀態(tài)，拒絕申請(qǐng)。</p><p>　　2．2銀行家算法步驟</p><p>　?。?）如果Requesti＜o(jì)r =Need,則轉(zhuǎn)向步驟(2)；否則，認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。</p><p>　?。?）如果Request＜o(jì)r=Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無(wú)足夠的資源，進(jìn)程必須等待。</p>

15、<p>　?。?）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：</p><p>　　Available=Available-Request[i];</p><p>　　Allocation=Allocation+Request;</p><p>　　Need=Need-Request;</p><p>　　(

16、4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)</p><p>　　2．3安全性算法步驟</p><p><b>　?。?）設(shè)置兩個(gè)向量</b></p><p>　　①工作向量Work。它表示系統(tǒng)可提供進(jìn)程繼續(xù)運(yùn)行所需要的各類(lèi)資源數(shù)目，執(zhí)行安全算法開(kāi)始時(shí)，Work=Allocation;</p><p>

17、;　?、诓紶栂蛄縁inish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開(kāi)始時(shí)先做Finish[i]=false，當(dāng)有足夠資源分配給進(jìn)程時(shí)，令Finish[i]=true。</p><p>　　public void Safty() //利用安全性算法進(jìn)行安全性檢測(cè)</p><p>　　public void changdata(int i) //進(jìn)行資源分配<

18、/p><p>　　void judge() //利用銀行家算法對(duì)申請(qǐng)資源進(jìn)行判定</p><p>　　2．4 各模塊間的調(diào)用關(guān)系</p><p>　　主函數(shù)void main()</p><p>　　要調(diào)用： printFrame()，print()，Safty()，judge()</p><p>　　安全性檢測(cè)函數(shù)

19、Safty()</p><p>　　要調(diào)用：print()</p><p>　　銀行家算法函數(shù)judge()</p><p>　　要調(diào)用print()、Safty()、和judge()本身</p><p><b>　　3、詳細(xì)設(shè)計(jì) </b></p><p>　　3．1主要函數(shù)的核心代碼：</

20、p><p>　?。?）進(jìn)行初始化輸入的函數(shù)</p><p>　?。?）打印輸出的函數(shù)</p><p>　?。?）利用安全性算法進(jìn)行檢測(cè)的函數(shù)</p><p>　?。?）進(jìn)行資源分配的函數(shù)</p><p>　?。?）利用行家算法進(jìn)行判定的函數(shù)</p><p>　　注：具體代碼請(qǐng)見(jiàn)附錄—源程序清單。&l

21、t;/p><p><b>　　3．2程序流程圖：</b></p><p>　　1、系統(tǒng)主要過(guò)程流程圖</p><p>　　2、銀行家算法流程圖</p><p>　　3、安全性算法流程圖</p><p>　　注：程序流程圖是根據(jù)自己程序的整個(gè)流程用photoshop制成，再插入進(jìn)來(lái)。</p>

22、<p><b>　　4、測(cè)試結(jié)果及分析</b></p><p>　　4.1 用例測(cè)試a：初始化</p><p>　　系統(tǒng)是安全的，安全序列為：2-->4-->1-->3-->5--></p><p>　　**************此時(shí)刻資源分配情況**************</p>

23、<p>　　Number Name Max Allocation Need</p><p>　　0 p0 7 5 3 0 1 0 7 4 3</p><p>　　1 p1 3 2 2 2 0 0 1 2 2</p><p>　　2 p2

24、 9 0 2 3 0 2 6 0 0</p><p>　　3 p3 2 2 2 2 1 1 0 1 1</p><p>　　4 p4 4 3 3 0 0 2 4 3 1</p><p>　　4.2 用例測(cè)試b：進(jìn)程1發(fā)出請(qǐng)求Request(2,1,2)

25、——Request>Need，</p><p>　　請(qǐng)輸入您要分配的資源進(jìn)程號(hào)：1</p><p>　　請(qǐng)輸入進(jìn)程1申請(qǐng)的資源：</p><p><b>　　A類(lèi)資源請(qǐng)求：2</b></p><p><b>　　B類(lèi)資源請(qǐng)求：1</b></p><p><b>

26、;　　C類(lèi)資源請(qǐng)求：2</b></p><p>　　進(jìn)程1申請(qǐng)的資源大于它所需要的資源。</p><p>　　請(qǐng)求不合理，不予分配！</p><p>　　4.3 用例測(cè)試c：進(jìn)程0發(fā)出請(qǐng)求Request（5，3，2）——Request>Available，不予分配</p><p>　　請(qǐng)輸入您要分配的資源進(jìn)程號(hào)：0</

27、p><p>　　請(qǐng)輸入進(jìn)程0申請(qǐng)的資源：</p><p><b>　　A類(lèi)資源請(qǐng)求：5</b></p><p><b>　　B類(lèi)資源請(qǐng)求：3</b></p><p><b>　　C類(lèi)資源請(qǐng)求：2</b></p><p>　　進(jìn)程0申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用

28、的資源。</p><p><b>　　不能給與分配！</b></p><p>　　4.4用例測(cè)試d：進(jìn)程1發(fā)出請(qǐng)求Request(1,0,2)——可以分配</p><p>　　請(qǐng)輸入您要分配的資源進(jìn)程號(hào)：1</p><p>　　請(qǐng)輸入進(jìn)程1申請(qǐng)的資源：</p><p><b>　　A類(lèi)資

29、源請(qǐng)求：1</b></p><p><b>　　B類(lèi)資源請(qǐng)求：0</b></p><p><b>　　C類(lèi)資源請(qǐng)求：2</b></p><p>　　系統(tǒng)是安全的，安全序列為：2-->4-->1-->3-->5--></p><p>　　***********

30、***此時(shí)刻資源分配情況**************</p><p>　　Number Name Max Allocation Need</p><p>　　0 p0 7 5 3 0 1 0 7 4 3</p><p>　　1 p1 3 2 2 3 0 2 0

31、 2 0</p><p>　　2 p2 9 0 2 3 0 2 6 0 0</p><p>　　3 p3 2 2 2 2 1 1 0 1 1</p><p>　　4 p4 4 3 3 0 0 2 4 3 1</p><

32、p>　　4.5用例測(cè)試e：進(jìn)程0發(fā)出請(qǐng)求Request(1,0,1)——系統(tǒng)不安全。</p><p>　　請(qǐng)輸入您要分配的資源進(jìn)程號(hào)：0</p><p>　　請(qǐng)輸入進(jìn)程0申請(qǐng)的資源：</p><p><b>　　A類(lèi)資源請(qǐng)求：0</b></p><p><b>　　B類(lèi)資源請(qǐng)求：2</b>&l

33、t;/p><p><b>　　C類(lèi)資源請(qǐng)求：0</b></p><p><b>　　系統(tǒng)不安全！</b></p><p><b>　　系統(tǒng)不安全！</b></p><p><b>　　系統(tǒng)不安全！</b></p><p><b&g

34、t;　　5、總結(jié)</b></p><p>　　在本程序代碼中，總共有五個(gè)方法，一個(gè)是main方法，輸入數(shù)據(jù)是用printFrame()函數(shù)來(lái)實(shí)現(xiàn)，輸出結(jié)果是用print()函數(shù)來(lái)實(shí)現(xiàn)的，銀行家算法用judge( )函數(shù)來(lái)實(shí)現(xiàn)，而安全性算法是用Safty()來(lái)實(shí)現(xiàn)的</p><p>　　首先，輸入欲申請(qǐng)資源的進(jìn)程以及其所申請(qǐng)的資源數(shù)，存放在Request數(shù)組中。然后，判斷進(jìn)程請(qǐng)求

35、的資源數(shù)是否大于其所需的資源數(shù)，若大于則報(bào)錯(cuò)并返回，若不大于則繼續(xù)判斷它是否大于系統(tǒng)在此時(shí)刻可利用的資源數(shù)，同樣，如果大于則報(bào)錯(cuò)并反回，如果不大于則調(diào)用changedata( )函數(shù)來(lái)進(jìn)行預(yù)分配，之后再調(diào)用安全型算法safty檢查。</p><p>　　最后，無(wú)論此次分配是否成功，我們都可以選擇繼續(xù)分配或者退出系統(tǒng)。</p><p>　　總之，銀行家算法是避免死鎖的主要方法，其思路在很多方

36、面都非常值得我們來(lái)學(xué)習(xí)借鑒。</p><p><b>　　6、附錄——源代碼</b></p><p>　　import java.util.Scanner;</p><p>　　public class Test </p><p><b>　　{</b></p><p>　　

37、int no1, no2;</p><p>　　static int Max[][]; //最大需求</p><p>　　static int Allocation[][]; //已分配資源數(shù)</p><p>　　static int Need[][]; //仍需資源數(shù)</p><p>　　stat

38、ic int Available[]; //可利用資源數(shù)</p><p>　　static String name1[]; </p><p>　　static String name2[]; </p><p>　　static boolean[] Finish; </p><p>　　static int[] t

39、emp = { 0 }; //存放安全序列</p><p>　　static int work[];</p><p>　　static int[] Request;</p><p>　　Scanner input = new Scanner(System.in);</p><p>　　public static void main(St

40、ring[] args) { //主方法</p><p>　　Test t = new Test();</p><p>　　t.printFrame();</p><p>　　t.Safty();</p><p>　　t.judge();</p><p><b>　　}</b></p

41、><p>　　public void printFrame() { //輸入初始化數(shù)據(jù)</p><p>　　System.out.print("請(qǐng)輸入系統(tǒng)中進(jìn)程的個(gè)數(shù):");</p><p>　　no1 = input.nextInt();</p><p>　　System.out.print("請(qǐng)輸入資源的種類(lèi)

42、數(shù)：");</p><p>　　no2 = input.nextInt();</p><p>　　Max = new int[no1][no2];</p><p>　　Allocation = new int[no1][no2];</p><p>　　Need = new int[no1][no2];</p><

43、p>　　Available = new int[no2];</p><p>　　name1 = new String[no1];</p><p>　　name2 = new String[no2];</p><p>　　int sum[] = new int[3];</p><p>　　for (int i = 0; i < no

44、1; i++) {</p><p>　　System.out.print("請(qǐng)輸入進(jìn)程" + i + "的名字:");</p><p>　　name1[i] = input.next();</p><p><b>　　}</b></p><p>　　for (int i = 0;

45、 i < no2; i++) </p><p><b>　　{</b></p><p>　　System.out.print("請(qǐng)輸入資源" + i + "的名字:");</p><p>　　name2[i] = input.next();</p><p><b>

46、;　　}</b></p><p>　　for (int i = 0; i < no1; i++) </p><p><b>　　{</b></p><p>　　for (int j = 0; j < no2; j++)</p><p><b>　　{</b></p>

47、;<p>　　System.out.print("請(qǐng)輸入進(jìn)程" + name1[i] + "的" + name2[j]</p><p>　　+ "類(lèi)資源最大需求量:");</p><p>　　Max[i][j] = input.nextInt();</p><p><b>　　}&l

48、t;/b></p><p><b>　　}</b></p><p>　　for (int i = 0; i < no1; i++){</p><p>　　for (int j = 0; j < no2; j++) {</p><p>　　System.out.print("請(qǐng)輸入進(jìn)程"

49、; + name1[i] + "的" + name2[j]</p><p>　　+ "類(lèi)資源已占有資源量:");</p><p>　　Allocation[i][j] = input.nextInt();</p><p>　　Need[i][j] = Max[i][j] - Allocation[i][j];</p>

50、;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　for (int i = 0; i < no2; i++){</p><p>　　System.out.print("請(qǐng)輸入類(lèi)資源" + name2[i] + "的可利用資源數(shù)：&

51、quot;);</p><p>　　Available[i] = input.nextInt();</p><p><b>　　}</b></p><p>　　for (int i = 0; i < no2; i++){</p><p>　　Available[i] = Available[i] - sum[i];

52、}</p><p><b>　　}</b></p><p>　　public void print() //打印輸出</p><p><b>　　{</b></p><p>　　System.out.println("**************此時(shí)刻資源分配情況**********

53、****");</p><p>　　System.out.println(" Number Name Max Allocation Need");</p><p>　　for (int i = 0; i < no1; i++)</p><p><b>　　{</b></p&

54、gt;<p>　　System.out.print( " "+ i +" ");</p><p>　　System.out.print(name1[i]+" ");</p><p>　　for (int j = 0; j < no2; j++) {</p><p>

55、　　System.out.print(Max[i][j]+" ");}</p><p>　　for (int j = 0; j < no2; j++) {</p><p>　　System.out.print(" "+ Allocation[i][j]);}</p><p>　　for (int j = 0; j

56、< no2; j++) {</p><p>　　System.out.print(" " + Need[i][j]);}</p><p>　　System.out.println();</p><p><b>　　}</b></p><p>　　System.out.print("各

57、個(gè)類(lèi)資源可利用的資源數(shù)分別為:");</p><p>　　for (int j = 0; j < no2; j++) {</p><p>　　System.out.print(" " + Available[j]);}</p><p>　　System.out.println();</p><p><

58、b>　　}</b></p><p>　　public void Safty() { //進(jìn)行安全性檢測(cè)</p><p>　　Finish = new boolean[no1];</p><p>　　temp = new int[no1];</p><p>　　int i, k = 0, m, apply

59、,j;//k為安全序列的序列數(shù)</p><p>　　int flag = 0;</p><p>　　work = new int[no2];</p><p>　　for (i = 0; i < no2; i++) </p><p>　　{work[i] = Available[i];}</p><p>　　for

60、 (i = 0; i < no1; i++) //當(dāng)前執(zhí)行換后，重第一個(gè)開(kāi)始檢測(cè)</p><p><b>　　{</b></p><p>　　apply = 0;</p><p>　　for (j = 0; j < no2; j++) </p><p><b>　　{</b><

61、/p><p>　　if (Finish[i] == false && Need[i][j] <= work[j]) </p><p><b>　　{</b></p><p><b>　　apply++;</b></p><p>　　if (apply == no2)</p

62、><p><b>　　{</b></p><p>　　for (m = 0; m < no2; m++)</p><p>　　work[m] = work[m] + Allocation[i][m];// 變分配數(shù)</p><p>　　Finish[i] = true;</p><p>　　te

63、mp[k] = i+1; //保存安全序列</p><p>　　i = -1; //</p><p><b>　　k++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

64、;　　} </b></p><p><b>　　}</b></p><p>　　for (i = 0; i < no2; i++)</p><p><b>　　{</b></p><p>　　if (Finish[i] == false) {System.out.println

65、("系統(tǒng)不安全！");}</p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　System.out.print("系統(tǒng)是安全的，安全序列為：");</p><p>　　for (i = 0; i <

66、 no1; i++) // 輸出運(yùn)行進(jìn)程數(shù)組</p><p>　　{ System.out.print(temp[i] + "-->"); }</p><p>　　System.out.println();</p><p><b>　　print();</b></p><p><

67、b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public void changdata(int i) { //進(jìn)行資源分配</p><p><b>　　int j;</b>&l

68、t;/p><p>　　for (j = 0; j < no2; j++) </p><p><b>　　{</b></p><p>　　Available[j] = Available[j] - Request[j];</p><p>　　Allocation[i][j] = Allocation[i][j] + Re

69、quest[j];</p><p>　　Need[i][j] = Need[i][j] - Request[j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void judge(){ //利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定

70、</p><p>　　Request = new int[no2];</p><p>　　char ch='y';</p><p>　　int i = 0, j = 0;</p><p>　　System.out.print("請(qǐng)輸入您要分配的資源進(jìn)程號(hào)：");</p><p>　　

71、for(j=0;j<10;j++)</p><p><b>　　{</b></p><p>　　i = input.nextInt();</p><p>　　if(i>no1) </p><p>　　{System.out.println("輸入錯(cuò)誤，請(qǐng)重新輸入:");continue;}

72、</p><p>　　else break; </p><p><b>　　}</b></p><p>　　System.out.println("請(qǐng)輸入進(jìn)程" + i + "申請(qǐng)的資源：");</p><p>　　for (j = 0; j < no2; j++)<

73、;/p><p><b>　　{</b></p><p>　　System.out.print(name2[j] + "類(lèi)資源請(qǐng)求：");</p><p>　　Request[j] = input.nextInt(); // 輸入需要申請(qǐng)的資源</p><p><b>　　}</b&g

74、t;</p><p>　　for (j = 0; j < no2; j++)</p><p><b>　　{</b></p><p>　　if (Request[j] > Need[i][j]) // 判斷申請(qǐng)是否大于需求</p><p><b>　　{</b></p>

75、;<p>　　System.out.println("進(jìn)程" + i + "申請(qǐng)的資源大于它所需要的資源");</p><p>　　System.out.println("分配不合理，不予分配！");</p><p><b>　　ch = 'n';</b></p>

76、<p><b>　　break;</b></p><p><b>　　} </b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if (Request[j] > Availabl

77、e[j]) // 判斷申請(qǐng)是否大于當(dāng)前資源{</p><p>　　System.out.println("進(jìn)程" + i + "申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源。");</p><p>　　System.out.println("不能給予分配！"); </p><p><b>

78、　　ch = 'n';</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&l

79、t;p>　　if (ch == 'y') </p><p><b>　　{</b></p><p>　　changdata(i); // 根據(jù)進(jìn)程需求量變換資源</p><p>　　Safty(); // 根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷</p><p><b>　　}<

80、;/b></p><p>　　System.out.println("請(qǐng)輸入您所要進(jìn)行的操作：1：繼續(xù)分配 2：退出");</p><p>　　for(i=0;i<5;i++)</p><p><b>　　{</b></p><p>　　int choice = input.nextInt

81、();</p><p>　　if (choice == 1) judge();</p><p>　　else if (choice == 2) System.exit(0);</p><p>　　else System.out.println("輸入錯(cuò)誤，請(qǐng)重新輸入：");</p><p><b>　　}&