操作系統(tǒng)課程設計實驗報告-用C++實現銀行家算法.doc

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