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