銀行家演算法的安全性演算法

『壹』 銀行家演算法安全序列怎麼判斷

先說一下銀行家的演算法：
設進程cusneed提出請求REQUEST [i]，則銀行家演算法按如下規則進行判斷。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉（2)；否則，出錯。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，則轉（3)；否則，等待。
(3)系統試探分配資源，修改相關數據：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。
=================================================
題目中的計算過程：
先算出每個進程還需要多少進程才能滿足，即Request的值 = Need - Allocation
進程名 Allocation Need Request Available
ABC ABC ABC ABC
P1 4 0 5 4 0 11 0 0 6 2 3 3
P2 4 0 2 5 3 6 1 2 4
P3 2 1 4 4 2 5 2 1 1
P4 2 1 2 5 5 9 3 4 7
P5 3 1 3 4 2 4 1 1 1
第一題A項p3 p1 p4 p2 p5
先分配給P3，其Request(2,1,1) < available(2,2,3) 滿足，分配資源等待P3完成，P3進程完成之後，Available = (2,1,4) + (2,3,3) = (4,4,7)
然後分配給p1,其Request(0,0,6) < available(4,4,7)，可以滿足資源，分配資源給P1,P1完成任務釋放資源Available = (4,0,5) +(4,4,7) = (8,4,12)
接著P4，request(3 4 7) < available(8,4,12),可以滿足資源，分配資源給P4,P4完成任務釋放資源Available = (2,1,2) +(8,4,12) = (10,5,14)
接著p2，request(1 2 4) < available(10,5,14)可以滿足資源，分配資源給P4,P4完成任務釋放資源Available = (4,0,2)+ (10,5,14) = (14,5,16)
最後P5,request(1 1 1) < available(14,5,16)可以滿足資源，分配資源給P4,P4完成任務,資源全部釋放，變為(3 1 3 )+ (14,5,16) = (17,6,19)
所以A是安全序列。
同理分析B p1 p3 p5 p2 p4，先分配給P1的話Request(0,0,6) > available(2,3,3)，C資源不滿足，所以該序列不安全。
分析C項p4 p2 p3 p5 p1,先分配給p4, Request(3,4,7) > available(2,3,3)，ABC資源都不滿足，該序列不安全。
分析D項p2 p3 p1 p4 p5，先分配給P2，Request(1,2,4) > available(2,3,3)，C資源不滿足，所以該序列不安全。

第二題，分析方法跟上面的一樣，只是比較費時。如果單選的話，看一下答案，D項，先分配給P4，顯然完成P4還需( 3 4 7) ,其大於 available，所D項不安全。

『貳』 銀行家演算法(操作系統）

1、這是安全狀態：
P1的需求小於可用資源數，先滿足P1的請求，然後回收P1資源：可用資源變為 （3,3,2）＋（2,0,0）＝（5,3,2）；
這時P3可分配，P3結束後回收資源，可用資源為（5,3,2）＋（2,1,1）＝（7,4,3）
這時P0可分配，P0結束後回收資源，可用資源為（7,4,3）＋（0,1,0）＋（7,5,3）
接下來是P2，結束後可用資源為（7,5,3）＋（3,0,2）＝（10,5,5）
最後分配P4，結束後可用資源為（10,5,5）＋（0,0,2）＝（10,5,7）
這樣得到一個安全序列：P1－P3－P0－P2－P4，所以T0狀態是安全的。

2、T0時刻P1請求（1,1,2）<可用資源數（3,3,2），可以直接滿足。

『叄』 銀行家演算法

銀行家演算法，一種解決資源分配問題的策略，用於避免系統進入不安全狀態。其核心思想在於動態檢查系統是否滿足安全條件。在進行資源分配時，系統會維護一個安全序列，該序列中每一步都確保系統處於安全狀態。如果分配請求滿足安全序列，系統便可以安全地執行資源分配。否則，請求將被拒絕。通過這種機制，銀行家演算法確保了系統始終處於安全狀態，有效防止了死鎖和資源浪費。

銀行家演算法中，系統維護一個資源分配矩陣，表示系統中各種資源的數量。同時，系統還會維護一個進程資源需求矩陣和一個進程已分配資源矩陣。安全序列的生成需要遵循以下步驟：首先，初始化安全序列為空，然後遍歷所有進程，如果當前進程已分配資源加上請求資源不會超過其最大需求，並且不會使系統進入不安全狀態，則將該進程加入安全序列。遍歷結束後，安全序列中所有進程的資源分配情況即為安全狀態。

在實際應用中，銀行家演算法廣泛用於操作系統、資料庫管理系統和分布式系統中。特別是在多進程環境下的資源管理，銀行家演算法通過動態檢查安全條件，確保資源分配的合理性和安全性。通過實現銀行家演算法，系統可以有效避免資源競爭導致的死鎖問題，確保系統的穩定運行。

總結，銀行家演算法通過維護安全序列和動態檢查安全條件，確保了資源分配過程的安全性與合理性。在多進程環境中，銀行家演算法有效地解決了資源分配問題，避免了系統進入不安全狀態，為現代操作系統、資料庫管理系統和分布式系統提供了堅實的資源管理基礎。

『肆』 銀行家演算法

簡介
銀行家演算法是一種最有代表性的避免死鎖的演算法。在避免死鎖方法中允許進程動態地申請資源，但系銀行家演算法統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家演算法，系統必須設置若干數據結構。 要解釋銀行家演算法，必須先解釋操作系統安全狀態和不安全狀態。 安全序列是指一個進程序列{P1，…，Pn}是安全的，如果對於每一個進程Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有進程Pj (j < i )當前佔有資源量之和。
安全狀態
如果存在一個由系統中所有進程構成的安全序列P1，…，Pn，則系統處於安全狀態。安全狀態一定是沒有死鎖發生。
不安全狀態
不存在一個安全序列。不安全狀態不一定導致死鎖。
[編輯本段]銀行家演算法的數據結構
1）可利用資源向量Available 是個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目。如果Available〔j〕=K，則表示系統中現有Rj類資源K個。 2）最大需求矩陣Max 這是一個n×m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max〔i,j〕=K，則表示進程i需要Rj類資源的最大數目為K。 3）分配矩陣Allocation 這也是一個n×m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation〔i,j〕=K，則表示進程i當前已分得Rj類資源的 數目為K。 4）需求矩陣Need。 這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need〔i,j〕=K，則表示進程i還需要Rj類資源K個，方能完成其任務。 Need〔i,j〕=Max〔i,j〕-Allocation〔i,j〕
[編輯本段]銀行家演算法原理：
我們可以把操作系統看作是銀行家，操作系統管理的資源相當於銀行家管理的資金，進程向操作系統請求分配資源相當於用戶向銀行家貸款。 為保證資金的安全,銀行家規定: (1) 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客; (2) 顧客可以分歧貸款,但貸款的總數不能超過最大需求量; (3) 當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間里得到貸款; (4) 當顧客得到所需的全部資金後,一定能在有限的時間里歸還所有的資金. 操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程已佔用的資源數與本次申請的資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統現存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。 運行平台：Windows XP VS2005 編程語言：C#
[編輯本段]演算法的實現
初始化
由用戶輸入數據，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。
銀行家演算法
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處於安全狀態，便可以避免發生死鎖。 銀行家演算法的基本思想是分配資源之前,判斷系統是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的演算法。 設進程cusneed提出請求REQUEST [i]，則銀行家演算法按如下規則進行判斷。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(2)；否則，出錯。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。 (3)系統試探分配資源，修改相關數據： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]; NEED[cusneed][i]-=REQUEST[cusneed][i]; (4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。
安全性檢查演算法
(1)設置兩個工作向量Work=AVAILABLE;FINISH (2)從進程集合中找到一個滿足下述條件的進程， FINISH==false; NEED<=Work; 如找到，執行(3)；否則，執行(4) (3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。 Work+=ALLOCATION; Finish=true; GOTO 2 (4)如所有的進程Finish= true，則表示安全；否則系統不安全。
[編輯本段]演算法
/// 資源數 public static int resourceNumber; /// 進程數 public static int processNumber; /// 可用資源數組 public static int[] Available; /// 工作向量 public static int[] work; /// 它表示系統是否有足夠的資源分配給進程 public static bool[] Finish; /// 最大需求矩陣 public static int[][] Max; /// 分配矩陣 public static int[][] Allocation; /// 需求矩陣 public static int[][] Need; /// 安全序列 public static int[] SafeSequence; /// 資源請求向量 public static int[] Request; 演算法思想： 主要是：遞歸+深度優先搜尋+回溯 演算法源代碼如下： /// 深搜+回溯實現銀行家演算法 /// <param name="n">已完成的進程數</param> public void DFS_searchSafeSequence(int n) { if (n == processNumber) { //找到一個安全序列,可以顯示所有安全序列 //顯示在richTextBoxshow.Text上 for (int i = 0; i < processNumber; i++) { richTextBoxshow.Text += SafeSequence[i] + " "; } richTextBoxshow.Text += "\n"; return; } for (int i = 0; i < processNumber; i++) { if (Finish[i] == false)//進程尚未完成 { //判斷現有資源是否可以滿足這個進程 bool isOK = true; for (int j = 0; j < resourceNumber; j++) { if (Need[i][j] > work[j]) { isOK = false; break; } } //可以滿足 if (isOK) { //先試探的將資源分配給這個進程 for (int j = 0; j < resourceNumber; j++) { work[j] += Allocation[i][j]; } //已經完成 Finish[i] = true; //加入安全序列 SafeSequence[n] = i; //繼續搜索 DFS_searchSafeSequence(n+1); //回溯 Finish[i] = false; SafeSequence[n] = -1; for (int j = 0; j < resourceNumber; j++) { work[j] -= Allocation[i][j];