銀行家算法模擬程序設(shè)計(jì)

銀行家算法模擬程序設(shè)計(jì)目錄一、課程設(shè)計(jì)的目的 3二、課程設(shè)計(jì)的要求 3三、課程設(shè)計(jì)題目描述 3四、算法流程圖 41、銀行家算法流程圖 42、安全性檢查算法流程圖 5五、課程設(shè)計(jì)之銀行家算法原理 51．銀行家算法的思路 52．銀行家算法 53．安全性檢查算法（IsSafe()函數(shù)） 6六、源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn) 71．程序結(jié)構(gòu) 72．?dāng)?shù)據(jù)結(jié)構(gòu) 73．函數(shù)聲明 84.源代碼 86.運(yùn)行界面 14七、課程設(shè)計(jì)的總結(jié) 16一、課程設(shè)計(jì)的目的操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的核心系統(tǒng)軟件，它負(fù)責(zé)控制和管理整個(gè)系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些資源，使計(jì)算機(jī)高效的工作。《操作系統(tǒng)課程設(shè)計(jì)》是《操作系統(tǒng)》理論課的必要補(bǔ)充，是復(fù)習(xí)和檢驗(yàn)所學(xué)課程的重要手段，本課程設(shè)計(jì)的目的是綜合應(yīng)用學(xué)生所學(xué)知識(shí)，通過(guò)實(shí)驗(yàn)環(huán)節(jié)，加深學(xué)生對(duì)操作系統(tǒng)基本原理和工作過(guò)程的理解，提高學(xué)生獨(dú)立分析問題、解決問題的能力，增強(qiáng)學(xué)生的動(dòng)手能力。二、課程設(shè)計(jì)的要求1．分析設(shè)計(jì)內(nèi)容，給出解決方案（要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。2．畫出程序的基本結(jié)構(gòu)框圖和流程圖。3．對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析說(shuō)明。4．源代碼格式要規(guī)范。5．設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析。6．設(shè)計(jì)中遇到的問題，設(shè)計(jì)的心得體會(huì)。7．按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計(jì)報(bào)告。三、課程設(shè)計(jì)題目描述銀行家算法是一種最有代表性的避免死鎖的算法。

要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。

安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。

不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。

安全序列：一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(j<i)當(dāng)前占有資源量之和。

銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。四、算法流程圖錯(cuò)誤Requesti<=Needi?1、銀行家算法流程圖 錯(cuò)誤Requesti<=Needi? 否 是進(jìn)程Pi阻塞Requesti<=Available?進(jìn)程Pi阻塞Requesti<=Available? 否是試分配：試分配：Available-=RequestiAllocationi+=RequestiNeedi-=Requesti試將分配作廢，恢復(fù)原資源分配狀態(tài)執(zhí)行安全性算法，檢查試將分配作廢，恢復(fù)原資源分配狀態(tài)執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)安全正式分配正式分配2、安全性檢查算法流程圖Work=AvailableWork=AvailableFinish[i]=0找一個(gè)滿足下列條件的進(jìn)程Finish[i]=0且Needi<Work所有進(jìn)程的Finish[i]=1?找一個(gè)滿足下列條件的進(jìn)程Finish[i]=0且Needi<Work所有進(jìn)程的Finish[i]=1? 是 不是 找到系統(tǒng)處于安全狀態(tài)系統(tǒng)處于不系統(tǒng)處于安全狀態(tài)系統(tǒng)處于不安全狀態(tài)Work+=AllocationFinish[i]=1五、課程設(shè)計(jì)之銀行家算法原理1．銀行家算法的思路先對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求的是不大于需要的，是否不大于可利用的。若請(qǐng)求合法，則進(jìn)行試分配。最后對(duì)試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來(lái)狀態(tài)，拒絕申請(qǐng)。2．銀行家算法進(jìn)程mi發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資源，Request[mi][j]=k(1)Request[mi][j]<=need[mi][j],檢查申請(qǐng)量是否不大于需求量,若條件不符重新輸入，不允許申請(qǐng)大于需求量。(2)Request[mi][j]<=available[mi][j]，檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資源數(shù)量,若條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，重新申請(qǐng)資源。(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[i]-=Request[mi][i]; Allocation[mi][i]+=Request[mi][i]; Need[mi][i]-=Request[mi][i](4)試分配后，執(zhí)行安全性檢查，調(diào)用IsSafe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓該進(jìn)程等待。(5)用while循環(huán)語(yǔ)句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。3．安全性檢查算法（IsSafe()函數(shù)）(1)設(shè)置兩個(gè)向量：工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時(shí)，Work=Available。Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]=0；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令Finish[i]=1。(2)在進(jìn)程中查找符合以下條件的進(jìn)程：條件1：Finish[i]=0；條件2：need[i][j]<=Work[j]若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；(4)如果所有的Finish[i]=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)六、源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn)1．程序結(jié)構(gòu)程序共有以下七個(gè)部分：安全性檢查IsSafe()：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。初始化算法1Read()：用于程序開始進(jìn)行初始化數(shù)據(jù)，從文件中讀入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對(duì)各類資源最大需求數(shù)等。初始化算法2Input()：用于程序開始進(jìn)行初始化數(shù)據(jù)，從鍵盤上輸入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對(duì)各類資源最大需求數(shù)等。Init():進(jìn)行銀行家算法模擬實(shí)現(xiàn)的模塊，調(diào)用其他各個(gè)模塊進(jìn)行銀行家算法模擬過(guò)程。Menu():顯示菜單。Design()：主界面設(shè)計(jì)模塊。主函數(shù)main()：逐個(gè)調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進(jìn)行2．?dāng)?shù)據(jù)結(jié)構(gòu)銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)：intAvailable[100]//各種資源可利用的數(shù)量intAllocation[50][100]//各進(jìn)程當(dāng)前已分配的資源數(shù)量intMax[50][100]//各進(jìn)程對(duì)各類資源的最大需求數(shù)intNeed[50][100]//需求矩陣intRequest[50][100]//申請(qǐng)各類資源的數(shù)量intWork[100]//工作向量，表系統(tǒng)可提供給進(jìn)程運(yùn)行所需各類資源數(shù)量intFinish[50]//表系統(tǒng)是否有足夠的資源分配給進(jìn)程，0為否，1為是intp[50];//存儲(chǔ)安全序列intm，n;//m為進(jìn)程的數(shù)量,n為資源種類數(shù)3．函數(shù)聲明intIsSafe();//安全性檢測(cè)voidRead();//從文件讀入數(shù)據(jù)voidInput();//從鍵盤輸入數(shù)據(jù)voidInit();//銀行家算法voidMenu();//菜單voidDesign();//主界面設(shè)計(jì)4.源代碼#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<conio.h>voidmain(){ Design();printf("┃請(qǐng)按任意鍵進(jìn)行初始化操作...┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); printf(">>>"); getch(); system("cls"); cout<<"請(qǐng)輸入進(jìn)程的數(shù)目:"; cin>>m; cout<<"請(qǐng)輸入資源種類:";cin>>n; Menu();}intIsSafe(){ inti,j,k; intlen=-1;///記錄安全序列的進(jìn)程個(gè)數(shù)，如果len==m，即表示處于安全狀態(tài) int Work[100]; for(i=0;i<n;i++) {Work[i]=Available[i]; } for(i=0;i<m;i++) Finish[i]=0;for(i=0;i<m;i++) {if(Finish[i]==1)continue; else { for(j=0;j<n;j++) { Need[i][j]=Max[i][j]-Allocation[i][j];if(Need[i][j]>Work[j])break; if(Need[i][j]<0)return0; } if(j==n){ for(k=0;k<n;k++)Work[k]+=Allocation[i][k]; Finish[i]=1; len++; p[len]=i; i=-1; } elsecontinue; } } if(len==m-1) { cout<<"系統(tǒng)是安全的\n"; cout<<"安全序列是:"; for(i=0;i<=len;i++) { cout<<p[i]; if(i!=len)cout<<"-->"; } cout<<endl; return1; } elsereturn0;}voidRead(){inti,j;FILE*fp;fp=fopen("Max.txt","r+"); cout<<"從Max.txt文件中讀入數(shù)據(jù)，則每個(gè)進(jìn)程最多需要的各類資源數(shù)為:"<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { fscanf(fp,"%d",&Max[i][j]); cout<<Max[i][j]<<""; } cout<<endl; } fclose(fp);fp=fopen("Allocation.txt","r+"); cout<<"從Allocation.txt文件中讀入數(shù)據(jù)，則每個(gè)進(jìn)程已分配的各類資源數(shù)為:"<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { fscanf(fp,"%d",&Allocation[i][j]); cout<<Allocation[i][j]<<""; Need[i][j]=Max[i][j]-Allocation[i][j]; } cout<<endl; } fclose(fp); fp=fopen("Available.txt","r+"); cout<<"從Available.txt文件中讀入數(shù)據(jù)，則現(xiàn)有空閑各類資源數(shù)為:"; for(i=0;i<n;i++) { fscanf(fp,"%d",&Available[i]); cout<<Available[i]<<""; }cout<<endl; fclose(fp);}voidInput(){inti,j; cout<<"輸入每個(gè)進(jìn)程最多所需的各類資源數(shù)，按照"<<m<<"*"<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i++) {for(j=0;j<n;j++) { cin>>Max[i][j]; } }cout<<"輸入每個(gè)進(jìn)程已分配的各類資源數(shù)，按照"<<m<<"*"<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i++) {for(j=0;j<n;j++) { cin>>Allocation[i][j]; } } for(i=0;i<m;i++) {for(j=0;j<n;j++) { Need[i][j]=Max[i][j]-Allocation[i][j]; if(Need[i][j]<0) { cout<<"你輸入的第"<<i+1<<"個(gè)進(jìn)程的第"<<j+1<<"個(gè)資源數(shù)錯(cuò)誤，請(qǐng)重新輸入"<<endl; j--; continue; } } }cout<<"請(qǐng)輸入現(xiàn)有未分配的各類資源數(shù)目："; for(i=0;i<n;i++) { cin>>Available[i]; }}voidInit(){ inti,mi; charok;IsSafe(); while(1)//死循環(huán)，只要括號(hào)里為非零，就一直循環(huán)這條句子。 { cout<<"請(qǐng)輸入要申請(qǐng)資源的進(jìn)程號(hào)(第一個(gè)進(jìn)程號(hào)為0，以此類推)"; cin>>mi; cout<<"請(qǐng)輸入該進(jìn)程所請(qǐng)求的各類資源的數(shù)目:"; for(i=0;i<n;i++)cin>>Request[mi][i];for(i=0;i<n;i++) {while(Request[mi][i]>Need[mi][i]) { cout<<"你輸入的請(qǐng)求數(shù)超過(guò)進(jìn)程的需求數(shù)，錯(cuò)誤！"<<endl; break; } while(Request[mi][i]>Available[i]) {cout<<"你輸入的請(qǐng)求數(shù)超過(guò)系統(tǒng)的資源數(shù)，系統(tǒng)無(wú)法滿足！"<<endl;break; } break; }for(i=0;i<n;i++) { Available[i]-=Request[mi][i]; Allocation[mi][i]+=Request[mi][i]; Need[mi][i]-=Request[mi][i]; } if(IsSafe())cout<<"系統(tǒng)成功分配資源！"<<endl; else { cout<<"系統(tǒng)未能成分配資源,收回預(yù)分配資源！"<<endl; for(i=0;i<n;i++) {Available[i]+=Request[mi][i]; Allocation[mi][i]-=Request[mi][i]; Need[mi][i]+=Request[mi][i]; } } for(i=0;i<m;i++)Finish[i]=0;cout<<"你還想再次請(qǐng)求分配嗎？是請(qǐng)按y/Y,否請(qǐng)按n/N:"; while(1) { cin>>ok; if(ok=='y'||ok=='Y'||ok=='n'||ok=='N')break; elsecontinue; } if(ok=='y'||ok=='Y')continue; else { system("cls"); Menu(); } } }voidMenu(){intcode;printf("***********************\n"); printf("*請(qǐng)選擇：*\n"); printf("**\n"); printf("*1.從文件中讀入數(shù)據(jù)*\n");printf("*2.從鍵盤輸入數(shù)據(jù)*\n"); printf("*3.退出*\n"); printf("***********************\n"); printf("請(qǐng)選擇操作：\b\b");scanf("%d",&code); do { switch(code) { case1:Read(); Init(); break; case2:Input(); Init(); break; case3:system("cls"); Design(); printf("┃謝謝使用銀行家算法!┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━