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

1、<p>　　操作系統(tǒng)課程設(shè)計(jì)報(bào)告</p><p>　　選題名稱: 基于時間片的高優(yōu)先級調(diào)度模擬實(shí)現(xiàn) </p><p>　　系（院）: 經(jīng)濟(jì)管理學(xué)院 </p><p>　　專 業(yè): 信息管理與信息系統(tǒng) </p><p>　　班 級:

2、 信管1091 </p><p><b>　　設(shè)計(jì)任務(wù)書</b></p><p><b>　　摘要 </b></p><p>　　操作系統(tǒng)（Operating System，簡稱OS）是計(jì)算機(jī)系統(tǒng)的重要組成部分，是一個重要的系統(tǒng)軟件，它負(fù)責(zé)管理計(jì)算機(jī)系統(tǒng)的硬、軟件資源和整個計(jì)算機(jī)的工作流程，協(xié)

3、調(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)境。更能滿足用戶的需求。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，人們對于計(jì)算機(jī)系統(tǒng)性能的要求也越來越高，對于操作系統(tǒng)所使用的算法也在不斷地發(fā)展。OS對調(diào)度分配實(shí)質(zhì)是一種資源分配，因而調(diào)度算法要根據(jù)不同的系統(tǒng)資源分

4、配策略所規(guī)定的來分配算法。對于不同的系統(tǒng)目標(biāo)，又必須采用不同的調(diào)度算法。有的算法適合長作業(yè)，有的適合短作業(yè)，有的適合作業(yè)調(diào)度，有的適合進(jìn)程調(diào)度。本課程設(shè)計(jì)所討論的基于優(yōu)先級的時間片調(diào)度算法是在諸多的調(diào)度算法中具有明顯有點(diǎn)的調(diào)度算法。該算法涉及到高優(yōu)先級調(diào)度算法、時間片輪轉(zhuǎn)算法、多級反饋隊(duì)列調(diào)度算法。本課題基于Microsoft Visual C++6.0平臺，對算法作出具體的解釋。</p><p>　　關(guān)鍵詞：操

5、作系統(tǒng)，調(diào)度算法，優(yōu)先級，時間片 </p><p><b>　　目 錄</b></p><p><b>　　1 引言5</b></p><p>　　1.1課題設(shè)計(jì)背景5</p><p>　　1.2目的和意義6</p><p>　　1.3調(diào)度算法發(fā)展過程6</

6、p><p>　　1.4使用的到的開發(fā)工具9</p><p><b>　　2需求分析11</b></p><p>　　2.1需求背景11</p><p>　　2.2課程設(shè)計(jì)任務(wù)14</p><p>　　2.3課程設(shè)計(jì)要求15</p><p>　　2.4課程設(shè)計(jì)思想15

7、</p><p><b>　　3概要設(shè)計(jì)16</b></p><p>　　3.1課程設(shè)計(jì)所用方法及其原理16</p><p>　　3.2 主要的數(shù)據(jù)結(jié)構(gòu)17</p><p>　　3.3課題設(shè)計(jì)的流程圖18</p><p><b>　　4詳細(xì)設(shè)計(jì)19</b></

8、p><p>　　4.1設(shè)計(jì)進(jìn)程控制塊19</p><p>　　4.2進(jìn)程調(diào)度21</p><p><b>　　4.3優(yōu)先級22</b></p><p>　　4.3.1 優(yōu)先級簡介22</p><p>　　4.3.2優(yōu)先權(quán)調(diào)度算法的類型22</p><p>　　4.4

9、時間片輪轉(zhuǎn)算法26</p><p>　　4.5 多級反饋隊(duì)列調(diào)度算法29</p><p>　　5調(diào)試與操作說明34</p><p>　　5.1調(diào)試過程中遇到的問題及解決方案34</p><p>　　5.2 測試結(jié)果37</p><p><b>　　總 結(jié)41</b></p>

10、;<p><b>　　致 謝43</b></p><p><b>　　參考文獻(xiàn)44</b></p><p><b>　　附 錄45</b></p><p><b>　　1 引言</b></p><p><b>　　1.1課

11、題設(shè)計(jì)背景</b></p><p>　　計(jì)算機(jī)自從1946年第一臺真正意義上的數(shù)字電子計(jì)算機(jī)ENIAC (Electronic Numerical Integrator And Computer)的 誕生以來，已經(jīng)經(jīng)歷了1854年－1890年、1890年－20世紀(jì)早期、20世紀(jì)中期、20世紀(jì)晚期－現(xiàn)在四個階段，每一個階段的發(fā)展都發(fā)生了質(zhì)與量的突飛猛進(jìn)。然而，計(jì)算機(jī)的發(fā)展只是代表了硬件的提升，對于軟件，

12、操作系統(tǒng)的發(fā)展更加引人注目。</p><p>　　操作系統(tǒng)（Operating System，簡稱OS）是管理電腦硬件與軟件資源的程序，同時也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)是控制其他程序運(yùn)行，管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合。操作系統(tǒng)身負(fù)諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)的型態(tài)非常多樣，不同機(jī)器安裝的OS可從簡單到復(fù)雜

13、，可從手機(jī)的嵌入式系統(tǒng)到超級電腦的大型操作系統(tǒng)。目前微機(jī)上常見的操作系統(tǒng)有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。操作系統(tǒng)的不斷提升對于計(jì)算機(jī)整體性能的提高有著至關(guān)重要的作用。</p><p>　　操作系統(tǒng)對于各個方面的要求都不得不提到效率的問題，計(jì)算機(jī)系統(tǒng)的處理機(jī)調(diào)度便變得尤為重要。處理機(jī)調(diào)度的效率甚至可能成為提高計(jì)算機(jī)處理速度的瓶頸。處理機(jī)調(diào)度就是對系統(tǒng)的資源做出

14、合理的分配，因而，提高處理機(jī)的調(diào)度算法也變得尤為重要。</p><p><b>　　1.2目的和意義</b></p><p>　　在多道程序設(shè)計(jì)系統(tǒng)中，內(nèi)存中有多道程序運(yùn)行，他們相互爭奪處理機(jī)這一重要的資源。處理機(jī)調(diào)度就是從就緒隊(duì)列中，按照一定的算法選擇一個進(jìn)程并將處理機(jī)分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。</p><p>　　一般情況下，當(dāng)占

15、用處理機(jī)的進(jìn)程因?yàn)槟撤N請求得不到滿足而不得不放棄CPU進(jìn)入等待狀態(tài)時，或者當(dāng)時間片到，系統(tǒng)不得不將CPU分配給就緒隊(duì)列中另一進(jìn)程的時候，都要引起處理機(jī)調(diào)度。除此之外，進(jìn)程正常結(jié)束、中斷處理等也可能引起處理機(jī)的調(diào)度。因此，處理機(jī)調(diào)度是操作系統(tǒng)核心的重要組成部分，它的主要功能如下：記住進(jìn)程的狀態(tài)，如進(jìn)程名稱、指令計(jì)數(shù)器、程序狀態(tài)寄存器以及所有通用寄存器等現(xiàn)場信息，將這些信息記錄在相應(yīng)的進(jìn)程控制塊中；根據(jù)一定的算法，決定哪個進(jìn)程能獲得處理機(jī)，

16、以及占用多長時間；收回處理機(jī)，即正在執(zhí)行的進(jìn)程因?yàn)闀r間片用完或因?yàn)槟撤N原因不能再執(zhí)行的時候，保存該進(jìn)程的現(xiàn)場，并收回處理機(jī)。</p><p>　　1.3調(diào)度算法發(fā)展過程</p><p>　　調(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)

17、中，為了保證系統(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)點(diǎn)和缺點(diǎn)。因此，在這里便要對一種結(jié)合了多種算法的具有極強(qiáng)的適應(yīng)性的調(diào)度算法—基于優(yōu)先級的時間片調(diào)度算法作研究。</p><p>　　1）FCFS（First come first serve)，或者稱

18、為FIFO算法，先來先處理。這個算法的優(yōu)點(diǎn)是簡單，實(shí)現(xiàn)容易，并且似乎公平；缺點(diǎn)在于短的任務(wù)有可能變的非常慢，因?yàn)槠淝懊娴娜蝿?wù)占用很長時間，造成了平均響應(yīng)時間非常慢。 2）時間片輪詢算法，這是對FIFO算法的改進(jìn)，目的是改善短程序（運(yùn)行時間短）的響應(yīng)時間，其方法就是周期性地進(jìn)行進(jìn)程切換。這個算法的關(guān)鍵點(diǎn)在于時間片的選擇，時間片過大，那么輪轉(zhuǎn)就越接近FIFO，如果太小，進(jìn)程切換的開銷大于執(zhí)行程序的開銷，從而降低了系統(tǒng)效率。因此選擇合

19、適的時間片就非常重要。選擇時間片的兩個需要考慮的因素：一次進(jìn)程切換所使用的系統(tǒng)消耗以及我們能接受的整個系統(tǒng)消耗、系統(tǒng)運(yùn)行的進(jìn)程數(shù)。時間片輪詢看上起非常公平，并且響應(yīng)時間非常好，然而時間片輪轉(zhuǎn)并不能保證系統(tǒng)的響應(yīng)時間總是比FIFO短，這很大程度上取決于時間片大小的選擇，以及這個大小與進(jìn)程運(yùn)行時間的相互關(guān)系。 3）STCF算法（Short time to complete first)，顧名思義就是短任務(wù)優(yōu)先算法。這種算法的核心就是

20、所有的程序都有一個優(yōu)先級，短任務(wù)的優(yōu)先級比長任務(wù)的高</p><p>　　STCF又分為兩類：非搶占式和搶占式。非搶占式STCF就是讓已經(jīng)在CPU上運(yùn)行的程序執(zhí)行到結(jié)束或者阻塞，然后在所有的就緒進(jìn)程中選擇執(zhí)行時間最短的來執(zhí)行；而搶占式STCF就不是這樣，在每進(jìn)來一個新的進(jìn)程時，就對所有進(jìn)程（包括正在CPU上執(zhí)行的進(jìn)程）進(jìn)行檢查，誰的執(zhí)行時間短，就運(yùn)行誰。</p><p>　　STCF總是能

21、提供最優(yōu)的響應(yīng)時間，然而它也有缺點(diǎn)，第一可能造成長任務(wù)的程序無法得到CPU時間而饑餓，因?yàn)镺S總是優(yōu)先執(zhí)行短任務(wù)；其次，關(guān)鍵問題在于我們怎么知道程序的運(yù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)度算

22、法可以通過給長任務(wù)的進(jìn)程更高的優(yōu)先級來解決這個問題；優(yōu)先級調(diào)度遇到的問題可能是短任務(wù)的進(jìn)程饑餓，這個可以通過動態(tài)調(diào)整優(yōu)先級來解決。實(shí)際上動態(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)

23、。 （3）如果沒有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。 （4）調(diào)度程序遍歷就緒隊(duì)列中的任</p><p>　?。?）此時調(diào)度程序重復(fù)上面計(jì)算過程，轉(zhuǎn)到第4步。 （6）當(dāng)調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計(jì)算所得的權(quán)值都為不大于0時，重復(fù)第2步。linux還有兩個實(shí)時進(jìn)程的調(diào)度策略：FIFO和RR,實(shí)時進(jìn)程會立即搶占非實(shí)時進(jìn)程。 5）顯然，沒有什么調(diào)度算法是毫無缺點(diǎn)的，因此現(xiàn)代OS通常都會采

24、用混合調(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)點(diǎn)是非常靈活，如果你給短任務(wù)發(fā)更多“彩票”，那么就類似STCF調(diào)度，如果給每個進(jìn)程一樣多的“彩票”，那

25、么就類似保證調(diào)度；用戶公平調(diào)度算法，是按照每個用戶，而不是按照每個進(jìn)程來進(jìn)行公平分配CPU時間，這是為了防止貪婪用戶啟用了過多進(jìn)程導(dǎo)致系統(tǒng)效率降低甚至停頓。 7）實(shí)時系統(tǒng)的調(diào)度算法，實(shí)時系統(tǒng)需要考慮每個具體任務(wù)的響應(yīng)時間必須符合要求，在截止時間前完成。 </p><p>　　1.4使用到的開發(fā)工具</p><p>　　在本次課程設(shè)計(jì)中，我們選擇了C++語言作為我們所使用的

26、開發(fā)語言，開發(fā)工具則選用了Microsoft Visual C++ 6.0。MFC借助C++的優(yōu)勢為Windows開發(fā)開辟了一片新天地，同時也借助ApplicationWizzard使開發(fā)者擺脫離了那些每次都必寫基本代碼，借助ClassWizard和消息映射使開發(fā)者擺脫了定義消息處理時那種混亂和冗長的代碼段。更重要的是利用C++的封裝功能使開發(fā)者擺脫Windows中各種句柄的困擾，只需要面對C++中的對象，這樣一來使開發(fā)更接近開發(fā)語言而

27、遠(yuǎn)離系統(tǒng)。正因?yàn)镸FC是建立在C++的基礎(chǔ)上，所以我強(qiáng)調(diào)C/C++語言基礎(chǔ)對開發(fā)的重要性。利用C++的封裝性開發(fā)者可以更容易理解和操作各種窗口對象；利用C++的派生性開發(fā)者可以減少開發(fā)自定義窗口的時間和創(chuàng)造出可重用的代碼；利用虛擬性可以在必要時更好的控制窗口的活動。而且C++本身所具備的超越C語言的特性都可以使開發(fā)者編寫出更易用，更靈活的代碼。</p><p>　　Microsoft Visual C++ 6.0

28、[2]：Visual C++ 6.0，簡稱VC或者VC6.0，是微軟推出的一款C++編譯器，將“高級語言”翻譯為“機(jī)器語言（低級語言）”的程序。Visual C++是一個功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C++1.0后，隨著其新版本的不斷問世，Visual C++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。雖然微軟公司推出了 Visual C++.NET(Visual C++7.0)，但它的應(yīng)

29、用有很大的局限性，只適用于Windows 2000、Windows XP和Windows NT4.0。所以實(shí)際中，更多的是以Visual C++6.0為平臺。</p><p><b>　　1.4.1特色</b></p><p>　　Visual C++6.0由Microsoft開發(fā), 它不僅是一個C++ 編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境

30、（integrated development environment，IDE）。Visual C++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C++是一個功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual

31、C++1.0后，隨著其新版本的不斷問世，Visual C++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。雖然微軟公司推出了Visual C++.NET(Visual C++7.0)，但它的應(yīng)用的很大的局限性，只適用于Windows 2000,Windows XP和Windows NT4.0。所以實(shí)際中，更多的是以Visual C++6.0為平臺。 Visual C++6.0以擁有“語法高亮”，自動編譯功能以及高級除錯功能而</p>

32、;<p><b>　　1.4.2缺點(diǎn)</b></p><p>　　由于C++是由C語言發(fā)展起來的，也支持C語言的編譯。6.0版本是使用最多的版本，很經(jīng)典。最大的缺點(diǎn)是對于模版的支持比較差。現(xiàn)在最新補(bǔ)丁為SP6，推薦安裝，否則易出現(xiàn)編譯時假死狀態(tài)。僅支持Windows操作系統(tǒng)。目前發(fā)現(xiàn)與windows 7兼容性不好，安裝成功后可能會出現(xiàn)無法打開cpp文件的現(xiàn)象。</p>

33、;<p>　　現(xiàn)在的最新版C++編譯器集合在Microsoft Visual Studio 2010軟件里面，包含C++，Visual basic，C#，J#，.net。等, 其中，VC開發(fā)環(huán)境的版本已經(jīng)升級至Microsoft Visual C++ 2010，對C++的支持更加全面穩(wěn)定，建議電腦性能好的可以使用此版本。目前微軟公司已經(jīng)停止對VC++6.0系列產(chǎn)品的維護(hù)，繼而轉(zhuǎn)向.NET平臺環(huán)境，新的MS2008、MS20

34、10等將更符合新世紀(jì)通用開發(fā)需求。</p><p><b>　　不要隨便加空行?。?lt;/b></p><p><b>　　2需求分析</b></p><p><b>　　2.1需求背景</b></p><p>　　無論是在批處理系統(tǒng)還是分時系統(tǒng)中，用戶進(jìn)程數(shù)一般都多于處理機(jī)數(shù)、這

35、將導(dǎo)致它們互相爭奪處理機(jī)。另外，系統(tǒng)進(jìn)程也同樣需要使用處理機(jī)。這就要求進(jìn)程調(diào)度程序按一定的策略，動態(tài)地把處理機(jī)分配給處于就緒隊(duì)列中的某一個進(jìn)程，以使之執(zhí)行。</p><p>　　眾所周知，現(xiàn)在的操作系統(tǒng)都是多任務(wù)的操作系統(tǒng)，實(shí)際上并不是真正同時運(yùn)行多個進(jìn)程，只不過是進(jìn)程在頻繁切換，而這種切換用戶基本上感覺不到，進(jìn)程調(diào)度就是操作系統(tǒng)來完成的。當(dāng)以下情況出現(xiàn)時需要操作系統(tǒng)來調(diào)度進(jìn)程：時間片到，即每個進(jìn)程所分配的時間片

36、用完后，要跳轉(zhuǎn)到調(diào)度程序；占用CPU的當(dāng)前運(yùn)行進(jìn)程提出I/O操作，發(fā)起對內(nèi)核的系統(tǒng)調(diào)用時，在系統(tǒng)調(diào)用結(jié)束后,跳轉(zhuǎn)到調(diào)度程序；當(dāng)前運(yùn)行進(jìn)程對所有內(nèi)核系統(tǒng)調(diào)用的結(jié)束時都要跳轉(zhuǎn)到調(diào)度程序，根據(jù)當(dāng)前的調(diào)度信息來決定下一個可以占用CPU的進(jìn)程。</p><p>　　然而進(jìn)程調(diào)度的實(shí)現(xiàn)需要一系列的算法。如短作業(yè)優(yōu)先調(diào)度算法，但該算法僅照顧了短作業(yè)而忽略了長進(jìn)程，而且如果并未指明進(jìn)程的長度，則短進(jìn)程優(yōu)先和基于進(jìn)程長度的搶占式調(diào)

37、度算法都將無法使用。</p><p>　　在早期的時間片輪轉(zhuǎn)算法[3]中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊(duì)列，每次調(diào)度時，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾 ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計(jì)時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列的隊(duì)首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證

38、就緒隊(duì)列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間的處理機(jī)執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。但該算法存在未考慮優(yōu)先級的不足。而基于時間片的高優(yōu)先級調(diào)度算法則不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各種類型進(jìn)程的需要。</p><p>　　本次試驗(yàn)就是依據(jù)該算法的原理進(jìn)行設(shè)計(jì)的。首先設(shè)置多個就緒隊(duì)列并為各個隊(duì)列賦予不同的優(yōu)先級，第一個隊(duì)列的優(yōu)先級最高，依次降低；當(dāng)新進(jìn)程進(jìn)入內(nèi)存后將

39、其放入第一隊(duì)列的隊(duì)尾，然后再按先來先服務(wù)的原則排隊(duì)等待調(diào)度；僅當(dāng)?shù)谝粋€隊(duì)列為空閑時，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行。</p><p>　　根據(jù)分析，得到如下結(jié)果：</p><p><b>　?。?）系統(tǒng)組成</b></p><p>　　系統(tǒng)由虛擬內(nèi)核(VKernel)、命令解釋程序(Commander)、用戶程序（Application）、

40、編譯器（Compiler）四部分組成。</p><p>　　VKernel首先運(yùn)行，并常駐內(nèi)存。</p><p>　　Kernel啟動后，創(chuàng)建Commander進(jìn)程。根據(jù)用戶請求創(chuàng)建多個Application進(jìn)程。</p><p>　　Kernel負(fù)責(zé)維護(hù)6個數(shù)據(jù)結(jié)構(gòu)，包括時間 (Time), 處理器狀態(tài)(CPUstate),進(jìn)程表 (PCBTable), 就緒隊(duì)列

41、(ReadyState),等待隊(duì)列(BlockedState),運(yùn)行進(jìn)程（RunningState）。</p><p>　　Time是系統(tǒng)時間片。CPUstate應(yīng)包括程序計(jì)數(shù)器PC,累加器A、B,狀態(tài)寄存器F的值。PCBTable的每一項(xiàng)是一個進(jìn)程的進(jìn)程控制塊(PCB)。</p><p>　　Commander程序、Application程序是用下列CPU虛擬指令書寫的程序：</p

42、><p>　　#include <stdio.h> /*定義頭文件（本程序自帶的）*</p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　#include <math.h></p><p&g

43、t;　　typedef struct node /*進(jìn)程節(jié)點(diǎn)信息*/</p><p><b>　　{</b></p><p>　　char name[20]; /*進(jìn)程的名字*/</p><p>　　int prio; /*進(jìn)程的優(yōu)先級*/</p><p>　　int round; /*分配CPU的時

44、間片*/</p><p>　　int cputime; /*CPU執(zhí)行時間*/</p><p>　　int needtime; /*進(jìn)程執(zhí)行所需要的時間*/</p><p>　　char state; /*進(jìn)程的狀態(tài)，W--就緒態(tài)，R--執(zhí)行態(tài)，F(xiàn)--完成態(tài)*/</p><p>　　int count; /*記錄執(zhí)行的次數(shù)

45、*/</p><p>　　struct node *next; /*鏈表指針*/</p><p><b>　　}PCB;</b></p><p>　　typedef struct Queue /*多級就緒隊(duì)列節(jié)點(diǎn)信息*/</p><p><b>　　{</b></p><p&

46、gt;　　PCB *LinkPCB; /*就緒隊(duì)列中的進(jìn)程隊(duì)列指針*/</p><p>　　int prio; /*本就緒隊(duì)列的優(yōu)先級*/</p><p>　　int round; /*本就緒隊(duì)列所分配的時間片*/</p><p>　　struct Queue *next; /*指向下一個就緒隊(duì)列的鏈表指針*/</p><p&g

47、t;　　}ReadyQueue;</p><p>　　PCB *run=NULL,*finish=NULL; /*定義三個隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/</p><p>　　ReadyQueue *Head = NULL; /*定義第一個就緒隊(duì)列*/</p><p>　　int num; /*進(jìn)程個數(shù)*/</p><p>　　

48、int ReadyNum; /*就緒隊(duì)列個數(shù)*/</p><p>　　void Output(); /*進(jìn)程信息輸出函數(shù)*/</p><p>　　void InsertFinish(PCB *in); /*將進(jìn)程插入到完成隊(duì)列尾部*/</p><p>　　void InsertPrio(ReadyQueue *in); /

49、*創(chuàng)建就緒隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/</p><p>　　void PrioCreate(); /*創(chuàng)建就緒隊(duì)列輸入函數(shù)*/</p><p>　　void GetFirst(ReadyQueue *queue); /*取得某一個就緒隊(duì)列中的隊(duì)頭進(jìn)程*/</p><p>　　void InsertLast(PCB *in,ReadyQu

50、eue *queue); /*將進(jìn)程插入到就緒隊(duì)列尾部*/</p><p>　　void ProcessCreate(); /*進(jìn)程創(chuàng)建函數(shù)*/</p><p>　　void RoundRun(ReadyQueue *timechip); /*時間片輪轉(zhuǎn)調(diào)度算法*/</p><p>　　void MultiDispatch(); /

51、*多級調(diào)度算法，每次執(zhí)行一個時間片*/</p><p><b>　?。?）命令解釋程序</b></p><p>　　命令解釋程序從標(biāo)準(zhǔn)輸入重復(fù)讀入用戶命令,然后以消息形式發(fā)送給內(nèi)核。命令解釋程序處理的命令由設(shè)計(jì)者定義并實(shí)現(xiàn)。</p><p><b>　?。?）編譯器</b></p><p>　　編譯

52、器把虛擬指令和虛擬系統(tǒng)調(diào)用編譯為可執(zhí)行字節(jié)碼?？蓤?zhí)行字節(jié)碼由內(nèi)核解釋執(zhí)行。</p><p><b>　　2.2課程設(shè)計(jì)任務(wù)</b></p><p>　　1）設(shè)計(jì)進(jìn)程控制塊； </p><p>　　2）設(shè)計(jì)優(yōu)先級對應(yīng)的時間片； </p><p>　　3）實(shí)現(xiàn)高優(yōu)先級非搶占式調(diào)度算法； </p><p&g

53、t;　　4）實(shí)現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法； </p><p>　　5）實(shí)現(xiàn)基于高優(yōu)先級的時間片輪轉(zhuǎn)算法。</p><p>　　2.2.1課題目的 </p><p>　　1) 理解進(jìn)程調(diào)度相關(guān)理論； </p><p>　　2) 掌握時間片調(diào)度原理； </p><p>　　3) 掌握高優(yōu)先級調(diào)度原理。</p>&l

54、t;p>　　2.2.2課題內(nèi)容 </p><p>　　1) 設(shè)計(jì)進(jìn)程控制塊； </p><p>　　2) 設(shè)計(jì)多個進(jìn)程隊(duì)列； </p><p>　　3) 設(shè)計(jì)多個進(jìn)程； </p><p>　　4) 動態(tài)生成時間片、執(zhí)行時間和優(yōu)先級；</p><p>　　5) 設(shè)計(jì)基于時間片的多優(yōu)先級調(diào)度算法； </p>

55、;<p>　　2.2.3測試要求 </p><p>　　要求輸出進(jìn)程名以及與其對應(yīng)的優(yōu)先級、輪數(shù)、CPU時間、需要時間、進(jìn)程狀態(tài)、計(jì)數(shù)器，可執(zhí)行文件的輸出格式如下：</p><p>　　進(jìn)程名 優(yōu)先級 輪數(shù) CPU時間 需要時間 進(jìn)程狀態(tài) 計(jì)數(shù)器</p><p>　　Jc2 2 8 0 2

56、 W 0</p><p>　　Jc1 1 8 0 1 R 0</p><p><b>　　2.3課程設(shè)計(jì)要求</b></p><p>　　1) 編寫程序完成課題內(nèi)容； </p><p>　　2) 在課程設(shè)計(jì)報(bào)告中畫出基于時

57、間片的高優(yōu)先級調(diào)度函數(shù)流程圖； </p><p>　　3) 撰寫課程設(shè)計(jì)報(bào)告，并參加答辯。 </p><p><b>　　2.4課程設(shè)計(jì)思想</b></p><p>　　FCFS、SJF和優(yōu)先級調(diào)度算法僅對某一類作業(yè)有利，相比之下，它能全面滿足不同類型作業(yè)的需求，較好實(shí)現(xiàn)公平性與資源利用率之間的平衡。對交互型作業(yè)，由于通常較短，這些作業(yè)在第一隊(duì)

58、列規(guī)定的時間片內(nèi)完成，可使用戶感到滿意；對短批作業(yè)，開始時在第一隊(duì)列中執(zhí)行一個時間片就可完成，便可與交互型作業(yè)一樣獲得快速晌應(yīng)，否則通常也僅需在第二、第三隊(duì)列中各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍較短；對長批作業(yè)，它們依次在第一至第n個隊(duì)列中輪番執(zhí)行，不必?fù)?dān)心長時間得不到處理。</p><p>　　不要隨便加空行?。。?lt;/p><p><b>　　3概要設(shè)計(jì)</b&g

59、t;</p><p>　　3.1課程設(shè)計(jì)所用方法及其原理</p><p><b>　　3.1.1優(yōu)先級</b></p><p>　　優(yōu)先級[4]體現(xiàn)了進(jìn)程的重要程度或緊迫程度，在大多數(shù)現(xiàn)代操作系統(tǒng)中，都采用了優(yōu)先級調(diào)度策略。優(yōu)先級從小到大（如0-127），0 優(yōu)先級最低，127 最高。在本實(shí)驗(yàn)中，要求優(yōu)先級為0-8。 </p>&

60、lt;p>　　3.1.2基于時間片調(diào)度 </p><p>　　將所有的就緒進(jìn)程按照先來先服務(wù)[5]的原則，排成一個隊(duì)列，每次調(diào)度時，將CPU 分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)時間片用完時，由一個計(jì)時器發(fā)出時鐘中斷請求，調(diào)度程序把此進(jìn)程終止，把該進(jìn)程放到隊(duì)尾。 </p><p>　　在調(diào)度過程中，需要通過時間函數(shù)檢測進(jìn)程的執(zhí)行時間，當(dāng)該進(jìn)程執(zhí)行時間≥時間片大小時，進(jìn)行調(diào)度。 &

61、lt;/p><p>　　3.1.3高優(yōu)先級調(diào)度 </p><p>　　優(yōu)先級高的進(jìn)程優(yōu)先得到cpu，等該進(jìn)程執(zhí)行完畢后，另外的進(jìn)程才能執(zhí)行。 </p><p>　　3.1.4基于時間片的高優(yōu)先級調(diào)度 </p><p>　　時間片和優(yōu)先級調(diào)度的結(jié)合，在系統(tǒng)中，每個優(yōu)先級對應(yīng)一個就緒隊(duì)列，在每個就緒隊(duì)列內(nèi)，采用時間片調(diào)度。當(dāng)高優(yōu)先級進(jìn)程隊(duì)列調(diào)度完成后

62、，才能轉(zhuǎn)入更低優(yōu)先級的就緒隊(duì)列調(diào)度。</p><p>　　不要隨便加空行！?。?lt;/p><p>　　3.2 主要的數(shù)據(jù)結(jié)構(gòu)</p><p>　　表3.1 PCB的數(shù)據(jù)結(jié)構(gòu)</p><p>　　不要隨便加空行?。。?lt;/p><p>　　3.3課題設(shè)計(jì)的流程圖</p><p>　　圖3.1 主要數(shù)據(jù)

63、流程圖</p><p><b>　　4詳細(xì)設(shè)計(jì)</b></p><p>　　4.1設(shè)計(jì)進(jìn)程控制塊</p><p>　　為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)，即進(jìn)程控制塊【6】他的作用是使一個在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序（含數(shù)據(jù)），成為一個能獨(dú)立運(yùn)行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。在進(jìn)程的整個生命周期中，系

64、統(tǒng)總是通過PCB而不是任何別的什么而感知到該進(jìn)程的存在的。PCB是進(jìn)程存在的唯一標(biāo)志。</p><p>　　4.1.1進(jìn)程控制塊的內(nèi)容</p><p>　　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)使用

65、。外部標(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)程的用戶。</p><p>　　2）處理機(jī)狀態(tài)[8]：主要是由處理機(jī)的各種寄存器中的內(nèi)容組成。處理機(jī)在運(yùn)行時，許多信息都放在寄存器中。當(dāng)處理機(jī)被中斷時，所有這些信息都必須保存在PCB中，以便在該進(jìn)程重新執(zhí)行時，能從斷電繼續(xù)執(zhí)行。這

66、些寄存器包括：（1）通用寄存器，又稱為用戶可視寄存器，它們是用戶進(jìn)程可以訪問的，用于在暫存信息，在大多數(shù)處理機(jī)中，有8~32個通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中科超過100個；（2）指令計(jì)數(shù)器，其中存放訪問的下一條指令的地址；（3）程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條形碼、執(zhí)行方式中斷屏蔽標(biāo)志等 。（4）用戶棧指針，指每個用戶進(jìn)程都有一個或若干個與之相關(guān)的系統(tǒng)棧，用于存放過過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址，棧指針指向該棧的棧頂。<

67、;/p><p>　　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)程使用處理機(jī)的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)；（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)所

68、等待發(fā)生的事件，即阻塞原因。</p><p>　　4）進(jìn)程控制信息：進(jìn)程控制信息包括程序和數(shù)據(jù)地址的地址，只進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存底（首）址，以便再調(diào)度到該進(jìn)程執(zhí)行時，能從CPU中找到其程序和數(shù)據(jù)；進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時必須的機(jī)制，如信息隊(duì)列指針、信號量等，他們可能全部或的放在PCB中；資源清單，即一張列出了除CPU以外的、進(jìn)程所需的全部資源即已經(jīng)分配到該進(jìn)程的資源清單；鏈接指針

69、，它給出了本進(jìn)程（PCB）所在隊(duì)列中的下一個進(jìn)程的PCB的首地址。</p><p>　　4.1.2 PCB的信息</p><p>　　進(jìn)程名字name、進(jìn)程的優(yōu)先級prio、分配CPU的時間片round、進(jìn)程執(zhí)行所需要的時間needtime、進(jìn)程的狀態(tài)state、記錄執(zhí)行的次數(shù)count、鏈表指針next。</p><p>　　4.1.3進(jìn)程控制塊的格式</p

70、><p>　　圖4.1進(jìn)程控制塊格式</p><p>　　其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，如Q1、Q2等。</p><p>　　指針——進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程的指針指出第一個進(jìn)程的進(jìn)程控制塊首地址。</p><p>　　要求運(yùn)行時間——假設(shè)進(jìn)程需要運(yùn)行的單位時間數(shù)。</p>

71、<p>　　已運(yùn)行時間——假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時間數(shù)，初始值為“0”。</p><p>　　狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“W”表示。當(dāng)一個進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“F”表示，當(dāng)進(jìn)程運(yùn)行時，它的狀態(tài)為“執(zhí)行”，用“R”表示。</p><p>　　4.2進(jìn)程的三種基本狀態(tài)</p><p>　　1）就緒（rea

72、dy）狀態(tài)</p><p>　　分配到除CPU以外所有必要的資源以后，只要在獲得CPU，便可立即執(zhí)行，進(jìn)程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個，通常將它們排成一個隊(duì)列，稱為就緒隊(duì)列。</p><p><b>　　2）執(zhí)行狀態(tài)</b></p><p>　　進(jìn)程已獲得CPU，其程序正在執(zhí)行。在單機(jī)處理系統(tǒng)中，只有一個進(jìn)程

73、處于執(zhí)行狀態(tài)；在多處理機(jī)系統(tǒng)中，則有多個進(jìn)程處于執(zhí)行狀態(tài)。</p><p><b>　　3）阻塞狀態(tài)</b></p><p>　　正在執(zhí)行的進(jìn)程由于發(fā)生某個時間而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)或者封鎖狀態(tài)。致使進(jìn)程阻塞的典型事件有：強(qiáng)求I/O，申請緩存空間等。通常將這種處于阻塞狀態(tài)

74、的進(jìn)程也排成一個隊(duì)列。有的系統(tǒng)則根據(jù)阻塞原因的不同而把處于阻塞狀態(tài)的進(jìn)程拍成多個隊(duì)列。</p><p>　　處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序?yàn)橹峙涞牧颂幚頇C(jī)之后，該進(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)程訪問

75、時），使之無法繼續(xù)執(zhí)行，該進(jìn)程將由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。如圖，表示了進(jìn)程三種基本狀態(tài)以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系。</p><p><b>　　4.3優(yōu)先級</b></p><p>　　4.3.1 優(yōu)先級簡介</p><p>　　是指在進(jìn)程創(chuàng)建時先確定一個初始優(yōu)先數(shù)， 以后在進(jìn)程運(yùn)行中隨著進(jìn)程特性的改變不斷修改優(yōu)先數(shù)，這樣，由于開始優(yōu)先數(shù)很低而得

76、不到CPU的進(jìn)程，就能因?yàn)榈却龝r間的增長而優(yōu)先數(shù)變?yōu)樽罡叨玫紺PU運(yùn)行。</p><p>　　4.3.2優(yōu)先權(quán)調(diào)度算法的類型 　　</p><p>　　1）非搶占式優(yōu)先權(quán)算法：在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成； 或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系

77、統(tǒng)中；也可某些對實(shí)時性要求不嚴(yán)的實(shí)時系統(tǒng)中。 　　</p><p>　　2）搶占式優(yōu)先權(quán)調(diào)度算法：系統(tǒng)同樣把處理機(jī)分配給優(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í)行,重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。這種搶占式的優(yōu)先權(quán)調(diào)度算法,能更好地滿足緊迫作業(yè)的要求,常用于要求比較嚴(yán)格的實(shí)時系統(tǒng)中, 以及對性能要求較高的批

78、處理和分時系統(tǒng)中。 　　</p><p>　　4.3.3優(yōu)先權(quán)的類型 　　</p><p>　　1）靜態(tài)優(yōu)先權(quán)[10]：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運(yù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ù)有三

79、個方面:（1）進(jìn)程類型(系統(tǒng)進(jìn)程/用戶進(jìn)程)（2）進(jìn)程對資源的需求(需求量的大小)（3）用戶要求(用戶進(jìn)程緊迫程度) 　　</p><p>　　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ī)定,在就緒隊(duì)列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的

80、進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法。 　</p><p>　　4.3.4 優(yōu)先權(quán)的變化規(guī)律</p><p>　　由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間,故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。</p><p>　　4.3.5優(yōu)先級的算法</p><p>　　1)設(shè)定系統(tǒng)中有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制

81、塊（ PCB）表示，進(jìn)程隊(duì)列采用鏈表數(shù)據(jù)結(jié)構(gòu)。</p><p>　　2)進(jìn)程控制塊包含如下信息：進(jìn)程名、優(yōu)先數(shù)、需要運(yùn)行時間、已用CPU時間、進(jìn)程狀態(tài) 等等等。</p><p>　　3)在每次運(yùn)行設(shè)計(jì)的處理調(diào)度程序之前，由終端輸入五個進(jìn)程的“優(yōu)先數(shù)”和“要求運(yùn)行時間”。</p><p>　　4)進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時間人為地指定.進(jìn)程的運(yùn)行時間以時間片為單位進(jìn)行

82、計(jì)算。</p><p>　　5)采用優(yōu)先權(quán)調(diào)度算法，將五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成就緒隊(duì)列。用頭指針指出隊(duì)列首進(jìn)程，隊(duì)列采用鏈表結(jié)構(gòu)。</p><p>　　6)處理機(jī)調(diào)度總是選隊(duì)列首進(jìn)程運(yùn)行。采用動態(tài)優(yōu)先數(shù)辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)“1”，同時將已運(yùn)行時間加“1”。</p><p>　　7)進(jìn)程運(yùn)行一次后，若要求運(yùn)行時間不等于已運(yùn)行時間，則再將它加入就緒隊(duì)列；

83、否則將其狀態(tài)置為“結(jié)束”,且退出就緒隊(duì)列。</p><p>　　8)“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面6，7步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。</p><p>　　9)在設(shè)計(jì)的程序中有輸入語句，輸入5個進(jìn)程的“優(yōu)先數(shù)”和“要求運(yùn)行時間”，也有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名、運(yùn)行一次后隊(duì)列的變化，以及結(jié)束進(jìn)程的進(jìn)程名。</p><p>　

84、　10)最后，為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時間”，運(yùn)行并調(diào)試所設(shè)計(jì)的程序，顯示或打印出逐次被選中進(jìn)程的進(jìn)程名及其進(jìn)程控制塊的動態(tài)變化過程。</p><p>　　4.3.6最高優(yōu)先級優(yōu)先調(diào)度算法流程圖</p><p>　　圖4.3最高優(yōu)先級優(yōu)先調(diào)度算法流程圖</p><p>　　4.4 時間片輪轉(zhuǎn)算法</p><p>　　4.4

85、.1時間片輪轉(zhuǎn)法的基本原理</p><p>　　系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊(duì)列，每次調(diào)度時，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時間片。此實(shí)驗(yàn)中時間片的單位定義為100ms。當(dāng)執(zhí)行的時間片用完時，由一個計(jì)時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中的對手進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程

86、在一給定的時間內(nèi)均能獲得一時間片的處理機(jī)執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。</p><p>　　4.4.2 時間片輪轉(zhuǎn)算法描述</p><p>　　1）設(shè)系統(tǒng)有10個進(jìn)程，每個進(jìn)程用一個進(jìn)程控制塊PCB來代表。</p><p>　　2）為每個進(jìn)程任意確定一個要求運(yùn)行時間。</p><p>　　3）按照進(jìn)程輸入的先后順序

87、排成一個隊(duì)列。再設(shè)一個隊(duì)首指針指向第一個到達(dá)進(jìn)程的首址。</p><p>　　4）執(zhí)行處理機(jī)調(diào)度時，開始選擇隊(duì)首的第一個進(jìn)程運(yùn)行。另外，再設(shè)一個當(dāng)前運(yùn)行進(jìn)程的指針，指向當(dāng)前正在運(yùn)行的進(jìn)程。</p><p>　　5）考慮到代碼的可重用性， 輪轉(zhuǎn)法調(diào)度程序和最高優(yōu)先級優(yōu)先調(diào)度是調(diào)用同一個?？爝M(jìn)行輸出</p><p>　　注:由于輪轉(zhuǎn)法調(diào)度程序和最高優(yōu)先級優(yōu)先調(diào)度是調(diào)用同

88、一個?？爝M(jìn)行輸出,所以在時間輪轉(zhuǎn)法調(diào)度算法的進(jìn)程中,依然顯示上述所定義的優(yōu)先級數(shù)。</p><p>　　6）進(jìn)程運(yùn)行一次后，以后的調(diào)度則將當(dāng)前指針依此下移一個位置，指向下一個進(jìn)程，即調(diào)整當(dāng)前運(yùn)行指針指向該進(jìn)程的鏈接指針?biāo)高M(jìn)程，以指示應(yīng)運(yùn)行進(jìn)程。同時還應(yīng)采用計(jì)數(shù)器來判斷該進(jìn)程的要求運(yùn)行時間是否等于已運(yùn)行時間。若不等，則等待下一輪的運(yùn)行，但此時該進(jìn)程應(yīng)插到代執(zhí)行隊(duì)列的尾部，否則將該進(jìn)程的狀態(tài)置為完成態(tài)F，并退出執(zhí)行

89、隊(duì)列進(jìn)入完成隊(duì)列。</p><p>　　7）若就緒隊(duì)列不空，則重復(fù)上述的5）和6）步驟直到所有的進(jìn)程都運(yùn)行完為止。</p><p>　　8）在所設(shè)計(jì)的調(diào)度程序中，包含顯示或打印語句。顯示或打印每次選中的進(jìn)程的名稱、所需運(yùn)行的時間、輪數(shù)、cpu時間、運(yùn)行一次后進(jìn)程所處的狀態(tài)以及計(jì)數(shù)器的變化情況。</p><p><b>　　4.4.3 要求</b>

90、;</p><p>　　1）在開始頁面用戶可輸入進(jìn)程名，給出時間片的大小和每個進(jìn)程的服務(wù)時間。 </p><p>　　2）每運(yùn)行一次，給進(jìn)程的服務(wù)時間減去一個時間片大小排到隊(duì)尾，顯示一個時間片后的新隊(duì)列。</p><p>　　3）直到所有的進(jìn)程都服務(wù)完。</p><p>　　4.4.4 時間片的工作流程</p><p&g

91、t;　　時間片輪轉(zhuǎn)的原則是系統(tǒng)將所有的就緒進(jìn)程按照先來先服務(wù)的原則排成一個隊(duì)列，每次調(diào)度時，把CPU分配對手進(jìn)程，并令其執(zhí)行一個時間片，當(dāng)執(zhí)行完時，有一個計(jì)時器發(fā)出時鐘中斷請求，該進(jìn)程停止，并被送到就緒隊(duì)列的末尾，然后再把處理機(jī)分配就緒隊(duì)列的隊(duì)列進(jìn)程，同時也讓它執(zhí)行一個時間片。</p><p>　　根據(jù)時間片輪轉(zhuǎn)調(diào)度算法并結(jié)合本實(shí)驗(yàn)，分析進(jìn)程運(yùn)行情況，得到如下圖所示的時間軸：</p><p&g

92、t;　　不要隨便加空行?。。?lt;/p><p>　　圖4.4進(jìn)程運(yùn)行情況</p><p>　　不要隨便加空行?。?！</p><p>　　4.4.5 時間片輪轉(zhuǎn)調(diào)度流程圖</p><p>　　圖4.5時間片輪轉(zhuǎn)法調(diào)度算法流程圖</p><p>　　4.5 多級反饋隊(duì)列調(diào)度算法</p><p>　　多

93、級反饋隊(duì)列調(diào)度算法是一種CPU處理機(jī)調(diào)度算法，UNIX操作系統(tǒng)采取的便是這種調(diào)度算法。多級反饋隊(duì)列調(diào)度算法不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各類進(jìn)程的需要，因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。</p><p>　　4.5.1 多級反饋隊(duì)列調(diào)度算法原理</p><p>　　1）設(shè)有Ｋ個隊(duì)列，其中各個隊(duì)列對于處理機(jī)的優(yōu)先級是不一樣的，也就是說位于各個隊(duì)列中的作業(yè)(進(jìn)程)

94、的優(yōu)先級也是不一樣的。一般來說，第一個隊(duì)列的優(yōu)先級 最高，第二個隊(duì)列次之，其余各隊(duì)列的優(yōu)先級逐個降低。</p><p>　　2）對于某個特定的隊(duì)列來說，里面是遵循時間片輪轉(zhuǎn)法。也就是說，位于隊(duì)列Ｋ中有N個作業(yè)，它們的運(yùn)行時間是通過Ｋ這個隊(duì)列所設(shè)定的時間片來確定的（為了便于理解，我們也可以認(rèn)為特定隊(duì)列中的作業(yè)的優(yōu)先級是按照FCFS來調(diào)度的）。 </p><p>　　3）各個隊(duì)列的時間片是一樣

95、的嗎？不一樣，這就是該算法設(shè)計(jì)的精妙之處。各個隊(duì)列的時間片是隨著優(yōu)先級的增加而減少的，也就是說，優(yōu)先級越高的隊(duì)列中它的時間片就越短。例如，第二個隊(duì)列的時間片要比第一個隊(duì)列的時間片要長一倍，……，最后一個隊(duì)列(優(yōu)先級最低的隊(duì)列)的時間片一般很大。下圖是多級反饋隊(duì)列算法的示意。</p><p>　　圖 4.6多級反饋隊(duì)列調(diào)度算法</p><p>　　4.5.2 多級反饋隊(duì)列調(diào)度算法描述<

96、/p><p>　　1）設(shè)置多個就緒隊(duì)列，并給隊(duì)列賦予不同的優(yōu)先級數(shù)，第一個最高，依次遞減。</p><p>　　2）賦予各個隊(duì)列中進(jìn)程執(zhí)行時間片的大小，優(yōu)先級越高的隊(duì)列，時間片越小。</p><p>　　3）當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將其放入一個對列末尾，如果在一個時間片結(jié)束時尚未完成，將其轉(zhuǎn)入第二隊(duì)列末尾。</p><p>　　4）當(dāng)一個進(jìn)程

97、從一個對列移至第n個隊(duì)列后，便在第n個隊(duì)列中采用時間片輪轉(zhuǎn)執(zhí)行完。</p><p>　　5）僅當(dāng)時間片空閑時，才調(diào)度第二個隊(duì)列中的進(jìn)程。(1~i-1)空閑時，才調(diào)度i，如果處理機(jī)正在第i隊(duì)列中運(yùn)行，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則新進(jìn)程搶占處理機(jī)，將正在運(yùn)行的進(jìn)程放入第i隊(duì)列隊(duì)尾，將處理機(jī)分給新進(jìn)程。</p><p>　　4.5.3 多級反饋隊(duì)列調(diào)度算法的性能</p>&l

98、t;p>　　多級反饋隊(duì)列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。</p><p>　　1）終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多數(shù)屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。</p><p>　　2）短批處理作業(yè)用戶。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一對列中執(zhí)行

99、一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。</p><p>　　3）長批處理作業(yè)用戶。對于長作業(yè)它將依次在第1,2，…，k個隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。</p><p>　　4.5.4 多級反饋隊(duì)列調(diào)度算法的運(yùn)作</p><p

100、>　　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。</p><p>　?。?）時刻0： A到達(dá)。運(yùn)行1個時間片 ， 完成執(zhí)行，調(diào)入完成隊(duì)列，此時B到達(dá)。</p>&l

101、t;p>　?。?）時刻1： B到達(dá)。運(yùn)行了1個時間片后，C到達(dá)。</p><p>　?。?）時刻2： C到達(dá)。由于時間片仍然由B掌控，于是等待。B在運(yùn)行了1個時間片后，已經(jīng)完成2個時間片的限制，加入完成隊(duì)列隊(duì)尾，現(xiàn)在處理機(jī)分配給C。</p><p>　?。?）時刻3 ：D到達(dá)。由于時間片仍然由C掌控，于是等待。C在運(yùn)行了1個時間片后，E到達(dá)。</p><p>

102、　　（5）時刻4 ：E到達(dá)。由于時間片仍然由C掌控，于是等待。C在運(yùn)行了1個時間片后，時間片用完，置于等待，處理機(jī)分配給D，F(xiàn)到達(dá)。</p><p>　?。?）時刻5 ：F到達(dá)。由于時間片由D掌控，于是等待。D在運(yùn)行了1個時間片后，G到達(dá)。</p><p>　?。?）時刻6： G到達(dá)。由于時間片由D掌控，于是等待。D在運(yùn)行了1個時間片后，時間片用完，置于等待，處理機(jī)分配給E，H到達(dá)。<

103、;/p><p>　?。?）時刻7： H到達(dá)。由于時間片由E掌控，于是等待。E在運(yùn)行了1個時間片后，I到達(dá)。</p><p>　　（9）時刻8 ：I到達(dá)。由于時間片由E掌控，于是等待。E在運(yùn)行了1個時間片后，時間片用完，置于等待，處理機(jī)分配給F，J到達(dá)。</p><p>　?。?0）時刻9 ：J到達(dá)。由于時間片由F掌控，于是等待。F在運(yùn)行了2個時間片后，時間片用完，置于等

104、待，處理機(jī)分配給C。</p><p>　?。?1）時刻11。C運(yùn)行了1個時間片后，完成執(zhí)行，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給G。</p><p>　?。?2）時刻12。G運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給H。</p><p>　　（13）時刻14。H運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給D。</p><p>

105、　　（14）時刻16。D運(yùn)行了2個時間片后，完成執(zhí)行，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給I。</p><p>　?。?5）時刻18。I運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給J。</p><p>　?。?6）時刻20。J運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給E。</p><p>　　（17）時刻22。E運(yùn)行了2個時間片后，時間片用完，于是等

106、待，處理機(jī)分配給F。</p><p>　?。?8）時刻24。F運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給G。</p><p>　　(19)時刻26。G運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給H。</p><p>　　(20)時刻28。H運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給I。</p><p>　　(

107、21)時刻30。I運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給J。</p><p>　　(22)時刻32。J運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給E。</p><p>　　(23)時刻34。E運(yùn)行了1個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給F。</p><p>　　(24)時刻35。F運(yùn)行了2個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)

108、尾，處理機(jī)分配給G。</p><p>　　(25)時刻37。G運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給H。</p><p>　　(26)時刻39。H運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給I。</p><p>　　(27)時刻41。I運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給J。</p><p>　　(

109、28)時刻43。J運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給G。</p><p>　　(29)時刻45。G運(yùn)行了1個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給H。</p><p>　　(30)時刻46。H運(yùn)行了2個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給I。</p><p>　　(31)時刻48。I運(yùn)行了2個時間片后，時間片用完，于是等

110、待，處理機(jī)分配給J。</p><p>　　(32)時刻50。J運(yùn)行了2個時間片后，時間片用完，于是等待，處理機(jī)分配給I。</p><p>　　(33)時刻52。I運(yùn)行了1個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)尾，處理機(jī)分配給J。</p><p>　　(34)時刻53。J運(yùn)行了2個時間片后，執(zhí)行完成，調(diào)入完成隊(duì)列隊(duì)尾，算法完畢。</p><p>

111、<b>　　進(jìn)程運(yùn)行情況如下圖</b></p><p>　　圖4.7進(jìn)程運(yùn)行情況</p><p><b>　　5調(diào)試與操作說明</b></p><p>　　5.1調(diào)試過程中遇到的問題及解決方案</p><p>　　1）一開始執(zhí)行的結(jié)果都是左對齊，無法居中顯示，如下圖顯示</p><