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

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