王會歌

【摘 要】CPU調(diào)度在操作系統(tǒng)中占據(jù)著非常重要的位置，是多道程序系統(tǒng)實現(xiàn)的核心技術(shù)，是進(jìn)程狀態(tài)轉(zhuǎn)換可實現(xiàn)的先決條件。但是目前CPU調(diào)度問題的課程設(shè)計還存在諸多問題，例如課程內(nèi)容過于理論，遠(yuǎn)遠(yuǎn)偏離了實際應(yīng)用。本文我們利用理論結(jié)合實際淺談本科生《操作系統(tǒng)》課程中CPU調(diào)度課程設(shè)計的教學(xué)環(huán)節(jié)。

【關(guān)鍵詞】操作系統(tǒng)；CPU調(diào)度；進(jìn)程

中圖分類號： TP316 文獻(xiàn)標(biāo)識碼： A 文章編號： 2095-2457（2017）23-0069-002

【Abstract】CPU scheduling occupies a very important position in the operating system and is the core technology of multiprocessor system implementation.It is a precondition for the process state transition to be realized.However，there are still many problems in the curriculum design of CPU scheduling.For example，the content of the course is too theoretical and deviates far from the practical application.In this paper，we use theory and practice to discuss the teaching process of CPU scheduling course design in undergraduate "operating system" course.

【Key words】Operating system；CPU scheduling；Process

CPU調(diào)度是多道程序操作系統(tǒng)的設(shè)計基礎(chǔ)。通過在進(jìn)程之間切換CPU，操作系統(tǒng)可以提高單位時間內(nèi)CPU處理進(jìn)程的數(shù)量。本文我們將根據(jù)理論結(jié)合實踐的教學(xué)方法淺談CPU調(diào)度中的課程設(shè)計環(huán)節(jié)。在課程講授過程中，我們不建議一開始直接講授教學(xué)內(nèi)容，建議在講解核心問題之前首先巧妙地引導(dǎo)，具體方法和內(nèi)容如下：首先通過CUP-I/O執(zhí)行周期講述為什么要進(jìn)行CPU調(diào)度。我們知道進(jìn)程的執(zhí)行過程是由CPU執(zhí)行周期與I/O等待周期組成的，是兩者交替的過程。在交替過程中會出現(xiàn)進(jìn)程由于發(fā)生I/O操作或者異常而引起進(jìn)程主動或者被迫放棄CPU，從而出現(xiàn)CPU調(diào)度問題。為了使學(xué)生更加深入的理解這個環(huán)節(jié)，我們將結(jié)合下圖，從短CPU執(zhí)行時間的出現(xiàn)頻率較高，長CPU執(zhí)行時間出現(xiàn)頻率較低，以及輸入/輸出型程序會產(chǎn)生很多短CPU執(zhí)行時間，計算型程序可能會產(chǎn)生少量的長CPU執(zhí)行時間這個環(huán)節(jié)進(jìn)一步說明產(chǎn)生CPU調(diào)度的原因。

為了幫助學(xué)生更好的理解CPU調(diào)度，我們首先向?qū)W生講解CPU調(diào)度程序這個重要的概念。具體的說，CPU調(diào)度程序指的是，當(dāng)CPU空閑時，由CPU調(diào)度程序從就緒隊列中選擇一個進(jìn)程并將CPU分配給它，使這個進(jìn)程運行。然后通過下面的實現(xiàn)代碼并結(jié)合上機過程進(jìn)一步詳細(xì)講解。

接下來，我們將進(jìn)入到CPU調(diào)度講解的具體環(huán)節(jié)，其課程設(shè)計安排如下。首先通過下圖回顧進(jìn)程狀態(tài)之間的轉(zhuǎn)換原理，然后介紹CPU調(diào)度的兩種類型，即搶占式調(diào)度和非搶占式調(diào)度。通過進(jìn)程狀態(tài)轉(zhuǎn)換區(qū)分可搶占式調(diào)度和非可搶占式調(diào)度。具體內(nèi)容如下：

非搶占式調(diào)度指的是一旦將CPU分配給某一個進(jìn)程，該進(jìn)程將會一直占有CPU直到進(jìn)入到終止?fàn)顟B(tài)（指情況4）或切換到等待狀態(tài)（指情況1）時自動釋放CPU的使用權(quán)限。從上面分析易知，當(dāng)出現(xiàn)情況1、4時，會發(fā)生非搶占式調(diào)度，在這種情況下進(jìn)程是主動放棄CPU的。

搶占式調(diào)度指的是優(yōu)先級高的進(jìn)程可以搶占占有CPU的優(yōu)先級較低的進(jìn)程。當(dāng)出現(xiàn)情況2、3時，會發(fā)生搶占式調(diào)度。另外，為了保持代碼執(zhí)行的原子性，進(jìn)而實現(xiàn)進(jìn)程的同步，可以對進(jìn)程設(shè)計關(guān)中斷和開中斷來實現(xiàn)，即當(dāng)執(zhí)行到不允許被中斷的代碼段時，進(jìn)入這段代碼時需要關(guān)中斷，執(zhí)行完這段代碼后再開中斷。

接下來，我們介紹分派程序。分派程序指的是將CPU使用權(quán)交給調(diào)度程序所選擇的進(jìn)程。特別要強調(diào)的是，分派程序和調(diào)度程序是兩個不同的概念，從分派程序的含義我們能夠清楚的理解這一點：在CPU調(diào)度中，分派程序主要負(fù)責(zé)分配CPU，而調(diào)度程序則根據(jù)某種特定的算法從內(nèi)存空間中選擇將要分配CPU的進(jìn)程。為了更深刻的理解這一問題，我們通過下面的代碼進(jìn)行演示。

最后，進(jìn)入到CPU調(diào)度算法環(huán)節(jié)的講解。在學(xué)習(xí)該內(nèi)容之前我們先理解CPU調(diào)度所遵循的幾條準(zhǔn)則。具體地說，CPU一般按照如下準(zhǔn)則進(jìn)行調(diào)度。1）CPU使用率：反映CPU計算機系統(tǒng)中使用的百分率。2）吞吐量：一個單位時間內(nèi)系統(tǒng)完成的進(jìn)程數(shù)量。3）周轉(zhuǎn)時間：從進(jìn)程提交到進(jìn)程完成的時間間隔，包括等待進(jìn)入內(nèi)存時間。4）在就緒隊列中的等待時間、在CPU上的執(zhí)行時間以及執(zhí)行I/O時間的和。5）等待時間：指的是進(jìn)程在就緒隊列中的等待時間。6）響應(yīng)時間：從提交請求到產(chǎn)生第一響應(yīng)的時間。一般情況下，等待時間是CPU最常用的調(diào)度準(zhǔn)則。在理解了這些概念之后，進(jìn)一步講解CPU常用的調(diào)度算法。具體地說，CPU調(diào)度算法主要有以下幾種：先來先服務(wù)、最短作業(yè)有限調(diào)度算法、優(yōu)先權(quán)調(diào)度算法，輪轉(zhuǎn)法調(diào)度，多級隊列調(diào)度和多級反饋隊列調(diào)度算法。其中最短作業(yè)優(yōu)先和多級反饋隊列調(diào)度算法是教學(xué)的難點。我們分別采用算法和圖示的方法對這兩個難點進(jìn)行分析。首先，因為在最短作業(yè)優(yōu)先調(diào)度算法中，主要困難在于不知道如何確定下一個CPU 區(qū)間的長度。

另外，對于多級反饋隊列調(diào)度算法，我們采用的方法是，首先講解該算法的基本實現(xiàn)思想：1）將就緒隊列分解成多個隊列，并為每個隊列賦不同的優(yōu)先級。第一個隊列，優(yōu)先級最高。2）為每個隊列中的進(jìn)程設(shè)置不同的時間片大小，優(yōu)先級越高，其時間片越小。3）當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一個就緒隊列的未尾，按先來先服務(wù)的原則進(jìn)行排列并等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如果它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)，如果它在一個時間片不能完成，則將它轉(zhuǎn)入第二個隊列的未尾，繼續(xù)等待調(diào)度。4）僅當(dāng)?shù)谝粋€隊列為空時，調(diào)度程序才調(diào)度第二個隊列中的進(jìn)程運行。為更好的幫助學(xué)生理解該實現(xiàn)思想，我們將結(jié)合下圖進(jìn)行講解。

【參考文獻(xiàn)】

[1]Abraham Silberschatz，Peter Baer Galvin和Greg Gagne著，鄭扣根譯.操作系統(tǒng)概念第七版.高等教育出版社，2017年1月.

[2]劉珂男，童薇，馮丹，劉景寧，張炬.一種靈活高效的虛擬CPU調(diào)度算法，軟件學(xué)報，2017年2月.

[3]周思林，謝從華.基于FLS的多級隊列CPU調(diào)度系統(tǒng)仿真研究.計算機仿真，2015年7月.endprint