【正文】 學(xué) 號： 09407227 姓 名： 王子丹 指導(dǎo)教師： 陜粉麗 專 業(yè)： 計算機科學(xué)與技術(shù) 系 別： 計算機系 完成時間： 2020 年 5 月 長治學(xué)院學(xué)士學(xué)位論文 (設(shè)計 ) I 銀行家算法避免死鎖的研究與實現(xiàn) 專業(yè)： 計算機科學(xué)與技術(shù) 姓名： 王子丹 學(xué)號： 09407227 指導(dǎo)教師 ：陜粉麗 摘 要： Dijkstra 的銀行家算法是最有代表性的避免死鎖的算法，該算法由于能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。 關(guān)鍵詞 ： 銀行家算法；死鎖；避免死鎖；安全性序列 銀行家算法避免死鎖的研究與實現(xiàn) II 目 錄 1 前言 ................................................................. 1 課題背景 ........................................................ 1 死鎖 ............................................................ 1 系統(tǒng)安全狀態(tài) .................................................... 2 銀行家算法 ...................................................... 2 2 需求分析 ............................................................. 3 問題描述 ........................................................ 3 基本要求 ........................................................ 3 數(shù)據(jù)流模型 ...................................................... 3 3 概要設(shè)計 ............................................................. 4 模塊的劃分 ...................................................... 4 模塊調(diào)用關(guān)系 .................................................... 4 各模塊之間的接口 ................................................ 4 程序流程圖 ...................................................... 5 4 詳細設(shè)計 ............................................................. 5 數(shù)據(jù)結(jié)構(gòu)選取分析 ................................................ 6 數(shù)據(jù)結(jié)構(gòu)設(shè)計 .................................................... 6 算法整體設(shè)計與調(diào)用 .............................................. 6 程序流圖 ........................................................ 7 5 程序分析測試 ......................................................... 9 分模塊分析與測試 ................................................ 9 集成測試 ....................................................... 11 6 結(jié)論 ................................................................ 12 參考文獻 .............................................................. 12 致謝 .................................................................. 14 附錄 .................................................................. 15 長治學(xué)院學(xué)士學(xué)位論文 (設(shè)計 ) 1 銀行家算法避免死鎖的研究與實現(xiàn) 1 前言 課題背景 在多道程序系統(tǒng)中，雖可以借助多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利 用率，提高系統(tǒng)吞吐量，但可能發(fā)生一種危險 —— 死鎖。而銀行家算法起源于銀行系統(tǒng)的發(fā)放貸款，和計算機操作系統(tǒng)的資源分配完全符合，因此可以借鑒該算法的思想，設(shè)計出一種有效的算法程序，解決該問題。 為保證系統(tǒng)中諸進程的正常運行，應(yīng)事先采取必要的措施，來預(yù)防發(fā)生死鎖。 （ 2）避免死鎖。通過系統(tǒng)設(shè)置的檢測機構(gòu)，及時的檢測出死鎖的發(fā)生。 銀行家算法避免死鎖的研究與實現(xiàn) 2 系統(tǒng)安全狀態(tài) 預(yù)防死鎖和解除死鎖都是通過施加條件限制，來預(yù)防發(fā)生死鎖。但如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當(dāng)進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。 2 需求分析 問題描述 運用銀行家算法避免死鎖的發(fā)生是在確保當(dāng)前系統(tǒng)安全的前提下推進的，對進程請求先進行安全性檢查來決定資源分配與否，從而確保系統(tǒng)的安全，有效的避免了死鎖的發(fā)生。 數(shù)據(jù)流模型 用鍵盤輸入信息，對系統(tǒng)資源初始化，輸入進程請求，用安全性算法進行安全性檢查，系統(tǒng)安全的話就進行試分配，再進行安全性檢查；如果試分配失敗則恢復(fù)系統(tǒng)。分別為 Flag1， pro， Flag2。 程序流程圖 假 設(shè) Request 是進程的請求向量， Need 是需求向量， Available 是可利用資源向量。接著，系統(tǒng)試探著把資源分配給進程，系統(tǒng)執(zhí)行安全性算法。具體程序總流程圖如圖 3 所示。否則之前的試分配作廢，恢復(fù)試分配之前的數(shù)據(jù)結(jié)構(gòu)，輸出相關(guān)提示信息，接收下一個進程請求。然后，判斷異常情況，利用 Reasonable 函數(shù)找到當(dāng)前可執(zhí)行的進程。 =j++。 (4)對試分配后的系統(tǒng)，進行安全性檢查的程序流程圖 和圖 5 大致一樣，唯一一點在于當(dāng)找不到安全序列時，將本次試分配作廢，恢復(fù)該次 試分配之前的數(shù)據(jù)結(jié)構(gòu)。 Finish[i]=pnum。 Retumn p。起初效果不理想，經(jīng)過一些調(diào)整后，顯示才比較理想。 (3)安全模塊 Safety_Algorithm 的調(diào)試 ?試分配前的安全算法，結(jié)果如果輸出一個安全性序列，并且經(jīng)過人工檢查該安全性序列，確實有效，則該模塊正確 ,如圖 10 所示；如果系統(tǒng)不安全，打印出相關(guān)信息，返回上一層。 長治學(xué)院學(xué)士學(xué)位論文（設(shè)計） 11 圖 12 試分配后輸出一個安全性序列 圖 13 試分配后不安全狀態(tài)的資源恢復(fù) 集成測試 各模塊測試通過后，集成在一起測試，系統(tǒng)初始資源和模塊測試時保持一致，以下是測試用例以及結(jié)果， 基本包括了該算法的所有情況。 （ 4） 00： Request(0,2,0) 結(jié)果： 試分配后，系統(tǒng)不安全，試分配作廢。之后，確定自己設(shè)計的算法分四大模塊。但通過查閱書本，對算法細節(jié)重新建立正確的認識后，再通過單步調(diào)試后，最終解決。 avoid deadlock。在此向幫助和指導(dǎo)過我的各位老師表示最 真誠 的感謝！ 此外，還要 感謝我的同學(xué)和朋友，在我寫論文的過程中給予我很多素材，還在論文的撰寫和排版 的 過程中提供熱情的幫助。 int Need[M]。 process* last=NULL。 if(NULL==*head) { *head=p。 } } void Init_process(process **head,int m,int* count) { int i,j=0。 printf(請輸入第 %d 個進程信息 :\n,)。 if([P0]!=1) { for(i=1。 } printf(分配矩陣 : )。[i])。i++) { scanf(%d,amp。 } else 長治學(xué)院學(xué)士學(xué)位論文（