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