銀行家演算法是學習計算機作業系統中最重要的演算法之一，銀行家演算法又稱資源分配拒絕法，是用來避免死鎖的，
以下用例題來解釋銀行家演算法
題目假設：
有四家公司：行程P0、行程P1、行程P2、行程P3
一間銀行：名叫系統的銀行，銀行有三個金庫A、B、C
題目情景：四家公司因為企業發展需要，都需要向銀行進行貸款，每個公司需要貸款金額不同，銀行貸款給各個公司所使用的金庫也不同，
此時此刻，各公司所需要的引數如公司總貸款(Claim)、公司已貸金額(Allocation)的表格所示：
| 公司 | 公司總貸款(Claim) | 公司已貸金額(Allocation) |
|---|---|---|
| A B C | A B C | |
| P0 | 3 2 2 | 1 0 0 |
| P1 | 6 1 3 | 5 1 1 |
| P2 | 3 1 4 | 2 1 1 |
| P3 | 4 2 2 | 0 0 2 |
銀行還剩金額(Available)：
| 銀行還剩金額(Available) |
|---|
| A B C |
| 1 1 2 |
銀行（系統）為什么要給公司（行程）這樣分配金額（資源）？
為了避免分配金額（資源）出現公司（行程）回圈等待（死鎖）的情況
什么是回圈等待？就是P0公司在等待著銀行分配金額，但銀行的錢不夠了，銀行的錢都在公司P1了，但公司P1需要完成專案的錢還遠遠不夠，要等公司P2的專案完成了把錢還給銀行才可能夠，
銀行現在手里三個金庫A、B、C都還有錢，但銀行把錢分給哪個公司最合理，能最快識訓資金呢？如圖所示，各個公司的還需貸款(Claim-Allocation)為
| 公司還需貸款(Claim-Allocation) | |
|---|---|
| A B C | |
| P0 | 2 2 2 |
| P1 | 1 0 2 |
| P2 | 1 0 3 |
| P3 | 4 2 0 |
因為銀行剩余金額(Available)=(1，1，2)>公司P1還需要的貸款金額(Claim-Allocation)=(1，0，2)
所以銀行可以把手上剩余的錢分配給公司P1
假設當銀行把手上的剩余金額(Available)分配給公司P1，即銀行Available=(1，1，2)-公司P0(Claim-Allocation)=(1，0，2)=(0，1，0)
此時，公司P1獲得了專案所需的全部資金，即公司已經獲得的資金(Calim)=(6，1，3)，當公司P1完成專案后，就把貸款的金額還給銀行了，
此時銀行三個金庫的金額為(0，1，0)加上剛剛公司P1還回來的金額(6，1，3)，即(6，2，3)
| 銀行還剩金額(Available) |
|---|
| A B C |
| 6 2 3 |
此時，各公司的情況如下
| 公司 | 公司總貸款(Claim) | 公司已貸金額(Allocation) |
|---|---|---|
| A B C | A B C | |
| P0 | 3 2 2 | 1 0 0 |
| P2 | 3 1 4 | 2 1 1 |
| P3 | 4 2 2 | 0 0 2 |
| 公司還需貸款(Claim-Allocation) | |
|---|---|
| A B C | |
| P0 | 2 2 2 |
| P2 | 1 0 3 |
| P3 | 4 2 0 |
因為銀行剩余金額(Available)=(6，2，3)>公司P0(Claim-Allocation)=(2，2，2)和公司P2(Claim-Allocation)=(1，0，3)和公司P3（Claim-Allocation）=（4，2，0）所以銀行可以把手上剩余的錢分配給公司P0或者公司P2或者公司P3
假設當銀行把手上的剩余金額(Available)分配給公司P0，即銀行Available=(6，2，3)-公司P0(Claim-Allocation)=(2，2，2)=(4，0，1)
此時，公司P0獲得了專案所需的全部資金，即公司已經獲得的資金(Calim)=(3，2，2)，當公司P0完成專案后，就把貸款的金額還給銀行了，
此時銀行三個金庫的金額為(4，0，1)加上剛付訓剩下的(3，2，2)，即(7，2，3)
| 銀行還剩金額(Available) |
|---|
| A B C |
| 7 2 3 |
此時，各公司的情況如下
| 公司 | 公司總貸款(Claim) | 公司已貸金額(Allocation) |
|---|---|---|
| A B C | A B C | |
| P2 | 3 1 4 | 2 1 1 |
| P3 | 4 2 2 | 0 0 2 |
| 公司還需貸款(Claim-Allocation) | |
|---|---|
| A B C | |
| P2 | 1 0 3 |
| P3 | 4 2 0 |
因為銀行剩余金額(Available)=(7，2，3)>公司P2(Claim-Allocation)=(1，0，3)和公司P3(Claim-Allocation)=(4，2，0)
所以銀行可以把手上剩余的錢分配給公司P2或者公司P3
銀行分配給公司P2后，識訓來的錢又可以分配給公司P3還需貸款的錢，這樣，就把四個公司的專案所需資金都解決了
解決順序是公司P1→公司P0→公司P2→公司P3，或者公司P1→公司P0→公司P3→公司P2，或者其他，有很多
這個順序就是銀行家演算法中的安全序列，此時銀行處于安全狀態
至此，整個計算程序就結束了，
在作業系統的計算題考試中，常出現的幾個問題是：
①系統是否處于安全狀態，即看一開始的時候銀行（系統）還剩下的金額（資源）夠不夠分配給其中的一個公司（行程），或者分配之后返還的金額夠不夠再進行下一輪的分配（一般題目不會這樣出，這是死題）
②求出系統的安全序列，就如上面的解釋進行計算即可
③問某個公司（假設還需貸款(Claim-Allocation)=(1，1，1)）能不能申請金額（資源），但銀行（系統）只有（0，1，0）的儲備資金，所以是不能申請
④各個行程還需要的資源數，即(Claim-Allocation)
本例題是采用
作業系統教程（第五版）費翔林 駱斌 編著
P184 23題
如有問題可私聊博主或私郵博主
感謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250677.html
標籤：其他
上一篇：雜談 跟編程無關的事情5