邱煜炎

摘要：進(jìn)程管理是操作系統(tǒng)課程的核心，而進(jìn)程調(diào)度是進(jìn)程管理理論的教學(xué)重點(diǎn).如果不能將理論與真實操作系統(tǒng)相結(jié)合，學(xué)生很難掌握各種調(diào)度算法的應(yīng)用背景和運(yùn)行原理.筆者通過剖析Linux內(nèi)核源碼，采用探索啟發(fā)式教學(xué)方法，引入進(jìn)程調(diào)度應(yīng)用于Linux操作系統(tǒng)的真實案例，使學(xué)生真切感知實際操作系統(tǒng)中進(jìn)程調(diào)度的運(yùn)行機(jī)理.并且通過修改內(nèi)核源代碼改進(jìn)調(diào)度算法，使學(xué)生加強(qiáng)對調(diào)度算法理論的深入理解，從而提高學(xué)生對操作系統(tǒng)課程學(xué)習(xí)的積極性及分析解決問題的能力.

關(guān)鍵詞：操作系統(tǒng);進(jìn)程調(diào)度;Linux內(nèi)核;教學(xué)方法

中圖分類號：G642.0? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2019）01-0063-03

1 引言

操作系統(tǒng)是計算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)核心課，該課程對其他專業(yè)課程起著承上啟下的作用.課程主要內(nèi)容涵蓋進(jìn)程管理、進(jìn)程調(diào)度與死鎖、存儲器管理、設(shè)備管理、文件管理、操作系統(tǒng)接口等[1].由于操作系統(tǒng)課程理論性強(qiáng)，知識點(diǎn)龐雜從而導(dǎo)致學(xué)生對本門課程的學(xué)習(xí)熱情明顯不高.基于此，筆者嘗試通過剖析Linux內(nèi)核源碼去闡述進(jìn)程調(diào)度的運(yùn)行機(jī)制[2]，采用探索啟發(fā)式教學(xué)方法，讓學(xué)生充分感知真實操作系統(tǒng)軟件的設(shè)計思路，真正讓理論落地于實際，從而提高學(xué)生對操作系統(tǒng)課程的學(xué)習(xí)熱情.

在Linux內(nèi)核版本的選擇上，最新穩(wěn)定版（4.15.15）由于代碼量太過龐大（1400萬行）[3]，學(xué)生很難梳理其架構(gòu)與脈絡(luò)，對代碼剖析更是無從下手，由此產(chǎn)生了畏懼和排斥.0.11版發(fā)行于20世紀(jì)90年代，雖年代久遠(yuǎn)但具備了現(xiàn)代操作系統(tǒng)的基本功能，如多用戶多任務(wù)、中斷并發(fā)、同步互斥等，而代碼量也只有一萬四千行（不包含注釋）.為了深入理解進(jìn)程調(diào)度算法以及增強(qiáng)學(xué)生對內(nèi)核源碼解讀的代入感，筆者最終選擇0.11版Linux內(nèi)核作為操作系統(tǒng)課程的教學(xué)資源.

針對課程設(shè)置，筆者結(jié)合多年的操作系統(tǒng)教學(xué)經(jīng)驗，將進(jìn)程調(diào)度教學(xué)環(huán)節(jié)規(guī)劃為四大部分：一、進(jìn)程調(diào)度概述，讓學(xué)生對進(jìn)程調(diào)度概念有一個大致的了解;二、進(jìn)程調(diào)度步驟宏觀解讀，通過引入Linux實例展示其進(jìn)程調(diào)度的基本步驟;三、進(jìn)程調(diào)度機(jī)制微觀探索，通過分析schedule函數(shù)源代碼，讓同學(xué)了解真實操作系統(tǒng)中進(jìn)程調(diào)度算法的核心內(nèi)容;四、調(diào)度算法優(yōu)化實踐，通過改進(jìn)源代碼，提升操作系統(tǒng)內(nèi)核多進(jìn)程調(diào)度質(zhì)量，使學(xué)生對進(jìn)程調(diào)度算法的解讀得到升華.

2 進(jìn)程調(diào)度概述

進(jìn)程調(diào)度的基本內(nèi)容，包括進(jìn)程調(diào)度的基本概念、進(jìn)程調(diào)度的目標(biāo)、進(jìn)程調(diào)度算法以及各種算法的應(yīng)用場景.進(jìn)程調(diào)度的主要算法有：先來先服務(wù)算法、短作業(yè)優(yōu)先算法、靜/動態(tài)優(yōu)先級算法、時間片輪轉(zhuǎn)法等.評估算法的指標(biāo)有CPU的運(yùn)行效率、進(jìn)程運(yùn)行公平性、響應(yīng)及時性、內(nèi)存吞吐量等幾方面因素.

上述提及的這些目標(biāo)不可兼?zhèn)?，在講授這些指標(biāo)性能取舍問題時，筆者利用各種真實操作系統(tǒng)進(jìn)行列舉，如UNIX采用動態(tài)優(yōu)先數(shù)調(diào)度、BSD采用多級反饋隊列調(diào)度、Windows采用搶先式多任務(wù)調(diào)度等[4].通過舉例，讓學(xué)生對調(diào)度算法不同的應(yīng)用場景有一個感性的認(rèn)識.

3 進(jìn)程調(diào)度步驟宏觀解讀

為了讓同學(xué)了解0.11版Linux內(nèi)核進(jìn)程調(diào)度的運(yùn)行機(jī)理，在宏觀上筆者基于主要源文件對進(jìn)程調(diào)度的步驟進(jìn)行解讀，如圖1所示：

通過此結(jié)構(gòu)圖，學(xué)生可以了解到主程序文件（main.c）對進(jìn)程調(diào)度進(jìn)行了初始化操作，即執(zhí)行shed_init（）函數(shù).而調(diào)用的sched_init（）函數(shù)來自進(jìn)程調(diào)度程序文件（sched.c），此時筆者要強(qiáng)調(diào)sched.c文件的重要作用，因為這是進(jìn)程調(diào)度的核心.同時，作為進(jìn)程調(diào)度的依據(jù)，進(jìn)程控制塊PCB源自頭文件sched.h中的task_struct結(jié)構(gòu)體.操作系統(tǒng)利用中斷使用戶態(tài)切換至內(nèi)核態(tài)，因此要設(shè)置中斷門（set_intr_gate），執(zhí)行時鐘中斷處理指令（_timer_interrupt）.在中斷處理指令中調(diào)用了do_timer函數(shù)，此函數(shù)執(zhí)行時間片輪轉(zhuǎn).最后，利用sched.c文件中的進(jìn)程調(diào)度函數(shù)schedule（），引出進(jìn)程調(diào)度的核心算法.

經(jīng)過以上步驟的解讀，學(xué)生大致了解了0.11版Linux內(nèi)核進(jìn)程調(diào)度的基本流程，即操作系統(tǒng)通過時間片時鐘中斷語句，以進(jìn)程調(diào)度算法為依據(jù)對下一個進(jìn)程進(jìn)行調(diào)度處理.

4 進(jìn)程調(diào)度機(jī)制微觀探索

進(jìn)程調(diào)度的實現(xiàn)應(yīng)具備三個基本機(jī)制，分別是進(jìn)程隊列，進(jìn)程分派程序和上下文切換機(jī)制[5].筆者分別針對三大模塊實現(xiàn)的核心代碼，引導(dǎo)學(xué)生進(jìn)行逐層剖析.

4.1 進(jìn)程隊列

首先將調(diào)度進(jìn)程頭文件sched.h作為切入點(diǎn)，此文件主要包含進(jìn)程控制塊task_struct結(jié)構(gòu)體.而進(jìn)程隊列的實現(xiàn)是由結(jié)構(gòu)體數(shù)組構(gòu)成，通過剛才提及的進(jìn)程調(diào)度核心文件sched.c中第65行代碼可以進(jìn)行例證，核心代碼如下：

struct task_struct *task[NR_TASKS];

4.2 進(jìn)程分派程序

進(jìn)程分派的核心是選擇進(jìn)程，而選擇的依據(jù)是task_struct結(jié)構(gòu)體，涉及counter和priority兩個元素，分別表示任務(wù)運(yùn)行時間片和運(yùn)行優(yōu)先數(shù).當(dāng)定義好結(jié)構(gòu)體后，程序又以宏定義的方式對結(jié)構(gòu)體元素進(jìn)行了初始化操作（#define INIT_TASK），其中counter和priority的初始值都設(shè)置為15.基于以上的描述，學(xué)生意識到0.11版Linux內(nèi)核對每個新進(jìn)程都以相同的時間片和優(yōu)先數(shù)進(jìn)行初始化配置.

其次，要深入解讀sched.c文件的scedule（）函數(shù)，這是進(jìn)程調(diào)度的核心.這部分代碼根據(jù)進(jìn)程的時間片和優(yōu)先權(quán)調(diào)度機(jī)制，來選擇隨后要執(zhí)行的任務(wù).它首先循環(huán)檢查進(jìn)程控制塊數(shù)組中的所有進(jìn)程，根據(jù)每個就緒態(tài)任務(wù)剩余執(zhí)行時間的值counter，選取該值最大的一個任務(wù)，并利用switch_to（）函數(shù)切換到該任務(wù)[6].核心代碼如下：

每當(dāng)選擇出一個新的可運(yùn)行進(jìn)程時，schedule（）函數(shù)就會調(diào)用定義在include/asm/system.h中的switch_to（）宏執(zhí)行實際進(jìn)程切換操作.該宏利用匯編語句把CPU的當(dāng)前進(jìn)程狀態(tài)（上下文）替換成新進(jìn)程的狀態(tài).筆者通過圖的方式對其過程進(jìn)行了解讀，學(xué)生對操作系統(tǒng)控制CPU進(jìn)行進(jìn)程切換有了直觀的認(rèn)識，如圖2所示：

5 調(diào)度算法優(yōu)化實踐

現(xiàn)代分時操作系統(tǒng)中，目前公認(rèn)的一種較好的進(jìn)程調(diào)度算法是采取多級反饋隊列調(diào)度算法，如圖3所示.

基于此，筆者優(yōu)化了0.11版Linux內(nèi)核調(diào)度算法，即將授課過程中涉及的程序文件進(jìn)行代碼修改，并編譯運(yùn)行內(nèi)核，達(dá)到進(jìn)程調(diào)度的預(yù)期效果.在此教學(xué)過程中，學(xué)生們即感受到多級反饋調(diào)度的優(yōu)勢，也加強(qiáng)了解讀內(nèi)核源代碼的能力.

6 小結(jié)

進(jìn)程調(diào)度是操作系統(tǒng)課程的重點(diǎn)和難點(diǎn)，筆者嘗試通過解讀Linux內(nèi)核源代碼，并運(yùn)用探索啟發(fā)式教學(xué)方法，讓學(xué)生生動理解操作系統(tǒng)進(jìn)程調(diào)度的過程.在操作系統(tǒng)課程體系的其他環(huán)節(jié)，也可以嘗試引入Linux內(nèi)核源代碼作為教學(xué)參考資料，真正做到理論聯(lián)系實際，從而提高學(xué)生主動實踐、積極探索、終身學(xué)習(xí)的能力.

參考文獻(xiàn)：

〔1〕羅嬌敏.操作系統(tǒng)進(jìn)程同步和互斥教學(xué)方法研究[J].教育教學(xué)論壇，2017（44）：255-256.

〔2〕吳淑泉.高校“Linux操作系統(tǒng)”課程教學(xué)研究與探索[J].教育理論與實踐，2017（33）：57-58.

〔3〕Latest Stable Kernel.[EB/OL].https：//www.kernel.org/pub.

〔4〕陳莉君，康華.Linux操作系統(tǒng)原理與應(yīng)用（第2版）[M].北京：清華大學(xué)出版社，2016.64-65.

〔5〕湯小丹，梁紅兵.計算機(jī)操作系統(tǒng)（第3版）[M].陜西：西安電子科技大學(xué)出版社，2012.86-87.

〔6〕趙炯.Linux內(nèi)核完全注釋[M].北京：機(jī)械工業(yè)出版社，2017.92-97.

〔7〕趙炯.Linux內(nèi)核完全剖析[M].北京：機(jī)械工業(yè)出版社，2017.130.