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

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

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

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

4、家算法設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，若Requestij=k;表示進(jìn)程需要j類資源k個(gè)。當(dāng)Pi發(fā)出資源請(qǐng)求時(shí)，系統(tǒng)按下屬步驟進(jìn)行檢查； 如果Requestij<=Needij;便轉(zhuǎn)向步驟（2），否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)他所宣布的最大值。如果 Requestij<=Availableij,便轉(zhuǎn)向步驟（3），否則認(rèn)為尚無(wú)足夠資源，進(jìn)程需等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程，并修改下面數(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)。若安全，才正式將資源分配給進(jìn)程 Pi，已完成此次分配。否則，將本次的試探分配作 廢，回復(fù)原來(lái)的資源分配狀態(tài)，將進(jìn)程Pi等待。2：安全性算法1）設(shè)置兩個(gè)向量；1 :工作向量Work,表示系統(tǒng)可提供給進(jìn)程運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，初始時(shí)Work=Available2 : Finish ,表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始 時(shí)先做 Finishi=true（2）從進(jìn)程中找到一個(gè)能滿需下屬條件的進(jìn)程1 ； Finishi=false ；2： Needij<=Workj

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

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

8、分配。五、流程圖設(shè)計(jì)訐始初始化後入Request大于Needfor j=0 to n-1耳請(qǐng)資源 大干Available是.申請(qǐng)資源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;/定義最大進(jìn)程數(shù)II定義最大資源數(shù)最大需求矩陣已分配矩陣可用資源數(shù)組II需求矩陣請(qǐng)求矩陣存儲(chǔ)完成資源分配的進(jìn)程II模擬的資源分

10、配序列系統(tǒng)是否有足夠的資源分配給進(jìn)程IIm個(gè)進(jìn)程,n個(gè)資源#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;自定義進(jìn)程數(shù)目與資源種類 *coutvv"*n" coutvv"*利用銀行家算法避免死鎖*n" coutvv"*n"cout<v"

11、*n" coutvv"請(qǐng)輸入進(jìn)程的數(shù)目:"cin>>m;coutvv"請(qǐng)輸入資源的種類:"cin>>n;II*輸入每個(gè)進(jìn)程對(duì)每種資源的最大需求、已經(jīng)獲得的數(shù) 量、每種類型資源的數(shù)目coutvv"各進(jìn)程資源最大需求(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)錯(cuò)誤！ "/當(dāng)資源配置的種 類數(shù)大于預(yù)先輸入的數(shù)值時(shí)，出錯(cuò)coutvv"各進(jìn)程當(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)錯(cuò)誤！ "/當(dāng)資源配置的種 類數(shù)大于預(yù)先輸入的數(shù)值時(shí)，出錯(cuò)Needij=

13、MAXij-Allocationij; 需求數(shù)等于最大 需求減去已經(jīng)分配數(shù)coutvv"系統(tǒng)可用資源(Available):"vvendl;for(j=0;jvn;j+)cin»Availablej;輸入各種資源的可利用數(shù)coutvv"當(dāng)前時(shí)刻的進(jìn)程分配情況如圖：n"coutvv"進(jìn)程號(hào)-"vv"MAX-"vv"Allocation-"vv"Need-"vv"Available-n" 顯示各進(jì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() 銀行家算法，為進(jìn)程分配資源*/int i,j;int choice;wh

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

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

17、locationij+Requestij; 所得資源增加Needij=Needij-Requestij;II 仍需資源減少if(safealg()v0)安全性算法的返回值coutvv"分配不成功，請(qǐng)等待！"；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沒(méi)有足夠的資源分配給該進(jìn)程/if(safealg()v0)els

18、ecoutvv"同意分配請(qǐng)求!"vvendl;for(j=0;jvn;j+)Workj=Availablej;coutvv"進(jìn)程號(hào)-"vv"-Work-"vv"Need-"vv"Allocation-"vv"Work+Allocation-" vv"Finish-"vvendl;for(i=0;ivm;i+)II按模擬分配序列進(jìn)行分配coutvv"進(jìn)程 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、 "/完成該進(jìn)程for(j=0;jvn;j+) Workj=AllocationSequenceij+Workj; 回收 該進(jìn)程所分配的資源coutvvendl;/離開 /if(safealg()>=0) /if(choice=1) else if(choice=2)break;else coutvv*請(qǐng)輸入1或2!"/只認(rèn)可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+)/掃描所有進(jìn)程，預(yù)設(shè)所有進(jìn)程不能運(yùn)行Finishi=False;for(i=0;ivm;i+) /if(Finishi=True)continue;else /對(duì)于未運(yùn)行的進(jìn)程，進(jìn)行如下處理/for(j=0;jvn;j+)/ 找到一個(gè)滿足 Finishi=false 且 Needijv=Workj的進(jìn)程if(Needij>Workj)由于部分資源得不到滿足，進(jìn)程i無(wú)法運(yùn)行break;if(j=n)進(jìn)程各類資源全部得到滿足Finishi=True;for(k=0;kvn;k+)進(jìn)程i正常運(yùn)行后，釋放其占有的資源Workk+=Allocationik;II 工作分配加

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

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