操作系統(tǒng)課程設(shè)計(jì)銀行家算法報(bào)告操作系統(tǒng)銀行家算法實(shí)驗(yàn)報(bào)告

1、第21頁(yè) 共21頁(yè)操作系統(tǒng)課程設(shè)計(jì)銀行家算法報(bào)告操作系統(tǒng)銀行家算法實(shí)驗(yàn)報(bào)告操作系統(tǒng)-銀行家算法 課程設(shè)計(jì)報(bào)告 姓 名： 學(xué) 號(hào)： 班 級(jí)：計(jì)科班 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 指導(dǎo)教師： 時(shí) 間： 2022 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)分析p 及代碼實(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é)

2、課程的重要手段，本課程設(shè)計(jì)的目的是綜合應(yīng)用學(xué)生所學(xué)知識(shí)，通過(guò)實(shí)驗(yàn)環(huán)節(jié)，加深學(xué)生對(duì)操作系統(tǒng)基本原理和工作過(guò)程的理解，提高學(xué)生獨(dú)立分析p 問(wèn)題、解決問(wèn)題的能力，增強(qiáng)學(xué)生的動(dòng)手能力。 二、課程設(shè)計(jì)的要求 1分析p 設(shè)計(jì)內(nèi)容，給出解決方案（要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。 2畫(huà)出程序的基本結(jié)構(gòu)框圖和流程圖。 3對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析p 說(shuō)明。 4代碼格式要規(guī)范。 5設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析p 。 6設(shè)計(jì)中遇到的問(wèn)題，設(shè)計(jì)的心得體會(huì)。 7按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計(jì)報(bào)告。 三、課程設(shè)計(jì)題目描述 銀行家算法是一種最有代表性的避免死鎖的算法。 要解釋銀

3、行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。 安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒(méi)有死鎖發(fā)生。 不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。 那么什么是安全序列呢？ 安全序列：一個(gè)進(jìn)程序列P1，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1in），它以后尚需要的資量不超過(guò)系統(tǒng)當(dāng)前剩余資量與所有進(jìn)程Pj (j i )當(dāng)前占有資量之和。 銀行家算法： 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資，當(dāng)進(jìn)程首次

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

5、恢復(fù)原來(lái)狀態(tài)，拒絕申請(qǐng)。 2銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu) 可利用資向量 int Availablej j為資的種類。 最大需求矩陣 int Maxij i為進(jìn)程的數(shù)量。 分配矩陣 int Allocationij 需求矩陣 int needij= Maxij- Allocationij 申請(qǐng)各類資數(shù)量 int Request ij i進(jìn)程申請(qǐng)j資的數(shù)量 工作向量 int Workx int Finishy 3銀行家算法bank 進(jìn)程i發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資，Request ij=k (1)檢查申請(qǐng)量是否不大于需求量：Request ij=needi,j,若條件不符重新輸入，不允許申請(qǐng)大于需求量

6、。 (2)檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資數(shù)量：Request ij=availablei,j，若條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，用goto語(yǔ)句跳轉(zhuǎn)到重新申請(qǐng)資。 (3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資分配給申請(qǐ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)。若安全，才正式將資分配給進(jìn)程；否則本次試

7、探分配作廢，恢復(fù)原來(lái)的資分配狀態(tài)，讓該進(jìn)程等待。 (5)用dowhile 循環(huán)語(yǔ)句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資申請(qǐng)。 4安全性檢查算法（safe函數(shù)）(1)設(shè)置兩個(gè)向量： 工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資數(shù)目，在執(zhí)行安全性算法開(kāi)始時(shí)，Work= Available。 Finish，它表示系統(tǒng)是否有足夠的資分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi=0；當(dāng)有足夠的資分配給進(jìn)程時(shí)，再令Finishi=1。 (2)在進(jìn)程中查找符合以下條件的進(jìn)程： 條件1：Finishi=0； 條件2：needij=Workj 若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)

8、(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)分析p 及代碼實(shí)現(xiàn) 1程序結(jié)構(gòu) 程序共有以下五個(gè)部分： (1) .初始化chushihua：用于程序開(kāi)始進(jìn)行初始化輸入數(shù)據(jù)：進(jìn)程數(shù)量、資種類、各種資可利用數(shù)量、各進(jìn)程的各種資已分配數(shù)量、各進(jìn)程對(duì)各類資最大需求數(shù)等。 (2).當(dāng)前安全性檢查safe：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。 (3).銀

9、行家算法bank：進(jìn)行銀行家算法模擬實(shí)現(xiàn)的模塊，調(diào)用其他各個(gè)模塊進(jìn)行銀行家算法模擬過(guò)程。 (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ù)量 int Allocationyy; /各進(jìn)程當(dāng)前已分配的資數(shù)量 int Maxyy; /各進(jìn)程對(duì)各類資的最大需求

10、數(shù) int Needyy; /還需求矩陣 int Requestx; /申請(qǐng)各類資的數(shù)量 int Workx; /工作向量，表系統(tǒng)可提供給進(jìn)程運(yùn)行所需各類資數(shù)量 int Finishy; /表系統(tǒng)是否有足夠的資分配給進(jìn)程，0為否，1為是 int py; /存儲(chǔ)安全序列 int i,j; /全局變量，主要用于循環(huán)語(yǔ)句中 int n,m; /n為進(jìn)程的數(shù)量,m為資種類數(shù) int l=0,counter=0; 3函數(shù)聲明 void chushihua; /系統(tǒng)初始化函數(shù) void safe; /安全性算法函數(shù) void bank; /銀行家算法函數(shù) void show ; /輸出當(dāng)前資分配情況 4主

11、函數(shù)main int main cout /顯示程序開(kāi)始提示信息 chushihua; /初始化函數(shù)調(diào)用 coutendlendl; showdata; /輸出初始化后的狀態(tài) /=判斷當(dāng)前狀態(tài)的安全性= safe; /安全性算法函數(shù)調(diào)用 if (ln) cout“n當(dāng)前狀態(tài)不安全，無(wú)法申請(qǐng),程序退出!“endl; coutendl; system(“pause“); sign; /調(diào)用簽名函數(shù) return 0; / break; else int i; /局部變量 l=0; cout“n安全的狀態(tài)!“endl; cout“安全序列為: “; coutendl“進(jìn)程“(“p0“)“; /輸出安

12、全序列，考慮顯示格式，先輸出第一個(gè) for (i=1; in; i+) cout“進(jìn)程“(“pi“)“; for (i=0; in; i+) Finishi=0; /所有進(jìn)程置為未分配狀態(tài) coutendlendl; bank; /銀行家算法函數(shù)調(diào)用 return 0; 5. 操作系統(tǒng)銀行家算法流程圖： 初始化函數(shù)chushihua開(kāi)始 AVAILABLEi-=REQUESTi; ALLOCATIONi+=REQUESTi; NEEDi-=REQUESTi; 輸入進(jìn)程的數(shù)量 輸入資種類數(shù) 輸入個(gè)資當(dāng)前可用資數(shù) 輸入各進(jìn)程當(dāng)前已分配的資數(shù) 輸入各進(jìn)程對(duì)各類資的最大需求 輸出提示：輸入有誤，請(qǐng)重新

13、輸入 初始化函數(shù)chushihua結(jié)束，銀行家函數(shù) Bank 提出請(qǐng)求REQUESTi Error; REQUESTi=NEEDi REQUESTi=AVAILABLEi Error; Safe; 輸出提示：你的請(qǐng)求被拒！ AVAILABLEi-=REQUESTi；ALLOCATIONi-=REQUESTi; NEEDi+=REQUESTi； 輸出提示：同意分配請(qǐng)求 是否進(jìn)行再次分配 退出程序，銀行家算法Bank結(jié)束; 安全性算法Safe開(kāi)始 Work=AVAILABLE; FINISH=false； NEEDi=Work&;&;FINISHi=false; Work+=ALLOCATIONi

14、; FINISHi=ture; 所有進(jìn)程的FINISH=ture； 輸出提示：系統(tǒng)是不安全的 安全，輸出安全序列 Return ture； 安全算法safe結(jié)束 2. 程序代碼： _include _include _include _include /定義全局變量 const int x=10,y=10; /常量，便于修改 int Availablex; /各資可利用的數(shù)量 int Allocationyy; /各進(jìn)程當(dāng)前已分配的資數(shù)量 int Maxyy; /各進(jìn)程對(duì)各類資的最大需求數(shù) int Needyy; /尚需多少資 int Requestx; /申請(qǐng)多少資 int Workx; /

15、工作向量，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資數(shù)量 int Finishy; /表示系統(tǒng)是否有足夠的資分配給進(jìn)程，1為是 int py; /存儲(chǔ)安全序列 int i,j; /i表示進(jìn)程，j表示資 int n,m; /n為進(jìn)程i的數(shù)量,m為資j種類數(shù) int l=0; /l用來(lái)記錄有幾個(gè)進(jìn)程是Finishi=1的，當(dāng)l=n是說(shuō)明系統(tǒng)狀態(tài)是安全的 int counter=0; /函數(shù)聲明 void chushihua; /初始化函數(shù) void safe; /安全性算法 void show; /函數(shù)show,輸出當(dāng)前狀態(tài) void bank; /銀行家算法 void jieshu; /結(jié)束函數(shù)

16、void chushihua coutn; coutm; coutendl“輸入各種資當(dāng)前可用的數(shù)量( “m“ 種): “endl; for (j=0; jm; j+) cout“輸入資 “j“ 可利用的數(shù)量Available“jAvailablej; /輸入數(shù)字的過(guò)程. Workj=Availablej; /初始化Workj，它的初始值就是當(dāng)前可用的資數(shù) coutendl“輸入各進(jìn)程當(dāng)前已分配的資數(shù)量Allocation“n“m“: “endl; for (i=0; in; i+) for (j=0; jm; j+) cout“ 輸入進(jìn)程 “i“ 當(dāng)前已分配的資 “jAllocationij

17、; coutendl; Finishi=0;/初始化Finishi coutendl“輸入各進(jìn)程對(duì)各類資的最大需求Max“n“m“: “endl; for (i=0; in; i+) for (j=0; jm; j+) cout“ 輸入進(jìn)程 “i“ 對(duì)資 “jMaxij; if(Maxij=Allocationij) /若最大需求大于已分配，則計(jì)算需求量 Needij = Maxij-Allocationij; else Needij=0;/Max小于已分配的時(shí)候，此類資已足夠不需再申請(qǐng) coutendl; coutendl“初始化完成“endl; /安全性算法函數(shù) void safe l=0

18、; for (i=0; in;i+) /i+ if (Finishi=0) /逐個(gè)查找Finishi=0的進(jìn)程 條件一 counter=0; /記數(shù)器 for (j=0; j=Needij) counter=counter+1;/可用大于需求，記數(shù) if(counter=m) /i進(jìn)程的每類資都符合Workj=Needij 條件二 pl=i; /存儲(chǔ)安全序列 Finishi=1; /i進(jìn)程標(biāo)志為可分配 for (j=0; jm;j+) Workj=Workj+Allocationij; /釋放資 l=l+1; /記數(shù),現(xiàn)在有L個(gè)進(jìn)程是安全的，當(dāng)L=N時(shí)說(shuō)明滿足安全序列 i= -1; /從第一個(gè)

19、進(jìn)程開(kāi)始繼續(xù)尋找滿足條件一二的進(jìn)程 /顯示當(dāng)前狀態(tài)函數(shù) void show /函數(shù)show,輸出當(dāng)前資分配情況 int i,j; /局部變量 int Ally; /各種資的總數(shù)量 int L1; /局部變量L1 cout“當(dāng)前的狀態(tài)為：“endl; cout“各種資的總數(shù)量:“endl; for (j=0;jm;j+) cout“ 資“j“: “; Allj=Availablej; /總數(shù)量=可用的+已分配的 for (i=0;in;i+) Allj+=Allocationij; coutAllj“ “; coutendl“當(dāng)前各種資可用的量為(available):“endl; for (j

20、=0;jm;j+) cout“ 資“j“: “Availablej“ “; coutendl“各進(jìn)程已經(jīng)得到的資量(allocation): “endl; for(i=0;i=m;i+) for (j=i;jm;j+) cout“ 資“j; coutendl; for(L1=0;L1n;L1+) cout“進(jìn)程“L1“:“; for (j=i;jm;j+) coutAllocationL1j“ “; coutendl; coutendl“各進(jìn)程還需要的資量(need):“endl; for(i=0;i=m;i+) for (j=i;jm;j+) cout“ 資“j; coutendl; for

21、(L1=0;L1n;L1+) cout“進(jìn)程“L1“:“; for (j=i;jm;j+) coutNeedL1j“ “; coutendl; /銀行家算法函數(shù) void bank coutendl“進(jìn)程申請(qǐng)分配資：“endl; int k=0; /用于輸入進(jìn)程編號(hào) bool r=false; / 初值為假，輸入Y繼續(xù)申請(qǐng)則置為真 do/輸入請(qǐng)求 cout“輸入申請(qǐng)資的進(jìn)程(0-“n-1k; coutn-1) /輸入錯(cuò)誤處理 coutendl“輸入錯(cuò)誤，重新輸入：“endl; coutendl“輸入申請(qǐng)資的進(jìn)程(0-“n-1k; coutendl; coutendl“輸入該進(jìn)程申請(qǐng)各類資的數(shù)量

22、: “endl; for (j=0; jm; j+) do /dowhile 循環(huán)判斷申請(qǐng)輸入的情況 cout“進(jìn)程 “k“ 申請(qǐng)資“jRequestj; coutNeedkj) /申請(qǐng)大于需求量時(shí)出錯(cuò)，提示重新輸入（貸款數(shù)目不允許超過(guò)需求數(shù)目）cout“申請(qǐng)大于需要量!“endl; cout“申請(qǐng)的資“j“的數(shù)量為“Requestj“,大于進(jìn)程“k“對(duì)該資需求量“Needkj“。“endl; cout“重新輸入!“Availablej) /申請(qǐng)大于可利用量， 應(yīng)該阻塞等待？ ？ cout“n沒(méi)有那么多資，目前可利用資“j“數(shù)量為“Availablej“,本次申請(qǐng)不成功，進(jìn)程等待!“Needk

23、j); /RequestjAvailablej| /改變Avilable、Allocation、Need的值 for (j=0; jm; j+) Availablej = Availablej-Requestj; Allocationkj = Allocationkj+Requestj; Needkj = Needkj-Requestj; Workj = Availablej; /判斷當(dāng)前狀態(tài)的安全性 safe; /調(diào)用安全性算法函數(shù) if (ln) l=0; cout“n試分配后，狀態(tài)不安全,所以不予分配!恢復(fù)原狀態(tài)“endl; /恢復(fù)數(shù)據(jù) for (j=0; jm; j+) Availab

24、lej = Availablej+Requestj; Allocationkj = Allocationkj-Requestj; Needkj = Needkj+Requestj; Workj = Availablej; for (i=0; in; i+) Finishi=0; /進(jìn)程置為未分配狀態(tài) else l=0; cout“n申請(qǐng)資成功!“endl; for(j=0;jm;j+) if(Needkj=0); else /有一種資還沒(méi)全部申請(qǐng)到，則該進(jìn)程不可執(zhí)行，不能釋放擁有的資 l=1; /置l為1，作為判斷標(biāo)志 break; if(l!=1) /進(jìn)程可以執(zhí)行，則釋放該進(jìn)程的所有資 fo

25、r (j=0;jm;j+) Availablej=Availablej+Allocationkj; Allocationkj=0; cout“該進(jìn)程已得到所有需求資，執(zhí)行后將釋放其所有擁有資！“endl; l=0; /歸零 cout“n安全的狀態(tài)!“endl; cout“安全序列為: “; coutendl“進(jìn)程“(“p0“)“; /輸出安全序列，考慮顯示格式，先輸出第一個(gè) Finish0=0; for (i=1; in; i+) cout“進(jìn)程“(“pi“)“; Finishi=0; /所有進(jìn)程置為未分配狀態(tài) coutendlendl; show; /顯示當(dāng)前狀態(tài) ppp: /申請(qǐng)大于可利用

26、量， 應(yīng)該阻塞等待,結(jié)束本次資申請(qǐng)，GOTO 語(yǔ)句跳轉(zhuǎn)至此 coutendl“是否繼續(xù)申請(qǐng)資(y/n) ?“; char* b=new char; /輸入y/n，判斷是否繼續(xù)申請(qǐng) b; coutendl; cout“-“endlendl; coutendl; if(*b=y|*b=Y) r=true; else r=false; /輸入非 Y 則令 R =false jieshu; /調(diào)用結(jié)束函數(shù) while (r=true); /結(jié)束函數(shù) void jieshu coutendlendl; cout“tt 演示計(jì)算完畢“endl; coutendlendl; /主函數(shù) int main coutendlendl“tttt模擬銀行家算法“endlendl; chushihua; /初始化函數(shù)調(diào)用 coutendl; show; /輸出當(dāng)前狀態(tài) safe; /判斷當(dāng)前狀態(tài)的安全性 if (ln) /l在safe中是用來(lái)記錄安全的進(jìn)程的個(gè)數(shù)的 cout“n當(dāng)前狀態(tài)不安全，拒絕申請(qǐng)！“endl; coutendl; return 0; else int i; /局部變量 l=0; coutendl“n當(dāng)前的狀態(tài)是安全的!安全序列為:“