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

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