銀行家算法課程設計報告

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

2、死鎖的算法，便是dijkstra的銀行家算法。利用銀行家算法，我們可以來檢測cpu為進程分配資源的情況，決定cpu是否響應某進程的的請求并為其分配資源，從而很好避免了死鎖的產生。2. 銀行家算法是一種最有代表性的避免死鎖的算法。 要解釋銀行家算法，必須先解釋操作系統安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果存在一個由系統中所有進程構成的安全序列p1，pn，則系統處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。 不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。那么什么是安全序列呢？安全序列：一個進程序列p1，pn是安全的，如果對于每一個進程pi(1in），它以后尚需要的資源量不超過系統當前剩余資源

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

4、vailablei + 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);return;如果安全檢測時安全的，則程序就會找出一個安全的序列，例如：p0,p1,p2,p3,p4。此程

5、序在找安全序列的時候每次都是從頭開始找的for (i = 0; i process; i+)for (j = 0; j ava; j+)/尋找條件 needi 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，為了尋找安全序列 elsecontinue;if (l = process)/可以找到安全序列，輸出并結束

6、printf(n系統安全!n);printf(安全序列為：);for (k = 0; k );return 1;printf(n系統不安全，不能滿足你的要求！n);return 0;最后一步是調用顯示函數showdate()函數，此函數讓我們更加直觀的看到銀行家算法的運行過程，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 (j

7、 = 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(navailablen);ava_xh();for (i = 0; i ava; i+)printf(%d , availablei);顯示了分配資源過后的needsizesize矩陣和availablesize和allo

8、cationsizesize矩陣。四測試初始化輸入：正常的分配成功，及其安全序列：請求的資源造成了系統的不安全，存在安全隱患：五總結在銀行家算法這個系統之中，所采用的數據結構應是最基本的部分。銀行家算法的數據結構我們采用了一維數組與二維數組來存儲，比如已分配資源數allocation、仍需求資源數need、以及系統可利用的資源數available、申請各類資源request、進程個數r等數組,其中每一個進程還使用了結構體。數據結構雖然重要但卻只是基礎，而最主要的用以實現系統功能的應該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統的安全性。安全性檢測我們是用check()函數來實

9、現的。除此之外，在程序當中，我們也得強調一下對輸入的合法性的判斷。比如，我們輸入的欲申請資源的進程號沒有在系統已存在的進程當中，或者進程號定義為整型，但是卻錯輸成字母等情況，我們需要對這些情況進行判斷，讓程序報錯返回而并非因錯誤而中斷。這樣的情況處理起來比較麻煩，相當于對每次輸入針對各種不同的情況都得做判斷。我也沒有涵蓋全部的輸入，僅僅只是對輸入的進程號不在已存在進程當中、以及輸入的操作選擇不存在兩種情況分別作了判斷，并且針對第二種情況設定了五次輸入錯誤的話系統關閉的功能。而因為對于某些比如進程號本來設定就是整型，因此對輸入的是字母的判別因比較復雜而未能加上。設計的存在著以下不足：一、不能實現

10、并發(fā)操作，即當總資源同時滿足幾個進程所需要的資源數時，這些進程不能同時進行，只能一一按進程順序執(zhí)行。二、掃描進程順序單一，只能按進程到來的順序（即編號）來掃描，從而產生的安全順序只能是在這個順序的基礎上產生的，而其實安全順序是有多個的。三、對進程數和資源數進行的數量進行了限制，都只能最多有十個。四、運行程序后，界面較差，進程數，所需要資源數，已分配資源數，能用資源數，不能一目了然?？傊?，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來學習借鑒。附錄：程序代碼：#define _crt_secure_no_warnings#include #include #include #i

11、nclude #define size 11int availablesize; int claimsizesize;int allocationsizesize;int needsizesize;int requestsizesize = 0 ;/記錄某個進程申請各個資源類中的資源實例的數量 int finishsize = 0 ;/工作變量，用于判斷進程是否已經執(zhí)行過，初始狀態(tài)全部為0，即未執(zhí)行 int psize;/記錄序列執(zhí)行順序 int ava;/記錄系統有多少個資源類 int process;/記錄進程數量int r;/記錄當前要申請資源的進程的序號 int key = 1;voi

12、d showdate();void allot();int 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(還要申請對進程分配資源嗎？(請按y鍵):);scanf( %c, &ch); while (ch = y |

13、 ch = y);return 0;int init()int i, j, k;printf(請輸入資源類數量(1-%d)：, size);while (1)scanf(%d, &ava);if (ava = 1)break;printf(輸入錯誤，請重新輸入：);printf(請依次輸入各資源類的個數（中間用空格分開）：n);while (1)ava_xh();for (i = 0; i ava; i+)scanf(%d, &availablei);for (i = 0; i ava; i+)if (availablei 2147483647)printf(有錯誤的輸入,重新開始吧。n);b

14、reak;if (i = ava)break;printf(請輸入進程數量：, size);while (1)scanf(%d, &process);if (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; j availablej)printf(有數

15、據超過系統實例最大量，退出)。nnnn);system(pause);getchar();return 0;/輸入及檢測進程占有各資源類中資源實例的數量printf(請輸入進程p(%d)已分配各類資源的數量allocation:n, i);ava_xh();for (j = 0; j ava; j+)scanf(%d, &allocationij);for (j = 0; j ava; j+)if (claimij allocationij)printf(有數據超過進程所需資源最大量。nnnn);system(pause);getchar();return 0;/輸入進程還需各個資源類中資源實

16、例的數量printf(下面是進程p(%d)還需各個資源類中資源的數量need:n, i);ava_xh();for (j = 0; j ava; j+)needij = claimij - allocationij;printf(%d , claimij - allocationij);printf(n=n);printf(n下面是目前系統剩余的各個資源類的實例數量：n);ava_xh();for (i = 0; i ava; i+)for (j = 0; j process; j+)availablei = availablei - allocationji;printf(%d , avai

17、lablei);printf(n=n);if (check() = 0)/安全檢測 printf(安全檢測失敗,可能發(fā)生死鎖,數據重置n);for (i = 0; i ava; i+)/重置數據 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):

18、, process - 1);while (1)scanf(%d, &r);if (r = 0)break;printf(輸入錯誤，請重新輸入：);printf(請輸入要申請的各個資源實例的數量：n);ava_xh();for (j = 0; j ava; j+)scanf(%d, &requestrj);for (i = 0; i needri)printf(n申請資源量超過所聲明的最大資源需求量maxn);return;for (i = 0; i availablei)printf(剩余資源實例不足，需要等待,重來一次.n);return;for (i = 0; i ava; i+)/假設

19、分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check() = 0 )/安全檢測 printf(安全檢測失敗,可能發(fā)生死鎖,數據重置n);for (i = 0; i ava; i+)/重置數據 availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + req

20、uestri;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);return;int check()int i, j, k, l = 0;int worksize = 0 ;/工作數組 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 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，為了尋找安全序列 else