《操作系統(tǒng),銀行家算法》課程設(shè)計(jì)報(bào)告

1、操作系統(tǒng),銀行家算法課程設(shè)計(jì)報(bào)告 操作系統(tǒng)-銀行家算法 課程設(shè)計(jì)報(bào)告 姓 名： 學(xué) 號： 班 級：計(jì)科班 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) xx大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院 目 錄 1 課程設(shè)計(jì)目的 1 2 課程設(shè)計(jì)的要求 1 3 課程設(shè)計(jì)題目描述 2 4 課程設(shè)計(jì)之銀行家算法原理 2 5 源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn) 4 6 課程設(shè)計(jì)總結(jié) 25 一、課程設(shè)計(jì)的目的 操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的核心系統(tǒng)軟件，它負(fù)責(zé)控制和管理整個(gè)系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些資源，使計(jì)算機(jī)高效的工作。操作系統(tǒng)課程設(shè)計(jì)是操作系統(tǒng)理論課的必要補(bǔ)充，是復(fù)習(xí)和檢驗(yàn)所學(xué)課程的重要手段，本課程設(shè)計(jì)的目的是綜合應(yīng)用學(xué)生所學(xué)知識，通過實(shí)驗(yàn)環(huán)節(jié)，

2、加深學(xué)生對操作系統(tǒng)根本原理和工作過程的理解，提高學(xué)生獨(dú)立分析問題、解決問題的能力，增強(qiáng)學(xué)生的動(dòng)手能力。 二、課程設(shè)計(jì)的要求 1分析設(shè)計(jì)內(nèi)容，給出解決方案（要說明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。 2畫出程序的根本結(jié)構(gòu)框圖和流程圖。 3對程序的每一局部要有詳細(xì)的設(shè)計(jì)分析說明。 4源代碼格式要標(biāo)準(zhǔn)。 5設(shè)計(jì)適宜的測試用例，對得到的運(yùn)行結(jié)果要有分析。 6設(shè)計(jì)中遇到的問題，設(shè)計(jì)的心得體會(huì)。 7按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計(jì)報(bào)告。 三、課程設(shè)計(jì)題目描述 銀行家算法是一種最有代表性的防止死鎖的算法。 要解釋銀行家算法，必須先解釋操作系統(tǒng)平安狀態(tài)和不平安狀態(tài)。 平安狀態(tài)：如果存在一個(gè)由系統(tǒng)中所

3、有進(jìn)程構(gòu)成的平安序列p1，pn，那么系統(tǒng)處于平安狀態(tài)。平安狀態(tài)一定是沒有死鎖發(fā)生。 不平安狀態(tài):不存在一個(gè)平安序列。不平安狀態(tài)不一定導(dǎo)致死鎖。 那么什么是平安序列呢？ 平安序列：一個(gè)進(jìn)程序列p1，pn是平安的，如果對于每一個(gè)進(jìn)程pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程pj (j < i )當(dāng)前占有資源量之和。 銀行家算法： 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)那么為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時(shí)，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的

4、資源可以滿足它的最大需求量那么按當(dāng)前的申請量分配資源，否那么就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。假設(shè)超過那么拒絕分配資源，假設(shè)沒有超過那么再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，假設(shè)能滿足那么按當(dāng)前的申請量分配資源，否那么也要推遲分配。 四、 課程設(shè)計(jì)之銀行家算法原理 1銀行家算法的思路 先對用戶提出的請求進(jìn)行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。假設(shè)請求合法，那么進(jìn)行試分配。最后對試分配后的狀態(tài)調(diào)用平安性檢查算法進(jìn)行平安性檢查。假設(shè)平安，那么分配，否那么，不分配，恢復(fù)原

5、來狀態(tài)，拒絕申請。 2銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu) 可利用資源向量 int availablej j為資源的種類。 最大需求矩陣 int maxij i為進(jìn)程的數(shù)量。 分配矩陣 int allocationij 需求矩陣 int needij= maxij- allocationij 申請各類資源數(shù)量 int request ij i進(jìn)程申請j資源的數(shù)量 工作向量 int workx int finishy 3銀行家算法bank() 進(jìn)程i發(fā)出請求申請k個(gè)j資源，request ij=k (1)檢查申請量是否不大于需求量：request ij<=needi,j,假設(shè)條件不符重新輸入，不

6、允許申請大于需求量。 (2)檢查申請量是否小于系統(tǒng)中的可利用資源數(shù)量：request ij<=availablei,j，假設(shè)條件不符就申請失敗，阻塞該進(jìn)程，用goto語句跳轉(zhuǎn)到重新申請資源。 (3)假設(shè)以上兩個(gè)條件都滿足，那么系統(tǒng)試探著將資源分配給申請的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： availablei,j= availablei,j- request ij；allocationij= allocationij+ request ij；needij= needij- request ij；(4)試分配后，執(zhí)行平安性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于平安狀態(tài)。假

7、設(shè)平安，才正式將資源分配給進(jìn)程；否那么本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。 (5)用dowhile 循環(huán)語句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請。 4平安性檢查算法（safe()函數(shù)） (1)設(shè)置兩個(gè)向量：工作向量work，它表示系統(tǒng)可提供應(yīng)進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行平安性算法開始時(shí)，work= available。 finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做finishi=0； 當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令finishi=1。 (2)在進(jìn)程中查找符合以下條件的進(jìn)程： 條件1：finishi=0；條件2：needij&

8、lt;=workj 假設(shè)找到，那么執(zhí)行步驟(3)否那么，執(zhí)行步驟(4) (3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：workj= workj+ allocationij；finishi=1；goto step 2； (4)如果所有的finishi=1都滿足，那么表示系統(tǒng)處于平安狀態(tài)，否那么，處于不平安狀態(tài)。 五、源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn) 1程序結(jié)構(gòu) 程序共有以下五個(gè)局部： (1) .初始化chushihua()：用于程序開始進(jìn)行初始化輸入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對各類資源最大需求數(shù)等。 (2).當(dāng)前平安

9、性檢查safe()：用于判斷當(dāng)前狀態(tài)平安性，根據(jù)不同地方的調(diào)用提示處理不同。 (3).銀行家算法bank()：進(jìn)行銀行家算法模擬實(shí)現(xiàn)的模塊，調(diào)用其他各個(gè)模塊進(jìn)行銀行家算法模擬過程。 (4).顯示當(dāng)前狀態(tài)show()：顯示當(dāng)前資源分配詳細(xì)情況，包括：各種資源的總數(shù)量(all)、系統(tǒng)目前各種資源可用的數(shù)量、各進(jìn)程已經(jīng)得到的資源數(shù)量、各進(jìn)程還需要的資源量。 (5).主程序main() 逐個(gè)調(diào)用初始化、顯示狀態(tài)、平安性檢查、銀行家算法函數(shù)，使程序有序的進(jìn)行。 2數(shù)據(jù)結(jié)構(gòu) 程序使用的全局變量： const int x=10，y=10； /定義常量 int availablex; /各種資源可利用的數(shù)量

10、int allocationyy; /各進(jìn)程當(dāng)前已分配的資源數(shù)量 int maxyy; /各進(jìn)程對各類資源的最大需求數(shù) int needyy; /還需求矩陣 int requestx; /申請各類資源的數(shù)量 int workx; /工作向量，表系統(tǒng)可提供應(yīng)進(jìn)程運(yùn)行所需各類資源數(shù)量 int finishy; /表系統(tǒng)是否有足夠的資源分配給進(jìn)程，0為否，1為是 int py; /存儲(chǔ)平安序列 int i,j; /全局變量，主要用于循環(huán)語句中 int n,m; /n為進(jìn)程的數(shù)量,m為資源種類數(shù) int l=0,counter=0; 3函數(shù)聲明 void chushihua();/系統(tǒng)初始化函數(shù) vo

11、id safe(); /平安性算法函數(shù) void bank(); /銀行家算法函數(shù) void show (); /輸出當(dāng)前資源分配情況 4主函數(shù)main() int main() cout<< /顯示程序開始提示信息 chushihua(); /初始化函數(shù)調(diào)用 cout<>“<<“進(jìn)程“<<“(“< #include #include using namespace std; #define true 1 /定義 true =1 #define false 0 /定義 flase=0 void bank(vector,vector >

12、,vector >,int ,int ); /聲明bank（應(yīng)行家算法）int safe(vector available,vector > need,vector > allocation,int n,int m);/聲明safe（）平安性算法 void init(); /*主函數(shù)main()*/ void main() init(); int safe(vector available,vector > need,vector > allocation,int n,int m); /*初始化函數(shù)init()*/ void init() int m; /m資源類

13、數(shù) int n; /進(jìn)程數(shù) cout<<“輸入資源類數(shù)“<>m; vector available(m); /動(dòng)態(tài)申請數(shù)組available可用資源向量 cout<<“輸入各類資源總數(shù):“<>availablei; /*/ file *fp; fp=fopen(“available.txt“,“r+“); cout<<“從available.txt文件中讀入數(shù)據(jù)，并輸出“<>n; vector > max(n, vector(m); /*/ /* 下面的被剛掉的為在dos下輸入資源向量*/ /*未被剛掉的是從max.

14、txt文件中讀入數(shù)據(jù)*/ /*/ /* for ( i=0;i>maxij; while (maxij>availablej) cout<>maxij; /*/ fp=fopen(“max.txt“,“r+“); cout<<“從max.txt文件中讀入數(shù)據(jù)，并輸出“< > allocation(n, vector(m); vector > need(n, vector(m); /*/ /* 下面的被剛掉的為在dos下輸入資源向量*/ /*未被剛掉的是從allocation.txt文件中讀入數(shù)據(jù)*/ /*/ /* for ( i=0;i&g

15、t;allocationij; while(allocationij>maxij) cout<>allocationij; needij=maxij-allocationij; availablej =availablej-allocationij; /*/ fp=fopen(“allocation.txt“,“r+“); cout<<“allocation.txt從文件中讀入數(shù)據(jù)，并輸出“< available,vector > need,vector > allocation,int n,int m); cout<<“此狀態(tài)平安!

16、“< available,vector > need,vector > allocation,int n,int m) vector request(m); int all=0; /定義變量all，如果all=0，表示進(jìn)程已經(jīng)運(yùn)行完，如果all>=1，表示還有進(jìn)程沒有運(yùn)行完 for (int i=0;i=1，表示還有進(jìn)程沒有運(yùn)行完 /循環(huán)直至all>0,即找到一個(gè)未運(yùn)行完的進(jìn)程 cout<<“任選一個(gè)進(jìn)程作為當(dāng)前進(jìn)程0-“<>jc; for (int j=0;j>requesti; while(requesti>needjci|

17、requesti>availablei) cout<<“請求向量無法滿足“<>again; if(again=y|again=y) all=0; continue; break; /*平安性算法safe()函數(shù)*/ int safe(vector available,vector > need,vector > allocation,int n,int m) vector work(m),finish(n);/申請工作向量work，finish work=available; vector count(n); /記錄平安序列 int len=-1; /記錄平安序列的進(jìn)程個(gè)數(shù)，如果len=n，即表示所有的finish【i】=true，處于平安狀態(tài) for(int i=0;i“; cout< 本次程序就是按照上面的思路展開的。但是因?yàn)闀r(shí)間上的倉促，本課程設(shè)計(jì)的存在著以下缺乏：一、不能實(shí)現(xiàn)并發(fā)操作，即當(dāng)總資源同時(shí)滿足幾個(gè)進(jìn)程所需要的資源數(shù)時(shí)，這些進(jìn)程不能同時(shí)進(jìn)行，只能一一按進(jìn)程順序執(zhí)行。二、掃描進(jìn)程順序單一，只能按進(jìn)程到來的順序