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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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