操作系統(tǒng)實驗報告三-銀行家算法

1、銀行家算法操作系統(tǒng)實驗三銀行家算法姓名：楊益林 學號：71115215報告日期：2017.06.07一、實驗目的通過實驗， 加深對多實例資源分配系統(tǒng)中死鎖避免方法銀行家算法的理解，掌握 Windows 環(huán)境下銀行家算法的實現(xiàn)方法，同時鞏固利用 Windows API進行共享數(shù)據(jù)互斥訪問和多線程編程的方法。二、實驗內(nèi)容1.在 Windows 操作系統(tǒng)上，利用 Win32API 編寫多線程應用程序?qū)崿F(xiàn)銀行家算法。2.創(chuàng)建 n 個線程來申請或釋放資源，只有保證系統(tǒng)安全，才會批準資源申請。3.通過 Win32 API 提供的信號量機制，實現(xiàn)共享數(shù)據(jù)的并發(fā)訪問。三、實驗步驟（一）設(shè)計思路：銀行家算法可分

2、為個主要的功能模塊，其描述如下：1.初始化由用戶輸入數(shù)據(jù)，分別對運行的進程數(shù)、總的資源種類數(shù)、總資源數(shù)、各進程所需要的最大資源數(shù)量（Max），已分配的資源數(shù)量賦值。2.安全性檢查算法(1)設(shè)置兩個工作向量Work=AVAILABLE;FINISH=false;(2)從進程集合中找到一個滿足下述條件的進程，F(xiàn)INISH=false;NEED<=Work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Finish=true;(4).如所有的進程Finish= true，則表示安全；否則系統(tǒng)不安全。 3. 銀行家

3、算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。設(shè)進程j提出請求REQUEST i，則銀行家算法按如下規(guī)則進行判斷。(1).如果REQUEST j i<= NEEDji，則轉(zhuǎn)(2)；否則，出錯。(2).如果REQUEST j i<= AVAILABLEji，則轉(zhuǎn)(3)；否則，出錯。(3).系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLEi-=REQ

4、UESTji; ALLOCATIONji+=REQUESTji;NEEDji-=REQUESTji;用到的數(shù)據(jù)結(jié)構(gòu)：實現(xiàn)銀行家算法要有若干數(shù)據(jù)結(jié)構(gòu)，它們用來表示資源分配系統(tǒng)的狀態(tài)。令n表示系統(tǒng)中進程的數(shù)目，m表示資源的分類數(shù)。還需要以下數(shù)據(jù)結(jié)構(gòu)：1).Available是一個長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示j類資源可用的數(shù)量為k。2).Max是一個n×m矩陣，它表示每個進程對資源的最大需求。Max i，j=k，表示進程pi至多可以申請k個j類資源單位。3).Allocation是一個n×m矩陣，它表示當前分給每個進程的資源數(shù)目。Al

5、location i，j=k，表示進程i當前分到k個j類資源。4).Need是一個n×m矩陣，它表示每個進程還缺少多少資源。Needi，j=k，表示進程pi尚需k個j類資源才能完成其任務。顯然Needi，j= Max i，j- Allocation i，j。（二）流程圖四、運行結(jié)果示例這里以書上的例子為例，初值如下表：AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 19 0 0P32 1 12 2 2P40 0 24 3 3現(xiàn)在讓進程P1再申請A:1 B:0 C:2個資源，首先調(diào)用安全算法

6、測試如果分配后系統(tǒng)是否安全，然后給出了分配序列，如下圖：如果再讓P4申請A:0 B:2 C:0個資源，首先調(diào)用安全算法測試如果分配后系統(tǒng)是否安全，發(fā)現(xiàn)分配后系統(tǒng)不安全，于是報分配錯誤，不予分配，結(jié)果如下圖：七、實驗體會銀行家算法的具體實現(xiàn)，我學到了很多課本上沒有的知識。想要完成模擬銀行家算法的C+程序，首先就是要徹底熟悉算法，了解算法的基本原理，才能開始著手程序設(shè)計在程序設(shè)計設(shè)計過程中，遇到了一些困難，通過向同學詢問，翻閱資料等，問題被一一解決了。首先就是在知識層面上了解了銀行家算法這種進程調(diào)度和避免死鎖的算法，并用C+程序真正模擬出安全性檢查和銀行家算法過程，復習了之前所學C+和數(shù)據(jù)結(jié)構(gòu)的知

7、識；在編程過程中雖然遇到很多困難，解決問題的過程中，同時也鍛煉了我不怕困難，勇于迎接挑戰(zhàn)的精神，為以后的工作打下了堅實的基礎(chǔ)。八、源程序并附上注釋#include<iostream>#include<string.h>#include<stdio.h>#include<iomanip>#define False 0#define True 1using namespace std;int Max100100 = 0 ;/各進程所需各類資源的最大需求int ReMax100100 = 0 ;int Avaliable100 = 0 ;/系統(tǒng)可用資源

8、int ReAvaliable100 = 0 ;char name100 = 0 ;/資源的名稱int Allocation100100 = 0 ;/系統(tǒng)已分配資源int ReAllocation100100 = 0 ;int Need100100 = 0 ;/還需要資源int ReNeed100100 = 0 ;int Request100 = 0 ;/請求資源向量int temp100 = 0 ;/存放安全序列int Work100 = 0 ;/存放系統(tǒng)可提供資源int M = 100;/進程的最大數(shù)量為100int N = 100;/資源的最大數(shù)量為100void showdata()/

9、顯示資源矩陣int i, j;cout << endl;cout << " Max Allocation Need Avaliable" << endl;cout << " "for (j = 0; j<4; j+)for (i = 0; i<N; i+)cout << namei << " "cout << " "cout << endl;for (i = 0; i<M; i+)cout <&l

10、t; " " << i << " "for (j = 0; j<N; j+)cout << Maxij << " "cout << " "for (j = 0; j<N; j+)cout << Allocationij << " "cout << " "for (j = 0; j<N; j+)cout << Needij << "

11、 "if (i = 0)cout << " "for (j = 0; j<N; j+)cout << Avaliablej << " "cout << endl;void save()int i, j;for (i = 0; i < N; i+)ReAvaliablei = Avaliablei;for (i = 0; i < M; i+)for (j = 0; j < N; j+)ReMaxij = Maxij;ReAllocationij = Allocationij;

12、ReNeedij = Needij;void restore()int i, j;for (i = 0; i < N; i+)Avaliablei=ReAvaliablei ;for (i = 0; i < M; i+)for (j = 0; j < N; j+)Maxij = ReMaxij;Allocationij = ReAllocationij;Needij = ReNeedij;int changdata(int i)/進行資源分配int j;for (j = 0; j<M; j+) Avaliablej = Avaliablej - Requestj;All

13、ocationij = Allocationij + Requestj;Needij = Needij - Requestj;return 1;int safe()/安全性算法int i, k = 0, m, apply, Finish100 = 0 ;int j;int flag = 0;for (int num = 0; num < N; num+)Worknum = Avaliablenum;for (i = 0; i<M; i+)apply = 0;for (j = 0; j<N; j+)if (Finishi = False&&Needij <

14、= Workj)apply+;if (apply = N)for (m = 0; m<N; m+)Workm = Workm + Allocationim;/變分配數(shù)Finishi = True;tempk = i;i = -1;k+;flag+;for (i = 0; i<M; i+)if (Finishi = False)cout << "系統(tǒng)不安全,所有狀態(tài)不改變！" << endl;/不成功系統(tǒng)不安全return 1;cout << "系統(tǒng)是安全的!" << endl;/如果安全，輸出成

15、功save();/進行保存cout << "安全序列:"for (i = 0; i<M; i+)/輸出運行進程數(shù)組cout << tempi;if (i<M - 1) cout << "->"cout << endl<<endl;return 0;void share()/利用銀行家算法對申請資源對進行判定bool ch=true;int i = 0, j = 0;/ch = 'y'cout << "請輸入請求分配資源的進程號(0-&quo

16、t; << M - 1 << "):"cin >> i;/輸入須申請的資源號cout << "請輸入進程 " << i << " 申請的資源數(shù)量:" << endl;for (j = 0; j<N; j+)cout << namej << ":"cin >> Requestj;/輸入需要申請的資源for (j = 0; j<N; j+)if (Requestj>Needij)/判

17、斷申請是否大于需求，若大于則出錯cout << "進程 " << i << "申請的資源大于它需要的資源"cout << " 分配不合理，不予分配！" << endl;ch = false;break;else if (Requestj>Avaliablej)/判斷申請是否大于當前資源，若大于則 /出錯cout << "進程" << i << "申請的資源大于系統(tǒng)現(xiàn)在可利用的資源"cout &l

18、t;< " 分配出錯，不予分配!" << endl;ch = false;break;if (ch) changdata(i);/根據(jù)進程需求量變換資源if (safe()restore();/根據(jù)進程需求量進行銀行家算法判斷showdata();/根據(jù)進程需求量顯示變換后的資源void changeresources()/修改資源函數(shù)cout << "當前的 Avaliable:" << endl;for (int i = 0; i<N; i+)cout << namei << &

19、quot;:" << Avaliablei << " "cout <<endl<< "輸入修改值:" << endl;for (int i = 0; i < N; i+)cout << namei << ":"cin >> Avaliablei;cout << "修改后的 Avaliable:" << endl;for (int k = 0; k<N; k+)cout <

20、;< namek << ":" << Avaliablek << endl;showdata();safe();int main()/主函數(shù)int i, j, number, m, n, flag;int choice = 1;char ming;cout << "請輸入系統(tǒng)資源的種類數(shù):"cin >> n;N = n;cout << "請依次輸入系統(tǒng)資源的名稱與數(shù)量："<<endl;for (i = 0; i<n; i+)/cout &l

21、t;< "資源" << i + 1 << "的名稱:"cin >> ming>>number;namei = ming;/cout << "資源"<< i + 1 <<"的數(shù)量:"/cin >> number;Avaliablei = number;cout << endl;cout << "請輸入進程的數(shù)量:"cin >> m;M = m;cout <

22、< "請輸入各進程的最大需求量(" << m << "*" << n << "矩陣) Max:" << endl;for (i = 0; i<m; i+)for (j = 0; j < n; j+)cin >> Maxij;doflag = 0;cout << "請輸入各進程已經(jīng)申請的資源量(" << m << "*" << n << "矩陣) Allocation:" << endl;for (i = 0; i<m; i+)for (j = 0; j<n; j+)cin >> Allocationij;if (Allocationij>Maxij)flag = 1;Needij = Maxij - Allocationij;Avaliablej = Aval