Linux內(nèi)核組調(diào)度的研究與應(yīng)用

杜慧江，王云光

0 引言

進(jìn)程調(diào)度是操作系統(tǒng)內(nèi)核的重要組成部分，直接影響著操作系統(tǒng)的效率。常用的調(diào)度算法一般基于靜態(tài)或動(dòng)態(tài)優(yōu)先級(jí)，維護(hù)若干個(gè)優(yōu)先級(jí)不同的運(yùn)行隊(duì)列；有些情況下要采取特殊方法對(duì)待，調(diào)度過程相對(duì)復(fù)雜。Linux2.6.23以后內(nèi)核采用完全公平調(diào)度算法CFS[1]，取消了優(yōu)先級(jí)隊(duì)列，公平對(duì)待每一個(gè)進(jìn)程，算法和實(shí)現(xiàn)簡單清晰，效率也較高。但是在公平對(duì)待所有進(jìn)程的同時(shí)，也存在一些不足，例如：假設(shè)在系統(tǒng)中有兩個(gè)任務(wù)，任務(wù)A擁有一個(gè)進(jìn)程；任務(wù)B的進(jìn)程擁有多個(gè)子進(jìn)程。如果簡單地公平對(duì)待所有進(jìn)程，則任務(wù)B就會(huì)占用大部分CPU時(shí)間，在任務(wù)級(jí)別上違背了公平原則。

1 組調(diào)度

針對(duì)上述不足，Linux內(nèi)核在2.6.26之后加入了組調(diào)度[1]：將上例任務(wù)B的多個(gè)子進(jìn)程分為一組，將任務(wù)A單獨(dú)作為一組，將兩個(gè)組用CFS算法公平調(diào)度，A和B各占有50%的CPU時(shí)間。當(dāng)調(diào)度器將CPU時(shí)間分配給任務(wù)B時(shí)，再進(jìn)一步確定應(yīng)該分配給B的哪個(gè)子進(jìn)程。這樣對(duì)于A和B兩個(gè)任務(wù)，是公平的。

分組的方法不只限定為根據(jù)每個(gè)任務(wù)的進(jìn)程所屬關(guān)系，也可以根據(jù)用戶來分：比如教師為一組，學(xué)生為另一組；或者系統(tǒng)管理員一組，數(shù)據(jù)庫管理員一組，普通用戶一組等。

Linux 2.6.27內(nèi)核有三種分組調(diào)度方式：公平組調(diào)度CONFIG_FAIR_GROUP_SCHED、實(shí)時(shí)組調(diào)度CONFIG_RT_GROUP_SCHED和控制組調(diào)度CONFIG_CGROUP_SCHED[2]。這幾種方式在內(nèi)核中都有對(duì)應(yīng)的布爾開關(guān)參數(shù)來控制，并且都以CONFIG_GROUP_SCHED參數(shù)為真作為前提條件。

1.1 公平組調(diào)度

公平組調(diào)度建立在CFS算法的基礎(chǔ)上。CFS用基于時(shí)間計(jì)算鍵值的紅黑樹來選取下一個(gè)任務(wù)，公平組調(diào)度對(duì)此做了一些改變[4]：

首先，創(chuàng)建了調(diào)度實(shí)體sched_entity取代單個(gè)進(jìn)程作為調(diào)度對(duì)象，作為紅黑樹的葉子結(jié)點(diǎn)。sched_entity 是一個(gè)結(jié)構(gòu)體，既封裝了與需要調(diào)度的若干個(gè)進(jìn)程有關(guān)的信息，又沒有改變CFS調(diào)度算法的工作方式；它代表一組指定的進(jìn)程；每個(gè)實(shí)體都有自己的一個(gè)運(yùn)行隊(duì)列，同時(shí)也都有一個(gè)父親指針、一個(gè)指向需要調(diào)度的運(yùn)行隊(duì)列的指針。

在內(nèi)核代碼的/include/linux/sched.h中定義了sched_entity：

其次，公平組調(diào)度采用了嵌套層次結(jié)構(gòu)。在頂層有一棵紅黑樹，所有葉子結(jié)點(diǎn)都是一個(gè)調(diào)度實(shí)體；這層的調(diào)度實(shí)體如果不只是一個(gè)單獨(dú)的進(jìn)程而是包含一組進(jìn)程，就嵌套一棵子紅黑樹，每個(gè)子進(jìn)程都處于子紅黑樹的葉子結(jié)點(diǎn)。還可以繼續(xù)嵌套下去，不過目前的Linux內(nèi)核還沒有實(shí)現(xiàn)更多層次的嵌套調(diào)度。

當(dāng)調(diào)度器挑選下一個(gè)將要運(yùn)行的任務(wù)時(shí)，它查找所有頂層的調(diào)度實(shí)體并且找出最應(yīng)當(dāng)占用CPU的那個(gè)實(shí)體，也就是頂層紅黑樹最左邊的葉子結(jié)點(diǎn)；如果那個(gè)實(shí)體不只是一個(gè)進(jìn)程，而是一個(gè)有多個(gè)進(jìn)程的調(diào)度實(shí)體，那么調(diào)度器就查找該實(shí)體的運(yùn)行隊(duì)列，繼續(xù)尋找其中應(yīng)該獲得CPU的任務(wù)，沿著層次向下直到找到一個(gè)實(shí)際的進(jìn)程。當(dāng)進(jìn)程開始運(yùn)行，有關(guān)的運(yùn)行信息被收集起來，沿著層次結(jié)構(gòu)向上傳送以便當(dāng)前進(jìn)程的CPU占用情況可以被每個(gè)層次知曉。

1.2 實(shí)時(shí)組調(diào)度

實(shí)時(shí)組調(diào)度要調(diào)度多個(gè)包含實(shí)時(shí)任務(wù)的組，就要給每個(gè)組分配固定比例的可用CPU時(shí)間。如果沒有給定占用CPU時(shí)間的下限，很明顯一個(gè)組會(huì)被別的組擠占；如果沒有給定占用CPU時(shí)間的上限，則會(huì)擠占不屬于自己的CPU時(shí)間，因此只能分配某個(gè)固定的比例。

CPU時(shí)間是根據(jù)每個(gè)組在一個(gè)周期內(nèi)可以占用的比例來分配的，給每個(gè)實(shí)時(shí)組都分配某個(gè)比例，這個(gè)比例內(nèi)的CPU時(shí)間別的組不能占用。沒有分配給實(shí)時(shí)組的時(shí)間，會(huì)被用在普通優(yōu)先級(jí)的任務(wù)；分配給實(shí)時(shí)組的時(shí)間如果沒有被使用，也會(huì)被轉(zhuǎn)給普通優(yōu)先級(jí)的任務(wù)。

例如：一個(gè)實(shí)時(shí)渲染任務(wù)要求達(dá)到每秒25幀，即幀之間的間隔最多為 0.04秒；并且同時(shí)還要播放音樂、響應(yīng)用戶輸入。渲染任務(wù)屬于圖形組，音樂屬于音頻組。如果cpu時(shí)間的80%分配給圖形組，也就是渲染任務(wù)的每兩幀之間的時(shí)間間隔最多0.032秒。于是，圖形組會(huì)有0.04秒的周期，最多占用其中 0.032秒。如果音頻組需要每 0.005秒填充DMA緩沖，但是只需要 3%時(shí)間就可以完成，那么音頻組會(huì)被分配0.005秒的時(shí)間，但是只用0.00015秒運(yùn)行?？沼喑鰜淼?.00485秒會(huì)被用于用戶輸入和其他任務(wù)。

要讓某個(gè)組加入實(shí)時(shí)組調(diào)度，必須先給這個(gè)組分配一定比例的CPU時(shí)間，然后實(shí)時(shí)任務(wù)才能運(yùn)行；否則，哪怕這個(gè)組的任務(wù)已經(jīng)有了實(shí)時(shí)運(yùn)行的優(yōu)先級(jí)也不行。默認(rèn)情況下，所有的CPU時(shí)間都被分給root組，如果想分CPU時(shí)間給別的組，就要減少root組的配額然后把空出的CPU時(shí)間分給別的組。

1.3 控制組調(diào)度

控制組調(diào)度可以讓管理員隨意對(duì)系統(tǒng)中的任務(wù)分組，它是基于控制組虛擬文件系統(tǒng)來實(shí)現(xiàn)的。控制組在以下方面對(duì)內(nèi)核做了擴(kuò)展：

1) 組內(nèi)每個(gè)任務(wù)有對(duì)css_set引用計(jì)數(shù)的指針；

2) css_set包含一系列對(duì)子系統(tǒng)狀態(tài)的引用計(jì)數(shù)指針。為了提高性能，沒有從任務(wù)到某個(gè)層次中某個(gè)控制組的直接鏈接，但是可以用這些指針找到控制組。

3) 控制組的文件系統(tǒng)可以被加載或者從用戶空間操縱。

4) 可以列出控制組中所有的任務(wù)。

5) 啟動(dòng)后系統(tǒng)擁有初始的根控制組和css_set

6) 用建立和解除與css_set的聯(lián)系來完成fork和exit操作。

在cgroup.h文件中定義了cgroup如下：

控制組調(diào)度引入了子系統(tǒng)和層次兩個(gè)概念，可以把一系列任務(wù)、子任務(wù)聚合或分割到設(shè)定了定制行為的組中。

子系統(tǒng)：一個(gè)子系統(tǒng)是一個(gè)模塊，利用控制組功能提供的分組工具，為控制組內(nèi)的任務(wù)調(diào)度資源或者實(shí)現(xiàn)針對(duì)該分組的某些資源占用限制。為了簡單也可以把一個(gè)子系統(tǒng)理解為一個(gè)組。

層次：指位于樹中同一層的多個(gè)控制組，每個(gè)任務(wù)必定屬于某個(gè)控制組。

每個(gè)子系統(tǒng)有系統(tǒng)指定的狀態(tài)，與層次中的每個(gè)控制組聯(lián)接。每個(gè)層次有一個(gè)組虛擬文件系統(tǒng)（VFS）的實(shí)例和它自己聯(lián)接。

可以舉例來說明子系統(tǒng)和層次之間的關(guān)系。服務(wù)器上有幾種不同的用戶：學(xué)生、教授和系統(tǒng)任務(wù)。那么cpu資源可以如下規(guī)劃：把cpu資源分為兩個(gè)層，頂層是top CPU set，第二層有兩個(gè)cpuset，分別是cpuset1和cpuset2。

圖1 子系統(tǒng)和層次關(guān)系

系統(tǒng)任務(wù)被聯(lián)系在頂層的 cputset，可能會(huì)在任何 cpu時(shí)間運(yùn)行，上限是20%的cpu時(shí)間。其他資源的分配如下：

內(nèi)存：教授50%，學(xué)生30%，系統(tǒng)20%

磁盤：教授50%，學(xué)生30%，系統(tǒng)20%

網(wǎng)絡(luò)：WWW瀏覽20%，NFS網(wǎng)絡(luò)文件服務(wù)60%，其他20%；WWW中教授15%，學(xué)生5%

瀏覽器進(jìn)程歸入WWW的網(wǎng)絡(luò)組，nfs文件訪問進(jìn)程歸入NFS網(wǎng)絡(luò)組；瀏覽器會(huì)依據(jù)打開瀏覽器的是教授還是學(xué)生來分享適當(dāng)比例的CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)資源。

然后可以回頭看一下sched.c中task_group的定義，不難理解其中針對(duì)每種調(diào)度方式的變量設(shè)置：

2 應(yīng)用

在2.6.28內(nèi)核中，增加了兩個(gè)互斥的公平組調(diào)度實(shí)現(xiàn)[2]：基于用戶 id對(duì)任務(wù)組公平調(diào)度CONFIG_FAIR_USER_SCHED和基于控制組虛擬文件系統(tǒng)對(duì)任務(wù)組公平調(diào)度CONFIG_FAIR_CGROUP_SCHED。某一時(shí)刻只能選擇其中一種方式，在運(yùn)行過程中調(diào)度參數(shù)可以調(diào)整。下面通過舉例說明公平用戶組調(diào)度和公平控制組兩種方式的使用方法：

當(dāng)內(nèi)核CONFIG_FAIR_USER_SCHED參數(shù)打開后，在/sys/kernel/uids目錄中會(huì)為每一個(gè)新用戶創(chuàng)建一個(gè)子目錄,其中有一個(gè)“cpu_share”文件。

當(dāng)內(nèi)核CONFIG_FAIR_CGROUP_SCHED參數(shù)打開后，每個(gè)用虛擬文件系統(tǒng)創(chuàng)建的用戶組都會(huì)有一個(gè)屬于自己的“cpu.shares”文件。

3 結(jié)論

通過公平組調(diào)度、實(shí)時(shí)組調(diào)度、控制組調(diào)度等幾種組調(diào)度方式，Linux內(nèi)核擴(kuò)展了進(jìn)程調(diào)度的范疇、豐富了調(diào)度的手段，能夠更出色地適應(yīng)多種應(yīng)用需求。

[1] Molnar Ingo. Modular Scheduler Core and Completely Fair Scheduler[EB/OL] .(2007-04-13).http://lkml.org/lkml/2007/4/13/180.

[2] Linux內(nèi)核文檔(2.6.27.1) [CP] . Documentation/scheduler/sched-design-CFS.txt. (2008-10-16).http://www.kernel.org.

[3] Avinesh Kumar.使用完全公平調(diào)度程序進(jìn)行多任務(wù)處理[EB/OL] .(2008-02-04).http://www.ibm.com/developerwor ks/cn/linux/l-cfs/index.html.

[4] Linux內(nèi)核源代碼(2.6.27.1) [CP] . (2008-10-16).http://lxr.linux.no/linux/init/Kconfig.