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

操 作 系 統(tǒng)實(shí)驗(yàn)報告(2)學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院班級：計(jì)091學(xué)號：姓名：時間：2011/12/30目 錄1. 實(shí)驗(yàn)名稱32. 實(shí)驗(yàn)?zāi)康?3. 實(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)康模和ㄟ^自己編程來實(shí)現(xiàn)銀行家算法，進(jìn)一步理解銀行家算法的概念及含義，提高對銀行家算法的認(rèn)識，同時提高自己的動手實(shí)踐能力。各種死鎖防止方法能夠阻止發(fā)生死鎖，但必然會降低系統(tǒng)的并發(fā)性并導(dǎo)致低效的資源利用率。死鎖避免卻與此相反，通過合適的資源分配算法確保不會出現(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個進(jìn)程共享m個系統(tǒng)資源的系統(tǒng)，進(jìn)程可動態(tài)的申請和釋放資源，系統(tǒng)按各進(jìn)程的申請動態(tài)的分配資源。五、實(shí)驗(yàn)原理：系統(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)程集合，若為空則表明本次申請可行，系統(tǒng)處于安全狀態(tài)，可以真正執(zhí)行本次分配，否則，本次資源分配暫不實(shí)施，讓申請資源的進(jìn)程等待。銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會導(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)。安全序列是指一個進(jìn)程序列P1，Pn是安全的，如果對于每一個進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j s.R1) return false;if(R2 s.R2) return false;if(R3 s.R3) return false;return true;class Data/封裝所有數(shù)據(jù)public:Process *p;/進(jìn)程指針Source sum;/總資源量Source available;/可獲得量Source ask;/請求量int pLength;/進(jìn)程個數(shù)int * ruler;/邏輯尺void clearProcess()/進(jìn)程currentAvail清零for(int i=0;ipLength;i+)pi.currentAvail.setSource(0, 0, 0);class DataInit/封裝初始化數(shù)據(jù)函數(shù)類private:public:DataInit()/構(gòu)造函數(shù)void initLength(Data *db)/設(shè)置進(jìn)程個數(shù)int n;coutn;db-pLength = n;db-p = new Processn;if(!db-p)coutruler = new intn;if(!db-ruler)coutpdb-ruleri.currentAvail.add(db-available);/將當(dāng)前系統(tǒng)可用資源量賦給該序列的第一個進(jìn)程if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)/若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回falsereturn false;for(i=1; ipLength; i+)/當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個進(jìn)程的未釋放資源前可獲得資源量currentAvaildb-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.currentAvail);/當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個進(jìn)程的釋放的資源量db-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.allocation);/若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回falseif(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)return false;/若當(dāng)前進(jìn)程currentAvail大于該進(jìn)程總資源量，返回falseif(!db-pdb-ruleri.currentAvail.lower(db-sum)return false;return true;/該序列進(jìn)程安全。返回truebool exsitSafeList(Data *db)/判斷是否存在安全序列int i = 0;for(i = 0; i pLength; i+)/設(shè)置邏輯尺的刻度值db-ruleri = i;while(1) /該循環(huán)將檢測邏輯尺刻度值的全排列 if(checkList(db)/找到一個安全序列，返回truereturn true;db-clearProcess();/將所有進(jìn)程的currentAvail清零if(!next_permutation(db-ruler,db-ruler+db-pLength)/所有排列完畢后退出生成排列庫函數(shù)的調(diào)用return false;return false;int findSafeList(Data *db, int i=0)/尋找安全序列/請求值大于系統(tǒng)當(dāng)前可用資源值，返回0if(!db-ask.lower(db-available)return 0;/請求值大于當(dāng)前進(jìn)程需求資源值，返回1if(!db-ask.lower(db-pi.claim_allocation)return 1;Source s(db-pi.allocation);/根據(jù)請求，分配資源值db-available.sub(db-ask);db-pi.allocation.add(db-ask);db-pi.claim_allocation.sub(db-ask);if(!exsitSafeList(db)/判斷是否存在安全序列db-available.add(db-ask);/不存在安全序列，回滾，恢復(fù)分配前狀態(tài)，并返回2db-pi.allocation.sub(db-ask);db-pi.claim_allocation.add(db-ask);return 2;db-ask.setSource(0,0,0);/找到安全序列，將請求資源置零，返回3return 3;3.功能模塊設(shè)計(jì)class Data/封裝所有數(shù)據(jù)class DataInit/封裝初始化數(shù)據(jù)函數(shù)類class Display/封裝顯示方法class FindSafeList/尋找安全序列struct Process/進(jìn)程屬性構(gòu)成void main() /主函數(shù)8、 實(shí)驗(yàn)運(yùn)行結(jié)果：輸入進(jìn)程數(shù)，及相關(guān)資源數(shù)量分配選擇算法完成的操作：1 查看進(jìn)程情況2 請求分配 2.1分配失敗2.2 分配成功2.3 繼續(xù)分配失敗，退出九、實(shí)驗(yàn)心得：通過此次實(shí)驗(yàn)，我能夠更加深入的理解銀行家算法的執(zhí)行過程，也懂得用銀行家算法去防止發(fā)生死鎖，有效地解決了資源利用率低的問題，保證了系統(tǒng)的安全性。當(dāng)然在實(shí)驗(yàn)過程中，我也遇到了一些困難，但是我通過及時請教同學(xué)，查詢相關(guān)資料，及時解決了問題，但仍有不足之處，我將會在今后學(xué)習(xí)中更加努力。附錄：源代碼（部分）#include#include using namespace std;class Source /資源的基本構(gòu)成以及功能 private:public:int R1;/定義三類類資源int R2;int R3;Source(int r1 = 0,int r2 = 0,int r3 = 0)R1=r1;R2=r2;R3=r3;Source(Source& s)R1=s.R1;R2=s.R2;R3=s.R3;void setSource(int r1 = 0,int r2 = 0,int r3 = 0)/設(shè)置各類資源R1=r1;R2=r2;R3=r3;void add(Source s)/加法R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;void sub(Source s)/減法R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;bool lower(Source s)/比較if(R1 s.R1) return false;if(R2 s.R2) return false;if(R3 s.R3) return false;return true;struct Process/進(jìn)程屬性構(gòu)成Source claim;/進(jìn)程最大需求量Source allocation;/進(jìn)程占有量Source claim_allocation;/進(jìn)程需求量Source currentAvail;/進(jìn)程可獲得量;class Data/封裝所有數(shù)據(jù)public:Process *p;/進(jìn)程指針Source sum;/總資源量Source available;/可獲得量Source ask;/請求量int pLength;/進(jìn)程個數(shù)int * ruler;/邏輯尺void clearProcess()/進(jìn)程currentAvail清零for(int i=0;ipLength;i+)pi.currentAvail.setSource(0, 0, 0);class DataInit/封裝初始化數(shù)據(jù)函數(shù)類private:public:DataInit()/構(gòu)造函數(shù)void initLength(Data *db)/設(shè)置進(jìn)程個數(shù)int n;coutn;db-pLength = n;db-p = new Processn;if(!db-p)coutruler = new intn;if(!db-ruler)coutask.setSource(r1,r2,r3);void initSum(Data *db)/設(shè)置總資源量int r1,r2,r3;coutr1r2r3;db-sum.setSource(r1,r2,r3);void initAvail(Data *db)/設(shè)置可獲得量int r1,r2,r3;cout輸入初始分配 Allocation:n;coutr1r2r3;db-available.setSource(r1,r2,r3);void initProcess(Data *db)/設(shè)置各進(jìn)程屬性值int r1,r2,r3;cout輸入t0時分配 Allocation:n;for(int i=0;ipLength;i+)/設(shè)置進(jìn)程pi 的 allocationcoutpir1r2r3;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_allocationr2=db-pi.claim.R2-db-pi.claim.R2;r3=db-pi.claim.R3-db-pi.claim.R3;db-pi.claim_allocation.setSource(r1, r2, r3);class Display/封裝顯示方法private:public:Display()/構(gòu)造函數(shù)void displaySource(Source s)/設(shè)置基本資源顯示方式couts.R1 s.R2 s.R3;displayAvailable(Source s)/顯示可獲得資源量displaySource(s);void displayProcess(Process *p,int length)/顯示進(jìn)程基本信息for(int i=0; ilength; i+)cout pit;displaySource(pi.claim);couttt;displaySource(pi.allocation);coutendl;coutendl;void displaySafeList(Data *db)/顯示安全序列for(int i=0; ipLength; i+)cout pruleripdb-ruleri.currentAvail);coutpdb-ruleri.claim);coutpdb-ruleri.allocation);coutpdb-ruleri.claim_allocation);cout true;coutendl;void displayAskResult(Data *db,int n)/顯示請求資源結(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(int i=0;ipLength;i+)coutruleri ;coutendl;char c=N;coutc;if(c=Y|c=y)coutpdb-ruleri.currentAvail.add(db-available);/將當(dāng)前系統(tǒng)可用資源量賦給該序列的第一個進(jìn)程if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)/若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回falsereturn false;for(i=1; ipLength; i+)/當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個進(jìn)程的未釋放資源前可獲得資源量currentAvaildb-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.currentAvail);/當(dāng)前進(jìn)程的可獲得資源量currentAvail獲得前一個進(jìn)程的釋放的資源量db-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.allocation);/若當(dāng)前進(jìn)程currentAvail小于該進(jìn)程需求量(claim-allocation)，返回falseif(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail)return false;/若當(dāng)前進(jìn)程currentAvail大于該進(jìn)程總資源量，返回falseif(!db-pdb-ruleri.currentAvail.lower(db-sum)return false;return true;/該序列進(jìn)程安全。返回truebool exsitSafeList(Data *db)/判斷是否存在安全序列int i = 0;for(i = 0; i pLength; i+)/設(shè)置邏輯尺的刻度值db-ruleri = i;while(1) /該循環(huán)將檢測邏輯尺刻度值的全排列 if(checkList(db)/找到一個安全序列，返回truereturn true;db-clearProcess();/將所有進(jìn)程的currentAvail清零if(!next_permutation(db-ruler,db-ruler+db-pLength)/所有排列完畢后退出生成排列庫函數(shù)的調(diào)用return false;return false;int findSafeList(Data *db, int i=0)/尋找安全序列/請求值大于系統(tǒng)當(dāng)前可用資源值，返回0if(!db-ask.lower(db-available)return 0;/請求值大于當(dāng)前進(jìn)程需求資源值，返回1if(!db-ask.lower(db-pi.claim_allocation)return 1;Source s(db-pi.allocation);/根據(jù)請求，分配資源值db-available.sub(db-ask);db