計算機操作系統(tǒng)的銀行家算法
計算機操作系統(tǒng)的銀行家算法相信很多小伙伴都一知半解，下面由學(xué)習(xí)啦小編為大家整理了計算機操作系統(tǒng)的銀行家算法的相關(guān)知識，希望對大家有幫助!
計算機操作系統(tǒng)的銀行家算法
一、需求分析
1、進程的狀態(tài)有：就緒，等待和完成。當(dāng)系統(tǒng)不能滿足進程的資源請求時，進程出于等待狀態(tài)。資源需求總量表示進程運行過程中對資源的總的需求量。已占資源量表示進程目前已經(jīng)得到但還為歸還的資源量。因此，進程在以后還需要的剩余資源量等于資源需要總量減去已占資源量。陷入每個進程的資源需求總量不應(yīng)超過系統(tǒng)擁有的資源總量。
2、銀行家算法分配資源的原則是：當(dāng)某個進程提出資源請求時，假定先分配資源給它，然后查找各進程的剩余請求，檢查系統(tǒng)的剩余資源量是否由于進程的分配而導(dǎo)致系統(tǒng)死鎖。若能，則讓進程等待，否則，讓進程的假分配變?yōu)檎娣峙洹?/p>
(1)查找各進程的剩余請求，檢查系統(tǒng)的剩余資源量是否能滿足其中一進程，如果能，則轉(zhuǎn)B)。
(2)將資源分配給所選的進程，這樣，該進程已獲得資源最大請求，最終能運行完成。標(biāo)記這個進程為終止進程，并將其占有的全部資源歸還給系統(tǒng)。
重復(fù)第(1)步(2)步，直到所有進程都標(biāo)記為終止進程，或知道一個死鎖發(fā)生。若所有進程都標(biāo)記為終止進程，則系統(tǒng)的初始狀態(tài)是安全的，否則為不安全的。若安全，則正式將資源分配給它，否則，假定的分配作廢，讓其等待。
二、系統(tǒng)結(jié)構(gòu)設(shè)計
1、設(shè)計分析
當(dāng)某個進程對某類資源提出請求時，假定先分配資源給它，然后查找各進程的剩余請求，檢查系統(tǒng)的剩余資源量是否由于進程的分配而導(dǎo)致系統(tǒng)死鎖。若能，則讓進程等待，否則，讓進程的假分配變?yōu)檎娣峙洹?/p>
2、數(shù)據(jù)結(jié)構(gòu)
(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可利用資源的數(shù)目，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可利用資源的數(shù)目，其數(shù)值隨該類資源的分配和回首而動態(tài)的改變，如果Available=K，則代表Rj類資源K個。
(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。
(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。
(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程還需要各類資源數(shù)。
3、銀行家算法
設(shè)Requesti是進程Pi的請求向量，如果Requesti[j]=K，表示進程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按照以下步驟進行檢查：
A：如果Requesti[j]<=Need[i,j]，執(zhí)行B，否則認為出錯，因為它需要的資源數(shù)已經(jīng)超過它所宣布的最大值。
B: 如果Requesti[j]<=Available[j]，轉(zhuǎn)向步驟C，否則尚無足夠資源，Pi必須等待。
C:系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：
Available[j]:= Available[j]- Requesti[j];
Allocation[i,j]:=Allocation[i,j]+ Requesti[j];
Need[i,j]:= Need[i,j]- Requesti[j];
D:系統(tǒng)執(zhí)行安全性算法，檢查此次自奧運分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配，否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。
設(shè)置WORK[R]是系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目, 剛開始 系統(tǒng)可提供給進程繼續(xù)運行所需的j類資源數(shù)目,FINISH[i]檢查安全性是否通過。
4、程序流程圖
三、總結(jié)和體會
通過在劉玉宏老師的幫助下，我成功的完成了這次課程設(shè)計，雖然其中存在很多的不足。在這個銀行家算法課程設(shè)計中，利用二維數(shù)組作為基本的數(shù)據(jù)結(jié)構(gòu)用以存儲資源及進程信息，利用check()函數(shù)來判斷進程執(zhí)行是否安全，通過二維數(shù)組和distribute ()和restore()函數(shù)很好的解決了進程的分配及撤銷問題。
實驗中我使用當(dāng)一個進程不滿足安全狀態(tài)時緊接著查找它的下一個進程，若下一個進程滿足則給予分配資源，然后又返回從頭開始才找滿足安全狀態(tài)的進程，經(jīng)過劉老師的課堂講解我知道還可以按照進程的編號從小到大一次下循環(huán)查找，直到進程執(zhí)行完畢。
不同的算法可以實現(xiàn)相同的功能，這是我從本次實驗中深深體會到的，因而在今后的學(xué)習(xí)中遇到問題我會嘗試著用的不同的方法來解決，有時候換個角度可以很方便的解決問題。
附：計算機操作系統(tǒng)的銀行家算法主要清單
#include <string.h>
#include <iostream.h>
#define FALSE 0
#define TRUE 1
#define W 10
#define R 10
int M ; //總進程數(shù)
int N ; //資源種類
int All[W];//各種資源的數(shù)目總和
int Max[W][R]; //M個進程對N類資源最大資源需求量
int Available[R]; //系統(tǒng)可用資源數(shù)
int Allocation[W][R]; //M個進程已經(jīng)得到N類資源的資源量
int Need[W][R]; //M個進程還需要N類資源的資源量
int Request[R]; //請求資源個數(shù)
void output() //輸出資源分配情況
{
int i,j;
cout<<endl<<"*************************"<<endl;
cout<<"各種資源的總數(shù)量:"<<endl;
for (j=0;j<N;j++)
cout<<" 資源"<<j<<": "<<All[j]<<endl;
cout<<endl;
cout<<"*************************"<<endl;
cout<<"目前各種資源可利用的數(shù)量為:"<<endl;
for (j=0;j<N;j++)
cout<<" 資源"<<j<<": "<<Available[j]<<endl;
cout<<endl<<endl;
cout<<"*************************"<<endl;
cout<<"各進程還需要的資源數(shù)量:"<<endl;
for (j=0;j<N;j++)
{ cout<<" 資源"<<j<<" "; }
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"進程"<<i<<": ";
for (j=0;j<N;j++)
cout<<Need[i][j]<<" ";;
cout<<endl;
}
cout<<endl;
cout<<"**************************"<<endl;
cout<<"各進程已經(jīng)分配得到的資源量: "<<endl<<endl;
for (j=0;j<N;j++)
{ cout<<" 資源"<<j<<" "; }
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"進程"<<i<<": ";
for (j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
void distribute(int k) ///////////////////分配資源
{
int j;
for (j=0;j<N;j++)
{
Available[j]=Available[j]-Request[j];
Allocation[k][j]=Allocation[k][j]+Request[j];
Need[k][j]=Need[k][j]-Request[j];//第k個進程對第j中資源還需要的資源量
}
}
void restore(int k) //如果分配失敗，則恢復(fù)原來的資源分配狀態(tài)
{
int j;
for (j=0;j<N;j++)
{
Available[j]=Available[j]+Request[j];
Allocation[k][j]=Allocation[k][j]-Request[j];
Need[k][j]=Need[k][j]+Request[j];
}
}
int check() //檢查安全性
{
int WORK[R],FINISH[W];//WORK[R]是系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目
int i,j;
for(j=0;j<N;j++) WORK[j]=Available[j];//剛開始 系統(tǒng)可提供給進程繼續(xù)運行所需的j類資源數(shù)目 等于j類可用資源數(shù)目
for(i=0;i<M;i++) FINISH[i]=FALSE;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(FINISH[i]==FALSE&&Need[i][j]<=WORK[j])
{
WORK[j]=WORK[i]+Allocation[i][j];
}
}
FINISH[i]=TRUE;
}
for(i=0;i<M;i++)
{
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 系統(tǒng)不安全! 本次資源申請不成功!!!"<<endl;
cout<<endl;
return 1;
}
else
{
cout<<endl;
cout<<" 經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。"<<endl;
cout<<endl;
}
}
return 0;
}
void bank() //銀行家算法
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
cout<<"***********************************"<<endl;
cout<<endl<<" 請輸入需申請資源的進程號:";
cin>>i;
if(i<0||i>=M) cout<<" 輸入的進程號不存在，重新輸入!"<<endl;
}
for (j=0;j<N;j++)
{
cout<<" 資源"<<j<<": ";
cin>>Request[j];
if(Request[j]>Need[i][j]) //若請求的資源數(shù)大于進程還需要i類資源的資源量j
{
cout<<endl<<" 進程"<<i<<"申請的資源數(shù)大于進程"<<i<<"還需要"<<j<<"類資源的數(shù)量!";
cout<<" 若繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!"<<endl;
flag='N';
break;
}
else
{
if(Request[j]>Available[j]) //若請求的資源數(shù)大于可用資源數(shù)
{
cout<<endl<<" 進程"<<i<<"申請的資源數(shù)大于系統(tǒng)可用"<<j<<"類資源的數(shù)量!";
cout<<" 若繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!"<<endl;
flag='N';
break;
}
}
}
if(flag=='Y'||flag=='y')
{
distribute(i); //調(diào)用change(i)函數(shù)，改變資源數(shù)
if(check()) //若系統(tǒng)安全
{
restore(i); //調(diào)用restore(i)函數(shù)，恢復(fù)資源數(shù)
output(); //輸出資源分配情況
}
else //若系統(tǒng)不安全
output(); //輸出資源分配情況
}
else //若flag=N||flag=n
cout<<endl;
cout<<" 是否繼續(xù)銀行家算法演示,按'Y'或'y'鍵繼續(xù),按'N'或'n'鍵退出演示: ";
cin>>flag;
}
}
void version()
{
cout<<endl;
cout<<"\t*************************"<<endl;
cout<<"\t* *"<<endl;
cout<<"\t* 銀 行 家 算 法 *"<<endl;
cout<<"\t* *"<<endl;
cout<<"\t*************************"<<endl;
}
void main() //主函數(shù)
{
int i=0,j=0,p;
version();
cout<<endl<<"請輸入總進程數(shù):";
cin>>M;
cout<<endl<<"***************************"<<endl;
cout<<"請輸入總資源種類:";
cin>>N;
cout<<endl<<"***************************"<<endl;
cout<<"請輸入各類資源總數(shù):";
for(i=0;i<N;i++)
cin>>All[i];
cout<<endl<<"***************************"<<endl;
cout<<"輸入各進程所需要的各類資源的最大數(shù)量:"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>Max[i][j];
if (Max[i][j]>All[j])
cout<<endl<<"占有資源超過了聲明的該資源總數(shù),請重新輸入"<<endl;
}while (Max[i][j]>All[j]);
}
}
cout<<endl<<"********************************"<<endl;
cout<<"輸入各進程已經(jīng)分配的各類資源的數(shù)量:"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>Allocation[i][j];
if (Allocation[i][j]>Max[i][j])
cout<<endl<<"占有資源超過了聲明的最大資源,請重新輸入"<<endl;
}while (Allocation[i][j]>Max[i][j]);
}
}
for (j=0;j<N;j++) //初始化資源數(shù)量
{
p=All[j];
for (i=0;i<M;i++)
{
p=p-Allocation[i][j];//減去已經(jīng)被占據(jù)的資源
Available[j]=p;
if(Available[j]<0)
Available[j]=0;
}
}
for (i=0;i<M;i++)
for(j=0;j<N;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
output();
bank();
}