實驗二 銀行家算法
一、實驗目的
1、了解什麼是作業系統安全狀态和不安全狀态；
2、了解如何避免系統死鎖；
3、了解銀行家算法是一種最有代表性的避免死鎖的算法，掌握其實作原理及實作過程。
二、實驗内容
根據銀行家算法的基本思想，編寫和調試一個實作動态資源配置設定的模拟程式，并能夠有效避免死鎖的發生。
三、實驗原理
程序申請資源時，系統通過一定的算法判斷本次申請是否不可能産生死鎖（處于安全狀态）。若可能産生死鎖（處于不安全狀态），則暫不進行本次資源配置設定，以避免死鎖。算法有著名的銀行家算法。
1、什麼是系統的安全狀态和不安全狀态？
所謂安全狀态，是指如果系統中存在某種程序式列＜P1，P2，…，Pn＞，系統按該序列為每個程序配置設定其所需要的資源，直至最大需求，則最終能使每個程序都可順利完成，稱該程序式列＜P1，P2，…，Pn，＞為安全序列。
如果不存在這樣的安全序列，則稱系統處于不安全狀态。
2、銀行家算法
把作業系統看作是銀行家，作業系統管理的資源相當于銀行家管理的資金，程序向作業系統請求配置設定資源相當于使用者向銀行家貸款。
為保證資金的安全，銀行家規定:
(1) 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客;
(2) 顧客可以分期貸款，但貸款的總數不能超過最大需求量;
(3) 當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間裡得到貸款;
(4) 當顧客得到所需的全部資金後,一定能在有限的時間裡歸還所有的資金。
作業系統按照銀行家制定的規則設計的銀行家算法為：
（1）程序首次申請資源的配置設定：如果系統現存資源可以滿足該程序的最大需求量，則按目前的申請量配置設定資源，否則推遲配置設定。
（2）程序在執行中繼續申請資源的配置設定：若該程序已占用的資源與本次申請的資源之和不超過對資源的最大需求量，且現存資源能滿足該程序尚需的最大資源量，則按目前申請量配置設定資源，否則推遲配置設定。
（3）至少一個程序能完成：在任何時刻保證至少有一個程序能得到所需的全部資源而執行到結束。
銀行家算法通過動态地檢測系統中資源配置設定情況和程序對資源的需求情況來決定如何配置設定資源，并能在確定系統處于安全狀态時才把資源配置設定給申請者，進而避免系統發生死鎖。
四、實驗中用到的系統調用函數（包括實驗原理中介紹的和自己采用的），自己采用的系統調用函數要按照指導書中的格式說明進行介紹。
模拟程式沒有用到系統調用函數
五、實驗步驟
要求寫出實驗過程和思路。
流程圖：
銀行家算法資料結構：
1、系統可利用資源向量Available[m]
這是一個含有m個元素的數組，其中每一個元素代表一類系統可利用資源數目，其初始值随機生成，其數值随該類資源的配置設定和回收而動态的改變。Available[i]=N表示系統中現有第i類資源N個。
2、最大需求矩陣Max
這是一個含有n*m大小的矩陣，其定義了每個程序對系統某類資源的最大需求量。Max[i][j]=N表示程序i對第j類資源的需求為N個。
3、程序已擁有資源矩陣Allocation
這是一個含有n*m大小的矩陣，其定義了每個程序對系統某類資源的已擁有個數。Allocation[i][j]=N表示程序i對第j類資源的已擁有數為N。
4、程序需求矩陣Need
這是一個含有n*m大小的矩陣，其定義了每個程序對系統某類資源的需求數量，Need[i][j]=N表示程序i對第j類資源的需求為N。
其中，Need、Allocation、Max矩陣的關系為：Need[i][j]=Max[i][j]-Allcation[i][j]
以上數組全部由C++對記憶體空間申請動态數組實作。
5、程序請求向量request
這是一個含有m個元素的數組，其中每一個元素代表此時某程序對每一類系統可利用資源的申請數量，數值大小不超過系統可利用的資源數。request[i]=N表示某程序對第i類資源的申請數為N。
6、Temp
這是一個含有m個元素的數組，其初始值為Available，将對Available的操作代替在Temp上進行。
7、程序滿足需求的标志數組Finish
在安全性檢測中對每個程序進行檢測配置設定時，可滿足的程序即标志位置1。
Finish[i]=1表示此次嘗試配置設定資源後系統可利用資源能滿足第i個程序的需求。
銀行家算法思路：
申請資源RequestRes()：
1、産生申請向量
2、與系統可利用資源對比(request[i]<=Available[i])判斷能否滿足，能則轉步驟3，否則直接傳回。
3、足夠資源配置設定，嘗試配置設定資源
4、執行安全性檢測算法
5、如安全性檢測不通過，回收配置設定出去的資源
安全性檢測算法思路：
1、初始化Temp與Finish，使Temp[i]=Available[i]，Finish[i]=0
2、當Finish[i]=0&&Need<=Temp時轉步驟3，否則轉步驟4
3、程序獲得所需資源，視為執行完畢，釋放所有資源，使Temp=Temp+Available
Finish[i]=1。
4、計數Finish數組是否全為1，是則系統安全，可以配置設定，否則不安全。
六、實驗結果分析（截屏的實驗結果，與實驗結果對應的實驗分析）
在程式設計方面，我已經事先對初始化的資料進行安全性檢驗，確定初始化的資料不會産生死鎖，是能夠通過安全性檢驗的具有安全序列的資料。
将系統此時可利用資源配置設定給P1，滿足全部需求，預設執行完畢回收P1的資源。此時系統可利用資源為6 4 13 14 6 8 2。滿足P0全部需求。故安全性檢測通過。可以配置設定資源。本次随機産生的系統擁有資源較多，但第二類資源從P1中收回後為4個剛好滿足P0總需求，要是少一個則會發生死鎖。
将此時系統可利用資源配置設定給P0，滿足其全部需求後回收P0擁有的資源，此時系統可利用資源為9 5 12 10 9 8 7 9 12。滿足P1的全部需求，将所需資源全配置設定給P1後回收P1的資源，此時系統可利用資源為10 6 14 12 10 11 8 12 16滿足P2全部需求，故安全性檢測通過，可以配置設定。
檢測系統可利用資源不足以配置設定申請資源，直接傳回。
初始時系統剩餘可利用資源為2 6 3 4 7，滿足安全性，安全序列為1→2→3→0(不唯一)，當嘗試配置設定後剩餘1 5 1 2 6，無法滿足任一程序需求，安全性檢測不通過。如配置設定則造成系統死鎖，故配置設定失敗。
系統嘗試配置設定後剩餘可利用資源8 0 2 1 8 0 4 2
此時執行安全檢測，對于程序0，滿足需求，全部配置設定後收回資源。
此時系統可利用資源為9 1 3 3 13 1 8 6
按順序到程序1，對比Need，發現第三類資源不足，跳過
按順序到程序2，對比Need，發現第二類資源不足，跳過
按順序到程序3，對比Need，滿足需求，全部配置設定後收回資源。
此時系統可利用資源為11 2 4 7 14 3 9 9
按順序到程序4，對比Need，發現第二類資源不足，跳過
按順序到程序5，對比Need，發現第二類資源不足，跳過
再次循環，對程序1，對比Need，發現第六類資源不足，跳過
循環完畢，發現滿足程序不足全部，撤銷配置設定的資源，傳回不安全。
初始系統可利用資源的産生為[1,9]之間，最大需求資源的産生範圍為[0.9]，已配置設定資源産生範圍為[0,5]，申請資源産生範圍為[0,還需求數]。通過研究發現，改變系統可利用資源的産生範圍為[1,5]之間，實驗結果有80％為系統無足夠資源配置設定，直接結束程式。這是因為要能配置設定必須保證系統每一類可利用資源都滿足申請資源數，但系統可利用資源較少，随機産生的申請資源數較高，且一旦系統資源種類有很多時要保證每一類都滿足是比較困難的。可以通過調高系統可利用資源的産生範圍或者調低随機産生的系統資源種類數來提高申請通過率。
關于算法效率方面，在安全性檢測中用到了嵌套三層for循環來對每個程序進行嘗試配置設定檢測，時間複雜度為O(n3)，由于銀行家算法的原理，每次嘗試配置設定資源之後必須對目前所有程序進行安全性檢測，找到一個安全序列之後才能成功配置設定，是以對每個程序的檢測是必不可少的，目前還沒有想到比較明顯的能夠實作該目的且效率較高的算法。
七、思考題
1、 如何設計程式的輸入子產品才能滿足實驗要求，請舉例說明；
由實驗要求可知，測試資料全部不可手工輸入。現在設定所有資料全部随機生成。初始資料中，在[1,10]随機生成資源類數和程序數，對Available數組、Max數組随機生成資料并指派，對Allocation數組的資料随機生成中，要求生成的資料不可大于Max數組中對應資料，大于則重新生成。Need數組中資料要求為Max數組的值-已配置設定Allocation數組中對應的值。嵌套循環裡進行相減指派即可。設計申請資源向量request時，随機産生的需求數一定要小于或等于需求數，在這裡我寫的産生範圍為[0,還需求數]。
2、 銀行家算法在實作過程中必須注意哪些資源配置設定細節才能避免死鎖？
（1）對比請求資源向量和系統目前可利用資源向量，如果某一類資源不滿足請求則直接傳回配置設定資源失敗。
（2）系統可利用資源滿足需求時，試探性配置設定更新資料中，應使系統可利用資源Available=Available-request，已擁有資源Allocation=Allocation+request，需求向量Need=Need-request。
（3）初始化系統資源時應進行安全性檢測，如果初始化時産生的資料都無法使程序擁有安全序列，後面的銀行家算法執行将沒有任何意義。
八、實驗資料及源代碼（學生必須送出自己設計的程式源代碼，并有注釋，源代碼電子版也一并送出），包括思考題的程式。
程式完整代碼請轉至個人GitHub倉庫（如果喜歡，麻煩點個star✨謝謝~）
結語：随筆僅供參考，千萬不要照抄哦~我相信你可以的~！