實(shí)驗(yàn)2.2 銀行家算法

1、精選文檔實(shí)驗(yàn)2.2 銀行家算法一、 實(shí)驗(yàn)?zāi)康乃梨i會(huì)引起計(jì)算機(jī)工作僵死，因此操作系統(tǒng)中必須防止。本實(shí)驗(yàn)的目的在于讓學(xué)生獨(dú)立的使用高級(jí)語言編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，了解死鎖產(chǎn)生的條件和原因，并采用銀行家算法有效地防止死鎖的發(fā)生，以加深對(duì)課堂上所講授的知識(shí)的理解。二、 實(shí)驗(yàn)要求設(shè)計(jì)有n個(gè)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)，進(jìn)程可動(dòng)態(tài)的申請(qǐng)和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。系統(tǒng)能顯示各個(gè)進(jìn)程申請(qǐng)和釋放資源，以及系統(tǒng)動(dòng)態(tài)分配資源的過程，便于用戶觀察和分析；三、 數(shù)據(jù)結(jié)構(gòu)1 可利用資源向量Available ，它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源的數(shù)目，

2、其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available（j）=k，標(biāo)是系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。2 最大需求矩陣Max，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max（i，j）=k，表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。3 分配矩陣Allocation，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中的每類資源當(dāng)前一分配到每一個(gè)進(jìn)程的資源數(shù)。如果Allocation（i，j）=k，表示進(jìn)程i當(dāng)前已經(jīng)分到Rj類資源的數(shù)目為k。Allocation i表示進(jìn)程i的分配向量，有矩陣Alloc

3、ation的第i行構(gòu)成。4 需求矩陣Need，這是一個(gè)n×m的矩陣，用以表示每個(gè)進(jìn)程還需要的各類資源的數(shù)目。如果Need（i，j）=k，表示進(jìn)程i還需要Rj類資源k個(gè)，才能完成其任務(wù)。Need i表示進(jìn)程i的需求向量，由矩陣Need的第i行構(gòu)成。上述三個(gè)矩陣間存在關(guān)系：Need（i，j）=Max（i，j）-Allocation（i，j）；四、 銀行家算法Request i 是進(jìn)程Pi 的請(qǐng)求向量。Request i （j）=k表示進(jìn)程Pi請(qǐng)求分配Rj類資源k個(gè)。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：1 如果Request i Need，則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯(cuò)，因?yàn)樗?qǐng)

4、求的資源數(shù)已超過它當(dāng)前的最大需求量。2 如果Request i Available，則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無足夠的資源滿足Pi的申請(qǐng)，Pi必須等待。3 系統(tǒng)試探性地把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available = Available - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Request i4 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。如果安全才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。假定

5、系統(tǒng)有5個(gè)進(jìn)程（p0,p1,p2,p3,p4）和三類資源（A，B，C），各種資源的數(shù)量分別為10，5，7，在T0時(shí)刻的資源分配情況如下圖： Max Allocation Need Available A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 3 3 2 ( 2 3 0 )P1 3 2 2 2 0 0 1 2 2 (3 0 2 ) (0 2 0 )P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1五、 安全性算法1 設(shè)置兩個(gè)向量。Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)

6、目，它包含m個(gè)元素，開始執(zhí)行安全性算法時(shí)，Work = Available。Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始Finish（I）=false；當(dāng)有足夠資源分配給進(jìn)程Pi時(shí)，令Finish（i）=true；2 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程。Finish（i）= = false；Need i work；如找到則執(zhí)行步驟3；否則，執(zhí)行步驟4；3 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行Work = work + Allocation i Finish（i）=true；轉(zhuǎn)向步驟2；4 若所有進(jìn)程的Finish（i）都為t

7、rue，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。六、 系統(tǒng)流程圖開 始輸入資源數(shù)m, 及各類資源總數(shù)，初始化Available向量輸入進(jìn)程數(shù)n，i=1輸入進(jìn)程i的最大需求向量max。inmax資源總數(shù)提示錯(cuò)誤重新輸入i加1任選一個(gè)進(jìn)程作為當(dāng)前進(jìn)程輸入該進(jìn)程的資源請(qǐng)求量Request 調(diào)用銀行家算法，及安全性算法，完成分配，或并給出提示該進(jìn)程的Need向量為0該進(jìn)程已運(yùn)行結(jié)束Need矩陣為0所有進(jìn)程運(yùn)行都結(jié)束結(jié) 束NYYNNY初始化need 矩陣NY 七銀行家算法程序代碼#include<stdio.h>#include<conio.h>#include<

8、iostream>using namespace std;typedef struct Max1 / 資源的最大需求量int m_a;int m_b;int m_c;Max; typedef struct Allocation1 /已分配的資源數(shù)int a_a;int a_b;int a_c;Allocation; typedef struct Need1 /還需要的資源數(shù)int n_a;int n_b;int n_c;Need; struct Available1 /可利用的資源量int av_a;int av_b;int av_c; q;struct pr /定義一個(gè)結(jié)構(gòu)char n

9、ame;Max max;Allocation allocation;Need need;int finishflag;p5;char na5;/*void init() /讀入文件"1.txt"cout<<"各進(jìn)程還需要的資源數(shù)NEED："<<endl;FILE *fp;fp=fopen("1.txt","r+"); / 打開文件"1.txt"for(int i=0;i<5;i+)fscanf(fp,"%c,%d,%d,%d,%d,%d,%dn"

10、,&,&pi.max.m_a,&pi.max.m_b,&pi.max.m_c,&pi.allocation.a_a,&pi.allocation.a_b,&pi.allocation.a_c);pi.need.n_a=pi.max.m_a-pi.allocation.a_a;pi.need.n_b=pi.max.m_b-pi.allocation.a_b;pi.need.n_c=pi.max.m_c-pi.allocation.a_c;cout<<<<": "<

11、<pi.need.n_a<<" "<<pi.need.n_b<<" "<<pi.need.n_c<<endl;fclose(fp); /關(guān)閉文件/*int fenpei()/分配資源cout<<"Available:"cout<<q.av_a<<" "<<q.av_b<<" "<<q.av_c<<endl;int finishcnt=0,k=0,c

12、ount=0;for(int j=0;j<5;j+)pj.finishflag=0;while(finishcnt<5)for(int i=0;i<5;i+)if(pi.finishflag=0&&q.av_a>=pi.need.n_a&&q.av_b>=pi.need.n_b&&q.av_c>=pi.need.n_c)q.av_a+=pi.allocation.a_a;q.av_b+=pi.allocation.a_b;q.av_c+=pi.allocation.a_c;pi.finishflag=1;fin

13、ishcnt+;nak+=;break;count+;/禁止循環(huán)過多if(count>5)return 0;return 1;/*int shq() /申請(qǐng)資源int m=0,i=0,j=0,k=0; /m為進(jìn)程號(hào); i,j,k為申請(qǐng)的三類資源數(shù) cout<<"請(qǐng)輸入進(jìn)程號(hào)和請(qǐng)求資源的數(shù)目!"<<endl;cout<<"如：進(jìn)程號(hào) 資源A B C"<<endl;cout<<" 0 2 0 2"<<endl;cin>>m>>

14、;i>>j>>k;if(i<=pm.need.n_a&&j<=pm.need.n_b &&k<=pm.need.n_c)if(i<=q.av_a&&j<=q.av_b&&k<=q.av_c)pm.allocation.a_a+=i;pm.allocation.a_b+=j;pm.allocation.a_c+=k;pm.need.n_a=pm.max.m_a-pm.allocation.a_a;pm.need.n_b=pm.max.m_b-pm.allocation.a_

15、b;pm.need.n_c=pm.max.m_c-pm.allocation.a_c;cout<<"各進(jìn)程還需要的資源數(shù)NEED:"<<'n'for(int w=0;w<5;w+) cout<<<<": "<<pw.need.n_a<<" "<<pw.need.n_b<<" "<<pw.need.n_c<<endl;return 1;elsecout<&l

16、t;"Request>Available讓進(jìn)程"<<m<<"等待."<<endl;else cout<<"Request>Need,讓進(jìn)程"<<m<<"等待."<<endl;return 0;/*void main()int flag;char c;cout<<" /* 銀 行 家 算 法*/ "<<endl;cout<<"確認(rèn)已經(jīng)在"1.txt

17、"文檔中正確輸入各進(jìn)程的有關(guān)信息后按回車鍵"<<endl;getch();init();q.av_a=10; /各種資源的數(shù)量q.av_b=5;q.av_c=7;while(flag)for(int i=0;i<5;i+)q.av_a-= pi.allocation.a_a;q.av_b-= pi.allocation.a_b;q.av_c-= pi.allocation.a_c;if(fenpei()cout<<"這樣配置資源是安全的!"<<endl;cout<<"其安全序列是： "for(int k=0;k<5;k+)cout<<"->"<<nak;cout<<endl;cout<<"有進(jìn)程發(fā)出Request