操作系統(tǒng)實(shí)驗(yàn)之銀行家算法
操作系統(tǒng)實(shí)驗(yàn)之銀行家算法
操作系統(tǒng)實(shí)驗(yàn)中的銀行家算法復(fù)雜難懂,那么我們究竟要怎么去理解呢?下面由學(xué)習(xí)啦小編為大家整理了操作系統(tǒng)實(shí)驗(yàn)銀行家算法的相關(guān)知識,希望大家喜歡!
操作系統(tǒng)實(shí)驗(yàn)——銀行家算法
一、實(shí)驗(yàn)?zāi)康?/p>
1、 理解銀行家算法。
2、 掌握進(jìn)程安全性檢查的方法與資源分配的方法。
二、實(shí)驗(yàn)內(nèi)容與基本要求
編制模擬銀行家算法的程序,并以下面給出的例子驗(yàn)證所編寫的程序的正確性。
進(jìn)程 | 已占資源 | 最大需求數(shù) |
---|---|---|
資源種類 | A B C D | A B C D |
P0 | 0 0 1 2 | 0 0 1 2 |
P1 | 1 0 0 0 | 1 7 5 0 |
P2 | 1 3 5 4 | 2 3 5 6 |
P3 | 0 6 3 2 | 0 6 5 2 |
P4 | 0 0 1 4 | 0 6 5 6 |
現(xiàn)在系統(tǒng)中A、B、C、D 4類資源分別還剩1、5、2、0個,請按銀行家算法回答:
1、 現(xiàn)在系統(tǒng)是否處于安全狀態(tài)?
2、 如果現(xiàn)在進(jìn)程P1提出需要(0、4、2、0)個資源的請求,系統(tǒng)能否滿足它的請求?
三、實(shí)驗(yàn)報(bào)告內(nèi)容
1、 銀行家算法和安全性檢查算法原理
銀行家算法:
銀行家算法最初級原為銀行系統(tǒng)設(shè)計(jì),以確保銀行在發(fā)放現(xiàn)金貸款時,不會發(fā)生不能滿足所有客戶需要的情況。在OS設(shè)計(jì)中,也可以用它來避免死鎖。
為實(shí)現(xiàn)銀行家算法,每個新進(jìn)程在進(jìn)入系統(tǒng)時它必須申明在運(yùn)行過程中,可能需要的每種資源類型的最大單元數(shù)目,其數(shù)目不應(yīng)超過系統(tǒng)所擁有的資源總量。當(dāng)某一進(jìn)程請求時,系統(tǒng)會自動判斷請求量是否小于進(jìn)程最大所需,同時判斷請求量是否小于當(dāng)前系統(tǒng)資源剩余量。若兩項(xiàng)均滿足,則系統(tǒng)試分配資源并執(zhí)行安全性檢查算法。
安全性檢查算法 :
安全性檢查算法用于檢查系統(tǒng)進(jìn)行資源分配后是否安全,若安全系統(tǒng)才可以執(zhí)行此次分配;若不安全,則系統(tǒng)不執(zhí)行此次分配。
安全性檢查算法原理為:在系統(tǒng)試分配資源后,算法從現(xiàn)有進(jìn)程列表尋找出一個可執(zhí)行的進(jìn)程進(jìn)行執(zhí)行,執(zhí)行完成后回收進(jìn)程占用資源;進(jìn)而尋找下一個可執(zhí)行進(jìn)程。當(dāng)進(jìn)程需求量大于系統(tǒng)可分配量時,進(jìn)程無法執(zhí)行。當(dāng)所有進(jìn)程均可執(zhí)行,則產(chǎn)生一個安全執(zhí)行序列,系統(tǒng)資源分配成功。若進(jìn)程無法全部執(zhí)行,即無法找到一條安全序列,則說明系統(tǒng)在分配資源后會不安全,所以此次分配失敗。
2、 程序流程圖
3、 程序及注釋
#include
//////////////////////////////////////////////////////////////////////////
//全局變量定義
int Available[100]; //可利用資源數(shù)組
int Max[50][100]; //最大需求矩陣
int Allocation[50][100]; //分配矩陣
int Need[50][100]; //需求矩陣
int Request[50][100]; //M個進(jìn)程還需要N類資源的資源量
int Finish[50];
int p[50];
int m,n; //M個進(jìn)程,N類資源
/////////////////////////////////////////////////////////////////////////
//安全性算法
int Safe()
{
int i,j,l=0;
int Work[100]; //可利用資源數(shù)組
for (i=0;i
Work[i]=Available[i];
for (i=0;i
Finish[i]=0;
for (i=0;i
{
if (Finish[i]==1)
continue;
else
{
for (j=0;j
{
if (Need[i][j]>Work[j])
break;
}
if (j==n)
{
Finish[i]=1;
for(int k=0;k
Work[k]+=Allocation[i][k];
p[l++]=i;
i=-1;
}
else continue;
}
if (l==m)
{
cout<<"系統(tǒng)是安全的"<<'\n';
cout<<"系統(tǒng)安全序列是:\n";
for (i=0;i
{
cout<
if (i!=l-1)
cout<<"-->";
}
cout<<'\n';
return 1;
}
}
}
/////////////////////////////////////////////////////////////////////////////////
//銀行家算法
int main()
{
int i,j,mi;
cout<<"輸入進(jìn)程的數(shù)目:\n";
cin>>m;
cout<<"輸入資源的種類:\n";
cin>>n;
cout<<"輸入每個進(jìn)程最多所需的各類資源數(shù),按照"<
for (i=0;i
for(j=0;j
cin>>Max[i][j];
cout<<"輸入每個進(jìn)程已經(jīng)分配的各類資源數(shù),按照"<
for (i=0;i
{
for(j=0;j
{
cin>>Allocation[i][j];
Need[i][j]=Max[i][j]-Allocation[i][j];
if (Need[i][j]<0)
{
cout<<"你輸入的第"<
j--;
continue;
}
}
}
cout<<"請輸入各個資源現(xiàn)有的數(shù)目:\n";
for (i=0;i
cin>>Available[i];
Safe();
while (1)
{
cout<<"輸入要申請的資源的進(jìn)程號:(第一個進(jìn)程號為0,第二個進(jìn)程號為1,依此類推)\n";
cin>>mi;
cout<<"輸入進(jìn)程所請求的各個資源的數(shù)量\n";
for (i=0;i
cin>>Request[mi][i];
for (i=0;i
{
if (Request[mi][i]>Need[mi][i])
{
cout<<"所請求資源數(shù)超過進(jìn)程的需求量!\n";
return 0;
}
if (Request[mi][i]>Available[i])
{
cout<<"所請求資源數(shù)超過系統(tǒng)所有的資源數(shù)!\n";
return 0;
}
}
for (i=0;i
{
Available[i]-=Request[mi][i];
Allocation[mi][i]+=Request[mi][i];
Need[mi][i]-=Request[mi][i];
}
if (Safe())
cout<<"同意分配請求\n";
else
{
cout<<"SORRY╮(╯▽╰)╭……你的請求被拒絕…\n";
for (i=0;i
{
Available[i]+=Request[mi][i];
Allocation[mi][i]-=Request[mi][i];
Need[mi][i]+=Request[mi][i];
}
}
for (i=0;i
Finish[i]=0;
char Flag; //標(biāo)志位
cout<<"是否再次請求分配?是請按Y/y,否請按N/n";
while (1)
{
cin>>Flag;
if (Flag=='Y'||Flag=='y'||Flag=='N'||Flag=='n')
break;
else
{
cout<<"請按要求重新輸入:\n";
continue;
}
}
if (Flag=='Y'||Flag=='y')
continue;
else break;
}
}
4、 運(yùn)行結(jié)果以及結(jié)論
圖示為題目所給定的條件下的程序運(yùn)行結(jié)果。可看出在現(xiàn)有分配情況下,該系統(tǒng)安全。
下圖為,P1提出請求后,程序的運(yùn)行結(jié)果,可知,系統(tǒng)仍然安全,所以系統(tǒng)可以滿足請求。