銀行家算法課程設(shè)計(jì)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上銀行家算法一 需求分析1. 在多道程序系統(tǒng)中，多個進(jìn)程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖(Deadlock)，是指多個進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局（DeadlyEmbrace），當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無外力作用，他們都無法在向前推進(jìn)。  要預(yù)防死鎖，有摒棄“請求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件等方法。 但是，在預(yù)防死鎖的幾種方法之中，都施加了較強(qiáng)的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)狀態(tài)分

2、為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。 而最具代表性的避免死鎖的算法，便是Dijkstra的銀行家算法。 利用銀行家算法，我們可以來檢測CPU為進(jìn)程分配資源的情況，決定CPU是否響應(yīng)某進(jìn)程的的請求并為其分配資源，從而很好避免了死鎖的產(chǎn)生。2. 銀行家算法是一種最有代表性的避免死鎖的算法。    要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。   安全狀態(tài)：如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。    不安

3、全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。   那么什么是安全序列呢？ 安全序列：一個進(jìn)程序列P1，Pn是安全的，如果對于每一個進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。   銀行家算法： 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時(shí)，要測試該

4、進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。3.設(shè)計(jì)要求：設(shè)計(jì)一n個并發(fā)進(jìn)程共享m個系統(tǒng)資源的程序?qū)崿F(xiàn)銀行家算法。要求包括： （1） 簡單的初始化界面； （2） 系統(tǒng)資源的占用和剩余情況； （3） 為進(jìn)程分配資源，用銀行家算法

5、對其進(jìn)行檢測，分為以下三種情況：        A. 所申請的資源大于其所需資源，提示分配不合理不予分配并返回；         B. 所申請的資源未大于其所需資源，但大于系統(tǒng)此時(shí)的可利用資源，提示分配不合理不予分配并返回；  C. 所申請的資源未大于其所需資源，亦未大于系統(tǒng)此時(shí)的可利用資源，預(yù)分配并進(jìn)行安全性檢查：     &

6、#160;  a. 預(yù)分配后系統(tǒng)是安全的，將該進(jìn)程所申請的資源予以實(shí)際分配并打印后返回；        b. 與分配后系統(tǒng)進(jìn)入不安全狀態(tài)，提示系統(tǒng)不安全并返回； （4） 對輸入進(jìn)行檢查，即若輸入不符合條件，應(yīng)當(dāng)報(bào)錯并返回重新輸入； （5） 撤銷作業(yè)，釋放資源。二概要設(shè)計(jì)（一）算法思路： 先對用戶提出的請求進(jìn)行合法性檢查，即檢查請求是否大于需要的，是否大于可利用的。若請求合法，則進(jìn)行預(yù)分配，對分配后的狀態(tài)調(diào)用安全性算法進(jìn)行檢查。若安全，則

7、分配；若不安全，則拒絕申請，恢復(fù)到原來的狀態(tài)，拒絕申請。(二)算法步驟：（1）如果Requestior =Need,則轉(zhuǎn)向步驟(2)；否則，認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 （2）如果Requestor=Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無足夠的資源，進(jìn)程必須等待。 （3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的值：Available=Available-Requesti;      Allocation=Allocation+Request;

8、    Need=Need-Request; (4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。三詳細(xì)設(shè)計(jì)#define SIZE 11int availableSIZE; int claimSIZESIZE;int allocationSIZESIZE;int needSIZESIZE;int requestSIZESIZE = 0 ;/記錄某個進(jìn)程申請各個資源類中的資源實(shí)例的數(shù)量 int finishSIZE = 0 ;/工作變量，用于判斷進(jìn)程是否已經(jīng)執(zhí)行過，初始狀態(tài)全部為0，即未執(zhí)行 int pSIZE;/記錄序列執(zhí)行順序 int

9、 ava;/記錄系統(tǒng)有多少個資源類 int process;/記錄進(jìn)程數(shù)量int r;/記錄當(dāng)前要申請資源的進(jìn)程的序號 int key = 1;這部分程序一開始定義了程序所需要的矩陣，資源類，進(jìn)程數(shù)等等，用來記錄進(jìn)程資源的分配情況，可見的顯示了銀行家算法。void showdate();void allot();int init();int check();這些事主函數(shù)運(yùn)行時(shí)所要調(diào)用的函數(shù)，首先要調(diào)用的是init（）函數(shù)，這個函數(shù)初始化了claimSIZESIZE矩陣和allocationSIZESIZE矩陣，初始化成功以后就開始給進(jìn)程分配資源，開始調(diào)用allot()函數(shù)，銀行家算法的核心之一

10、就是進(jìn)行資源類的分配，下面是分配的過程： 試分配->進(jìn)行安全性檢測->分配成功當(dāng)然，進(jìn)行安全性檢測后，如果不安全，我們要記得數(shù)據(jù)重置，也是資源的回收。for (i = 0; i < ava; i+)/假設(shè)分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check() = 0 )/安全檢測 printf("安全檢測失敗,可能發(fā)生死鎖,數(shù)據(jù)重置n");fo

11、r (i = 0; i < ava; i+)/重置數(shù)據(jù) availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + requestri;elseint key = 0;for (j = 0; j < ava; j+)if (needrj = 0)key+;if (key = ava)for (j = 0; j < ava; j+)availablej += allocationrj;allocationrj = 0;printf("n進(jìn)程順

12、利執(zhí)行.nn");return;如果安全檢測時(shí)安全的，則程序就會找出一個安全的序列，例如：p0,p1,p2,p3,p4。此程序在找安全序列的時(shí)候每次都是從頭開始找的for (i = 0; i < process; i+)for (j = 0; j < ava; j+)/尋找條件 Needi<=Worki if (needij > workj)break;if (j = ava) && (finishi = 0)/尋找條件 Finishi=false ，每次從頭開始找安全序列finishi = 1;for (k = 0; k < ava;

13、k+)workk = workk + allocationik;pl = i;/記錄安全序列 l+;/i = -1;/重置i，為了尋找安全序列 elsecontinue;if (l = process)/可以找到安全序列，輸出并結(jié)束 printf("n系統(tǒng)安全!n");printf("安全序列為：");for (k = 0; k < l; k+)printf("P(%d)", pk);if (k != l - 1)printf("->");return 1;printf("n系統(tǒng)不安全，不能滿

14、足你的要求！n");return 0;最后一步是調(diào)用顯示函數(shù)showdate()函數(shù)，此函數(shù)讓我們更加直觀的看到銀行家算法的運(yùn)行過程，printf("P(%d) ", i);for (j = 0; j < ava; j+)printf("%d ", claimij);printf("n");printf("nAllocationn");printf(" ");ava_xh();for (i = 0; i < process; i+)printf("P(%d) &q

15、uot;, i);for (j = 0; j < ava; j+)printf("%d ", allocationij);printf("n");printf("nNeedn");printf(" ");ava_xh();for (i = 0; i < process; i+)printf("P(%d) ", i);for (j = 0; j < ava; j+)printf("%d ", needij);printf("n");prin

16、tf("nAvailablen");ava_xh();for (i = 0; i < ava; i+)printf("%d ", availablei);顯示了分配資源過后的needSIZESIZE矩陣和availableSIZE和allocationSIZESIZE矩陣。四測試初始化輸入：正常的分配成功，及其安全序列：請求的資源造成了系統(tǒng)的不安全，存在安全隱患：五總結(jié)在銀行家算法這個系統(tǒng)之中，所采用的數(shù)據(jù)結(jié)構(gòu)應(yīng)是最基本的部分。銀行家算法的數(shù)據(jù)結(jié)構(gòu)我們采用了一維數(shù)組與二維數(shù)組來存儲，比如已分配資源數(shù)allocation 、仍需求資源數(shù)ne

17、ed 、以及系統(tǒng)可利用的資源數(shù)available 、申請各類資源request 、進(jìn)程個數(shù)r 等數(shù)組,其中每一個進(jìn)程還使用了結(jié)構(gòu)體。 數(shù)據(jù)結(jié)構(gòu)雖然重要但卻只是基礎(chǔ)，而最主要的用以實(shí)現(xiàn)系統(tǒng)功能的應(yīng)該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統(tǒng)的安全性。 安全性檢測我們是用check( )函數(shù)來實(shí)現(xiàn)的。 除此之外，在程序當(dāng)中，我們也得強(qiáng)調(diào)一下對輸入的合法性的判斷。比如，我們輸入的欲申請資源的進(jìn)程號沒有在系統(tǒng)已存在的進(jìn)程當(dāng)中，或者進(jìn)程號定義為整型，但是卻錯輸成字母等情況，我們需要對這些情況進(jìn)行判斷，讓程

18、序報(bào)錯返回而并非因錯誤而中斷。 這樣的情況處理起來比較麻煩，相當(dāng)于對每次輸入針對各種不同的情況都得做判斷。我也沒有涵蓋全部的輸入，僅僅只是對輸入的進(jìn)程號不在已存在進(jìn)程當(dāng)中、以及輸入的操作選擇不存在兩種情況分別作了判斷，并且針對第二種情況設(shè)定了五次輸入錯誤的話系統(tǒng)關(guān)閉的功能。而因?yàn)閷τ谀承┍热邕M(jìn)程號本來設(shè)定就是整型，因此對輸入的是字母的判別因比較復(fù)雜而未能加上。設(shè)計(jì)的存在著以下不足：一、不能實(shí)現(xiàn)并發(fā)操作，即當(dāng)總資源同時(shí)滿足幾個進(jìn)程所需要的資源數(shù)時(shí)，這些進(jìn)程不能同時(shí)進(jìn)行，只能一一按進(jìn)程順序執(zhí)行。二、掃描進(jìn)程順序單一，只能按進(jìn)程到來的順序（即編號）來掃描，從而產(chǎn)生的安全順序只能是在這個順序

19、的基礎(chǔ)上產(chǎn)生的，而其實(shí)安全順序是有多個的。三、對進(jìn)程數(shù)和資源數(shù)進(jìn)行的數(shù)量進(jìn)行了限制，都只能最多有十個。四、運(yùn)行程序后，界面較差，進(jìn)程數(shù)，所需要資源數(shù)，已分配資源數(shù)，能用資源數(shù)，不能一目了然。 總之，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來學(xué)習(xí)借鑒。附錄：程序代碼：#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <windows.h>#define SIZE 11int a

20、vailableSIZE; int claimSIZESIZE;int allocationSIZESIZE;int needSIZESIZE;int requestSIZESIZE = 0 ;/記錄某個進(jìn)程申請各個資源類中的資源實(shí)例的數(shù)量 int finishSIZE = 0 ;/工作變量，用于判斷進(jìn)程是否已經(jīng)執(zhí)行過，初始狀態(tài)全部為0，即未執(zhí)行 int pSIZE;/記錄序列執(zhí)行順序 int ava;/記錄系統(tǒng)有多少個資源類 int process;/記錄進(jìn)程數(shù)量int r;/記錄當(dāng)前要申請資源的進(jìn)程的序號 int key = 1;void showdate();void allot();i

21、nt init();int check();void ava_xh()/輸出資源序號 int k;for (k = 0; k < ava; k+)printf("%c ", k + 65);printf("n");int main(void)int t;char ch;while (1)/聲明循環(huán) system("cls");t = init();if (t = 1)break;do/資源申請循環(huán) allot();showdate();printf("還要申請對進(jìn)程分配資源嗎？(請按Y鍵):");scanf(

22、" %c", &ch); while (ch = 'y' | ch = 'Y');return 0;int init()int i, j, k;printf("請輸入資源類數(shù)量(1-%d)：", SIZE);while (1)scanf("%d", &ava);if (ava <= SIZE) && (ava >= 1)break;printf("輸入錯誤，請重新輸入：");printf("請依次輸入各資源類的個數(shù)（中間用空格分開

23、）：n");while (1)ava_xh();for (i = 0; i < ava; i+)scanf("%d", &availablei);for (i = 0; i < ava; i+)if (availablei < 0) | (availablei > )printf("有錯誤的輸入,重新開始吧。n");break;if (i = ava)break;printf("請輸入進(jìn)程數(shù)量：", SIZE);while (1)scanf("%d", &proce

24、ss);if (process <= SIZE) && (process >= 1)break;printf("輸入錯誤，請重新輸入：");printf("=n");for (i = 0; i < process; i+)/輸入及檢測進(jìn)程所需各類資源的資源實(shí)例最大量printf("請輸入進(jìn)程P(%d)所需各類資源的資源最大量Max:n", i);ava_xh();for (j = 0; j < ava; j+)scanf("%d", &claimij);for (j

25、= 0; j < ava; j+)if (claimij > availablej)printf("有數(shù)據(jù)超過系統(tǒng)實(shí)例最大量，退出)。nnnn");system("pause");getchar();return 0;/輸入及檢測進(jìn)程占有各資源類中資源實(shí)例的數(shù)量printf("請輸入進(jìn)程P(%d)已分配各類資源的數(shù)量Allocation:n", i);ava_xh();for (j = 0; j < ava; j+)scanf("%d", &allocationij);for (j = 0

26、; j < ava; j+)if (claimij < allocationij)printf("有數(shù)據(jù)超過進(jìn)程所需資源最大量。nnnn");system("pause");getchar();return 0;/輸入進(jìn)程還需各個資源類中資源實(shí)例的數(shù)量printf("下面是進(jìn)程P(%d)還需各個資源類中資源的數(shù)量Need:n", i);ava_xh();for (j = 0; j < ava; j+)needij = claimij - allocationij;printf("%d ", cla

27、imij - allocationij);printf("n=n");printf("n下面是目前系統(tǒng)剩余的各個資源類的實(shí)例數(shù)量：n");ava_xh();for (i = 0; i < ava; i+)for (j = 0; j < process; j+)availablei = availablei - allocationji;printf("%d ", availablei);printf("n=n");if (check() = 0)/安全檢測 printf("安全檢測失敗,可能發(fā)

28、生死鎖,數(shù)據(jù)重置n");for (i = 0; i < ava; i+)/重置數(shù)據(jù) availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + requestri;elseprintf("n進(jìn)程順利執(zhí)行.nn");showdate();return 1;void allot()int i, j, k;printf("n請輸入當(dāng)前要申請資源的進(jìn)程的序號(0-%d):", process - 1);while (1)

29、scanf("%d", &r);if (r <= process - 1) && (r >= 0)break;printf("輸入錯誤，請重新輸入：");printf("請輸入要申請的各個資源實(shí)例的數(shù)量：n");ava_xh();for (j = 0; j < ava; j+)scanf("%d", &requestrj);for (i = 0; i < ava; i+)if (requestri > needri)printf("n申請資源量

30、超過所聲明的最大資源需求量Maxn");return;for (i = 0; i < ava; i+)if (requestri > availablei)printf("剩余資源實(shí)例不足，需要等待,重來一次.n");return;for (i = 0; i < ava; i+)/假設(shè)分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check

31、() = 0 )/安全檢測 printf("安全檢測失敗,可能發(fā)生死鎖,數(shù)據(jù)重置n");for (i = 0; i < ava; i+)/重置數(shù)據(jù) availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + requestri;elseint key = 0;for (j = 0; j < ava; j+)if (needrj = 0)key+;if (key = ava)for (j = 0; j < ava; j+)avail

32、ablej += allocationrj;allocationrj = 0;printf("n進(jìn)程順利執(zhí)行.nn");return;int check()int i, j, k, l = 0;int workSIZE = 0 ;/工作數(shù)組 for (i = 0; i < ava; i+)/初始化 worki = availablei;for (i = 0; i < process; i+) /初始化 finishi = 0;for (i = 0; i < process; i+)for (j = 0; j < ava; j+)/尋找條件 Needi<=Worki if (needij > workj)break;if (j = ava) && (finishi = 0)/尋找條件 Finishi=false ，每次從頭開始找安全序列finishi = 1;for (k = 0; k < ava; k+)workk = workk + allocationik;pl = i;/記錄安全序列 l+;/i = -1;/重置i，為了尋找安全序列 elseco