操作系統(tǒng)課程設(shè)計銀行家算法的模擬實現(xiàn)

1、操作系統(tǒng)課程設(shè)計（銀行家算法的模擬實現(xiàn)）1、 設(shè)計目的 1、進(jìn)一步了解進(jìn)程的并發(fā)執(zhí)行。 2、加強對進(jìn)程死鎖的理解。 3、用銀行家算法完成死鎖檢測。2、 設(shè)計內(nèi)容給出進(jìn)程需求矩陣C、資源向量R以及一個進(jìn)程的申請序列。使用進(jìn)程啟動拒絕和資源分配拒絕（銀行家算法）模擬該進(jìn)程組的執(zhí)行情況。3、 設(shè)計要求 1、初始狀態(tài)沒有進(jìn)程啟動。 2、計算每次進(jìn)程申請是否分配，如：計算出預(yù)分配后的狀態(tài)情況（安全狀態(tài)、不安全狀態(tài)），如果是安全狀態(tài)，輸出安全序列。 3、每次進(jìn)程申請被允許后，輸出資源分配矩陣A和可用資源向量V。 4、每次申請情況應(yīng)可單步查看，如：輸入一個空格，繼續(xù)下個申請。4、 算法原理 1、銀行家算法中

2、的數(shù)據(jù)結(jié)構(gòu)(1)、可利用資源向量Available，這是一個含有m個元素的數(shù)組，其中的每個元素代表一類可利用資源的數(shù)目， 其初始值是系統(tǒng)中所配置的該類全部資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。（2）、最大需求矩陣Max，這是一個n*m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）、分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)

3、程i當(dāng)前已經(jīng)分得Rj類資源的數(shù)目為K。（4）、需求矩陣Need。這也是一個n*m的矩陣，用以表示每個進(jìn)程尚需要的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。上述三個矩陣間存在以下關(guān)系：Needi,j=Maxi,j-Allocationi,j2、 銀行家算法應(yīng)用模擬實現(xiàn)Dijkstra的銀行家算法以避免死鎖的出現(xiàn)，分兩部分組成：一是銀行家算法（掃描）；二是安全性算法。 （1）銀行家算法（掃描） 設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requestij=K，表示進(jìn)程Pi需要K個Ri類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： 如果Req

4、uestij<=Needi,j，便轉(zhuǎn)向步驟；否則認(rèn)為出錯，因為它所需的資源數(shù)已經(jīng)超過了它所宣布的最大值。 如果Requestij<=Allocationi,j，便轉(zhuǎn)向步驟；否則表示尚無足夠資源，Pi需等待。 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。 Availablej=Available-Requestij； Allocationi,j=Allocationi,j+Requestij； Needi,j=Needi,j-Requestij； 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，已完成本次分配；否則，將

5、本次的試探分配作廢，恢復(fù)原來資源的分配狀態(tài)，讓進(jìn)程Pi等待。（2） 安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： 設(shè)置兩個向量：一個是工作向量Work；它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需要的各類資源的數(shù)目，它含有m個元素，在執(zhí)行安全性算法開始時，work=Available；另一個是Finish；它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做Finishi=false；當(dāng)有足夠資源分配給進(jìn)程時，再令Finishi=true； 從進(jìn)程集合中找到能滿足下述條件的進(jìn)程： 一是Finishi=false；二是Needi,j<=Workj；若找到，執(zhí)行步驟，否則，執(zhí)行步驟； 當(dāng)進(jìn)

6、程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj=Workj+Allocationi,j； Finishi=true； go to step； 如果所有進(jìn)程的 Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。5、 設(shè)計思路 1、進(jìn)程一開始向系統(tǒng)提出最大需求量； 2、進(jìn)程每次提出新的需求（分期貸款）都統(tǒng)計是否超出它事先提出的最大需求量； 3、若正常，則判斷該進(jìn)程所需剩余量（包括本次申請）是否超出系統(tǒng)所掌握的剩余資源量，若不超出，則分配，否則等待。六、 程序運行調(diào)試結(jié)果1、 程序初始化2、檢測系統(tǒng)資源分配是否安全結(jié)果7、 小結(jié)

7、“銀行家算法的模擬實現(xiàn)”是本學(xué)期操作系統(tǒng)課程的課程設(shè)計。在設(shè)計此程序的過程中我們遇到過許多問題也學(xué)到了很多東西。通過這周的課程設(shè)計，我加深了對銀行家算法的理解，掌握了銀行家算法避免死鎖的過程和方法，理解了死鎖產(chǎn)生的原因和條件以及避免死鎖的方法。所編寫程序基本實現(xiàn)了銀行家算法的功能，并在其基礎(chǔ)上考慮了輸出顯示格式的美觀性，使界面盡可能友好。并且在編程時將主要的操作都封裝在函數(shù)中，這樣使程序可讀性增強，使程序更加清晰明了。在算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計上考慮了很長時間。在程序設(shè)計中先后參考了很多網(wǎng)絡(luò)資料也參考了一些別人寫的的程序綜合這些算法思想和自己的思路對程序做了很好的設(shè)計方式對一些算法的優(yōu)越性等也作了一

8、些考慮。當(dāng)然，在編寫和調(diào)試過程中我遇到了許多的問題，通過網(wǎng)上查詢資料、翻閱課本、向同學(xué)請教、多次調(diào)試等方法逐漸解決了大部分問題。讓我收獲很多，相信在今后的生活中也有一定幫助。附：程序源代碼：#include <stdio.h>#include <stdlib.h>#include <conio.h> # define m 50 int no1; /進(jìn)程數(shù)int no2; /資源數(shù)int r;int allocationmm,needmm,availablem,maxmm; char name1m,name2m; /定義全局變量void main()void

9、check();void print();int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm,available1m;printf("*n");printf("* 銀行家算法的設(shè)計與實現(xiàn) *n"); printf("*n");printf("請輸入進(jìn)程總數(shù):n");scanf("%d",&no1);printf("請輸入資源種類數(shù):n");scanf("%d",&no2); p

10、rintf("請輸入Max矩陣:n");for(i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&maxij); /輸入已知進(jìn)程最大資源需求量printf("請輸入Allocation矩陣:n");for(i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&allocationij); /輸入已知的進(jìn)程已分配的資源數(shù) for(i=0;i<no1;i+)for(j=0;j<no2;j+)needij=

11、maxij-allocationij; /根據(jù)輸入的兩個數(shù)組計算出need矩陣的值 printf("請輸入Available矩陣n");for(i=0;i<no2;i+)scanf("%d",&availablei); /輸入已知的可用資源數(shù)print(); /輸出已知條件check(); /檢測T0時刻已知條件的安全狀態(tài)if(r=1) /如果安全則執(zhí)行以下代碼do q=0; p=0;printf("n請輸入請求資源的進(jìn)程號(04)：n");for(j=0;j<=10;j+)scanf("%d"

12、,&i);if(i>=no1)printf("輸入錯誤，請重新輸入：n"); continue; else break;printf("n請輸入該進(jìn)程所請求的資源數(shù)requestj:n");for(j=0;j<no2;j+)scanf("%d",&requestj);for(j=0;j<no2;j+)if(requestj>needij) p=1; /判斷請求是否超過該進(jìn)程所需要的資源數(shù)if(p)printf("請求資源超過該進(jìn)程資源需求量，請求失?。");elsefor(

13、j=0;j<no2;j+)if(requestj>availablej) q=1; /判斷請求是否超過可用資源數(shù)if(q) printf("沒有做夠的資源分配，請求失?。");else /請求滿足條件for(j=0;j<no2;j+) available1j=availablej; allocation1ij=allocationij;need1ij=needij; /保存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)availablej=availablej-requestj; allocationij+=requestj;needij=needij-

14、requestj; /系統(tǒng)嘗試把資源分配給請求的進(jìn)程print();check(); /檢測分配后的安全性if(r=0) /如果分配后系統(tǒng)不安全for(j=0;j<no2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij; /還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)printf("返回分配前資源數(shù)n");print();printf("n你還要繼續(xù)分配嗎？Y or N ?n"); /判斷是否繼續(xù)進(jìn)行資源分配c=getche();while(c='

15、;y'|c='Y');void check() /安全算法函數(shù)int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;i<no1;i+)finishi=false; / 初始化進(jìn)程均沒得到足夠資源數(shù)并完成for(i=0;i<no2;i+) worki=availablei;/worki表示可提供進(jìn)程繼續(xù)運行的各類資源數(shù)k=no1;dofor(i=0;i<no1;i+)if(finishi=false)f=1;for(j=0;j<no2;j+)if(needij>workj)f=0;if(f

16、=1) /找到還沒有完成且需求數(shù)小于可提供進(jìn)程繼續(xù)運行的資源數(shù)的進(jìn)程finishi=true;av+=i; /記錄安全序列號for(j=0;j<no2;j+)workj+=allocationij; /釋放該進(jìn)程已分配的資源k-; /每完成一個進(jìn)程分配，未完成的進(jìn)程數(shù)就減1while(k>0);f=1;for(i=0;i<no1;i+) /判斷是否所有的進(jìn)程都完成if(finishi=false) f=0;break;if(f=0) /若有進(jìn)程沒完成，則為不安全狀態(tài)printf("系統(tǒng)處在不安全狀態(tài)！");r=0;elseprintf("n系統(tǒng)當(dāng)

17、前為安全狀態(tài)，安全序列為：n");for(i=0;i<no1;i+)printf("p%d ",ai); /輸出安全序列void print() /輸出函數(shù)int i,j;printf("n");printf("*此時刻資源分配情況*n");printf("進(jìn)程名/號 | Max | Allocation | Need |n"); for (i = 0; i < no1; i+)printf(" p%d/%d ",i,i); for (j = 0; j < no2; j+) printf("%d ",maxij);for (j = 0; j < no2; j