?? suanfa1computer.cpp
字號:
#include "string.h"
#include "iostream"
using namespace std;
#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int M ; //總進程數(shù)
int N ; //資源種類
int ALL_RESOURCE[W];//各種資源的數(shù)目總和
int MAX[W][R]; //M個進程對N類資源最大資源需求量
int AVAILABLE[R]; //系統(tǒng)可用資源數(shù)
int ALLOCATION[W][R]; //M個進程已經(jīng)得到N類資源的資源量
int NEED[W][R]; //M個進程還需要N類資源的資源量
int Request[R]; //請求資源個數(shù)
void showdata() //函數(shù)showdata,輸出資源分配情況
{
int i,j;
cout<<"各種資源的總數(shù)量(all):"<<endl;
cout<<" ";
for (j=0;j<N;j++)cout<<" 資源"<<j<<": "<<ALL_RESOURCE[j];
cout<<endl<<endl;
cout<<"系統(tǒng)目前各種資源可用的數(shù)為(available):"<<endl;
cout<<" ";
for (j=0;j<N;j++)cout<<" 資源"<<j<<": "<<AVAILABLE[j];
cout<<endl<<endl;
cout<<" 各進程還需要的資源量(need):"<<endl<<endl;
cout<<" 資源"<<" 資源"<<" 資源"<<endl;
for (i=0;i<M;i++)
for (i=0;i<M;i++)
{
cout<<"進程p"<<i<<": ";
for (j=0;j<N;j++)cout<<NEED[i][j]<<" ";;
cout<<endl;
}
cout<<endl;
cout<<" 各進程已經(jīng)得到的資源量(allocation): "<<endl<<endl;
cout<<" 資源"<<" 資源"<<" 資源"<<endl;
for (i=0;i<M;i++)
{
cout<<"進程p"<<i<<": ";
for (j=0;j<N;j++)cout<<ALLOCATION[i][j]<<" ";
cout<<endl;
}
cout<<endl;
};
void changdata(int k) //函數(shù)changdata,改變可用資源和已經(jīng)拿到資源和還需要的資源的值
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
};
void rstordata(int k) //函數(shù)rstordata,恢復可用資源和已經(jīng)拿到資源和還需要的資源的值
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
};
int chkerr(int s) //函數(shù)chkerr,檢查是否安全
{
int WORK,FINISH[W],temp[R];
int i,j,k=0;
for(i=0;i<M;i++)FINISH[i]=FALSE;
for(j=0;j<N;j++)
{
WORK=AVAILABLE[j];
i=s;
while(i<M)
{
if (FINISH[i]==FALSE&&NEED[i][j]<=WORK)
{
WORK=WORK+ALLOCATION[i][j];
FINISH[i]=TRUE;
temp[k]=i;
k++;
i=0;
}
else
{
i++;
}
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 系統(tǒng)不安全!!! 本次資源申請不成功!!!"<<endl;
cout<<endl;
return 1;
}
}
cout<<endl;
cout<<" 經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。"<<endl;
cout<<endl;
cout<<" 本次安全序列：";
for(i=0;i<M;i++)cout<<"p"<<temp[i]<<"->";
cout<<endl<<endl;
return 0;
}
附錄
int chkerr2(int s) //函數(shù)chkerr2,檢查是否安全
{
int WORK,FINISH[W],temp[R];
int i,j,k=0;
for(i=0;i<M;i++)FINISH[i]=FALSE;
for(j=0;j<N;j++)
{
WORK=AVAILABLE[j];
i=s;
while(i<M)
{
if (FINISH[i]==FALSE&&NEED[i][j]<=WORK)
{
WORK=WORK+ALLOCATION[i][j];
FINISH[i]=TRUE;
temp[k]=i;
k++;
i=0;
}
else
{
i++;
}
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 本次資源申請成功!!!但系統(tǒng)不安全!!! "<<endl;
cout<<endl;
return 1;
}
}
cout<<endl;
cout<<" 經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。"<<endl;
cout<<endl;
cout<<" 本次安全序列：";
for(i=0;i<M;i++)cout<<"p"<<temp[i]<<"->";
cout<<endl<<endl;
return 0;
}
void bank() //銀行家算法
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
cout<<" 請輸入需申請資源的進程號（從P0到P"<<M-1<<"，否則重輸入!）:";
cout<<"p";cin>>i;
if(i<0||i>=M)cout<<" 輸入的進程號不存在，重新輸入!"<<endl;
}
cout<<" 請輸入進程P"<<i<<"申請的資源數(shù):"<<endl;
for (j=0;j<N;j++)
{
cout<<" 資源"<<j<<": ";
cin>>Request[j];
if(Request[j]>NEED[i][j])
{
cout<<" 進程P"<<i<<"申請的資源數(shù)大于進程P"<<i<<"還需要"<<j<<"類資源的資源量!";
cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl;
flag='N';
break;
}
else
{
if(Request[j]>AVAILABLE[j])
{
cout<<" 進程P"<<i<<"申請的資源數(shù)大于系統(tǒng)可用"<<j<<"類資源的資源量!";
cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl;
flag='N';
break;
}
}
}
if(flag=='Y'||flag=='y')
{
changdata(i);
if(chkerr(i))
{
rstordata(i);
showdata();
}
else
showdata();
}
else
showdata();
cout<<endl;
cout<<" 是否繼續(xù)銀行家算法演示,按'Y'或'y'鍵繼續(xù),按'N'或'n'鍵退出演示: ";
cin>>flag;
}
}
void randomallocation() //隨機分配算法
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
cout<<" 請輸入需申請資源的進程號（從P0到P"<<M-1<<"，否則重輸入!）:";
cout<<"p";cin>>i;
if(i<0||i>=M)cout<<" 輸入的進程號不存在，重新輸入!"<<endl;
}
cout<<" 請輸入進程P"<<i<<"申請的資源數(shù):"<<endl;
for (j=0;j<N;j++)
{
cout<<" 資源"<<j<<": ";
cin>>Request[j];
if(Request[j]>AVAILABLE[j])
{
cout<<" 進程P"<<i<<"申請的資源數(shù)大于系統(tǒng)可用"<<j<<"類資源的資源量!";
cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl;
flag='N';
break;
}
}
if(flag=='Y'||flag=='y')
{
changdata(i);
showdata();
chkerr2(i);
}
cout<<" 是否繼續(xù)隨機分配算法演示,按'Y'或'y'鍵繼續(xù),按'N'或'n'鍵退出演示: ";
cin>>flag;
}
}
void main() //主函數(shù)
{
int i=0,j=0,p;
cout<<"輸入總進程數(shù):"<<endl;
cin>>M;
cout<<"輸入總資源種類:"<<endl;
cin>>N;
cout<<"請輸入總資源數(shù)(all_resource):"<<endl;
for(i=0;i<M;i++)
cin>>ALL_RESOURCE[i];
cout<<"依次輸入各進程所需要的最大資源數(shù)量(max):"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>MAX[i][j];
if (MAX[i][j]>ALL_RESOURCE[j])
cout<<endl<<"占有資源超過了聲明的該資源總數(shù),請重新輸入"<<endl;
}while (MAX[i][j]>ALL_RESOURCE[j]);
}
}
cout<<"依次輸入各進程已經(jīng)占據(jù)的資源數(shù)量(allocation):"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>ALLOCATION[i][j];
if (ALLOCATION[i][j]>MAX[i][j])
cout<<endl<<"占有資源超過了聲明的最大資源,請重新輸入"<<endl;
}while (ALLOCATION[i][j]>MAX[i][j]);
}
}
//初始化資源數(shù)量
for (i=0;i<M;i++)
{ p=ALL_RESOURCE[i];
for (j=0;j<N;j++)
{
p-=ALLOCATION[j][i];//減去已經(jīng)被占據(jù)的資源
AVAILABLE[i]=p;
if(AVAILABLE[i]<0)
AVAILABLE[i]=0;
}
}
for (i=0;i<M;i++)
for(j=0;j<N;j++)
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
showdata();
do{
cout<<endl<<"1--隨機分配算法 2--銀行家算法"<<endl;
cout<<endl<<"請選擇算法: ";
cin>>i;
if(i==2) //m=2表賦值,m==2表判斷
bank();
else
randomallocation();
}while(!((i==1)||(i==2)));
}
課程設計目的和意義
此次課程設計的主要內(nèi)容是模擬實現(xiàn)資源分配。同時要求編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并使用適當?shù)乃惴ǎ行У姆乐购捅苊馑梨i的發(fā)生。
具體用銀行家算法實現(xiàn)資源分配。要求如下：
(1) 設計一個3個并發(fā)進程共享3類不同資源的系統(tǒng)，進程可動態(tài)地申請資源和釋放資源，系統(tǒng)按各進程的申請動態(tài)地分配資源。
(2) 設計用銀行家算法和隨機分配算法，實現(xiàn)資源分配的兩個資源分配程序，應具有顯示或打印各進程依次要求申請的資源數(shù)以及依次分配資源的情況。
(3) 確定一組各進程依次申請資源數(shù)的序列，在相同的情況下分別運行上述兩種資源分配程序，觀察運行結果。
銀行家算法是避免死鎖的一種重要方法，本實驗要求用高級語言編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。死鎖的產(chǎn)生，必須同時滿足四個條件，即一個資源每次只能由一個進程占用：第二個為等待條件，即一個進程請求資源不能滿足時，它必須等待，但它仍繼續(xù)保持已得到的所有其他資源：第四個為循環(huán)等待條件，系統(tǒng)中存在若干個循環(huán)等待的進程，即其中每一個進程分別等待它前一個進程所持有的資源。防止死鎖的機構只能確保上述四個條件之一不出現(xiàn)，則系統(tǒng)就不會發(fā)生死鎖。通過這個算法可用解決生活中的實際問題,如銀行貸款等.
通過對這個算法的設計,讓學生能夠對書本知識有更深的理解,在操作和其它方面有更高的提升.
二、方案設計及開發(fā)過程
隨機分配算法:當進程申請資源時，如果系統(tǒng)中現(xiàn)存資源數(shù)能滿足進程的當前資源申請量，就把資源能會產(chǎn)生死鎖。隨機分配算法很容易進入死鎖.
銀行家分配算法，顧名思義是來源于銀行的借貸業(yè)務，一定數(shù)量的本金要應多個客戶的借貸周轉，為了防止銀行加資金無法周轉而倒閉，對每一筆貸款，必須考察其是否能限期歸還。在操作系統(tǒng)中研究資源分配策略時也有類似問題，系統(tǒng)中有限的資源要供多個進程使用，必須保證得到的資源的進程能在有限的時間內(nèi)歸還資源，以供其他進程使用資源。如果資源分配不得到就會發(fā)生進程循環(huán)等待資源，個進程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。
把個進程需要和已占有資源的情況記錄在進程控制中，假定進程控制塊PCB其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當進程在處于等待態(tài)時，表示系統(tǒng)不能滿足該進程當前的資源申請。“資源需求總量”表示進程在整個執(zhí)行過程中總共要申請的資源量。顯然，，每個進程的資源需求總量不能超過系統(tǒng)擁有的資源總數(shù), 銀行算法進行資源分配可以避免死鎖.
2.算法描述
隨機分配算法:
設進程I提出請求Request[N]，則銀行家算法按如下規(guī)則進行判斷
(1) 如果Request[N]<=AVAILABLE，則轉(2)；否則，出錯。
(2) 系統(tǒng)分配資源，修改相關數(shù)據(jù)：
AVAILABLE=AVAILABLE-REQUEST
ALLOCATION=ALLOCATION+REQUEST
NEED=NEED-REQUES
(3) 系統(tǒng)執(zhí)行安全性檢查
銀行家算法:
設進程I提出請求Request[N]，則銀行家算法按如下規(guī)則進行判斷。
(1)如果Request[N]<=NEED[I，N]，則轉(2)；否則，出錯。
(2)如果Request[N]<=AVAILABLE，則轉(3)；否則，出錯。
(3)系統(tǒng)試探分配資源，修改相關數(shù)據(jù)：
AVAILABLE=AVAILABLE-REQUEST
ALLOCATION=ALLOCATION+REQUEST
NEED=NEED-REQUEST
(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復原狀，進程等待。
3．安全性檢查
(1)設置兩個工作向量WORK=AVAILABLE；FINISH[M]=FALSE
(2)從進程集合中找到一個滿足下述條件的進程，
FINISH[i]=FALSE
NEED<=WORK
如找到，執(zhí)行(3)；否則，執(zhí)行(4)
(3)設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。
WORK=WORK+ALLOCATION
FINISH=TRUE
GO TO 2
(4)如所有的進程Finish[M]=true，則表示安全；否則系統(tǒng)不安全。
3.數(shù)據(jù)結構
假設有M個進程N類資源，則有如下數(shù)據(jù)結構:
#define W 10
#define R 20
int M ; //總進程數(shù)
int N ; //資源種類
int ALL_RESOURCE[W]; //各種資源的數(shù)目總和
int MAX[W][R]; //M個進程對N類資源最大資源需求量
int AVAILABLE[R]; //系統(tǒng)可用資源數(shù)
int ALLOCATION[W][R]; //M個進程已經(jīng)得到N類資源的資源量
int NEED[W][R]; //M個進程還需要N類資源的資源量
int Request[R]; //請求資源個數(shù)
4.主要函數(shù)說明
void showdata(); //主要用來輸出資源分配情況
void changdata(int); //主要用來輸出資源分配后后的情況
void rstordata(int); //用來恢復資源分配情況,如:銀行家算法時,由于分配不安全
則要恢復資源分配情況
int chkerr(int); //銀行家分配算法的安全檢查
int chkerr2(int) ; //隨機分配算法安全檢查
void bank() ; //銀行家算法
void randomallocation(); //隨機分配算法
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -