銀行家算法.doc

。操作系統(tǒng)銀行家算法課后作業(yè)一、實(shí)驗(yàn)?zāi)康募由顚?duì)多實(shí)例資源分配系統(tǒng)中死鎖避免方法銀行家算法的理解，掌握 Windows 環(huán)境下銀行家算法的實(shí)現(xiàn)方法。強(qiáng)調(diào)對(duì)于資源的管理、申請(qǐng)、比較來避免出現(xiàn)死鎖的情況，保證系統(tǒng)的正常運(yùn)行。 二、實(shí)驗(yàn)內(nèi)容1.在 Windows 操作系統(tǒng)上，利用DEVC+編寫應(yīng)用程序?qū)崿F(xiàn)銀行家算法。2.創(chuàng)建 n 個(gè)線程來申請(qǐng)或釋放資源，只有保證系統(tǒng)安全，才會(huì)批準(zhǔn)資源申請(qǐng)。三、實(shí)驗(yàn)步驟（一）設(shè)計(jì)思路：銀行家算法可分為個(gè)主要的功能模塊，其描述如下：1.初始化由用戶輸入數(shù)據(jù)，分別對(duì)運(yùn)行的進(jìn)程數(shù)、總的資源種類數(shù)、總資源數(shù)、各進(jìn)程所需要的最大資源數(shù)量（Max），已分配的資源數(shù)量賦值。2.安全性檢查算法(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH=false;(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;(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)；否則，出錯(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)，它們用來表示資源分配系統(tǒng)的狀態(tài)。令n表示系統(tǒng)中進(jìn)程的數(shù)目，m表示資源的分類數(shù)。還需要以下數(shù)據(jù)結(jié)構(gòu)：1).Available是一個(gè)長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示j類資源可用的數(shù)量為k。2).Max是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程對(duì)資源的最大需求。Max i，j=k，表示進(jìn)程pi至多可以申請(qǐng)k個(gè)j類資源單位。3).Allocation是一個(gè)nm矩陣，它表示當(dāng)前分給每個(gè)進(jìn)程的資源數(shù)目。Allocation i，j=k，表示進(jìn)程i當(dāng)前分到k個(gè)j類資源。4).Need是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程還缺少多少資源。Needi，j=k，表示進(jìn)程pi尚需k個(gè)j類資源才能完成其任務(wù)。顯然Needi，j= Max i，j- Allocation i，j。（二）流程圖四、運(yùn)行結(jié)果示例這里以書上的例子為例，初值如下表：AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 19 0 0P32 1 12 2 2P40 0 24 3 3將Available數(shù)列輸入，每個(gè)資源的數(shù)量，線程的數(shù)目輸入每個(gè)進(jìn)程的最大資源需求量輸入每個(gè)線程的資源量僅輸入一個(gè)例子再輸入一個(gè)不安全的狀態(tài)申請(qǐng)資源量大于最大需求資源量輸入一個(gè)申請(qǐng)資源大于資源系統(tǒng)現(xiàn)有可分配資源的情況成功觸發(fā)銀行家算法的條件系統(tǒng)顯示不安全以上實(shí)例，很好證明了對(duì)于銀行家算法的實(shí)例。代碼附錄：/感謝CSDN論壇的代碼資源#include#include#includeint Available10; /可使用資源向量int Max1010; /最大需求矩陣int Allocation1010=0; /分配矩陣int Need1010=0; /需求矩陣int Work10; /工作向量int Finish10; /狀態(tài)標(biāo)志int Request1010; /進(jìn)程申請(qǐng)資源向量int Pause10;int List10;int i,j;int n; /系統(tǒng)資源總數(shù)int m; /總的進(jìn)程數(shù)int a; /當(dāng)前申請(qǐng)的進(jìn)程號(hào)int l,e; /計(jì)數(shù)器int b=0,c=0,f=0,g; /計(jì)數(shù)器void mainenter()/主要的輸入部分代碼 printf(請(qǐng)輸入系統(tǒng)總共有的資源數(shù)：); scanf(%d,&n); printf(請(qǐng)輸入總共有多少個(gè)進(jìn)程：); scanf(%d,&m); for(i=1;i=n;i+) printf(第%d類資源有的資源實(shí)例：,i); scanf(%d,&Availablei); for(i=1;i=m;i+) for(j=1;j=n;j+) printf(進(jìn)程P%d對(duì)第%d類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /進(jìn)程提出新申請(qǐng)的代碼部分 printf(請(qǐng)輸入申請(qǐng)資源的進(jìn)程：); scanf(%d,&a); for(i=1;iNeedai) printf(n出錯(cuò)！進(jìn)程申請(qǐng)的資源數(shù)多于它自己申報(bào)的最大量n); if(RequestaiAvailablei) printf(nP%d必須等待n,a);/以下是試探性分配 Availablei=Availablei-Requestai; Allocationai=Allocationai+Requestai; Needai=Needai-Requestai; Worki=Availablei; for(i=1;i=m;i+) Pausei=Availablei;/Pausei只是一個(gè)暫時(shí)寄存的中間變量，為防止在下面 /安全性檢查時(shí)修改到Availablei而代替的一維數(shù)組 Finishi=false; for(g=1;g=m;g+) for(i=1;i=m;i+) b=0; /計(jì)數(shù)器初始化 for(j=1;j=n;j+) if(Needij=Pausej) b=b+1; if(Finishi=false&b=n) for(l=1;l=n;l+) Pausel=Pausel+Allocationil; Finishi=true; printf($ %d ,i);/依次輸出進(jìn)程安全序列之一中每個(gè)元素 printf(n); for(i=1;i=m;i+) if(Finishi=true) f=f+1;/統(tǒng)計(jì)Finishitrue的個(gè)數(shù) if (f=m) printf(safe static); f=0;/將計(jì)數(shù)器f重新初始化，為下一次提出新的進(jìn)程申請(qǐng)做準(zhǔn)備 else printf( unsafe static );/以下代碼為當(dāng)系統(tǒng)被判定為不安全狀態(tài)時(shí) /返回提出申請(qǐng)前的狀態(tài) for(i=1;i=n;i+) Availablei=Availablei+Requestai; Allocationai=Allocationai-Requestai; Needai=Needai+Requestai; void mainprint() printf(當(dāng)前的系統(tǒng)狀態(tài)n); printf( 目前占有量 最大需求量 尚需要量 n進(jìn)程); for(i=1;i=n;i+) for(j=1;j=n;j+) printf( %d類,j); for(i=1;i=m;i+) printf(nP%d,i); for(j=1;j=n;j+) printf( %d ,Allocationij); for(j=1;j=n;j+) printf( %d ,Maxij); for(j=1;j=n;j+) printf( %d ,Needij); printf(nn系統(tǒng)剩余資源量： ); for(i=1;i=n;i+) printf( %d ,Availablei); printf(n);int main() int k,h=1; while(h) system(cls); printf(nn 1:輸入系統(tǒng)的資源數(shù)、申請(qǐng)進(jìn)程數(shù)、每個(gè)類資源的實(shí)例數(shù)); printf(n 2: 輸入進(jìn)程的資源申請(qǐng)); printf(n 3: 輸出系統(tǒng)狀態(tài)); printf(n 4: 退出程序); printf(nn 請(qǐng)選擇 ); scanf(%d,&k); switch(k) case 1:mainenter(); break; case 2:mainrequest(); break; case 3:mainprint(); break; case 4:h=0; break; printf(n); system(pause); system(cls); printf(nn 謝謝使用 n); printf(nn See you next time