操作系統(tǒng)課程設(shè)計(jì)報(bào)告

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

指導(dǎo)教師：潘煜學(xué)號(hào)：070603115姓名：張鑫班級(jí)：070603學(xué)期：2009至2010學(xué)年1學(xué)期1、概述一、設(shè)計(jì)目的1.對(duì)死鎖避免中的銀行家算法作進(jìn)一步理解。2.加深理解死鎖的概念。3.加深理解安全序列和安全狀態(tài)的概念。4.通過編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并采用適當(dāng)?shù)乃惴?，有效地防止和避免死鎖地發(fā)生。二、開發(fā)環(huán)境

操作系統(tǒng)Windowsxp編譯環(huán)境VC++6.0生成文件銀行家算法.cpp2、需求分析一、死鎖概念：是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中,因爭奪資源而造成的一種互相等待的現(xiàn)象,若無外力作用,它們都將無法推進(jìn)下去.此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖,這些永遠(yuǎn)在互相等待的進(jìn)程稱為死鎖進(jìn)程.

由于資源占用是互斥的，當(dāng)某個(gè)進(jìn)程提出申請(qǐng)資源后，使得有關(guān)進(jìn)程在無外力協(xié)助下，永遠(yuǎn)分配不到必需的資源而無法繼續(xù)運(yùn)行，這就產(chǎn)生了死鎖。二、關(guān)于死鎖的一些結(jié)論：1.參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）2.參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源3.參與死鎖的所有進(jìn)程都在等待資源4.參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。資源分類：永久性資源：可以被多個(gè)進(jìn)程多次使用（可再用資源）1）

可搶占資源2）

不可搶占資源臨時(shí)性資源：只可使用一次的資源；如信號(hào)量,中斷信號(hào)，同步信號(hào)等（可消耗性資源）“申請(qǐng)--分配--使用--釋放”模式產(chǎn)生死鎖的四個(gè)必要條件：1、互斥使用（資源獨(dú)占）

一個(gè)資源每次只能給一個(gè)進(jìn)程使用2、不可強(qiáng)占（不可剝奪）

資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放3、請(qǐng)求和保持（部分分配，占有申請(qǐng)）一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占有（只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配）4、循環(huán)等待存在一個(gè)進(jìn)程等待隊(duì)列

{P1,P2,…,Pn},其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路。死鎖的解決方案5.1產(chǎn)生死鎖的例子申請(qǐng)不同類型資源產(chǎn)生死鎖P1：…申請(qǐng)打印機(jī)申請(qǐng)掃描儀使用釋放打印機(jī)釋放掃描儀…P2：…申請(qǐng)掃描儀申請(qǐng)打印機(jī)使用釋放打印機(jī)釋放掃描儀…申請(qǐng)同類資源產(chǎn)生死鎖（如內(nèi)存）設(shè)有資源R，R有m個(gè)分配單位，由n個(gè)進(jìn)程P1,P2,…,Pn（n>m）共享。假設(shè)每個(gè)進(jìn)程對(duì)R的申請(qǐng)和釋放符合下列原則：

*一次只能申請(qǐng)一個(gè)單位

*滿足總申請(qǐng)后才能使用

*使用完后一次性釋放m=2，n=3資源分配不當(dāng)導(dǎo)致死鎖產(chǎn)生5.2死鎖預(yù)防:摒棄“請(qǐng)求和保持”摒棄“不剝奪”條件摒棄“環(huán)路等待”5.3安全狀態(tài)與不安全狀態(tài)：安全狀態(tài):如果操作系統(tǒng)能保證所有的進(jìn)程在有限的時(shí)間內(nèi)得到需要的全部資源，則稱系統(tǒng)處于“安全狀態(tài)”。3、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一、可利用資源向量矩陣AVAILABLE。這是一個(gè)含有M個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果AVAILABLE[j]=K，則表示系統(tǒng)中現(xiàn)有R類資源K個(gè)二、最大需求矩陣MAX。這是一個(gè)N*M的矩陣，用以表示每一個(gè)進(jìn)程對(duì)M類資源的最大需求。如果MAX[i,j]=K，則表示進(jìn)程I需要R類資源的數(shù)目為K。三、分配矩陣ALLOCATION。這也是一個(gè)N*M的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果ALLOCATION[i,j]=K，則表示進(jìn)程i當(dāng)前已分得R類資源的數(shù)目為K。四、需求矩陣NEED。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果NEED[i,j]=K，則表示進(jìn)程i還需要R類資源K個(gè)，才能完成其任務(wù)。

上述矩陣存在下述關(guān)系：NEED[i,j]=MAX[i,j]﹣ALLOCATION[i,j]

4、算法的實(shí)現(xiàn)初始化由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。銀行家算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST[i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果REQUEST[cusneed][i]<=NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。(2)如果REQUEST[cusneed][i]<=AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。三、安全性檢查算法(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH==false;NEED<=Work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的進(jìn)程Finish=true，則表示安全；否則系統(tǒng)不安全。四、各算法流程圖初始化算法流程圖：銀行家算法流程圖：源程序清單#include"iostream.h"intmain(intargc,char*argv[]){ intI,J,i,i1,j,n,sign; intavail[10],max[10][10],alloc[10][10],need[10][10],requ[10][10],work[10],finish[10]; cout<<"請(qǐng)輸入進(jìn)程數(shù)和資源數(shù)，以空格分開:"; cin>>I>>J; for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"請(qǐng)輸入進(jìn)程"<<i<<"對(duì)資源"<<j<<"的最大需求量："; cin>>max[i][j];/*初始化max*/ } } for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"請(qǐng)輸入進(jìn)程"<<i<<"已分配到資源"<<j<<"的數(shù)量："; cin>>alloc[i][j];/*初始化alloc*/ } } for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"請(qǐng)輸入進(jìn)程"<<i<<"還需要資源"<<j<<"的數(shù)量："; cin>>need[i][j];/*初始化need*/ } } for(j=0;j<J;j++) { cout<<"資源"<<j<<"可利用數(shù)量："; cin>>avail[j];/*初始化avail*/ }/*************用安全性算法判斷系統(tǒng)初始化后的當(dāng)前狀態(tài)是否安全START************/ for(j=0;j<J;j++) { work[j]=avail[j]; } for(i=0;i<I;i++) { finish[i]=0;/*設(shè)置兩個(gè)工作向量*/ }A1: for(i=0;i<I;i++) { sign=1;/*sign==1表示need<=work*/ for(j=0;j<J;j++) { if(need[i][j]>work[j]) { sign=0; } } if(finish[i]==0&&sign==1) { for(j=0;j<J;j++) { work[j]=work[j]+alloc[i][j]; } finish[i]=1;/*設(shè)置finish向量*/ cout<<"P"<<i<<endl;/*輸出安全序列*/ gotoA1; } } sign=1;/*判斷系統(tǒng)狀態(tài)是否安全*/ for(i=0;i<I;i++) { if(finish[i]==0) sign=0; } if(sign==0) { cout<<"當(dāng)前系統(tǒng)處于不安全狀態(tài)."<<endl; } else { cout<<"當(dāng)前系統(tǒng)處于安全狀態(tài)，可以接受資源請(qǐng)求."<<endl; }/*************用安全性算法判斷系統(tǒng)初始化后的當(dāng)前狀態(tài)是否安全END************//***********************設(shè)置請(qǐng)求向量START***********************/S: cout<<"請(qǐng)輸入請(qǐng)求資源的進(jìn)程的進(jìn)程號(hào)："; cin>>i;i1=i; for(j=0;j<J;j++) { cout<<"請(qǐng)輸入進(jìn)程"<<i<<"請(qǐng)求的資源"<<j<<"的數(shù)量："; cin>>requ[i][j]; /*進(jìn)程請(qǐng)求資源*/ } for(j=0;j<J;j++) { if(requ[i][j]>need[i][j]) { cout<<"錯(cuò)誤！請(qǐng)求數(shù)超過需要數(shù)！"<<endl; gotoS; } } for(j=0;j<J;j++) { if(requ[i][j]>avail[j]) { cout<<"可利用資源不足，無法分配。"<<endl; gotoS; } }/***********************設(shè)置請(qǐng)求向量END***********************/ for(j=0;j<J;j++) { avail[j]=avail[j]-requ[i][j];/*系統(tǒng)嘗試分配資源*/ alloc[i][j]=alloc[i][j]+requ[i][j]; need[i][j]=need[i][j]-requ[i][j]; }/*************************安全性算法START****************************/ for(j=0;j<J;j++) { work[j]=avail[j]; } for(i=0;i<I;i++) { finish[i]=0;/*設(shè)置兩個(gè)工作向量*/ }A2: for(i=0;i<I;i++) { sign=1;/*sign==1表示need<=work*/ for(j=0;j<J;j++) { if(need[i][j]>work[j]) { sign=0; } } if(finish[i]==0&&sign==1) { for(j=0;j<J;j++) { work[j]=work[j]+alloc[i][j]; } finish[i]=1;/*設(shè)置finish向量*/ cout<<"P"<<i<<endl;/*輸出安全序列*/ gotoA2; } } sign=1; for(i=0;i<I;i++) { if(finish[i]==0) sign=0;/*判斷系統(tǒng)狀態(tài)是否安全*/ } if(sign==0) { cout<<"不安全，系統(tǒng)已收回嘗試分配的資源！"<<endl;/*若不安全，不予分配，并將數(shù)據(jù)修改回原來的值*/ for(j=0;j<J;j++) { avail[j]=avail[j]+requ[i1][j]; alloc[i1][j]=alloc[i1][j]-requ[i1][j]; need[i1][j]=need[i1][j]+requ[i1][j]; } gotoS; } else { cout<<"安全，可以分配."<<endl;/*若安全，則可以分配*/ gotoS; }/*************************安全性算法END****************************/ return0;}5、結(jié)束語心得與體會(huì)：銀行家算法是避免死鎖的一種重要方法，通過編寫一個(gè)簡單的銀行家算法程序，加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。銀行家算法是為了使系統(tǒng)保持安全狀態(tài)。我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。死鎖的產(chǎn)生，必須同時(shí)滿足四個(gè)條件，即一個(gè)資源每次只能由一個(gè)進(jìn)程占有；第二個(gè)為等待條件，即一個(gè)進(jìn)程請(qǐng)求資源不能滿足時(shí)，它必須等待，單它仍繼續(xù)寶石已得到的所有其他資源；第三個(gè)為非剝奪條件，即在出現(xiàn)死鎖的系統(tǒng)中一定有不可剝奪使用的資源；第四個(gè)為循環(huán)等待條件，系統(tǒng)中存在若干個(gè)循環(huán)等待的進(jìn)程，即其中每一個(gè)進(jìn)程分別等待它前一個(gè)進(jìn)程所持有的資源。防止死鎖的機(jī)構(gòu)只能確保上述四個(gè)條件之一不出現(xiàn)，則系統(tǒng)就不會(huì)發(fā)生死鎖。通過這個(gè)算法可以用來解決生活中的實(shí)際問題，如銀行貸款等。銀行家算法能保證系統(tǒng)時(shí)時(shí)刻刻都處于安全狀態(tài)，但它要不斷檢測每個(gè)進(jìn)程對(duì)各類資源的占用和申請(qǐng)情況，需花費(fèi)較多的時(shí)間。經(jīng)過這次設(shè)計(jì)，讓我基明白了銀行家算法的基本原理，加深了對(duì)課堂上知識(shí)的理解，也懂得了如何讓銀行家算法實(shí)現(xiàn)。實(shí)例：（1）下列狀態(tài)是否安全？(三個(gè)進(jìn)程共享12個(gè)同類資源)進(jìn)程

已分配資源數(shù)

最大需求數(shù)1

1

4

(狀態(tài)a)2

4

43

5

8

1

1

4

(狀態(tài)b)2

4

63