1、操作系統課程設計題目：銀行家算法的設計與實現系 別： 計算機信息與技術系 專 業： 計算機科學與技術 班 級： B130601 姓 名： 伏海龍 學 號： B13060105 指導教師 ： 魏少華 2016年01月摘要此次課程設計的主要內容是模擬實現資源分配。同時要求編寫和調試一個系統動態分配資源的簡單模擬程序，觀察死鎖產生的條件，并用適當的算法，有效的防止和避免死鎖的發生。銀行家算法是一個避免死鎖的一種重要方法，通過高級語言編寫和調試一個簡單的銀行家算法程序。加深了解有關資源申請、避免死鎖等概念，并體會了解死鎖和避免死鎖的具體實施方法。死鎖的產生，必須同時滿足四個條件，即一個資源每次只能由一

2、個進程占用；第二個為等待條件，即一個進程請求資源不能滿足時，他必須等待，但他仍繼續保持已得到的所有其他資源；第四個為循環等待條件，系統中存在若干個循環等待的進程，即其中每一個進程分別等待他前一個進程所持有的資源。當不滿足以上條件時就能防止系統的死鎖，讓系統流暢運行。通過該算法可以解決生活中的實際問題，如銀行貸款等。通過對該算法的設計，讓學生能夠對書本的知識有更深刻的理解，在操作和其他方面有大幅度的提高。目錄 TOC o 1-3 h z u HYPERLINK l _Toc439675935 1. 概述 PAGEREF _Toc439675935 h 1 HYPERLINK l _Toc4396

3、75936 1.1設計目的 PAGEREF _Toc439675936 h 1 HYPERLINK l _Toc439675937 2. 需求分析 PAGEREF _Toc439675937 h 1 HYPERLINK l _Toc439675938 2.1死鎖概念 PAGEREF _Toc439675938 h 1 HYPERLINK l _Toc439675939 2.2死鎖的結論 PAGEREF _Toc439675939 h 2 HYPERLINK l _Toc439675940 2.3資源分類 PAGEREF _Toc439675940 h 2 HYPERLINK l _Toc439

4、675941 2.4產生死鎖的必要條件 PAGEREF _Toc439675941 h 2 HYPERLINK l _Toc439675942 2.5銀行家算發的意義 PAGEREF _Toc439675942 h 3 HYPERLINK l _Toc439675943 3. 數據結構分析設計 PAGEREF _Toc439675943 h 3 HYPERLINK l _Toc439675944 3.1可利用資源向量矩陣available PAGEREF _Toc439675944 h 3 HYPERLINK l _Toc439675945 3.2最大需求矩陣max PAGEREF _Toc4

5、39675945 h 3 HYPERLINK l _Toc439675946 3.3分配矩陣allocation PAGEREF _Toc439675946 h 3 HYPERLINK l _Toc439675947 3.4需求矩陣need PAGEREF _Toc439675947 h 3 HYPERLINK l _Toc439675948 4. 算法的實現 PAGEREF _Toc439675948 h 4 HYPERLINK l _Toc439675949 4.1初始化 PAGEREF _Toc439675949 h 4 HYPERLINK l _Toc439675950 4.2銀行家算

6、法 PAGEREF _Toc439675950 h 4 HYPERLINK l _Toc439675951 4.3算法流程圖 PAGEREF _Toc439675951 h 6 HYPERLINK l _Toc439675952 4.3.1.初始化算法流程圖： PAGEREF _Toc439675952 h 6 HYPERLINK l _Toc439675953 4.3.2銀行家算法流程圖： PAGEREF _Toc439675953 h 7 HYPERLINK l _Toc439675954 5.測試與實例分析 PAGEREF _Toc439675954 h 8 HYPERLINK l _T

7、oc439675955 6.實驗總結 PAGEREF _Toc439675955 h 9 HYPERLINK l _Toc439675956 參考文獻 PAGEREF _Toc439675956 h 101. 概述1.1設計目的銀行家算法是一種最具代表性的避免死鎖的算法。把笑傲作死同看作是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向操作系統請求分配資源相當于用戶向銀行家貸款。操作系統按照銀行家制定的規則為進程分配資源，當進程首次分配資源時，要測試進程對資源的最大需求量，如果系統現存的資源可以滿足他的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先

8、測試該進程已占用的子元素與本次申請的資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，反之則在測試系統現存的資源是否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配本次課程設計通過C語言編寫和調試實現銀行家算法的程序，達到進一步掌握銀行家算法，理解系統產生死鎖的原因以及避免死鎖的方法，增強聯系實際能力的目的。2. 需求分析2.1死鎖概念死鎖就是指多個進程在運行中因爭奪資源而造成的一種僵局，當進程出這中僵持狀態時，若無外力作用，他們就我無法進行運作。2.2死鎖的結論產生死鎖的原因是：競爭資源和進程推進順序不當處理死鎖的基本方法是：預防死鎖，避免死鎖

9、，檢測死鎖，解除死鎖。2.3資源分類1.可剝奪性資源，某些進程在獲得此類資源后，該資源可以被其他進程或系統比多。CPU和每寸均屬于可剝奪性資源。2.不可剝奪性資源，當系統把類資源分配給進程后，不能強行收回，只能在進程用完后自動釋放，如磁帶機，打印機3.非剝奪性資源，在系統中所配置的非剝奪性資源，由于他們的數量不能滿足諸進程的需要，會使進程在運行中，因爭奪這些資源而陷入僵局。4.臨時資源，他是指由一個進程產生，倍另一個進程使用短暫時間后便無用的資源，也稱之為消耗性資源。2.4產生死鎖的必要條件1.互斥條件：進程對他所分配的資源進行排他性使用，即在一段時間內摸個資源由一個進程占有。如果此時還有其他

10、進程請求該資源，則請求者只能等待，直至占有該資源的進程用畢釋放。2.請求和保持條件：進程已經保持了至少一個資源，但又提出新的資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但有對自己獲得的其他資源保持不放。3.不剝奪條件：進程已獲得的資源，在未使用完之前，不能剝奪，只有在使用完由自己釋放。4環路等待條件：發生死鎖時，必然存在一個進程一資源的環形鏈。2.5銀行家算發的意義依次對進程測試，直到每一進程能夠運行并釋放，從而實現了避免死鎖的功能。也能提供多種序列可完美實現要求。3. 數據結構分析設計3.1可利用資源向量矩陣available 這是一個含有m個元素的數組，其中每一個元素代表一類可利

11、用的資源數目，其初始值是系統中所配置的該類全部可用資源數目，起數值隨該類資源的分配和回收而動態地改變。如果availablej=k，則表示系統中現有R類資源K個3.2最大需求矩陣max 這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果maxi,j=K，則表示進程i需要R類資源的數目為K。3.3分配矩陣allocation這也是一個n*m的矩陣，他/她定義了系統中每一類資源當前已分配給每一進程的資源數。如果allocationi，j=K，則表示進程i當前已分得R類資源的數目為K。3.4需求矩陣need這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果need i

12、，j =K，則表示進程i 還需要R類資源K個，才能完成其任務。上述矩陣存在下述關系:Needi,j=maxi,j-allocationi,j4. 算法的實現4.1初始化1.創建available數組，用以存放系統中可用的資源數目；2.創建max數組，用以存放各個進程對各類資源的最大需求數目；3.創建allocation數組，用以存放各個進程已經分得的各類資源數目；4.創建need 數組，用以存放個各個進程還需要的各類資源數目；5.創建allocationl；need;availablel，用以存放系統試分配資源前系統資源分配情況；4.2銀行家算法設Request是請求P的請求向量，Request=K表示進程P需要K個j類資源。P發出資源請求后，按下列步驟進行檢查：如果reques j=needi,j，轉向步驟；否則報錯，所需要的資源數已超過它所宣布的最大值；如果requestjNEEDi或者REQUESTiAVAILABLEi報錯，重新輸入AVAILABLEi-=REQUEST i;ALLOCATIONi+=REQUEST i;NEEDi-=REQUESTi;初始化安全性檢查安全AVAILABLEi+=REQUEST i;ALLOCATIONi-=REQUEST i;NEEDi+=REQUESTi;保持原分配進程執行完釋放資源繼續分