計(jì)算機(jī)操作系統(tǒng) 銀行家算法

1、操作系統(tǒng)課程設(shè)計(jì)題目：銀行家算法的設(shè)計(jì)與實(shí)現(xiàn)系 別： 計(jì)算機(jī)信息與技術(shù)系 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： B130601 姓 名： 伏海龍 學(xué) 號(hào)： B13060105 指導(dǎo)教師 ： 魏少華 ×××2016年01月摘要此次課程設(shè)計(jì)的主要內(nèi)容是模擬實(shí)現(xiàn)資源分配。同時(shí)要求編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并用適當(dāng)?shù)乃惴?，有效的防止和避免死鎖的發(fā)生。銀行家算法是一個(gè)避免死鎖的一種重要方法，通過(guò)高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)簡(jiǎn)單的銀行家算法程序。加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)了解死鎖和避免死鎖的具體實(shí)施方法。死鎖的產(chǎn)生，必須同時(shí)

2、滿足四個(gè)條件，即一個(gè)資源每次只能由一個(gè)進(jìn)程占用；第二個(gè)為等待條件，即一個(gè)進(jìn)程請(qǐng)求資源不能滿足時(shí)，他必須等待，但他仍繼續(xù)保持已得到的所有其他資源；第四個(gè)為循環(huán)等待條件，系統(tǒng)中存在若干個(gè)循環(huán)等待的進(jìn)程，即其中每一個(gè)進(jìn)程分別等待他前一個(gè)進(jìn)程所持有的資源。當(dāng)不滿足以上條件時(shí)就能防止系統(tǒng)的死鎖，讓系統(tǒng)流暢運(yùn)行。通過(guò)該算法可以解決生活中的實(shí)際問(wèn)題，如銀行貸款等。通過(guò)對(duì)該算法的設(shè)計(jì)，讓學(xué)生能夠?qū)镜闹R(shí)有更深刻的理解，在操作和其他方面有大幅度的提高。目錄1. 概述11.1設(shè)計(jì)目的12. 需求分析12.1死鎖概念12.2死鎖的結(jié)論22.3資源分類22.4產(chǎn)生死鎖的必要條件22.5銀行家算發(fā)的意義33. 數(shù)據(jù)

3、結(jié)構(gòu)分析設(shè)計(jì)33.1可利用資源向量矩陣available 33.2最大需求矩陣max 33.3分配矩陣allocation33.4需求矩陣need34. 算法的實(shí)現(xiàn)44.1初始化44.2銀行家算法44.3算法流程圖64.3.1.初始化算法流程圖：64.3.2銀行家算法流程圖：75.測(cè)試與實(shí)例分析86.實(shí)驗(yàn)總結(jié)9參考文獻(xiàn)101. 概述1.1設(shè)計(jì)目的銀行家算法是一種最具代表性的避免死鎖的算法。把笑傲作死同看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次分配資源時(shí)，要測(cè)試進(jìn)程對(duì)資源的最大需

4、求量，如果系統(tǒng)現(xiàn)存的資源可以滿足他的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的子元素與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，反之則在測(cè)試系統(tǒng)現(xiàn)存的資源是否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配本次課程設(shè)計(jì)通過(guò)C語(yǔ)言編寫和調(diào)試實(shí)現(xiàn)銀行家算法的程序，達(dá)到進(jìn)一步掌握銀行家算法，理解系統(tǒng)產(chǎn)生死鎖的原因以及避免死鎖的方法，增強(qiáng)聯(lián)系實(shí)際能力的目的。2. 需求分析2.1死鎖概念死鎖就是指多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程出這中僵持狀態(tài)時(shí)，若無(wú)外力作用，他

5、們就我無(wú)法進(jìn)行運(yùn)作。2.2死鎖的結(jié)論產(chǎn)生死鎖的原因是：競(jìng)爭(zhēng)資源和進(jìn)程推進(jìn)順序不當(dāng)處理死鎖的基本方法是：預(yù)防死鎖，避免死鎖，檢測(cè)死鎖，解除死鎖。2.3資源分類1.可剝奪性資源，某些進(jìn)程在獲得此類資源后，該資源可以被其他進(jìn)程或系統(tǒng)比多。CPU和每寸均屬于可剝奪性資源。2.不可剝奪性資源，當(dāng)系統(tǒng)把類資源分配給進(jìn)程后，不能強(qiáng)行收回，只能在進(jìn)程用完后自動(dòng)釋放，如磁帶機(jī)，打印機(jī)3.非剝奪性資源，在系統(tǒng)中所配置的非剝奪性資源，由于他們的數(shù)量不能滿足諸進(jìn)程的需要，會(huì)使進(jìn)程在運(yùn)行中，因爭(zhēng)奪這些資源而陷入僵局。4.臨時(shí)資源，他是指由一個(gè)進(jìn)程產(chǎn)生，倍另一個(gè)進(jìn)程使用短暫時(shí)間后便無(wú)用的資源，也稱之為消耗性資源。2.4產(chǎn)

6、生死鎖的必要條件1.互斥條件：進(jìn)程對(duì)他所分配的資源進(jìn)行排他性使用，即在一段時(shí)間內(nèi)摸個(gè)資源由一個(gè)進(jìn)程占有。如果此時(shí)還有其他進(jìn)程請(qǐng)求該資源，則請(qǐng)求者只能等待，直至占有該資源的進(jìn)程用畢釋放。2.請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但有對(duì)自己獲得的其他資源保持不放。3.不剝奪條件：進(jìn)程已獲得的資源，在未使用完之前，不能剝奪，只有在使用完由自己釋放。4環(huán)路等待條件：發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程一資源的環(huán)形鏈。2.5銀行家算發(fā)的意義依次對(duì)進(jìn)程測(cè)試，直到每一進(jìn)程能夠運(yùn)行并釋放，從而實(shí)現(xiàn)了避免死鎖的功能。也能提供多種序列可完美實(shí)現(xiàn)要求。

7、3. 數(shù)據(jù)結(jié)構(gòu)分析設(shè)計(jì)3.1可利用資源向量矩陣available 這是一個(gè)含有m個(gè)元素的數(shù)組，其中每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目，起數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果availablej=k，則表示系統(tǒng)中現(xiàn)有R類資源K個(gè)3.2最大需求矩陣max 這是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果maxi,j=K，則表示進(jìn)程i需要R類資源的數(shù)目為K。3.3分配矩陣allocation這也是一個(gè)n*m的矩陣，他/她定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果allocationi，j=K，則表示進(jìn)程i當(dāng)前已分得

8、R類資源的數(shù)目為K。3.4需求矩陣need這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果need i ，j =K，則表示進(jìn)程i 還需要R類資源K個(gè)，才能完成其任務(wù)。上述矩陣存在下述關(guān)系:Needi,j=maxi,j-allocationi,j4. 算法的實(shí)現(xiàn)4.1初始化1.創(chuàng)建available數(shù)組，用以存放系統(tǒng)中可用的資源數(shù)目；2.創(chuàng)建max數(shù)組，用以存放各個(gè)進(jìn)程對(duì)各類資源的最大需求數(shù)目；3.創(chuàng)建allocation數(shù)組，用以存放各個(gè)進(jìn)程已經(jīng)分得的各類資源數(shù)目；4.創(chuàng)建need 數(shù)組，用以存放個(gè)各個(gè)進(jìn)程還需要的各類資源數(shù)目；5.創(chuàng)建allocationl；need;avai

9、lablel，用以存放系統(tǒng)試分配資源前系統(tǒng)資源分配情況；4.2銀行家算法設(shè)Request是請(qǐng)求P的請(qǐng)求向量，Request=K表示進(jìn)程P需要K個(gè)j類資源。P發(fā)出資源請(qǐng)求后，按下列步驟進(jìn)行檢查：1. 如果reques j<=needi,j，轉(zhuǎn)向步驟；否則報(bào)錯(cuò)，所需要的資源數(shù)已超過(guò)它所宣布的最大值；2. 如果requestj<=availablej，轉(zhuǎn)向步驟； 否則報(bào)錯(cuò)，尚無(wú)足夠資源P需等待；3. 嘗試將資源分配給進(jìn)程P，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：acailablej:=availablej-requestj;allocationi,j:=allocationi,j+request;

10、needi,j:=needi,j-requestj;4. 執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)師傅處于安全狀態(tài)。若安全，才正式將資源分配給Pi，已完成本次分配；否則，將本溪試探分配作廢，回復(fù)原來(lái)的資源分配狀態(tài)，讓Pi等待。4.3算法流程圖4.3.1.初始化算法流程圖：計(jì)算各個(gè)進(jìn)程還需的資源數(shù)NEEDij=Maxij Allocationij結(jié)束開(kāi)始輸入進(jìn)程總數(shù)M輸入資源種類個(gè)數(shù)N輸入每個(gè)進(jìn)程最大資源需求數(shù)Max輸入每個(gè)進(jìn)程已分配的資源數(shù)Allocation輸入現(xiàn)在可用資源數(shù)Available4.3.2銀行家算法流程圖：NOYESYESNO開(kāi)始錄入請(qǐng)求資源數(shù)RQUESTi>NEEDi或者REQUESTi>AVAILABLEi報(bào)錯(cuò)，重新輸入AVAILABLEi-=REQUEST i;ALLOCATIONi+=REQUEST i;NEEDi-=REQUESTi;初始化安全性檢查安全AVAILABLEi+=REQUEST i;ALLOCATIONi-=REQUEST i;NEEDi+=REQUESTi;保持原分配進(jìn)程執(zhí)行完釋放資源繼續(xù)分配結(jié)束YESNOYESNO5. 測(cè)試與實(shí)例分析6. 實(shí)驗(yàn)總結(jié)多個(gè)進(jìn)程同時(shí)