操作系統(tǒng)課設(shè)報(bào)告華航

1、北華航天工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告北 華 航 天 工 業(yè) 學(xué) 院操作系統(tǒng)課程設(shè)計(jì)報(bào)告課設(shè)報(bào)告題目： 進(jìn)程調(diào)度算法 銀行家算法 虛擬內(nèi)存中的頁面置換算法 磁盤調(diào)度算法 作者所在系部： 計(jì)算機(jī)科學(xué)與工程系 作者所在專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 作者所在班級： B0951 作 者 姓 名 ： 指導(dǎo)教師姓名： 趙輝 完 成 時(shí) 間 ： 2011年12月15日 北華航天工業(yè)學(xué)院教務(wù)處制摘 要在當(dāng)前的市場經(jīng)濟(jì)體制下，計(jì)算機(jī)產(chǎn)業(yè)不斷發(fā)展裝大，人們都操作系統(tǒng)的要求也越來越高。操作系統(tǒng)的可靠性和有效性顯得十分重要，不僅提高了計(jì)算機(jī)資源的利用率，操作系統(tǒng)應(yīng)該更能方便用戶的使用，因此開發(fā)有效的完善的計(jì)算機(jī)系統(tǒng)成為大勢所趨。本

2、文利用Visual Basic6.0編寫程序，在相關(guān)理論基礎(chǔ)和技術(shù)支持下，編譯了此系統(tǒng)實(shí)現(xiàn)了操作系統(tǒng)中的一些重要的算法，基本上模擬了真正操作系統(tǒng)中一些主要算法的實(shí)現(xiàn)過程。進(jìn)程調(diào)度算法中的先來先服務(wù)、短進(jìn)程優(yōu)先和高響應(yīng)比優(yōu)先。銀行家算法中的資源申請和安全性檢查，虛擬頁面置換算法中的先進(jìn)先出、最近最久未使用和最佳算法。磁盤調(diào)度算法中的先來先服務(wù)算法先來先服務(wù)算法、最短尋道時(shí)間優(yōu)先算法、掃描算法和循環(huán)掃描算法。本次課程設(shè)計(jì)主要有四項(xiàng)：進(jìn)程調(diào)度系統(tǒng)、銀行家系統(tǒng)、虛擬內(nèi)存中的頁面置換和磁盤調(diào)度系統(tǒng)。每個(gè)系統(tǒng)都經(jīng)過全面的調(diào)試，能夠正確的運(yùn)行，達(dá)到了預(yù)期的效果。關(guān)鍵詞：操作系統(tǒng) 進(jìn)程調(diào)度 銀行家 虛擬內(nèi)存中

3、的頁面置換 磁盤調(diào)度課題名稱進(jìn)程調(diào)度算法完成時(shí)間第16周指導(dǎo)教師趙 輝職稱講師學(xué)生姓名 班 級B0951總體設(shè)計(jì)要求和技術(shù)要點(diǎn)編程實(shí)現(xiàn)進(jìn)程調(diào)度算法的基本過程，設(shè)計(jì)要求：（1）能夠選擇進(jìn)程調(diào)度算法（先來先服務(wù)、短進(jìn)程優(yōu)先算法和高響應(yīng)比優(yōu)先算法）。（2）可以輸入進(jìn)程數(shù)目（至少4個(gè)進(jìn)程），以及各進(jìn)程的提交時(shí)間和運(yùn)行時(shí)間。（3）能夠顯示調(diào)度過程及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。工作內(nèi)容及時(shí)間進(jìn)度安排114周：布置任務(wù)，軟件設(shè)計(jì)21516周：編寫代碼，上機(jī)調(diào)試316周：軟件驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告417周：上交課程設(shè)計(jì)成果課程設(shè)計(jì)成果1課程設(shè)計(jì)報(bào)告2源程序代碼課題名稱銀行家算法完成時(shí)間第16周指導(dǎo)教師趙

4、輝職稱講師學(xué)生姓名 班 級B0951總體設(shè)計(jì)要求和技術(shù)要點(diǎn)編寫一程序，能夠模擬銀行家算法和安全算法來避免死鎖。假設(shè)系統(tǒng)資源有A、B、C三種，可以運(yùn)行5個(gè)進(jìn)程。該程序具備的基本功能為：1、程序可以輸入3種資源的數(shù)目，5個(gè)進(jìn)程對3種資源的最大需求量、已分配量和需求量。2、能夠判斷某一時(shí)刻系統(tǒng)是否處于安全狀態(tài)，如果處于安全狀態(tài)能夠給出安全序列。3、當(dāng)某進(jìn)程提出資源申請時(shí)，能夠判斷是否能把資源分配給申請進(jìn)程。工作內(nèi)容及時(shí)間進(jìn)度安排114周：布置任務(wù)，軟件設(shè)計(jì)21516周：編寫代碼，上機(jī)調(diào)試316周：軟件驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告417周：上交課程設(shè)計(jì)成果課程設(shè)計(jì)成果1課程設(shè)計(jì)報(bào)告2源程序代碼課題名稱虛擬內(nèi)

5、存中的頁面置換完成時(shí)間第16周指導(dǎo)教師趙 輝職稱講師學(xué)生姓名 班 級B09513總體設(shè)計(jì)要求和技術(shù)要點(diǎn)編程實(shí)現(xiàn)虛擬內(nèi)存中的頁面置換的基本過程，設(shè)計(jì)要求：（1）能夠輸入進(jìn)程的頁面訪問序列和分配的內(nèi)存塊數(shù)。（2）可以選擇頁面置換算法（先進(jìn)先出算法、最近最久未使用算法和最佳置換算法）。（3）能夠以下圖形式顯示頁面置換過程。工作內(nèi)容及時(shí)間進(jìn)度安排114周：布置任務(wù)，軟件設(shè)計(jì)21516周：編寫代碼，上機(jī)調(diào)試316周：軟件驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告417周：上交課程設(shè)計(jì)成果課程設(shè)計(jì)成果1課程設(shè)計(jì)報(bào)告2源程序代碼課題名稱磁盤調(diào)度算法完成時(shí)間第16周指導(dǎo)教師趙 輝職稱講師學(xué)生姓名班 級B0951總體設(shè)計(jì)要求和技術(shù)

6、要點(diǎn)編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法，并求出每種算法的平均尋道長度。設(shè)計(jì)要求：（1）能夠輸入程序要訪問的磁道序列和磁頭當(dāng)前所在的磁道數(shù)。（2）可以選擇某磁盤調(diào)度算法（先來先服務(wù)算法、最短尋道時(shí)間優(yōu)先算法、掃描算法和循環(huán)掃描算法）。（3）能夠以下圖形式顯示磁盤調(diào)度順序和平均尋道長度。工作內(nèi)容及時(shí)間進(jìn)度安排114周：布置任務(wù)，軟件設(shè)計(jì)21516周：編寫代碼，上機(jī)調(diào)試316周：軟件驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告417周：上交課程設(shè)計(jì)成果課程設(shè)計(jì)成果1課程設(shè)計(jì)報(bào)告2源程序代碼目 錄第一章 緒論11.1 課程設(shè)計(jì)的背景和意義11.1.1 課程設(shè)計(jì)的理論研究基礎(chǔ)11.1.2 課程設(shè)計(jì)的意義21.2 課程設(shè)計(jì)環(huán)境2第二章

7、 需求分析22.1 功能要求22.1.1 進(jìn)程調(diào)度算法22.1.2 銀行家算法32.1.3虛擬內(nèi)存中的頁面置換32.1.4磁盤調(diào)度算法32.2 問題的解決方案42.2.1進(jìn)程調(diào)度42.2.2銀行家算法42.2.3虛擬內(nèi)存中的頁面置換42.2.4磁盤調(diào)度算法4第三章 系統(tǒng)設(shè)計(jì)53.1 數(shù)據(jù)設(shè)計(jì)53.1.1 結(jié)構(gòu)體設(shè)計(jì)51. 進(jìn)程調(diào)度算法的結(jié)構(gòu)體設(shè)計(jì)52. 銀行家算法的結(jié)構(gòu)體設(shè)計(jì)53. 虛擬內(nèi)存中的頁面置換的結(jié)構(gòu)體設(shè)計(jì)54磁盤調(diào)度算法的結(jié)構(gòu)體設(shè)計(jì)53.1.2 函數(shù)設(shè)計(jì)61. 進(jìn)程調(diào)度算法的函數(shù)設(shè)計(jì)62. 銀行家算法的函數(shù)設(shè)計(jì)63. 虛擬內(nèi)存中的頁面置換的函數(shù)設(shè)計(jì)64磁盤調(diào)度算法的函數(shù)設(shè)計(jì)6第四章

8、系統(tǒng)實(shí)現(xiàn)74.1 結(jié)構(gòu)體實(shí)現(xiàn)74.1.1進(jìn)程調(diào)度算法的結(jié)構(gòu)體實(shí)現(xiàn)74.1.2銀行家算法的結(jié)構(gòu)體實(shí)現(xiàn)84.1.3虛擬內(nèi)存中的頁面置換的結(jié)構(gòu)體實(shí)現(xiàn)84.1.4磁盤調(diào)度算法的結(jié)構(gòu)體實(shí)現(xiàn)84.2 函數(shù)實(shí)現(xiàn)84.2.1進(jìn)程調(diào)度算法的函數(shù)實(shí)現(xiàn)84.2.2銀行家算法的函數(shù)實(shí)現(xiàn)184.2.3虛擬內(nèi)存中的頁面置換的函數(shù)實(shí)現(xiàn)254.2.4磁盤調(diào)度算法的函數(shù)實(shí)現(xiàn)334.3 主函數(shù)實(shí)現(xiàn)464.3.1進(jìn)程調(diào)度算法的主函數(shù)實(shí)現(xiàn)464.3.2銀行家算法的主函數(shù)實(shí)現(xiàn)464.3.3虛擬內(nèi)存中的頁面置換的主函數(shù)實(shí)現(xiàn)474.3.4磁盤調(diào)度算法的主函數(shù)實(shí)現(xiàn)494.4 系統(tǒng)界面504.4.1 進(jìn)程調(diào)度算法的運(yùn)行界面504.4.2 銀行

9、家算法的運(yùn)行界面504.4.3虛擬內(nèi)存中的頁面置換的運(yùn)行界面514.4.4磁盤調(diào)度算法的運(yùn)行界面51第五章 系統(tǒng)測試515.1 模塊測試515.1.1進(jìn)程調(diào)度算法的模塊測試515.1.2銀行家算法的模塊測試535.1.3虛擬內(nèi)存中的頁面置換的模塊測試545.1.4磁盤調(diào)度算法的模塊測試555.2 課程設(shè)計(jì)過程中遇到的問題57總 結(jié)58致 謝59參考文獻(xiàn)60第一章 緒論操作系統(tǒng)是計(jì)算機(jī)中最重要的軟件。隨著計(jì)算機(jī)的飛速發(fā)展，好的操作系統(tǒng)能夠大大方便人們對計(jì)算機(jī)的使用。推動(dòng)操作系統(tǒng)發(fā)展的主要?jiǎng)恿τ校翰粩嗵岣叩挠?jì)算機(jī)利用率，方便用戶、器件的不斷更新?lián)Q代和計(jì)算機(jī)結(jié)構(gòu)的不斷發(fā)展。而操作系統(tǒng)的目標(biāo)：有效性、

10、方便性、可擴(kuò)充性和開放性。為了使操作系統(tǒng)更加完善并且與計(jì)算機(jī)的發(fā)展相匹配，好的操作系統(tǒng)和好的算法是關(guān)鍵。而怎樣實(shí)現(xiàn)操作系統(tǒng)對資源的管理就要依靠好的算法來實(shí)現(xiàn)。本次課程設(shè)計(jì)中的算法都是很常用的，在編寫這些算法的同時(shí)，進(jìn)一步了解對這些算法的應(yīng)用顯得很重要，系統(tǒng)的漏洞會(huì)減少，安全性會(huì)增加。1.1 課程設(shè)計(jì)的背景和意義1.1.1 課程設(shè)計(jì)的理論研究基礎(chǔ)（1）進(jìn)程調(diào)度算法：先來先服務(wù)(FCFS)調(diào)度算法：當(dāng)采用該算法時(shí)，每次調(diào)度是從就緒的進(jìn)程隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程運(yùn)行完成后或發(fā)生某事件而阻塞后，進(jìn)程調(diào)度程序才將處理機(jī)分配給其它進(jìn)程。短作業(yè)優(yōu)先(SJF)

11、該算法是以作業(yè)的長短來計(jì)算優(yōu)先級的，作業(yè)越短，其優(yōu)先級越高。作業(yè)的長短，是以作業(yè)所要求的運(yùn)行時(shí)間來衡量的。高響應(yīng)比優(yōu)先調(diào)度算法：該算法既考慮作業(yè)的等待時(shí)間，又考慮作業(yè)運(yùn)行時(shí)間。響應(yīng)比=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間（2）銀行家算法：當(dāng)每一個(gè)新進(jìn)程在進(jìn)入系統(tǒng)時(shí)，它必須申明在運(yùn)行過程中，可能需要的每種資源類型的最大單元數(shù)目，其數(shù)目不應(yīng)該超過系統(tǒng)所擁有的資源總量。當(dāng)進(jìn)程請求一組資源時(shí)，系統(tǒng)必須首先確定是否有足夠的資源分配給該進(jìn)程。若有，再進(jìn)一步計(jì)算，在將這些資源分配給進(jìn)程后，是否會(huì)使系統(tǒng)處于不安全狀態(tài)。如果不會(huì)，才將資源分配給它，否則讓進(jìn)程等待。（3）虛擬內(nèi)存中的頁面置換算法：內(nèi)存的物理塊

12、數(shù)有限，往往通過虛擬內(nèi)存即外存來擴(kuò)充內(nèi)存，使一些頁表先進(jìn)入內(nèi)存塊中，當(dāng)需要訪問的頁面不在當(dāng)前內(nèi)存塊時(shí)，需要置換原來的頁面。先進(jìn)先出置換算法：按照進(jìn)入內(nèi)存的先后順序，當(dāng)后續(xù)的頁面不在當(dāng)前內(nèi)存塊中時(shí)，需要調(diào)入的頁面將最先進(jìn)入內(nèi)存塊中的頁面置換出去。最近最久未使用置換算法：需要訪問的頁面不在內(nèi)存塊中時(shí)，將當(dāng)前內(nèi)存中很久未使用的頁面置換出去。最佳置換算法：最佳置換算法是預(yù)先知道系統(tǒng)將要使用哪些頁面而將以后用到最少的頁面置換出去，這種算法在實(shí)際中時(shí)無法實(shí)現(xiàn)的，所以本次沒有實(shí)現(xiàn)這個(gè)算法。 （4）磁盤調(diào)度算法：主要實(shí)現(xiàn)對訪問磁盤序列的調(diào)度，包括先來先服務(wù)、最短尋道時(shí)間優(yōu)先、掃描算法和循環(huán)掃描算法。先來先服務(wù)

13、則是從當(dāng)前磁道數(shù)一直按訪問序列依次訪問相應(yīng)的磁道；最短尋道時(shí)間優(yōu)先則是按距離當(dāng)前磁道最短的磁道先被訪問；掃描算法則是從當(dāng)前磁道號遞增的方向上依次訪問距離當(dāng)前磁道最短的磁道，然后在從外向里訪問；循環(huán)掃描算法則是從當(dāng)前磁道號遞增的方向上依次訪問距離當(dāng)前磁道最短的磁道，然后再從里向外訪問。1.1.2 課程設(shè)計(jì)的意義課程設(shè)計(jì)是學(xué)生學(xué)習(xí)完操作系統(tǒng)課程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓學(xué)生更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動(dòng)手能力。運(yùn)用到了結(jié)構(gòu)體、標(biāo)準(zhǔn)輸入輸出函數(shù)、格式輸出、一些最優(yōu)選擇比較、查找算法等、實(shí)現(xiàn)了基本的課設(shè)要求，對操作系統(tǒng)的理解

14、上了新的層次，更加明白了操作系統(tǒng)對各類作業(yè)的調(diào)度及處理。1.2 課程設(shè)計(jì)環(huán)境軟件環(huán)境：Microsoft Visual C+ 6.0環(huán)境 硬件環(huán)境：惠普筆記本電腦?？犷?處理器、1G獨(dú)立顯卡、320硬盤。第二章 需求分析2.1 功能要求2.1.1 進(jìn)程調(diào)度算法編程實(shí)現(xiàn)進(jìn)程調(diào)度算法的基本過程，設(shè)計(jì)要求：（1）能夠選擇進(jìn)程調(diào)度算法（先來先服務(wù)、短進(jìn)程優(yōu)先算法和高響應(yīng)比優(yōu)先算法）。（2）可以輸入進(jìn)程數(shù)目（至少4個(gè)進(jìn)程），以及各進(jìn)程的提交時(shí)間和運(yùn)行時(shí)間。（3）能夠以下圖形式顯示調(diào)度過程及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2.1. 2 銀行家算法編寫一程序，能夠模擬銀行家算法和安全算法來避免死鎖。假設(shè)系統(tǒng)

15、資源有A、B、C三種，可以運(yùn)行5個(gè)進(jìn)程。該程序具備的基本功能為：（1）程序可以輸入3種資源的數(shù)目，5個(gè)進(jìn)程對3種資源的最大需求量、已分配量和需求量。（2）能夠判斷某一時(shí)刻系統(tǒng)是否處于安全狀態(tài)，如果處于安全狀態(tài)能夠給出安全序列。（3）當(dāng)某進(jìn)程提出資源申請時(shí)，能夠判斷是否能把資源分配給申請進(jìn)程。2.1. 3 虛擬內(nèi)存中的頁面置換（1）能夠輸入進(jìn)程的頁面訪問序列和分配的內(nèi)存塊數(shù)。（2）可以選擇頁面置換算法（先進(jìn)先出算法、最近最久未使用算法和最佳置換算法）。（3）能夠以下圖形式顯示頁面置換過程。（4）能夠計(jì)算缺頁次數(shù)和缺頁率。2.1. 4 磁盤調(diào)度算法編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法，并求出每種算法的平均尋

16、道長度。設(shè)計(jì)要求：（1）能夠輸入程序要訪問的磁道序列和磁頭當(dāng)前所在的磁道數(shù)。（2）可以選擇某磁盤調(diào)度算法（先來先服務(wù)算法、最短尋道時(shí)間優(yōu)先算法、掃描算法和循環(huán)掃描算法）。（3）能夠以下圖形式顯示磁盤調(diào)度順序和平均尋道長度。2.2 問題的解決方案2.2.1進(jìn)程調(diào)度采用結(jié)構(gòu)體數(shù)組存放進(jìn)程的信息，首先對所有提交的進(jìn)程進(jìn)行排序，先按照時(shí)間順序，如果時(shí)間相同則短進(jìn)程在前。在先來先服務(wù)調(diào)度算法中先判斷到達(dá)時(shí)間，依據(jù)到達(dá)時(shí)間的早晚調(diào)度相應(yīng)進(jìn)程；在短作業(yè)優(yōu)先中還是先判斷到達(dá)時(shí)間，只有在上一個(gè)進(jìn)程結(jié)束之后下一個(gè)進(jìn)程已經(jīng)來到時(shí)，則采用最短進(jìn)程優(yōu)先，否則按照先來先服務(wù)的順序調(diào)度執(zhí)行。到達(dá)時(shí)間相等時(shí)采用短作業(yè)優(yōu)先，運(yùn)

17、行時(shí)間相等時(shí)先來先服務(wù)。在高響應(yīng)比優(yōu)先調(diào)度算法中，當(dāng)上一個(gè)進(jìn)程結(jié)束后下一個(gè)進(jìn)程已經(jīng)來到時(shí)，采用高響應(yīng)比優(yōu)先調(diào)度，否則還采用先來先服務(wù)算法。2.2.2銀行家算法將進(jìn)程抽象成一個(gè)結(jié)構(gòu)體，定義申請創(chuàng)建進(jìn)程的結(jié)構(gòu)體數(shù)組，存放相應(yīng)的信息，用來存儲該進(jìn)程對資源的最大請求量、已分配量和需求量。安全性算法用來判斷當(dāng)前是否處于安全狀態(tài)；若有進(jìn)程提出資源申請，先嘗試著將其請求的資源分配給它，然后調(diào)用安全性算法，判斷此次資源分配是否會(huì)導(dǎo)致系統(tǒng)處于不安全狀態(tài)，如果處于不安全狀態(tài)則把已分配的收回，否則分配成功。2.2.3虛擬內(nèi)存中的頁面置換采用頁面信息結(jié)構(gòu)體用來存放頁號和到來時(shí)間。將要訪問的頁號和虛擬內(nèi)存中的塊號都定義

18、為相同的結(jié)構(gòu)體數(shù)組。首先判斷內(nèi)存塊中是否存儲有該頁號，如果有則不缺頁，如果沒有，則看內(nèi)存塊是否已滿，如果未滿，則直接將頁面調(diào)入內(nèi)存；如果已滿根據(jù)相應(yīng)的算法將原內(nèi)存中的某一塊置換。先來先服務(wù)是替換掉最先進(jìn)入內(nèi)存的頁面；最近最久未使用是替換掉最近一段時(shí)間沒有使用過的頁面，最佳算法則是替換掉以后永不使用的或者是最長時(shí)間內(nèi)不再被訪問的頁面。2.2.4磁盤調(diào)度算法采用全局變量一維數(shù)組來存儲要訪問的磁盤序列。按照順序存放在一維數(shù)組里，同時(shí)按照相應(yīng)的算法來訪問磁道。先來先服務(wù)則是依次按照訪問序列訪問，最短尋道時(shí)間優(yōu)先則是從當(dāng)前磁道判斷找與當(dāng)前磁道距離最近的磁道號進(jìn)行訪問，掃描算法的方向有兩種一種是像磁道號增

19、加的方向，另一種是按照磁道號減小的方向訪問。循環(huán)掃描的方向也有向磁道號方向增加和向磁道號方向減少兩種。第三章 系統(tǒng)設(shè)計(jì)3.1 數(shù)據(jù)設(shè)計(jì)3.1.1 結(jié)構(gòu)體設(shè)計(jì)1. 進(jìn)程調(diào)度算法結(jié)構(gòu)體結(jié)構(gòu)體名稱Process數(shù)據(jù)成員 name; /進(jìn)程名稱 sub;/提交時(shí)間operate;/執(zhí)行時(shí)間wait;/等待時(shí)間 finish;/完成時(shí)間 work; /運(yùn)行時(shí)間 cycle;/周轉(zhuǎn)時(shí)間 wcycle;/帶權(quán)周轉(zhuǎn)時(shí)間2. 銀行家算法的結(jié)構(gòu)體設(shè)計(jì)結(jié)構(gòu)體名稱Source數(shù)據(jù)成員maxMAX; /max是每個(gè)進(jìn)程所需資源的最大需求量allocationMAX; /allocation是進(jìn)程已分配的資源數(shù)needM

20、AX; /need是每個(gè)進(jìn)程尚需要的資源數(shù)3. 虛擬內(nèi)存中的頁面置換的結(jié)構(gòu)體設(shè)計(jì)結(jié)構(gòu)體名稱pinfo數(shù)據(jù)成員int num; /頁面號int time; /序號4. 磁盤調(diào)度算法的數(shù)組定義int totalnum; /全局變量總磁道數(shù)int snum; /全局變量訪問的磁道總數(shù)int tracknumMAX;/全局變量存放要訪問的磁道號int lengthMAX; /全局變量存放每次移動(dòng)距離int begin; /開始磁道號int visitedMAX; /是否被訪問過int sortedMAX; /將磁道排序int finalMAX;/最終訪問序列3.1. 2函數(shù)設(shè)計(jì)1. 進(jìn)程調(diào)度算法進(jìn)程調(diào)

21、度中的函數(shù)如下：init(Process p)：初始化進(jìn)程函數(shù)add(Process p,int m)：進(jìn)程信息計(jì)算函數(shù)sort(Process p)：對進(jìn)程按時(shí)間排序函數(shù)display(Process p,int x,int xx)：進(jìn)程信息顯示函數(shù)FCFS(Process p)：進(jìn)程調(diào)度中的先來先服務(wù)算法SJF(Process p)：進(jìn)程調(diào)度中的短進(jìn)程優(yōu)先算法HighPriority(Process p)：進(jìn)程調(diào)度中的高優(yōu)先權(quán)調(diào)度算法2. 銀行家算法init(Source s)：初始化進(jìn)程和資源函數(shù)display(Source s)：顯示各進(jìn)程和資源的情況safe(Source s)：安全

22、性算法Request(Source s)：銀行家算法，某一進(jìn)程請求資源檢查是否能夠分配release(Source s)：某一進(jìn)程獲得資源后請求釋放3. 虛擬內(nèi)存頁面置換算法init(pinfo pages,pinfo store)：初始化頁面和存儲塊display(pinfo store)：輸出當(dāng)前存儲塊中的頁面search(int y,pinfo store)：檢查存儲塊中是否有相同的頁面FIFO(pinfo pages,pinfo store)：先進(jìn)先出置換算法LRU(pinfo pages,pinfo store)：最近最久未使用置換算法OPT(pinfo pages,pinfo st

23、ore)：最佳置換算法count(pinfo pages,pinfo store,int i,int j)：以后多長時(shí)間被使用4. 磁盤調(diào)度算法init()：對磁道信息進(jìn)行初始化FCFS()：先來先服務(wù)算法SSTF()：最短尋道時(shí)間優(yōu)先算法sort()：按照磁道號排序算法SCAN()：掃描算法CSCAN()：循環(huán)掃描算法第四章 系統(tǒng)實(shí)現(xiàn)4.1 結(jié)構(gòu)體實(shí)現(xiàn)4.1.1進(jìn)程調(diào)度算法的結(jié)構(gòu)體實(shí)現(xiàn)const int MAX=100;struct Process /進(jìn)程結(jié)構(gòu)體string name;double sub;/提交時(shí)間double operate;/執(zhí)行時(shí)間double wait;/等待時(shí)間d

24、ouble finish;/完成時(shí)間double work;/運(yùn)行時(shí)間double cycle;/周轉(zhuǎn)時(shí)間double wcycle;/帶權(quán)周轉(zhuǎn)時(shí)間int sign;/是否被執(zhí)行;4.1.2銀行家算法的結(jié)構(gòu)體實(shí)現(xiàn)const int MAX=10;typedef structint maxMAX;int allocationMAX;int needMAX;Source;4.1.3虛擬內(nèi)存中的頁面置換的結(jié)構(gòu)體實(shí)現(xiàn)typedef struct int num; /頁面號int time;/進(jìn)入序號pinfo;4.1.4磁盤調(diào)度算法的結(jié)構(gòu)體實(shí)現(xiàn)const int MAX=500;int totalnu

25、m; /總磁道數(shù)int snum; /訪問的磁道總數(shù)int tracknumMAX;/存放要訪問的磁道號int lengthMAX; /移動(dòng)距離int begin; /開始磁道號int visitedMAX; /是否被訪問過int sortedMAX; /排列后的順序int finalMAX;/最終訪問的序列4.2 函數(shù)實(shí)現(xiàn)4.2.1進(jìn)程調(diào)度算法的函數(shù)實(shí)現(xiàn)void init(Process p)/初始化各個(gè)進(jìn)程的信息int i;for(i=0;i<MAX;i+)pi.sub=0;pi.operate=0;pi.wait=0;pi.finish=0;pi.work=0;pi.cycle=0

26、;pi.wcycle=0;pi.sign=0;cout<<"請輸入進(jìn)程的個(gè)數(shù)："cin>>num;for(i=0;i<num;i+)cout<<"請輸入第"<<i+1<<"個(gè)進(jìn)程的名稱、到達(dá)時(shí)間和運(yùn)行時(shí)間："<<endl;cin>>>>pi.sub>>pi.work;while(pi.sub<0|pi.work<0)cout<<"您的輸入錯(cuò)誤，請重新輸入第"<

27、<i+1<<"個(gè)進(jìn)程的名稱、到達(dá)時(shí)間和運(yùn)行時(shí)間："cin>>>>pi.sub>>pi.work;void sort(Process p)/按到達(dá)時(shí)間排序 int i; int j; int k; for(i=0;i<num-1;i+) k=i; for(j=i+1;j<num;j+) if(pi.sub>pj.sub) k=j;Process x;x=pk;pk=pi;pi=x; if(pi.sub=pj.sub) if(pi.work>pj.work) k=j;Process y;

28、y=pk;pk=pi;pi=y; void add(Process p,int m)/對進(jìn)程信息進(jìn)行修改 pm.wait=pm.operate-pm.sub; pm.finish=pm.operate+pm.work; pm.cycle=pm.finish-pm.sub; pm.wcycle=pm.cycle/pm.work;void display(Process p,int x,int xx)/顯示進(jìn)程調(diào)度信息cout<<"-"<<endl;cout<<xx<<setw(8)<<<<s

29、etw(8)<<px.sub<<setw(8)<<px.operate<<setw(8)<<px.wait <<setw(8)<<px.finish<<setw(8)<<px.work<<setw(8)<<px.cycle<<setw(8)<<px.wcycle<<endl;void FCFS(Process p)/先來先服務(wù)調(diào)度算法double averagecycle;double averagewcyle;averagec

30、ycle=0;averagewcyle=0;int i;for(i=0;i<num;i+)pi.sign=0;/先將訪問的標(biāo)志位置0 cout<<"=先來先服務(wù)算法="<<endl; cout<<"次序 名稱 提交時(shí)刻 開始時(shí)刻 等待時(shí)間 完成時(shí)間 運(yùn)行時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間"<<endl;sort(p);for(i=0;i<num;i+)if(i=0)pi.operate=pi.sub;add(p,i);display(p,i,i+1);elseif(pi.sub<=pi-1.fi

31、nish)pi.operate=pi-1.finish;add(p,i);display(p,i,i+1);elsepi.operate=pi.sub;add(p,i);display(p,i,i+1);for(i=0;i<num;i+) averagecycle=averagecycle+pi.cycle;for(i=0;i<num;i+) averagewcyle=averagewcyle+pi.wcycle;cout<<"使用先來先服務(wù)算法的平均周轉(zhuǎn)時(shí)間為："<<averagecycle/num<<endl;cout&l

32、t;<"使用先來先服務(wù)算法的平均帶權(quán)周轉(zhuǎn)時(shí)間為："<<averagewcyle/num<<endl;void SJF(Process p)/短進(jìn)程優(yōu)先調(diào)度算法int i;int j;int k;int ii;for(i=0;i<num;i+)pi.sign=0;cout<<"=短進(jìn)程優(yōu)先算法="<<endl; cout<<"次序 名稱 提交時(shí)刻 開始時(shí)刻 等待時(shí)間 完成時(shí)間 運(yùn)行時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間"<<endl;sort(p);int fin

33、al;int daoda=0;int temp=0;/標(biāo)記上次執(zhí)行到哪里int c=0;double averagecycle;double averagewcyle;averagecycle=0;averagewcyle=0;Process p1MAX,p2MAX;for(i=0;i<num;i+)if(i=0)/如果是第一個(gè)進(jìn)程p0.operate=p0.sub;p0.sign=1;add(p,0);p10=p0;temp+;display(p1,0,temp); final=p1i.finish;else/如果不是第一個(gè)進(jìn)程daoda=0;for(j=0;j<num;j+)i

34、f(pj.sign=0&&pj.sub<=final)daoda+;if(daoda=0)/如果沒有到達(dá)的則找到最早到達(dá)的且最短的進(jìn)程c=0;for( ii=0;ii<num;ii+)if(pii.sign=0)c=ii;break;/找到將要執(zhí)行程序的下標(biāo) pc.operate=pc.sub;/開始運(yùn)行時(shí)間等于提交時(shí)間pc.sign=1;add(p,c);p1i=pc;temp+;display(p1,i,temp);final=p1i.finish;elseint biao=0;for( ii=0;ii<num;ii+)if(pii.sign=0&

35、&pii.sub<=final)biao=ii;break;for(ii=0;ii<num;ii+)if(pii.sign=0&&pbiao.work>pii.work&&pii.sub<=final)biao=ii;pbiao.sign=1;pbiao.operate=final;add(p,biao);p1i=pbiao;temp+;display(p1,i,temp);/i+1=tempfinal=p1i.finish;for(i=0;i<num;i+) averagecycle=averagecycle+p1i.cy

36、cle;for(i=0;i<num;i+) averagewcyle=averagewcyle+p1i.wcycle;cout<<"使用先來先服務(wù)算法的平均周轉(zhuǎn)時(shí)間為："<<averagecycle/num<<endl;cout<<"使用先來先服務(wù)算法的平均帶權(quán)周轉(zhuǎn)時(shí)間為："<<averagewcyle/num<<endl;void HighPriority(Process p)/高響應(yīng)比優(yōu)先調(diào)度算法int i;int j;int k;int ii;for(i=0;i<n

37、um;i+)pi.sign=0;cout<<"=高響應(yīng)比優(yōu)先算法="<<endl; cout<<"次序 名稱 提交時(shí)刻 開始時(shí)刻 等待時(shí)間 完成時(shí)間 運(yùn)行時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間"<<endl; sort(p);int final;int daoda=0;int temp=0;/標(biāo)記上次執(zhí)行到哪里int c=0;double averagecycle;double averagewcyle;averagecycle=0;averagewcyle=0;Process p1MAX,p2MAX;int pri

38、ority;for(i=0;i<num;i+)if(i=0)/如果是第一個(gè)進(jìn)程p0.operate=p0.sub;p0.sign=1;add(p,0);p10=p0;temp+;display(p1,0,temp); final=p1i.finish;else/如果不是第一個(gè)進(jìn)程daoda=0;for(j=0;j<num;j+)if(pj.sign=0&&pj.sub<=final)daoda+;if(daoda=0)/如果沒有到達(dá)的則找到最早到達(dá)的且最短的進(jìn)程for(ii=0;ii<num;ii+)if(pii.sign=0)c=ii;break;/找

39、到將要執(zhí)行程序的下標(biāo)pc.sign=1; pc.operate=pc.sub;/開始運(yùn)行時(shí)間等于提交時(shí)間add(p,c);p1i=pc;temp+;display(p1,i,temp);final=p1i.finish;elseint biao=0;for( ii=0;ii<num;ii+)if(pii.sign=0&&pii.sub<=final)biao=ii;break;priority=(final-pbiao.sub+pbiao.operate)/pbiao.operate;for(ii=0;ii<num;ii+)if(pii.sign=0&

40、&pbiao.work>pii.work &&pii.sub<=final&&(final-pii.sub+pii.operate)/pii.operate>priority)priority=(final-pii.sub+pii.operate)/pii.operate;biao=ii;pbiao.sign=1;pbiao.operate=final;add(p,biao);p1i=pbiao;temp+;display(p1,i,temp);final=p1i.finish;for(i=0;i<num;i+) averagec

41、ycle=averagecycle+pi.cycle;for(i=0;i<num;i+) averagewcyle=averagewcyle+pi.wcycle;cout<<"使用先來先服務(wù)算法的平均周轉(zhuǎn)時(shí)間為："<<averagecycle/num<<endl;cout<<"使用先來先服務(wù)算法的平均帶權(quán)周轉(zhuǎn)時(shí)間為："<<averagewcyle/num<<endl;4.2.2銀行家算法的函數(shù)實(shí)現(xiàn)void init(Source s)/初始化進(jìn)程和資源int i,j;int y

42、;for(i=0;i<MAX;i+)for(j=0;j<MAX;j+)si.allocationj=0;si.maxj=0;si.needj=0;for(i=0;i<MAX;i+)availablei=0;requesti=0;cout<<"請輸入系統(tǒng)中的進(jìn)程數(shù)："cin>>pnum;while(pnum<0|pnum>MAX)cout<<"您輸入的進(jìn)程數(shù)不正確請重新輸入："cin>>pnum;cout<<"請輸入系統(tǒng)中的資源數(shù)："cin>

43、>snum;while(snum<0|snum>MAX)cout<<"您輸入的資源數(shù)不正確請重新輸入："cin>>snum;for(i=0;i<pnum;i+)cout<<"請分別輸入第"<<i<<"個(gè)進(jìn)程對各類資源的最大需求量:"<<endl;for(j=0;j<snum;j+)cin>>si.maxj;while(si.maxj<0|si.maxj>MAX)cout<<"您輸入的進(jìn)程數(shù)

44、不正確請重新輸入："cin>>si.maxj; cout<<"請分別輸入第"<<i<<"個(gè)進(jìn)程各類資源已分配的數(shù)量:"<<endl;for(j=0;j<snum;j+)cin>>si.allocationj;while(si.allocationj<0|si.allocationj>MAX|si.allocationj>si.maxj)cout<<"您輸入的進(jìn)程數(shù)不正確請重新輸入："cin>>si.allo

45、cationj;for(j=0;j<snum;j+)si.needj=si.maxj-si.allocationj;for(j=0;j<snum;j+)while(si.maxj!=si.allocationj+si.needj|si.allocationj>si.maxj)/已分配數(shù)不能大于最大需求量cout<<"*您的輸入不正確請重新輸入*"<<endl;cout<<"第"<<i<<"個(gè)進(jìn)程的最大需求量："<<endl;for(j=0;j&l

46、t;snum;j+)cin>>si.maxj;cout<<"請分別輸入第"<<i<<"個(gè)進(jìn)程各類資源已分配的數(shù)量:"<<endl;for(j=0;j<snum;j+)cin>>si.allocationj;cout<<"請分別輸入第"<<i<<"個(gè)進(jìn)程各類資源需求的數(shù)量:"<<endl;for(j=0;j<snum;j+)cin>>si.needj;cout<<

47、"請輸入各類資源現(xiàn)有數(shù)目："<<endl;for(i=0;i<snum;i+)cin>>availablei;while(availablei<0)cout<<"您的輸入錯(cuò)誤，請重新輸入："cin>>availablei;void display(Source s)/資源分配顯示函數(shù)int i,j;cout<<"="<<endl;cout<<" 資源分配"<<endl;cout<<"=&

48、quot;<<endl;cout<<"系統(tǒng)可用資源分別為："<<endl;for(i=0;i<snum;i+)cout<<availablei<<" " ;cout<<endl;cout<<"MAX ALLOCATION NEED"<<endl;for(i=0;i<pnum;i+)for(j=0;j<snum;j+)cout<<si.maxj<<" "cout<<&q

49、uot; "for(j=0;j<snum;j+)cout<<si.allocationj<<" "cout<<" "for(j=0;j<snum;j+)cout<<si.needj<<" "cout<<endl;int safe(Source s)/安全性算法int sign;int workMAX;int finishMAX;int sortMAX;int i,j,k,m,n;int flag;m=0;for(i=0;i<snum;i

50、+)worki=availablei;for(j=0;j<MAX;j+)finishj=0;/初始化將所有未分配的置為0for(i=0;i<pnum;i+)sign=0;for(j=0;j<snum;j+)if(finishi=0&&si.needj<=workj) sign+; if(sign=snum) for(k=0;k<snum;k+)workk=workk+si.allocationk;finishi=1;sortm=i;m+;i=-1; elsebreak;flag=0;for(k=0;k<pnum;k+) if(finishk=1)flag+;if(flag=pnum)cout<<"系統(tǒng)存在安全性序列。安全性序列為："<<