銀行家算法.doc

。操作系統(tǒng)銀行家算法課后作業(yè)一、實驗?zāi)康募由顚Χ鄬嵗Y源分配系統(tǒng)中死鎖避免方法銀行家算法的理解，掌握 Windows 環(huán)境下銀行家算法的實現(xiàn)方法。強調(diào)對于資源的管理、申請、比較來避免出現(xiàn)死鎖的情況，保證系統(tǒng)的正常運行。 二、實驗內(nèi)容1.在 Windows 操作系統(tǒng)上，利用DEVC+編寫應(yīng)用程序?qū)崿F(xiàn)銀行家算法。2.創(chuàng)建 n 個線程來申請或釋放資源，只有保證系統(tǒng)安全，才會批準(zhǔn)資源申請。三、實驗步驟（一）設(shè)計思路：銀行家算法可分為個主要的功能模塊，其描述如下：1.初始化由用戶輸入數(shù)據(jù)，分別對運行的進(jìn)程數(shù)、總的資源種類數(shù)、總資源數(shù)、各進(jìn)程所需要的最大資源數(shù)量（Max），已分配的資源數(shù)量賦值。2.安全性檢查算法(1)設(shè)置兩個工作向量Work=AVAILABLE;FINISH=false;(2)從進(jìn)程集合中找到一個滿足下述條件的進(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提出請求REQUEST i，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1).如果REQUEST j i= NEEDji，則轉(zhuǎn)(2)；否則，出錯。(2).如果REQUEST j i= AVAILABLEji，則轉(zhuǎn)(3)；否則，出錯。(3).系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLEi-=REQUESTji; ALLOCATIONji+=REQUESTji;NEEDji-=REQUESTji;用到的數(shù)據(jù)結(jié)構(gòu)：實現(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是一個長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示j類資源可用的數(shù)量為k。2).Max是一個nm矩陣，它表示每個進(jìn)程對資源的最大需求。Max i，j=k，表示進(jìn)程pi至多可以申請k個j類資源單位。3).Allocation是一個nm矩陣，它表示當(dāng)前分給每個進(jìn)程的資源數(shù)目。Allocation i，j=k，表示進(jìn)程i當(dāng)前分到k個j類資源。4).Need是一個nm矩陣，它表示每個進(jìn)程還缺少多少資源。Needi，j=k，表示進(jìn)程pi尚需k個j類資源才能完成其任務(wù)。顯然Needi，j= Max i，j- Allocation i，j。（二）流程圖四、運行結(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ù)列輸入，每個資源的數(shù)量，線程的數(shù)目輸入每個進(jìn)程的最大資源需求量輸入每個線程的資源量僅輸入一個例子再輸入一個不安全的狀態(tài)申請資源量大于最大需求資源量輸入一個申請資源大于資源系統(tǒng)現(xiàn)有可分配資源的情況成功觸發(fā)銀行家算法的條件系統(tǒng)顯示不安全以上實例，很好證明了對于銀行家算法的實例。代碼附錄：/感謝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)程申請資源向量int Pause10;int List10;int i,j;int n; /系統(tǒng)資源總數(shù)int m; /總的進(jìn)程數(shù)int a; /當(dāng)前申請的進(jìn)程號int l,e; /計數(shù)器int b=0,c=0,f=0,g; /計數(shù)器void mainenter()/主要的輸入部分代碼 printf(請輸入系統(tǒng)總共有的資源數(shù)：); scanf(%d,&n); printf(請輸入總共有多少個進(jìn)程：); scanf(%d,&m); for(i=1;i=n;i+) printf(第%d類資源有的資源實例：,i); scanf(%d,&Availablei); for(i=1;i=m;i+) for(j=1;j=n;j+) printf(進(jìn)程P%d對第%d類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /進(jìn)程提出新申請的代碼部分 printf(請輸入申請資源的進(jìn)程：); scanf(%d,&a); for(i=1;iNeedai) printf(n出錯！進(jìn)程申請的資源數(shù)多于它自己申報的最大量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只是一個暫時寄存的中間變量，為防止在下面 /安全性檢查時修改到Availablei而代替的一維數(shù)組 Finishi=false; for(g=1;g=m;g+) for(i=1;i=m;i+) b=0; /計數(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)程安全序列之一中每個元素 printf(n); for(i=1;i=m;i+) if(Finishi=true) f=f+1;/統(tǒng)計Finishitrue的個數(shù) if (f=m) printf(safe static); f=0;/將計數(shù)器f重新初始化，為下一次提出新的進(jìn)程申請做準(zhǔn)備 else printf( unsafe static );/以下代碼為當(dāng)系統(tǒng)被判定為不安全狀態(tài)時 /返回提出申請前的狀態(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ù)、申請進(jìn)程數(shù)、每個類資源的實例數(shù)); printf(n 2: 輸入進(jìn)程的資源申請); printf(n 3: 輸出系統(tǒng)狀態(tài)); printf(n 4: 退出程序); printf(nn 請選擇 ); 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