《操作系統》課程設計報告
課題：
銀行家算法
專業
計算機科學與技術
學生姓名
班級
計算機
學號
指導教師
信息工程學院
一、實驗要求和實驗目的實驗目的：本課程設計是學生學習完《操作系統原理》課程后，進行的一次全面的綜合訓練，通過課程設計，讓學生更好地掌握操作系統的原理及實現方法，加深對操作系統基礎理論和重要算法的理解，加強學生的動手能力。
實驗要求：從課程設計的目的出發，通過設計工作的各個環節，達到以下教學要求：兩人一組，每組從所給題目中任選一個（如自擬題目，需經指導教師同意），每個學生必須獨立完成課程設計，不能相互抄襲，同組者文檔不能相同；設計完成后，將所完成的工作交由指導教師檢查；要求寫出一份詳細的設計報告。
二、設計內容：
課題一、編制銀行家算法通用程序，并檢測所給狀態的系統安全性。
1）銀行家算法中的數據結構：
可利用資源向量Available。這是一個含有m個
元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。Available[j]=K，則表示系統中現有Rj
類資源K個。
最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i，j]=K，則表示進程i需要Rj類資源的最大數目為K。
1.分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統中每一類資料當前已分配給沒一進程的資源數。如果Allocation[i，j]=K，則表示進程i當前已分得Rj類資源的數目為K。需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。
上述三個矩陣存在如下關系：
Need[i,j]=
Max[i，j]-
Allocation[i，j]
2）銀行家算法
設Request[i]
是進程Pi的請求向量，如果Request[i，j]=K,表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：如果Request[i，j]<=
Need[i,j]，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。
三、設計思路
設計思路A、設計進程對各在資源最大申請表示及初值確定。B、設定系統提供資源初始狀態。C、設定每次某個進程對各類資源的申請表示。D、編制程序，依據銀行家算法，決定其申請是否得到滿足。
四、詳細設計
1、初始化：由用戶輸入數據，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。
2、銀行家算法：在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處于安全狀態，便可以避免發生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。
設進程cusneed提出請求REQUEST
[i]，則銀行家算法按如下規則進行判斷。
(1)如果REQUEST
[cusneed]
[i]<=
NEED[cusneed][i]，則轉(2)；否則，出錯。
(2)如果REQUEST
[cusneed]
[i]<=
AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。
銀行家算法的數據結構
假設有M個進程N類資源，則有如下數據結構:
#define
W
#define
R
int
M
;
//總進程數
int
N
;
//資源種類
int
ALL_RESOURCE[W];
//各種資源的數目總和
int
MAX[W][R];
//M個進程對N類資源最大資源需求量
int
AVAILABLE[R];
//系統可用資源數
int
ALLOCATION[W][R];
//M個進程已經得到N類資源的資源量
int
NEED[W][R];
//M個進程還需要N類資源的資源量
int
Request[R];
//請求資源個數
3.“安全性檢測“算法
1)先定義兩個變量,用來表示推算過程的數據.F[n]=A[n],表示推算過程中,系統中剩余資源量的變化.J[n]=False表示推算過程中各進程是否假設“已完成“
系統試探分配資源，修改相關數據：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i];
4、安全性檢查算法
1)設置兩個工作向量Work=AVAILABLE;FINISH
2)從進程集合中找到一個滿足下述條件的進程，FINISH==false;
NEED<=Work;
如找到，執行(3)；否則，執行(4)
3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。
Work+=ALLOCATION;
Finish=true;
GOTO
4)如所有的進程Finish=
true，則表示安全；否則系統不安全。
安全狀態:
在某時刻系統中所有進程可以排列一個安全序列:{P1,P2,`````Pn},剛稱此時,系統是安全的.所謂安全序列{P1,P2,`````Pn}是指對于P2,都有它所需要剩余資源數量不大于系統掌握的剩余的空間資源與所有Pi(j 最大需求 尚需 P1 P2 P3 4?????????????2 在每一次進程中申請的資源,判定一下,若實際分配的話,之后系統是否安全.銀行家算法的數據結構.五、代碼清單 #include #include #include #include #include #include const int MAX_P=20; const int MAXA=10; //定義A類資源的數量 const int MAXB=5; const int MAXC=7; typedef struct node{ int a; int b; int c; int remain_a; int remain_b; int remain_c; }bank; typedef struct node1{ char name[20]; int a; int b; int c; int need_a; int need_b; int need_c; }process; bank banker; process processes[MAX_P]; int quantity; //初始化函數 void initial() { int i; banker.a=MAXA; banker.b=MAXB; banker.c=MAXC; banker.remain_a=MAXA; banker.remain_b=MAXB; banker.remain_c=MAXC; for(i=0;i strcpy(processes[i].name,““); processes[i].a=0; processes[i].b=0; processes[i].c=0; processes[i].need_a=0; processes[i].need_b=0; processes[i].need_c=0; } } //新加作業 void add() { char name[20]; int flag=0; int t; int need_a,need_b,need_c; int i; cout< cout<<“新加作業“< cout<<“請輸入新加作業名:“; cin>>name; for(i=0;i if(!strcmp(processes[i].name,name)){ flag=1; break; } } if(flag){ cout<<“錯誤,作業已存在“< } else{ cout<<“本作業所需A類資源:“; cin>>need_a; cout<<“本作業所需B類資源:“; cin>>need_b; cout<<“本作業所需C類資源:“; cin>>need_c; t=1; cout< if(need_a>banker.remain_a){ cout<<“錯誤,所需A類資源大于銀行家所剩A類資源“< t=0; } if(need_b>banker.remain_b){ cout<<“錯誤,所需B類資源大于銀行家所剩B類資源“< t=0; } if(need_c>banker.remain_c){ cout<<“錯誤,所需C類資源大于銀行家所剩C類資源“< t=0; } if(t){ strcpy(processes[quantity].name,name); processes[quantity].need_a=need_a; processes[quantity].need_b=need_b; processes[quantity].need_c=need_c; quantity++; cout<<“新加作業成功“< } else{ cout<<“新加作業失敗“< } } } //為作業申請資源 void bid() { char name[20]; int i,p; int a,b,c; int flag; cout< cout<<“要申請資源的作業名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ cout<<“該作業要申請A類資源數量:“; cin>>a; cout<<“該作業要申請B類資源數量:“; cin>>b; cout<<“該作業要申請C類資源數量:“; cin>>c; flag=1; if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){ cout<<“錯誤,所申請A類資源大于銀行家所剩A類資源或該進程還需數量“< flag=0; } if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){ cout<<“錯誤,所申請B類資源大于銀行家所剩B類資源或該進程還需數量“< flag=0; } if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){ cout<<“錯誤,所申請C類資源大于銀行家所剩C類資源或該進程還需數量“< flag=0; } if(flag){ banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processes[p].a+=a; processes[p].b+=b; processes[p].c+=c; cout<<“為作業申請資源成功“< } else{ cout<<“為作業申請資源失敗“< } } else{ cout<<“該作業不存在“< } } //撤消作業 void finished() { char name[20]; int i,p; cout< cout<<“要撤消作業名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ banker.remain_a+=processes[p].a; banker.remain_b+=processes[p].b; banker.remain_c+=processes[p].c; for(i=p;i processes[i]=processes[i+1]; } strcpy(processes[quantity-1].name,““); processes[quantity-1].a=0; processes[quantity-1].b=0; processes[quantity-1].c=0; processes[quantity-1].need_a=0; processes[quantity-1].need_b=0; processes[quantity-1].need_c=0; quantity--; cout<<“撤消作業成功“< } else{ cout<<“撤消作業失敗“< } } //查看資源情況 void view() { int i; cout< cout<<“銀行家所剩資源(剩余資源/總共資源)“< cout<<“A類:“< cout<<“ B類:“< cout<<“ C類:“< cout< if(quantity>0){ for(i=0;i cout<<“作業名:“< cout<<“A類:“< cout<<“ B類:“< cout<<“ C類:“< cout< } } else{ cout<<“當前沒有作業“< } } //顯示版權信息函數 void version() { cout< cout<<“ 銀行家算法 “< cout< } void main() { int chioce; int flag=1; initial(); version(); while(flag){ cout<<“1.新加作業 2.為作業申請資源 3.撤消作業“< cout<<“4.查看資源情況 0.退出系統“< cout<<“請選擇:“; cin>>chioce; switch(chioce){ case 1: add(); break; case 2: bid(); break; case 3: finished(); break; case 4: view(); break; case 0: flag=0; break; default: cout<<“選擇錯誤“< } } } 六、使用說明 運行環境C-FREE4.0，新建任務。將編制好的代碼輸入此運行環境中。 按F5：出現如上圖所示窗口。按照提示，新建一個作業：wujun。為作業分配資源，A：3；B：4；C：5。輸入2，為作業分配資源。三種資源的數量分配分別為:A:3;B:5;C:4。輸入4，查看資源情況。出現出錯提示，所申請的B類資源超過銀行家所剩B類資源或作業申請資源失敗。輸入0，退出系統。 重新加入一個作業：wujun1.并為作業分配資源分別為A:3;B:3;C:3，為該作業分配資源A:3;B:2;C:2.輸入4查看資源情況。 顯示輸出，銀行家算法所剩資源（剩余資源、總共資源）。 七、實驗心得 八、參考文獻 湯子瀛等.計算機操作系統.西安電子科技大學出版社.2001年5月 蔣靜 徐志偉.操作系統原理?技術與編程『M』.北京:機械工業出版社,2004
點擊咨詢