銀行演算法類

㈠ 銀行家演算法

所謂死鎖，是指多個進程循環等待它叢燃方佔有的資源而無限期地僵持下去的局面。死鎖是指兩個或兩個以上的進程在執行過程中，由於競爭資源或者由於彼此通信而造成的一種阻塞的現象段山，若無外力作用，它們都將無法推進下去。此時稱系統處於死鎖狀態或系統產生了死鎖，這些永遠在互相等待的進程稱為死鎖進程。

銀行家演算法：避免死鎖
資源有序分配法：預防死鎖
資源分配圖化簡法：檢測死鎖
撤銷進程法：解決死鎖

銀行家演算法：銀行家演算法是從當前狀態出發，按照系統各類資源剩餘量逐個檢查各進程需要申請的資源量，找到一個各類資源申請量均小於等於系統剩餘資源量的進滲燃虛程P1。然後分配給該P1進程所請求的資源，假定P1完成工作後歸還其佔有的所有資源，更新系統剩餘資源狀態並且移除進程列表中的P1，進而檢查下一個能完成工作的客戶，......。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。若找不到這樣的安全序列，則當前狀態不安全。

㈡ 銀行家演算法

簡介
銀行家演算法是一種最有代表性的避免死鎖的演算法。在避免死鎖方法中允許進程動態地申請資源，但系銀行家演算法統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家演算法，系統必須設置若干數據結構。 要解釋銀行家演算法，必須先解釋操作系統安全狀態和不安全狀態。 安全序列是指一個進程序列{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];

㈢ 「銀行家演算法」是怎樣的一個演算法

銀行家演算法=-- -

1. 安全狀態: 在某時刻系統中所有進程可以排列一個安全序列:{P1,P2,`````Pn},剛稱此時,系統是安全的.
所謂安全序列{P1,P2,`````Pn}是指對於P2,都有它所需要剩餘資源數量不大於系統掌握的剩餘的空間資源與所有Pi(j<i)所佔的資源之和.
2.不安全狀態可能產生死鎖.
目前狀態 最大需求 尚需
P1 3 9 6
P2 5 10 5
P3 2 4 2

在每一次進程中申請的資源,判定一下,若實際分配的話,之後系統是否安全.
3.銀行家演算法的思路:
1),進程一開始向系統提出最大需求量.
2),進程每次提出新的需求(分期貸款)都統計是否超出它事先提出的最大需求量.
3),若正常,則判斷該進程所需剩餘剩餘量(包括本次申請)是否超出系統所掌握的
剩餘資源量,若不超出,則分配,否則等待.
4.銀行家演算法的數據結構.
1),系統剩餘資源量A[n],其中A[n]表示第I類資源剩餘量.
2),各進程最大需求量,B[m][n],其中B[j][i]表示進程j對i
類資源最大需求.
3),已分配資源量C[m][n],其中C[j][i]表示系統j程已得到的第i資源的數量.
4),剩餘需求量.D[m][n],其中D[j][i]對第i資源尚需的數目.
5.銀行家演算法流程:當某時刻,某進程時,提出新的資源申請,系統作以下操作:
1),判定E[n]是否大於D[j][n],若大於,表示出錯.
2),判定E[n]是否大於系統剩餘量A[n],若大於,則該進程等待.
3),若以上兩步沒有問題,嘗試分配,即各變數作調整.
4),按照安全性推測演算法,判斷,分配過後,系統是否安全,若安全,則實際分配,否則,撤消分配,讓進程等待.
6."安全性檢測"演算法
1),先定義兩個變數,用來表示推算過程的數據.
F[n]=A[n],表示推算過程中,系統中剩餘資源量的變化.
J[n]=False表示推算過程中各進程是否假設"已完成"
2),流程:
在"剩餘"的進程中(在推算)過程中,一些進程假設已完成,查找D[j][n]<=F[n]的進程,找到後令J[j]=True
(假設該進程完成),F[n]+D[j][n](該進程所佔資源釋放),如此循環執行.
若最後,所有的F[n]=True(在推算過程中,所有進程均可以完成),則表示(分配過後)系統是安全的,否則系統是不安全的.
參考資料：http://huangqiyu.blogchina.com/419807.html

㈣ 銀行家演算法應用在哪些方面

只要是涉及多個獨立個體對某種資源的動態申請和回收就可以應用此演算法。在計算機科學中一般用此演算法檢測進程的推進順序是否是安全隊列，如果不是的話，會因為對資源的爭奪而造成死鎖。

㈤ 淺析銀行家演算法

作為避免死鎖的一種演算法，銀行家演算法可以說是最為出名的了。這個名字的來源是因為該演算法起初是為銀行系統設計的，以確保銀行在發放現金貸款時，不會發生不能滿足所有客戶需要的情況。在操作系統中也可以用它來實現避免死鎖。

首先我們要了解銀行家演算法的本質也即避免死鎖的原理。避免死鎖作為一種事先預防死鎖的策略，原理是在為各個進程分配資源的過程中不允許系統進去不安全狀態，以此來避免死鎖的發生。所謂安全狀態，是指系統能按某種進程推進順序為每個進程分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順利地完成。此時稱該進程推進序列為安全序列，如果無法找到這樣一個安全序列，則稱系統處於不安全狀態。

銀行家演算法中的數據結構。為了實現銀行家演算法，在系統中必須設置這樣四個數據結構，分別用來描述系統中可利用的資源，所有進程對資源的最大需求，系統中的資源分配以及所有進程還需要多少資源的情況。

(1)可利用資源向量Available。這是一個含有m個元表的數組,其中的每一個元素代表一類可利用的資源數目。其數值隨該類資源的分配和回收而動態地改變。如果 Available=K,則表示系統中現有Rj類資源K個。

    (2)最大需求矩陣Max。這是一個nxm的矩陣,它定義了系統中n個進程中的每個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。

    (3)分配矩陣 Allocation。這也是一個nxm的矩陣,它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,表示進程i當前已分得Rj類資源的數目為K。

    (4)需求矩陣Need。這也是一個nxm的矩陣,用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個才能完成。

當一個進程發出請求資源的請求後，如果它所請求的資源大於目前系統可利用資源則不予分配。如果小於可利用資源，則系統試探著把資源分配給該進程，並修改分配之後的資源數值。接著系統執行安全演算法，檢查此次資源分配後系統是否處於安全狀態。若安全，才正式將資源分配給該進程，以完成本次分配。否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓該進程等待。

㈥ 銀行家演算法

銀行家演算法是一種預防死鎖的演算法。具體演算法步驟可以參考網路： 銀行家演算法

例子 ：某系統有A、B、C、D , 4類資源共5個進程（P0、P1、P2、P3、P4）共享，各進程對資源的需求和分配情況如下表所示。

輸入進程的數目:5
輸入資源的種類:4
輸入每個進程最多所需的各類資源數:
P0 : 0 0 1 2
P1 : 1 7 5 0
P2 : 2 3 5 6
P3 : 0 6 5 2
P4 : 0 6 5 6
輸入每個進程已經分配的各類資源數:
P0 : 0 0 1 2
P1 : 1 0 0 0
P2 : 1 3 5 4
P3 : 0 6 3 2
P4 : 0 0 1 4
請輸入各個資源現有的數目:
1 5 2 0
當前系統安全!
系統安全序列是:
P0->P2->P1->P3->P4
輸入要申請資源的進程號(0-4)：1
輸入進程所請求的各資源的數量:0 4 2 0
系統安全!
系統安全序列是:
P0->P2->P1->P3->P4
同意分配請求!

系統可用的資源數為 : 1 1 0 0
各進程還需要的資源量:
進程 P0 : 0 0 0 0
進程 P1 : 0 3 3 0
進程 P2 : 1 0 0 2
進程 P3 : 0 0 2 0
進程 P4 : 0 6 4 2

各進程已經得到的資源量:
進程 P0 : 0 0 1 2
進程 P1 : 1 4 2 0
進程 P2 : 1 3 5 4
進程 P3 : 0 6 3 2
進程 P4 : 0 0 1 4

是否再次請求分配？是請按Y/y，否請按N/n:
N

㈦ 什麼是銀行家演算法

銀行家演算法是最有代表性的避免死鎖演算法，是Dijkstra提出的銀行家演算法。這是由於該演算法能用於銀行系統現金貸款的發放而得名。
銀行家可以把一定數量的資金供多個用戶周轉使用,為保證資金的安全,銀行家規定:
(1)當一個用戶對資金的最大需求量不超過很行家現有的資金時可接納該用戶.
(2)用戶可以分期貸款,但貸款的總數不能超過最大需求量;
(3)當銀行家現有的資金不能滿足用戶的尚需總數時,對用戶的貸款可推遲支付,但總能使用戶在有限的時間里得到貸款;
(4)當用戶得到所需的全部資金後,一定能在有限的時間里歸還所有資金

銀行家演算法是通過動態地檢測系統中資源分配情況和進程對資源的需求情況來決定如何分配資源的，在能確保系統處於安全狀態時才能把資源分配給申請者，從而避免系統發生死鎖。
要記住的一些變數的名稱
1 Available（可利用資源總數）
某類可利用的資源數目，其初值是系統中所配置的該類全部可用資源數目。
2 Max：某個進程對某類資源的最大需求數
3 Allocation： 某類資源已分配給某進程的資源數。
4 Need：某個進程還需要的各類資源數。
Need= Max-Allocation

系統把進程請求的資源(Request)分配給它以後要修改的變數
Available:=Available-Request;
Allocation:=Allocation+Request;
Need:= Need- Request;

㈧ 銀行家演算法是什麼

銀行家演算法=-- -

1. 安全狀態: 在某時刻系統中所有進程可以排列一個安全序列:{P1,P2,`````Pn},剛稱此時,系統是安全的.
所謂安全序列{P1,P2,`````Pn}是指對於P2,都有它所需要剩餘資源數量不大於系統掌握的剩餘的空間資源與所有Pi(j<i)所佔的資源之和.
2.不安全狀態可能產生死鎖.
目前狀態 最大需求 尚需
P1 3 9 6
P2 5 10 5
P3 2 4 2

在每一次進程中申請的資源,判定一下,若實際分配的話,之後系統是否安全.
3.銀行家演算法的思路:
1),進程一開始向系統提出最大需求量.
2),進程每次提出新的需求(分期貸款)都統計是否超出它事先提出的最大需求量.
3),若正常,則判斷該進程所需剩餘剩餘量(包括本次申請)是否超出系統所掌握的
剩餘資源量,若不超出,則分配,否則等待.
4.銀行家演算法的數據結構.
1),系統剩餘資源量A[n],其中A[n]表示第I類資源剩餘量.
2),各進程最大需求量,B[m][n],其中B[j][i]表示進程j對i
類資源最大需求.
3),已分配資源量C[m][n],其中C[j][i]表示系統j程已得到的第i資源的數量.
4),剩餘需求量.D[m][n],其中D[j][i]對第i資源尚需的數目.
5.銀行家演算法流程:當某時刻,某進程時,提出新的資源申請,系統作以下操作:
1),判定E[n]是否大於D[j][n],若大於,表示出錯.
2),判定E[n]是否大於系統剩餘量A[n],若大於,則該進程等待.
3),若以上兩步沒有問題,嘗試分配,即各變數作調整.
4),按照安全性推測演算法,判斷,分配過後,系統是否安全,若安全,則實際分配,否則,撤消分配,讓進程等待.
6."安全性檢測"演算法
1),先定義兩個變數,用來表示推算過程的數據.
F[n]=A[n],表示推算過程中,系統中剩餘資源量的變化.
J[n]=False表示推算過程中各進程是否假設"已完成"
2),流程:
在"剩餘"的進程中(在推算)過程中,一些進程假設已完成,查找D[j][n]<=F[n]的進程,找到後令J[j]=True
(假設該進程完成),F[n]+D[j][n](該進程所佔資源釋放),如此循環執行.
若最後,所有的F[n]=True(在推算過程中,所有進程均可以完成),則表示(分配過後)系統是安全的,否則系統是不安全的.
參考資料：http://huangqiyu.blogchina.com/419807.html