操作系統(tǒng)課程設(shè)計報告-銀行家算法

1、操作系統(tǒng)課程設(shè)計報告課題： 銀行家算法 專業(yè)計算機(jī)科學(xué)與技術(shù)學(xué)生姓名班級b計算機(jī)072學(xué)號0710604216指導(dǎo)教師信息工程學(xué)院一、實(shí)驗(yàn)要求和實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康模罕菊n程設(shè)計是學(xué)生學(xué)習(xí)完操作系統(tǒng)原理課程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計，讓學(xué)生更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動手能力。實(shí)驗(yàn)要求：從課程設(shè)計的目的出發(fā)，通過設(shè)計工作的各個環(huán)節(jié)，達(dá)到以下教學(xué)要求：兩人一組，每組從所給題目中任選一個（如自擬題目，需經(jīng)指導(dǎo)教師同意），每個學(xué)生必須獨(dú)立完成課程設(shè)計，不能相互抄襲，同組者文檔不能相同；設(shè)計完成后，將所完成的工作交由指導(dǎo)教師檢查；要求

2、寫出一份詳細(xì)的設(shè)計報告。二、設(shè)計內(nèi)容：課題一、編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。1）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：可利用資源向量available。這是一個含有m個 元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。availablej=k，則表示系統(tǒng)中現(xiàn)有rj 類資源k個。最大需求矩陣max。這是一個n*m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果maxi，j=k，則表示進(jìn)程i需要rj類資源的最大數(shù)目為k。1. 分配矩陣allocation。這也是一個n*m的

3、矩陣，它定義了系統(tǒng)中每一類資料當(dāng)前已分配給沒一進(jìn)程的資源數(shù)。如果allocationi，j=k，則表示進(jìn)程i當(dāng)前已分得rj類資源的數(shù)目為k。需求矩陣need。這也是一個n*m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果needi,j=k，則表示進(jìn)程i還需要rj類資源k個，方能完成其任務(wù)。上述三個矩陣存在如下關(guān)系： needi,j= maxi，j- allocationi，j2）銀行家算法設(shè)requesti 是進(jìn)程pi的請求向量，如果requesti，j=k,表示進(jìn)程pi需要k個rj類型的資源。當(dāng)pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：如果requesti，j= needi,j，便轉(zhuǎn)向步

4、驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。三、設(shè)計思路設(shè)計思路a、 設(shè)計進(jìn)程對各在資源最大申請表示及初值確定。b、 設(shè)定系統(tǒng)提供資源初始狀態(tài)。c、 設(shè)定每次某個進(jìn)程對各類資源的申請表示。d、 編制程序，依據(jù)銀行家算法，決定其申請是否得到滿足。四、詳細(xì)設(shè)計1、初始化：由用戶輸入數(shù)據(jù)，分別對可利用資源向量矩陣available、最大需求矩陣max、分配矩陣allocation、需求矩陣need賦值。2、銀行家算法：在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)

5、生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。設(shè)進(jìn)程cusneed提出請求request i，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果request cusneed i= needcusneedi，則轉(zhuǎn)(2)；否則，出錯。(2)如果request cusneed i= availablecusneedi，則轉(zhuǎn)(3)；否則，出錯。銀行家算法的數(shù)據(jù)結(jié)構(gòu)假設(shè)有m個進(jìn)程n類資源，則有如下數(shù)據(jù)結(jié)構(gòu):#define w 10#define r 20int m ; /總進(jìn)程數(shù)int n ; /資源種類 int all_resourcew;

6、 /各種資源的數(shù)目總和int maxwr; /m個進(jìn)程對n類資源最大資源需求量int availabler; /系統(tǒng)可用資源數(shù)int allocationwr; /m個進(jìn)程已經(jīng)得到n類資源的資源量int needwr; /m個進(jìn)程還需要n類資源的資源量int requestr; /請求資源個數(shù) 3.安全性檢測算法 1)先定義兩個變量,用來表示推算過程的數(shù)據(jù). fn=an,表示推算過程中,系統(tǒng)中剩余資源量的變化. jn=false表示推算過程中各進(jìn)程是否假設(shè)已完成 系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：availablei-=requestcusneedi;allocationcusneedi+=re

7、questcusneedi;、needcusneedi-=requestcusneedi;4、安全性檢查算法1)設(shè)置兩個工作向量work=available;finish2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程，finish=false;need=work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。work+=allocation;finish=true;goto 24)如所有的進(jìn)程finish= true，則表示安全；否則系統(tǒng)不安全。 安全狀態(tài): 在某時刻系統(tǒng)中所有進(jìn)程可以排列一個安全序列:p1,p2,pn,剛稱此時,系統(tǒng)是安全的. 所謂安

8、全序列p1,p2,pn是指對于p2,都有它所需要剩余資源數(shù)量不大于系統(tǒng)掌握的剩余的空間資源與所有pi(ji)所占的資源之和. 不安全狀態(tài)可能產(chǎn)生死鎖.目前狀態(tài) 最大需求 尚需 p1 3 9 6 p2 5 10 5 p3 2 42 在每一次進(jìn)程中申請的資源,判定一下,若實(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

9、 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 name20; int a; int b; int c; int need_a; int need_b; int need_c; process; bank banker; process processesmax_p; int quantity; /初始化函數(shù) void initial() int i; banker.a=maxa; banker.

10、b=maxb; banker.c=maxc; banker.remain_a=maxa; banker.remain_b=maxb; banker.remain_c=maxc; for(i=0;imax_p;i+) strcpy(,); processesi.a=0; processesi.b=0; processesi.c=0; processesi.need_a=0; processesi.need_b=0; processesi.need_c=0; /新加作業(yè) void add() char name20; int flag=0; int t; int ne

11、ed_a,need_b,need_c; int i; coutendl; cout新加作業(yè)endl; coutname; for(i=0;iquantity;i+) if(!strcmp(,name) flag=1; break; if(flag) cout錯誤,作業(yè)已存在endl; else coutneed_a; coutneed_b; coutneed_c; t=1; coutneed_abanker.remain_a) cout錯誤,所需a類資源大于銀行家所剩a類資源banker.remain_b) cout錯誤,所需b類資源大于銀行家所剩b類資源bank

12、er.remain_c) cout錯誤,所需c類資源大于銀行家所剩c類資源endl; t=0; if(t) strcpy(,name); processesquantity.need_a=need_a; processesquantity.need_b=need_b; processesquantity.need_c=need_c; quantity+; cout新加作業(yè)成功endl; else cout新加作業(yè)失敗endl; /為作業(yè)申請資源 void bid() char name20; int i,p; int a,b,c; int flag;

13、 coutendl為作業(yè)申請資源endl; coutname; p=-1; for(i=0;iquantity;i+) if(!strcmp(,name) p=i; break; if(p!=-1) couta; coutb; coutc; flag=1; if(abanker.remain_a)|(aprocessesp.need_a-processesp.a) cout錯誤,所申請a類資源大于銀行家所剩a類資源或該進(jìn)程還需數(shù)量banker.remain_b)|(bprocessesp.need_b-processesp.b) cout錯誤,所申請b類資源大于銀

14、行家所剩b類資源或該進(jìn)程還需數(shù)量banker.remain_c)|(cprocessesp.need_c-processesp.c) cout錯誤,所申請c類資源大于銀行家所剩c類資源或該進(jìn)程還需數(shù)量endl; flag=0; if(flag) banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processesp.a+=a; processesp.b+=b; processesp.c+=c; cout為作業(yè)申請資源成功endl; else cout為作業(yè)申請資源失敗endl; else cout該作業(yè)不存在endl; /撤

15、消作業(yè) void finished() char name20; int i,p; coutendl撤消作業(yè)endl; coutname; p=-1; for(i=0;iquantity;i+) if(!strcmp(,name) p=i; break; if(p!=-1) banker.remain_a+=processesp.a; banker.remain_b+=processesp.b; banker.remain_c+=processesp.c; for(i=p;iquantity-1;i+) processesi=processesi+1; strcp

16、y(,); processesquantity-1.a=0; processesquantity-1.b=0; processesquantity-1.c=0; processesquantity-1.need_a=0; processesquantity-1.need_b=0; processesquantity-1.need_c=0; quantity-; cout撤消作業(yè)成功endl; else cout撤消作業(yè)失敗endl; /查看資源情況 void view() int i; coutendl查看資源情況endl; cout銀行家所剩資

17、源(剩余資源/總共資源)endl; couta類:banker.remain_a/banker.a; cout b類:banker.remain_b/banker.b; cout c類:banker.remain_c/banker.c; coutendlendl作業(yè)占用情況(已占用資源/所需資源)endl0) for(i=0;iquantity;i+) cout作業(yè)名:endl; couta類:processesi.a/processesi.need_a; cout b類:processesi.b/processesi.need_b; cout c類:proces

18、sesi.c/processesi.need_c; coutendl; else cout當(dāng)前沒有作業(yè)endl; /顯示版權(quán)信息函數(shù) void version() coutendlendl; cout 銀行家算法 endl; coutendlendl; void main() int chioce; int flag=1; initial(); version(); while(flag) cout1.新加作業(yè) 2.為作業(yè)申請資源 3.撤消作業(yè)endl; cout4.查看資源情況 0.退出系統(tǒng)endl; coutchioce; 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選擇錯誤endlendl; 六、使用說明運(yùn)行環(huán)境c-free4.0，新建任務(wù)。將編制好的代碼輸入此運(yùn)行環(huán)境中。按f5：出現(xiàn)如上圖所示窗口。按照提示，新建一個作業(yè)：