1、操作系統課程設計題目名稱：銀行家算法名學指導教師 編寫日期第一章問題描述1. 課設題目重述設計目的：了解多道程序系統中，多個進程并發執行的資源分配。設計要求：管理員可以把一定數量的作業供多個用戶周轉使用，為保 證作業的安全，管理員規定：當一個用戶對作業的最大需求量不超過管理 員現有的資金就要接納該用戶；用戶可以分期貸款，但貸款的總數不能超 過最大需求量；當管理員現有的作業不能滿足用戶的所需數時，對用戶的 請求可以推遲支付，但總能使用戶在有限的時間里得到請求。當用戶得到 所需的全部作業后，一定能在有限的吋間里歸還所有的作業。2. 問題分析銀行家算法是最具有代表性的避免死鎖的算法。我們可以把操作系

2、統 看作是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向 操作系統請求分配資源相當于用戶向銀行家貸款。在死鎖的避免中，銀行 家算法把系統狀態分為安全狀態和不安全狀態，只要能使系統始終處于安 全狀態，便可以避免發生死鎖。所謂安全狀態，是指系統能按某種順序為 每個進程分配所需資源，直到最大需求，使每一個進程都可以順利完成， 即可找到一個安全資源分配序列。所以我們需要解決問題有：1. 熟悉銀行家算法的工作原理，明口如何判斷系統處于安全狀態，避免死 鎖。2. 在windows操作系統上，如何利用win32 api編寫多線程應用程序實現 銀行家算法。3. 創建n個線程來申請或釋放資源，如何保證

3、系統安全，批準資源申請。4. 通過win 32 api提供的信號量機制，實現共享數據的并發訪問。5. 實驗環境操作系統：wind ows 8.1實驗語言：c+第二章系統設計1. 主要數據結構1. 可利用資源向量avai lableo如果av ailable j二k,則表示系統中現 有rj類資源k個。2. 最大需求矩陣maxo如果max i, j二k,則表示進程i需耍rj類資源的 最大數目為k。3. 分配矩陣all ocationo如果allocation i, j二k,則表示進程i當前 已分得rj類資源的數目為k。4. 需求矩陣necdo如果need i, j二k,則表示進程i還需要rj類資源

4、k 個,方能完成其任務。need li, j =ma x i, j -all ocation i, jo5. 銀行家算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意 的系統性能。在該方法屮把系統的狀態分為安全狀態和不安全狀態，只要 能使系統始終都處于安全狀態，便可以避免發生死鎖。銀行家算法的基本 思想是分配資源之前，判斷系統是否是安全的;若是，才分配。設進程 cusne ed 提出請求 requ est i,如果 request c usneed i, 表示進程pi需要k個rj類型的資源。則銀行家算法按如下規則進行判斷。1. 如果 req uest cusn codneedcu

5、sne edi,則轉向步驟(2)；否則， 出錯，為它所需要的資源數已超過它所宣布的最大值。2. 如果 reque st cusnee dailablecu sneed i,則轉向步驟(3)；否貝施 出錯，因為它所需要的資源數己超過它所宣布的最大值。3. 系統試探分配資源，修改相關數據：availab lei-=req uestcusne cd i;all ocationcu sneed i+二requestc usneed i;needcusn eed i-=r equestcus need i;4. 系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。5.

6、對于某一進程i,若對所有的j,有needij=o ,則表此進程資源分 配完畢，應將占用資源釋放。根據以上步驟，所以銀行家算法流程圖如下所示圖1銀行家算法流程圖6. 安全性檢查算法1. 設置了兩個變量 工作向量work,表示系統可提供給進程繼續運行所需的各類資源數 目。開始時，work :=availabl eo finish,表示系統是否有足夠的資源分配給進程，使之運行完成。開 始時令f inishi：二false；當有足夠的資源分配給進程時，再令 finishi :二true。2. 從進程集合屮找到一個能滿足下述條件的進程：1. finish i =false;2. ne ed i, j w

7、wo rk j；若找到，執行步驟(3),否則，執行步驟(4)。3. 當進程pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資 源，故應執行：work j:二work i +a1 location i , j;finish i : =true;goto step 2;4. 如果所有進程的finish i =true都滿足，則表示系統處于安全狀態; 否則，系統處于不安全狀態。根據以上步驟，所以安全性檢查算法流程圖如下所示:圖2安全性檢查算法流程圖5. 銀行家算法安全性序列分析假定系統屮有五個進程po, pl , p2, p3, p4和三類資源a , b, c,各種資源的數量分別為10、5、

8、7,在t0時刻的資源分配情況如表1 所示：表1 to時刻的資源分配表1. to時刻的安全性：表2 to時刻的安全序列2. p1請求資源：p1發出請求向量requ estl (1,0,2 ),系統按銀行家算法 進行檢查： req uestl (1,0,2) wneedl (1, 2,2) requestl (1, 0,2) wavailable (3, 3,2) 系統先假定可為p 1分配資源，并修改a vailable,allocation 1和needl向量，由此形成的資源變化情況如表2所示：表3系統先假定可為p1分配資源時刻的資源分配表 再利用安全性算法檢查此時系統是否安全。表4 p1申請資

9、源時的安全性檢查3. p4請求資源：p4發出請求向量requ est4 (3, 3, 0 ),系統按銀行家算 法進行檢查： re quest4 (3,3,0) wneed4 (4, 3,1); reques t4 (3,3,0 ) le (2, 3,0 ),讓 p4 等待。第三章源代碼清單1. 函數清單工程中出現的所有自己編寫的函數調用系統的重要函數，他們的函數 功能都被列在這張表屮了，如下表所示：表5自己編寫函數及功能形參列表表6調用系統的重要函數及功能形參列表2. 各函數的調用關系圖圖是本次課程設計工程所有自己編寫的函數調用系統的重要函數的函 數調用關系，箭頭指向某函數表示某函數被調用。圖

10、3各函數的調用關系圖第四章運行結果測試與分析1. 程序的正常輸出結果1.程序剛進入時的界面，5秒倒計時后進入銀行家算法初始化輸入。2.初始化，輸入進程數目，資源種類數，每個進程所需的各種資源，每個 進程現已分配的資源數以及各資源現有數0。初始化后的各進程的資源狀態列表，此時系統是安全的，存在一個安全 序列1->3->0->2->4o進程1進行資源請求分配，請求資源數1,0,2。4.5.第一次分配結果成功，存在一個安全序列：1->3->0->2->4 o因為這是進 程1所需資源數不為0,即ne edl!=0,所以系統不釋放進程1的資源。 第二次分配

11、，4號進程請求系統資源數12 0。預分配后，系統進行安全 性檢測時，不存在一個安全序列，所以請求被拒絕。進程1再次請求資源020。存在一個安全序列1->3 ->0->2->4o這i寸進程1的所需要的資源總數為0,即need=0,所以系統釋放進程1的資源。6.按照一個安全序列，使所有進程都獲得資源并釋放資源。7.程序的差錯控制1.對進入銀行家算法進行輸入控制，輸入40以外的字符，系統提示為非法輸入，用戶重新輸入。2.4.進程最多所需的資源數不能為負，下圖為系統提示哪個進程的第幾個資 源輸入錯誤。進程已分配的資源數不能為負，同時已分配的資源數不能大于進程最多 所需的資源數。

12、下圖為系統提示哪個進程的第幾個資源輸入錯誤。輸入的資源請求不能超過系統所有資源數，以及進程所需資源數。第五章結論與心得本次設計中首先要解決的問題是對所做題目的理解。簡單的文字描述總是 生澀難懂，像銀行家算法這一問題，聯系實際生活中銀行貸款這一現象，再來 看問題時，一切開始顯得清晰，再根據書上對這個問題的描述，便可以把自己 究竟該作何工作搞清楚。明白了需求，下一個難點是如何通過軟件實現。因為這次是一個人一個題 目，所以整個課程設計是自己獨立完成的。本次課程設計對銀行家算法的實現 不同于以往簡單的模擬，需要調用win 32的api來創建線程，以及調用win3 2 api提供的信號量機制，實現共享數

13、據的并發訪問。這些我以前都沒有嘗試過， 所以一開始不知道怎么下手，這也是本次課程設計中我遇到的最大的問題。所 以在正式編程前我先著重了解了一下這些api的使用，編一些程序去實驗這些 api的功能作用，再進行銀行家算法的編程。了解了這些api同時也幫助自己對 信號量，線程有了更深的認識。除此z外，在程序屮，我們也得強調一下對輸入合法性的判斷，比如，我 們輸入的的預申請資源的進程號沒有在系統已存在的進程中，或者進程資源數 不能為負數等等，我們需要對這些情況進行判斷，讓程序報錯返回重新輸入而 不是因錯誤而中斷。通過本次課程設計，我對軟件的開發的過程有了較為深入的了解，雖然只 是對一個問題的簡單實現，但麻雀雖小五臟俱全，我對相關問題的解決已經有