reference ; http://www.yuanma.org/data/2008/0116/article_2945.htm
算法的實(shí)現(xiàn)
一、初始化
由用戶(hù)輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。
?
二、銀行家算法
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿(mǎn)意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。
銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。
設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。
(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í)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。
?
三、安全性檢查算法
(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH
(2)從進(jìn)程集合中找到一個(gè)滿(mǎ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個(gè)進(jìn)程,n個(gè)資源
*/
void
?Init();
bool
?Safe();
void
?Bank();
int
?main()
{
????Init();
????Safe();
????Bank();
????getchar();
????
}
//
給出系統(tǒng)擁有的每種資源數(shù)，已經(jīng)分配給每個(gè)進(jìn)程的資源數(shù)，還有每個(gè)進(jìn)程最多需要每種資源的個(gè)數(shù)，讓你判斷當(dāng)前系統(tǒng)是不是安全的?
void
?Init()????????????????
/**/
/*
初始化算法
*/
{
????
int
?i,j;
????cout
<<
"
請(qǐng)輸入進(jìn)程的數(shù)目:
"
;
????cin
>>
m;
????cout
<<
"
請(qǐng)輸入資源的種類(lèi):
"
;
????cin
>>
n;
????cout
<<
"
請(qǐng)輸入每個(gè)進(jìn)程最多所需的各資源數(shù),按照
"
<<
m
<<
"
x
"
<<
n
<<
"
矩陣輸入
"
<<
endl;
????
for
(i
=
0
;i
<
m;i
++
)
????
for
(j
=
0
;j
<
n;j
++
)
????cin
>>
MAX[i][j];
????cout
<<
"
請(qǐng)輸入每個(gè)進(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
<<
"
個(gè)進(jìn)程所擁有的第
"
<<
j
+
1
<<
"
個(gè)資源數(shù)錯(cuò)誤,請(qǐng)重新輸入:
"
<<
endl;
????????????????j
--
;
????????????????
continue
;
????????????}
????????}
????}
????cout
<<
"
請(qǐng)輸入各個(gè)資源現(xiàn)有的數(shù)目:
"
<<
endl;
????
for
(i
=
0
;i
<
n;i
++
)
????
{
????????cin
>>
AVAILABLE[i];
????}
}
void
?Bank()????????????????
/**/
/*
銀行家算法
*/
{
????
int
?i,cusneed;
????
char
?again;
????
while
(
1
)
????
{
Restart:
????????cout
<<
"
請(qǐng)輸入要申請(qǐng)資源的進(jìn)程號(hào)(注:第1個(gè)進(jìn)程號(hào)為0,依次類(lèi)推)
"
<<
endl;
????????cin
>>
cusneed;
????????cout
<<
"
請(qǐng)輸入進(jìn)程所請(qǐng)求的各資源的數(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
<<
"
您輸入的請(qǐng)求數(shù)超過(guò)進(jìn)程的需求量!請(qǐng)重新輸入!
"
<<
endl;
????????????????
goto
?Restart;
????????????}
????????????
if
(REQUEST[cusneed][i]
>
AVAILABLE[i])
????????????
{
????????????????cout
<<
"
您輸入的請(qǐng)求數(shù)超過(guò)系統(tǒng)有的資源數(shù)!請(qǐng)重新輸入!
"
<<
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
<<
"
同意分配請(qǐng)求!
"
<<
endl;
????????}
????????
else
????????
{
????????????cout
<<
"
您的請(qǐng)求被拒絕!
"
<<
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
<<
"
您還想再次請(qǐng)求分配嗎?是請(qǐng)按y/Y,否請(qǐng)按其它鍵
"
<<
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
++
)
????????????
{
????????????????
/**/
/*
????????????????看看所有的資源對(duì)于這個(gè)進(jìn)程是不是都有效
????????????????
*/
????????????????
if
(NEED[i][j]
>
Work[j])
????????????????
{
????????????????????
break
;
????????????????}
????????????}
????????????
if
(j
==
n)
????????????
{?
????????????????
/**/
/*
????????????????那么你就需要看每個(gè)進(jìn)程還需要每種資源多少，把它計(jì)算出來(lái)，然后看你剩下的可分配的資源數(shù)是不是可以達(dá)到其中一個(gè)進(jìn)程的要求，
????????????????如果可以，就分配給它，讓這個(gè)進(jìn)程執(zhí)行，執(zhí)行結(jié)束后，這個(gè)進(jìn)程釋放資源，重新計(jì)算系統(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)一個(gè)用戶(hù)對(duì)資金的最大的需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就可以接納該用戶(hù)。
2）用戶(hù)可以分期貸款，但貸款的總數(shù)不能超過(guò)最大需求量。
3）當(dāng)銀行家現(xiàn)有的資金不能滿(mǎn)足用戶(hù)的尚需貸款時(shí)，對(duì)用戶(hù)的貸款可推遲支付，但總能使用戶(hù)在有限的時(shí)間里得到貸款。
4）當(dāng)用戶(hù)得到所需的全部資金后，一定能在有限的時(shí)間里歸還所有資金。
我們把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于是銀行家管理的資金，則銀行家算法就是：
1）當(dāng)一個(gè)進(jìn)程首次申請(qǐng)資源時(shí)，測(cè)試該進(jìn)程對(duì)資源的最大的需求量，如果不超過(guò)系統(tǒng)現(xiàn)存資源時(shí)就可以按他的當(dāng)前申請(qǐng)量為其分配資源。 否則推遲分配。
2）進(jìn)程執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，測(cè)試該進(jìn)程占用資源和本次申請(qǐng)資源總數(shù)有沒(méi)有超過(guò)最大需求量。超過(guò)就不分配，沒(méi)超過(guò)則再測(cè)試現(xiàn)存資源是否滿(mǎn)足進(jìn)程還需要的最大資源量，滿(mǎn)足則按當(dāng)前申請(qǐng)量分配，否則也推遲分配。
總之，銀行家算法要保證分配資源時(shí)系統(tǒng)現(xiàn)存資源一定能滿(mǎn)足至少一個(gè)進(jìn)程所需的全部資源。這樣就可以保證所有進(jìn)程都能在有限時(shí)間內(nèi)得到需要的全部資源。這就是安全狀態(tài)。
（銀行家算法在操作系統(tǒng)的實(shí)踐考試中可能會(huì)用到）