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