操作系統(tǒng)課程設(shè)計報告-基于時間片的輪轉(zhuǎn)調(diào)度算法

PAGE58淮陰工學(xué)院操作系統(tǒng)課程設(shè)計報告選題名稱:基于時間片的高優(yōu)先級調(diào)度模擬實現(xiàn)系（院）: 經(jīng)濟(jì)管理學(xué)院 專業(yè): 信息管理與信息系統(tǒng) 班級:信管1091姓名:趙潔學(xué)號：1091807127姓名:楊娟學(xué)號：1091807123姓名:俞慶燕學(xué)號：1091807124姓名:方晨學(xué)號：1091807105指導(dǎo)教師:陳禮青邱軍林學(xué)年學(xué)期: 2011~2012 學(xué)年第一學(xué)期 2012 年1 月設(shè)計任務(wù)書課題名稱基于時間片的高優(yōu)先級調(diào)度模擬實現(xiàn)設(shè)計目的理解進(jìn)程調(diào)度相關(guān)理論。掌握時間片調(diào)度原理。掌握高優(yōu)先級調(diào)度原理。實驗環(huán)境硬件：PC機，奔騰IV以上CPU，512MB以上內(nèi)存，80G以上硬盤。軟件：Windows2000/XP、MicrosoftVisualC++6.0。任務(wù)要求搜集基于時間片的高優(yōu)先級調(diào)度模擬實現(xiàn)可能涉及到的知識和相關(guān)資料。應(yīng)用MicrosoftVisualC++6.0集成開發(fā)環(huán)境，設(shè)計并實現(xiàn)一個基于時間片的高優(yōu)先級調(diào)度模擬程序。確?；跁r間片的高優(yōu)先級調(diào)度模擬程序能正確運行。參加答辯，撰寫課程設(shè)計報告。工作進(jìn)度計劃序號起止日期工作內(nèi)容12012.1.1課題任務(wù)下達(dá)，查閱文獻(xiàn)資料22012.1.2～2012.1.3課題總體設(shè)計、素材搜集與處理32012.1.4～2012.1.7課題詳細(xì)設(shè)計、調(diào)試、完善設(shè)計42012.1.8答辯，撰寫報告指導(dǎo)教師（簽章）：年月日摘要操作系統(tǒng)（OperatingSystem，簡稱OS）是計算機系統(tǒng)的重要組成部分，是一個重要的系統(tǒng)軟件，它負(fù)責(zé)管理計算機系統(tǒng)的硬、軟件資源和整個計算機的工作流程，協(xié)調(diào)系統(tǒng)部件之間,系統(tǒng)與用戶之間、用戶與用戶之間的關(guān)系。隨著操作系統(tǒng)的新技術(shù)的不斷出現(xiàn)功能不斷增加。操作系統(tǒng)作為一個標(biāo)準(zhǔn)的套裝軟件必須滿足盡可能多用戶的需要，于是系統(tǒng)不斷膨脹，功能不斷增加，并逐漸形成從開發(fā)工具到系統(tǒng)工具再到應(yīng)用軟件的一個平臺環(huán)境。更能滿足用戶的需求。隨著計算機技術(shù)的不斷發(fā)展，人們對于計算機系統(tǒng)性能的要求也越來越高，對于操作系統(tǒng)所使用的算法也在不斷地發(fā)展。OS對調(diào)度分配實質(zhì)是一種資源分配，因而調(diào)度算法要根據(jù)不同的系統(tǒng)資源分配策略所規(guī)定的來分配算法。對于不同的系統(tǒng)目標(biāo)，又必須采用不同的調(diào)度算法。有的算法適合長作業(yè)，有的適合短作業(yè)，有的適合作業(yè)調(diào)度，有的適合進(jìn)程調(diào)度。本課程設(shè)計所討論的基于優(yōu)先級的時間片調(diào)度算法是在諸多的調(diào)度算法中具有明顯有點的調(diào)度算法。該算法涉及到高優(yōu)先級調(diào)度算法、時間片輪轉(zhuǎn)算法、多級反饋隊列調(diào)度算法。本課題基于MicrosoftVisualC++6.0平臺，對算法作出具體的解釋。關(guān)鍵詞：操作系統(tǒng)，調(diào)度算法，優(yōu)先級，時間片目錄43301引言 5TOC\o"1-2"\h\z\u233811.1課題設(shè)計背景 5251641.2目的和意義 6173161.3調(diào)度算法發(fā)展過程 6234061.4使用的到的開發(fā)工具 9284302需求分析 11143102.1需求背景 11215412.2課程設(shè)計任務(wù) 14218222.3課程設(shè)計要求 15250582.4課程設(shè)計思想 1561043概要設(shè)計 16325763.1課程設(shè)計所用方法及其原理 1657283.2主要的數(shù)據(jù)結(jié)構(gòu) 17280113.3課題設(shè)計的流程圖 18178424詳細(xì)設(shè)計 19196024.1設(shè)計進(jìn)程控制塊 19207424.2進(jìn)程調(diào)度 21245444.3優(yōu)先級 22267194.3.1優(yōu)先級簡介 22211654.3.2優(yōu)先權(quán)調(diào)度算法的類型 22244644.4時間片輪轉(zhuǎn)算法 2640824.5多級反饋隊列調(diào)度算法 2926485調(diào)試與操作說明 3416545.1調(diào)試過程中遇到的問題及解決方案 34262065.2測試結(jié)果 3718259總結(jié) 4118259致謝 4318259參考文獻(xiàn) 4418259附錄 451引言1.1課題設(shè)計背景計算機自從1946年第一臺真正意義上的數(shù)字電子計算機ENIAC(ElectronicNumericalIntegratorAndComputer)的誕生以來，已經(jīng)經(jīng)歷了1854年－1890年、1890年－20世紀(jì)早期、20世紀(jì)中期、20世紀(jì)晚期－現(xiàn)在四個階段，每一個階段的發(fā)展都發(fā)生了質(zhì)與量的突飛猛進(jìn)。然而，計算機的發(fā)展只是代表了硬件的提升，對于軟件，操作系統(tǒng)的發(fā)展更加引人注目。操作系統(tǒng)（OperatingSystem，簡稱OS）是管理電腦硬件與軟件資源的程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)是控制其他程序運行，管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合。操作系統(tǒng)身負(fù)諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)的型態(tài)非常多樣，不同機器安裝的OS可從簡單到復(fù)雜，可從手機的嵌入式系統(tǒng)到超級電腦的大型操作系統(tǒng)。目前微機上常見的操作系統(tǒng)有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。操作系統(tǒng)的不斷提升對于計算機整體性能的提高有著至關(guān)重要的作用。操作系統(tǒng)對于各個方面的要求都不得不提到效率的問題，計算機系統(tǒng)的處理機調(diào)度便變得尤為重要。處理機調(diào)度的效率甚至可能成為提高計算機處理速度的瓶頸。處理機調(diào)度就是對系統(tǒng)的資源做出合理的分配，因而，提高處理機的調(diào)度算法也變得尤為重要。1.2目的和意義在多道程序設(shè)計系統(tǒng)中，內(nèi)存中有多道程序運行，他們相互爭奪處理機這一重要的資源。處理機調(diào)度就是從就緒隊列中，按照一定的算法選擇一個進(jìn)程并將處理機分配給它運行，以實現(xiàn)進(jìn)程并發(fā)地執(zhí)行。一般情況下，當(dāng)占用處理機的進(jìn)程因為某種請求得不到滿足而不得不放棄CPU進(jìn)入等待狀態(tài)時，或者當(dāng)時間片到，系統(tǒng)不得不將CPU分配給就緒隊列中另一進(jìn)程的時候，都要引起處理機調(diào)度。除此之外，進(jìn)程正常結(jié)束、中斷處理等也可能引起處理機的調(diào)度。因此，處理機調(diào)度是操作系統(tǒng)核心的重要組成部分，它的主要功能如下：記住進(jìn)程的狀態(tài)，如進(jìn)程名稱、指令計數(shù)器、程序狀態(tài)寄存器以及所有通用寄存器等現(xiàn)場信息，將這些信息記錄在相應(yīng)的進(jìn)程控制塊中；根據(jù)一定的算法，決定哪個進(jìn)程能獲得處理機，以及占用多長時間；收回處理機，即正在執(zhí)行的進(jìn)程因為時間片用完或因為某種原因不能再執(zhí)行的時候，保存該進(jìn)程的現(xiàn)場，并收回處理機。1.3調(diào)度算法發(fā)展過程調(diào)度算法[1]是根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法，例如，在批處理系統(tǒng)中，為了照顧為數(shù)眾多的段作業(yè)，應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法；又如在分時系統(tǒng)中，為了保證系統(tǒng)具有合理的響應(yīng)時間，應(yīng)當(dāng)采用輪轉(zhuǎn)法進(jìn)行調(diào)度。目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度；但也有些調(diào)度算法既可以用于作業(yè)調(diào)度，也可以用于進(jìn)程調(diào)度。各種調(diào)度算法都有其具有的優(yōu)點和缺點。因此，在這里便要對一種結(jié)合了多種算法的具有極強的適應(yīng)性的調(diào)度算法—基于優(yōu)先級的時間片調(diào)度算法作研究。1）FCFS（Firstcomefirstserve)，或者稱為FIFO算法，先來先處理。這個算法的優(yōu)點是簡單，實現(xiàn)容易，并且似乎公平；缺點在于短的任務(wù)有可能變的非常慢，因為其前面的任務(wù)占用很長時間，造成了平均響應(yīng)時間非常慢。

2）時間片輪詢算法，這是對FIFO算法的改進(jìn)，目的是改善短程序（運行時間短）的響應(yīng)時間，其方法就是周期性地進(jìn)行進(jìn)程切換。這個算法的關(guān)鍵點在于時間片的選擇，時間片過大，那么輪轉(zhuǎn)就越接近FIFO，如果太小，進(jìn)程切換的開銷大于執(zhí)行程序的開銷，從而降低了系統(tǒng)效率。因此選擇合適的時間片就非常重要。選擇時間片的兩個需要考慮的因素：一次進(jìn)程切換所使用的系統(tǒng)消耗以及我們能接受的整個系統(tǒng)消耗、系統(tǒng)運行的進(jìn)程數(shù)。時間片輪詢看上起非常公平，并且響應(yīng)時間非常好，然而時間片輪轉(zhuǎn)并不能保證系統(tǒng)的響應(yīng)時間總是比FIFO短，這很大程度上取決于時間片大小的選擇，以及這個大小與進(jìn)程運行時間的相互關(guān)系。

3）STCF算法（Shorttimetocompletefirst)，顧名思義就是短任務(wù)優(yōu)先算法。這種算法的核心就是所有的程序都有一個優(yōu)先級，短任務(wù)的優(yōu)先級比長任務(wù)的高，而OS總是安排優(yōu)先級高的進(jìn)程運行。STCF又分為兩類：非搶占式和搶占式。非搶占式STCF就是讓已經(jīng)在CPU上運行的程序執(zhí)行到結(jié)束或者阻塞，然后在所有的就緒進(jìn)程中選擇執(zhí)行時間最短的來執(zhí)行；而搶占式STCF就不是這樣，在每進(jìn)來一個新的進(jìn)程時，就對所有進(jìn)程（包括正在CPU上執(zhí)行的進(jìn)程）進(jìn)行檢查，誰的執(zhí)行時間短，就運行誰。STCF總是能提供最優(yōu)的響應(yīng)時間，然而它也有缺點，第一可能造成長任務(wù)的程序無法得到CPU時間而饑餓，因為OS總是優(yōu)先執(zhí)行短任務(wù)；其次，關(guān)鍵問題在于我們怎么知道程序的運行時間，怎么預(yù)測某個進(jìn)程需要的執(zhí)行時間？通常有兩個辦法：使用啟發(fā)式方法估算（例如根據(jù)程序大小估算），或者將程序執(zhí)行一遍后記錄其所用的CPU時間，在以后的執(zhí)行過程中就可以根據(jù)這個測量數(shù)據(jù)來進(jìn)行STCF調(diào)度。

4）優(yōu)先級調(diào)度，STCF遇到的問題是長任務(wù)的程序可能饑餓，那么優(yōu)先級調(diào)度算法可以通過給長任務(wù)的進(jìn)程更高的優(yōu)先級來解決這個問題；優(yōu)先級調(diào)度遇到的問題可能是短任務(wù)的進(jìn)程饑餓，這個可以通過動態(tài)調(diào)整優(yōu)先級來解決。實際上動態(tài)調(diào)整優(yōu)先級（稱為權(quán)值）+時間片輪詢的策略正是linux的進(jìn)程調(diào)度策略之一的SCHED_OTHER分時調(diào)度策略,它的調(diào)度過程如下：

（1）創(chuàng)建任務(wù)指定采用分時調(diào)度策略，并指定優(yōu)先級nice值(-20~19)。

（2）將根據(jù)每個任務(wù)的nice值確定在cpu上的執(zhí)行時間(counter)。

（3）如果沒有等待資源，則將該任務(wù)加入到就緒隊列中。

（4）調(diào)度程序遍歷就緒隊列中的任務(wù)，通過對每個任務(wù)動態(tài)優(yōu)先級的計算(counter+20-nice)結(jié)果，選擇計算結(jié)果最大的一個去運行，當(dāng)這個時間片用完后(counter減至0)或者主動放棄cpu時，該任務(wù)將被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。（5）此時調(diào)度程序重復(fù)上面計算過程，轉(zhuǎn)到第4步。

（6）當(dāng)調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計算所得的權(quán)值都為不大于0時，重復(fù)第2步。linux還有兩個實時進(jìn)程的調(diào)度策略：FIFO和RR,實時進(jìn)程會立即搶占非實時進(jìn)程。

5）顯然，沒有什么調(diào)度算法是毫無缺點的，因此現(xiàn)代OS通常都會采用混合調(diào)度算法。例如將不同的進(jìn)程分為幾個大類，每個大類有不同的優(yōu)先級，不同大類的進(jìn)程的調(diào)度取決于大類的優(yōu)先級，同一個大類的進(jìn)程采用時間片輪詢來保證公平性。

6）其他調(diào)度算法，保證調(diào)度算法保證每個進(jìn)程享用的CPU時間完全一樣；彩票調(diào)度算法是一種概率調(diào)度算法，通過給進(jìn)程“發(fā)彩票”的多少，來賦予不同進(jìn)程不同的調(diào)用時間，彩票調(diào)度算法的優(yōu)點是非常靈活，如果你給短任務(wù)發(fā)更多“彩票”，那么就類似STCF調(diào)度，如果給每個進(jìn)程一樣多的“彩票”，那么就類似保證調(diào)度；用戶公平調(diào)度算法，是按照每個用戶，而不是按照每個進(jìn)程來進(jìn)行公平分配CPU時間，這是為了防止貪婪用戶啟用了過多進(jìn)程導(dǎo)致系統(tǒng)效率降低甚至停頓。

7）實時系統(tǒng)的調(diào)度算法，實時系統(tǒng)需要考慮每個具體任務(wù)的響應(yīng)時間必須符合要求，在截止時間前完成。

（1）EDF調(diào)度算法，就是最早截止任務(wù)優(yōu)先（Earliestdeadlinefirst)算法，也就是讓最早截止的任務(wù)先做。當(dāng)新的任務(wù)過來時，如果它的截止時間更靠前，那么就讓新任務(wù)搶占正在執(zhí)行的任務(wù)。EDF算法其實是貪心算法的一種體現(xiàn)。如果一組任務(wù)可以被調(diào)度（也就是所有任務(wù)的截止時間在理論上都可以得到滿足），那么EDF可以滿足。如果一批任務(wù)不能全部滿足（全部在各自的截止時間前完成），那EDF滿足的任務(wù)數(shù)最多，這就是它最優(yōu)的體現(xiàn)。EDF其實就是搶占式的STCF，只不過將程序的執(zhí)行時間換成了截止時間。EDF的缺點在于需要對每個任務(wù)的截止時間做計算并動態(tài)調(diào)整優(yōu)先級，并且搶占任務(wù)也需要消耗系統(tǒng)資源。因此它的實際效果比理論效果差一點。

（2）RMS調(diào)度算法，EDF是動態(tài)調(diào)度算法，而RMS（ratemonotonicscheduling)算法是一種靜態(tài)最優(yōu)算法；該算法在進(jìn)行調(diào)度前先計算出所有任務(wù)的優(yōu)先級，然后按照計算出來的優(yōu)先級進(jìn)行調(diào)度，任務(wù)執(zhí)行中間既不接收新任務(wù)，也不進(jìn)行優(yōu)先級調(diào)整或者CPU搶占。因此它的優(yōu)點是系統(tǒng)消耗小，缺點就是不靈活了。對于RMS算法，關(guān)鍵點在于判斷一個任務(wù)組是否能被調(diào)度，這里有一個定律，如果一個系統(tǒng)的所有任務(wù)的CPU利用率都低于ln2，那么這些任務(wù)的截止時間均可以得到滿足，ln2約等于0.693147，也就是此時系統(tǒng)還剩下有30%的CPU時間。這個證明是Liu和Kayland在1973年給出的。1.4使用到的開發(fā)工具在本次課程設(shè)計中，我們選擇了C++語言作為我們所使用的開發(fā)語言，開發(fā)工具則選用了MicrosoftVisualC++6.0。MFC借助C++的優(yōu)勢為Windows開發(fā)開辟了一片新天地，同時也借助ApplicationWizzard使開發(fā)者擺脫離了那些每次都必寫基本代碼，借助ClassWizard和消息映射使開發(fā)者擺脫了定義消息處理時那種混亂和冗長的代碼段。更重要的是利用C++的封裝功能使開發(fā)者擺脫Windows中各種句柄的困擾，只需要面對C++中的對象，這樣一來使開發(fā)更接近開發(fā)語言而遠(yuǎn)離系統(tǒng)。正因為MFC是建立在C++的基礎(chǔ)上，所以我強調(diào)C/C++語言基礎(chǔ)對開發(fā)的重要性。利用C++的封裝性開發(fā)者可以更容易理解和操作各種窗口對象；利用C++的派生性開發(fā)者可以減少開發(fā)自定義窗口的時間和創(chuàng)造出可重用的代碼；利用虛擬性可以在必要時更好的控制窗口的活動。而且C++本身所具備的超越C語言的特性都可以使開發(fā)者編寫出更易用，更靈活的代碼。MicrosoftVisualC++6.0[2]：VisualC++6.0，簡稱VC或者VC6.0，是微軟推出的一款C++編譯器，將“高級語言”翻譯為“機器語言（低級語言）”的程序。VisualC++是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問世，VisualC++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。雖然微軟公司推出了VisualC++.NET(VisualC++7.0)，但它的應(yīng)用有很大的局限性，只適用于Windows2000、WindowsXP和WindowsNT4.0。所以實際中，更多的是以VisualC++6.0為平臺。1.4.1特色三級標(biāo)題也不要縮進(jìn)；下同。三級標(biāo)題也不要縮進(jìn)；下同。VisualC++6.0由Microsoft開發(fā),它不僅是一個C++編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrateddevelopmentenvironment，IDE）。VisualC++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lassWizard等開發(fā)工具。這些組件通過一個名為DeveloperStudio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。VisualC++是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問世，VisualC++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。雖然微軟公司推出了VisualC++.NET(VisualC++7.0)，但它的應(yīng)用的很大的局限性，只適用于Windows2000,WindowsXP和WindowsNT4.0。所以實際中，更多的是以VisualC++6.0為平臺。VisualC++6.0以擁有“語法高亮”，自動編譯功能以及高級除錯功能而著稱。比如，它允許用戶進(jìn)行遠(yuǎn)程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及創(chuàng)建預(yù)編譯頭文件(stdafx.h)、最小重建功能及累加連結(jié)(link)著稱。這些特征明顯縮短程序編輯、編譯及連結(jié)的時間花費，在大型軟件計劃上尤其顯著。1.4.2缺點由于C++是由C語言發(fā)展起來的，也支持C語言的編譯。6.0版本是使用最多的版本，很經(jīng)典。最大的缺點是對于模版的支持比較差?，F(xiàn)在最新補丁為SP6，推薦安裝，否則易出現(xiàn)編譯時假死狀態(tài)。僅支持Windows操作系統(tǒng)。目前發(fā)現(xiàn)與windows7兼容性不好，安裝成功后可能會出現(xiàn)無法打開cpp文件的現(xiàn)象?，F(xiàn)在的最新版C++編譯器集合在MicrosoftVisualStudio2010軟件里面，包含C++，Visualbasic，C#，J#，.net。等,其中，VC開發(fā)環(huán)境的版本已經(jīng)升級至MicrosoftVisualC++2010，對C++的支持更加全面穩(wěn)定，建議電腦性能好的可以使用此版本。目前微軟公司已經(jīng)停止對VC++6.0系列產(chǎn)品的維護(hù)，繼而轉(zhuǎn)向.NET平臺環(huán)境，新的MS2008、MS2010等將更符合新世紀(jì)通用開發(fā)需求。不要隨便加空行?。?需求分析2.1需求背景無論是在批處理系統(tǒng)還是分時系統(tǒng)中，用戶進(jìn)程數(shù)一般都多于處理機數(shù)、這將導(dǎo)致它們互相爭奪處理機。另外，系統(tǒng)進(jìn)程也同樣需要使用處理機。這就要求進(jìn)程調(diào)度程序按一定的策略，動態(tài)地把處理機分配給處于就緒隊列中的某一個進(jìn)程，以使之執(zhí)行。眾所周知，現(xiàn)在的操作系統(tǒng)都是多任務(wù)的操作系統(tǒng)，實際上并不是真正同時運行多個進(jìn)程，只不過是進(jìn)程在頻繁切換，而這種切換用戶基本上感覺不到，進(jìn)程調(diào)度就是操作系統(tǒng)來完成的。當(dāng)以下情況出現(xiàn)時需要操作系統(tǒng)來調(diào)度進(jìn)程：時間片到，即每個進(jìn)程所分配的時間片用完后，要跳轉(zhuǎn)到調(diào)度程序；占用CPU的當(dāng)前運行進(jìn)程提出I/O操作，發(fā)起對內(nèi)核的系統(tǒng)調(diào)用時，在系統(tǒng)調(diào)用結(jié)束后,跳轉(zhuǎn)到調(diào)度程序；當(dāng)前運行進(jìn)程對所有內(nèi)核系統(tǒng)調(diào)用的結(jié)束時都要跳轉(zhuǎn)到調(diào)度程序，根據(jù)當(dāng)前的調(diào)度信息來決定下一個可以占用CPU的進(jìn)程。然而進(jìn)程調(diào)度的實現(xiàn)需要一系列的算法。如短作業(yè)優(yōu)先調(diào)度算法，但該算法僅照顧了短作業(yè)而忽略了長進(jìn)程，而且如果并未指明進(jìn)程的長度，則短進(jìn)程優(yōu)先和基于進(jìn)程長度的搶占式調(diào)度算法都將無法使用。在早期的時間片輪轉(zhuǎn)算法[3]中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。但該算法存在未考慮優(yōu)先級的不足。而基于時間片的高優(yōu)先級調(diào)度算法則不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各種類型進(jìn)程的需要。本次試驗就是依據(jù)該算法的原理進(jìn)行設(shè)計的。首先設(shè)置多個就緒隊列并為各個隊列賦予不同的優(yōu)先級，第一個隊列的優(yōu)先級最高，依次降低；當(dāng)新進(jìn)程進(jìn)入內(nèi)存后將其放入第一隊列的隊尾，然后再按先來先服務(wù)的原則排隊等待調(diào)度；僅當(dāng)?shù)谝粋€隊列為空閑時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運行。根據(jù)分析，得到如下結(jié)果：（1）系統(tǒng)組成系統(tǒng)由虛擬內(nèi)核(VKernel)、命令解釋程序(Commander)、用戶程序（Application）、編譯器（Compiler）四部分組成。VKernel首先運行，并常駐內(nèi)存。Kernel啟動后，創(chuàng)建Commander進(jìn)程。根據(jù)用戶請求創(chuàng)建多個Application進(jìn)程。Kernel負(fù)責(zé)維護(hù)6個數(shù)據(jù)結(jié)構(gòu)，包括時間(Time),處理器狀態(tài)(CPUstate),進(jìn)程表(PCBTable),就緒隊列(ReadyState),等待隊列(BlockedState),運行進(jìn)程（RunningState）。Time是系統(tǒng)時間片。CPUstate應(yīng)包括程序計數(shù)器PC,累加器A、B,狀態(tài)寄存器F的值。PCBTable的每一項是一個進(jìn)程的進(jìn)程控制塊(PCB)。Commander程序、Application程序是用下列CPU虛擬指令書寫的程序：#include<stdio.h>/*定義頭文件（本程序自帶的）*#include<stdlib.h>#include<string.h>#include<math.h>typedefstructnode/*進(jìn)程節(jié)點信息*/{charname[20];/*進(jìn)程的名字*/intprio;/*進(jìn)程的優(yōu)先級*/intround;/*分配CPU的時間片*/intcputime;/*CPU執(zhí)行時間*/intneedtime;/*進(jìn)程執(zhí)行所需要的時間*/charstate;/*進(jìn)程的狀態(tài)，W--就緒態(tài)，R--執(zhí)行態(tài)，F(xiàn)--完成態(tài)*/intcount;/*記錄執(zhí)行的次數(shù)*/structnode*next;/*鏈表指針*/}PCB;typedefstructQueue/*多級就緒隊列節(jié)點信息*/{PCB*LinkPCB;/*就緒隊列中的進(jìn)程隊列指針*/intprio;/*本就緒隊列的優(yōu)先級*/intround;/*本就緒隊列所分配的時間片*/structQueue*next;/*指向下一個就緒隊列的鏈表指針*/}ReadyQueue;PCB*run=NULL,*finish=NULL;/*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/ReadyQueue*Head=NULL;/*定義第一個就緒隊列*/intnum;/*進(jìn)程個數(shù)*/intReadyNum;/*就緒隊列個數(shù)*/voidOutput();/*進(jìn)程信息輸出函數(shù)*/voidInsertFinish(PCB*in);/*將進(jìn)程插入到完成隊列尾部*/voidInsertPrio(ReadyQueue*in);/*創(chuàng)建就緒隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/voidPrioCreate();/*創(chuàng)建就緒隊列輸入函數(shù)*/voidGetFirst(ReadyQueue*queue);/*取得某一個就緒隊列中的隊頭進(jìn)程*/voidInsertLast(PCB*in,ReadyQueue*queue);/*將進(jìn)程插入到就緒隊列尾部*/voidProcessCreate();/*進(jìn)程創(chuàng)建函數(shù)*/voidRoundRun(ReadyQueue*timechip);/*時間片輪轉(zhuǎn)調(diào)度算法*/voidMultiDispatch();/*多級調(diào)度算法，每次執(zhí)行一個時間片*/（2）命令解釋程序命令解釋程序從標(biāo)準(zhǔn)輸入重復(fù)讀入用戶命令,然后以消息形式發(fā)送給內(nèi)核。命令解釋程序處理的命令由設(shè)計者定義并實現(xiàn)。（3）編譯器編譯器把虛擬指令和虛擬系統(tǒng)調(diào)用編譯為可執(zhí)行字節(jié)碼?？蓤?zhí)行字節(jié)碼由內(nèi)核解釋執(zhí)行。2.2課程設(shè)計任務(wù)1）設(shè)計進(jìn)程控制塊；2）設(shè)計優(yōu)先級對應(yīng)的時間片；3）實現(xiàn)高優(yōu)先級非搶占式調(diào)度算法；4）實現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法；5）實現(xiàn)基于高優(yōu)先級的時間片輪轉(zhuǎn)算法。2.2.1課題目的三級標(biāo)題也不要縮進(jìn)；下同。三級標(biāo)題也不要縮進(jìn)；下同。1)理解進(jìn)程調(diào)度相關(guān)理論；2)掌握時間片調(diào)度原理；3)掌握高優(yōu)先級調(diào)度原理。2.2.2課題內(nèi)容1)設(shè)計進(jìn)程控制塊；2)設(shè)計多個進(jìn)程隊列；3)設(shè)計多個進(jìn)程；4)動態(tài)生成時間片、執(zhí)行時間和優(yōu)先級；5)設(shè)計基于時間片的多優(yōu)先級調(diào)度算法；2.2.3測試要求要求輸出進(jìn)程名以及與其對應(yīng)的優(yōu)先級、輪數(shù)、CPU時間、需要時間、進(jìn)程狀態(tài)、計數(shù)器，可執(zhí)行文件的輸出格式如下：進(jìn)程名優(yōu)先級輪數(shù)CPU時間需要時間進(jìn)程狀態(tài)計數(shù)器Jc22802W0Jc11801R02.3課程設(shè)計要求1)編寫程序完成課題內(nèi)容；2)在課程設(shè)計報告中畫出基于時間片的高優(yōu)先級調(diào)度函數(shù)流程圖；3)撰寫課程設(shè)計報告，并參加答辯。2.4課程設(shè)計思想FCFS、SJF和優(yōu)先級調(diào)度算法僅對某一類作業(yè)有利，相比之下，它能全面滿足不同類型作業(yè)的需求，較好實現(xiàn)公平性與資源利用率之間的平衡。對交互型作業(yè)，由于通常較短，這些作業(yè)在第一隊列規(guī)定的時間片內(nèi)完成，可使用戶感到滿意；對短批作業(yè)，開始時在第一隊列中執(zhí)行一個時間片就可完成，便可與交互型作業(yè)一樣獲得快速晌應(yīng)，否則通常也僅需在第二、第三隊列中各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍較短；對長批作業(yè)，它們依次在第一至第n個隊列中輪番執(zhí)行，不必?fù)?dān)心長時間得不到處理。

不要隨便加空行?。?！3概要設(shè)計3.1課程設(shè)計所用方法及其原理3.1.1優(yōu)先級優(yōu)先級[4]體現(xiàn)了進(jìn)程的重要程度或緊迫程度，在大多數(shù)現(xiàn)代操作系統(tǒng)中，都采用了優(yōu)先級調(diào)度策略。優(yōu)先級從小到大（如0-127），0優(yōu)先級最低，127最高。在本實驗中，要求優(yōu)先級為0-8。3.1.2基于時間片調(diào)度 將所有的就緒進(jìn)程按照先來先服務(wù)[5]的原則，排成一個隊列，每次調(diào)度時，將CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序把此進(jìn)程終止，把該進(jìn)程放到隊尾。 在調(diào)度過程中，需要通過時間函數(shù)檢測進(jìn)程的執(zhí)行時間，當(dāng)該進(jìn)程執(zhí)行時間≥時間片大小時，進(jìn)行調(diào)度。3.1.3高優(yōu)先級調(diào)度 優(yōu)先級高的進(jìn)程優(yōu)先得到cpu，等該進(jìn)程執(zhí)行完畢后，另外的進(jìn)程才能執(zhí)行。3.1.4基于時間片的高優(yōu)先級調(diào)度 時間片和優(yōu)先級調(diào)度仔細(xì)檢查縮進(jìn)！的結(jié)合，在系統(tǒng)中，每個優(yōu)先級對應(yīng)一個就緒隊列，在每個就緒隊列內(nèi)，采用時間片調(diào)度。當(dāng)高優(yōu)先級進(jìn)程隊列調(diào)度完成后，才能轉(zhuǎn)入更低優(yōu)先級的就緒隊列調(diào)度。仔細(xì)檢查縮進(jìn)！不要隨便加空行?。?！3.2主要的數(shù)據(jù)結(jié)構(gòu)表3.1PCB的數(shù)據(jù)結(jié)構(gòu)字段名類型寬度別名name字符型10進(jìn)出名prio數(shù)值型1進(jìn)程的優(yōu)先級round日期時間型8分配CPU的時間片needtime日期時間型8進(jìn)程執(zhí)行所需要的時間state字符型10進(jìn)程的狀態(tài)count數(shù)值型10記錄執(zhí)行的次數(shù)next指針型100鏈表指針不要隨便加空行！??！3.3課題設(shè)計的流程圖圖3.1主要數(shù)據(jù)流程圖4詳細(xì)設(shè)計4.1設(shè)計進(jìn)程控制塊為了描述和控制進(jìn)程的運行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)，即進(jìn)程控制塊【6】他的作用是使一個在多道程序環(huán)境下不能獨立運行的程序（含數(shù)據(jù)），成為一個能獨立運行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。在進(jìn)程的整個生命周期中，系統(tǒng)總是通過PCB而不是任何別的什么而感知到該進(jìn)程的存在的。PCB是進(jìn)程存在的唯一標(biāo)志。4.1.1進(jìn)程控制塊的內(nèi)容1）進(jìn)程標(biāo)識符[7]：進(jìn)程標(biāo)識符用于惟一的標(biāo)識一個進(jìn)程。一個進(jìn)程通常有兩種標(biāo)識符：內(nèi)部標(biāo)識符和外部標(biāo)識符。內(nèi)部標(biāo)識符指在所有的操作系統(tǒng)中，都為每一個進(jìn)程賦予了一個惟一的標(biāo)識符，他通常是一個進(jìn)程的符號。設(shè)置內(nèi)部標(biāo)識符主要是為了方便系統(tǒng)使用。外部標(biāo)識符是由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶（進(jìn)程）在訪問該進(jìn)程時使用。為了描述進(jìn)程的家族關(guān)系，還應(yīng)設(shè)置父進(jìn)程標(biāo)識和子進(jìn)程標(biāo)識。此外，還可設(shè)置用戶標(biāo)識，以指示擁有該進(jìn)程的用戶。2）處理機狀態(tài)[8]：主要是由處理機的各種寄存器中的內(nèi)容組成。處理機在運行時，許多信息都放在寄存器中。當(dāng)處理機被中斷時，所有這些信息都必須保存在PCB中，以便在該進(jìn)程重新執(zhí)行時，能從斷電繼續(xù)執(zhí)行。這些寄存器包括：（1）通用寄存器，又稱為用戶可視寄存器，它們是用戶進(jìn)程可以訪問的，用于在暫存信息，在大多數(shù)處理機中，有8~32個通用寄存器，在RISC結(jié)構(gòu)的計算機中科超過100個；（2）指令計數(shù)器，其中存放訪問的下一條指令的地址；（3）程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條形碼、執(zhí)行方式中斷屏蔽標(biāo)志等。（4）用戶棧指針，指每個用戶進(jìn)程都有一個或若干個與之相關(guān)的系統(tǒng)棧，用于存放過過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址，棧指針指向該棧的棧頂。3）進(jìn)程調(diào)度信息[9]：在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的信息，包括：（1）進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和兌換的依據(jù)；（2）進(jìn)程優(yōu)先級，用于描述進(jìn)程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進(jìn)程應(yīng)優(yōu)先獲得處理機；（3）進(jìn)程調(diào)度所需的其它信息，他們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時間總和、進(jìn)程已執(zhí)行的時間總和等；（4）事件，指進(jìn)程由執(zhí)行狀態(tài)改為阻塞狀態(tài)所等待發(fā)生的事件，即阻塞原因。4）進(jìn)程控制信息：進(jìn)程控制信息包括程序和數(shù)據(jù)地址的地址，只進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存底（首）址，以便再調(diào)度到該進(jìn)程執(zhí)行時，能從CPU中找到其程序和數(shù)據(jù)；進(jìn)程同步和通信機制，指實現(xiàn)進(jìn)程同步和進(jìn)程通信時必須的機制，如信息隊列指針、信號量等，他們可能全部或的放在PCB中；資源清單，即一張列出了除CPU以外的、進(jìn)程所需的全部資源即已經(jīng)分配到該進(jìn)程的資源清單；鏈接指針，它給出了本進(jìn)程（PCB）所在隊列中的下一個進(jìn)程的PCB的首地址。4.1.2進(jìn)程名字name、進(jìn)程的優(yōu)先級prio、分配CPU的時間片round、進(jìn)程執(zhí)行所需要的時間needtime、進(jìn)程的狀態(tài)state、記錄執(zhí)行的次數(shù)count、鏈表指針next。4.1.3進(jìn)程控制塊的格式進(jìn)程名指針要求運行時間已運行時間狀態(tài)圖4.1進(jìn)程控制塊格式其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，如Q1、Q2等。指針——進(jìn)程按順序排成循環(huán)鏈隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程的指針指出第一個進(jìn)程的進(jìn)程控制塊首地址。要求運行時間——假設(shè)進(jìn)程需要運行的單位時間數(shù)。已運行時間——假設(shè)進(jìn)程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“W”表示。當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“F”表示，當(dāng)進(jìn)程運行時，它的狀態(tài)為“執(zhí)行”，用“R”表示。4.2進(jìn)程的三種基本狀態(tài)1）就緒（ready）狀態(tài)分配到除CPU以外所有必要的資源以后，只要在獲得CPU，便可立即執(zhí)行，進(jìn)程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。2）執(zhí)行狀態(tài)進(jìn)程已獲得CPU，其程序正在執(zhí)行。在單機處理系統(tǒng)中，只有一個進(jìn)程處于執(zhí)行狀態(tài)；在多處理機系統(tǒng)中，則有多個進(jìn)程處于執(zhí)行狀態(tài)。3）阻塞狀態(tài)正在執(zhí)行的進(jìn)程由于發(fā)生某個時間而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)或者封鎖狀態(tài)。致使進(jìn)程阻塞的典型事件有：強求I/O，申請緩存空間等。通常將這種處于阻塞狀態(tài)的進(jìn)程也排成一個隊列。有的系統(tǒng)則根據(jù)阻塞原因的不同而把處于阻塞狀態(tài)的進(jìn)程拍成多個隊列。處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序為之分配的了處理機之后，該進(jìn)程便可執(zhí)行，相應(yīng)的，它就由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。正在執(zhí)行的進(jìn)程也成為當(dāng)前進(jìn)程，如果因分配給它的時間片已完而被暫停執(zhí)行時，該進(jìn)程便由執(zhí)行狀態(tài)又回復(fù)到就緒狀態(tài)；如果因發(fā)生某件事而使進(jìn)程的執(zhí)行受阻（例如，進(jìn)程請求訪問某臨界資源，而該資源正在被其他進(jìn)程訪問時），使之無法繼續(xù)執(zhí)行，該進(jìn)程將由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。如圖，表示了進(jìn)程三種基本狀態(tài)以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系。4.3優(yōu)先級4.3.1優(yōu)先級簡介是指在進(jìn)程創(chuàng)建時先確定一個初始優(yōu)先數(shù)，以后在進(jìn)程運行中隨著進(jìn)程特性的改變不斷修改優(yōu)先數(shù)，這樣，由于開始優(yōu)先數(shù)很低而得不到CPU的進(jìn)程，就能因為等待時間的增長而優(yōu)先數(shù)變?yōu)樽罡叨玫紺PU運行。4.3.2優(yōu)先權(quán)調(diào)度算法的類型1）非搶占式優(yōu)先權(quán)算法：在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可某些對實時性要求不嚴(yán)的實時系統(tǒng)中。2）搶占式優(yōu)先權(quán)調(diào)度算法：系統(tǒng)同樣把處理機分配給優(yōu)先權(quán)最高的進(jìn)程,使之執(zhí)行。但在其執(zhí)行期間,只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程,進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行,重新將處理機分配給新到的優(yōu)先權(quán)最高的進(jìn)程。這種搶占式的優(yōu)先權(quán)調(diào)度算法,能更好地滿足緊迫作業(yè)的要求,常用于要求比較嚴(yán)格的實時系統(tǒng)中,以及對性能要求較高的批處理和分時系統(tǒng)中。4.3.3優(yōu)先權(quán)的類型1）靜態(tài)優(yōu)先權(quán)[10]：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如,0~7，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異:有的系統(tǒng)用“0”表示最高優(yōu)先權(quán),當(dāng)數(shù)值愈大時,其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有三個方面:（1）進(jìn)程類型(系統(tǒng)進(jìn)程/用戶進(jìn)程)（2）進(jìn)程對資源的需求(需求量的大小)（3）用戶要求(用戶進(jìn)程緊迫程度)2)動態(tài)優(yōu)先權(quán):動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定,在就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊列的進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法。4.3.4優(yōu)先權(quán)的變化規(guī)律由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間,故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。4.3.5優(yōu)先級的算法1)設(shè)定系統(tǒng)中有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊（PCB）表示，進(jìn)程隊列采用鏈表數(shù)據(jù)結(jié)構(gòu)。2)進(jìn)程控制塊包含如下信息：進(jìn)程名、優(yōu)先數(shù)、需要運行時間、已用CPU時間、進(jìn)程狀態(tài)等等等。3)在每次運行設(shè)計的處理調(diào)度程序之前，由終端輸入五個進(jìn)程的“優(yōu)先數(shù)”和“要求運行時間”。4)進(jìn)程的優(yōu)先數(shù)及需要的運行時間人為地指定.進(jìn)程的運行時間以時間片為單位進(jìn)行計算。5)采用優(yōu)先權(quán)調(diào)度算法，將五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成就緒隊列。用頭指針指出隊列首進(jìn)程，隊列采用鏈表結(jié)構(gòu)。6)處理機調(diào)度總是選隊列首進(jìn)程運行。采用動態(tài)優(yōu)先數(shù)辦法，進(jìn)程每運行一次優(yōu)先數(shù)“1”，同時將已運行時間加“1”。7)進(jìn)程運行一次后，若要求運行時間不等于已運行時間，則再將它加入就緒隊列；否則將其狀態(tài)置為“結(jié)束”,且退出就緒隊列。8)“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面6，7步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。9)在設(shè)計的程序中有輸入語句，輸入5個進(jìn)程的“優(yōu)先數(shù)”和“要求運行時間”，也有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名、運行一次后隊列的變化，以及結(jié)束進(jìn)程的進(jìn)程名。10)最后，為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，運行并調(diào)試所設(shè)計的程序，顯示或打印出逐次被選中進(jìn)程的進(jìn)程名及其進(jìn)程控制塊的動態(tài)變化過程。4.3.6最高優(yōu)先級優(yōu)先調(diào)度算法流程圖開始開始初始化PCB，輸入進(jìn)程信息各進(jìn)程按優(yōu)先數(shù)從高到低排列就緒隊列是否為空結(jié)束運行進(jìn)程已占用CPU時間已達(dá)到所需的運行時間使運行進(jìn)程的優(yōu)先數(shù)減1，把運行進(jìn)程插入就緒隊列進(jìn)程完成，撤銷該進(jìn)程時間片到，運行進(jìn)程已占用了CPU時間+1N已達(dá)到未達(dá)到就緒隊列首進(jìn)程投入運行圖4.3最高優(yōu)先級優(yōu)先調(diào)度算法流程圖4.4時間片輪轉(zhuǎn)算法4.4.1時間片輪轉(zhuǎn)法的基本原理系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。此實驗中時間片的單位定義為100ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中的對手進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。4.4.2時間片輪轉(zhuǎn)算法描述1）設(shè)系統(tǒng)有10個進(jìn)程，每個進(jìn)程用一個進(jìn)程控制塊PCB來代表。2）為每個進(jìn)程任意確定一個要求運行時間。3）按照進(jìn)程輸入的先后順序排成一個隊列。再設(shè)一個隊首指針指向第一個到達(dá)進(jìn)程的首址。4）執(zhí)行處理機調(diào)度時，開始選擇隊首的第一個進(jìn)程運行。另外，再設(shè)一個當(dāng)前運行進(jìn)程的指針，指向當(dāng)前正在運行的進(jìn)程。5）考慮到代碼的可重用性，輪轉(zhuǎn)法調(diào)度程序和最高優(yōu)先級優(yōu)先調(diào)度是調(diào)用同一個?？爝M(jìn)行輸出注:由于輪轉(zhuǎn)法調(diào)度程序和最高優(yōu)先級優(yōu)先調(diào)度是調(diào)用同一個模快進(jìn)行輸出,所以在時間輪轉(zhuǎn)法調(diào)度算法的進(jìn)程中,依然顯示上述所定義的優(yōu)先級數(shù)。6）進(jìn)程運行一次后，以后的調(diào)度則將當(dāng)前指針依此下移一個位置，指向下一個進(jìn)程，即調(diào)整當(dāng)前運行指針指向該進(jìn)程的鏈接指針?biāo)高M(jìn)程，以指示應(yīng)運行進(jìn)程。同時還應(yīng)采用計數(shù)器來判斷該進(jìn)程的要求運行時間是否等于已運行時間。若不等，則等待下一輪的運行，但此時該進(jìn)程應(yīng)插到代執(zhí)行隊列的尾部，否則將該進(jìn)程的狀態(tài)置為完成態(tài)F，并退出執(zhí)行隊列進(jìn)入完成隊列。7）若就緒隊列不空，則重復(fù)上述的5）和6）步驟直到所有的進(jìn)程都運行完為止。8）在所設(shè)計的調(diào)度程序中，包含顯示或打印語句。顯示或打印每次選中的進(jìn)程的名稱、所需運行的時間、輪數(shù)、cpu時間、運行一次后進(jìn)程所處的狀態(tài)以及計數(shù)器的變化情況。4.4.31）在開始頁面用戶可輸入進(jìn)程名，給出時間片的大小和每個進(jìn)程的服務(wù)時間。2）每運行一次，給進(jìn)程的服務(wù)時間減去一個時間片大小排到隊尾，顯示一個時間片后的新隊列。3）直到所有的進(jìn)程都服務(wù)完。4.4.4時間片的工作流程時間片輪轉(zhuǎn)的原則是系統(tǒng)將所有的就緒進(jìn)程按照先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配對手進(jìn)程，并令其執(zhí)行一個時間片，當(dāng)執(zhí)行完時，有一個計時器發(fā)出時鐘中斷請求，該進(jìn)程停止，并被送到就緒隊列的末尾，然后再把處理機分配就緒隊列的隊列進(jìn)程，同時也讓它執(zhí)行一個時間片。根據(jù)時間片輪轉(zhuǎn)調(diào)度算法并結(jié)合本實驗，分析進(jìn)程運行情況，得到如下圖所示的時間軸：不要隨便加空行?。。?1234567891112141618200123456789111214161820A1B1C1D1E1F1C2G1H1D2I1A0B0C0D0E0F0G0H0I0J0222426283032343537394143J1E2F2G2H2I2J2E3F3G3H3I3J3G4H4I4J4I5J545464850525355圖4.4進(jìn)程運行情況不要隨便加空行?。。?.4.5時間片輪轉(zhuǎn)調(diào)度流程圖YYN開始初始化PCB，輸入進(jìn)程信息各進(jìn)程按輸入順序插入到隊列就緒隊列是否為空結(jié)束分配時間片，運行首進(jìn)程計數(shù)器計數(shù)，運行時間逐漸增加，所需時間逐漸減少運行進(jìn)程已占用CPU時間已達(dá)到所需的運行時間已達(dá)到進(jìn)程完成，撤銷該進(jìn)程并將插到完成隊列把運行進(jìn)程插入到隊尾未達(dá)到圖4.5時間片輪轉(zhuǎn)法調(diào)度算法流程圖4.5多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法是一種CPU處理機調(diào)度算法，UNIX操作系統(tǒng)采取的便是這種調(diào)度算法。多級反饋隊列調(diào)度算法不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各類進(jìn)程的需要，因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。4.5.1多級反饋隊列調(diào)度算法原理1）設(shè)有Ｋ個隊列，其中各個隊列對于處理機的優(yōu)先級是不一樣的，也就是說位于各個隊列中的作業(yè)(進(jìn)程)的優(yōu)先級也是不一樣的。一般來說，第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先級逐個降低。2）對于某個特定的隊列來說，里面是遵循時間片輪轉(zhuǎn)法。也就是說，位于隊列Ｋ中有N個作業(yè)，它們的運行時間是通過Ｋ這個隊列所設(shè)定的時間片來確定的（為了便于理解，我們也可以認(rèn)為特定隊列中的作業(yè)的優(yōu)先級是按照FCFS來調(diào)度的）。3）各個隊列的時間片是一樣的嗎？不一樣，這就是該算法設(shè)計的精妙之處。各個隊列的時間片是隨著優(yōu)先級的增加而減少的，也就是說，優(yōu)先級越高的隊列中它的時間片就越短。例如，第二個隊列的時間片要比第一個隊列的時間片要長一倍，……，最后一個隊列(優(yōu)先級最低的隊列)的時間片一般很大。下圖是多級反饋隊列算法的示意。圖4.6多級反饋隊列調(diào)度算法4.5.2多級反饋隊列調(diào)度算法描述1）設(shè)置多個就緒隊列，并給隊列賦予不同的優(yōu)先級數(shù)，第一個最高，依次遞減。2）賦予各個隊列中進(jìn)程執(zhí)行時間片的大小，優(yōu)先級越高的隊列，時間片越小。3）當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將其放入一個對列末尾，如果在一個時間片結(jié)束時尚未完成，將其轉(zhuǎn)入第二隊列末尾。4）當(dāng)一個進(jìn)程從一個對列移至第n個隊列后，便在第n個隊列中采用時間片輪轉(zhuǎn)執(zhí)行完。5）僅當(dāng)時間片空閑時，才調(diào)度第二個隊列中的進(jìn)程。(1~i-1)空閑時，才調(diào)度i，如果處理機正在第i隊列中運行，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列，則新進(jìn)程搶占處理機，將正在運行的進(jìn)程放入第i隊列隊尾，將處理機分給新進(jìn)程。4.5.3多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。1）終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多數(shù)屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。2）短批處理作業(yè)用戶。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一對列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二隊列和第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。3）長批處理作業(yè)用戶。對于長作業(yè)它將依次在第1,2，…，k個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。4.5.4多級反饋隊列調(diào)度算法的運作1)現(xiàn)在有10個作業(yè)JC1，JC2，JC3，JC4，JC5，JC6，JC7，JC8，JC9，JC10，分別用A，B，C，D，E，F(xiàn)，G，H，I，J表示，分別在0,1,2,3,4,5,6,7,8,9時刻到達(dá)，所需要的CPU時間片分別為1,2,3,4,5,6,7,8,9,10。（1）時刻0：A到達(dá)。運行1個時間片，完成執(zhí)行，調(diào)入完成隊列，此時B到達(dá)。（2）時刻1：B到達(dá)。運行了1個時間片后，C到達(dá)。（3）時刻2：C到達(dá)。由于時間片仍然由B掌控，于是等待。B在運行了1個時間片后，已經(jīng)完成2個時間片的限制，加入完成隊列隊尾，現(xiàn)在處理機分配給C。（4）時刻3：D到達(dá)。由于時間片仍然由C掌控，于是等待。C在運行了1個時間片后，E到達(dá)。（5）時刻4：E到達(dá)。由于時間片仍然由C掌控，于是等待。C在運行了1個時間片后，時間片用完，置于等待，處理機分配給D，F(xiàn)到達(dá)。（6）時刻5：F到達(dá)。由于時間片由D掌控，于是等待。D在運行了1個時間片后，G到達(dá)。（7）時刻6：G到達(dá)。由于時間片由D掌控，于是等待。D在運行了1個時間片后，時間片用完，置于等待，處理機分配給E，H到達(dá)。（8）時刻7：H到達(dá)。由于時間片由E掌控，于是等待。E在運行了1個時間片后，I到達(dá)。（9）時刻8：I到達(dá)。由于時間片由E掌控，于是等待。E在運行了1個時間片后，時間片用完，置于等待，處理機分配給F，J到達(dá)。（10）時刻9：J到達(dá)。由于時間片由F掌控，于是等待。F在運行了2個時間片后，時間片用完，置于等待，處理機分配給C。（11）時刻11。C運行了1個時間片后，完成執(zhí)行，調(diào)入完成隊列隊尾，處理機分配給G。（12）時刻12。G運行了2個時間片后，時間片用完，于是等待，處理機分配給H。（13）時刻14。H運行了2個時間片后，時間片用完，于是等待，處理機分配給D。（14）時刻16。D運行了2個時間片后，完成執(zhí)行，調(diào)入完成隊列隊尾，處理機分配給I。（15）時刻18。I運行了2個時間片后，時間片用完，于是等待，處理機分配給J。（16）時刻20。J運行了2個時間片后，時間片用完，于是等待，處理機分配給E。（17）時刻22。E運行了2個時間片后，時間片用完，于是等待，處理機分配給F。（18）時刻24。F運行了2個時間片后，時間片用完，于是等待，處理機分配給G。(19)時刻26。G運行了2個時間片后，時間片用完，于是等待，處理機分配給H。(20)時刻28。H運行了2個時間片后，時間片用完，于是等待，處理機分配給I。(21)時刻30。I運行了2個時間片后，時間片用完，于是等待，處理機分配給J。(22)時刻32。J運行了2個時間片后，時間片用完，于是等待，處理機分配給E。(23)時刻34。E運行了1個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，處理機分配給F。(24)時刻35。F運行了2個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，處理機分配給G。(25)時刻37。G運行了2個時間片后，時間片用完，于是等待，處理機分配給H。(26)時刻39。H運行了2個時間片后，時間片用完，于是等待，處理機分配給I。(27)時刻41。I運行了2個時間片后，時間片用完，于是等待，處理機分配給J。(28)時刻43。J運行了2個時間片后，時間片用完，于是等待，處理機分配給G。(29)時刻45。G運行了1個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，處理機分配給H。(30)時刻46。H運行了2個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，處理機分配給I。(31)時刻48。I運行了2個時間片后，時間片用完，于是等待，處理機分配給J。(32)時刻50。J運行了2個時間片后，時間片用完，于是等待，處理機分配給I。(33)時刻52。I運行了1個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，處理機分配給J。(34)時刻53。J運行了2個時間片后，執(zhí)行完成，調(diào)入完成隊列隊尾，算法完畢。進(jìn)程運行情況如下圖序號字體不對。序號字體不對。圖4.7進(jìn)程運行情況5調(diào)試與操作說明5.1調(diào)試過程中遇到的問題及解決方案1）一開始執(zhí)行的結(jié)果都是左對齊，無法居中顯示，如下圖顯示圖5.1進(jìn)程運行結(jié)果一原因：經(jīng)檢查程序發(fā)現(xiàn)語句printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);設(shè)置有錯誤。解決方案：將代碼改為printf("%3s\t%5d\t%3d\t%4d\t%4d\t\t%4c\t\t%3d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);結(jié)果如下圖所示：圖5.2進(jìn)程運行結(jié)果二2）調(diào)試程序發(fā)現(xiàn)進(jìn)程所需時間≤8，一旦大于8優(yōu)先級值則出現(xiàn)負(fù)值，如下圖所示：圖5.3進(jìn)程運行結(jié)果三原因：原代碼語句tmp->prio=8-tmp->round使用減法運算解決方案：改為tmp->prio=tmp->round%9，此時輸入下圖數(shù)據(jù)，運行成功。圖5.4進(jìn)程運行結(jié)果四5.2測試結(jié)果1)將所編寫完成的代碼進(jìn)行編譯，檢測代碼是否存在錯誤，若存在錯誤則進(jìn)行代碼的修改；否則執(zhí)行編譯操作，編譯完成后即可點擊執(zhí)行按鈕，彈出可執(zhí)行對話框。根據(jù)對話框所提示內(nèi)容進(jìn)行輸寫。2）結(jié)合本實驗的要求，輸入就緒隊列的個數(shù)為5，輸入就緒隊列的CPU時間片分別為2、4、8、16、32，輸入,進(jìn)程個數(shù)為5，進(jìn)程名與所需時間依次為（jc1、1)、(jc2、2）、（jc3、3）、（jc4、4）、（jc5、5)，點擊回車鍵，則出現(xiàn)執(zhí)行結(jié)果，如下圖所示：圖5-5進(jìn)程運行結(jié)果五3）再次輸入進(jìn)程個數(shù)為5，出現(xiàn)如圖所示的調(diào)式結(jié)果：圖5-6進(jìn)程運行結(jié)果六圖5-7進(jìn)程運行結(jié)果七圖5-8進(jìn)程運行結(jié)果八圖5-9進(jìn)程運行結(jié)果九圖5-10進(jìn)程運行結(jié)果十圖5-11進(jìn)程運行結(jié)果十一4）調(diào)試完成，按任意一個鍵則退出可執(zhí)行對話框。總 結(jié)因在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按照先來先服務(wù)的原則排成一個隊列，每次調(diào)度是，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)執(zhí)行的時間片用完時，調(diào)度程序停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。在時間片輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的影響。如果選擇很小的時間片將有利于短作業(yè)，因為它能較快地完成，但會頻繁的發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；反之，如果選擇太長時間片，使得每個進(jìn)程都能在一個時間片內(nèi)完成，所以，一般定為時間片略大于一次典型地交互所需要的時間。在完成時間片輪轉(zhuǎn)算法的實現(xiàn)過程中，我們遇到了一些問題，比如怎樣運用循環(huán)隊列，如何設(shè)計結(jié)構(gòu)體等等，也積極配合并思考進(jìn)行解決。整體來說，我們的算法雖然實現(xiàn)了體現(xiàn)進(jìn)程動態(tài)運行變化的過程，但是相對而言比較簡單。實驗中，我們小組不斷討論對算法進(jìn)行優(yōu)化，使得運行結(jié)果看起來更容易理解，也達(dá)到了處理機調(diào)度的功能。做實驗讓我們對于時間片輪轉(zhuǎn)的思想理解的更加透徹，鞏固了理論知識的學(xué)習(xí)。實驗心得體會：首先，我們認(rèn)為這次課程設(shè)計是對學(xué)習(xí)《操作系統(tǒng)》的一次綜合考察，鍛煉我們綜合分析問題、解決問題的能力。初次得到課程設(shè)計的題目時，為程序本身的簡單而竊喜過；實驗過程中也出現(xiàn)了一些難題需要解決，為此去苦苦探索過。課程設(shè)計期間，我們完全投入進(jìn)去了，就像是在做一個相當(dāng)重要的項目一樣的感覺。曾經(jīng)跑過圖書館幾次，只是為了一種新的想法得到實現(xiàn)，也曾多次登錄網(wǎng)站瀏覽網(wǎng)頁，為了彌補一些知識上的紕漏，為此曾灑下了真實的汗水。當(dāng)我們的想法得到實現(xiàn)，又學(xué)會了新的知識的時候，心中滿是欣喜，或許這是實踐出真知的真實驗證，有付出就有回報的真實寫照吧。其次，我們感受了真誠的友誼。在實驗中，遇到的問題是多方面的，而且有那么一部分是以前學(xué)過的C語言問題，但是已經(jīng)忘卻或是以前沒有真正的理解過。但是你會發(fā)現(xiàn)就在你的身邊，會有那么一批人在背后熱心的幫助你，讓你身處困境卻感到無限希望。這好像是人生的一種歷程，風(fēng)風(fēng)雨雨中我們一起走過，然后為了一些坑坑洼洼彼此真誠的幫助過和無私的付出過。團(tuán)隊的協(xié)作和彼此心的交流讓我們彼此豐厚起來，這也是我們成長中必不可失的重要部分。最后，我們認(rèn)識到了自己的不足。平心而論，以前真的沒有認(rèn)真的學(xué)習(xí)過，即使是在聽課，可是后來卻沒有對學(xué)習(xí)中出現(xiàn)的問題而仔細(xì)分析過。得過且過，迷失了我前進(jìn)的方向，而現(xiàn)在卻又重新敞開了。不論是以后的學(xué)習(xí)還是工作，我想這都是很重要的，我們需要不斷進(jìn)步的動力?？偟恼f來知識上的收獲很是重要，精神上的豐收也是更加可喜的，讓我知道了學(xué)無止境的道理。我們每一個人永遠(yuǎn)不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財富，經(jīng)歷是一份擁有。這次課程設(shè)計必將成為我人生旅途上一個非常美好的回憶?？刂圃谝豁?。控制在一頁。致謝充實的課程設(shè)計活動在大家的辛勤忙碌中結(jié)束了，它給我們不僅帶來了豐碩的實驗成果，而且使我們對操作系統(tǒng)這門課程的認(rèn)識又更近了一步；時間是檢驗認(rèn)識真理性的唯一標(biāo)準(zhǔn)，在通過我們親身實踐的過程中，我們感受到了巨大的成就感以及獲得了對于課本中的知識更加感性的認(rèn)識。在此，我們必須要向?qū)ξ覀兦斑M(jìn)道路提供指引明燈的人致以最誠摯的感謝。首先，要感謝的是兩位指導(dǎo)老師，陳禮青老師和邱軍林老師。我們很難想象，沒有燈塔指引的我們在茫茫的計算機知識的海洋中如何找到方向。陳禮青老師是一位治學(xué)非常嚴(yán)謹(jǐn)?shù)睦蠋?，對我們的要求較為嚴(yán)格，而且對我們在程序的選擇，修改中起到了至關(guān)重要的作用。對于我們在課程設(shè)計中遇到的各種問題，陳老師總是對我們不清楚的甚至是糾纏不清的問題作出解答，是我們不至于深陷自我桎梏的泥潭。同樣，邱軍林老師也是一位極其耐心和負(fù)責(zé)任的老師，而且對于數(shù)據(jù)庫的深刻認(rèn)識在我們糾正錯誤方面做出了不可磨滅的貢獻(xiàn)，而且在最后的課程設(shè)計的答辯過程中，邱老師和陳老師都對我們系統(tǒng)的改進(jìn)做出了一些建議。對于我們課程設(shè)計程序的改善大有裨益。兩位老師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度以及對學(xué)生耐心負(fù)責(zé)的態(tài)度對我們以后工作生活起著深遠(yuǎn)的影響。淮陰工學(xué)院為我們的課程設(shè)計提供了極好地平臺，這個平臺就是基礎(chǔ)。對于學(xué)習(xí)操作系統(tǒng)的我們，我們自然而然的認(rèn)識到操作系統(tǒng)對于計算機的重要意義，沒有操作系統(tǒng)的一臺計算機對于我們是沒有任何用處的。所以，感謝淮陰工學(xué)院培養(yǎng)出來的良好的學(xué)習(xí)氛圍和堅實的硬件基礎(chǔ)，對我們的前進(jìn)起著推波助瀾的強大作用。當(dāng)然，我們是一個團(tuán)體在戰(zhàn)斗，團(tuán)體的團(tuán)結(jié)讓我們在操作系統(tǒng)課程設(shè)計中付出的努力開花結(jié)果。團(tuán)結(jié)就是力量，大家在課程設(shè)計中各顯其能，使得每個人都在爭論與交流中得到提高，這些才能使得課程設(shè)計這條大船平穩(wěn)的前行，每一位都是好樣的！最后，要向在幕后默默支持和培養(yǎng)我們的父母致以最誠摯的感謝，感恩的話已經(jīng)言盡，一言以蔽之，我們也會在你們的付出中奮勇前行！參考文獻(xiàn)湯小丹，梁紅兵，哲鳳屏，湯子瀛.計算機操作系統(tǒng).西安電子科技大學(xué)出版社，2007.2.孟慶昌.操作系統(tǒng)教程.北京：電子工業(yè)出版社，2004.陳向群，楊芙清.操作系統(tǒng)教程.2版.北京：北京大學(xué)出版社，2006.GaryNutt著.操作系統(tǒng)現(xiàn)代觀點.孟祥由，晏益慧，譯.北京：機械工業(yè)出版社，2004.屠祁，屠立德，等.操作系統(tǒng)基礎(chǔ).3版。北京：清華大學(xué)出版社，2000.哲鳳屏，湯子瀛，楊成忠.計算機操作系統(tǒng).臺灣：儒林圖書公司,1994.黃祥喜.計算機操作系統(tǒng)實驗教程.廣州：中山大學(xué)出版社，1994.李勇，劉恩林.計算機體系結(jié)構(gòu).長沙：國防科技大學(xué)出版社，1987.王鵬，尤晉元，等，譯.操作系統(tǒng)設(shè)計與實現(xiàn).北京：電子工業(yè)出版社，1998.張堯?qū)W，史美林.計算機操作系統(tǒng)教程.北京：清華大學(xué)出版社，2000.附 錄#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode/*進(jìn)程節(jié)點信息*/{charname[20];/*進(jìn)程的名字*/intprio;/*進(jìn)程的優(yōu)先級*/intround;/*分配CPU的時間片*/intcputime;/*CPU執(zhí)行時間*/intneedtime;/*進(jìn)程執(zhí)行所需要的時間*/charstate;/*進(jìn)程的狀態(tài)，W--就緒態(tài)，R--執(zhí)行態(tài)，F(xiàn)--完成態(tài)*/intcount;/*記錄執(zhí)行的次數(shù)*/structnode*next;/*鏈表指針*/}PCB;typedefstructQueue/*多級就緒隊列節(jié)點信息*/{PCB*LinkPCB;/*就緒隊列中的進(jìn)程隊列指針*/intprio;/*本就緒隊列的優(yōu)先級*/intround;/*本就緒隊列所分配的時間片*/structQueue*next;/*指向下一個就緒隊列的鏈表指針*/}ReadyQueue;PCB*run=NULL,*finish=NULL;/*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/ReadyQueue*Head=NULL;/*定義第一個就緒隊列*/intnum;/*進(jìn)程個數(shù)*/intReadyNum;/*就緒隊列個數(shù)*/voidOutput();/*進(jìn)程信息輸出函數(shù)*/voidInsertFinish(PCB*in);/*將進(jìn)程插入到完成隊列尾部*/voidInsertPrio(ReadyQueue*in);/*創(chuàng)建就緒隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/voidPrioCreate();/*創(chuàng)建就緒隊列輸入函數(shù)*/voidGetFirst(ReadyQueue*queue);/*取得某一個就緒隊列中的隊頭進(jìn)程*/voidInsertLast(PCB*in,ReadyQueue*queue);/*將進(jìn)程插入到就緒隊列尾部*/voidProcessCreate();/*進(jìn)程創(chuàng)建函數(shù)*/voidRoundRun(ReadyQueue*timechip);/*時間片輪轉(zhuǎn)調(diào)度算法*/voidMultiDispatch();/*多級調(diào)度算法，每次執(zhí)行一個時間片*/intmain(void){PrioCreate();/*創(chuàng)建就緒隊列*/ProcessCreate();/*創(chuàng)建就緒進(jìn)程隊列*/MultiDispatch();/*算法開始*/Output();/*輸出最終的調(diào)度序列*/return0;}voidOutput()/*進(jìn)程信息輸出函數(shù)*/{ReadyQueue*print=Head;PCB*p;printf("進(jìn)程名\t優(yōu)先級\t輪數(shù)\tcpu時間\t需要時間\t進(jìn)程狀態(tài)\t計數(shù)器\n");while(print){if(print->LinkPCB!=NULL){p=print->LinkPCB;while(p){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}}print=print->next;}p=finish;while(p!=NULL){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}p=run;while(p!=NULL){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}}voidInsertFinish(PCB*in)/*將進(jìn)程插入到完成隊列尾部*/{PCB*fst;fst=finish;if(finish==NULL){in->next=finish;finish=in;}else{while(fst->next!=NULL){fst=fst->next;}in->next=fst->next;fst->next=in;}}voidInsertPrio(ReadyQueue*in)/*創(chuàng)建就緒隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/{ReadyQueue*fst,*nxt;fst=nxt=Head;if(Head==NULL)/*如果沒有隊列，則為第一個元素*/{in->next=Head;Head=in;}else/*查到合適的位置進(jìn)行插入*/{if(in->prio>=fst->prio)/*比第一個還要大，則插入到隊頭*/{in->next=Head;Head=in;}else{while(fst->next!=NULL)/*移動指針查找第一個別它小的元素的位置進(jìn)行插入*