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

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

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

3、調(diào)系統(tǒng)部件之間,系統(tǒng)與用戶之間、用戶與用戶之間的關系。隨著操作系統(tǒng)的新技術的不斷出現(xiàn)功能不斷增加。操作系統(tǒng)作為一個標準的套裝軟件必須滿足盡可能多用戶的需要，于是系統(tǒng)不斷膨脹，功能不斷增加，并逐漸形成從開發(fā)工具到系統(tǒng)工具再到應用軟件的一個平臺環(huán)境。更能滿足用戶的需求。隨著計算機技術的不斷發(fā)展，人們對于計算機系統(tǒng)性能的要求也越來越高，對于操作系統(tǒng)所使用的算法也在不斷地發(fā)展。OS對調(diào)度分配實質(zhì)是一種資源分配，因而調(diào)度算法要根據(jù)不同的系統(tǒng)資源分

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

5、作系統(tǒng)，調(diào)度算法，優(yōu)先級，時間片 </p><p><b>　　目 錄</b></p><p><b>　　1 引言5</b></p><p>　　1.1課題設計背景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課程設計任務14</p><p>　　2.3課程設計要求15</p><p>　　2.4課程設計思想15

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

8、p><p>　　4.1設計進程控制塊19</p><p>　　4.2進程調(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)先權調(diào)度算法的類型22</p><p>　　4.4

9、時間片輪轉(zhuǎn)算法26</p><p>　　4.5 多級反饋隊列調(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>　　參考文獻44</b></p><p><b>　　附 錄45</b></p><p><b>　　1 引言</b></p><p><b>　　1.1課

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

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

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

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

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

16、以及占用多長時間；收回處理機，即正在執(zhí)行的進程因為時間片用完或因為某種原因不能再執(zhí)行的時候，保存該進程的現(xiàn)場，并收回處理機。</p><p>　　1.3調(diào)度算法發(fā)展過程</p><p>　　調(diào)度算法[1]是根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的的系統(tǒng)和系統(tǒng)目標，通常采用不同的調(diào)度算法，例如，在批處理系統(tǒng)中，為了照顧為數(shù)眾多的段作業(yè)，應采用短作業(yè)優(yōu)先的調(diào)度算法；又如在分時系統(tǒng)

17、中，為了保證系統(tǒng)具有合理的響應時間，應當采用輪轉(zhuǎn)法進行調(diào)度。目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度；但也有些調(diào)度算法既可以用于作業(yè)調(diào)度，也可以用于進程調(diào)度。各種調(diào)度算法都有其具有的優(yōu)點和缺點。因此，在這里便要對一種結(jié)合了多種算法的具有極強的適應性的調(diào)度算法—基于優(yōu)先級的時間片調(diào)度算法作研究。</p><p>　　1）FCFS（First come first serve)，或者稱

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

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

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

21、提供最優(yōu)的響應時間，然而它也有缺點，第一可能造成長任務的程序無法得到CPU時間而饑餓，因為OS總是優(yōu)先執(zhí)行短任務；其次，關鍵問題在于我們怎么知道程序的運行時間，怎么預測某個進程需要的執(zhí)行時間？通常有兩個辦法：使用啟發(fā)式方法估算（例如根據(jù)程序大小估算），或者將程序執(zhí)行一遍后記錄其所用的CPU時間，在以后的執(zhí)行過程中就可以根據(jù)這個測量數(shù)據(jù)來進行STCF調(diào)度。 4）優(yōu)先級調(diào)度，STCF遇到的問題是長任務的程序可能饑餓，那么優(yōu)先級調(diào)度算

22、法可以通過給長任務的進程更高的優(yōu)先級來解決這個問題；優(yōu)先級調(diào)度遇到的問題可能是短任務的進程饑餓，這個可以通過動態(tài)調(diào)整優(yōu)先級來解決。實際上動態(tài)調(diào)整優(yōu)先級（稱為權值）+時間片輪詢的策略正是linux的進程調(diào)度策略之一的 SCHED_OTHER分時調(diào)度策略,它的調(diào)度過程如下： （1）創(chuàng)建任務指定采用分時調(diào)度策略，并指定優(yōu)先級nice值(-20~19)。 （2）將根據(jù)每個任務的nice值確定在cpu上的執(zhí)行時間(counter)

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

24、用混合調(diào)度算法。例如將不同的進程分為幾個大類，每個大類有不同的優(yōu)先級，不同大類的進程的調(diào)度取決于大類的優(yōu)先級，同一個大類的進程采用時間片輪詢來保證公平性。 6）其他調(diào)度算法，保證調(diào)度算法保證每個進程享用的CPU時間完全一樣；彩票調(diào)度算法是一種概率調(diào)度算法，通過給進程“發(fā)彩票”的多少，來賦予不同進程不同的調(diào)用時間，彩票調(diào)度算法的優(yōu)點是非常靈活，如果你給短任務發(fā)更多“彩票”，那么就類似STCF調(diào)度，如果給每個進程一樣多的“彩票”，那

25、么就類似保證調(diào)度；用戶公平調(diào)度算法，是按照每個用戶，而不是按照每個進程來進行公平分配CPU時間，這是為了防止貪婪用戶啟用了過多進程導致系統(tǒng)效率降低甚至停頓。 7）實時系統(tǒng)的調(diào)度算法，實時系統(tǒng)需要考慮每個具體任務的響應時間必須符合要求，在截止時間前完成。 </p><p>　　1.4使用到的開發(fā)工具</p><p>　　在本次課程設計中，我們選擇了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、遠離系統(tǒng)。正因為MFC是建立在C++的基礎上，所以我強調(diào)C/C++語言基礎對開發(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++編譯器，將“高級語言”翻譯為“機器語言（低級語言）”的程序。Visual C++是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C++1.0后，隨著其新版本的不斷問世，Visual C++已成為專業(yè)程序員進行軟件開發(fā)的首選工具。雖然微軟公司推出了 Visual C++.NET(Visual C++7.0)，但它的應

29、用有很大的局限性，只適用于Windows 2000、Windows XP和Windows NT4.0。所以實際中，更多的是以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++是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual

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

32、;<p><b>　　1.4.2缺點</b></p><p>　　由于C++是由C語言發(fā)展起來的，也支持C語言的編譯。6.0版本是使用最多的版本，很經(jīng)典。最大的缺點是對于模版的支持比較差?，F(xiàn)在最新補丁為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)品的維護，繼而轉(zhuǎn)向.NET平臺環(huán)境，新的MS2008、MS20

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

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

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

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

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

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

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

41、(ReadyState),等待隊列(BlockedState),運行進程（RunningState）。</p><p>　　Time是系統(tǒng)時間片。CPUstate應包括程序計數(shù)器PC,累加器A、B,狀態(tài)寄存器F的值。PCBTable的每一項是一個進程的進程控制塊(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 /*進程節(jié)點信息*/</p><p><b>　　{</b></p><p>　　char name[20]; /*進程的名字*/</p><p>　　int prio; /*進程的優(yōu)先級*/</p><p>　　int round; /*分配CPU的時

44、間片*/</p><p>　　int cputime; /*CPU執(zhí)行時間*/</p><p>　　int needtime; /*進程執(zhí)行所需要的時間*/</p><p>　　char state; /*進程的狀態(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 /*多級就緒隊列節(jié)點信息*/</p><p><b>　　{</b></p><p&

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

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

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

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

50、eue *queue); /*將進程插入到就緒隊列尾部*/</p><p>　　void ProcessCreate(); /*進程創(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>　　命令解釋程序從標準輸入重復讀入用戶命令,然后以消息形式發(fā)送給內(nèi)核。命令解釋程序處理的命令由設計者定義并實現(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課程設計任務</b></p><p>　　1）設計進程控制塊； </p><p>　　2）設計優(yōu)先級對應的時間片； </p><p>　　3）實現(xiàn)高優(yōu)先級非搶占式調(diào)度算法； </p><p&g

53、t;　　4）實現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法； </p><p>　　5）實現(xiàn)基于高優(yōu)先級的時間片輪轉(zhuǎn)算法。</p><p>　　2.2.1課題目的 </p><p>　　1) 理解進程調(diào)度相關理論； </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) 設計進程控制塊； </p><p>　　2) 設計多個進程隊列； </p><p>　　3) 設計多個進程； </p><p>　　4) 動態(tài)生成時間片、執(zhí)行時間和優(yōu)先級；</p><p>　　5) 設計基于時間片的多優(yōu)先級調(diào)度算法； </p>

55、;<p>　　2.2.3測試要求 </p><p>　　要求輸出進程名以及與其對應的優(yōu)先級、輪數(shù)、CPU時間、需要時間、進程狀態(tài)、計數(shù)器，可執(zhí)行文件的輸出格式如下：</p><p>　　進程名 優(yōu)先級 輪數(shù) CPU時間 需要時間 進程狀態(tài) 計數(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課程設計要求</b></p><p>　　1) 編寫程序完成課題內(nèi)容； </p><p>　　2) 在課程設計報告中畫出基于時

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

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

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

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

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

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

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

64、統(tǒng)總是通過PCB而不是任何別的什么而感知到該進程的存在的。PCB是進程存在的唯一標志。</p><p>　　4.1.1進程控制塊的內(nèi)容</p><p>　　1）進程標識符[7]：進程標識符用于惟一的標識一個進程。一個進程通常有兩種標識符：內(nèi)部標識符和外部標識符。內(nèi)部標識符指在所有的操作系統(tǒng)中，都為每一個進程賦予了一個惟一的標識符，他通常是一個進程的符號。設置內(nèi)部標識符主要是為了方便系統(tǒng)使用

65、。外部標識符是由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶（進程）在訪問該進程時使用。為了描述進程的家族關系，還應設置父進程標識和子進程標識。此外，還可設置用戶標識，以指示擁有該進程的用戶。</p><p>　　2）處理機狀態(tài)[8]：主要是由處理機的各種寄存器中的內(nèi)容組成。處理機在運行時，許多信息都放在寄存器中。當處理機被中斷時，所有這些信息都必須保存在PCB中，以便在該進程重新執(zhí)行時，能從斷電繼續(xù)執(zhí)行。這

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

67、;/p><p>　　3）進程調(diào)度信息[9]：在PCB中還存放一些與進程調(diào)度和進程對換有關的信息，包括：（1）進程狀態(tài)，指明進程的當前狀態(tài)，作為進程調(diào)度和兌換的依據(jù)；（2）進程優(yōu)先級，用于描述進程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進程應優(yōu)先獲得處理機；（3）進程調(diào)度所需的其它信息，他們與所采用的進程調(diào)度算法有關，比如，進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等；（4）事件，指進程由執(zhí)行狀態(tài)改為阻塞狀態(tài)所

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

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

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

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

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

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

74、的進程也排成一個隊列。有的系統(tǒng)則根據(jù)阻塞原因的不同而把處于阻塞狀態(tài)的進程拍成多個隊列。</p><p>　　處于就緒狀態(tài)的進程，在調(diào)度程序為之分配的了處理機之后，該進程便可執(zhí)行，相應的，它就由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。正在執(zhí)行的進程也成為當前進程，如果因分配給它的時間片已完而被暫停執(zhí)行時，該進程便由執(zhí)行狀態(tài)又回復到就緒狀態(tài)；如果因發(fā)生某件事而使進程的執(zhí)行受阻（例如，進程請求訪問某臨界資源，而該資源正在被其他進程訪問

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

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

77、統(tǒng)中；也可某些對實時性要求不嚴的實時系統(tǒng)中。 　　</p><p>　　2）搶占式優(yōu)先權調(diào)度算法：系統(tǒng)同樣把處理機分配給優(yōu)先權最高的進程,使之執(zhí)行。但在其執(zhí)行期間,只要又出現(xiàn)了另一個其優(yōu)先權更高的進程,進程調(diào)度程序就立即停止當前進程(原優(yōu)先權最高的進程)的執(zhí)行,重新將處理機分配給新到的優(yōu)先權最高的進程。這種搶占式的優(yōu)先權調(diào)度算法,能更好地滿足緊迫作業(yè)的要求,常用于要求比較嚴格的實時系統(tǒng)中, 以及對性能要求較高的批

78、處理和分時系統(tǒng)中。 　　</p><p>　　4.3.3優(yōu)先權的類型 　　</p><p>　　1）靜態(tài)優(yōu)先權[10]：靜態(tài)優(yōu)先權是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。一般地，優(yōu)先權是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如,0~7，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異:有的系統(tǒng)用“0”表示最高優(yōu)先權,當數(shù)值愈大時,其優(yōu)先權愈低；而有的系統(tǒng)恰恰相反。確定進程優(yōu)先權的依據(jù)有三

79、個方面:（1）進程類型(系統(tǒng)進程/用戶進程)（2）進程對資源的需求(需求量的大小)（3）用戶要求(用戶進程緊迫程度) 　　</p><p>　　2)動態(tài)優(yōu)先權:動態(tài)優(yōu)先權是指在創(chuàng)建進程時所賦予的優(yōu)先權，可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定,在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權以速率a提高。若所有的進程都具有相同的優(yōu)先權初值，則顯然是最先進入就緒隊列的

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

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

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

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

84、　10)最后，為五個進程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，運行并調(diào)試所設計的程序，顯示或打印出逐次被選中進程的進程名及其進程控制塊的動態(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)將所有的就緒進程按先來先服務的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。此實驗中時間片的單位定義為100ms。當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中的對手進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程

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

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

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

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

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

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

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

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

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

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

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

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

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

99、一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應時間。對于稍長的作業(yè)，通常也只需在第二隊列和第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。</p><p>　　3）長批處理作業(yè)用戶。對于長作業(yè)它將依次在第1,2，…，k個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必擔心其作業(yè)長期得不到處理。</p><p>　　4.5.4 多級反饋隊列調(diào)度算法的運作</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時刻到達，所需要的CPU時間片分別為1,2,3,4,5,6,7,8,9,10。</p><p>　?。?）時刻0： A到達。運行1個時間片 ， 完成執(zhí)行，調(diào)入完成隊列，此時B到達。</p>&l

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

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

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

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

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

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

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

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

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

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

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