| 一、設計目的 1 、了解多道程式系統中，多個程序并發執行的資源配置設定。 2 、掌握死鎖的産生的原因、産生死鎖的必要條件和處理死鎖的基本方法。 3 、掌握預防死鎖的方法，系統安全狀态的基本概念。 4 、掌握銀行家算法，了解資源在程序并發執行中的資源配置設定政策。 5 、了解死鎖避免在目前計算機系統不常使用的原因。 二、設計任務 ① 在 Window98/2000 系統的 TC2.0 環境下運作程式； ② 通過最有代表性的避免死鎖的算法 (Dijkstra) 的銀行家算法程式實作來了解程序并發中的資源配置設定，死鎖避免在死鎖解決中的可行性； ③ 設計程式在自動、手動方式下運作，了解銀行家算法的實質。 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 三、設計内容與步驟 A 、銀行家算法設計的知識準備 。 1 、死鎖概念。 在多道程式系統中，雖可借助于多個程序的并發執行，來改善系統的資源使用率，提高系統的吞吐量，但可能發生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個程序在運作中因争奪資源而造成的一種僵局(Deadly_Embrace),當程序處于這種僵持狀态時，若無外力作用，它們都将無法再向前推進。一組程序中，每個程序都無限等待被該組程序中另一程序所占有的資源，因而永遠無法得到的資源，這種現象稱為程序死鎖，這一組程序就稱為死鎖程序 。 2 、關于死鎖的一些結論： Ø 參與死鎖的程序最少是兩個 Ø （兩個以上程序才會出現死鎖） Ø 參與死鎖的程序至少有兩個已經占有資源 Ø 參與死鎖的所有程序都在等待資源 Ø 參與死鎖的程序是目前系統中所有程序的子集 注：如果死鎖發生，會浪費大量系統資源，甚至導緻系統崩潰。 3 、資源分類。永久性資源： 可以被多個程序多次使用（可再用資源） l 可搶占資源 l 不可搶占資源 臨時性資源：隻可使用一次的資源；如信号量,中斷信号，同步信号等（可消耗性資源） “申請--配置設定--使用--釋放”模式 4 、産生死鎖的四個必要條件 ：互斥使用（資源獨占）、不可強占（不可剝奪）、請求和保持（部分配置設定，占有申請）、循環等待。 1) 互斥使用（資源獨占） 一個資源每次隻能給一個程序使用 2) 不可強占（不可剝奪） 資源申請者不能強行的從資源占有者手中奪取資源，資源隻能由占有者自願釋放 3) 請求和保持（部分配置設定，占有申請） 一個程序在申請新的資源的同時保持對原有資源的占有（隻有這樣才是動态申請，動态配置設定） 4) 循環等待存在一個程序等待隊列 {P1 , P2 , … , Pn}, 其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個程序等待環路 5、 死鎖的解決方案5.1 産生死鎖的例子 申請不同類型資源産生死鎖 P1： … 申請列印機 申請掃描器 使用 釋放列印機 釋放掃描器 … P2： … 申請掃描器 申請列印機 使用 釋放列印機 釋放掃描器 … 申請同類資源産生死鎖（如記憶體） 設有資源R，R有m個配置設定機關，由n個程序P1,P2,…,Pn（n > m）共享。假設每個程序對R的申請和釋放符合下列原則： * 一次隻能申請一個機關 * 滿足總申請後才能使用 * 使用完後一次性釋放 m=2，n=3 資源配置設定不當導緻死鎖産生 5.2死鎖預防: 定義:在系統設計時确定資源配置設定算法，保證不發生死鎖。具體的做法是破壞産生死鎖的四個必要條件之一 ①破壞“不可剝奪”條件 在允許程序動态申請資源前提下規定，一個程序在申請新的資源不能立即得到滿足而變為等待狀态之前，必須釋放已占有的全部資源，若需要再重新申請 ②破壞“請求和保持”條件 要求每個程序在運作前必須一次性申請它所要求的所有資源，且僅當該程序所要資源均可滿足時才給予一次性配置設定 ③破壞“循環等待”條件 采用資源有序配置設定法： 把系統中所有資源編号，程序在申請資源時必須嚴格按資源編号的遞增次序進行，否則作業系統不予配置設定 6．安全狀态與不安全狀态 安全狀态： 如果存在一個由系統中所有程序構成的安全序列P1，…Pn，則系統處于安全狀态。一個程序式列{P1，…，Pn}是安全的，如果對于每一個程序Pi(1≤i≤n），它以後尚需要的資源量不超過系統目前剩餘資源量與所有程序Pj (j < i )目前占有資源量之和，系統處于安全狀态 (安全狀态一定是沒有死鎖發生的) 不安全狀态:不存在一個安全序列，不安全狀态一定導緻死鎖。 B、銀行家算法 一、銀行家算法中的資料結構1．可利用資源向量Available 它是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源數目。其數值随該類資源的配置設定和回收而動态地改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。 2．最大需求短陣Max 這是—個n×m的矩陣，它定義了系統中n個程序中的每一個程序對m類資源的最大需求。如果Max(i，j)＝K，表示程序i需要Rj類資源的最大數目為K。 3．配置設定短陣Allocation 這是一個n×m的矩陣，它定義了系統中每一類資源目前已配置設定給每個程序的資源數。如果Allocation(i,j)＝K，表示程序i目前已分得Rj類資源的數目為K。 4．需求矩陣Need 它是一個n×m的矩陣，用以表示每一個程序尚需的各類資源數，如果Need[i,j]=K，則表示程序i還需要Rj類資源k個，方能完成其任務。 上述三個矩陣間存在下述關系： Need[i,j]=Max[i,j]-Allocation[i,j] 二、銀行家算法設Requesti是程序Pi的請求向量。如果Requesti[j]＝k，表示程序隻需要k個Rj類型的資源。當Pi發出資源請求後，系統按下述步驟進行檢查： （1）如果 Requesti[j]<=Need[i,j]，則轉向步驟2；否則，認為出錯，因為它所需要的資源數已超過它所宣布的最大值。 （2）如果Requesti[j]<=Available[j] ，則轉向步驟3；否則，表示系統中尚無足夠的資源，Pi必須等待。 （3）系統試探把要求的資源配置設定給程序Pi，并修改下面資料結構中的數值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[j]; （4）系統執行安全性算法，檢查此次資源配置設定後，系統是否處于安全狀态。若安全，才正式将資源配置設定給程序Pi，以完成本次配置設定；否則，将試探配置設定廢棄，恢複原來的資源配置設定狀态，讓程序Pi等待。 三、安全性算法系統所執行的安全性算法可描述如下： （1）設定兩個向量 ①、工作向量Work。它表示系統可提供給程序繼續運作所需要的各類資源數目，它含有m個元素，執行安全算法開始時，Work = Available。 ②、Finish。它表示系統是否有足夠的資源配置設定給程序，使之運作完成，開始時先做Finish[i]:=false ；當有足夠資源配置設定給程序時，令 Finish[i]:=true。 （2）從程序集合中找到一個能滿足下述條件的程序： ①、Finish[i]=false; ②、Need[i,j]<=Work[j];如找到，執行步驟（3）；否則，執行步驟（4）。 （3）當程序Pi獲得資源後，可順利執行，直至完成，并釋放出配置設定給它的資源，故應執行： Work[j]:=Work[i]+Allocation[i,j]; Finish[i]:=true; goto step 2； （4）如果所有程序的Finish[i]:=true，則表示系統處于安全狀态；否則，系統處于不安全狀态。 四、銀行家算法之例 假定系統中有五個程序：{P0，P1，P2，P3，P4}和三種類型的資源{A，B，C}，每一種資源的數量分别為10、5、7,在T0時刻的資源配置設定情況如圖1所示。
(2) P1請求資源：P1送出請求向量Request1(1,0,2),系統按銀行家算法進行檢查： ①Request1(1,0,2)<=Need1(1,2,2) ②Request1(1,0,2)<=Available1(3,3,2) ③系統先假定可為P1配置設定資源，并修改Available,Allocation1和Need1向量，由此形成資源變化情況如圖1中的圓括号所示。 ④再利用安全性算法檢查此時系統是否安全。如圖3所示。
由所進行的安全性檢查得知，可以找到一個安全序列｛P1,P3,P4,P2,P0｝。是以系統是安全的，可以立即将P1所申請的資源配置設定給它。 (3) P4請求資源：P4送出請求向量Request4(3,3,0),系統按銀行家算法進行檢查： ①Request4(3,3,0)≤Need4(4,3,1); ②Request4(3,3,0)不小于等于Available(2,3,0),讓P4等待。 (4) P0請求資源：P0送出請求向量Request0(0,2,0),系統按銀行家算法進行檢查。 ①Request0(0,2,0) ≤Need0(7,4,3); ②Request0(0,2,0) ≤Available(2,3,0); ③系統暫時先假定可為P0配置設定資源，并修改有關資料，如圖4所示。
#include<stdio.h> #include<stdlib.h> #ifndef MY_MAX #define MY_MAX 5 #endif int max1[5][3]={ {7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3} }; int allocation1[5][3]={ {0,1,0}, {2,0,0}, {3,0,2}, {2,1,1}, {0,0,2} }; int need1[5][3]={ {7,4,3}, {1,2,2}, {6,0,0}, {0,1,1}, {4,3,1} }; int available1[3]={3,3,2}; int max[10][10],allocation[10][10],need[10][10],available[10]; int n_proc; int type_src; int request[10][10]; int work[10]; int finish[10]; int index[10]; int t=0; int serial_proc=0; int random_num(int min,int max) { int i,range; double j; range=max-min; i=rand(); j=((double)i/(double)RAND_MAX); i=(int)(j*(double)range); i+=min; return i; } void init0_data(void) { int i,j; n_proc=5; type_src=3; for(i=0;i<n_proc;i++) for(j=0;j<type_src;j++) max[i][j]=max1[i][j]; for(i=0;i<n_proc;i++) for(j=0;j<type_src;j++) allocation[i][j]=allocation1[i][j]; for(i=0;i<n_proc;i++) for(j=0;j<type_src;j++) need[i][j]=need1[i][j]; for(j=0;j<type_src;j++) available[j]=available1[j]; for(i=0;i<n_proc;i++) index[i]=-1; } void init1_data(void) { int i,j,k1=0; n_proc=random_num(1,MY_MAX); type_src=random_num(1,MY_MAX); for(i=0;i<n_proc;i++) do{ for(j=0;j<type_src;j++) max[i][j]=random_num(0,MY_MAX); k1=0; for(j=0;j<type_src;j++) k1+=max[i][j]; }while(k1==0); for(i=0;i<n_proc;i++) do{ for(j=0;j<type_src;j++) allocation[i][j]=random_num(0,max[i][j]+1); k1=0; for(j=0;j<type_src;j++) if(allocation[i][j]==max[i][j]) k1++; }while(k1==type_src); for(i=0;i<n_proc;i++) for(j=0;j<type_src;j++) need[i][j]=max[i][j]-allocation[i][j]; do{ for(j=0;j<type_src;j++) available[j]=random_num(0,MY_MAX); k1=0; for(i=0;i<n_proc;i++) { for(j=0;j<type_src;j++) if(need[i][j]>available[j]) { k1++; break; } } }while(k1==n_proc); for(i=0;i<n_proc;i++) index[i]=-1; } void proc_require1(void) { int j,tmp; serial_proc=index[0]; do{ printf("[%d]請求資源數：",serial_proc); for(j=0;j<type_src;j++) printf("%2d",request[serial_proc][j]=random_num(0,MY_MAX)); tmp=0; for(j=0;j<type_src;j++) tmp+=request[serial_proc][j]; }while(tmp==0); } void proc_require0(void) { int j,tmp; require0: printf("/t現在第?程序請求/n"); scanf("%d",&serial_proc); if (serial_proc<0 ||serial_proc>=n_proc) { printf("程序号非法(越界)/n"); goto require0; } tmp=0; for(j=0;j<type_src;j++) tmp+=need[serial_proc][j]; if (!tmp) { printf("[%d]該程序處于完成狀态/n",serial_proc); goto require0; } printf("/t對[%d]程序,各資源要求/n",serial_proc); for(j=0;j<type_src;j++) scanf("%d",&request[serial_proc][j]); printf("/n"); } int over_need() { int j; for(j=0;j<type_src;j++) if(request[serial_proc][j]>need[serial_proc][j]) { printf("/t請求資源超過需求資源/n"); return 1; } return 0; } int over_avail() { int j; for(j=0;j<type_src;j++) if(request[serial_proc][j]>available[j]) { printf("/t[%d]請求資源超過可利用資源/n",serial_proc); return 1; } return 0; } int apply_success(int be_need,int be_avail) { if (be_need==0 && be_avail==0) { return 1; } return 0; } int check_security() { int i,j,tmp; for(j=0;j<type_src;j++) work[j]=available[j]; for(i=0;i<n_proc;i++) finish[i]=0; t=0; L2: for(i=0;i<n_proc;i++) if(finish[i]==0) { tmp=1; for(j=0;j<type_src;j++) if(need[i][j]>work[j]) { tmp=0; break; } if(!tmp) continue; else { for(j=0;j<type_src;j++) work[j]+=allocation[i][j]; finish[i]=1; tmp=0; for(j=0;j<type_src;j++) tmp+=need[i][j]; if(tmp) index[t++]=i; goto L2; } } for(j=0;j<n_proc;j++) if(finish[j]==0) return 0; return 1; } void banker() { int allocation_t[10],available_t[10],need_t[10]; int tmp; int j; for(j=0;j<type_src;j++) { available_t[j]=available[j]; allocation_t[j]=allocation[serial_proc][j]; need_t[j]=need[serial_proc][j]; } for(j=0;j<type_src;j++) { available[j]-=request[serial_proc][j]; need[serial_proc][j]-=request[serial_proc][j]; allocation[serial_proc][j]+=request[serial_proc][j]; } if(check_security(type_src,n_proc)) { tmp=0; for(j=0;j<type_src;j++) tmp+=need[serial_proc][j]; if(!tmp) for(j=0;j<type_src;j++) available[j]+=allocation[serial_proc][j]; } else { for(j=0;j<type_src;j++) { allocation[serial_proc][j]=allocation_t[j]; need[serial_proc][j]=need_t[j]; available[j]=available_t[j]; } } } int finish_all(void) { int i,j; for(i=0;i<n_proc;i++) for(j=0;j<type_src;j++) if(need[i][j]!=0) return 1; return 0; } void output() { int i,j; printf("/n安全序列輸出格式：[程序号,程序數]/n"); for(i=0;i<t;i++) { printf("[%d,%d] ",index[i],t); } printf("/n"); printf("依次為:最大需求矩陣,已配置設定矩陣,需求矩陣,可利用矩陣/n"); for(i=0;i<n_proc;i++) { printf("+"); for(j=0;j<type_src;j++) printf("%2d",max[i][j]); printf("+"); for(j=0;j<type_src;j++) printf("%2d",allocation[i][j]); printf("+"); for(j=0;j<type_src;j++) printf("%2d",need[i][j]); printf("+"); if (i==serial_proc) for(j=0;j<type_src;j++) printf("%3d",available[j]); printf("+"); printf("/n"); } } void main(void) { start: printf("/n/t銀行家算法/n/t/t/t設計者:李行/t2003.1.1/n請确定工作方式: '1'為自動;'0'為手動/a/n"); switch(getche()){ case '1': do{ init1_data(); }while(!check_security(type_src,n_proc)); output(); do{ proc_require1(); if(apply_success(over_need(),over_avail())) banker(); output(); }while(finish_all()); break; case '0': do{ init0_data(); }while(!check_security(type_src,n_proc)); output(); do{ proc_require0(); if(apply_success(over_need(),over_avail())) banker(); output(); }while(finish_all()); break; default: printf("/t請按提示操作啦!/n"); break; } printf("繼續?y/n/n"); if(getche()=='y') goto start; } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 四、測試與評價 1、 程式運作及結果測評 ： 在自動、手動方式下都能正确得出結果，但在自動模式下，當值MY＿MAX增大時，計算時間長，增加了系統的開銷，這也就說明了在實際系統中不常用銀行家算法――死鎖避免在死鎖解決中的這一原因。 2、 程式架構測評：主要使用了函數将每個子產品分開，便于了解。但由于，程式設計了自動實作模式，導緻程式顯得過長。每個子產品之間的資訊交換主要通過全局變量平實作，從這個角度講，子產品的劃分并不嚴格。對于自動與手動這兩種工作方式，解題思路是備援的，但程式卻為了避免之間的幹擾備援設計了函數，因而各個函數内聚度不高，功能也還有相容點，是以在函數設計也不十分合理。盡管如此，本設計嚴格從銀行家算法出發，能很好地幫助讀者了解銀行家算法在多程序并行為死鎖避免采取的資源配置設定、安全性檢測的政策。特别，在自動方式下，資源配置設定利用第一次安全檢測的結果避免了後繼執行程序的不确定，有效地解決了自動請求的過重盲目的特點。當然，這部分有違銀行家算法，但并沒有增加額外的空間開銷，還減少了時間上的開銷，個人覺得是成功的。 3、設計特點 ① 資料結構：數組； ② 全局變量 ③ 在自動方式下，采用do{}while(條件)以保證程序能夠推進。 ④ getche()在調試時産生Warnings但能編譯通過，getchar()對于鍵的接收不好确定，而getche()則一按即可。 4、設計心得： 為準确了解，應該以手動模式下運作為準，這樣的互動性較好！而自動實作下，更接近于機器的工作方式。程式在設計初，隻是用了手動這一模式，後來聽取同學的意見以随機數實作自動模式，在設計時出了好些問題，但想多了問題也就通了，而新的問題又出現，卻總能解決。在這種模式下能更徹底了解銀行家算法中的資源配置設定政策。 |
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)