淺談《操作系統(tǒng)》課程中CPU調(diào)度課程設(shè)計(jì)

王會(huì)歌

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

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

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

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

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

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

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

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

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

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

【參考文獻(xiàn)】

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

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

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