操作系統(tǒng)課程設(shè)計實驗報告-用C++實現(xiàn)銀行家算法

.../操作系統(tǒng)實驗報告<2>學院：計算機科學與技術(shù)學院班級：計091學號：姓名：時間：2011/12/30目錄實驗名稱……………………3實驗目的……………………3實驗內(nèi)容……………………3實驗要求……………………3實驗原理……………………3實驗環(huán)境……………………4實驗設(shè)計……………………47.1數(shù)據(jù)結(jié)構(gòu)設(shè)計……………………47.2算法設(shè)計…………67.3功能模塊設(shè)計……………………7實驗運行結(jié)果………………8實驗心得……………………9附錄：源代碼〔部分…………………9一、實驗名稱：用C++實現(xiàn)銀行家算法二、實驗目的：通過自己編程來實現(xiàn)銀行家算法,進一步理解銀行家算法的概念及含義,提高對銀行家算法的認識,同時提高自己的動手實踐能力。各種死鎖防止方法能夠阻止發(fā)生死鎖,但必然會降低系統(tǒng)的并發(fā)性并導致低效的資源利用率。死鎖避免卻與此相反,通過合適的資源分配算法確保不會出現(xiàn)進程循環(huán)等待鏈,從而避免死鎖。本實驗旨在了解死鎖產(chǎn)生的條件和原因,并采用銀行家算法有效地防止死鎖的發(fā)生。三、實驗內(nèi)容：利用C++,實現(xiàn)銀行家算法四、實驗要求：1.完成銀行家算法的設(shè)計2.設(shè)計有n個進程共享m個系統(tǒng)資源的系統(tǒng),進程可動態(tài)的申請和釋放資源,系統(tǒng)按各進程的申請動態(tài)的分配資源。五、實驗原理：系統(tǒng)中的所有進程放入進程集合,在安全狀態(tài)下系統(tǒng)收到進程的資源請求后,先把資源試探性的分配給它。之后,系統(tǒng)將剩下的可用資源和進程集合中的其他進程還需要的資源數(shù)作比較,找出剩余資源能夠滿足的最大需求量的進程,從而保證進程運行完畢并歸還全部資源。這時,把這個進程從進程集合中刪除,歸還其所占用的所有資源,系統(tǒng)的剩余資源則更多,反復執(zhí)行上述步驟。最后,檢查進程集合,若為空則表明本次申請可行,系統(tǒng)處于安全狀態(tài),可以真正執(zhí)行本次分配,否則,本次資源分配暫不實施,讓申請資源的進程等待。銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態(tài)地申請資源,但系統(tǒng)在進行資源分配之前,應先計算此次分配資源的安全性,若分配不會導致系統(tǒng)進入不安全狀態(tài),則分配,否則等待。為實現(xiàn)銀行家算法,系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。要解釋銀行家算法,必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個進程序列{P1,…,Pn}是安全的,如果對于每一個進程Pi<1≤i≤n,它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj<j<i>當前占有資源量之和。安全狀態(tài)：如果存在一個由系統(tǒng)中所有進程構(gòu)成的安全序列P1,…,Pn,則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài)：不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。我們可以把操作系統(tǒng)看作是銀行家,操作系統(tǒng)管理的資源相當于銀行家管理的資金,進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。為保證資金的安全,銀行家規(guī)定：<1>當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；<2>顧客可以分期貸款,但貸款的總數(shù)不能超過最大需求量；<3>當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間里得到貸款；<4>當顧客得到所需的全部資金后,一定能在有限的時間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源,當進程首次申請資源時,要測試該進程對資源的最大需求量,如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源,否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時,先測試該進程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源,若能滿足則按當前的申請量分配資源,否則也要推遲分配。六、實驗環(huán)境：Win-7系統(tǒng)VisualC++6.0七、實驗設(shè)計：1.數(shù)據(jù)結(jié)構(gòu)設(shè)計定義結(jié)構(gòu)體：structProcess//進程屬性構(gòu)成{ Sourceclaim; //進程最大需求量 Sourceallocation; //進程占有量 Sourceclaim_allocation;//進程需求量 SourcecurrentAvail;//進程可獲得量};定義類對象：classSource//資源的基本構(gòu)成以及功能{private:public: intR1;//定義三類類資源 intR2; intR3; Source<intr1=0,intr2=0,intr3=0>{ R1=r1;R2=r2;R3=r3; } Source<Source&s> { R1=s.R1;R2=s.R2;R3=s.R3; } voidsetSource<intr1=0,intr2=0,intr3=0>//設(shè)置各類資源 { R1=r1;R2=r2;R3=r3; } voidadd<Sources>//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3; } voidsub<Sources>//減法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3; } boollower<Sources>//比較 { if<R1>s.R1>returnfalse; if<R2>s.R2>returnfalse; if<R3>s.R3>returnfalse; returntrue; }};classData//封裝所有數(shù)據(jù){public: Process*p;//進程指針 Sourcesum;//總資源量 Sourceavailable; //可獲得量 Sourceask;//請求量 intpLength; //進程個數(shù) int*ruler; //邏輯尺 voidclearProcess<> //進程currentAvail清零 { for<inti=0;i<pLength;i++> { p[i].currentAvail.setSource<0,0,0>;} }};classDataInit//封裝初始化數(shù)據(jù)函數(shù)類{private:public: DataInit<>//構(gòu)造函數(shù) { } voidinitLength<Data*db>//設(shè)置進程個數(shù) { intn; cout<<"輸入進程數(shù):"; cin>>n; db->pLength=n; db->p=newProcess[n]; if<!db->p> {cout<<"error!noenoughmemoryspace！";return;} db->ruler=newint[n]; if<!db->ruler> {cout<<"error!noenoughmemoryspace！";return;} }2.算法設(shè)計classFindSafeList//尋找安全序列{private:public: FindSafeList<> //構(gòu)造函數(shù) {} boolcheckList<Data*db> //檢查一個序列安全性 { inti=0; //i用于循環(huán) db->p[db->ruler[i]].currentAvail.add<db->available>; //將當前系統(tǒng)可用資源量賦給該序列的第一個進程 if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> //若當前進程currentAvail小于該進程需求量<claim-allocation>,返回false {returnfalse;} for<i=1;i<db->pLength;i++> { //當前進程的可獲得資源量currentAvail獲得前一個進程的未釋放資源前可獲得資源量currentAvail db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].currentAvail>; //當前進程的可獲得資源量currentAvail獲得前一個進程的釋放的資源量 db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].allocation>; //若當前進程currentAvail小于該進程需求量<claim-allocation>,返回false if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> { returnfalse; } //若當前進程currentAvail大于該進程總資源量,返回false if<!db->p[db->ruler[i]].currentAvail.lower<db->sum>> { returnfalse; } } returntrue; //該序列進程安全。返回true } boolexsitSafeList<Data*db> //判斷是否存在安全序列 { inti=0; for<i=0;i<db->pLength;i++> //設(shè)置邏輯尺的刻度值 { db->ruler[i]=i; } while<1> //該循環(huán)將檢測邏輯尺刻度值的全排列 { if<checkList<db>> //找到一個安全序列,返回true { returntrue; } db->clearProcess<>; //將所有進程的currentAvail清零 if<!next_permutation<db->ruler,db->ruler+db->pLength>> //所有排列完畢后退出生成排列庫函數(shù)的調(diào)用 { returnfalse; } } returnfalse; } intfindSafeList<Data*db,inti=0> //尋找安全序列 { //請求值大于系統(tǒng)當前可用資源值,返回0 if<!db->ask.lower<db->available>> { return0; } //請求值大于當前進程需求資源值,返回1 if<!db->ask.lower<db->p[i].claim_allocation>> { return1; } Sources<db->p[i].allocation>; //根據(jù)請求,分配資源值 db->available.sub<db->ask>; db->p[i].allocation.add<db->ask>; db->p[i].claim_allocation.sub<db->ask>; if<!exsitSafeList<db>> //判斷是否存在安全序列 { db->available.add<db->ask>; //不存在安全序列,回滾,恢復分配前狀態(tài),并返回2 db->p[i].allocation.sub<db->ask>; db->p[i].claim_allocation.add<db->ask>; return2; } db->ask.setSource<0,0,0>; //找到安全序列,將請求資源置零,返回3 return3; } };3.功能模塊設(shè)計classData//封裝所有數(shù)據(jù)classDataInit//封裝初始化數(shù)據(jù)函數(shù)類classDisplay//封裝顯示方法classFindSafeList//尋找安全序列structProcess//進程屬性構(gòu)成voidmain<>//主函數(shù)實驗運行結(jié)果：輸入進程數(shù),及相關(guān)資源數(shù)量分配選擇算法完成的操作：1查看進程情況2請求分配2.1分配失敗2.2分配成功2.3繼續(xù)分配失敗,退出九、實驗心得：通過此次實驗,我能夠更加深入的理解銀行家算法的執(zhí)行過程,也懂得用銀行家算法去防止發(fā)生死鎖,有效地解決了資源利用率低的問題,保證了系統(tǒng)的安全性。當然在實驗過程中,我也遇到了一些困難,但是我通過及時請教同學,查詢相關(guān)資料,及時解決了問題,但仍有不足之處,我將會在今后學習中更加努力。附錄：源代碼〔部分#include<iostream>#include<algorithm>usingnamespacestd;classSource//資源的基本構(gòu)成以及功能{private:public: intR1;//定義三類類資源 intR2; intR3; Source<intr1=0,intr2=0,intr3=0> { R1=r1;R2=r2;R3=r3; } Source<Source&s> { R1=s.R1;R2=s.R2;R3=s.R3; } voidsetSource<intr1=0,intr2=0,intr3=0>//設(shè)置各類資源 { R1=r1;R2=r2;R3=r3; } voidadd<Sources>//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3; } voidsub<Sources>//減法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3; } boollower<Sources>//比較 { if<R1>s.R1>returnfalse; if<R2>s.R2>returnfalse; if<R3>s.R3>returnfalse; returntrue; }};structProcess//進程屬性構(gòu)成{ Sourceclaim; //進程最大需求量 Sourceallocation; //進程占有量 Sourceclaim_allocation;//進程需求量 SourcecurrentAvail;//進程可獲得量};classData//封裝所有數(shù)據(jù){public: Process*p;//進程指針 Sourcesum;//總資源量 Sourceavailable; //可獲得量 Sourceask;//請求量 intpLength; //進程個數(shù) int*ruler; //邏輯尺 voidclearProcess<> //進程currentAvail清零{ for<inti=0;i<pLength;i++> { p[i].currentAvail.setSource<0,0,0>;} }};classDataInit//封裝初始化數(shù)據(jù)函數(shù)類{private:public: DataInit<>//構(gòu)造函數(shù) { } voidinitLength<Data*db>//設(shè)置進程個數(shù) { intn; cout<<"輸入進程數(shù):"; cin>>n; db->pLength=n; db->p=newProcess[n]; if<!db->p> {cout<<"error!noenoughmemoryspace！";return;} db->ruler=newint[n]; if<!db->ruler> {cout<<"error!noenoughmemoryspace！";return;} } voidsetAsk<Data*db> //設(shè)置請求資源量 { intr1,r2,r3; r1=0; r2=0; r3=0; db->ask.setSource<r1,r2,r3>; } voidinitSum<Data*db> //設(shè)置總資源量 { intr1,r2,r3; cout<<"Available<R1,R2,R3>:"; cin>>r1>>r2>>r3; db->sum.setSource<r1,r2,r3>; } voidinitAvail<Data*db> //設(shè)置可獲得量 { intr1,r2,r3; cout<<"輸入初始分配Allocation:\n"; cout<<"available[R1,R2,R3]:\n"; cin>>r1>>r2>>r3; db->available.setSource<r1,r2,r3>; } voidinitProcess<Data*db> //設(shè)置各進程屬性值 { intr1,r2,r3; cout<<"輸入t0時分配Allocation:\n"; for<inti=0;i<db->pLength;i++>//設(shè)置進程p[i]的allocation { cout<<'p'<<i<<"allocation[R1,R2,R3]:"; cin>>r1>>r2>>r3; db->p[i].allocation.setSource<r1,r2,r3>; cout<<'p'<<i<<"maxallocation<claim[R1,R2,R3]>:";//設(shè)置進程p[i]的claim cin>>r1>>r2>>r3; db->p[i].claim.setSource<r1,r2,r3>; r1=db->p[i].claim.R1-db->p[i].claim.R1;//設(shè)置進程p[i]的claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource<r1,r2,r3>; } }};classDisplay//封裝顯示方法{private:public: Display<> //構(gòu)造函數(shù) { } voiddisplaySource<Sources> //設(shè)置基本資源顯示方式 {cout<<s.R1<<""<<s.R2<<""<<s.R3;} displayAvailable<Sources> //顯示可獲得資源量 {displaySource<s>;} voiddisplayProcess<Process*p,intlength> //顯示進程基本信息 {for<inti=0;i<length;i++>{ cout<<"p"<<i<<"\t"; displaySource<p[i].claim>;cout<<"\t\t"; displaySource<p[i].allocation>; cout<<endl; } cout<<endl; } voiddisplaySafeList<Data*db> //顯示安全序列 { for<inti=0;i<db->pLength;i++> { cout<<"p"<<db->ruler[i]<<"";displaySource<db->p[db->ruler[i]].currentAvail>; cout<<""; displaySource<db->p[db->ruler[i]].claim>; cout<<""; displaySource<db->p[db->ruler[i]].allocation>; cout<<""; displaySource<db->p[db->ruler[i]].claim_allocation>; cout<<"true"; cout<<endl; } } voiddisplayAskResult<Data*db,intn> //顯示請求資源結(jié)果 { if<n==0> {cout<<"不分配,請求量大于當前可獲得量!\n";return;} if<n==1> {cout<<"不分配,請求量大于當前可獲得量!\n";return;} if<n==2> {cout<<"不分配,找不到安全序列!\n";return;} if<n==3> { cout<<"存在安全序列:";for<inti=0;i<db->pLength;i++> {cout<<db->ruler[i]<<"";} cout<<endl; charc='N'; cout<<"查看安全序列詳情?<Y/N>"; cin>>c; if<c=='Y'||c=='y'> { cout<<"進程currentavailclaimallocationclaim-allocationpossible\n"; displaySafeList<db>; } return; } }};classFindSafeList//尋找安全序列{private:public: FindSafeList<> //構(gòu)造函數(shù) {} boolcheckList<Data*db> //檢查一個序列安全性 { inti=0; //i用于循環(huán) db->p[db->ruler[i]].currentAvail.add<db->available>; //將當前系統(tǒng)可用資源量賦給該序列的第一個進程 if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> //若當前進程currentAvail小于該進程需求量<claim-allocation>,返回false {returnfalse;} for<i=1;i<db->pLength;i++> { //當前進程的可獲得資源量currentAvail獲得前一個進程的未釋放資源前可獲得資源量currentAvaildb->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].currentAvail>; //當前進程的可獲得資源量currentAvail獲得前一個進程的釋放的資源量 db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].allocation>; //若當前進程currentAvail小于該進程需求量<claim-allocation>,返回false if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> { returnfalse; } //若當前進程currentAvail大于該進程總資源量,返回false if<!db->p[db->ruler[i]].currentAvail.lower<db->sum>> { returnfalse; } } returntrue; //該序列進程安全。返回true } boolexsitSafeList<Data*db> //判斷是否存在安全序列 { inti=0; for<i=0;i<db->pLength;i++> //設(shè)置邏輯尺的刻度值 { db->ruler[i]=i; } while<1> //該循環(huán)將檢測邏輯尺刻度值的全排列 { if<checkList<db>> //找到一個安全序列,返回true { returntrue; } db->clearProcess<>; //將所有進程的currentAvail清零 if<!next_permutation<db->ruler,db->ruler+db->pLength>> //所有排列完畢后退出生成排列庫函數(shù)的調(diào)用 { returnfalse; } } returnfalse; } intfindSafeList<Data*db,inti=0> //尋找安全序列 { //請求值大于系統(tǒng)當前可用資源值,返回0 if<!db->ask.lower<db->available>> { return0; } //請求值大于當前進程需求資源值,返回1 if<!db->ask.lower<db->p[i].claim_allocation>> { return1; } Sources<db->p[i].allocation>; //根據(jù)請求,分配資源值 db->available.sub<db->ask>; db->p[i].allocation.add<db->ask>; db->p[i].claim_allocation.sub<db->ask>; if<!exsitSafeList<db>> //判斷是否存在安全序列 { db->available.add<db->ask>; //不存在安全序列,回滾,恢復分配前狀態(tài),并返回2 db->p[i].allocation.sub<db->ask>; db->p[i].claim_allocation.add<db->ask>; return2; } db->ask.setSource<0,0,0>; //找到安全序列,將請求資源置零