PAGE銀行家算法課程設計報告PAGE5/20目錄一、需求分析…………………2二、系統概要設計……………2三、系統詳細設計………………4四、系統主要源代碼……………5五、系統測試及調試……………5六.、心得體會……………………8七、參考文獻……………………9八、附錄…………9

操作系統課程設計報告課設內容簡介：銀行家算法的模擬實現。一、需求分析控制工作流程，管理資源，為用戶服務，是操作系統的主要功能。在資源管理中，操作系統的任務是使各種系統資源得到充分合理的應用，解決用戶作業因資源而產生的矛盾，并合理的讓用戶再合適的時間內得到其應有的服務。現代操作系統引入了多道程序設計技術，允許鎖個進程同時駐留內存并發執行。若干個進程將不可避免地競爭系統資源，如果操作系統不能夠協調多個進程對系統資源的競爭與共享，將會導致執行結果異常，系統不穩定、失效等多種問題，從而產生死鎖，產生死鎖的原因可分為兩種：（1）競爭資源引起死鎖（2）進程推進順序不當引起死鎖。銀行家算法是一種代表性的避免死鎖的算法，在進程申請資源的時候，系統調用銀行家算法來檢測此次分配會不會導致死鎖的產生，及判斷此次分配的安全性。若檢測到此次分配是安全的則分配給申請進程所申請的資源，若檢測到此次分配是不安全的，則相應的進程等待。二、系統概要設計（1）系統主要功能：系統運用銀行家算法先對用戶提出的計算機系統資源請求進行合法性檢查，再進行預分配，利用安全性檢查算法進行安全性檢查，后決定是否給相應進程動態分配資源。（2）系統模塊功能結構：（3）運行環境要求：相關工具：MicrosoftVisualC++6.（4）數據結構設計及相關說明：

（1）、可利用資源向量

INT

AVAILABLE[M]

M為資源的類型。

（2）、最大需求矩陣

INT

MAX[N][M]

N為進程的數量。

（3）、已分配矩陣

INT

ALLOCATION[N][M]

（4）、還需求矩陣

INT

NEED[N][N]

（5）、申請各類資源數量intRequest[x];//

（6）、工作向量

intWork[x];

（7）、intFinish[y];//表示系統是否有足夠的資源分配給進程，0為否，非0為是

三、系統詳細設計

（1）、系統初始化。輸入進程數量，資源種類，各進程已分配、還需求各資源數量，各資源可用數量等

（2）、輸入用戶的請求三元組（I，J，K），為進程I申請K個J類資源。

（3）、檢查用戶的請求是否小于還需求的數量，條件是K<=NEED[I,J]。如果條件不符則提示重新輸

入，即不允許索取大于需求量

（4）、檢查用戶的請求是否小于系統中的可利用資源數量，條件是K<=AVALIABLE[I,J]。如果條件不

符則申請失敗，阻塞該進程，重新進行進程動態資源申請（使用goto語句）

（5）、進行資源的預分配，語句如下：

AVALIBLE[I][J]=AVALIBLE[I][J]-K；

ALLOCATION[I][J]=ALLOCATION[I][J]+K；

NEED[I][J]=NEED[I][J]-K；

（6）、系統調用安全性檢查算法（safe()函數）進行檢查，如果檢查通過，則不用回收，否則進行

回收，進程資源申請失敗進入等待。

4、安全性檢查算法（safe()子函數）

（1）、設置兩個臨時變量。

（2）、在進程中查找符合以下條件的進程。

條件1：FINISH[I]=0

條件2：NEED[I][J]〈=WORK[J]

（3）、如果查找成功則進行資源的模擬回收，語句如下：

WORK[J]=WORK[J]+ALLOCATION[I][J]；

FINISH[I]=1或查找到的順序號

（4）、如果查找不成功，則檢查所有進程的FINISH[]，如果有一個為0，則系統不為0，返回不成功

標志。否則返回成功標志。四、系統主要原代碼見附錄！！五、系統測試及調試5.1

5.3

出現問題及解決方案：本程序考慮了程序功能實現、格式顯示合理化、輸入錯誤異常處理等各個方面的設計，盡可能使程序設計的更加完美。在長期的設計調試過程中遇到過許多問題，通過網上搜索、查詢資料、調試試驗等方法一一解決。下面大致羅列一些主要問題：5.3.1關于輸入錯誤的異常處理：數字判斷在調試程序過程中我們都知道在要求輸入整型數據時，如不小心鍵入字母符號等，則程序立即出錯；還有如在要求輸入一個字符時，如果不小心輸入為了字符串，則也會出錯（此時多鍵入的字符被保留在緩沖區內，當下次要求屏幕輸入時先從緩沖區取出導致出錯）。因此設計了一個判斷函數intshuzi(intn);

進行處理此類輸入異常錯誤。此函數主要設計思路為：定義一個動態字符串指針，輸入后判斷每個輸入的字符是否在’0’—‘9’之間來判斷是否輸入的為數字字符，然后按照字符ASCII碼值與數字值的關系將輸入的字符轉換為整數。而對于字符輸入的問題，可以定義為一個動態字符串指針然后只取輸入的第一個字符內容。5.3.2關于某些判斷算法優劣問題：在程序中很多地方都會用到循環判斷是否符合條件的算法，在設計這些算法時有很多方法，而有的算法可以更節省時間。如下安全性算法中尋找尋找符合Finish[i]==0條件的進程的例子：/*算法一：

for(j=0;j<m;j++)

if(Work[j]>=Need[i][j])counter=counter+1;//記數

if(counter==m){…*/

//算法二：

for(j=0;j<m;j++)

if(Work[j]>=Need[i][j]);

//可用大于等于需求

else{

counter=1;

break;

}

if(counter!=1){…顯然算法二要優于算法一。本程序中還有很多類似的地方。這里主要考慮的是一個程序的優化設計問題。六、心得體會在設計此程序的過程中，我遇到過許多問題，也學到了很多東西。本程序的設計實現主要是用C++語言實現，通過對程序算法的設計優化、輸出顯示的格式設計、輸入過程中的異常處理等一些設計過程中的問題的考慮解決，在C++學習上也有了很大的進步。程序設計過程中開始遇到的最大的問題是算法的結構設計問題，課本上只給了設計要求及簡單的算法，要真正實現還需要考慮很多方面。在算法的數據結構設計上考慮了很長時間。在程序設計中先后參考了很多網絡資料，也參考了一些別人寫的的程序，綜合這些算法思想和自己的思路對程序做了很好的設計方式，對一些算法的優越性等也作了一些考慮。此外考慮最多的就是異常錯誤處理的設計。一個好的程序必須能在各種環境下都有其相應的處理方式，至少能應對一些常見的可能發生的錯誤。在課程設計過程中遇到了許多問題，也向同宿舍的同學做了一些請教一起討論，也因此從他們身上學到了許多東西。七、參考文獻[1]湯子瀛等.《計算機操作系統》.西安：西安電子科技大學出版社，2006.10.[2]劉璟等.《高級語言c++程序設計》.北京：高等教育出版社，2006.03.[3]胡志剛、譚長庚.計算機操作系統.中南大學出版社.2005.7[4]張堯學.計算機操作系統教程（第二版）.清華大學出版社.2000.8八、附錄#include<iostream.h>

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<string.h>//===定義全局變量===

constintx=50,y=100;

intAvailable[x];

intAllocation[y][y];

intMax[y][y];

intNeed[y][y];

intRequest[x];

intWork[x];

intFinish[y];

intp[y];inti,j;

intn,m;

//n為進程的數量,m為資源種類數

intl=0,counter=0;

//函數聲明

intshuzi(intsz);

voidchushihua();

//系統初始化函數

voidsafe();

//安全性算法函數

voidbank();

//銀行家算法函數

voidshowdata();

//===數字判斷函數===

intshuzi(intsz){

char*temp;

temp=newchar;

intlen;

sz=0;//清零

chars;//

do{

//gets(temp);

//getline(cin,temp)

cin>>temp;

len=strlen(temp);

for(inti=0;i<len;i++){

s=*(temp+i);

if(s<'0'||s>'9'){

cout<<"抱歉，輸錯了!你輸入的是數字嗎?!\n\n";

cout<<"請重新輸入：";

break;

}

}

}while(s<'0'||s>'9');

for(inti=0;i<len;i++){

/

intt=1;

for(intj=1;j<len-i;j++)t*=10;

sz+=(*(temp+i)-48)*t;

}

returnsz;

}

//===系統初始化函數===

voidchushihua(){

//===系統初始化輸入===

cout<<"%%程序開始，系統初始化輸入%%"<<endl;

//<<endl

cout<<"==============================================================="<<endl<<endl;

cout<<"請輸入進程的數量:"

n=shuzi(n);

cout<<"請輸入資源種類數:";

m=shuzi(m);

cout<<endl<<endl<<"請輸入各種資源可利用的數量("<<m<<"種):"<<endl;

cout<<endl;

for(j=0;j<m;j++){

cout<<"

輸入資源"<<j<<"可利用的數量Available["<<j<<"]:";

Available[j]=shuzi(Available[j]);

Work[j]=Available[j];

//初始化Work[j]

//

cout<<endl;

}

//system("cls");

//清屏

cout<<endl;

cout<<"請輸入各進程當前已分配的資源數量Allocation["<<n<<"]["<<m<<"]:"<<endl<<endl;

for(i=0;i<n;i++){

for(j=0;j<m;j++){

cout<<"

請輸入進程"<<i<<"當前已分配的資源"<<j<<"數量:";

Allocation[i][j]=shuzi(Allocation[i][j]);

}

cout<<endl;

Finish[i]=0;//初始化Finish[i]

//break;

}

cout<<endl<<endl;

cout<<"請輸入各進程對各類資源的最大需求數Max["<<n<<"]["<<m<<"]:"<<endl<<endl;

for(i=0;i<n;i++){

for(j=0;j<m;j++){

cout<<"

請輸入進程"<<i<<"對資源"<<j<<"的最大需求數:";

Max[i][j]=shuzi(Max[i][j]);

if(Max[i][j]>=Allocation[i][j])

//

Need[i][j]=Max[i][j]-Allocation[i][j];

//計算還需求量

else

Need[i][j]=0;

}

cout<<endl;

}

cout<<endl<<"%%初始化完成!%%"<<endl;

}//===安全性算法函數===

voidsafe(){

l=0;

for(i=0;i<n;){

//i++

if(Finish[i]==0){

//尋找Finish[i]==0的進程

條件一

counter=0;

//記數器

for(j=0;j<m;j++)

if(Work[j]>=Need[i][j]);

//可用大于等于需求

else{

counter=1;

break;

}

if(counter!=1){//進程的每類資源量都符合條件Work[j]>=Need[i][j]

條件二

p[l]=i;

//存儲安全序列

Finish[i]=1;

for(j=0;j<m;j++){

Work[j]=Work[j]+Allocation[i][j];

}

l=l+1;

i=-1;

}

}

i++;

}

}

//===顯示分配情況函數===

voidshowdata()//函數showdata,輸出當前資源分配情況

{

inti,j;//局部變量

intAll[y];//各種資源的總數量

intl2;//局部變量

l1,

cout<<"==============================================================="<<endl<<endl;

cout<<"%%系統當前狀態如下：%%"<<endl<<endl;cout<<"%%各種資源的總數量(all):"<<endl;

for(j=0;j<m;j++){

cout<<"資源"<<j<<":";

All[j]=Available[j];

for(i=0;i<n;i++){

All[j]+=Allocation[i][j];

cout<<All[j]<<"

";

if((j+1)%5==0)cout<<endl;

//每行顯示五個

&&j!=0

}

cout<<endl<<endl;

cout<<"%%系統目前各種資源可用的數為(available):"<<endl;

for(j=0;j<m;j++){

cout<<"資源"<<j<<":"<<Available[j]<<"

";

if((j+1)%5==0)cout<<endl;//每行最多顯示五個

&&j!=0

}

cout<<endl<<endl;

cout<<"%%各進程已經得到的資源量(allocation):"<<endl;

//

l1=0;

//歸零

for(i=0;i<=m/5;i++){

for(j=i*5;j<i*5+5&&j<m;j++)cout<<"

資源"<<j;

cout<<endl;

for(l2=0;l2<n;l2++){

cout<<"進程"<<l2<<":";

for(j=i*5;j<i*5+5&&j<m;j++)cout<<Allocation[l2][j]<<"

";

cout<<endl;

}

}

cout<<endl;

cout<<"%%各進程還需要的資源量(need):"<<endl;

//<<endl

//l1=0;

for(i=0;i<=m/5;i++){

//設計每行顯示五種資源

for(j=i*5;j<i*5+5&&j<m;j++)cout<<"

資源"<<j;

cout<<endl;

for(l2=0;l2<n;l2++){

cout<<"進程"<<l2<<":";

for(j=i*5;j<i*5+5&&j<m;j++)cout<<Need[l2][j]<<"

";

cout<<endl;

}

}

//===銀行家算法函數===

voidbank(){

cout<<"==============================================================="<<endl<<endl;

cout<<"%%以下開始為進程進行資源分配申請%%"<<endl<<endl;

//===申請資源===

intk=0;//用于輸入進程編號

boolr=false;

//初值為假，輸入Y繼續申請則置為真

do{

//輸入請求

cout<<"請輸入申請資源的進程編號(輸入0--"<<n-1<<"之間):";

k=shuzi(k);

cout<<endl;

while(k>n-1){//輸入異常處理

cout<<endl<<"您輸入了錯誤的進程號，請重新輸入!"<<endl;

cout<<endl<<"請輸入申請資源的進程編號(輸入0--"<<n-1<<"之間):";

k=shuzi(k);

cout<<endl;

}

cout<<endl<<"請輸入該進程申請各類資源的數量:"<<endl;

for(j=0;j<m;j++){

do{

cout<<"進程"<<k<<"申請資源["<<j<<"]的數量:";

Request[j]=shuzi(Request[j]);

cout<<endl;

if(Request[j]>Need[k][j]){

cout<<"申請大于需要量!!!"<<endl;

cout<<"您申請資源"<<j<<"的數量為"<<Request[j]<<",大于進程"<<k<<"對該資源需求量"<<Need[k][j]<<"。"<<endl;

cout<<"請重新輸入!!!"<<endl;

}

else

if(Request[j]>Available[j]){

cout<<"\n沒有那么多資源，目前可利用資源"<<j<<"數量為"<<Available[j]<<",本次申請不成功，進程等待!!!"<<endl;

Finish[k]=0;

//該進程等待

gotoppp;

}

}while(Request[j]>Need[k][j]);

//Request[j]>Available[j]||

}

//改變Avilable、Allocation、Need的值

for(j=0;j<m;j++){

Available[j]=Available[j]-Request[j];

Allocation[k][j]=Allocation[k][j]+Request[j];

Need[k][j]=Need[k][j]-Request[j];

Work[j]=Available[j];

}

//判斷當前狀態的安全性

safe();

//調用安全性算法函數

if(l<n){

l=0;

cout<<"\n當前狀態不安全,不予分配!!!!!!"<<endl;

//恢復數據

for(j=0;j<m;j++){

Available[j]=Available[j]+Request[j];

Allocation[k][j]=Allocation[k][j]-Request[j];

Need[k][j]=Need[k][j]+Request[j];

Work[j]=Available[j];

}

for(i=0;i<n;i++)

Finish[i]=0;

/

}

else{

//

system("cls");

l=0;

cout<<"\n申請資源成功!!!"<<endl;//===========================================

/*

for(j=0;j<m;j++)if(Need[k][j]==0)l=l+1;

if(l==m){

//此處借用l做下計數器

for(j=0;j<m;j++){

Available[j]=Available[j]+Max[k][j];

Allocation[k][j]=0;

}

}

l=0;

//歸零

//===========================================

cout<<"\n安全的狀態!!!"<<endl;

cout<<"安全序列為:

";

cout<<endl<<"進程"<<"("<<p[0]<<")";

Finish[0]=0;

for(i=1;i<n;i++){

cout<<"==>>"<<"進程"<<"("<<p[i]<<")";

Finish[i]=0;//所有進程置為未分配狀態

}

cout<<endl<<endl;

}

showdata();

//顯