銀行家算法畢業(yè)論文.doc

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