操作系統(tǒng)課程設(shè)計

1、模擬通過銀行家算法避免死鎖一、銀行家算法產(chǎn)生的背景及目的1:在多道程序系統(tǒng)中，雖然借助于多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的利用率， 提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險一死鎖。死鎖就是多個進程在運行過程 中因爭奪資源而造成的一種僵局，當(dāng)進程處于這種僵局狀態(tài)時，如無外力作用， 他們將無法再向前進行，如再把信號量作為同步工具時，多個Wait和Signal操作順序不當(dāng)，會產(chǎn)生進程死鎖。然而產(chǎn)生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件。在預(yù)防死鎖的幾種方法中，都施加了較強的限制條件，在避免死鎖的方法 中，所施加的條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安

2、全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，便可避免死鎖。 2:實驗?zāi)康模鹤寣W(xué)生獨立的使用編程語言編寫和調(diào)試一個系統(tǒng)分配資源的簡單 模擬程序，了解死鎖產(chǎn)生的原因及條件。采用銀行家算法及時避免死鎖的產(chǎn)生， 進一步理解課堂上老師講的相關(guān)知識點。銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶中誰能完成其工作，然后假定其完成工作且歸還全部貸款， 再進而檢查下一個能完成工作的客戶。如果所有客戶都能完成工作，則找到一個 安全序列，銀行家才是安全的。二：銀行家算法中的數(shù)據(jù)結(jié)構(gòu)1 :可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中

3、所配置的該類全部可用資源的 數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。如果Availablej=k ，z則表示系統(tǒng)中現(xiàn)有Rj類資源K個。2 :最大需求矩陣Max>這是一個n*m的矩陣，它定義了系統(tǒng)中n個進程中的每 一個進程對m類資源的最大需求。如果 Maxi,j=k ，表示第i個進程需要第Rj 類資源的最大數(shù)目k個.3:分配矩陣Allocation, 也是n*m的矩陣，若 Allocationi,j=k,表示第i個進程已分配Rj類資源的數(shù)目為k個。4 :需求矩陣Need也是一個n*m的矩陣，Needi,j=k, 表示第i個進程還需 Rj類資源k個。三、銀行家算法及安全性算法1：銀行

4、家算法設(shè)Requesti是進程Pi的請求向量，若Requestij=k;表示進程需要j類資源k個。當(dāng)Pi發(fā)出資源請求時，系統(tǒng)按下屬步驟進行檢查； 如果Requestij<=Needij;便轉(zhuǎn)向步驟（2），否則認為出錯，因為它所需要的資源數(shù)已超過他所宣布的最大值。如果 Requestij<=Availableij,便轉(zhuǎn)向步驟（3），否則認為尚無足夠資源，進程需等待。（3）系統(tǒng)試探著把資源分配給進程，并修改下面數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)Availableij=Availableij-Requestij;Allocati on ij=Allocatio nij+Requestij;Needij=Ne

5、edij-Requestij;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程 Pi，已完成此次分配。否則，將本次的試探分配作 廢，回復(fù)原來的資源分配狀態(tài)，將進程Pi等待。2：安全性算法1）設(shè)置兩個向量；1 :工作向量Work,表示系統(tǒng)可提供給進程運行所需的各類資源數(shù)目，它含有m個元素，初始時Work=Available2 : Finish ,表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始 時先做 Finishi=true（2）從進程中找到一個能滿需下屬條件的進程1 ； Finishi=false ；2： Needij<=Workj

6、;若找到執(zhí)行步驟（3），否則執(zhí)行步驟（4）（3）當(dāng)進程Pi順利獲得資源后，直至完成，并釋放分配給它的資源，執(zhí)行:Workj=Workj+Allocatio nij;Fini shi=true;Go to step （2）;（5）如果所有的進程Finishi都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于 不安全狀態(tài)。四、模塊設(shè)計與分析及整體功能概述模塊設(shè)計與分析：整個銀行家算法分為初始化函數(shù)Init （），安全性算法函數(shù)safe （），銀行 家算法函數(shù)bank （）三部分。初始化函數(shù)生成開始時刻系統(tǒng)中的進程和資源情 況，安全性算法判斷當(dāng)某進程申請資源時，系統(tǒng)能否處于安全狀態(tài)。在本實驗中， 若系統(tǒng)處于

7、安全狀態(tài)，便生成一個安全進程序列（安全序列可能有多個）。銀行家算法函數(shù)bank （）負責(zé)整體的檢查與異常判斷。整體功能概述：死鎖會引起系統(tǒng)陷入僵局，操作系統(tǒng)必須防止此現(xiàn)象的發(fā)生。本實驗通過一個動態(tài)分配資源的模擬程序，更清楚的理解死鎖產(chǎn)生的原因和條件。Dijkstra的銀行家算法是最有代表性的避免死鎖的方法。運行程序時用戶設(shè)定系統(tǒng)中進程和 可利用資源的種類數(shù)目。輸入各進程的可利用資源 Available，最大需求MAX已 分配資源Allocation，需求資源Need,之后各系統(tǒng)發(fā)出資源請求 Request，利用實驗中的安全性算法判斷能否產(chǎn)生一個安全性隊列，若能，則給該進程分配成 功，否則，不予

8、分配。五、流程圖設(shè)計訐始初始化後入Request大于Needfor j=0 to n-1耳請資源 大干Available是.申請資源Availablei, j >NeedAvai1ablej=Avai1ablej-Requesti, jAllocation, i, j=f<e quest. i, j +-A1 local ion _i, jNeedfij j=Needi? j-Request i. jWork j =Avai 1 abl ej, Finishi-false尋找NeMi, j <=Work j inishi=falseWork j=Workj_ +A1locat

9、ion1, j系統(tǒng)不安全六、源代碼及調(diào)試分析#include<iostream.h> #define MAXm 50 #define MAXn 100 int MAXMAXmMAXn; int AllocationMAXmMAXn; int AvailableMAXn; int NeedMAXmMAXn; int RequestMAXmMAXn; int FinishMAXm; int SequenceMAXm; int WorkMAXn; int m,n;/定義最大進程數(shù)II定義最大資源數(shù)最大需求矩陣已分配矩陣可用資源數(shù)組II需求矩陣請求矩陣存儲完成資源分配的進程II模擬的資源分

10、配序列系統(tǒng)是否有足夠的資源分配給進程IIm個進程,n個資源#define False 0#define True 1II*初始化算法*void input(); 數(shù)據(jù)輸入函數(shù) int safealg(); 安全性算法函數(shù) void banker(); 銀行家算法函數(shù) void main() input();safealg();banker();void input() II*int i,j;自定義進程數(shù)目與資源種類 *coutvv"*n" coutvv"*利用銀行家算法避免死鎖*n" coutvv"*n"cout<v"

11、*n" coutvv"請輸入進程的數(shù)目:"cin>>m;coutvv"請輸入資源的種類:"cin>>n;II*輸入每個進程對每種資源的最大需求、已經(jīng)獲得的數(shù) 量、每種類型資源的數(shù)目coutvv"各進程資源最大需求(Max),按照"vvmvv"x"vvnvv" 矩陣輸入:n"for(i=0;ivm;i+)coutvv"P"vvivv":"for(j=0;jvn;j+)cin»MAXij;if(j=n)coutvv&

12、quot;資源種類數(shù)匹配出現(xiàn)錯誤！ "/當(dāng)資源配置的種 類數(shù)大于預(yù)先輸入的數(shù)值時，出錯coutvv"各進程當(dāng)前獲得資源(Allocation),按照"vvm<v"x"vvnvv"矩陣輸入"vvendl;for(i=0;i<m;i+)coutvv"P"vvivv":"for(j=0;jvn;j+)cin»Allocationij;if(j=n)coutvv"資源種類數(shù)匹配出現(xiàn)錯誤！ "/當(dāng)資源配置的種 類數(shù)大于預(yù)先輸入的數(shù)值時，出錯Needij=

13、MAXij-Allocationij; 需求數(shù)等于最大 需求減去已經(jīng)分配數(shù)coutvv"系統(tǒng)可用資源(Available):"vvendl;for(j=0;jvn;j+)cin»Availablej;輸入各種資源的可利用數(shù)coutvv"當(dāng)前時刻的進程分配情況如圖：n"coutvv"進程號-"vv"MAX-"vv"Allocation-"vv"Need-"vv"Available-n" 顯示各進程的 資源情況for(i=0;ivm;i+)coutv

14、v"P"vvivv":"for(j=0;jvn;j+)coutvv" "vvMAXij;for(j=0;jvn;j+)coutvv" "vvAllocationij;coutvv""for(j=0;jvn;j+)coutvv" "vvNeedij;for(j=0;jvn;j+)coutvv" "vvAvailablej coutvvendl;/ 回車換行/*void banker() 銀行家算法，為進程分配資源*/int i,j;int choice;wh

15、ile(1)coutvvendl;coutvv"輸入要進行的操作(1:分配資源 2:離開):"用戶選擇cin»choice;if(choice=1) / 分配資源coutvv"從P0到P"vvm-lvv"之間選擇要分配資源的進程號:n"cin»i;if(i>=m)coutvv"無此進程號！請重新輸入:n"cin»i;重新輸入進程號coutvv"請輸入進程申請的資源(Request):"vvendl;for(j=0;jvn;j+)cin»Request

16、ij;/*銀行家算法進行檢杳*/for(j=0;jvn;j+)if(Requestij>Needij) coutvv"申請的資源大于它需要的資源數(shù)，請重 新輸入!n"/資源申請不合理continue;if(Requestij>Availablej)資源申請數(shù)目大于可利用數(shù)，無法分配，得等待 coutvv"當(dāng)前系統(tǒng)可用資源不夠，請等待!"vvendl;continue;for(j=0；jvn;j+)資源申請得到允許時，變換各個資源數(shù) Availablej=Availablej-Requestij;II 可用資源減少Allocationij=Al

17、locationij+Requestij; 所得資源增加Needij=Needij-Requestij;II 仍需資源減少if(safealg()v0)安全性算法的返回值coutvv"分配不成功，請等待！"；for (j=0;jvn;j+)把資源恢復(fù)成分配之前的狀態(tài)Availablej=Availablej+Requestij;Allocationij=Allocationij-Requestij; Needij=Needij+Requestij;for(i=0;ivm;i+) Finishi=False;/I沒有足夠的資源分配給該進程/if(safealg()v0)els

18、ecoutvv"同意分配請求!"vvendl;for(j=0;jvn;j+)Workj=Availablej;coutvv"進程號-"vv"-Work-"vv"Need-"vv"Allocation-"vv"Work+Allocation-" vv"Finish-"vvendl;for(i=0;ivm;i+)II按模擬分配序列進行分配coutvv"進程 P"vvSequenceivv":"for(j=0;jvn;j+

19、) coutvvWorkjvv""coutvv""for(j=0;jvn;j+) coutvvNeedSequenceijvv""coutvv""for(j=0;jvn;j+) coutvvAllocationSequenceijvv""coutvv""for(j=0；j<n;j+) coutvvAllocationSequenceij+Workjvv"" coutvv""coutvvFinishSequenceivv"

20、 "/完成該進程for(j=0;jvn;j+) Workj=AllocationSequenceij+Workj; 回收 該進程所分配的資源coutvvendl;/離開 /if(safealg()>=0) /if(choice=1) else if(choice=2)break;else coutvv*請輸入1或2!"/只認可1或2 /while(1)/*安全性算法*/int safealg()int i,j,k,l=0;/int WorkMAXn;/ 工作組/記錄序列for(i=0;ivn;i+)Worki=Availablei;/工作分配初始化為系統(tǒng)可用資源for

21、(i=0;ivm;i+)/掃描所有進程，預(yù)設(shè)所有進程不能運行Finishi=False;for(i=0;ivm;i+) /if(Finishi=True)continue;else /對于未運行的進程，進行如下處理/for(j=0;jvn;j+)/ 找到一個滿足 Finishi=false 且 Needijv=Workj的進程if(Needij>Workj)由于部分資源得不到滿足，進程i無法運行break;if(j=n)進程各類資源全部得到滿足Finishi=True;for(k=0;kvn;k+)進程i正常運行后，釋放其占有的資源Workk+=Allocationik;II 工作分配加

22、上可用資源Sequencel+=i; 模擬資源分配序列生成 i=-1;II重新掃描所有進程從i=0開始else 某一資源得不到滿足continue; /試探下一個進程/if(l=m)II都試探完畢coutvv"系統(tǒng)安全!"vvendl;coutvv"安全序列："for(i=0;ivl;i+)II輸出安全序列coutvv"進程 P"vvSequenceivv"-> " coutvvendl;return 0;IIcoutvv"系統(tǒng)進入不安全狀態(tài)！"vvendl;return -1;分析：輸入

23、各進程的可利用資源Available ，最大需求 MAX已分配資源 Allocation，需求資源Need,之后各系統(tǒng)發(fā)出資源請求Request，利用實驗中的安全性算法判斷能否產(chǎn)生一個安全性隊列，若能，則給該進程分配成功，否則，不予分配。在確定安全序列的過程中，要 檢測所有進程的Fini shi的值，每次循環(huán)檢測完后要重復(fù)從第一個進程開始。七、運行結(jié)果假設(shè)輸入進程個數(shù)為5,資源種類數(shù)為3,并以此輸入各進程初始時刻的各種資 源數(shù)量，如下*利用銀行家算法避免死鎖*雷輸入進程的數(shù)目汚訟按照E X3矩陣輸入:P0：4 5 7Pl：5 4 6P2：4 3 3P3：3 5 4P4；4 3 g各進程當(dāng)前獲得資源t Allocat ion,按照£ x3矩陣輸入2 31 21 12 11 0P0：2Pl：2P2：8P3：l系統(tǒng)可用