銀行家算法畢業論文銀行家算法畢業論文題目：銀行家算法設計銀行家算法畢業論文摘要Dijkstra的銀行家算法是最有代表性的避免死鎖的算法，該算法由于能用于銀行系統現金貸款的發放而得名。銀行家算法是在確保當前系統安全的前提下推進的。對進程請求先進行安全性檢查，來決定資源分配與否，從而確保系統的安全，有效的避免了死鎖的發生。該論文在理解和分析了銀行家算法的核心思想以及狀態的本質涵義的前提下，對算法的實現在總體上進行了設計，包括在對算法分模塊設計，并對各個模塊的算法思想通過流程圖表示，分塊編寫代碼，并進行測試，最后進行程序的測試，在設計思路上嚴格按照軟件工程的思想執行，確保了設計和實現的可行，可信。代碼實現采用C語言。關鍵詞：銀行家算法；死鎖；避免死鎖；安全性序列銀行家算法畢業論文I目錄中文摘要.I1緒論.11.1課題背景.11.2課題意義.11.3銀行家算法.11.4死鎖.21.5安全性序列.22需求分析.32.1問題描述.32.2基本要求.32.3數據流模型.33概要設計.43.1模塊的劃分.43.2模塊調用關系.43.3各模塊之間的接口.43.4程序流程圖.54詳細設計.64.1數據結構選取分析.64.2數據結構設計.64.3算法整體設計與調用.64.4模塊設計與時間復雜度分析.74.4.1系統資源初始化函數Init_process.74.4.2安全性算法Safety_Algorithm.74.4.3接受進程請求試分配Attempt_Allocation；.74.4.4對試分配后的系統進行安全性檢查Safety_Algorithm.84.5程序流圖.8銀行家算法畢業論文II4.5.1系統以及進程資源初始化Init_process的程序流程圖.84.5.2安全性算法Safety_Algorithm的程序流程圖.94.5.3接受進程請求試分配Attempt_Allocation的程序流程圖.94.5.4對試分配后的系統進行安全性檢查Safety_Algorithm的程序流程圖.95程序分析測試.105.1分模塊分析與測試.105.1.1初始化系統資源模塊Init_process的測試105.1.2試分配模塊Attempt_Allocation的測試115.1.3安全模塊Safety_Algorithm的調試.115.2集成測試.126小結.13參考文獻.14附錄（源代碼）.151緒論11緒論1.1課題背景在多道程序系統中，雖可以借助多個進程的并發執行來改善系統的資源利用率，提高系統吞吐量，但可能發生一種危險死鎖，即多個進程在運行過程中因爭奪資源而造成的一種僵局，若無外力作用，將無法再向前推進。如此，尋求一種避免死鎖的方法便顯得有為重要。死鎖的產生一般的原因有兩點：競爭資源和進程間推進順序非法。因此，我們只需在當前的有限資源下，找到一組合法的執行順序，便能很好的避免死鎖，我們稱它為安全序列。而銀行家算法起源于銀行系統的發放貸款，和計算機操作系統的資源分配完全符合，因此可以借鑒該算法的思想，設計出一種有效的算法程序，解決該問題。1.2課題意義（1）運用軟件工程的方法指導設計和實現，即是對這學期剛剛學過的軟件工程課的復習，又是一次實戰演練，從而提高自己的分析問題，解決問題和動手能力；（2）通過整個算法的設計與實現進一步加深了對算法的理解和多道程序下的計算機系統資源分配現狀，為以后進一步的學習打下了良好的基礎。1.3銀行家算法我們可以把操作系統看作是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向操作系統請求分配資源相當于用戶向銀行家貸款。為保證資金的安全,銀行家規定:(1)當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客；操作系統課程設計報告2(2)顧客可以分歧貸款,但貸款的總數不能超過最大需求量；(3)當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間里得到貸款；(4)當顧客得到所需的全部資金后,一定能在有限的時間里歸還所有的資金.操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程已占用的資源數與本次申請的資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統現存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。1.4死鎖死鎖是進程死鎖的簡稱，是由Dijkstra于1965年研究銀行家算法時首先提出來的。是指多個進程循環等待它方占有的資源而無限期地僵持下去的局面。很顯然，如果沒有外力的作用，那麼死鎖涉及到的各個進程都將永遠處于封鎖狀態。它是計算機操作系統乃至并發程序設計中最難處理的問題之一。實際上，死鎖問題不僅在計算機系統中存在，在我們日常生活中它也廣泛存在。在計算機系統中，涉及軟件，硬件資源都可能發生死鎖。例如：系統中只有一臺CD-ROM驅動器和一臺打印機，某一個進程占有了CD-ROM驅動器，又申請打印機；另一進程占有了打印機，還申請CD-ROM。結果，兩個進程都被阻塞，永遠也不能自行解除。1.5安全性序列安全序列的的實際意義在于：系統每次進行資源分配后，如果對于系統中新的資源狀況，存在一個安全序列，則至少存在一條確保系統不會進入死鎖的路徑。按照該序列，銀行家可以實施一個有效的分配過程使得所有客戶得到滿足銀行家算法的核心在于安全序列的產生。安全序列正是一種安全的進程推進順序2需求分析32需求分析2.1問題描述運用銀行家算法，避免死鎖的發生。在確保當前系統安全的前提下推進的。對進程請求先進行安全性檢查，來決定資源分配與否，從而確保系統的安全，有效的避免了死鎖的發生。問題的關鍵在于安全性算法，即找安全性序列。2.2基本要求（1）從鍵盤輸入當前系統的資源信息，包括當前可用資源，每個進程對各類資源的最大需求量，每個進程當前已分配的各個資源量和每個進程尚需要的各個資源量，輸出結果顯示在DOS界面上；（2）輸入進程請求，按照設計好的安全性算法進行檢查，得到結果并輸出整個執行過