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