【正文】 模擬通過銀行家算法避免死鎖一、 銀行家算法產(chǎn)生的背景及目的 1：在多道程序系統(tǒng)中，雖然借助于多個進(jìn)程的并發(fā)執(zhí)行來改善系統(tǒng)的利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險—死鎖。死鎖就是多個進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵局狀態(tài)時，如無外力作用，他們將無法再向前進(jìn)行，如再把信號量作為同步工具時，多個Wait和Signal操作順序不當(dāng)，會產(chǎn)生進(jìn)程死鎖。然而產(chǎn)生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件。在預(yù)防死鎖的幾種方法中，都施加了較強(qiáng)的限制條件，在避免死鎖的方法中，所施加的條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，便可避免死鎖。2：實驗?zāi)康模鹤寣W(xué)生獨立的使用編程語言編寫和調(diào)試一個系統(tǒng)分配資源的簡單模擬程序，了解死鎖產(chǎn)生的原因及條件。采用銀行家算法及時避免死鎖的產(chǎn)生，進(jìn)一步理解課堂上老師講的相關(guān)知識點。銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶中誰能完成其工作，然后假定其完成工作且歸還全部貸款，再進(jìn)而檢查下一個能完成工作的客戶。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。二：銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 1：可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。如果Available[j]=k，z則表示系統(tǒng)中現(xiàn)有Rj類資源K 個。 2：最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j]=k，表示第i個進(jìn)程需要第Rj類資源的最大數(shù)目k個.3: 分配矩陣Allocation,也是n*m的矩陣，若Allocation[i,j]=k,表示第i個進(jìn)程已分配Rj類資源的數(shù)目為k個。 4：需求矩陣Need。也是一個n*m的矩陣，Need[i,j]=k,表示第i個進(jìn)程還需Rj類資源k個。三、銀行家算法及安全性算法 1：銀行家算法設(shè)Request[i]是進(jìn)程Pi的請求向量，若Request[i][j]=k。表示進(jìn)程需要j類資源k個。當(dāng)Pi發(fā)出資源請求時，系統(tǒng)按下屬步驟進(jìn)行檢查；(1) 如果Request[i][j]=Need[i][j]。便轉(zhuǎn)向步驟（2），否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過他所宣布的最大值。(2) 如果Request[i][j]=Available[i][j],便轉(zhuǎn)向步驟（3），否則認(rèn)為尚無足夠資源，進(jìn)程需等待。(3) 系統(tǒng)試探著把資源分配給進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)Available[i][j]=Available[i][j]Request[i][j]。Allocation[i][j]=Allocation[i][j]+Request[i][j]。Need[i][j]=Need[i][j]Request[i][j]。(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，已完成此次分配。否則，將本次的試探分配作廢，回復(fù)原來的資源分配狀態(tài)，將進(jìn)程Pi等待。2：安全性算法（1） 設(shè)置兩個向量； 1：工作向量Work，表示系統(tǒng)可提供給進(jìn)程運(yùn)行所需的各類資源數(shù)目，它含有m個元素，初始時Work=Available 2：Finish ,表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finish[i]=true（2） 從進(jìn)程中找到一個能滿需下屬條件的進(jìn)程1；Finish[i]=false；2：Need[i][j]=Work[j]。若找到執(zhí)行步驟（3），否則執(zhí)行步驟（4）（3） 當(dāng)進(jìn)程Pi順利獲得資源后，直至完成，并釋放分配給它的資源，執(zhí)行： Work[j]=Work[j]+Allocation[i][j]。 Finish[i]=true。 Go to step (2)。(5) 如果所有的進(jìn)程Finish[i]都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。四、模塊設(shè)計與分析及整體功能概述模塊設(shè)計與分析： 整個銀行家算法分為初始化函數(shù)Init（），安全性算法函數(shù) safe（），銀行家算法函數(shù)bank（）三部分。初始化函數(shù)生成開始時刻系統(tǒng)中的進(jìn)程和資源情況，安全性算法判斷當(dāng)某進(jìn)程申請資源時，系統(tǒng)能否處于安全狀態(tài)。在本實驗中，若系統(tǒng)處于安全狀態(tài)，便生成一個安全進(jìn)程序列（安全序列可能有多個）。銀行家算法函數(shù)bank（）負(fù)責(zé)整體的檢查與異常判斷。整體功能概述：死鎖會引起系統(tǒng)陷入僵局，操作系統(tǒng)必須防止此現(xiàn)象的發(fā)生。本實驗通過一個動態(tài)分配資源的模擬程序，更清楚的理解死鎖產(chǎn)生的原因和條件。Dijkstra的銀行家算法是最有代表性的避免死鎖的方法。運(yùn)行程序時用戶設(shè)定系統(tǒng)中進(jìn)程和可利用資源的種類數(shù)目。輸入各進(jìn)程的可利用資源Available，最大需求MAX，已分配資源Allocation ，需求資源Need，之后各系統(tǒng)發(fā)出資源請求Request，利用實驗中的安全性算法判斷能否產(chǎn)生一個安全性隊列，若能，則給該進(jìn)程分配成功，否則，不予分配。五、流程圖設(shè)計 六、源代碼及調(diào)試分析 includedefine MAXm 50 // 定義最大進(jìn)程數(shù)define MAXn 100 //定義最大資源數(shù)int MAX[MAXm][MAXn]。 //最大需求矩陣int Allocation[MAXm][MAXn]。 //已分配矩陣int Available[MAXn]。 //可用資源數(shù)組int Need[MAXm][MAXn]。 //需求矩陣int Request[MAXm][MAXn]。 //請求矩陣int Finish[MAXm]。 //存儲完成資源分配的進(jìn)程int Sequence[MAXm]。 //模擬的資源分配序列int Work[MAXn]。 //系統(tǒng)是否有足夠的資源分配給進(jìn)程int m,n。 //m個進(jìn)程,n個資源define False 0define True 1void input()。 //數(shù)據(jù)輸入函數(shù)int safealg()。 //安全性算法函數(shù)void banker()。 //銀行家算法函數(shù)void main(){input()。safealg()。banker()。}//*************初始化算法***************void input() { int i,j。 //************自定義進(jìn)程數(shù)目與資源種類******************* cout***********************************\n。 cout*利用銀行家算法避免死鎖*\n。 cout* *\n。 cout************************************\n。 cout請輸入進(jìn)程的數(shù)目:。 cinm。 cout請輸入資源的種類:。 cinn。 //*****輸入每個進(jìn)程對每種資源的最大需求、已經(jīng)獲得的數(shù)量、每種類型資源的