操作系統(tǒng)課程設(shè)計報告銀行家算法的設(shè)計與實現(xiàn)(java語言)

操作系統(tǒng)課程設(shè)計報告-銀行家算法的設(shè)計與實現(xiàn)(JAVA語言)操作系統(tǒng)課程設(shè)計題目院系專業(yè)班級學(xué)生學(xué)號指導(dǎo)教師年月基于計算機此次課程設(shè)計的主要內(nèi)容是模擬實現(xiàn)資源分配同時要求編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序觀察死鎖產(chǎn)生的條件并使用適當?shù)乃惴ㄓ行У姆乐购捅苊馑梨i的發(fā)生具體用銀行家算法實現(xiàn)資源分配要求如下1設(shè)計一個3個并發(fā)進程共享3類不同資源的系統(tǒng)進程可動態(tài)地申請資源和釋放資源系統(tǒng)按各進程的申請動態(tài)地分配資源2設(shè)計用銀行家算法和隨機分配算法實現(xiàn)資源分配的兩個資源分配程序應(yīng)具有顯示或打印各進程依次要求申請的資源數(shù)以及依次分配資源的情況3確定一組各進程依次申請資源數(shù)的序列在相同的情況下分別運行上述兩種資源分配程序觀察運行結(jié)果銀行家算法是避免死鎖的一種重要方法本實驗要求用高級語言編寫和調(diào)試一個簡單的銀行家算法程序加深了解有關(guān)資源申請避免死鎖等概念并體會和了解死鎖和避免死鎖的具體實施方法死鎖的產(chǎn)生必須同時滿足四個條件即一個資源每次只能由一個進程占用第二個為等待條件即一個進程請求資源不能滿足時它必須等待但它仍繼續(xù)保持已得到的所有其他資源第四個為循環(huán)等待條件系統(tǒng)中存在若干個循環(huán)等待的進程即其中每一個進程分別等待它前一個進程所持有的資源防止死鎖的機構(gòu)只能確保上述四個條件之一不出現(xiàn)則系統(tǒng)就不會發(fā)生死鎖通過這個算法可用解決生活中的實際問題如銀行貸款等通過對這個算法的設(shè)計讓學(xué)生能夠?qū)局R有更深的理解在操作和其它方面有更高的提升關(guān)鍵詞死鎖安全狀態(tài)安全序列銀行家算法安全性檢查目錄1概述311設(shè)計目的312開發(fā)環(huán)境32需求分析421死鎖概念422死鎖的結(jié)論423資源分類424產(chǎn)生死鎖的必要條件425死鎖的解決方案4com鎖的例子4com防5com態(tài)與不安全狀態(tài)53數(shù)據(jù)結(jié)構(gòu)分析設(shè)計631可利用資源向量矩陣available[]632最大需求矩陣[][]633分配矩陣allocation[][]634需求矩陣need[][]64算法的實現(xiàn)741初始化742銀行家算法743安全性檢查算法744各算法流程圖85測試與實例分析106心得體會147參考文獻與源程序清單附錄15

概述11設(shè)計目的銀行家算法是一種最有代表性的避免死鎖的算法把操作系統(tǒng)看作是銀行家操作系統(tǒng)管理的資源相當于銀行家管理的資金進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源當進程首次申請資源時要測試該進程對資源的最大需求量如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源否則就推遲分配當進程在執(zhí)行中繼續(xù)申請資源時先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量若超過則拒絕分配資源若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量若能滿足則按當前的申請量分配資源否則也要推遲分配本次課程設(shè)計通過用JAVA語言編寫和調(diào)試實現(xiàn)銀行家算法的程序達到進一步掌握銀行家算法理解系統(tǒng)產(chǎn)生死鎖的原因以及系統(tǒng)避免死鎖的方法增強理論聯(lián)系實際的能力的目的12開發(fā)環(huán)境操作系統(tǒng)WindowsXP編譯工具Myeclipse86生成文件×××java源代碼文件和×××class編譯文件

2需求分析21死鎖概念死鎖就是指多個進程在運行中因爭奪資源而造成的一種僵局當進程出于這種僵持狀態(tài)時若無外力作用它們都將無法再向前推進22死鎖的結(jié)論產(chǎn)生死鎖的原因是競爭資源和進程間推進順序不當處理死鎖的基本方法是①預(yù)防死鎖②避免思索③檢測死鎖④解除死鎖23資源分類1可剝奪性資源某些進程在獲得此類資源后該資源可以再被其他進程或系統(tǒng)剝奪CPU和內(nèi)存均屬于可剝奪性資源2不可剝奪性資源當系統(tǒng)把這類資源分配給進程后再不能強行回收只能在進程用完后自動釋放如磁帶機打印機3非剝奪性資源在系統(tǒng)中所配置的非剝奪性資源由于它們的數(shù)量不能滿足諸進程運行的需要會使進程在運行構(gòu)成中因爭奪這些資源而陷入僵局4臨時性資源它是指由一個進程產(chǎn)生被另一個進程使用一短暫時間后便無用的資源也稱之為消耗性資源24產(chǎn)生死鎖的必要條件1互斥條件進程對它所分配到的資源進行排他性使用即在一段時間內(nèi)某資源由一個進程占有如果此時還有其它進程請求該資源則請求者只能等待直至占有該資源的進程用畢釋放2請求和保持條件進程已經(jīng)保持了至少一個資源但又提出新的資源請求而該資源又被其他進程占有此時請求進程阻塞但又對自己獲得的其他資源保持不放3不剝奪條件進程已經(jīng)獲得的資源在未使用完之前不能被剝奪只有在使用完是由自己釋放4環(huán)路等待條件發(fā)生死鎖時必然存在一個進程--資源的環(huán)形鏈25死鎖的解決方案com鎖的例子該例子是由于進程推進順序非法引發(fā)的死鎖進程P1和P2并發(fā)執(zhí)行如果按順序①執(zhí)行P1RequestR1P1RequestR2P1ReleaseR1P1ReleaseR2P2RequestR2P2RequestR1P2ReleaseR2P2ReleaseR1兩個進程可順利完成如果按曲線②執(zhí)行P1和P2將進入不安全區(qū)DP1保持了資源R1P2保持了R2接下來P2將申請不到R1P1申請不到R2系統(tǒng)處于不安全狀態(tài)往前推進將發(fā)生死鎖 圖3-15com防預(yù)防死鎖的方法是使產(chǎn)生死鎖的四個必要條件中的234條件之一不能成立即1摒棄請求和保持條件系統(tǒng)規(guī)定所有進程在開始運行之前都必須一次性申請其在整個運行過程中所需的全部資源使該進程再整個運行過程中不會提出資源請求因而摒棄了請求條件又由于進程在等待期間沒有占有任何資源所以也摒棄了保持條件2摒棄不剝奪條件系統(tǒng)規(guī)定進程逐個提出對資源的要求當一個已經(jīng)保持了某些資源的進程再提出新的資源請求而未被滿足時必須釋放已經(jīng)保持的所有資源待以后需要是在再重新申請3摒棄環(huán)路等待條件系統(tǒng)規(guī)定所有資源按類型進行線性排隊并賦予不同的序號所有進程對資源的請求都必須嚴格按資源序號遞增的順序提出com態(tài)與不安全狀態(tài) 在避免死鎖的方法中允許進程動態(tài)地申請資源但系統(tǒng)在進行資源分配之前應(yīng)先計算此次資源分配的安全性若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)則將資源分配給進程否則令進程等待所謂安全狀態(tài)是指系統(tǒng)能按某種進程順序P1P2P3Pn來為每個進程分配所需資源直至滿足每個進程對資源的最大需求是每個進曾都可以順利完成如果系統(tǒng)找不到這樣一個序列系統(tǒng)就處于不安全狀態(tài)雖然并非所有的不安全狀態(tài)都是死鎖狀態(tài)但當系統(tǒng)進入不安全狀態(tài)后便可能進入死鎖狀態(tài)只要系統(tǒng)處于安全狀態(tài)系統(tǒng)便可以避免進入不安全狀態(tài)因此避免死鎖的實質(zhì)在于系統(tǒng)在進行資源分配時如何使系統(tǒng)不進入不安全狀態(tài)安全序列一個進程序列P1Pn是安全的如果對于每一個進程Pi1≤i≤n它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pjji當前占有資源量之和 銀行家算發(fā)就是用具避免死鎖的一個有效方法3數(shù)據(jù)結(jié)構(gòu)分析設(shè)計31可利用資源向量矩陣available[]這是一個含有m個元素的數(shù)組其中的每一個元素代表一類可利用的資源數(shù)目其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目其數(shù)值隨該類資源的分配和回收而動態(tài)地改變?nèi)绻鸻vailable[j]K則表示系統(tǒng)中現(xiàn)有R類資源K個32最大需求矩陣[][]這是一個nm的矩陣用以表示每一個進程對m類資源的最大需求如果[ij]K則表示進程i需要R類資源的數(shù)目為K33分配矩陣allocation[][]這也是一個nm的矩陣它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)如果allocation[ij]K則表示進程i當前已分得R類資源的數(shù)目為K34需求矩陣need[][]這也是一個nm的矩陣用以表示每一個進程尚需的各類資源數(shù)如果need[ij]K則表示進程i還需要R類資源K個才能完成其任務(wù)上述矩陣存在下述關(guān)系need[ij][ij]－allocation[ij]4算法的實現(xiàn)41初始化1創(chuàng)建available[]數(shù)組用以存放系統(tǒng)中可用的資源數(shù)目2創(chuàng)建[][]數(shù)組用以存放各個進程對各類資源的最大需求數(shù)目3創(chuàng)建allocation[][]數(shù)組用以存放各個進程已經(jīng)分得的各類資源數(shù)目4創(chuàng)建need[][]數(shù)組用以存放各個進程還需要的各類資源數(shù)目5創(chuàng)建allocation1[][]need1[][]available1[]用以存放系統(tǒng)試分配資源前系統(tǒng)資源分配情況42銀行家算法設(shè)Requesti是進程Pi的請求向量RequestiK表示進程Pi需要K個j類資源Pi發(fā)出資源請求后按下列步驟進行檢查1如果requesti[j]≤need[ij]轉(zhuǎn)向步驟②否則報錯所需要的資源數(shù)已超過它所宣布的最大值2如果requesti[j]≤available[j]轉(zhuǎn)向步驟③否則報錯尚無足夠資源Pi需等待3嘗試將資源分配給進程Pi并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值available[j]available[j]-raquesti[j]allocation[ij]allocation[ij]raquesti[j]need[ij]need[ij]-raquesti[j]4執(zhí)行安全性算法檢查此次資源分配后系統(tǒng)是否出于安全狀態(tài)若安全才正式將資源分配給進程Pi已完成本次分配否則將本次試探分配作廢恢復(fù)原來的資源分配狀態(tài)讓Pi等待43安全性檢查算法1設(shè)置兩個向量一工作向量work表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目執(zhí)行安全性算法開始時workavailable二finish標志表示系統(tǒng)是否有足夠的資源分配給進程使之運行完成初始化finish[i]false有足夠資源分配給進程時令finish[i]true2從進程集合中找到一個能滿足下述條件的進程finish[i]falseNeed[ij]≤work[j]找到執(zhí)行步驟③否則執(zhí)行步驟④3當進程Pi獲得資源后可順利執(zhí)行直至完成并釋放出分配給它的資源故應(yīng)執(zhí)行Work[j]work[i]allocation[ij]Finish[i]trueGotostep②4如果所有進程的finish[i]true都滿足則表示系統(tǒng)處于安全狀態(tài)否則系統(tǒng)處于不安全狀態(tài)44各算法流程圖1初始化算法流程2銀行家算法流程圖

5測試與實例分析1下列狀態(tài)是否安全四個進程共享12個同類資源 資源進程 ABC AllocationABC NeedABC AvailableABC P0322 100 222 212 P1613 411 202 P2 314 211 103 P3 422 002 420 利用銀行家算法程序進行檢測打開程序輸入上述數(shù)據(jù)初始化數(shù)據(jù)后顯示進行安全檢測經(jīng)檢查系統(tǒng)為安全狀態(tài)存在安全序列p1p2p3p02考慮下列系統(tǒng)狀態(tài)系統(tǒng)是否安全若安全就給出所有的安全序列如果此時p0和p1均提出資源請求Request101能否立即給予滿足解繼續(xù)執(zhí)行銀行家算法程序1P0申請資源101申請不成功系統(tǒng)不為其分配資源繼續(xù)執(zhí)行銀行家算法程序2P1申請資源101申請成功存在安全序列p1p2p3p0所以對p2來說能得到立即滿足如果此刻P2繼續(xù)請求資源Reques101則就有系統(tǒng)將資源試分給P1則可用資源數(shù)變?yōu)?11然后繼續(xù)試分配給p0Request101它小于Avalable可以分配但分配后很明顯找不到一個安全序列發(fā)現(xiàn)系統(tǒng)處于不安全狀態(tài)不能分配給它于是回收資源系統(tǒng)的可用資源恢復(fù)到1116心得體會通過一個周的課程設(shè)計雖然理解起來很容易但想用算法具體去實現(xiàn)它還是有一定的難度雖然做起來比較吃力但當我通過自己親手做出來時使我更加加深了對銀行家算法的理解掌握了銀行家算法避免死鎖的過程和方法理解了死鎖產(chǎn)生的原因和條件以及避免死鎖的方法并且還鞏固了JAVA知識掌握了用JAVA實現(xiàn)銀行家算法的方法所編寫程序基本實現(xiàn)了銀行家算法的功能并在其基礎(chǔ)上考慮了輸出顯示格式的美觀性使界面盡可能友好并且在編程時將主要的操作都封裝在方法中如輸入進程和資源信息放在了一個構(gòu)造方法publicTheBanker中進行安全性檢測的方法Security_check進行申請資源的方法checkRequest打印當前各資源的方法print這樣使程序可讀性增強使程序更加清晰明了當然由于JAVA學(xué)的也就是些基礎(chǔ)平時的不常聯(lián)系使得我實際操作能力的很欠缺我在編寫和調(diào)試過程中遇到了許多的問題通過網(wǎng)上查詢資料翻閱課本向同學(xué)請教多次調(diào)試等方法逐漸解決了大部分問題這次課程設(shè)計非常有意義它讓我收獲很多不僅掌握了課本所學(xué)的知識也鞏固了JAVA的相關(guān)知識7參考文獻與源程序清單湯子瀛哲鳳屏湯小丹計算機操作系統(tǒng)西安電子科技大學(xué)出版社20062美威爾頓麥可匹克Java入門經(jīng)典第3版施宏斌譯北京清華大學(xué)出版社2009美BruceEckelJava編程思想陳昊鵬譯北京機械工業(yè)出版社2007importcomnerpublicclassTestBanker publicstaticvoidmainString[]args Sycomtln"-----操作系統(tǒng)銀行家算法-------" TheBankertbnewTheBanker booleanflagtrue whileflag Sycomtln"1死鎖避免檢驗是否安全" Sycomtln"2死鎖檢測" Sycomtln"3退出" Sycomtln" Sycomtln"請選擇" ScannerinputnewScannerSystemin intnuminputnextInt switchnum case1 tbSecurity_check flagtrue break case2 tbcheckRequest死鎖檢測 flagtrue break case3 Sycomtln"謝謝使用再見" flagfalse break importcomnerpublicclassTheBanker intm進程個數(shù) intn每個進程的資源個數(shù) int[][]最大需求矩陣 int[][]allocation以分配的資源已占有的資源 int[][]need需求的資源 int[]available可利用的資源 int[]p記錄安全序列 boolean[]finish標志一個進程是否完成true表示完成false表示未完成 ScannerinputnewScannerSystemin publicTheBanker Sycomtln"請輸入系統(tǒng)中的進程數(shù)" minputnextInt Sycomtln"請輸入進程的資源類型數(shù)" ninputnextInt newint[m][n] allocationnewint[m][n] neednewint[m][n] availablenewint[n] finishnewboolean[m] Sycomtln"請輸入一個"m"行"n"列的各進程的最大需求量" forinti0ilengthi依次輸入進程的各個最大資源數(shù) Sycomtln"請輸入第p"i1"進程的" forintj0j[i]lengthj [i][j]inputnextInt Sycomtln"請輸入一個"m"行"n"列的各進程的各占有量" forinti0iallocationlengthi依次輸入進程的各個占有資源數(shù) Sycomtln"請輸入第p"i1"進程中的Alloction" forintj0jallocation[i]lengthj allocation[i][j]inputnextInt forinti0ineedlengthi計算出各個進程需求的資源數(shù) forintj0jneed[i]lengthj need[i][j][i][j]-allocation[i][j] Sycomtln"請輸入可用資源數(shù)Avallable"輸入進程的可用資源數(shù) forinti0ini available[i]inputnextInt Sycomtln"初始化結(jié)果為下表" print 顯示列表publicvoidprint Sycomtln" Sycomtln"\t\tAllocation\tNeed\tAvalable" Sycomtln"\tABC\tABC\t\tABC\tABC" forinti0imi Sycomt"P"i"" Sycomt"" forintj0jnj Sycomt[i][j]"" Sycomt"\t" forintj0jnj Sycomtallocation[i][j]"" Sycomt"\t\t" forintj0jnj Sycomtneed[i][j]"" Sycomt"\t" ifi0 forintj0jnj Sycomtavailable[j]"" Sycomtln Sycomtln" publicbooleanSecurity_check int[]worknewint[n] forinti0ini work[i]available[i]把available的值賦給work finishnewboolean[m] forinti0imi開始把進程全部置未分配狀態(tài)都為false finish[i]false intnum0對每個進程都要把所有資源都進行比較 intnum10 intcount0記錄可以分配的序列 intcount10記錄所有序列是否分配 pnewint[m]找到安全序列 whilenum1m forinti0imi iffinish[i]false判斷finish的狀態(tài)如果為true說明剛才已經(jīng)找到不需要重復(fù) forintj0jnj ifneed[i][j]work[j]比較一個進程的各種資源是否滿足條件 num ifnumn如果一個進程所有資源都滿足條件needwork則找到了一個進程滿足 forintk0knk work[k]work[k]allocation[i][k] finish[i]true找到一個進程滿足 p[count]i記錄找到的是第幾個進程 num0必須把它清零重新來找下個資源種類的每種是否都滿足條件 num1 記錄有多少個序列 forinti0imi iffinish[i]true count1檢測是否所有的進程最后都是true ifcount1m如果序列里面總數(shù)等于總共有多少程序就找到了安全的序列并且輸出反之沒有找到 Sycomtln"存在一個安全序列安全序列為" forinti0imi ifim-1 Sycomt"P"p[i]"--" else Sycomtln"P"p[i] Sycomtln" returntrue else Sycomtln"沒有找到一個安全序列系統(tǒng)處于不安全狀態(tài)" returnfalse publicvoidcheckRequest intprocess0記錄輸入的是第幾個進程 intcount20記錄試分配過程中滿足條件的個數(shù) booleanflagtrue主要防止輸入的數(shù)字已經(jīng)超出了本來process數(shù)量則要求重新輸入 Sycomtln"請輸入要申請的第幾個進程注意進程p下標是從0開始的" whileflag processinputnextInt ifpr