計(jì)算機(jī)操作系統(tǒng)程序設(shè)計(jì)課程考核報(bào)告銀行家算法模擬實(shí)現(xiàn)

1、 宿 遷 學(xué) 院計(jì)算機(jī)操作系統(tǒng)程序設(shè)計(jì)課程考核報(bào)告銀行家算法模擬實(shí)現(xiàn)班 級(jí)： 09軟件（1） 學(xué) 號(hào)： 姓 名： 指導(dǎo)老師： 2011年12月 19日目錄1. 課程設(shè)計(jì)簡(jiǎn)介-31.1課程設(shè)計(jì)題目- 31.2課程設(shè)計(jì)目的-31.3 課程設(shè)計(jì)要求-32 實(shí)驗(yàn)原理分析-42.1 算法的來(lái)源及基本思想-42.2 死鎖產(chǎn)生的條件-42.3 模擬進(jìn)程申請(qǐng)資源-53 概要設(shè)計(jì)-54 詳細(xì)設(shè)計(jì)-75 代碼設(shè)計(jì)-86 調(diào)試分析- 147 心得體會(huì)-218 參考文獻(xiàn)-21 1 課程設(shè)計(jì)簡(jiǎn)介： 1.1 課程設(shè)計(jì)題目銀行家算法的模擬實(shí)現(xiàn)。應(yīng)用銀行家算法驗(yàn)證進(jìn)程安全性檢查及分配資源。1.2 課程設(shè)計(jì)目的 本設(shè)計(jì)的目的是

2、通過(guò)編寫(xiě)和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并采用適當(dāng)?shù)乃惴?，有效地防止和避免死鎖地發(fā)生。a、了解進(jìn)程產(chǎn)生死鎖的原因，了解為什么要進(jìn)行死鎖的避免。b、掌握銀行家算法的數(shù)據(jù)結(jié)構(gòu)，了解算法的執(zhí)行過(guò)程，加深對(duì)銀行家算法的理解。1.3 課程設(shè)計(jì)要求設(shè)計(jì)一個(gè)n 個(gè)并發(fā)進(jìn)程共享m 個(gè)系統(tǒng)資源的系統(tǒng)。進(jìn)程可動(dòng)態(tài)申請(qǐng)資源和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。要求采用銀行家算法實(shí)現(xiàn)。(1) 初始化這組進(jìn)程的最大資源請(qǐng)求和依次申請(qǐng)的資源序列。把各進(jìn)程已占用和需求資源情況記錄在進(jìn)程控制塊中。假定進(jìn)程控制塊的內(nèi)容包括：進(jìn)程名，狀態(tài)，當(dāng)前申請(qǐng)量，資源需求總量，已占資源量，能執(zhí)行完標(biāo)志。

3、其中，進(jìn)程的狀態(tài)有：就緒、等待和完成。當(dāng)系統(tǒng)不能滿足進(jìn)程的資源請(qǐng)求時(shí)，進(jìn)程處于等待態(tài)。資源需求總量表示進(jìn)程運(yùn)行過(guò)程中對(duì)資源的總的需求量。已占資源量表示進(jìn)程目前已經(jīng)得到但還未歸還的資源量。因此，進(jìn)程在以后還需要的剩余資源量等于資源需要總量減去已占資源量。顯然每個(gè)進(jìn)程的資源需求總量不應(yīng)超過(guò)系統(tǒng)擁有的資源總量。(2) 銀行家算法分配資源的原則是：當(dāng)某個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，假定先分配資源給它，然后查找各進(jìn)程的剩余請(qǐng)求，檢查系統(tǒng)的剩余資源量是否由于進(jìn)程的分配而導(dǎo)致系統(tǒng)死鎖。若能，則讓進(jìn)程等待，否則，讓進(jìn)程的假分配變?yōu)檎娣峙洹?a) 查找各進(jìn)程的剩余請(qǐng)求，檢查系統(tǒng)的剩余資源量是否能滿足其中一進(jìn)程。如果能，

4、則轉(zhuǎn)b)。(b) 將資源分配給所需的進(jìn)程，這樣，該進(jìn)程已獲得資源最大請(qǐng)求，最終能運(yùn)行完成。標(biāo)記這個(gè)進(jìn)程為終止進(jìn)程，并將其占有的全部資源歸還給系統(tǒng)。 重復(fù)第a)步和第b )步，直到所有進(jìn)程都標(biāo)記為終止進(jìn)程，或直到一個(gè)死鎖發(fā)生。若所有進(jìn)程都標(biāo)記為終止進(jìn)程，則系統(tǒng)的初始狀態(tài)是安全的，否則為不安全的。若安全，則正式將資源分配給它，否則假定的分配作廢，讓其等待。2 實(shí)驗(yàn)原理分析：2.1 算法的來(lái)源及基本思想銀行家算法，顧名思義是來(lái)源于銀行的借貸業(yè)務(wù)，通過(guò)這個(gè)算法可以用來(lái)解決生活中的實(shí)際問(wèn)題，如銀行貸款等。一定數(shù)量的本金要應(yīng)多個(gè)客戶的借貸周轉(zhuǎn)，為了防止銀行加資金無(wú)法周轉(zhuǎn)而倒閉，對(duì)每一筆貸款，必須考察其是否

5、能限期歸還。在操作系統(tǒng)中研究資源分配策略時(shí)也有類(lèi)似問(wèn)題，系統(tǒng)中有限的資源要供多個(gè)進(jìn)程使用，必須保證得到的資源的進(jìn)程能在有限的時(shí)間內(nèi)歸還資源，以供其他進(jìn)程使用資源。如果資源分配不得到就會(huì)發(fā)生進(jìn)程循環(huán)等待資源，則進(jìn)程都無(wú)法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。2.2 死鎖產(chǎn)生的條件銀行家算法是用來(lái)避免死鎖的一種重要方法，通過(guò)編寫(xiě)一個(gè)簡(jiǎn)單的銀行家算法程序，加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。死鎖的產(chǎn)生，必須同時(shí)滿足四個(gè)條件：a、即一個(gè)資源每次只能由一個(gè)進(jìn)程使用；b、第二個(gè)為等待條件，即一個(gè)進(jìn)程請(qǐng)求資源不能滿足時(shí)，它必須等待，單它仍繼續(xù)寶石已得到的所有其他資源；c、第三個(gè)

6、為非剝奪條件，即在出現(xiàn)死鎖的系統(tǒng)中一定有不可剝奪使用的資源；d、第四個(gè)為循環(huán)等待條件，系統(tǒng)中存在若干個(gè)循環(huán)等待的進(jìn)程，即其中每一個(gè)進(jìn)程分別等待它前一個(gè)進(jìn)程所持有的資源。防止死鎖的機(jī)構(gòu)只能確保上述四個(gè)條件之一不出現(xiàn)，則系統(tǒng)就不會(huì)發(fā)生死鎖。銀行家算法是避免死鎖的方法中，施加的限制條件較弱的，有利于獲得令人滿意的系統(tǒng)性能的方法。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。2.3 模擬進(jìn)程申請(qǐng)資源把一個(gè)進(jìn)程需要和已占有資源的情況記錄在進(jìn)程控制中，假定進(jìn)程控制塊pcb其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當(dāng)進(jìn)程在處于等待態(tài)時(shí)，表示系統(tǒng)不能滿足該進(jìn)程

7、當(dāng)前的資源申請(qǐng)?！百Y源需求總量”表示進(jìn)程在整個(gè)執(zhí)行過(guò)程中總共要申請(qǐng)的資源量。顯然，每個(gè)進(jìn)程的資源需求總量不能超過(guò)系統(tǒng)擁有的資源總數(shù), 銀行算法進(jìn)行資源分配可以避免死鎖.3 概要設(shè)計(jì)：銀行家算法可分為個(gè)主要的功能模塊，其描述如下：1.初始化由用戶輸入數(shù)據(jù)，分別對(duì)運(yùn)行的進(jìn)程數(shù)、總的資源種類(lèi)數(shù)、總資源數(shù)、各進(jìn)程所需要的最大資源數(shù)量（max），已分配的資源數(shù)量賦值。2.安全性檢查算法(1)設(shè)置兩個(gè)工作向量work=available;finish=false;(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，finish=false;need=work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進(jìn)程獲得

8、資源，可順利執(zhí)行，直至完成，從而釋放資源。work+=allocation;finish=true;(4).如所有的進(jìn)程finish= true，則表示安全；否則系統(tǒng)不安全。 3. 銀行家算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。設(shè)進(jìn)程j提出請(qǐng)求request i，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1).如果request j i= needji，則轉(zhuǎn)(2)

9、；否則，出錯(cuò)。(2).如果request j i= availableji，則轉(zhuǎn)(3)；否則，出錯(cuò)。(3).系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： availablei-=requestji; allocationji+=requestji;needji-=requestji;用到的數(shù)據(jù)結(jié)構(gòu)：實(shí)現(xiàn)銀行家算法要有若干數(shù)據(jù)結(jié)構(gòu)，它們用來(lái)表示資源分配系統(tǒng)的狀態(tài)。令n表示系統(tǒng)中進(jìn)程的數(shù)目，m表示資源的分類(lèi)數(shù)。還需要以下數(shù)據(jù)結(jié)構(gòu)：1).available是一個(gè)長(zhǎng)度為m的向量，它表示每類(lèi)資源可用的數(shù)量。available j=k，表示j類(lèi)資源可用的數(shù)量為k。2).max是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程對(duì)資源的最大

10、需求。max i，j=k，表示進(jìn)程pi至多可以申請(qǐng)k個(gè)j類(lèi)資源單位。3).allocation是一個(gè)nm矩陣，它表示當(dāng)前分給每個(gè)進(jìn)程的資源數(shù)目。allocation i，j=k，表示進(jìn)程i當(dāng)前分到k個(gè)j類(lèi)資源。4).need是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程還缺少多少資源。needi，j=k，表示進(jìn)程pi尚需k個(gè)j類(lèi)資源才能完成其任務(wù)。顯然needi，j= max i，j- allocation i，j。4 詳細(xì)設(shè)計(jì)：1主函數(shù)main（）要求在主函數(shù)中輸入運(yùn)行的進(jìn)程數(shù)、總的資源種類(lèi)數(shù)、總資源數(shù)、各進(jìn)程所需要的最大資源數(shù)量（max），已分配的資源數(shù)量，并對(duì)這些數(shù)據(jù)進(jìn)行有效性檢驗(yàn)，不符合條件的數(shù)據(jù)要進(jìn)

11、行重新輸入。 2函數(shù)showdata( ) showdata()函數(shù)用來(lái)輸出資源的分配情況。對(duì)各進(jìn)程資源的總數(shù)量、系統(tǒng)目前可利用的資源數(shù)量、各進(jìn)程還需要的資源數(shù)量及各進(jìn)程已分配的資源數(shù)量進(jìn)行輸出。 3函數(shù)bank( ) bank()函數(shù)為銀行家算法，對(duì)需申請(qǐng)資源的進(jìn)程號(hào)j和所要申請(qǐng)的資源數(shù)量requestj進(jìn)行輸入,并分別將requestj與needij和availablej進(jìn)行比較，觀察所要申請(qǐng)的資源數(shù)目是否合理。如合理，則判斷此時(shí)系統(tǒng)是否安全，若安全則輸出資源的分配情況，否則輸出原來(lái)的系統(tǒng)資源分配情況，重新輸入申請(qǐng)資源的數(shù)量。 4函數(shù)changdata( ) changdata()函數(shù)用來(lái)

12、改變可用資源和已經(jīng)拿到資源和還需要的資源的值。當(dāng)申請(qǐng)的資源數(shù)目合理時(shí)，對(duì)現(xiàn)在的系統(tǒng)資源分配情況進(jìn)行刷新。 5函數(shù)chkerr（） chkerr（）函數(shù)用來(lái)檢查系統(tǒng)此時(shí)的安全性。如果系統(tǒng)能夠找到一個(gè)安全執(zhí)行的序列，則各進(jìn)程能正常運(yùn)行終結(jié)，否則，此進(jìn)程進(jìn)入阻塞狀態(tài)。 6函數(shù) rstordata（ ） changdata（）函數(shù),改變可用資源和已經(jīng)拿到資源和還需要的資源的值。若判斷出申請(qǐng)資源后系統(tǒng)是安全的，則要改變系統(tǒng)現(xiàn)在的資源分配情況： availablej= availablej+requestj; allocationkj= allocation kj-requestj; needkj=nee

13、dkj+requestj5 代碼設(shè)計(jì)： #include#include#include#define false 0 #define true 1 #define w 10#define r 20int m ; /總進(jìn)程數(shù)int n ; /資源種類(lèi) int all_resourcew;/各種資源的數(shù)目總和int maxwr; /m個(gè)進(jìn)程對(duì)n類(lèi)資源最大資源需求量int availabler; /系統(tǒng)可用資源數(shù)int allocationwr; /m個(gè)進(jìn)程已經(jīng)得到n類(lèi)資源的資源量int needwr; /m個(gè)進(jìn)程還需要n類(lèi)資源的資源量int requestr; /請(qǐng)求資源個(gè)數(shù)void showd

14、ata() /函數(shù)showdata,輸出資源分配情況 int i,j; printf(nn各種資源的總數(shù)量(all):n); for (j=0;jn;j+) printf( 資源 %d: %dn,j+1,all_resourcej); printf(nn); printf(系統(tǒng)目前各種資源可用的數(shù)為(available):n); for (j=0;jn;j+) printf( 資源 %d: %dn, j+1, availablej); printf(nn); printf(各進(jìn)程還需要的資源量(need):nn); printf( 進(jìn)程 ); for(i=0;in;i+) printf( 資源

15、%d ,i+1); printf(n); for (i=0;im;i+) printf(進(jìn)程p%d：,i+1); for (j=0;jn;j+) printf( %d ,needij); printf(n); printf(nn); printf( 各進(jìn)程已經(jīng)得到的資源量(allocation): nn); printf( 進(jìn)程 ); for(i=0;in;i+) printf( 資源%d ,i+1); printf(n); for (i=0;im;i+) printf(進(jìn)程p%d: ,i+1); for (j=0;jn;j+)printf( %d ,allocationij); printf

16、(n); printf(n); void changdata(int k) /函數(shù)changdata,改變可用資源和已經(jīng)拿到資源和還需要的資源的值 int j; for (j=0;jn;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj;void rstordata(int k) /函數(shù)rstordata,恢復(fù)可用資源和已經(jīng)拿到資源和還需要的資源的值int j; for (j=0;jn;j+) availablej=availablej+requestj;

17、allocationkj=allocationkj-requestj; needkj=needkj+requestj;int chkerr(int s) /函數(shù)chkerr,檢查是否安全 int work,finishw; int i,j,k=0; for(i=0;im;i+)finishi=false; for(j=0;jn;j+) work=availablej; i=s; do if(finishi=false&needij=work) work=work+allocationij; finishi=true; i=0; else i+; while(im); for(i=0;im;i+

18、) if(finishi=false) printf(n); printf( 系統(tǒng)不安全! 本次資源申請(qǐng)不成功!n); printf(n); return 1; printf(n); printf( 經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。n); printf(n); return 0; void bank() /銀行家算法 int i=0,j=0; char flag=y; while(flag=y|flag=y) i=-1; while(i=m) printf( 請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)（從p1到p%d，否則重輸入!）:,m); printf(p); scanf(%d,&i); if(im)

19、printf( 輸入的進(jìn)程號(hào)不存在，重新輸入!n); printf( 請(qǐng)輸入進(jìn)程p%d申請(qǐng)的資源數(shù):n,i); for (j=0;jneedi-1j) /若請(qǐng)求的資源數(shù)大于進(jìn)程還需要i類(lèi)資源的資源量j printf( 進(jìn)程p%d申請(qǐng)的資源數(shù)大于進(jìn)程p%d還需要%d類(lèi)資源的資源量!,i,i,j); printf(申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇!nn); flag=n; break; else if(requestjavailablej) /若請(qǐng)求的資源數(shù)大于可用資源數(shù) printf(進(jìn)程p%d申請(qǐng)的資源數(shù)大于系統(tǒng)可用%d類(lèi)資源的資源量!,i,j); printf(申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇!nn

20、); flag=n; break; if(flag=y|flag=y) changdata(i-1); /調(diào)用changdata(i)函數(shù)，改變資源數(shù) if(chkerr(i-1) /若系統(tǒng)安全 rstordata(i-1); /調(diào)用rstordata(i)函數(shù)，恢復(fù)資源數(shù) showdata(); /輸出資源分配情況 else /若系統(tǒng)不安全 showdata(); /輸出資源分配情況 else /若flag=n|flag=n showdata(); printf(n); printf(是否繼續(xù)銀行家算法演示,按y或y鍵繼續(xù),按n或n鍵退出演示: ); scanf(%c,&flag); voi

21、d main() /主函數(shù) int i=0,j=0,p; printf( * n); printf( 銀行家算法的模擬實(shí)現(xiàn) n);printf( 20090307143 吳天一 n); printf( * nn); printf(請(qǐng)輸入總進(jìn)程數(shù):); scanf(%d,&m); printf(請(qǐng)輸入總資源種類(lèi):); scanf(%d,&n); printf(請(qǐng)輸入總資源數(shù)(all_resource):); for(i=0;in;i+) scanf(%d,&all_resourcei); printf(依次輸入各進(jìn)程所需要的最大資源數(shù)量(max):n); for (i=0;im;i+) for

22、(j=0;jall_resourcej) printf(n占有資源超過(guò)了聲明的該資源總數(shù),請(qǐng)重新輸入!n); while (maxijall_resourcej); printf(依次輸入各進(jìn)程已經(jīng)占據(jù)的資源數(shù)量(allocation):n); for (i=0;im;i+) for (j=0;jmaxij) printf(n占有資源超過(guò)了聲明的最大資源,請(qǐng)重新輸入n); while (allocationijmaxij); /初始化資源數(shù)量 for (j=0;jn;j+) p=all_resourcej; for (i=0;im;i+) p=p-allocationij;/減去已經(jīng)被占據(jù)的資源 avai