操作系統(tǒng)-銀行家算法 課程設(shè)計(jì)報(bào)告姓 名： 學(xué) 號(hào)： 班 級(jí)： 計(jì)科班 專 業(yè)：目 錄 1 課程設(shè)計(jì)目的 1 2 課程設(shè)計(jì)的要求 1 3 課程設(shè)計(jì)題目描述 2 4 課程設(shè)計(jì)之銀行家算法原理 2 5 源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn) 4 6 課程設(shè)計(jì)總結(jié) 25 一、課程設(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ú)立分析問(wèn)題、解決問(wèn)題的能力，增強(qiáng)學(xué)生的動(dòng)手能力。二、課程設(shè)計(jì)的要求 1分析設(shè)計(jì)內(nèi)容，給出解決方案（要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。2畫(huà)出程序的基本結(jié)構(gòu)框圖和流程圖。3對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析說(shuō)明。4源代碼格式要規(guī)范。5設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析。6設(shè)計(jì)中遇到的問(wèn)題，設(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)一定是沒(méi)有死鎖發(fā)生。不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？ 安全序列：一個(gè)進(jìn)程序列P1，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1in），它以后尚需要的資源量不超過(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ò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。四、 課程設(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銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu) 可利用資源向量 int Availablej j為資源的種類。最大需求矩陣 int Maxij i為進(jìn)程的數(shù)量。分配矩陣 int Allocationij 需求矩陣 int needij= Maxij- Allocationij 申請(qǐng)各類資源數(shù)量 int Request ij i進(jìn)程申請(qǐng)j資源的數(shù)量 工作向量 int Workx int Finishy 3銀行家算法bank() 進(jìn)程i發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資源，Request ij=k (1)檢查申請(qǐng)量是否不大于需求量：Request ij<=needi,j,若條件不符重新輸入，不允許申請(qǐng)大于需求量。(2)檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資源數(shù)量：Request ij<=availablei,j，若條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，用goto語(yǔ)句跳轉(zhuǎn)到重新申請(qǐng)資源。(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablei,j= Availablei,j- Request ij； Allocationij= Allocationij+ Request ij； needij= needij- Request ij； (4)試分配后，執(zhí)行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓該進(jìn)程等待。(5)用dowhile 循環(huán)語(yǔ)句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。4安全性檢查算法（safe()函數(shù)） (1)設(shè)置兩個(gè)向量： 工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行安全性算法開(kāi)始時(shí)，Work= Available。Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi=0；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令Finishi=1。(2)在進(jìn)程中查找符合以下條件的進(jìn)程： 條件1：Finishi=0； 條件2：needij<=Workj 若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4) (3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj= Workj+ Allocationij； Finishi=1； goto step 2； (4)如果所有的Finishi=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。五、源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn) 1程序結(jié)構(gòu) 程序共有以下五個(gè)部分： (1) .初始化chushihua()：用于程序開(kāi)始進(jìn)行初始化輸入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對(duì)各類資源最大需求數(shù)等。(2).當(dāng)前安全性檢查safe()：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。(3).銀行家算法bank()：進(jìn)行銀行家算法模擬實(shí)現(xiàn)的模塊，調(diào)用其他各個(gè)模塊進(jìn)行銀行家算法模擬過(guò)程。(4).顯示當(dāng)前狀態(tài)show()：顯示當(dāng)前資源分配詳細(xì)情況，包括：各種資源的總數(shù)量(all)、系統(tǒng)目前各種資源可用的數(shù)量、各進(jìn)程已經(jīng)得到的資源數(shù)量、各進(jìn)程還需要的資源量。(5).主程序main() 逐個(gè)調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進(jìn)行。2數(shù)據(jù)結(jié)構(gòu) 程序使用的全局變量： const int x=10，y=10； /定義常量 int Availablex; /各種資源可利用的數(shù)量 int Allocationyy; /各進(jìn)程當(dāng)前已分配的資源數(shù)量 int Maxyy; /各進(jìn)程對(duì)各類資源的最大需求數(shù) int Needyy; /還需求矩陣 int Requestx; /申請(qǐng)各類資源的數(shù)量 int Workx; /工作向量，表系統(tǒng)可提供給進(jìn)程運(yùn)行所需各類資源數(shù)量 int Finishy; /表系統(tǒng)是否有足夠的資源分配給進(jìn)程，0為否，1為是 int py; /存儲(chǔ)安全序列 int i,j; /全局變量，主要用于循環(huán)語(yǔ)句中 int n,m; /n為進(jìn)程的數(shù)量,m為資源種類數(shù) int l=0,counter=0; 3函數(shù)聲明 void chushihua(); /系統(tǒng)初始化函數(shù) void safe(); /安全性算法函數(shù) void bank(); /銀行家算法函數(shù) void show (); /輸出當(dāng)前資源分配情況 4主函數(shù)main() int main() cout<< /顯示程序開(kāi)始提示信息 chushihua(); /初始化函數(shù)調(diào)用 cout<<endl<<endl; showdata(); /輸出初始化后的狀態(tài) /=判斷當(dāng)前狀態(tài)的安全性= safe(); /安全性算法函數(shù)調(diào)用 if (l<n) cout<<“n當(dāng)前狀態(tài)不安全，無(wú)法申請(qǐng),程序退出!“<<endl; cout<<endl; system(“pause“); sign(); /調(diào)用簽名函數(shù) return 0; / break; else int i; /局部變量 l=0; cout<<“n安全的狀態(tài)!“<<endl; cout<<“安全序列為: “; cout<<endl<<“進(jìn)程“<<“(“<<p0<<“)“; /輸出安全序列，考慮顯示格式，先輸出第一個(gè) for (i=1; i<n; i+) cout<<“=>>“<<“進(jìn)程“<<“(“<<pi<<“)“; for (i=0; i<n; i+) Finishi=0; /所有進(jìn)程置為未分配狀態(tài) cout<<endl<<endl; bank(); /銀行家算法函數(shù)調(diào)用 return 0; 5. 操作系統(tǒng)銀行家算法流程圖： 初始化函數(shù)chushihua()開(kāi)始 AVAILABLEi-=REQUESTi; ALLOCATIONi+=REQUESTi; NEEDi-=REQUESTi; 輸入進(jìn)程的數(shù)量 輸入資源種類數(shù) 輸入個(gè)資源當(dāng)前可用資源數(shù) 輸入各進(jìn)程當(dāng)前已分配的資源數(shù) 輸入各進(jìn)程對(duì)各類資源的最大需求 輸出提示：輸入有誤，請(qǐng)重新輸入 初始化函數(shù)chushihua()結(jié)束，銀行家函數(shù) Bank() 提出請(qǐng)求REQUESTi Error; REQUESTi<=NEEDi REQUESTi<=AVAILABLEi Error; Safe(); 輸出提示：你的請(qǐng)求被拒！ AVAILABLEi-=REQUESTi；ALLOCATIONi-=REQUESTi; NEEDi+=REQUESTi； 輸出提示：同意分配請(qǐng)求 是否進(jìn)行再次分配 退出程序，銀行家算法Bank()結(jié)束; 安全性算法Safe()開(kāi)始 Work=AVAILABLE; FINISH=false； NEEDi<=Work&&FINISHi=false; Work+=ALLOCATIONi; FINISHi=ture; 所有進(jìn)程的FINISH=ture； 輸出提示：系統(tǒng)是不安全的 安全，輸出安全序列 Return ture； 安全算法safe()結(jié)束 2. 源程序代碼： #include <iostream.h> #include <vector> #include <iomanip> using namespace std; #define TRUE 1 /定義 TRUE =1 #define FALSE 0 /定義 FLASE=0 void bank(vector<int>,vector<vector<int> >,vector<vector<int> >,int ,int ); /聲明bank（應(yīng)行家算法） int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m);/聲明safe（）安全性算法 void init(); /*主函數(shù)main()*/ void main() init(); int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m); /*初始化函數(shù)init()*/ void init() int m; /m資源類數(shù) int n; /進(jìn)程數(shù) cout<<“輸入資源類數(shù)“<<endl; cin>>m; vector<int> Available(m); /動(dòng)態(tài)申請(qǐng)數(shù)組Available可用資源向量 cout<<“輸入各類資源總數(shù):“<<endl; /*/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Available.txt文件中讀入數(shù)據(jù)*/ /*/ /*/ for (int i=0;i<m;i+) cout<<“輸入R“<<i<<“類資源總數(shù):“; cin>>Availablei; /*/ FILE *fp; fp=fopen(“Available.txt“,“r+“); cout<<“從Available.txt文件中讀入數(shù)據(jù)，并輸出“<<endl; for(int i=0;i<m;i+) fscanf(fp,“%d“,&Availablei); cout<<Availablei<<t; fclose(fp); cout<<“n輸入進(jìn)程數(shù)“<<endl; cin>>n; vector<vector<int> > Max(n, vector<int>(m); /*/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Max.txt文件中讀入數(shù)據(jù)*/ /*/ /* for ( i=0;i<n;i+) cout<<“輸入進(jìn)程“<<i<<“的最大需求向量“; for (int j=0;j<m;j+) cout<<“ 輸入需要R“<<j<<“類資源的最大數(shù)目“; cin>>Maxij; while (Maxij>Availablej) cout<<j<<“類資源最大需求超過(guò)該類資源總量，重新輸入“; cin>>Maxij; /*/ fp=fopen(“Max.txt“,“r+“); cout<<“從Max.txt文件中讀入數(shù)據(jù)，并輸出“<<endl; for(i=0;i<n;i+) for (int j=0;j<m;j+) fscanf(fp,“%d“,&Maxij); cout<<Maxij<<“ “; cout<<endl; fclose(fp); cout<<“輸入已分配的Allocation“<<endl; vector<vector<int> > Allocation(n, vector<int>(m); vector<vector<int> > Need(n, vector<int>(m); /*/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Allocation.txt文件中讀入數(shù)據(jù)*/ /*/ /* for ( i=0;i<n;i+) cout<<“輸入為進(jìn)程“<<i<<“的分配向量“; for (int j=0;j<m;j+) cout<<“ 輸入分配R“<<j<<“類資源的數(shù)目“; cin>>Allocationij; while(Allocationij>Maxij) cout<<j+1<<“類資源最大需求超過(guò)該類需求資源總量，重新輸入“; cin>>Allocationij; Needij=Maxij-Allocationij; Availablej =Availablej-Allocationij; /*/ fp=fopen(“Allocation.txt“,“r+“); cout<<“Allocation.txt從文件中讀入數(shù)據(jù)，并輸出“<<endl; for(i=0;i<n;i+) for (int j=0;j<m;j+) fscanf(fp,“%d“,&Allocationij); Needij=Maxij-Allocationij; /在初始化Max時(shí)，同時(shí)初始化Need數(shù)組 Availablej =Availablej-Allocationij; /在初始化Max時(shí)，同時(shí)修改Available數(shù)組 cout<<Allocationij<< ; cout<<endl; fclose(fp); int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m); cout<<“此狀態(tài)安全!“<<endl; bank(Available,Need,Allocation,n,m);/調(diào)用銀行家算法bank()函數(shù) /*銀行家算法bank()函數(shù)*/ void bank(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m) vector<int> Request(m); int all=0; /定義變量all，如果all=0，表示進(jìn)程已經(jīng)運(yùn)行完，如果all>=1，表示還有進(jìn)程沒(méi)有運(yùn)行完 for (int i=0;i<n;i+) for(int j=0;j<m;j+) all +=Needij; if (0=all) cout<<“所有進(jìn)程已經(jīng)運(yùn)行完，結(jié)束“<<endl; exit(0); int jc;/任選一個(gè)進(jìn)程 char again; all=0;/重新初始化all， while (1) while (all=0) all=0; /如果all=0，表示進(jìn)程已經(jīng)運(yùn)行完，如果all>=1，表示還有進(jìn)程沒(méi)有運(yùn)行完 /循環(huán)直至all>0,即找到一個(gè)未運(yùn)行完的進(jìn)程 cout<<“任選一個(gè)進(jìn)程作為當(dāng)前進(jìn)程0-“<<n-1<<endl; cin>>jc; for (int j=0;j<m;j+) all += Needjcj; if (0=all) cout<<“此進(jìn)程已經(jīng)運(yùn)行，重新輸入“<<endl; cout<<“輸入該進(jìn)程的請(qǐng)求向量“<<endl; for (i=0;i<m;i+) cin>>Requesti; while(Requesti>Needjci|Requesti>Availablei) cout<<“請(qǐng)求向量無(wú)法滿足“<<endl; break; / /系統(tǒng)試探著把資源分配給該進(jìn)程/ for (i=0;i<m;i+) Availablei=Availablei-Requesti; Allocationjci=Allocationjci+Requesti; Needjci=Needjci-Requesti; int bb=0; bb=safe(Available,Need,Allocation,n,m);/調(diào)用安全性算法，判斷此次資源分配后，系統(tǒng)是否處安全狀態(tài) if (1=bb) cout<<“系統(tǒng)成功分配資源“<<endl; else cout<<“系統(tǒng)未能成分配資源,收回預(yù)分配資源“<<endl; for (i=0;i<m;i+) Availablei=Availablei+Requesti; Allocationjci=Allocationjci-Requesti; Needjci=Needjci+Requesti; cout<<“您還想再次請(qǐng)求分配嗎?是請(qǐng)按y/Y,否請(qǐng)按其它鍵“<<endl; cin>>again; if(again=y|again=Y) all=0; continue; break; /*安全性算法safe()函數(shù)*/ int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m) vector<int> Work(m),Finish(n);/申請(qǐng)工作向量work，finish Work=Available; vector<int> count(n); /記錄安全序列 int len=-1; /記錄安全序列的進(jìn)程個(gè)數(shù)，如果len=n，即表示所有的finish【i】=true，處于安全狀態(tài) for(int i=0;i<m;i+)Finishi=FALSE; for (i=0;i<n;i+) int needed=1; for (int j=0;j<m;j+) if(Needij<=Workj) needed=needed*TRUE; else needed=needed*FALSE; if (Finishi=FALSE)&&needed=1) for (j=0;j<m;j+) Workj=Workj+Allocationij; Finishi=TRUE; len=len+1; countlen=i; i=-1; if (len=n-1) cout<<“系統(tǒng)是安全的“<<endl; cout<<“安全序列“<<endl; for (i=0;i<=len;i+) cout<<counti; if (i!=len) cout<<“->“; cout<<endl; return TRUE; else cout<<“系統(tǒng)是不安全的“<<endl; return FALSE; 運(yùn)行結(jié)果： 1. 初始化結(jié)果 2. 檢測(cè)系統(tǒng)資源分配是否安全結(jié)果： 六、課程設(shè)計(jì)的總結(jié) 操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動(dòng)態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。而我本次課程設(shè)計(jì)就是得用銀行家算法來(lái)避免“死鎖”。銀行家算法就是一個(gè)分配資源的過(guò)程，使分配的序列不會(huì)產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時(shí)，每次分配后總存在著一個(gè)進(jìn)程，如果讓它單獨(dú)運(yùn)行下去，必然可以獲得它所需要的全部資源，也就是說(shuō)，它能結(jié)束，而它結(jié)束后可以歸還這類資源以滿足其他申請(qǐng)者的需要。本次程序就是按照上面的思路展開(kāi)的。但是因?yàn)闀r(shí)間上的倉(cāng)促，本課程設(shè)計(jì)的存在著以下不足：一、不能實(shí)現(xiàn)并發(fā)操作，即當(dāng)總資源同時(shí)滿足幾個(gè)進(jìn)程所需要的資源數(shù)時(shí)，這些進(jìn)程不能同時(shí)進(jìn)行，只能一一按進(jìn)程順序執(zhí)行。二、掃描進(jìn)程順序單一，只能按進(jìn)程到來(lái)的順序（即編號(hào)）來(lái)掃描，從而產(chǎn)生的安全順序只能是在這個(gè)順序的基礎(chǔ)上產(chǎn)生的，而其實(shí)安全順序是有多個(gè)的。三、對(duì)進(jìn)程數(shù)和資源數(shù)進(jìn)行的數(shù)量進(jìn)行了限制，都只能最多有十個(gè)。四、運(yùn)行程序后，界面較差，進(jìn)程數(shù)，所需要資源數(shù)，已分配資源數(shù)，能用資源數(shù)，不能一目了然。這次課程設(shè)計(jì)時(shí)間上雖說(shuō)倉(cāng)促點(diǎn)，但是我依然學(xué)到了很多的實(shí)用性知識(shí)。除了更深的了解這個(gè)算法，而且對(duì)C語(yǔ)言進(jìn)行了復(fù)習(xí)，而且其過(guò)程中有很多的知識(shí)點(diǎn)都不記得了，所以在此感謝在此過(guò)程中幫助過(guò)我的老師和同學(xué)。最后的感悟就是：只要你親自動(dòng)手，你就能學(xué)到知識(shí)。再次感謝幫助過(guò)我的老師和同學(xué)！