C++ Jounior

銀行家算法

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

由用戶輸入數(shù)據(jù)，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。

?

二、銀行家算法

在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。

銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。

設(shè)進(jìn)程cusneed提出請求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。

(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯。

(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：

???????? AVAILABLE[i]-=REQUEST[cusneed][i];

???????? ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

???????? NEED[cusneed][i]-=REQUEST[cusneed][i];

(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。

?

三、安全性檢查算法

(1)設(shè)置兩個工作向量Work=AVAILABLE;FINISH

(2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程，

FINISH==false;

NEED<=Work;

如找到，執(zhí)行(3)；否則，執(zhí)行(4)

(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work+=ALLOCATION;

Finish=true;

GOTO 2

(4)如所有的進(jìn)程Finish= true，則表示安全；否則系統(tǒng)不安全。

各算法流程圖

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

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

void ?Bank()???????????????? /**/ /* 銀行家算法 */
{
???? int ?i,cusneed;
???? char ?again;
???? while ( 1 )
???? {
Restart:
????????cout << " 請輸入要申請資源的進(jìn)程號(注:第1個進(jìn)程號為0,依次類推) " << endl;
????????cin >> cusneed;
????????cout << " 請輸入進(jìn)程所請求的各資源的數(shù)量 " << 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 << " 您輸入的請求數(shù)超過進(jìn)程的需求量!請重新輸入! " << endl;
???????????????? goto ?Restart;
????????????}
???????????? if (REQUEST[cusneed][i] > AVAILABLE[i])
???????????? {
????????????????cout << " 您輸入的請求數(shù)超過系統(tǒng)有的資源數(shù)!請重新輸入! " << 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];???????????????????? /**/ /* 工作數(shù)組 */
???? 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 ++ )
???????????? {
???????????????? /**/ /*
????????????????看看所有的資源對于這個進(jìn)程是不是都有效
???????????????? */
???????????????? if (NEED[i][j] > Work[j])
???????????????? {
???????????????????? break ;
????????????????}
????????????}
???????????? if (j == n)
???????????? {?
???????????????? /**/ /*
????????????????那么你就需要看每個進(jìn)程還需要每種資源多少，把它計算出來，然后看你剩下的可分配的資源數(shù)是不是可以達(dá)到其中一個進(jìn)程的要求，
????????????????如果可以，就分配給它，讓這個進(jìn)程執(zhí)行，執(zhí)行結(jié)束后，這個進(jìn)程釋放資源，重新計算系統(tǒng)的可分配的資源
???????????????? */
????????????????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 << " 系統(tǒng)是安全的 " << endl;
????????????cout << " 安全序列: " << endl;
???????????? for (i = 0 ;i < l;i ++ )
???????????? {
????????????????cout << p[i];
???????????????? if (i != l - 1 )
???????????????? {
????????????????????cout << " --> " ;
????????????????}
????????????}
????????????cout << "" << endl;
???????????? return ? true ;
????????}
????}
????cout << " 系統(tǒng)是不安全的 " << endl;
???? return ? false ;
}

　　銀行家算法是這樣的：

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

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

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

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

　　我們把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于是銀行家管理的資金，則銀行家算法就是：

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

　　2）進(jìn)程執(zhí)行中繼續(xù)申請資源時，測試該進(jìn)程占用資源和本次申請資源總數(shù)有沒有超過最大需求量。超過就不分配，沒超過則再測試現(xiàn)存資源是否滿足進(jìn)程還需要的最大資源量，滿足則按當(dāng)前申請量分配，否則也推遲分配。

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

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

posted on 2008-07-06 22:16 snowball 閱讀(6814) 評論(8)  編輯 收藏 引用 所屬分類: 算法＋數(shù)據(jù)結(jié)構(gòu)