銀行家算法

reference ; http://www.yuanma.org/data/2008/0116/article_2945.htm
算法的實現
一、初始化

由用戶輸入數據，分別對可利用資源向量矩陣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，則表示安全；否則系統不安全。

各算法流程圖

#include? < iostream >
using ? namespace ?std;
#define ?MAXPROCESS?50????????????????????????/*最大進程數*/
#define ?MAXRESOURCE?100????????????????????????/*最大資源數*/
int ?AVAILABLE[MAXRESOURCE];???????????????????? /**/ /* 可用資源數組 */
int ?MAX[MAXPROCESS][MAXRESOURCE];???????????? /**/ /* 最大需求矩陣 */
int ?ALLOCATION[MAXPROCESS][MAXRESOURCE];???? /**/ /* 分配矩陣 */
int ?NEED[MAXPROCESS][MAXRESOURCE];???????????? /**/ /* 需求矩陣 */
int ?REQUEST[MAXPROCESS][MAXRESOURCE];???????? /**/ /* 進程需要資源數 */
bool ?FINISH[MAXPROCESS];???????????????????????? /**/ /* 系統是否有足夠的資源分配 */
int ?p[MAXPROCESS];????????????????????????????? /**/ /* 記錄序列 */
int ?m,n;???????????????????????????????????? /**/ /* m個進程,n個資源 */

void ?Init();
bool ?Safe();
void ?Bank();
int ?main()
{
????Init();
????Safe();
????Bank();
????getchar();
????
}
// 給出系統擁有的每種資源數，已經分配給每個進程的資源數，還有每個進程最多需要每種資源的個數，讓你判斷當前系統是不是安全的?
void ?Init()???????????????? /**/ /* 初始化算法 */
{
???? int ?i,j;
????cout << " 請輸入進程的數目: " ;
????cin >> m;
????cout << " 請輸入資源的種類: " ;
????cin >> n;
????cout << " 請輸入每個進程最多所需的各資源數,按照 " << m << " x " << n << " 矩陣輸入 " << endl;
???? for (i = 0 ;i < m;i ++ )
???? for (j = 0 ;j < n;j ++ )
????cin >> MAX[i][j];
????cout << " 請輸入每個進程已分配的各資源數,也按照 " << m << " x " << n << " 矩陣輸入 " << endl;
???? for (i = 0 ;i < m;i ++ )
???? {
???????? for (j = 0 ;j < n;j ++ )
???????? {
????????????cin >> ALLOCATION[i][j];
????????????NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];
???????????? if (NEED[i][j] < 0 )
???????????? {
????????????????cout << " 您輸入的第 " << i + 1 << " 個進程所擁有的第 " << j + 1 << " 個資源數錯誤,請重新輸入: " << endl;
????????????????j -- ;
???????????????? continue ;
????????????}
????????}
????}
????cout << " 請輸入各個資源現有的數目: " << endl;
???? for (i = 0 ;i < n;i ++ )
???? {
????????cin >> AVAILABLE[i];
????}
}

void ?Bank()???????????????? /**/ /* 銀行家算法 */
{
???? int ?i,cusneed;
???? char ?again;
???? while ( 1 )
???? {
Restart:
????????cout << " 請輸入要申請資源的進程號(注:第1個進程號為0,依次類推) " << endl;
????????cin >> cusneed;
????????cout << " 請輸入進程所請求的各資源的數量 " << endl;
???????? for (i = 0 ;i < n;i ++ )
???????? {
????????????cin >> REQUEST[cusneed][i];
????????}
???????? for (i = 0 ;i < n;i ++ )
???????? {
???????????? if (REQUEST[cusneed][i] > NEED[cusneed][i])
???????????? {
????????????????cout << " 您輸入的請求數超過進程的需求量!請重新輸入! " << endl;
???????????????? goto ?Restart;
????????????}
???????????? if (REQUEST[cusneed][i] > AVAILABLE[i])
???????????? {
????????????????cout << " 您輸入的請求數超過系統有的資源數!請重新輸入! " << endl;
???????????????? goto ?Restart;
????????????}
????????}
???????? for (i = 0 ;i < n;i ++ )
???????? {
????????????AVAILABLE[i] -= REQUEST[cusneed][i];
????????????ALLOCATION[cusneed][i] += REQUEST[cusneed][i];
????????????NEED[cusneed][i] -= REQUEST[cusneed][i];
????????}
???????? if (Safe())
???????? {
????????????cout << " 同意分配請求! " << endl;
????????}
???????? else
???????? {
????????????cout << " 您的請求被拒絕! " << endl;
???????????? for (i = 0 ;i < n;i ++ )
???????????? {
????????????????AVAILABLE[i] += REQUEST[cusneed][i];
????????????????ALLOCATION[cusneed][i] -= REQUEST[cusneed][i];
????????????????NEED[cusneed][i] += REQUEST[cusneed][i];
????????????}
????????}
???????? for (i = 0 ;i < m;i ++ )
???????? {
????????????FINISH[i] = false ;
????????}
????????cout << " 您還想再次請求分配嗎?是請按y/Y,否請按其它鍵 " << endl;
????????cin >> again;
???????? if (again == ' y ' || again == ' Y ' )
???????? {
???????????? continue ;
????????}
???????? break ;
????????}
}

bool ?Safe()???????????????????????????????????? /**/ /* 安全性算法 */
{
???? int ?i,j,k,l = 0 ;
???? int ?Work[MAXRESOURCE];???????????????????? /**/ /* 工作數組 */
???? for (i = 0 ;i < n;i ++ )
????Work[i] = AVAILABLE[i];
???? for (i = 0 ;i < m;i ++ )
???? {
????????FINISH[i] = false ;
????}
???? for (i = 0 ;i < m;i ++ )
???? {????
???????? if (FINISH[i] == true )
???????? {
???????????? continue ;
????????}
???????? else
???????? {
???????????? for (j = 0 ;j < n;j ++ )
???????????? {
???????????????? /**/ /*
????????????????看看所有的資源對于這個進程是不是都有效
???????????????? */
???????????????? if (NEED[i][j] > Work[j])
???????????????? {
???????????????????? break ;
????????????????}
????????????}
???????????? if (j == n)
???????????? {?
???????????????? /**/ /*
????????????????那么你就需要看每個進程還需要每種資源多少，把它計算出來，然后看你剩下的可分配的資源數是不是可以達到其中一個進程的要求，
????????????????如果可以，就分配給它，讓這個進程執行，執行結束后，這個進程釋放資源，重新計算系統的可分配的資源
???????????????? */
????????????????FINISH[i] = true ;
???????????????? for (k = 0 ;k < n;k ++ )
???????????????? {
????????????????????Work[k] += ALLOCATION[i][k];
????????????????}
????????????????p[l ++ ] = i;
????????????????i =- 1 ;
????????????}
???????????? else
???????????? {
???????????????? continue ;?
????????????}
????????}
???????? if (l == m)
???????? {
????????????cout << " 系統是安全的 " << endl;
????????????cout << " 安全序列: " << endl;
???????????? for (i = 0 ;i < l;i ++ )
???????????? {
????????????????cout << p[i];
???????????????? if (i != l - 1 )
???????????????? {
????????????????????cout << " --> " ;
????????????????}
????????????}
????????????cout << "" << endl;
???????????? return ? true ;
????????}
????}
????cout << " 系統是不安全的 " << endl;
???? return ? false ;
}

　　銀行家算法是這樣的：

　　1）當一個用戶對資金的最大的需求量不超過銀行家現有的資金時就可以接納該用戶。

　　2）用戶可以分期貸款，但貸款的總數不能超過最大需求量。

　　3）當銀行家現有的資金不能滿足用戶的尚需貸款時，對用戶的貸款可推遲支付，但總能使用戶在有限的時間里得到貸款。

　　4）當用戶得到所需的全部資金后，一定能在有限的時間里歸還所有資金。

　　我們把操作系統看作是銀行家，操作系統管理的資源相當于是銀行家管理的資金，則銀行家算法就是：

　　1）當一個進程首次申請資源時，測試該進程對資源的最大的需求量，如果不超過系統現存資源時就可以按他的當前申請量為其分配資源。 否則推遲分配。

　　2）進程執行中繼續申請資源時，測試該進程占用資源和本次申請資源總數有沒有超過最大需求量。超過就不分配，沒超過則再測試現存資源是否滿足進程還需要的最大資源量，滿足則按當前申請量分配，否則也推遲分配。

　　總之，銀行家算法要保證分配資源時系統現存資源一定能滿足至少一個進程所需的全部資源。這樣就可以保證所有進程都能在有限時間內得到需要的全部資源。這就是安全狀態。

　　（銀行家算法在操作系統的實踐考試中可能會用到）

posted on 2008-07-06 22:16 snowball 閱讀(7008) 評論(8)  編輯 收藏 引用 所屬分類: 算法＋數據結構