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

1、 操作系統(tǒng)課程設(shè)計(jì) 1、概述一、設(shè)計(jì)目的1、了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。 2、掌握死鎖的產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基本方法。 3、掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。 4、掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。 5、理解死鎖避免在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因二、開(kāi)發(fā)環(huán)境操作系統(tǒng)編譯環(huán)境生成文件windows vista vc+6.0bank for windows.exe源文件：bank.c2、需求分析避免多道程序系統(tǒng)中程序的死鎖。一、死鎖概念：在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來(lái)改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量

2、，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖(deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局(deadly_embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。二、關(guān)于死鎖的一些結(jié)論： 參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖） 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集 注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。 三、資源分類：

3、 永久性資源： 可以被多個(gè)進(jìn)程多次使用（可再用資源） l 可搶占資源 l 不可搶占資源 臨時(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占有的資源

4、，p2等待p3占有的資源，pn等待p1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路 5、 死鎖的解決方案 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ù)防: 定義:在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死

5、鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一 破壞“不可剝奪”條件 在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請(qǐng) 破壞“請(qǐng)求和保持”條件 要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分配 破壞“循環(huán)等待”條件 采用資源有序分配法： 把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。6安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)： 如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列p1，pn，則系統(tǒng)處于安全狀態(tài)。一個(gè)進(jìn)程序列p1，p

6、n是安全的，如果對(duì)于每一個(gè)進(jìn)程pi(1in），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程pj (j i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài) (安全狀態(tài)一定是沒(méi)有死鎖發(fā)生的) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。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類資

7、源的最大需求。如果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= maxi,j allocationi,j4、算法的實(shí)現(xiàn)一、初始化由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣available、最大需求

8、矩陣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= needcusneedi，則轉(zhuǎn)(2)；否則，出錯(cuò)。(2)如果request cusneed i= available

9、cusneedi，則轉(zhuǎn)(3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： availablei-=requestcusneedi; allocationcusneedi+=requestcusneedi; needcusneedi-=requestcusneedi;(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。三、安全性檢查算法(1)設(shè)置兩個(gè)工作向量work=available;finish(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，finish=false;need=work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進(jìn)程獲得資源，可

10、順利執(zhí)行，直至完成，從而釋放資源。work+=allocation;finish=true;goto 2(4)如所有的進(jìn)程finish= true，則表示安全；否則系統(tǒng)不安全。四、各算法流程圖 初始化算法流程圖：銀行家算法流程圖：安全性算法流程圖：四、源程序清單#define m 50int maxmm, allocationmm,needmm,availablem; /*定義全局變量*/int i, j, n, m, r;main() void check(); void print(); int p,q; int reqm, allocation1mm,need1mm,available1

11、m; printf(輸入進(jìn)程總數(shù):); scanf(%d, &n); /*輸入進(jìn)程總數(shù)*/ printf(輸入資源種類總數(shù):); scanf(%d, &m); /*輸入資源種類總數(shù)*/ printf(輸入最大矩陣:); for(i=0;in; i+) for(j=0;jm; j+) scanf(%2d,&maxij); /*輸入最大矩陣*/ printf(輸入已分配資源數(shù) :); for(i=0;in; i+) for(j=0;jm; j+) scanf(%d, &allocationij); /*輸入已分配資源數(shù)*/ printf(輸出還需要的資源數(shù):); for (i=0;in; i+)

12、for(j=0;jm; j+) needij=maxij-allocationij; printf(%2d,needij); /*輸出還需要的資源數(shù)*/ printf(n輸入可用資源數(shù) :); for (i=0;im; i+) scanf(%d, &availablei); /*輸入可用資源數(shù)*/ check(); /*檢測(cè)已知的狀態(tài)是否安全*/ if (r=1) /*如果已知的狀態(tài)安全則執(zhí)行以下代碼*/ do p=0,q=0; printf(n輸入請(qǐng)求資源的進(jìn)程號(hào): ); scanf(%d, &i); /*輸入請(qǐng)求資源的進(jìn)程號(hào)*/ printf(輸入該進(jìn)程所需的資源數(shù):); for(j=0;

13、jm; j+) scanf(%d,&reqj); /*輸入該進(jìn)程所需的資源數(shù) */ for(j=0;jneedij) p=1; /*判斷請(qǐng)求是否超過(guò)最大資源數(shù)*/ if(p) printf(n請(qǐng)求超過(guò)最大資源數(shù)!); else for(j=0;javailablej) q=1; /*判斷請(qǐng)求是否超過(guò)可用資源數(shù) */ if(q) printf(n請(qǐng)求超過(guò)可用資源數(shù)!); else for(j=0;jm; j+) /*請(qǐng)求滿足條件 */ available1j=availablej; /* 保存原已分配的資源數(shù)，需要的資源數(shù)，和可用的資源數(shù)*/ allocation1ij=allocationij

14、; need1ij=needij; availablej=availablej-reqj; /* 系統(tǒng)嘗試把資源分配給請(qǐng)求的進(jìn)程 */ allocationij=allocationij+reqj; needij=needij-reqj; print(); /*輸出可用資源數(shù)*/ check(); /*進(jìn)行安全檢測(cè)*/ if(r=0) /*分配后狀態(tài)不安全*/ for (j=0;jm; j+) availablej=available1j; /* 還原分配前的已分配的資 源數(shù)，仍需要的資源數(shù)和可用的資源數(shù) */ allocationij=allocation1ij; needij=need1i

15、j; printf( 不安全 返回:n); print(); printf(n是否繼續(xù)進(jìn)行資源分配? y or n ?n); /*判斷是否繼續(xù)進(jìn)行資源分配*/ while (getch()=y); void check() /*檢測(cè)函數(shù) */ int k, f, v=0; int workm,am; char finishm; r=1; for(i=0;in; i+) finishi=f; /*初始化各進(jìn)程均沒(méi)得到足夠資源并完成*/ for(j=0;jm; j+) workj=availablej; /*用workj表示可提供進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù) */ k=n; do for (i=0;i

16、n; i+) if (finishi=f) f=1; for (j=0;jworkj) f=0; if (f=1) /*找到還沒(méi)完成的且需求數(shù)小于可提供進(jìn)程繼續(xù)運(yùn)行的*/ finishi=t; /*資源數(shù)的進(jìn)程*/ av+=i; /*記錄安全序列 */ for (j=0;j0); f=1; for (i=0;in; i+) /*判斷是否所有的進(jìn)程都完成*/ if (finishi=f) f=0; break; if (f=0) /*若有進(jìn)程沒(méi)完成，則為不安全狀態(tài)*/ printf(不安全狀態(tài) . n); r=0; else /* 否則為安全狀態(tài)*/ printf(安全狀態(tài).); printf(

17、 輸出安全序列:); for (i=0;in;i+) printf (%d ,ai); /*輸出安全序列*/ printf(n); for (i=0;in; i+) printf(%2d,i); printf( ); for(j=0;jm; j+) printf(%2d,allocationij); printf( ); for(j=0;jm; j+) printf(%2d,needij); printf(n); void print() /*輸出函數(shù)*/ int processm; printf(可用資源數(shù): n); for(j=0;jm; j+) printf(%2d ,availablej); printf(n); 5、結(jié)束語(yǔ)心得與體會(huì)：銀行家算法能保證系統(tǒng)時(shí)時(shí)刻刻都處于安全狀態(tài)，但它要不斷檢測(cè)每個(gè)進(jìn)程對(duì)各類資源的占用和申請(qǐng)情況，需花費(fèi)較多的時(shí)間。對(duì)于較少實(shí)際編程的我來(lái)說(shuō)，編寫銀行家算法具有較大難度。但是在仔細(xì)研究并且與同學(xué)討論后，得出正確程序。開(kāi)始時(shí)在編寫系統(tǒng)試分配時(shí)有些問(wèn)題，在系統(tǒng)試分配后不安全的情況