第一篇：操作系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告-用C++實(shí)現(xiàn)銀行家算法
操 作 系 統(tǒng)
實(shí) 驗(yàn) 報(bào) 告
(2)學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級：計(jì)091 學(xué)號：姓名： 時(shí)間：2011/12/30
目 錄
1.實(shí)驗(yàn)名稱……………………………………………………3 2.實(shí)驗(yàn)?zāi)康摹? 3.實(shí)驗(yàn)內(nèi)容……………………………………………………3 4.實(shí)驗(yàn)要求……………………………………………………3 5.實(shí)驗(yàn)原理……………………………………………………3 6.實(shí)驗(yàn)環(huán)境……………………………………………………4 7.實(shí)驗(yàn)設(shè)計(jì)……………………………………………………4 7.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)……………………………………………………………………4 7.2算法設(shè)計(jì)…………………………………………………………………………6 7.3功能模塊設(shè)計(jì)……………………………………………………………………7 8.實(shí)驗(yàn)運(yùn)行結(jié)果………………………………………………8 9.實(shí)驗(yàn)心得……………………………………………………9
附錄：源代碼（部分）…………………………………………………………………9
一、實(shí)驗(yàn)名稱：
用C++實(shí)現(xiàn)銀行家算法
二、實(shí)驗(yàn)?zāi)康模?/p>
通過自己編程來實(shí)現(xiàn)銀行家算法，進(jìn)一步理解銀行家算法的概念及含義，提高對銀行家算法的認(rèn)識，同時(shí)提高自己的動手實(shí)踐能力。
各種死鎖防止方法能夠阻止發(fā)生死鎖，但必然會降低系統(tǒng)的并發(fā)性并導(dǎo)致低效的資源利用率。死鎖避免卻與此相反，通過合適的資源分配算法確保不會出現(xiàn)進(jìn)程循環(huán)等待鏈，從而避免死鎖。本實(shí)驗(yàn)旨在了解死鎖產(chǎn)生的條件和原因，并采用銀行家算法有效地防止死鎖的發(fā)生。
三、實(shí)驗(yàn)內(nèi)容：
利用C++,實(shí)現(xiàn)銀行家算法
四、實(shí)驗(yàn)要求：
1.完成銀行家算法的設(shè)計(jì)
2.設(shè)計(jì)有n個(gè)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)，進(jìn)程可動態(tài)的申請和釋放資源，系統(tǒng)按各進(jìn)程的申請動態(tài)的分配資源。
五、實(shí)驗(yàn)原理：
系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請求后，先把資源試探性的分配給它。之后，系統(tǒng)將剩下的可用資源和進(jìn)程集合中的其他進(jìn)程還需要的資源數(shù)作比較，找出剩余資源能夠滿足的最大需求量的進(jìn)程，從而保證進(jìn)程運(yùn)行完畢并歸還全部資源。這時(shí)，把這個(gè)進(jìn)程從進(jìn)程集合中刪除，歸還其所占用的所有資源，系統(tǒng)的剩余資源則更多，反復(fù)執(zhí)行上述步驟。最后，檢查進(jìn)程集合，若為空則表明本次申請可行，系統(tǒng)處于安全狀態(tài)，可以真正執(zhí)行本次分配，否則，本次資源分配暫不實(shí)施，讓申請資源的進(jìn)程等待。
銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實(shí)現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(j < i)當(dāng)前占有資源量之和。
安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。
不安全狀態(tài)：不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。
我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。
為保證資金的安全，銀行家規(guī)定：
(1)當(dāng)一個(gè)顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客；
(2)顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；
(3)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí)，對顧客的貸款可推遲支付，但總能使顧客在有限的時(shí)間里得到貸款；
(4)當(dāng)顧客得到所需的全部資金后，一定能在有限的時(shí)間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時(shí)，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。
六、實(shí)驗(yàn)環(huán)境：
Win-7系統(tǒng)
Visual C++ 6.0
七、實(shí)驗(yàn)設(shè)計(jì)：
1.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 定義結(jié)構(gòu)體：
struct Process//進(jìn)程屬性構(gòu)成 { Source claim;//進(jìn)程最大需求量
Source allocation;//進(jìn)程占有量
Source claim_allocation;//進(jìn)程需求量
Source currentAvail;//進(jìn)程可獲得量 };
定義類對象：
class Source //資源的基本構(gòu)成以及功能 {
private: public: int R1;//定義三類類資源
int R2;int R3;
Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;}
Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;}
void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//設(shè)置各類資源
{ R1=r1;R2=r2;R3=r3;}
void add(Source s)//加法
{ R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;}
void sub(Source s)//減法
{ R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;}
bool lower(Source s)//比較
{
if(R1 > s.R1)return false;
if(R2 > s.R2)return false;
if(R3 > s.R3)return false;
return true;} };
class Data//封裝所有數(shù)據(jù) { public: Process *p;//進(jìn)程指針
Source sum;//總資源量
Source available;//可獲得量
Source ask;//請求量
int pLength;//進(jìn)程個(gè)數(shù)
int * ruler;//邏輯尺
void clearProcess()//進(jìn)程currentAvail清零
{
for(int i=0;i
{ p[i].currentAvail.setSource(0, 0, 0);} } };
class DataInit//封裝初始化數(shù)據(jù)函數(shù)類 { private: public: DataInit()//構(gòu)造函數(shù)
{ }
void initLength(Data *db)//設(shè)置進(jìn)程個(gè)數(shù)
{
int n;
cout<<“輸入進(jìn)程數(shù): ”;
cin>>n;
db->pLength = n;
db->p = new Process[n];
if(!db->p)
{cout<<“error!no enough memory space！”;return;}
db->ruler = new int[n];
if(!db->ruler)
{cout<<“error!no enough memory space！”;return;} }
2.算法設(shè)計(jì)
class FindSafeList//尋找安全序列 { private: public: FindSafeList()//構(gòu)造函數(shù)
{}
bool checkList(Data *db)//檢查一個(gè)序列安全性
{
int i=0;//i用于循環(huán)
db->p[db->ruler[i]].currentAvail.add(db->available);//將當(dāng)前系統(tǒng)可用資源量賦給該序列的第一個(gè)進(jìn)程
if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回false
{return false;}
for(i=1;i< db->pLength;i++)
{
//當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個(gè)進(jìn)程的未釋放資源前可獲得資源量currentAvail
db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail);
//當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個(gè)進(jìn)程的釋放的資源量
db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation);
//若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回false
if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))
{ return false;}
//若當(dāng)前進(jìn)程currentAvail大于該進(jìn)程總資源量，返回false
if(!db->p[db->ruler[i]].currentAvail.lower(db->sum))
{ return false;}
}
return true;//該序列進(jìn)程安全。返回true
}
bool exsitSafeList(Data *db)//判斷是否存在安全序列
{
int i = 0;
for(i = 0;i < db->pLength;i++)//設(shè)置邏輯尺的刻度值
{ db->ruler[i] = i;}
while(1)
//該循環(huán)將檢測邏輯尺刻度值的全排列
{
if(checkList(db))
//找到一個(gè)安全序列，返回true
{ return true;}
db->clearProcess();//將所有進(jìn)程的currentAvail清零
if(!next_permutation(db->ruler,db->ruler+db->pLength))
//所有排列完畢后退出生成排列庫函數(shù)的調(diào)用
{ return false;
}
}
return false;}
int findSafeList(Data *db, int i=0)//尋找安全序列
{
//請求值大于系統(tǒng)當(dāng)前可用資源值，返回0
if(!db->ask.lower(db->available))
{ return 0;}
//請求值大于當(dāng)前進(jìn)程需求資源值，返回1
if(!db->ask.lower(db->p[i].claim_allocation))
{ return 1;}
Source s(db->p[i].allocation);//根據(jù)請求，分配資源值
db->available.sub(db->ask);
db->p[i].allocation.add(db->ask);
db->p[i].claim_allocation.sub(db->ask);
if(!exsitSafeList(db))//判斷是否存在安全序列
{
db->available.add(db->ask);
//不存在安全序列，回滾，恢復(fù)分配前狀態(tài)，并返回2
db->p[i].allocation.sub(db->ask);
db->p[i].claim_allocation.add(db->ask);
return 2;
}
db->ask.setSource(0,0,0);//找到安全序列，將請求資源置零，返回3
return 3;}
};3.功能模塊設(shè)計(jì)
class Data//封裝所有數(shù)據(jù)
class DataInit//封裝初始化數(shù)據(jù)函數(shù)類 class Display//封裝顯示方法
class FindSafeList//尋找安全序列 struct Process//進(jìn)程屬性構(gòu)成
void main()//主函數(shù)
八、實(shí)驗(yàn)運(yùn)行結(jié)果：
輸入進(jìn)程數(shù)，及相關(guān)資源數(shù)量分配
選擇算法完成的操作：1 查看進(jìn)程情況 請求分配
2.1分配失敗
2.2 分配成功
2.3 繼續(xù)分配失敗，退出
九、實(shí)驗(yàn)心得：
通過此次實(shí)驗(yàn)，我能夠更加深入的理解銀行家算法的執(zhí)行過程，也懂得用銀行家算法去防止發(fā)生死鎖，有效地解決了資源利用率低的問題，保證了系統(tǒng)的安全性。
當(dāng)然在實(shí)驗(yàn)過程中，我也遇到了一些困難，但是我通過及時(shí)請教同學(xué)，查詢相關(guān)資料，及時(shí)解決了問題，但仍有不足之處，我將會在今后學(xué)習(xí)中更加努力。
附錄：源代碼（部分）
#include
class Source //資源的基本構(gòu)成以及功能 {
private: public: int R1;//定義三類類資源
int R2;int R3;
Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;}
Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;}
void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//設(shè)置各類資源
{ R1=r1;R2=r2;R3=r3;}
void add(Source s)//加法
{ R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;}
void sub(Source s)//減法
{ R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;}
bool lower(Source s)//比較
{
if(R1 > s.R1)return false;
if(R2 > s.R2)return false;
if(R3 > s.R3)return false;
return true;}
};
struct Process//進(jìn)程屬性構(gòu)成 { Source claim;//進(jìn)程最大需求量
Source allocation;//進(jìn)程占有量
Source claim_allocation;//進(jìn)程需求量
Source currentAvail;//進(jìn)程可獲得量 };
class Data//封裝所有數(shù)據(jù) { public: Process *p;//進(jìn)程指針
Source sum;//總資源量
Source available;//可獲得量
Source ask;//請求量
int pLength;//進(jìn)程個(gè)數(shù)
int * ruler;//邏輯尺
void clearProcess()//進(jìn)程currentAvail清零
{
for(int i=0;i
{ p[i].currentAvail.setSource(0, 0, 0);} } };
class DataInit//封裝初始化數(shù)據(jù)函數(shù)類 { private: public: DataInit()//構(gòu)造函數(shù)
{ }
void initLength(Data *db)//設(shè)置進(jìn)程個(gè)數(shù)
{
int n;
cout<<“輸入進(jìn)程數(shù): ”;
cin>>n;
db->pLength = n;
db->p = new Process[n];
if(!db->p)
{cout<<“error!no enough memory space！”;return;}
db->ruler = new int[n];
if(!db->ruler){cout<<“error!no enough memory space！”;return;} }
void setAsk(Data *db)//設(shè)置請求資源量 { int r1,r2,r3;r1=0;r2=0;r3=0;
db->ask.setSource(r1,r2,r3);}
void initSum(Data *db)//設(shè)置總資源量
{ int r1,r2,r3;cout<<“Available(R1,R2,R3): ”;cin>>r1>>r2>>r3;db->sum.setSource(r1,r2,r3);}
void initAvail(Data *db)//設(shè)置可獲得量 { int r1,r2,r3;cout<<“輸入初始分配 Allocation:n”;cout<<“available[R1,R2,R3]:n ”;
cin>>r1>>r2>>r3;
db->available.setSource(r1,r2,r3);}
void initProcess(Data *db)//設(shè)置各進(jìn)程屬性值 { int r1,r2,r3;cout<<“輸入t0時(shí)分配 Allocation:n”;for(int i=0;i
cout<<'p'< cin>>r1>>r2>>r3; db->p[i].allocation.setSource(r1,r2,r3); cout<<'p'< cin>>r1>>r2>>r3; db->p[i].claim.setSource(r1,r2,r3); r1=db->p[i].claim.R1-db->p[i].claim.R1;//設(shè)置進(jìn)程p[i] 的 claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource(r1, r2, r3); } } }; class Display//封裝顯示方法 { private: public: Display()//構(gòu)造函數(shù) { } void displaySource(Source s)//設(shè)置基本資源顯示方式 {cout< displayAvailable(Source s)//顯示可獲得資源量 {displaySource(s);} void displayProcess(Process *p,int length)//顯示進(jìn)程基本信息 { for(int i=0;i { cout<<“ p”< displaySource(p[i].claim); cout<<“tt”; displaySource(p[i].allocation); cout< } cout< void displaySafeList(Data *db)//顯示安全序列 { for(int i=0;i { cout<<“ p”< ”; displaySource(db->p[db->ruler[i]].currentAvail); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim); cout<<“ ”; displaySource(db->p[db->ruler[i]].allocation); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim_allocation); cout<<“ true”; cout< } } void displayAskResult(Data *db,int n)//顯示請求資源結(jié)果 { if(n==0) {cout<<“不分配，請求量大于當(dāng)前可獲得量!n”;return;} if(n==1) {cout<<“不分配，請求量大于當(dāng)前可獲得量!n”;return;} if(n==2) {cout<<“不分配，找不到安全序列!n”;return;} if(n==3) { cout<<“存在安全序列:”; for(int i=0;i {cout< cout< char c='N'; cout<<“查看安全序列詳情?(Y/N)”; cin>>c; if(c=='Y'||c=='y') { cout<<“ 進(jìn)程 currentavail claim allocation claim-allocation possiblen”; displaySafeList(db); } return; } } }; class FindSafeList//尋找安全序列 { private: public: FindSafeList()//構(gòu)造函數(shù) {} bool checkList(Data *db)//檢查一個(gè)序列安全性 { int i=0;//i用于循環(huán) db->p[db->ruler[i]].currentAvail.add(db->available);//將當(dāng)前系統(tǒng)可用資源量 賦給該序列的第一個(gè)進(jìn)程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個(gè)進(jìn)程的未釋放資源前可獲得資源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個(gè)進(jìn)程的釋放的資源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若當(dāng)前進(jìn)程currentAvail大于該進(jìn)程總資源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//該序列進(jìn)程安全。返回true } bool exsitSafeList(Data *db)//判斷是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//設(shè)置邏輯尺的刻度值 { db->ruler[i] = i;} while(1) //該循環(huán)將檢測邏輯尺刻度值的全排列 { if(checkList(db)) //找到一個(gè)安全序列，返回true { return true;} db->clearProcess();//將所有進(jìn)程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完畢后退出生成排列庫函數(shù)的調(diào)用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//尋找安全序列 { //請求值大于系統(tǒng)當(dāng)前可用資源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //請求值大于當(dāng)前進(jìn)程需求資源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根據(jù)請求，分配資源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判斷是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滾，恢復(fù)分配前狀態(tài)，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，將請求資源置零，返回3 return 3;} }; void main(){ Data *db;db=new Data;if(!db){ cout<<“error!no enough memory space！”;return;} DataInit dataInit;dataInit.initLength(db);//設(shè)置進(jìn)程個(gè)數(shù) dataInit.initSum(db);//設(shè)置系統(tǒng)總資源量 dataInit.initAvail(db);//設(shè)置當(dāng)前系統(tǒng)可獲得資源量 dataInit.initProcess(db);//設(shè)置t0時(shí)刻進(jìn)程基本狀態(tài) Display display;FindSafeList findSafeList;int r1=0,r2=0,r3=0;int c;db->ask.setSource(r1,r2,r3);//設(shè)置請求資源為0，即無請求 c=findSafeList.findSafeList(db,0);//尋找安全序列，返回結(jié)果 if(c!=3){ cout<<“t0時(shí)刻的進(jìn)程組不存在安全序列!n”;return;} int choice=1;int pi; while(choice){ cout<<“n 選擇操作:n 查看進(jìn)程情況n 請求分配資源n 0 退出n ”; cin>>choice;switch(choice){ case 1: { } case 2: { } case 0: { default: { } } } cout<<“當(dāng)前資源量available[R1,R2,R3]:n ”;display.displayAvailable(db->available);cout< 實(shí)驗(yàn)四 死鎖 一、實(shí)驗(yàn)?zāi)康?/p> 當(dāng)系統(tǒng)的總資源數(shù)m小于或等于所有進(jìn)程對對資源的最大需求時(shí)，就可能產(chǎn)生 死鎖。死鎖會引起計(jì)算機(jī)系統(tǒng)的癱瘓。銀行家算法是在實(shí)現(xiàn)資源分配時(shí)避免死鎖的一個(gè)著名算法，該算法是在能確保系統(tǒng)處于安全狀態(tài)時(shí)才把資源分配給申請者。通過本實(shí)驗(yàn)使學(xué)生能進(jìn)一步理解死鎖的概念，并能選擇一個(gè)算法來避免死鎖。 二、實(shí)驗(yàn)題目 系統(tǒng)中有m個(gè)同類資源被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程對資源的最大需求數(shù)分別為S1, S2,…,Sn，且 Max(Si)<=m,(i=1,2,…n)。進(jìn)程可以動態(tài)地申請資源和釋放資源。編寫一個(gè)程序，現(xiàn)銀行家算法，當(dāng)系統(tǒng)將資源分配給某一進(jìn)程而不會死鎖時(shí)，就分配之。否則，推遲分配，并顯示適當(dāng)?shù)男畔ⅰ?/p> 三、數(shù)據(jù)結(jié)構(gòu) 主要數(shù)據(jù)結(jié)構(gòu): Struct aa { void Print();//用于打印輸出表格的函數(shù) void Input();//用于輸入的函數(shù) void tryfenpei(int i);//試分配函數(shù) void refenpei(int i);//恢復(fù)數(shù)據(jù)函數(shù) void checksafe(int s);//安全檢測函數(shù) }； 四、銀行家算法的流程圖 開始初始化資源類數(shù)c=3，進(jìn)程數(shù)t=5初始化Available[c]，Max[t][c]，Allocation[t][c]，Need[t][c]，Request[c]輸入進(jìn)程數(shù)iInt f=0f 五、源代碼 #include void Print();//用于打印輸出表格的函數(shù) void Input();//用于輸入的函數(shù) void tryfenpei(int i);//試分配函數(shù) void refenpei(int i);//恢復(fù)數(shù)據(jù)函數(shù) void checksafe(int s);//安全檢測函數(shù) //定義初始化數(shù)組 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用戶選擇的進(jìn)程號 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化數(shù)據(jù)如下：”< cout<<“試分配完成!”< cout<<“需要繼續(xù)實(shí)驗(yàn)嗎?（y-繼續(xù) n終止）”;} else if(ch=='N'||ch=='n'){ cout<<“感謝您的使用，祝您愉快!”< void Print(){ int i,j;cout<<“ 進(jìn)程個(gè)數(shù) ： ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全檢測函數(shù) void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三類資源A B C，一條進(jìn)程下面的安全性檢測只檢測了A類。如果A類通過了，那么還要判斷B類，C類。否則不用 { for(i=0;i } i=s;//s傳遞進(jìn)來賦給i，s是用戶輸入的進(jìn)程號（有主函數(shù)里的in傳遞進(jìn)來）while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、執(zhí)行結(jié)果： 七、實(shí)驗(yàn)總結(jié) 通過本次實(shí)驗(yàn)了解到用銀行家算法來預(yù)防死鎖是可靠的，但也是非常保守的，因?yàn)樗拗屏诉M(jìn)程對資源的存取，從而降低了進(jìn)程的并發(fā)運(yùn)行程度。死鎖檢測并不限制進(jìn)程對資源的申請，只要有，就分配，但這也可能造成死鎖。但由于死鎖并不是經(jīng)常發(fā)生的，故大大提高了系統(tǒng)運(yùn)行的效率。 總之，通過本實(shí)驗(yàn)，使我進(jìn)一步加深理解和掌握銀行家算法。 操作系統(tǒng)課程設(shè)計(jì) （銀行家算法的模擬實(shí)現(xiàn)） 一、設(shè)計(jì)目的 1、進(jìn)一步了解進(jìn)程的并發(fā)執(zhí)行。 2、加強(qiáng)對進(jìn)程死鎖的理解。 3、用銀行家算法完成死鎖檢測。 二、設(shè)計(jì)內(nèi)容 給出進(jìn)程需求矩陣C、資源向量R以及一個(gè)進(jìn)程的申請序列。使用進(jìn)程啟動拒絕和資源分配拒絕（銀行家算法）模擬該進(jìn)程組的執(zhí)行情況。 三、設(shè)計(jì)要求 1、初始狀態(tài)沒有進(jìn)程啟動。 2、計(jì)算每次進(jìn)程申請是否分配，如：計(jì)算出預(yù)分配后的狀態(tài)情況（安全狀態(tài)、不安全狀態(tài)），如果是安全狀態(tài)，輸出安全序列。 3、每次進(jìn)程申請被允許后，輸出資源分配矩陣A和可用資源向量V。 4、每次申請情況應(yīng)可單步查看，如：輸入一個(gè)空格，繼續(xù)下個(gè)申請。 四、算法原理 1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)、可利用資源向量Available，這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每個(gè)元素代表一類可利用資源的數(shù)目，其初始值是系統(tǒng)中所配置的該類全部資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 （2）、最大需求矩陣Max，這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 （3）、分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已經(jīng)分得Rj類資源的數(shù)目為K。 （4）、需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每個(gè)進(jìn)程尚需要的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣間存在以下關(guān)系： Need[i,j]=Max[i,j]-Allocation[i,j] 2、銀行家算法應(yīng)用 模擬實(shí)現(xiàn)Dijkstra的銀行家算法以避免死鎖的出現(xiàn)，分兩部分組成：一是銀行家算法（掃描）；二是安全性算法。 （1）銀行家算法（掃描） 設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個(gè)Ri類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： ①如果Requesti[j]<=Need[i,j]，便轉(zhuǎn)向步驟②；否則認(rèn)為出錯(cuò)，因?yàn)樗璧馁Y源數(shù)已經(jīng)超過了它所宣布的最大值。 ②如果Requesti[j]<=Allocation[i,j]，便轉(zhuǎn)向步驟③；否則表示尚無足夠資源，Pi需等待。 ③系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。 Available[j]=Available-Requesti[j]； Allocation[i,j]=Allocation[i,j]+Requesti[j]； Need[i,j]=Need[i,j]-Requesti[j]； ④系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，已完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來資源的分配狀態(tài)，讓進(jìn)程Pi等待。 （2）安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： ①設(shè)置兩個(gè)向量：一個(gè)是工作向量Work；它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源的數(shù)目，它含有m個(gè)元素，在執(zhí)行安全性算法開始時(shí)，work=Available；另一個(gè)是Finish；它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]=true； ②從進(jìn)程集合中找到能滿足下述條件的進(jìn)程： 一是Finish[i]==false；二是Need[i,j]<=Work[j]；若找到，執(zhí)行步驟③，否則，執(zhí)行步驟④； ③當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Work[j]=Work[j]+Allocation[i,j]； Finish[i]=true； go to step②； ④如果所有進(jìn)程的 Finish[i]==true都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。 五、設(shè)計(jì)思路 1、進(jìn)程一開始向系統(tǒng)提出最大需求量； 2、進(jìn)程每次提出新的需求（分期貸款）都統(tǒng)計(jì)是否超出它事先提出的最大需求量； 3、若正常，則判斷該進(jìn)程所需剩余量（包括本次申請）是否超出系統(tǒng)所掌握的剩余資源量，若不超出，則分配，否則等待。 六、程序運(yùn)行調(diào)試結(jié)果 1、程序初始化 2、檢測系統(tǒng)資源分配是否安全結(jié)果 七、小結(jié) “銀行家算法的模擬實(shí)現(xiàn)”是本學(xué)期操作系統(tǒng)課程的課程設(shè)計(jì)。在設(shè)計(jì)此程序的過程中我們遇到過許多問題也學(xué)到了很多東西。通過這周的課程設(shè)計(jì)，我加深了對銀行家算法的理解，掌握了銀行家算法避免死鎖的過程和方法，理解了死鎖產(chǎn)生的原因和條件以及避免死鎖的方法。所編寫程序基本實(shí)現(xiàn)了銀行家算法的功能，并在其基礎(chǔ)上考慮了輸出顯示格式的美觀性，使界面盡可能友好。并且在編程時(shí)將主要的操作都封裝在函數(shù)中，這樣使程序可讀性增強(qiáng)，使程序更加清晰明了。在算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)上考慮了很長時(shí)間。在程序設(shè)計(jì)中先后參考了很多網(wǎng)絡(luò)資料也參考了一些別人寫的的程序綜合這些算法思想和自己的思路對程序做了很好的設(shè)計(jì)方式對一些算法的優(yōu)越性等也作了一些考慮。當(dāng)然，在編寫和調(diào)試過程中我遇到了許多的問題，通過網(wǎng)上查詢資料、翻閱課本、向同學(xué)請教、多次調(diào)試等方法逐漸解決了大部分問題。讓我收獲很多，相信在今后的生活中也有一定幫助。 附：程序源代碼： #include int no1;//進(jìn)程數(shù) int no2;//資源數(shù) int r;int allocation[m][m],need[m][m],available[m],max[m][m];char name1[m],name2[m];//定義全局變量 void main(){ void check();void print();int i,j,p=0,q=0;char c;int request[m],allocation1[m][m],need1[m][m],available1[m];printf(“**********************************************n”);printf(“* 銀行家算法的設(shè)計(jì)與實(shí)現(xiàn) *n”);printf(“**********************************************n”);printf(“請輸入進(jìn)程總數(shù):n”);scanf(“%d”,&no1);printf(“請輸入資源種類數(shù):n”);scanf(“%d”,&no2);printf(“請輸入Max矩陣:n”);for(i=0;i for(j=0;j scanf(“%d”,&max[i][j]);//輸入已知進(jìn)程最大資源需求量 printf(“請輸入Allocation矩陣:n”);for(i=0;i for(j=0;j scanf(“%d”,&allocation[i][j]);//輸入已知的進(jìn)程已分配的資源數(shù) for(i=0;i for(j=0;j need[i][j]=max[i][j]-allocation[i][j];//根據(jù)輸入的兩個(gè)數(shù)組計(jì)算出need矩陣的值 printf(“請輸入Available矩陣n”);for(i=0;i scanf(“%d”,&available[i]);//輸入已知的可用資源數(shù) print();//輸出已知條件 check();//檢測T0時(shí)刻已知條件的安全狀態(tài) if(r==1)//如果安全則執(zhí)行以下代碼 { do{ q=0;p=0;printf(“n請輸入請求資源的進(jìn)程號(0~4)：n”); for(j=0;j<=10;j++) { scanf(“%d”,&i); if(i>=no1) { printf(“輸入錯(cuò)誤，請重新輸入：n”); continue; } else break; } printf(“n請輸入該進(jìn)程所請求的資源數(shù)request[j]:n”); for(j=0;j scanf(“%d”,&request[j]); else //請求滿足條件 { for(j=0;j { available1[j]=available[j]; allocation1[i][j]=allocation[i][j]; need1[i][j]=need[i][j]; //保存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù) available[j]=available[j]-request[j]; allocation[i][j]+=request[j]; need[i][j]=need[i][j]-request[j];//系統(tǒng)嘗試把資源分配給請求的進(jìn)程 } print(); check();//檢測分配后的安全性 if(r==0)//如果分配后系統(tǒng)不安全 { for(j=0;j { available[j]=available1[j]; allocation[i][j]=allocation1[i][j]; need[i][j]=need1[i][j];//還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù) } printf(“返回分配前資源數(shù)n”); print(); } } }printf(“n你還要繼續(xù)分配嗎？Y or N ?n”); //判斷是否繼續(xù)進(jìn)行資源分配 for(j=0;j if(p) printf(“請求資源超過該進(jìn)程資源需求量，請求失?。”);else { for(j=0;j if(request[j]>available[j])q=1;//判斷請求是否超過可用資源數(shù) if(q) printf(“沒有做夠的資源分配，請求失?。”); c=getche(); }while(c=='y'||c=='Y');} } void check()//安全算法函數(shù) { int k,f,v=0,i,j;int work[m],a[m];bool finish[m];r=1;for(i=0;i finish[i]=false;// 初始化進(jìn)程均沒得到足夠資源數(shù)并完成for(i=0;i k=no1;do{ for(i=0;i { if(finish[i]==false) { f=1; for(j=0;j if(need[i][j]>work[j]) f=0; if(f==1)//找到還沒有完成且需求數(shù)小于可提供進(jìn)程繼續(xù)運(yùn)行的資源數(shù)的進(jìn)程 { finish[i]=true; a[v++]=i;//記錄安全序列號 for(j=0;j work[j]+=allocation[i][j];//釋放該進(jìn)程已分配的資源 } } } k--;//每完成一個(gè)進(jìn)程分配，未完成的進(jìn)程數(shù)就減1 }while(k>0);f=1;for(i=0;i if(finish[i]==false) { f=0; break; } } if(f==0)//若有進(jìn)程沒完成，則為不安全狀態(tài) { printf(“系統(tǒng)處在不安全狀態(tài)！”); r=0;} else { printf(“n系統(tǒng)當(dāng)前為安全狀態(tài)，安全序列為：n”); for(i=0;i printf(“p%d ”,a[i]);//輸出安全序列 } } void print()//輸出函數(shù) { int i,j;printf(“n”);printf(“*************此時(shí)刻資源分配情況*********************n”);printf(“進(jìn)程名/號 | Max | Allocation | Need |n”);for(i = 0;i < no1;i++) { printf(“ p%d/%d ”,i,i); for(j = 0;j < no2;j++){printf(“%d ”,max[i][j]);} for(j = 0;j < no2;j++) {printf(“ %d ”,allocation[i][j]);} for(j = 0;j < no2;j++) {printf(“ %d ”,need[i][j]);} printf(“n”); } printf(“n”); printf(“各類資源可利用的資源數(shù)為:”); for(j = 0;j < no2;j++) {printf(“ %d”,available[j]);} } printf(“n”); （程序結(jié)束） 操作系統(tǒng) 課程設(shè)計(jì)報(bào)告 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名 班級 學(xué)號 指導(dǎo)教師 完成日期 信息工程學(xué)院 題目： 銀行家算法的模擬實(shí)現(xiàn) 一、設(shè)計(jì)目的本課程設(shè)計(jì)是學(xué)習(xí)完“操作系統(tǒng)原理”課程后進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動手能力。 二、設(shè)計(jì)內(nèi)容 1）概述 用C或C++語言編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。 1.算法介紹：數(shù)據(jù)結(jié)構(gòu)： 1） 可利用資源向量 Available； 2） 最大需求矩陣Max； 3） 分配矩陣Allocation； 4） 需求矩陣Need 2.功能介紹 模擬實(shí)現(xiàn)Dijkstra的銀行家算法以避免死鎖的出現(xiàn)，分兩部分組成： 第一部分：銀行家算法（掃描）； 第二部分：安全性算法。 2）設(shè)計(jì)原理 一．銀行家算法的基本概念 1、死鎖概念。 在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)━━死鎖。所謂死鎖(Deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。 2、關(guān)于死鎖的一些結(jié)論： ? 參與死鎖的進(jìn)程最少是兩個(gè) ? （兩個(gè)以上進(jìn)程才會出現(xiàn)死鎖） ? 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源 ? 參與死鎖的所有進(jìn)程都在等待資源 ? 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集 注：如果死鎖發(fā)生，會浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。 3、資源分類。 永久性資源： 可以被多個(gè)進(jìn)程多次使用（可再用資源） l 可搶占資源 l 不可搶占資源 臨時(shí)性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源） “申請--分配--使用--釋放”模式 4、產(chǎn)生死鎖的四個(gè)必要條件：互斥使用（資源獨(dú)占）、不可強(qiáng)占（不可剝奪）、請求和保持（部分分配，占有申請）、循環(huán)等待。 1) 互斥使用（資源獨(dú)占） 一個(gè)資源每次只能給一個(gè)進(jìn)程使用。 2) 不可強(qiáng)占（不可剝奪） 資源申請者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放。 3) 請求和保持（部分分配，占有申請） 一個(gè)進(jìn)程在申請新的資源的同時(shí)保持對原有資源的占有（只有這樣才是動態(tài)申請，動態(tài)分配）。 4) 循環(huán)等待 存在一個(gè)進(jìn)程等待隊(duì)列 {P1,P2,…,Pn},其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路。 5、死鎖預(yù)防: 定義:在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。 ①破壞“不可剝奪”條件 在允許進(jìn)程動態(tài)申請資源前提下規(guī)定，一個(gè)進(jìn)程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請 ②破壞“請求和保持”條件。 要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分配。 ③破壞“循環(huán)等待”條件 采用資源有序分配法： 把系統(tǒng)中所有資源編號，進(jìn)程在申請資源時(shí)必須嚴(yán)格按資源編號的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。 6．安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)： 如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…Pn，則系統(tǒng)處于安全狀態(tài)。一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i)當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài) (安全狀態(tài)一定是沒有死鎖發(fā)生的) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。 二．銀行家算法 1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 1）可利用資源向量Available 它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 2）最大需求短陣Max 這是—個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Max(i，j)＝K，表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 3）分配短陣Allocation 這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每個(gè)進(jìn)程的資源數(shù)。如果Allocation(i,j)＝K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 4）需求矩陣Need 它是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)，如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源k個(gè)，方能完成其任務(wù)。 上述三個(gè)矩陣間存在下述關(guān)系： Need[i,j]=Max[i,j]-Allocation[i,j] 2、銀行家算法 設(shè)Requesti是進(jìn)程Pi的請求向量。如果Requesti[j]＝k，表示進(jìn)程只需要k個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： 1）如果 Requesti[j]<=Need[i,j]，則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 2）如果Requesti[j]<=Available[j]，則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。 3）系統(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]; 4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 3、安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： 1）設(shè)置兩個(gè)向量 ①、工作向量Work。它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目，它含有m個(gè)元素，執(zhí)行安全算法開始時(shí)，Work = Available。 ②、Finish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始時(shí)先做Finish[i]:=false ；當(dāng)有足夠資源分配給進(jìn)程時(shí)，令 Finish[i]:=true。 2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： ①、Finish[i]=false; ②、Need[i,j]<=Work[j];如找到，執(zhí)行步驟（3）；否則，執(zhí)行步驟（4）。 3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Work[j]:=Work[i]+Allocation[i,j]; Finish[i]:=true; goto step 2； 4）如果所有進(jìn)程的Finish[i]:=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 三．銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程：{P0，P1，P2，P3，P4}和三種類型的資源{A，B，C}，每一種資源的數(shù)量分別為10、5、7,在T0時(shí)刻的資源分配情況如圖1所示。 資源情況 進(jìn)程 Max Allocation Need Available A B C A B C A B C A B C P0 0 0 (2 0) P1 0 0 (3 0 2) (0 0) P2 0 0 0 0 P3 0 P4 0 0 圖1 T0時(shí)刻的資源分配表 (1)T0時(shí)刻的安全性：利用安全性算法對T0時(shí)刻的資源分配情況進(jìn)行分析(如圖2)可知，在T0時(shí)刻存在著一個(gè)安全序列｛P1，P3，P4，P2，P0｝，故系統(tǒng)是安全的。 資源情況 進(jìn)程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 true true true true true P3 0 P4 0 0 P2 0 0 0 P0 0 0 圖2 T0時(shí)刻的安全序列 (2)P1請求資源：P1發(fā)出請求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查： ①Request1(1,0,2)<=Need1(1,2,2) ②Request1(1,0,2)<=Available1(3,3,2) ③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成資源變化情況如圖1中的圓括號所示。 ④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如圖3所示。 資源情況 進(jìn)程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 0 0 true true true true true P3 0 P4 0 0 P0 0 0 P2 0 0 0 圖3 P1申請資源時(shí)的安全性檢查 由所進(jìn)行的安全性檢查得知，可以找到一個(gè)安全序列｛P1,P3,P4,P2,P0｝。因此系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。 (3)P4請求資源：P4發(fā)出請求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查： ①Request4(3,3,0)≤Need4(4,3,1); ②Request4(3,3,0)不小于等于Available(2,3,0),讓P4等待。 (4)P0請求資源：P0發(fā)出請求向量Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查。 ①Request0(0,2,0) ≤Need0(7,4,3); ②Request0(0,2,0) ≤Available(2,3,0); ③系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖4所示。 資源情況 進(jìn)程 Allocation Need Available A B C A B C A B C P0 0 0 0 P1 0 0 0 P2 0 0 0 P3 0 P4 0 0 圖4 為P0分配資源后的有關(guān)資源數(shù)據(jù) (5)進(jìn)行安全性檢查：可用資源Available(2,1,0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。 3）詳細(xì)設(shè)計(jì)及編碼 1）銀行家算法流程圖 2）程序源代碼 #include #include #include #include //定義全局變量 const int x=20,y=20; //常量，便于修改 int Available[x]; //各資源可利用的數(shù)量 int Allocation[y][y]; //各進(jìn)程當(dāng)前已分配的資源數(shù)量 int Max[y][y]; //各進(jìn)程對各類資源的最大需求數(shù) int Need[y][y]; //尚需多少資源 int Request[x]; //申請多少資源 int Work[x]; //工作向量，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)量 int Finish[y]; //表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，1為是 int p[y]; //存儲安全序列 int i,j; //i表示進(jìn)程，j表示資源 int n,m; //n為進(jìn)程i的數(shù)量,m為資源j種類數(shù) int l=0; //l用來記錄有幾個(gè)進(jìn)程是Finish[i]=1的，當(dāng)l=n是說明系統(tǒng)狀態(tài)是安全的int counter=0; //函數(shù)聲明 void chushihua(); //初始化函數(shù) void safe(); //安全性算法 void show(); //函數(shù)show,輸出當(dāng)前狀態(tài) void bank(); //銀行家算法 //void jieshu(); //結(jié)束函數(shù) void chushihua() { cout<<“輸入進(jìn)程的數(shù)量: “;//從此開始輸入有關(guān)數(shù)據(jù) cin>>n; cout<<“輸入資源種類數(shù): “; cin>>m; cout< 種): “< for (j=0; j j++) { cout<<“輸入資源 “< 可利用的數(shù)量Available[“< “; cin>>Available[j]; //輸入數(shù)字的過程...Work[j]=Available[j]; //初始化Work[j]，它的初始值就是當(dāng)前可用的資源數(shù) } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 輸入進(jìn)程 “< 當(dāng)前已分配的資源 “< 數(shù)量: “; cin>>Allocation[i][j]; } cout< Finish[i]=0;//初始化Finish[i] } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 輸入進(jìn)程 “< 對資源 “< “; cin>>Max[i][j]; if(Max[i][j]>=Allocation[i][j]) //若最大需求大于已分配，則計(jì)算需求量 Need[i][j] = Max[i][j]-Allocation[i][j]; else Need[i][j]=0;//Max小于已分配的時(shí)候，此類資源已足夠不需再申請 } cout< } cout< } //安全性算法函數(shù) void safe() { l=0; for (i=0; i { //i++ if (Finish[i]==0) { //逐個(gè)查找Finish[i]==0的進(jìn)程 條件一 counter=0; //記數(shù)器 for (j=0; j j++) { if (Work[j]>=Need[i][j]) counter=counter+1;//可用大于需求，記數(shù) } if(counter==m) //i進(jìn)程的每類資源都符合Work[j]>=Need[i][j] 條件二 { p[l]=i; //存儲安全序列 Finish[i]=1; //i進(jìn)程標(biāo)志為可分配 for (j=0; j Work[j]=Work[j]+Allocation[i][j]; //釋放資源 l=l+1; //記數(shù),現(xiàn)在有L個(gè)進(jìn)程是安全的，當(dāng)L=N時(shí)說明滿足安全序列 i= -1; //從第一個(gè)進(jìn)程開始繼續(xù)尋找滿足條件一二的進(jìn)程 } } } } //顯示當(dāng)前狀態(tài)函數(shù) void show() //函數(shù)show,輸出當(dāng)前資源分配情況 { int i,j; //局部變量 int All[y]; //各種資源的總數(shù)量 cout<<“當(dāng)前的狀態(tài)為：“< cout<<“各種資源的總數(shù)量:“< for (j=0;j { cout<<“ 資源“< “; All[j]=Available[j]; //總數(shù)量=可用的+已分配的for (i=0;i All[j]+=Allocation[i][j]; cout< “; } cout< for (j=0;j cout<<“ 資源“< “< “; cout< “< for (j=0;j cout<<＇＼t＇<<“資源“< cout< for(i=0;i { cout<<“進(jìn)程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } cout< for (j=0;j cout<<＇＼t＇<<“資源“< cout< for(i=0;i { cout<<“進(jìn)程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } } //銀行家算法函數(shù) void bank() { cout< int k=0; //用于輸入進(jìn)程編號 bool r=false; // 初值為假，輸入Y繼續(xù)申請則置為真 do{//輸入請求 cout<<“輸入申請資源的進(jìn)程(0-“< “; cin>>k; cout< while(k>n-1) //輸入錯(cuò)誤處理 { cout< cout< “; cin>>k; cout< } cout< “< for (j=0; j j++) { do{ //do……while 循環(huán)判斷申請輸入的情況 cout<<“進(jìn)程 “< 申請資源[“< cin>>Request[j]; cout< if(Request[j]>Need[k][j]) { //申請大于需求量時(shí)出錯(cuò)，提示重新輸入（貸款數(shù)目不允許超過需求數(shù)目） cout<<“申請大于需要量!“< cout<<“申請的資源“< 進(jìn)程“< cout<<“重新輸入!“< } else //先判斷是否申請大于需求量，再判斷是否申請大于可利用量 if(Request[j]>Available[j]) { //申請大于可利用量，應(yīng)該阻塞等待？…… ？？？ cout<<“＼n沒有那么多資源，目前可利用資源“< Finish[k]=0; //該進(jìn)程等待 goto ppp; //goto語句 跳轉(zhuǎn)，結(jié)束本次申請 } }while(Request[j]>Need[k][j]); //Request[j]>Available[j]|| } //改變Avilable、Allocation、Need的值 for (j=0; j j++) { Available[j] = Available[j]-Request[j]; Allocation[k][j] = Allocation[k][j]+Request[j]; Need[k][j] = Need[k][j]-Request[j]; Work[j] = Available[j]; } //判斷當(dāng)前狀態(tài)的安全性 safe(); //調(diào)用安全性算法函數(shù) if (l { l=0; cout<<“＼n試分配后，狀態(tài)不安全,所以不予分配!恢復(fù)原狀態(tài)“< //恢復(fù)數(shù)據(jù) for (j=0; j j++) { Available[j] = Available[j]+Request[j]; Allocation[k][j] = Allocation[k][j]-Request[j]; Need[k][j] = Need[k][j]+Request[j]; Work[j] = Available[j]; } for (i=0; i i++) Finish[i]=0; //進(jìn)程置為未分配狀態(tài) } else { l=0; cout<<“＼n申請資源成功！!“< for(j=0;j { if(Need[k][j]==0); else { //有一種資源還沒全部申請到，則該進(jìn)程不可執(zhí)行，不能釋放擁有的資源 l=1; //置l為1，作為判斷標(biāo)志 break; } } if(l!=1) { //進(jìn)程可以執(zhí)行，則釋放該進(jìn)程的所有資源 for (j=0;j { Available[j]=Available[j]+Allocation[k][j]; Allocation[k][j]=0; } cout<<“該進(jìn)程已得到所有需求資源，執(zhí)行后將釋放其所有擁有資源！“< } l=0; //歸零 cout<<“＼n安全的狀態(tài)!“< cout<<“安全序列為: “; cout<第二篇：操作系統(tǒng)銀行家算法實(shí)驗(yàn)報(bào)告
第三篇：操作系統(tǒng)課程設(shè)計(jì)(銀行家算法的模擬實(shí)現(xiàn))
第四篇：操作系統(tǒng)課程設(shè)計(jì)銀行家算法的模擬實(shí)現(xiàn)