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

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