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

1、操作系統(tǒng)報(bào)告告(2)學(xué)院： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院班級(jí)：計(jì) 091學(xué)號(hào)：姓名：時(shí)間： 2011/12/30目錄1. 實(shí)驗(yàn)名稱 32. 實(shí)驗(yàn)?zāi)康?33. 實(shí)驗(yàn)內(nèi)容 34. 實(shí)驗(yàn)要求 35. 實(shí)驗(yàn)原理 36. 實(shí)驗(yàn)環(huán)境 47. 實(shí)驗(yàn)設(shè)計(jì) 47.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 47.2算法設(shè)計(jì) 67.3功能模塊設(shè)計(jì) 78. 實(shí)驗(yàn)運(yùn)行結(jié)果 89. 實(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)致低效

2、的資源利用率。死鎖避免卻與此相反，通過(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)

3、行完畢并歸還全部資源。這時(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是安

4、全的，如果對(duì)于每一個(gè)進(jìn)程 Pi(1 i n),它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(js.R1)returnfalse;if(R2s.R2)returnfalse;if(R3s.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

5、;ipLength;i+) pi.currentAvail.setSource(0,0,0);classDataInit/ 封裝初始化數(shù)據(jù)函數(shù)類private:public:DataInit()/ 構(gòu)造函數(shù) voidinitLength(Data*db)/ 設(shè)置進(jìn)程個(gè)數(shù)intn;coutn; db-pLength=n; db-p=newProcessn; if(!db-p) coutruler=newintn;if(!db-ruler) coutpdb-ruleri.currentAvail.add(db-available);/將當(dāng)前系統(tǒng)可用資源量賦給該序列的第一個(gè)進(jìn)程if(!db-pdb-

6、ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)/ 若當(dāng)前進(jìn)程 currentAvail 小于該進(jìn)程需求量 (claim-allocation) ，返回 falsereturnfalse; for(i=1;ipLength;i+)currentAvaildb-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.currentAvail);/當(dāng)前進(jìn)程的可獲得資源量 currentAvail 獲得前一個(gè)進(jìn)程的釋放的資源量 db-pdb-ruleri.currentAvail.add(db-pdb-

7、ruleri-1.allocation);/ 若當(dāng)前進(jìn)程 currentAvail 小于該進(jìn)程需求量 (claim-allocation) ，返回 false if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail) returnfalse; / 若當(dāng)前進(jìn)程 currentAvail 大于該進(jìn)程總資源量，返回 false if(!db-pdb-ruleri.currentAvail.lower(db-sum) returnfalse; returntrue; / 該序列進(jìn)程安全。返回 true boolexsitS

8、afeList(Data*db)/判斷是否存在安全序列inti=0; for(i=0;ipLength;i+)/ 設(shè)置邏輯尺的刻度值 db-ruleri=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; intfind

9、SafeList(Data*db,inti=0) /尋找安全序列/請(qǐng)求值大于系統(tǒng)當(dāng)前可用資源值，返回 0 if(!db-ask.lower(db-available) return0; /請(qǐng)求值大于當(dāng)前進(jìn)程需求資源值，返回1if(!db-ask.lower(db-pi.claim_allocation) return1; Sources(db-pi.allocation);/ 根據(jù)請(qǐng)求，分配資源值db-available.sub(db-ask);db-pi.allocation.add(db-ask); db-pi.claim_allocation.sub(db-ask);if(!exsitS

10、afeList(db)/判斷是否存在安全序列db-available.add(db-ask);/不存在安全序列，回滾，恢復(fù)分配前狀態(tài)，并返回2db-pi.allocation.sub(db-ask); db-pi.claim_allocation.add(db-ask);return2;db-ask.setSource(0,0,0);/找到安全序列，將請(qǐng)求資源置零，返回3return3;3. 功能模塊設(shè)計(jì)classData/圭寸裝所有數(shù)據(jù)classDataInit/ 封裝初始化數(shù)據(jù)函數(shù)類classDisplay/ 圭裝顯示方法classFindSafeList/ 尋找安全序列structPro

11、cess/進(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#includeusingnamespacestd;c

12、lassSource/資源的基本構(gòu)成以及功能private:public:in tR1;/定義三類類資源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=

13、R1-s.R1;R2=R2-s.R2;R3=R3-s.R3; boollower(Sources)/ 比較if(R1s.R1)returnfalse;if(R2s.R2)returnfalse;if(R3s.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;

14、/總資源量Sourceavailable;/可獲得量Sourceask;/ 請(qǐng)求量intpLength;/進(jìn)程個(gè)數(shù)int*ruler; /邏輯尺voidclearProcess() /進(jìn)程 currentAvail 清零for(inti=0;ipLength;i+) pi.currentAvail.setSource(0,0,0);classDataInit/ 圭裝初始化數(shù)據(jù)函數(shù)類private:public:DataInit()/ 構(gòu)造函數(shù) voidinitLength(Data*db)/ 設(shè)置進(jìn)程個(gè)數(shù)intn;coutn;db-pLength=n;db-p=newProcessn;if(!

15、db-p)coutruler=newintn;if(!db-ruler)coutask.setSource(r1,r2,r3);voidinitSum(Data*db) / 設(shè)置總資源量intr1,r2,r3;coutr1r2r3;db-sum.setSource(r1,r2,r3);voidinitAvail(Data*db) / 設(shè)置可獲得量intr1,r2,r3;cout 輸入初始分配 Allocation:n; coutr1r2r3; db-available.setSource(r1,r2,r3);voidinitProcess(Data*db) / 設(shè)置各進(jìn)程屬性值intr1,r2

16、,r3; cout 輸入 t0 時(shí)分配 Allocation:n; for(inti=0;ipLength;i+)/ 設(shè)置進(jìn)程 pi 的 allocation coutpir1r2r3;db-pi.allocation.setSource(r1,r2,r3); coutpir1r2r3;db-pi.claim.setSource(r1,r2,r3); r1=db-pi.claim.R1-db-pi.claim.R1;/ 設(shè)置進(jìn)程 pi 的 claim_allocation r2=db-pi.claim.R2-db-pi.claim.R2; r3=db-pi.claim.R3-db-pi.cla

17、im.R3;db-pi.claim_allocation.setSource(r1,r2,r3); ;classDisplay/ 封裝顯示方法private: public:Display() / 構(gòu)造函數(shù) voiddisplaySource(Sources) /設(shè)置基本資源顯示方式 couts.R1s.R2s.R3; displayAvailable(Sources)/顯示可獲得資源量displaySource(s);voiddisplayProcess(Process*p,intlength) / 顯示進(jìn)程基本信息 for(inti=0;ilength;i+) coutpit; displ

18、aySource(pi.claim); couttt;displaySource(pi.allocation); coutendl; coutendl; voiddisplaySafeList(Data*db) /顯示安全序列 for(inti=0;ipLength;i+) coutpruleripdb-ruleri.currentAvail);coutpdb-ruleri.claim);coutpdb-ruleri.allocation);coutpdb-ruleri.claim_allocation); couttrue;coutendl; voiddisplayAskResult(Dat

19、a*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;ipLength;i+) coutruleri; coutendl;charc=N;coutc;if(c=Y|c=y)coutpdb-ruleri.currentAvail.add(db-available);/將當(dāng)前系統(tǒng)可用資源量賦給該序列的第一個(gè)進(jìn)程if(!db-pdb-

20、ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)/ 若當(dāng)前進(jìn)程 currentAvail 小于該進(jìn)程需求量 (claim-allocation) ，返回 falsereturnfalse; for(i=1;ipLength;i+)/當(dāng)前進(jìn)程的可獲得資源量 currentAvail 獲得前一個(gè)進(jìn)程的未釋放資源前可獲得資源量 currentAvaildb-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.currentAvail); /當(dāng)前進(jìn)程的可獲得資源量 currentAvail 獲得前一個(gè)

21、進(jìn)程的釋放的資源量 db-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.allocation);/ 若當(dāng)前進(jìn)程 currentAvail 小于該進(jìn)程需求量 (claim-allocation) ，返回 false if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail) returnfalse; / 若當(dāng)前進(jìn)程 currentAvail 大于該進(jìn)程總資源量，返回 false if(!db-pdb-ruleri.currentAvail.lower(db-sum) retur

22、nfalse; returntrue;/ 該序列進(jìn)程安全。返回 trueboolexsitSafeList(Data*db)/判斷是否存在安全序列inti=0; for(i=0;ipLength;i+)/ 設(shè)置邏輯尺的刻度值 db-ruleri=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)/尋找安全序列if(!db-ask.lower(db-available) return0; /請(qǐng)求值大于當(dāng)前進(jìn)程需求資源值，返回1if(!db-ask.lower(db-pi.claim_allocation) return1; Sources(db-pi.allocation);/ 根據(jù)請(qǐng)求，分配資源值db-available.sub(db-ask);db-pi.alloc