操作系統(tǒng)
課程設(shè)計報告
專業(yè)
計算機(jī)科學(xué)與技術(shù)
學(xué)生姓名
班級
學(xué)號
指導(dǎo)教師
完成日期
信息工程學(xué)院
題目：
銀行家算法的模擬實現(xiàn)
一、設(shè)計目的本課程設(shè)計是學(xué)習(xí)完“操作系統(tǒng)原理”課程后進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計，更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動手能力。
二、設(shè)計內(nèi)容
1）概述
用C或C++語言編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。
1.算法介紹：數(shù)據(jù)結(jié)構(gòu)：
1）
可利用資源向量
Available；
2）
最大需求矩陣Max；
3）
分配矩陣Allocation；
4）
需求矩陣Need
2.功能介紹
模擬實現(xiàn)Dijkstra的銀行家算法以避免死鎖的出現(xiàn)，分兩部分組成：
第一部分：銀行家算法（掃描）；
第二部分：安全性算法。
2）設(shè)計原理
一．銀行家算法的基本概念
1、死鎖概念。
在多道程序系統(tǒng)中，雖可借助于多個進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進(jìn)。一組進(jìn)程中，每個進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。
2、關(guān)于死鎖的一些結(jié)論：
?
參與死鎖的進(jìn)程最少是兩個
?
（兩個以上進(jìn)程才會出現(xiàn)死鎖）
?
參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源
?
參與死鎖的所有進(jìn)程都在等待資源
?
參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集
注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。
3、資源分類。
永久性資源：
可以被多個進(jìn)程多次使用（可再用資源）
l
可搶占資源
l
不可搶占資源
臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）
“申請--分配--使用--釋放”模式
4、產(chǎn)生死鎖的四個必要條件：互斥使用（資源獨占）、不可強(qiáng)占（不可剝奪）、請求和保持（部分分配，占有申請）、循環(huán)等待。
1)
互斥使用（資源獨占）
一個資源每次只能給一個進(jìn)程使用。
2)
不可強(qiáng)占（不可剝奪）
資源申請者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放。
3)
請求和保持（部分分配，占有申請）
一個進(jìn)程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態(tài)申請，動態(tài)分配）。
4)
循環(huán)等待
存在一個進(jìn)程等待隊列
{P1,P2,…,Pn},其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個進(jìn)程等待環(huán)路。
5、死鎖預(yù)防:
定義:在系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一。
①破壞“不可剝奪”條件
在允許進(jìn)程動態(tài)申請資源前提下規(guī)定，一個進(jìn)程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請
②破壞“請求和保持”條件。
要求每個進(jìn)程在運(yùn)行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時才給予一次性分配。
③破壞“循環(huán)等待”條件
采用資源有序分配法：
把系統(tǒng)中所有資源編號，進(jìn)程在申請資源時必須嚴(yán)格按資源編號的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。
6．安全狀態(tài)與不安全狀態(tài)
安全狀態(tài)：
如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…Pn，則系統(tǒng)處于安全狀態(tài)。一個進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj
(j
i)當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)
(安全狀態(tài)一定是沒有死鎖發(fā)生的)
不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。
二．銀行家算法
1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)
1）可利用資源向量Available
它是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個。
2）最大需求短陣Max
這是—個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max(i，j)＝K，表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。
3）分配短陣Allocation
這是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每個進(jìn)程的資源數(shù)。如果Allocation(i,j)＝K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。
4）需求矩陣Need
它是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)，如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源k個，方能完成其任務(wù)。
上述三個矩陣間存在下述關(guān)系：
Need[i,j]=Max[i,j]-Allocation[i,j]
2、銀行家算法
設(shè)Requesti是進(jìn)程Pi的請求向量。如果Requesti[j]＝k，表示進(jìn)程只需要k個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：
1）如果
Requesti[j]<=Need[i,j]，則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。
2）如果Requesti[j]<=Available[j]，則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。
3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：
Available[j]:=Available[j]-Requesti[j];
Allocation[i,j]:=Allocation[i,j]+Requesti[j];
Need[i,j]:=Need[i,j]-Requesti[j];
4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。
3、安全性算法
系統(tǒng)所執(zhí)行的安全性算法可描述如下：
1）設(shè)置兩個向量
①、工作向量Work。它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目，它含有m個元素，執(zhí)行安全算法開始時，Work
=
Available。
②、Finish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始時先做Finish[i]:=false
；當(dāng)有足夠資源分配給進(jìn)程時，令
Finish[i]:=true。
2）從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：
①、Finish[i]=false;
②、Need[i,j]<=Work[j];如找到，執(zhí)行步驟（3）；否則，執(zhí)行步驟（4）。
3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：
Work[j]:=Work[i]+Allocation[i,j];
Finish[i]:=true;
goto
step
2；
4）如果所有進(jìn)程的Finish[i]:=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。
三．銀行家算法之例
假定系統(tǒng)中有五個進(jìn)程：{P0，P1，P2，P3，P4}和三種類型的資源{A，B，C}，每一種資源的數(shù)量分別為10、5、7,在T0時刻的資源分配情況如圖1所示。
資源情況
進(jìn)程
Max
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
A
B
C
P0
0
0
(2
0)
P1
0
0
(3
0
2)
(0
0)
P2
0
0
0
0
P3
0
P4
0
0
圖1
T0時刻的資源分配表
(1)T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進(jìn)行分析(如圖2)可知，在T0時刻存在著一個安全序列｛P1，P3，P4，P2，P0｝，故系統(tǒng)是安全的。
資源情況
進(jìn)程
Work
Need
Allocation
Work+Allocation
Finish
A
B
C
A
B
C
A
B
C
A
B
C
P1
0
0
true
true
true
true
true
P3
0
P4
0
0
P2
0
0
0
P0
0
0
圖2
T0時刻的安全序列
(2)P1請求資源：P1發(fā)出請求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查：
①Request1(1,0,2)<=Need1(1,2,2)
②Request1(1,0,2)<=Available1(3,3,2)
③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成資源變化情況如圖1中的圓括號所示。
④再利用安全性算法檢查此時系統(tǒng)是否安全。如圖3所示。
資源情況
進(jìn)程
Work
Need
Allocation
Work+Allocation
Finish
A
B
C
A
B
C
A
B
C
A
B
C
P1
0
0
0
0
true
true
true
true
true
P3
0
P4
0
0
P0
0
0
P2
0
0
0
圖3
P1申請資源時的安全性檢查
由所進(jìn)行的安全性檢查得知，可以找到一個安全序列｛P1,P3,P4,P2,P0｝。因此系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。
(3)P4請求資源：P4發(fā)出請求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查：
①Request4(3,3,0)≤Need4(4,3,1);
②Request4(3,3,0)不小于等于Available(2,3,0),讓P4等待。
(4)P0請求資源：P0發(fā)出請求向量Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查。
①Request0(0,2,0)
≤Need0(7,4,3);
②Request0(0,2,0)
≤Available(2,3,0);
③系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖4所示。
資源情況
進(jìn)程
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
P0
0
0
0
P1
0
0
0
P2
0
0
0
P3
0
P4
0
0
圖4
為P0分配資源后的有關(guān)資源數(shù)據(jù)
(5)進(jìn)行安全性檢查：可用資源Available(2,1,0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。
3）詳細(xì)設(shè)計及編碼
1）銀行家算法流程圖
2）程序源代碼
#include
#include
#include
#include
//定義全局變量
const
int
x=20,y=20;
//常量，便于修改
int
Available[x];
//各資源可利用的數(shù)量
int
Allocation[y][y];
//各進(jìn)程當(dāng)前已分配的資源數(shù)量
int
Max[y][y];
//各進(jìn)程對各類資源的最大需求數(shù)
int
Need[y][y];
//尚需多少資源
int
Request[x];
//申請多少資源
int
Work[x];
//工作向量，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)量
int
Finish[y];
//表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，1為是
int
p[y];
//存儲安全序列
int
i,j;
//i表示進(jìn)程，j表示資源
int
n,m;
//n為進(jìn)程i的數(shù)量,m為資源j種類數(shù)
int
l=0;
//l用來記錄有幾個進(jìn)程是Finish[i]=1的，當(dāng)l=n是說明系統(tǒng)狀態(tài)是安全的int
counter=0;
//函數(shù)聲明
void
chushihua();
//初始化函數(shù)
void
safe();
//安全性算法
void
show();
//函數(shù)show,輸出當(dāng)前狀態(tài)
void
bank();
//銀行家算法
//void
jieshu();
//結(jié)束函數(shù)
void
chushihua()
{
cout<<“輸入進(jìn)程的數(shù)量:
“;//從此開始輸入有關(guān)數(shù)據(jù)
cin>>n;
cout<<“輸入資源種類數(shù):
“;
cin>>m;
cout< 種): “< for (j=0; j j++) { cout<<“輸入資源 “< 可利用的數(shù)量Available[“< “; cin>>Available[j]; //輸入數(shù)字的過程...Work[j]=Available[j]; //初始化Work[j]，它的初始值就是當(dāng)前可用的資源數(shù) } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 輸入進(jìn)程 “< 當(dāng)前已分配的資源 “< 數(shù)量: “; cin>>Allocation[i][j]; } cout< Finish[i]=0;//初始化Finish[i] } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 輸入進(jìn)程 “< 對資源 “< “; cin>>Max[i][j]; if(Max[i][j]>=Allocation[i][j]) //若最大需求大于已分配，則計算需求量 Need[i][j] = Max[i][j]-Allocation[i][j]; else Need[i][j]=0;//Max小于已分配的時候，此類資源已足夠不需再申請 } cout< } cout< } //安全性算法函數(shù) void safe() { l=0; for (i=0; i { //i++ if (Finish[i]==0) { //逐個查找Finish[i]==0的進(jìn)程 條件一 counter=0; //記數(shù)器 for (j=0; j j++) { if (Work[j]>=Need[i][j]) counter=counter+1;//可用大于需求，記數(shù) } if(counter==m) //i進(jìn)程的每類資源都符合Work[j]>=Need[i][j] 條件二 { p[l]=i; //存儲安全序列 Finish[i]=1; //i進(jìn)程標(biāo)志為可分配 for (j=0; j Work[j]=Work[j]+Allocation[i][j]; //釋放資源 l=l+1; //記數(shù),現(xiàn)在有L個進(jìn)程是安全的，當(dāng)L=N時說明滿足安全序列 i= -1; //從第一個進(jìn)程開始繼續(xù)尋找滿足條件一二的進(jìn)程 } } } } //顯示當(dāng)前狀態(tài)函數(shù) void show() //函數(shù)show,輸出當(dāng)前資源分配情況 { int i,j; //局部變量 int All[y]; //各種資源的總數(shù)量 cout<<“當(dāng)前的狀態(tài)為：“< cout<<“各種資源的總數(shù)量:“< for (j=0;j { cout<<“ 資源“< “; All[j]=Available[j]; //總數(shù)量=可用的+已分配的for (i=0;i All[j]+=Allocation[i][j]; cout< “; } cout< for (j=0;j cout<<“ 資源“< “< “; cout< “< for (j=0;j cout<<＇＼t＇<<“資源“< cout< for(i=0;i { cout<<“進(jìn)程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } cout< for (j=0;j cout<<＇＼t＇<<“資源“< cout< for(i=0;i { cout<<“進(jìn)程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } } //銀行家算法函數(shù) void bank() { cout< int k=0; //用于輸入進(jìn)程編號 bool r=false; // 初值為假，輸入Y繼續(xù)申請則置為真 do{//輸入請求 cout<<“輸入申請資源的進(jìn)程(0-“< “; cin>>k; cout< while(k>n-1) //輸入錯誤處理 { cout< cout< “; cin>>k; cout< } cout< “< for (j=0; j j++) { do{ //do……while 循環(huán)判斷申請輸入的情況 cout<<“進(jìn)程 “< 申請資源[“< cin>>Request[j]; cout< if(Request[j]>Need[k][j]) { //申請大于需求量時出錯，提示重新輸入（貸款數(shù)目不允許超過需求數(shù)目） cout<<“申請大于需要量!“< cout<<“申請的資源“< 進(jìn)程“< cout<<“重新輸入!“< } else //先判斷是否申請大于需求量，再判斷是否申請大于可利用量 if(Request[j]>Available[j]) { //申請大于可利用量，應(yīng)該阻塞等待？…… ？？？ cout<<“＼n沒有那么多資源，目前可利用資源“< Finish[k]=0; //該進(jìn)程等待 goto ppp; //goto語句 跳轉(zhuǎn)，結(jié)束本次申請 } }while(Request[j]>Need[k][j]); //Request[j]>Available[j]|| } //改變Avilable、Allocation、Need的值 for (j=0; j 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]; } //判斷當(dāng)前狀態(tài)的安全性 safe(); //調(diào)用安全性算法函數(shù) if (l { l=0; cout<<“＼n試分配后，狀態(tài)不安全,所以不予分配!恢復(fù)原狀態(tài)“< //恢復(fù)數(shù)據(jù) for (j=0; j 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 i++) Finish[i]=0; //進(jìn)程置為未分配狀態(tài) } else { l=0; cout<<“＼n申請資源成功！!“< for(j=0;j { if(Need[k][j]==0); else { //有一種資源還沒全部申請到，則該進(jìn)程不可執(zhí)行，不能釋放擁有的資源 l=1; //置l為1，作為判斷標(biāo)志 break; } } if(l!=1) { //進(jìn)程可以執(zhí)行，則釋放該進(jìn)程的所有資源 for (j=0;j { Available[j]=Available[j]+Allocation[k][j]; Allocation[k][j]=0; } cout<<“該進(jìn)程已得到所有需求資源，執(zhí)行后將釋放其所有擁有資源！“< } l=0; //歸零 cout<<“＼n安全的狀態(tài)!“< cout<<“安全序列為: “; cout< Finish[0]=0; for (i=1; i i++) { cout<<“==>>“<<“進(jìn)程“<<“(“< Finish[i]=0; //所有進(jìn)程置為未分配狀態(tài) } cout< } show(); //顯示當(dāng)前狀態(tài) ppp: //申請大于可利用量，應(yīng)該阻塞等待,結(jié)束本次資源申請，GOTO 語句跳轉(zhuǎn)至此 cout< ?“; char* b=new char; //輸入y/n，判斷是否繼續(xù)申請 < cin>>b; cout< cout<<“-------------------------------------------“< cout< if(*b==＇y＇||*b==＇Y＇) r=true; else //{ r=false; //輸入非 Y 則令 R =false // jieshu(); //調(diào)用結(jié)束函數(shù) //} } while (r==true); } //結(jié)束函數(shù) //void jieshu() //{ // cout< // cout<<“＼t＼t 演示計算完畢“< // cout< //} //主函數(shù) int main() { cout< chushihua(); //初始化函數(shù)調(diào)用 cout< show(); //輸出當(dāng)前狀態(tài) safe(); //判斷當(dāng)前狀態(tài)的安全性 if (l //l在safe中是用來記錄安全的進(jìn)程的個數(shù)的{ cout<<“＼n當(dāng)前狀態(tài)不安全，拒絕申請！“< cout< return 0; } else { int i; //局部變量 l=0; cout< cout<<“進(jìn)程“<<“(“< //輸出安全序列 for (i=1; i i++) cout<<“->>“<<“進(jìn)程“<<“(“< for (i=0; i i++) Finish[i]=0; //所有進(jìn)程置為未分配狀態(tài) cout< } bank(); //調(diào)用銀行家算法函數(shù) cout<<“＼t＼t 演示計算完畢“< return 0; } 4）運(yùn)行結(jié)果分析 1．示例數(shù)據(jù) 進(jìn)程數(shù)量：5 資源種類3 資源情況 進(jìn)程 Max Allocation Need Available A B C A B C A B C A B C P0 0 0 (2 0) P1 0 0 (3 0 2) (0 0) P2 0 0 0 0 P3 0 P4 0 0 2.測試結(jié)果（以上表中數(shù)據(jù)為列） 截圖如下： 5）設(shè)計小結(jié) 這次我做的課題是“銀行家算法的模擬實現(xiàn)”，通過這次的課程設(shè)計，我不僅拓寬了自己的知識面，還在實踐過程中鞏固和加深了自己所學(xué)的理論知識，使自己的技術(shù)素質(zhì)和實踐能力有了進(jìn)一步的提高，同時我的專業(yè)水平也有了很大的進(jìn)步。 同時，在軟件開發(fā)方面也累積了不少經(jīng)驗，對操作系統(tǒng)的知識重要性的認(rèn)識更深了。通過設(shè)計過程的鍛煉，自己分析問題和解決問題的能力都得到了鍛煉和提高，完善了自己的知識結(jié)構(gòu)，加深了對所學(xué)知識的理解。 通過幾天努力，這次課程設(shè)計圓滿的結(jié)束了，在這個過程中，我學(xué)到了很多的知識，在以后的學(xué)習(xí)中，我會更加努力的學(xué)好專業(yè)知識，并將所學(xué)知識用于實踐當(dāng)中去，以便牢固掌握知識。 6）參考文獻(xiàn) [1]計算機(jī)操作系統(tǒng)(第3版)，湯小丹，西安電子科技大學(xué)出版社，2007年7月 [2]Visual C++面向?qū)ο缶幊探坛蹋ǖ诙妫?，王育堅，清華大學(xué)出版社，2007年10月）
點擊咨詢