銀行家算法課程設計報告

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

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

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

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

5、情況：        A. 所申請的資源大于其所需資源，提示分配不合理不予分配并返回；         B. 所申請的資源未大于其所需資源，但大于系統(tǒng)此時的可利用資源，提示分配不合理不予分配并返回；  C. 所申請的資源未大于其所需資源，亦未大于系統(tǒng)此時的可利用資源，預分配并進行安全性檢查：       &#

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

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

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

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

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

11、lt; 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進程順利執(zhí)行.nn")

12、;return;如果安全檢測時安全的，則程序就會找出一個安全的序列，例如：p0,p1,p2,p3,p4。此程序在找安全序列的時候每次都是從頭開始找的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 = wo

13、rkk + allocationik;pl = i;/記錄安全序列 l+;/i = -1;/重置i，為了尋找安全序列 elsecontinue;if (l = process)/可以找到安全序列，輸出并結束 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)不安全，不能滿足你的要求！n"

14、);return 0;最后一步是調(diào)用顯示函數(shù)showdate()函數(shù)，此函數(shù)讓我們更加直觀的看到銀行家算法的運行過程，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) ", i);for

15、(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");printf("nAva

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

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

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

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

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

21、 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("還要申請對進程分配資源嗎？(請按Y鍵):");scanf(" %c&quo

22、t;, &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ù)（中間用空格分開）：n");wh

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

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

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

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

27、j - allocationij);printf("n=n");printf("n下面是目前系統(tǒng)剩余的各個資源類的實例數(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進程順利執(zhí)行.nn");showdate();return 1;void allot()int i, j, k;printf("n請輸入當前要申請資源的進程的序號(0-%d):", process - 1);while (1)sca

29、nf("%d", &r);if (r <= process - 1) && (r >= 0)break;printf("輸入錯誤，請重新輸入：");printf("請輸入要申請的各個資源實例的數(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("剩余資源實例不足，需要等待,重來一次.n");return;for (i = 0; i < ava; i+)/假設分配 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+)availabl

32、ej += allocationrj;allocationrj = 0;printf("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，為了尋找安全序列