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