系統(tǒng)避免死鎖的銀行家算法課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大小：152.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　操作系統(tǒng)課程設計　　題目：銀行家算法 　　1、概述　　一、設計目的　　1、了解多道程序系統(tǒng)中，

2、多個進程并發(fā)執(zhí)行的資源分配。 　　2、掌握死鎖的產生的原因、產生死鎖的必要條件和處理死鎖的基本方法。 　　3、掌握預防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。 　　4、掌握銀行家算法，了解資源在進程并發(fā)執(zhí)行中的資源分配策略。 　　5、理解死鎖避免在當前計算機系統(tǒng)不常使用的原因

3、　　二、開發(fā)環(huán)境　　2、需求分析　　避免多道程序系統(tǒng)中程序的死鎖。　　一、死鎖概念：　　在多道程序系統(tǒng)中，雖可借助于

4、多個進程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個進程在運行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進。一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。

5、;　　二、關于死鎖的一些結論： 　　Ø 參與死鎖的進程最少是兩個（兩個以上進程才會出現(xiàn)死鎖） 　　Ø 參與死鎖的進程至少有兩個已經占有資源

6、16; 參與死鎖的所有進程都在等待資源 　　Ø 參與死鎖的進程是當前系統(tǒng)中所有進程的子集 　　注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(tǒng)崩潰。 <

7、b>　　三、資源分類： 　　永久性資源： 　　可以被多個進程多次使用（可再用資源） 　　l 可搶占資源 　　l&

8、#160; 不可搶占資源 　　臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源） 　　“申請--分配--使用--釋放”模式 　　四、產生死鎖的四個必要條件：

9、1、互斥使用（資源獨占） 　　一個資源每次只能給一個進程使用 　　2、不可強占（不可剝奪） 　　資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放 　　3、請求和保持（部分分配，占有申請） 　　一個進程在申請新

10、的資源的同時保持對原有資源的占有（只有這樣才是動態(tài)申請，動態(tài)分配） 　　4、循環(huán)等待 　　存在一個進程等待隊列 　　{P1 , P2 , … , Pn}, 　　其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的

11、資源，形成一個進程等待環(huán)路 　　5、死鎖的解決方案 　　5.1 產生死鎖的例子 　　申請不同類型資源產生死鎖 　　P1： 　　…

12、　　申請打印機 　　申請掃描儀 　　使用 　　釋放打印機 　　釋放掃描儀 <

13、/b>　　… 　　P2： 　　… 　　申請掃描儀

14、申請打印機 　　使用 　　釋放打印機 　　釋放掃描儀 　　… <p&g

15、t;　　申請同類資源產生死鎖（如內存） 　　設有資源R，R有m個分配單位，由n個進程P1,P2,…,Pn（n > m）共享。假設每個進程對R的申請和釋放符合下列原則： 　　* 一次只能申請一個單位 　　* 滿足總申請后才能使用 　　* 使用完后一次性釋放 </

16、p>　　m=2，n=3 　　資源分配不當導致死鎖產生　　5.2死鎖預防: 　　定義:在系統(tǒng)設計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產生死鎖的四個必要條件之一 <p&

17、gt;　　①破壞“不可剝奪”條件 　　在允許進程動態(tài)申請資源前提下規(guī)定，一個進程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請 　?、谄茐摹罢埱蠛捅３帧睏l件 　　要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當該進程所要資源均可滿足時才給予一次性分配 &l

18、t;/p>　?、燮茐摹把h(huán)等待”條件 　　采用資源有序分配法： 　　把系統(tǒng)中所有資源編號，進程在申請資源時必須嚴格按資源編號的遞增次序進行，否則操作系統(tǒng)不予分配。　　6．安全狀態(tài)與不安全狀態(tài) 　　安全狀態(tài)：

19、;　　如果存在一個由系統(tǒng)中所有進程構成的安全序列P1，…Pn，則系統(tǒng)處于安全狀態(tài)。一個進程序列{P1，…，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj (j 　　不安全狀態(tài):不存在一個安全序列，不安全

20、狀態(tài)一定導致死鎖。　　3、數(shù)據(jù)結構設計　　一、可利用資源向量矩陣AVAILABLE。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果AVAILABLE [j]= K，則表示系統(tǒng)中現(xiàn)有R類資源K個<

21、/p>　　二、最大需求矩陣MAX。這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果MAX [i,j]=K，則表示進程i需要R類資源的數(shù)目為K。　　三、分配矩陣ALLOCATION。這也是一個n*m的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果ALLOCATION [i,j]=K，則表示進程i當前已分得R類資源的數(shù)目為K。</

22、p>　　四、需求矩陣NEED。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果NEED [i,j]=K，則表示進程i還需要R類資源K個，才能完成其任務。　　上述矩陣存在下述關系：　　NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j]<b&g

23、t;　　4、算法的實現(xiàn)　　一、初始化　　由用戶輸入數(shù)據(jù)，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。　　二、銀行家算法&l

24、t;p>　　在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。　　銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。　　設進程cusneed提出請求REQUEST [i]，

25、則銀行家算法按如下規(guī)則進行判斷。　　(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(2)；否則，出錯。　　(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。　　(3)系統(tǒng)試探分

26、配資源，修改相關數(shù)據(jù)：　　AVAILABLE[i]-=REQUEST[cusneed][i];　　ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];　　NEED[cusneed][i]-=REQUEST[cusneed][i];　　(

27、4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復原狀，進程等待。　　三、安全性檢查算法　　(1)設置兩個工作向量Work=AVAILABLE;FINISH　　(2)從進程集合中找到一個滿足下述條件的進程，

28、FINISH==false;　　NEED<=Work;　　如找到，執(zhí)行(3)；否則，執(zhí)行(4)　　(3)設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。　　Work+=ALLOCATION;　　Finish=true;&

29、lt;/p>　　GOTO 2　　(4)如所有的進程Finish= true，則表示安全；否則系統(tǒng)不安全。　　四、各算法流程圖 　　初始化算法流程圖：

30、　　銀行家算法流程圖：　　安全性算法流程圖：　　四、源程序清單　　Option Explicit　　Dim i, j, x As Integ

31、er　　Dim flag As Integer　　Dim Max(5, 3) As Integer　　Dim Allocation(5, 3) As Integer　　Dim Need(5, 3) As Integer　　Dim

32、Available(3) As Integer　　Dim buttonpress As Integer　　Sub cmdclick()　　Dim rqz(3) As Integer　　Dim bb(3) As Boolean　　D

33、im cc(3) As Boolean　　Dim ok1, ok2 As Boolean　　Call duchu　　For i = 0 To 2　　rqz(i) = Val(InputBox("請輸入P" & buttonpress &

34、 "的請求資源:"))　　Next　　For i = 0 To 2　　If rqz(i) <= Need(buttonpress, i) Then　　bb(i) = True<p

35、>　　Else　　bb(i) = False　　End If　　If bb(0) And bb(1) And bb(2) = True Then　　ok1 = True

36、　　GoTo step1　　GoTo quit　　Else　　ok1 = False　　End If<p&g

37、t;　　Next　　If ok1 = False Then　　MsgBox ("請求資源數(shù)超過需求最大值！"), , "提示信息"　　GoTo quit&l

38、t;b>　　End If　　step1:　　For i = 0 To 2　　If rqz(i) <= Available(i) Then　　cc(i) = True<p&g

39、t;　　Else　　cc(i) = False　　End If　　If cc(0) And cc(1) And cc(2) = True Then　　ok2 = True&

40、lt;p>　　GoTo step2　　GoTo quit　　Else　　ok2 = False　　End If

41、　　Next　　If ok2 = False Then　　MsgBox ("尚無足夠資源，P0須等待！"), , "提示信息"　　GoTo quit<

42、b>　　End If　　step2:　　For i = 0 To 2　　Available(i) = Available(i) - rqz(i)　　Allocation(buttonpress, i) = A

43、llocation(buttonpress, i) + rqz(i)　　Need(buttonpress, i) = Need(buttonpress, i) - rqz(i)　　Next　　Call xieru　　Call Comm

44、and6_Click　　If flag = 0 Then　　For i = 0 To 2　　Available(i) = Available(i) + rqz(i)　　Allocation(buttonpress, i) = Allocation(buttonpress,

45、 i) - rqz(i)　　Need(buttonpress, i) = Need(buttonpress, i) + rqz(i)　　Next　　Call xieru　　GoTo quit<

46、;/p>　　Else　　MsgBox ("資源表分配更改成功！"), , "提示信息"　　GoTo quit　　End If<

47、/p>　　quit:　　Form1.Show　　End Sub　　Private Sub Command1_Click()　　buttonpress = 0</p

48、>　　Call cmdclick　　End Sub　　Private Sub Command2_Click()　　buttonpress = 1　　Call cmdclick<

49、p>　　End Sub　　Private Sub Command3_Click()　　buttonpress = 2　　Call cmdclick　　End Sub&

50、lt;p>　　Private Sub Command4_Click()　　buttonpress = 3　　Call cmdclick　　End Sub　　Private Sub Command5_Click()</p&g

51、t;　　buttonpress = 4　　Call cmdclick　　End Sub　　Private Sub Command6_Click()　　Dim a, b, c, d As Variant</p

52、>　　Dim Max(5, 3) As Integer　　Dim m, n, e As Integer　　Dim work(3) As Integer　　Dim aa(5) As Integer　　Dim Finish(5) As Boolea

53、n　　Dim pd(5, 3) As Boolean　　Dim canbefound As Boolean　　e = -1　　For i = 0 To 2　　Available(i) = Te

54、xt16(i).Text　　work(i) = Available(i)　　Next　　For i = 0 To 4　　For j = 0 To 2　　Max(0, j) = Text1(j)

55、.Text　　Max(1, j) = Text2(j).Text　　Max(2, j) = Text3(j).Text　　Max(3, j) = Text4(j).Text　　Max(4, j) = Text5(j).Text

56、Allocation(0, j) = Text6(j).Text　　Allocation(1, j) = Text7(j).Text　　Allocation(2, j) = Text8(j).Text　　Allocation(3, j) = Text9(j).Text

57、Allocation(4, j) = Text10(j).Text　　Need(0, j) = Text11(j).Text　　Need(1, j) = Text12(j).Text　　Need(2, j) = Text13(j).Text　　Need(3, j) = T

58、ext14(j).Text　　Need(4, j) = Text15(j).Text　　Next　　Next　　'判斷是否處于安全狀態(tài)<b&

59、gt;　　step1:　　m = m + 1　　For i = 0 To 4　　For j = 0 To 2　　If Need(i, j) <= work(j) And Finish(i) = False T

60、hen　　pd(i, j) = True　　Else　　pd(i, j) = False　　End If　　If pd(i, 0) And pd(i, 1

61、) And pd(i, 2) = True Then　　canbefound = True　　n = i　　e = e + 1　　aa(e) = n</

62、p>　　GoTo step2　　End If　　Next　　Next　　If canbefound = False Then<

63、;/p>　　MsgBox ("系統(tǒng)處于不安全狀態(tài)！"), , "提示信息"　　flag = 0　　GoTo quit　　Else&l

64、t;/p>　　GoTo step3　　End If　　step2:　　For i = 0 To 2　　work(i) = work(i) + Allocation(n,

65、 i)　　Finish(n) = True　　Next　　If m <= 4 Then　　GoTo step1　　Else&

66、lt;p>　　GoTo step3　　End If　　step3:　　MsgBox ("系統(tǒng)安全,安全序列為:" & "P" & aa(0) & " &quo

67、t; & "P" & aa(1) & " " & "P" & aa(2) & " " & "P" & aa(3) & " " & "P" & aa(4)), , "提示信息"

68、;　　flag = 1　　GoTo quit　　quit:　　Form1.Show　　End Sub

69、;　　Private Sub duchu()　　For i = 0 To 2　　Available(i) = Text16(i).Text　　Next　　For i = 0 To 4</

70、p>　　For j = 0 To 2　　Allocation(0, j) = Text6(j).Text　　Allocation(1, j) = Text7(j).Text　　Allocation(2, j) = Text8(j).Text

71、Allocation(3, j) = Text9(j).Text　　Allocation(4, j) = Text10(j).Text　　Need(0, j) = Text11(j).Text　　Need(1, j) = Text12(j).Text　　Need(2, j

72、) = Text13(j).Text　　Need(3, j) = Text14(j).Text　　Need(4, j) = Text15(j).Text　　Next　　Next

73、　　End Sub　　Private Sub xieru()　　For i = 0 To 2　　Text16(i).Text = Available(i)　　Next<

74、/p>　　For i = 0 To 4　　For j = 0 To 2　　Text6(j).Text = Allocation(0, j)　　Text7(j).Text = Allocation(1, j)　　Text8(j).Text = A

75、llocation(2, j)　　Text9(j).Text = Allocation(3, j)　　Text10(j).Text = Allocation(4, j)　　Text11(j).Text = Need(0, j)　　Text12(j).Text = Need

76、(1, j)　　Text13(j).Text = Need(2, j)　　Text14(j).Text = Need(3, j)　　Text15(j).Text = Need(4, j)　　Next<p&

77、gt;　　Print　　x = x + 2　　Next　　End Sub　　Private Sub Command7_C

78、lick()　　End　　End Sub　　'初始化資源分配表　　Private Sub Form_Load()<p&g

79、t;　　Dim a, b, c, d As Variant　　a = Array(7, 5, 3, 3, 2, 2, 9, 0, 2, 2, 2, 2, 4, 3, 3)　　b = Array(0, 1, 0, 2, 0, 0, 3, 0, 2, 2, 1, 1, 0, 0, 2)　　c = Array(7, 4

80、, 3, 1, 2, 2, 6, 0, 0, 0, 1, 1, 4, 3, 1)　　d = Array(3, 3, 2)　　x = 0　　For i = 0 To 2　　Available(i) = d(i)&

81、lt;p>　　Text16(i).Text = Available(i)　　Next　　For i = 0 To 4　　For j = 0 To 2　　Max(i, j) = a(i + j + x)&l

82、t;p>　　Text1(j).Text = Max(0, j)　　Text2(j).Text = Max(1, j)　　Text3(j).Text = Max(2, j)　　Text4(j).Text = Max(3, j)　　Text5(j).Text = Max

83、(4, j)　　Allocation(i, j) = b(i + j + x)　　Text6(j).Text = Allocation(0, j)　　Text7(j).Text = Allocation(1, j)　　Text8(j).Text = Allocation(

84、2, j)　　Text9(j).Text = Allocation(3, j)　　Text10(j).Text = Allocation(4, j)　　Need(i, j) = c(i + j + x)　　Text11(j).Text = Need(0, j)</p

85、>　　Text12(j).Text = Need(1, j)　　Text13(j).Text = Need(2, j)　　Text14(j).Text = Need(3, j)　　Text15(j).Text = Need(4, j)<b

86、>　　Next　　Print　　x = x + 2　　Next　　End Sub</p&

87、gt;　　5、結束語　　心得與體會：操作系統(tǒng)是計算機系統(tǒng)中必不可少的系統(tǒng)軟件。它是計算機系統(tǒng)中各種資源的管理者和各種活動的組織者、指揮者。銀行家算法是為了使系統(tǒng)保持安全狀態(tài)。我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配

88、資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。

89、　銀行家算法能保證系統(tǒng)時時刻刻都處于安全狀態(tài)，但它要不斷檢測每個進程對各類資源的占用和申請情況，需花費較多的時間。　　經過這次設計，讓我基明白了銀行家算法的基本原理，加深了對課堂上知識的理解，也懂得了如何讓銀行家算法實現(xiàn)。　　實例：　　（1）下列狀態(tài)是否安全？(三個進程共享1

90、2個同類資源)　　進程已分配資源數(shù)最大需求數(shù)　　114 (狀態(tài)a)　　244　　358　　114 (狀

91、態(tài)b)　　246　　368　　狀態(tài)a安全，序列為：2-->1--> 3　　狀態(tài)b不安全，只剩1個可用資源，收不回已分配資源。　　（2）

92、考慮下列系統(tǒng)狀態(tài)　　分配矩陣最大需求矩陣可用資源矩陣　　0 0 1 2 0 0 1 21 5 2 0　　1 0 0 01 7 5 0　　1 3 5 42 3 5 6　　0

93、6 3 20 6 5 2　　0 0 1 40 6 5 6　　問系統(tǒng)是否安全？若安全就給出所有的安全序列。若進程2請求(0420)，可否立即分配？　　答：安全。安全序列為：1-->3-->2-->5-->4。　　若進程2請求

94、(0420)，可立即分配。分配后可用資源為1 1 0 0，回收1進程資源，　　可用資源數(shù)為：1 1 1 2，然后執(zhí)行3-->2-->5-->4序列。　　6、參考文獻　　1、湯子嬴編：《計算機操作系統(tǒng)》，西安電子科技大學出版社<

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

系統(tǒng)避免死鎖的銀行家算法課程設計

文檔簡介

溫馨提示

最新文檔

評論

系統(tǒng)避免死鎖的銀行家算法課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載