【正文】 內(nèi)蒙古工業(yè)大學(xué)操作系統(tǒng)課程設(shè)計(jì)學(xué)校代碼： 10128學(xué) 號(hào)： 200810205004課程設(shè)計(jì)題 目：銀行家算法的設(shè)計(jì)與實(shí)現(xiàn) 學(xué)生姓名：朱見濤 學(xué) 院：信息工程學(xué)院系 別：計(jì)算機(jī)系 專 業(yè)：軟件工程 班 級(jí)：軟081指導(dǎo)教師：秦俊平 講師馬志強(qiáng) 講師20011年1月18日 18內(nèi)蒙古工業(yè)大學(xué)課程設(shè)計(jì)任務(wù)書（二）學(xué)院（系）：信息學(xué)院計(jì)算機(jī)系 課程名稱：操作系統(tǒng)課程設(shè)計(jì) 指導(dǎo)教師（簽名）： 專業(yè)班級(jí)： 軟件工程 08－1 學(xué)生姓名： 朱見濤 學(xué)號(hào)： 200810205004 一、課程設(shè)計(jì)題目銀行家算法的設(shè)計(jì)與實(shí)現(xiàn)二、課程設(shè)計(jì)的目的通過(guò)銀行家算法設(shè)計(jì)與實(shí)現(xiàn)，可以加深學(xué)生對(duì)死鎖的理解，掌握死鎖的預(yù)防、避免、檢測(cè)和解除的基本原理，重點(diǎn)掌握死鎖的避免方法—銀行家算法。使學(xué)生初步具有研究、設(shè)計(jì)、編制和調(diào)試操作系統(tǒng)模塊的能力。 三、課程設(shè)計(jì)的主要內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計(jì)要求、工作量要求等） 技術(shù)參數(shù)： Windows XP系統(tǒng)，VC++。設(shè)計(jì)要求： 1． 設(shè)計(jì)銀行家算法的核心數(shù)據(jù)結(jié)構(gòu)、安全性檢查算法；2． 畫出銀行家算法流程圖；3． 編程實(shí)現(xiàn)算法功能；4． 編寫課程設(shè)計(jì)說(shuō)明書。 工作量要求：完成以上設(shè)計(jì)要求中的所有算法功能。四、工作進(jìn)度安排 周一：布置、講解題目，收集資料；周二：系統(tǒng)分析，算法設(shè)計(jì)；周三：編制、調(diào)試程序；周四：測(cè)試系統(tǒng)，形成設(shè)計(jì)結(jié)論，編寫課設(shè)報(bào)告；周五：系統(tǒng)及材料驗(yàn)收，課設(shè)答辯。五、主要參考文獻(xiàn)[1] 張堯?qū)W編．計(jì)算機(jī)操作系統(tǒng)教程（第三版）習(xí)題解答與實(shí)驗(yàn)指導(dǎo)．北京:清華大學(xué)出版社，2006[2] 湯子瀛主編．計(jì)算機(jī)操作系統(tǒng)（第三版）．西安:西安電子科技大學(xué)出版社，2001 [3] 張坤等編．操作系統(tǒng)實(shí)驗(yàn)教程．北京:清華大學(xué)出版社，2008審核批準(zhǔn)意見系（教研室）主任（簽字） 目 錄第一章 設(shè)計(jì)內(nèi)容 11．1 設(shè)計(jì)目的 11．2 設(shè)計(jì)要求 11．3 程序設(shè)計(jì)思想 1第二章 數(shù)據(jù)結(jié)構(gòu)、算法和算法流程圖 22．1 數(shù)據(jù)結(jié)構(gòu) 22．2 程序功能圖 22．3 程序流程圖 3第三章 程序運(yùn)行結(jié)果及分析 63．1 程序運(yùn)行結(jié)果 63．2 程序分析 7第四章 心得體會(huì) 8參考文獻(xiàn) 9附錄 程序清單 10第一章 設(shè)計(jì)內(nèi)容1．1 設(shè)計(jì)目的通過(guò)銀行家算法設(shè)計(jì)與實(shí)現(xiàn)，可以加深學(xué)生對(duì)死鎖的理解，掌握死鎖的預(yù)防、避免、檢測(cè)和解除的基本原理，重點(diǎn)掌握死鎖的避免方法—銀行家算法。使學(xué)生初步具有研究、設(shè)計(jì)、編制和調(diào)試操作系統(tǒng)模塊的能力。1．2 設(shè)計(jì)要求銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)的申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i )當(dāng)前占有資源量之和。安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài)：不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。我們可以把操作系統(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í)，要測(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ò)則拒絕分配資源，若沒有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。1）分析設(shè)計(jì)內(nèi)容，給出解決方案（要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。2）畫出程序的基本結(jié)構(gòu)框圖和流程圖。3）對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析說(shuō)明。4）源代碼格式要規(guī)范。5）設(shè)計(jì)合適的測(cè)試用例，隊(duì)得到的運(yùn)行結(jié)果要有分析。6）設(shè)計(jì)中遇到的問(wèn)題，設(shè)計(jì)的心得體會(huì)。7）按期提交完整的程序代碼，可執(zhí)行程序和課程設(shè)計(jì)報(bào)告。 程序設(shè)計(jì)思想輸入當(dāng)前進(jìn)程資源的使用情況以及整個(gè)系統(tǒng)的資源使用情況，并進(jìn)行初始化安全性檢查；如果是不安全狀態(tài)，重新初始化系統(tǒng)；否則，從等待隊(duì)列中提取一個(gè)等待進(jìn)程，使用銀行家算法進(jìn)行檢測(cè)，輸出當(dāng)前系統(tǒng)的狀態(tài)和安全序列；如果是安全狀態(tài)，系統(tǒng)繼續(xù)從等待隊(duì)列中提取等待進(jìn)程進(jìn)行檢查；如果是不安全狀態(tài)，進(jìn)程回到等待隊(duì)列，系統(tǒng)從等待隊(duì)列中提取等待進(jìn)程進(jìn)行檢查。系統(tǒng)中申請(qǐng)資源的進(jìn)程全部進(jìn)入等待隊(duì)列等候處理。第二章 數(shù)據(jù)結(jié)構(gòu)、算法和算法流程圖2．1 數(shù)據(jù)結(jié)構(gòu)銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)可用資源向量 int AVAILABLE[i] //j為資源的種類最大需求矩陣 int MAX[i][j] //i為進(jìn)城的數(shù)量分配矩陣 int ALLOCATION[i][j] 需求矩陣 int NEED[i][j]=MAX[i][j]ALLOCATION[i][j]申請(qǐng)各類資源數(shù)量 int REQUEST[i][j] //i申請(qǐng)j資源的數(shù)量工作向量 int Work[i] int FINISH[i]安全序列 int p[i]2．2 程序功能圖銀行家算法系統(tǒng)顯示分配資源狀態(tài)資源分配安全性檢查初始化資源銀行家算法實(shí)現(xiàn)資源分配顯示安全序列文件系統(tǒng)提供的文件操作有建立文件(mkfile)、復(fù)制文件(copy)、顯示文件所有內(nèi)容(type)、刪除文件(delfile)。可以通過(guò)鍵盤輸入命令來(lái)模擬文件的操作。2．3 程序流程圖（1）主程序流程圖：第三章 程序運(yùn)行結(jié)果及分析3．1 程序運(yùn)行結(jié)果（1）初始化界面（2）檢測(cè)系統(tǒng)資源分配是否安全（若安全，輸入安全序列）3．2 程序分析本程序依靠鍵盤輸入初始化系統(tǒng)資源數(shù)量及種類，有銀行家算法檢驗(yàn)系統(tǒng)資源是否安全，輸出安全序列。提出請(qǐng)求REQUEST[i]，同意分配，則進(jìn)行安全性算法Safe（），否則輸出提示：請(qǐng)求被拒絕。直到所有進(jìn)程FINISH=true，安全且輸出安全序列，安全算法Safe（）結(jié)束。第四章 心得體會(huì)通過(guò)本次的課程設(shè)計(jì)，使我能夠正確運(yùn)用操作系統(tǒng)課程中所學(xué)的基本理論和知識(shí)。操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動(dòng)態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。而我本次課程設(shè)計(jì)就是得用銀行家算法來(lái)避免“死鎖”。銀行家算法是一個(gè)分配資源的過(guò)