楊沙洲
國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院, 2004 年 4 月
2004 年 4 月

本文從 Linux 2.4 調(diào)度系統(tǒng)的缺陷入手，詳細(xì)分析了 Linux 2.6 調(diào)度系統(tǒng)的原理和實(shí)現(xiàn)細(xì)節(jié)，并對(duì)與調(diào)度系統(tǒng)相關(guān)的負(fù)載平衡、NUMA 結(jié)構(gòu)以及實(shí)時(shí)性能進(jìn)行了分析和評(píng)價(jià)。文末，作者從調(diào)度系統(tǒng)的發(fā)展和實(shí)現(xiàn)出發(fā)，對(duì) Linux 的發(fā)展特點(diǎn)和方向提出了自己的看法。

1． 前言
Linux 的市場(chǎng)非常廣闊，從桌面工作站到低端服務(wù)器，它都是任何商用操作系統(tǒng)的有力競(jìng)爭(zhēng)對(duì)手。目前，Linux 正全力進(jìn)軍嵌入式系統(tǒng)和高端服務(wù)器系統(tǒng)領(lǐng)域，但它的技術(shù)缺陷限制了它的競(jìng)爭(zhēng)力：缺乏對(duì)實(shí)時(shí)任務(wù)的支持，多處理機(jī)可擴(kuò)展性差。在 2.4 內(nèi)核中，造成這兩個(gè)弱項(xiàng)的關(guān)鍵原因之一就是調(diào)度器設(shè)計(jì)上的缺陷。

2.6 調(diào)度系統(tǒng)從設(shè)計(jì)之初就把開(kāi)發(fā)重點(diǎn)放在更好滿足實(shí)時(shí)性和多處理機(jī)并行性上，并且基本實(shí)現(xiàn)了它的設(shè)計(jì)目標(biāo)。主要設(shè)計(jì)者，傳奇式人物 Ingo Molnar 將新調(diào)度系統(tǒng)的特性概括為如下幾點(diǎn)：

• 繼承和發(fā)揚(yáng) 2.4 版調(diào)度器的特點(diǎn)：
  • 交互式作業(yè)優(yōu)先
  • 輕載條件下調(diào)度/喚醒的高性能
  • 公平共享
  • 基于優(yōu)先級(jí)調(diào)度
  • 高 CPU 使用率
  • SMP 高效親和
  • 實(shí)時(shí)調(diào)度和 cpu 綁定等調(diào)度手段
• 在此基礎(chǔ)之上的新特性：
  • O(1)調(diào)度算法，調(diào)度器開(kāi)銷恒定（與當(dāng)前系統(tǒng)負(fù)載無(wú)關(guān)），實(shí)時(shí)性能更好
  • 高可擴(kuò)展性，鎖粒度大幅度減小
  • 新設(shè)計(jì)的 SMP 親和方法
  • 優(yōu)化計(jì)算密集型的批處理作業(yè)的調(diào)度
  • 重載條件下調(diào)度器工作更平滑
  • 子進(jìn)程先于父進(jìn)程運(yùn)行等其他改進(jìn)

在 2.5.x 的試驗(yàn)版本中，新的調(diào)度器的開(kāi)發(fā)一直受到廣泛關(guān)注，實(shí)測(cè)證明它的確使系統(tǒng)性能得到很大改善。本文就從新設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)開(kāi)始，圍繞 2.6 對(duì)于 2.4 所作的改進(jìn)，對(duì) 2.6 調(diào)度系統(tǒng)的原理和實(shí)現(xiàn)細(xì)節(jié)進(jìn)行分析。2.6 調(diào)度器設(shè)計(jì)相當(dāng)復(fù)雜，文中還存在很多需要繼續(xù)研究的地方，特別是各個(gè)調(diào)度參數(shù)的設(shè)定，隨著核心版本的升級(jí)，可能還會(huì)繼續(xù)修正。

2． 新的數(shù)據(jù)結(jié)構(gòu) runqueue
我們知道，在 2.4 內(nèi)核中，就緒進(jìn)程隊(duì)列是一個(gè)全局?jǐn)?shù)據(jù)結(jié)構(gòu)，調(diào)度器對(duì)它的所有操作都會(huì)因全局自旋鎖而導(dǎo)致系統(tǒng)各個(gè)處理機(jī)之間的等待，使得就緒隊(duì)列成為一個(gè)明顯的瓶頸。

2.4 的就緒隊(duì)列是一個(gè)簡(jiǎn)單的以 runqueue_head 為頭的雙向鏈表，在 2.6 中，就緒隊(duì)列定義為一個(gè)復(fù)雜得多的數(shù)據(jù)結(jié)構(gòu) struct runqueue，并且，尤為關(guān)鍵的是，每一個(gè) CPU 都將維護(hù)一個(gè)自己的就緒隊(duì)列，--這將大大減小競(jìng)爭(zhēng)。

O(1)算法中很多關(guān)鍵技術(shù)都與 runqueue 有關(guān)，所以，我們對(duì)調(diào)度器的分析就先從 runqueue 結(jié)構(gòu)開(kāi)始。

1) prio_array_t *active, *expired, arrays[2]

runqueue 中最關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。每個(gè) CPU 的就緒隊(duì)列按時(shí)間片是否用完分為兩部分，分別通過(guò) active 指針和 expired 指針訪問(wèn)，active 指向時(shí)間片沒(méi)用完、當(dāng)前可被調(diào)度的就緒進(jìn)程，expired 指向時(shí)間片已用完的就緒進(jìn)程。每一類就緒進(jìn)程都用一個(gè) struct prio_array 的結(jié)構(gòu)表示：

struct prio_array {
		int nr_active;		/* 本進(jìn)程組中的進(jìn)程數(shù) */
		struct list_head queue[MAX_PRIO];
							/* 以優(yōu)先級(jí)為索引的 HASH 表，見(jiàn)下 */
		unsigned long bitmap[BITMAP_SIZE];
							/* 加速以上 HASH 表訪問(wèn)的位圖，見(jiàn)下 */
};

圖1：active、expired 數(shù)組示例

圖中的 task 并不是 task_struct 結(jié)構(gòu)指針，而是 task_struct::run_list，這是一個(gè)小技巧，詳見(jiàn)下文 run_list 的解釋。

在 2.4 版的內(nèi)核里，查找最佳候選就緒進(jìn)程的過(guò)程是在調(diào)度器 schedule() 中進(jìn)行的，每一次調(diào)度都要進(jìn)行一次（在 for 循環(huán)中調(diào)用 goodness()），這種查找過(guò)程與當(dāng)前就緒進(jìn)程的個(gè)數(shù)相關(guān)，因此，查找所耗費(fèi)的時(shí)間是 O(n) 級(jí)的，n 是當(dāng)前就緒進(jìn)程個(gè)數(shù)。正因?yàn)槿绱?，調(diào)度動(dòng)作的執(zhí)行時(shí)間就和當(dāng)前系統(tǒng)負(fù)載相關(guān)，無(wú)法給定一個(gè)上限，這與實(shí)時(shí)性的要求相違背。

在新的 O(1) 調(diào)度中，這一查找過(guò)程分解為 n 步，每一步所耗費(fèi)的時(shí)間都是 O(1) 量級(jí)的。

prio_array 中包含一個(gè)就緒隊(duì)列數(shù)組，數(shù)組的索引是進(jìn)程的優(yōu)先級(jí)（共 140 級(jí)，詳見(jiàn)下 "static_prio" 屬性的說(shuō)明），相同優(yōu)先級(jí)的進(jìn)程放置在相應(yīng)數(shù)組元素的鏈表 queue 中。調(diào)度時(shí)直接給出就緒隊(duì)列 active 中具有最高優(yōu)先級(jí)的鏈表中的第一項(xiàng)作為候選進(jìn)程（參見(jiàn)"調(diào)度器"），而優(yōu)先級(jí)的計(jì)算過(guò)程則分布到各個(gè)進(jìn)程的執(zhí)行過(guò)程中進(jìn)行（見(jiàn)"優(yōu)化了的優(yōu)先級(jí)計(jì)算方法"）。

為了加速尋找存在就緒進(jìn)程的鏈表，2.6 核心又建立了一個(gè)位映射數(shù)組來(lái)對(duì)應(yīng)每一個(gè)優(yōu)先級(jí)鏈表，如果該優(yōu)先級(jí)鏈表非空，則對(duì)應(yīng)位為 1，否則為 0。核心還要求每個(gè)體系結(jié)構(gòu)都構(gòu)造一個(gè) sched_find_first_bit() 函數(shù)來(lái)執(zhí)行這一搜索操作，快速定位第一個(gè)非空的就緒進(jìn)程鏈表。

采用這種將集中計(jì)算過(guò)程分散進(jìn)行的算法，保證了調(diào)度器運(yùn)行的時(shí)間上限，同時(shí)在內(nèi)存中保留更加豐富的信息的做法也加速了候選進(jìn)程的定位過(guò)程。這一變化簡(jiǎn)單而又高效，是 2.6 內(nèi)核中的亮點(diǎn)之一。

arrays 二元數(shù)組是兩類就緒隊(duì)列的容器，active 和 expired 分別指向其中一個(gè)。active 中的進(jìn)程一旦用完了自己的時(shí)間片，就被轉(zhuǎn)移到 expired 中，并設(shè)置好新的初始時(shí)間片；而當(dāng) active 為空時(shí)，則表示當(dāng)前所有進(jìn)程的時(shí)間片都消耗完了，此時(shí)，active 和 expired 進(jìn)行一次對(duì)調(diào)，重新開(kāi)始下一輪的時(shí)間片遞減過(guò)程（參見(jiàn)"調(diào)度器"）。

回憶一下 2.4 調(diào)度系統(tǒng)，進(jìn)程時(shí)間片的計(jì)算是比較耗時(shí)的，在早期內(nèi)核版本中，一旦時(shí)間片耗盡，就在時(shí)鐘中斷中重新計(jì)算時(shí)間片，后來(lái)為了提高效率，減小時(shí)鐘中斷的處理時(shí)間，2.4 調(diào)度系統(tǒng)在所有就緒進(jìn)程的時(shí)間片都耗完以后在調(diào)度器中一次性重算。這又是一個(gè) O(n) 量級(jí)的過(guò)程。為了保證 O(1) 的調(diào)度器執(zhí)行時(shí)間，2.6 的時(shí)間片計(jì)算在各個(gè)進(jìn)程耗盡時(shí)間片時(shí)單獨(dú)進(jìn)行，而通過(guò)以上所述簡(jiǎn)單的對(duì)調(diào)來(lái)完成時(shí)間片的輪轉(zhuǎn)（參見(jiàn)"調(diào)度器"）。這又是 2.6 調(diào)度系統(tǒng)的一個(gè)亮點(diǎn)。

2) spinlock_t lock

runqueue 的自旋鎖，當(dāng)需要對(duì) runqueue 進(jìn)行操作時(shí)，仍然應(yīng)該鎖定，但這個(gè)鎖定操作只影響一個(gè) CPU 上的就緒隊(duì)列，因此，競(jìng)爭(zhēng)發(fā)生的概率要小多了。

3) task_t *curr

本 CPU 正在運(yùn)行的進(jìn)程。

4) tast_t *idle

指向本 CPU 的 idle 進(jìn)程，相當(dāng)于 2.4 中 init_tasks[this_cpu()] 的作用。

5) int best_expired_prio

記錄 expired 就緒進(jìn)程組中的最高優(yōu)先級(jí)（數(shù)值最?。Ｔ撟兞吭谶M(jìn)程進(jìn)入 expired 隊(duì)列的時(shí)候保存（schedule_tick()），用途見(jiàn) "expired_timestamp"的解釋）。

6) unsigned long expired_timestamp

當(dāng)新一輪的時(shí)間片遞減開(kāi)始后，這一變量記錄著最早發(fā)生的進(jìn)程耗完時(shí)間片事件的時(shí)間（jiffies 的絕對(duì)值，在 schedule_tick() 中賦），它用來(lái)表征 expired 中就緒進(jìn)程的最長(zhǎng)等待時(shí)間。它的使用體現(xiàn)在 EXPIRED_STARVING(rq) 宏上。

上面已經(jīng)提到，每個(gè) CPU 上維護(hù)了兩個(gè)就緒隊(duì)列，active 和 expired。一般情況下，時(shí)間片結(jié)束的進(jìn)程應(yīng)該從 active 隊(duì)列轉(zhuǎn)移到 expired 隊(duì)列中（schedule_tick()），但如果該進(jìn)程是交互式進(jìn)程，調(diào)度器就會(huì)讓其保持在 active 隊(duì)列上以提高它的響應(yīng)速度。這種措施不應(yīng)該讓其他就緒進(jìn)程等待過(guò)長(zhǎng)時(shí)間，也就是說(shuō)，如果 expired 隊(duì)列中的進(jìn)程已經(jīng)等待了足夠長(zhǎng)時(shí)間了，即使是交互式進(jìn)程也應(yīng)該轉(zhuǎn)移到 expired 隊(duì)列上來(lái)，排空 active。這個(gè)閥值就體現(xiàn)在EXPIRED_STARVING(rq) 上：在 expired_timestamp 和 STARVATION_LIMIT 都不等于 0 的前提下，如果以下兩個(gè)條件都滿足，則 EXPIRED_STARVING() 返回真：

• （當(dāng)前絕對(duì)時(shí)間 - expired_timestamp） >= （STARVATION_LIMIT * 隊(duì)列中所有就緒進(jìn)程總數(shù) + 1），也就是說(shuō) expired 隊(duì)列中至少有一個(gè)進(jìn)程已經(jīng)等待了足夠長(zhǎng)的時(shí)間；
• 正在運(yùn)行的進(jìn)程的靜態(tài)優(yōu)先級(jí)比 expired 隊(duì)列中最高優(yōu)先級(jí)要低（best_expired_prio，數(shù)值要大），此時(shí)當(dāng)然應(yīng)該盡快排空 active 切換到expired 上來(lái)。

7) struct mm_struct *prev_mm

保存進(jìn)程切換后被調(diào)度下來(lái)的進(jìn)程（稱之為 prev）的 active_mm 結(jié)構(gòu)指針。因?yàn)樵?2.6 中 prev 的 active_mm 是在進(jìn)程切換完成之后釋放的（mmdrop()），而此時(shí) prev 的 active_mm 項(xiàng)可能為 NULL，所以有必要在 runqueue 中預(yù)先保留。

8) unsigned long nr_running

本 CPU 上的就緒進(jìn)程數(shù)，該數(shù)值是 active 和 expired 兩個(gè)隊(duì)列中進(jìn)程數(shù)的總和，是說(shuō)明本 CPU 負(fù)載情況的重要參數(shù)（詳見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

9) unsigned long nr_switches

記錄了本 CPU 上自調(diào)度器運(yùn)行以來(lái)發(fā)生的進(jìn)程切換的次數(shù)。

10) unsigned long nr_uninterruptible

記錄本 CPU 尚處于 TASK_UNINTERRUPTIBLE 狀態(tài)的進(jìn)程數(shù)，和負(fù)載信息有關(guān)。

11) atomic_t nr_iowait

記錄本 CPU 因等待 IO 而處于休眠狀態(tài)的進(jìn)程數(shù)。

12) unsigned long timestamp_last_tick

本就緒隊(duì)列最近一次發(fā)生調(diào)度事件的時(shí)間，在負(fù)載平衡的時(shí)候會(huì)用到（見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

13) int prev_cpu_load[NR_CPUS]

記錄進(jìn)行負(fù)載平衡時(shí)各個(gè) CPU 上的負(fù)載狀態(tài)（此時(shí)就緒隊(duì)列中的 nr_running 值），以便分析負(fù)載情況（見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]

這兩個(gè)屬性僅在 NUMA 體系結(jié)構(gòu)下有效，記錄各個(gè) NUMA 節(jié)點(diǎn)上的就緒進(jìn)程數(shù)和上一次負(fù)載平衡操作時(shí)的負(fù)載情況（見(jiàn)"NUMA 結(jié)構(gòu)下的調(diào)度"）。

15) task_t *migration_thread

指向本 CPU 的遷移進(jìn)程。每個(gè) CPU 都有一個(gè)核心線程用于執(zhí)行進(jìn)程遷移操作（見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

16) struct list_head migration_queue

需要進(jìn)行遷移的進(jìn)程列表（見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

3． 改進(jìn)后的 task_struct
2.6 版的內(nèi)核仍然用 task_struct 來(lái)表征進(jìn)程，盡管對(duì)線程進(jìn)行了優(yōu)化，但線程的內(nèi)核表示仍然與進(jìn)程相同。隨著調(diào)度器的改進(jìn)，task_struct 的內(nèi)容也有了改進(jìn)，交互式進(jìn)程優(yōu)先支持、內(nèi)核搶占支持等新特性，在 task_struct 中都有所體現(xiàn)。在 task_struct 中，有的屬性是新增加的，有的屬性的值的含義發(fā)生了變化，而有的屬性僅僅是改了一下名字。

1) state
進(jìn)程的狀態(tài)仍然用 state 表示，不同的是，2.6 里的狀態(tài)常量重新定義了，以方便位操作：

/* 節(jié)選自[include/linux/sched.h] */
#define TASK_RUNNING		0
#define TASK_INTERRUPTIBLE	1
#define TASK_UNINTERRUPTIBLE	2
#define TASK_STOPPED		4
#define TASK_ZOMBIE		8
#define TASK_DEAD		16

新增加的TASK_DEAD指的是已經(jīng)退出且不需要父進(jìn)程來(lái)回收的進(jìn)程。

2) timestamp
進(jìn)程發(fā)生調(diào)度事件的時(shí)間（單位是 nanosecond，見(jiàn)下）。包括以下幾類：

• 被喚醒的時(shí)間（在 activate_task() 中設(shè)置）；
• 被切換下來(lái)的時(shí)間（schedule()）；
• 被切換上去的時(shí)間（schedule()）；
• 負(fù)載平衡相關(guān)的賦值（見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）。

從這個(gè)值與當(dāng)前時(shí)間的差值中可以分別獲得"在就緒隊(duì)列中等待運(yùn)行的時(shí)長(zhǎng)"、"運(yùn)行時(shí)長(zhǎng)"等與優(yōu)先級(jí)計(jì)算相關(guān)的信息（見(jiàn)"優(yōu)化了的優(yōu)先級(jí)計(jì)算方法"）。

3) prio
優(yōu)先級(jí)，相當(dāng)于 2.4 中 goodness() 的計(jì)算結(jié)果，在 0~MAX_PRIO-1 之間取值（MAX_PRIO 定義為 140），其中 0~MAX_RT_PRIO-1 （MAX_RT_PRIO 定義為100）屬于實(shí)時(shí)進(jìn)程范圍，MAX_RT_PRIO~MX_PRIO-1 屬于非實(shí)時(shí)進(jìn)程。數(shù)值越大，表示進(jìn)程優(yōu)先級(jí)越小。

2.6 中，動(dòng)態(tài)優(yōu)先級(jí)不再統(tǒng)一在調(diào)度器中計(jì)算和比較，而是獨(dú)立計(jì)算，并存儲(chǔ)在進(jìn)程的 task_struct 中，再通過(guò)上面描述的 priority_array 結(jié)構(gòu)自動(dòng)排序。

prio 的計(jì)算和很多因素相關(guān)，在"優(yōu)化了的優(yōu)先級(jí)計(jì)算方法"中會(huì)詳細(xì)討論。

4) static_prio
靜態(tài)優(yōu)先級(jí)，與 2.4 的 nice 值意義相同，但轉(zhuǎn)換到與 prio 相同的取值區(qū)間。

nice 值沿用 Linux 的傳統(tǒng)，在 -20 到 19 之間變動(dòng)，數(shù)值越大，進(jìn)程的優(yōu)先級(jí)越小。nice 是用戶可維護(hù)的，但僅影響非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)。2.6 內(nèi)核中不再存儲(chǔ) nice 值，而代之以 static_prio。進(jìn)程初始時(shí)間片的大小僅決定于進(jìn)程的靜態(tài)優(yōu)先級(jí)，這一點(diǎn)不論是實(shí)時(shí)進(jìn)程還是非實(shí)時(shí)進(jìn)程都一樣，不過(guò)實(shí)時(shí)進(jìn)程的static_prio 不參與優(yōu)先級(jí)計(jì)算。

nice 與 static_prio 之間的關(guān)系如下：
static_prio = MAX_RT_PRIO + nice + 20

內(nèi)核定義了兩個(gè)宏用來(lái)完成這一轉(zhuǎn)換：PRIO_TO_NICE()、NICE_TO_PRIO()。

5) activated
表示進(jìn)程因什么原因進(jìn)入就緒態(tài)，這一原因會(huì)影響到調(diào)度優(yōu)先級(jí)的計(jì)算。activated 有四個(gè)值：

• -1，進(jìn)程從 TASK_UNINTERRUPTIBLE 狀態(tài)被喚醒；
• 0，缺省值，進(jìn)程原本就處于就緒態(tài)；
• 1，進(jìn)程從 TASK_INTERRUPTIBLE 狀態(tài)被喚醒，且不在中斷上下文中；
• 2，進(jìn)程從 TASK_INTERRUPTIBLE 狀態(tài)被喚醒，且在中斷上下文中。
  activated 初值為 0，在兩個(gè)地方修改，一是在 schedule() 中，被恢復(fù)為 0，另一個(gè)就是 activate_task()，這個(gè)函數(shù)由 try_to_wake_up() 函數(shù)調(diào)用，用于激活休眠進(jìn)程：
• 如果是中斷服務(wù)程序調(diào)用的 activate_task()，也就是說(shuō)進(jìn)程由中斷激活，則該進(jìn)程最有可能是交互式的，因此，置 activated=2；否則置activated=1。
• 如果進(jìn)程是從 TASK_UNINTERRUPTIBLE 狀態(tài)中被喚醒的，則 activated=-1（在try_to_wake_up()函數(shù)中）。
  activated 變量的具體含義和使用見(jiàn)"優(yōu)化了的優(yōu)先級(jí)計(jì)算方式"。

6) sleep_avg
進(jìn)程的平均等待時(shí)間（以 nanosecond 為單位），在 0 到 NS_MAX_SLEEP_AVG 之間取值，初值為 0，相當(dāng)于進(jìn)程等待時(shí)間與運(yùn)行時(shí)間的差值。sleep_avg 所代表的含義比較豐富，既可用于評(píng)價(jià)該進(jìn)程的"交互程度"，又可用于表示該進(jìn)程需要運(yùn)行的緊迫性。這個(gè)值是動(dòng)態(tài)優(yōu)先級(jí)計(jì)算的關(guān)鍵因子，sleep_avg 越大，計(jì)算出來(lái)的進(jìn)程優(yōu)先級(jí)也越高（數(shù)值越?。Ｔ谙挛?進(jìn)程平均等待時(shí)間 sleep_avg" 中會(huì)詳細(xì)分析 sleep_avg 的變化過(guò)程。

7) interactive_credit
這個(gè)變量記錄了本進(jìn)程的"交互程度"，在 -CREDIT_LIMIT 到 CREDIT_LIMIT+1 之間取值。進(jìn)程被創(chuàng)建出來(lái)時(shí)，初值為 0，而后根據(jù)不同的條件加 1 減 1，一旦超過(guò) CREDIT_LIMIT（只可能等于 CREDIT_LIMIT+1），它就不會(huì)再降下來(lái)，表示進(jìn)程已經(jīng)通過(guò)了"交互式"測(cè)試，被認(rèn)為是交互式進(jìn)程了。interactive_credit具體的變化過(guò)程在"更精確的交互式進(jìn)程優(yōu)先"中會(huì)詳細(xì)描述。

8) nvcsw/nivcsw/cnvcsw/cnivcsw
進(jìn)程切換計(jì)數(shù)。

9) time_slice

進(jìn)程的時(shí)間片余額，相當(dāng)于 2.4 的 counter，但不再直接影響進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。在"新的運(yùn)行時(shí)間片表現(xiàn)"中專門分析了 time_slice 的行為。

10) first_time_slice

0 或 1，表示是否是第一次擁有時(shí)間片（剛創(chuàng)建的進(jìn)程）。這一變量用來(lái)判斷進(jìn)程結(jié)束時(shí)是否應(yīng)當(dāng)將自己的剩余時(shí)間片返還給父進(jìn)程（見(jiàn)"新的運(yùn)行時(shí)間片表現(xiàn)"）。

11) run_list

前面提到，優(yōu)先級(jí)數(shù)組 prio_array 結(jié)構(gòu)中按順序排列了各個(gè)優(yōu)先級(jí)下的所有進(jìn)程，但實(shí)際上數(shù)組中每一個(gè)元素都是 list_head 結(jié)構(gòu)，以它為表頭的鏈表中的每一個(gè)元素也是 list_head，其中鏈接的就是 task_struct 中的 run_list 成員。這是一個(gè)節(jié)省空間、加速訪問(wèn)的小技巧：調(diào)度器在 prio_array 中找到相應(yīng)的 run_list，然后通過(guò) run_list 在 task_struct 中的固定偏移量找到對(duì)應(yīng)的 task_struct（參見(jiàn) enqueue_task()、dequeue_task() 和 list.h 中的操作）。

12) array
記錄當(dāng)前 CPU 的活躍就緒隊(duì)列（runqueue::active）。

13) thread_info
當(dāng)前進(jìn)程的一些運(yùn)行環(huán)境信息，其中有兩個(gè)結(jié)構(gòu)成員與調(diào)度關(guān)系緊密：

• preempt_count：初值為 0 的非負(fù)計(jì)數(shù)器，大于 0 表示核心不宜被搶占；
• flags：其中有一個(gè) TIF_NEED_RESCHED 位，相當(dāng)于 2.4 中的 need_resched 屬性，如果當(dāng)前運(yùn)行中的進(jìn)程此位為 1，則表示應(yīng)該盡快啟動(dòng)調(diào)度器。

在 2.4 中，每個(gè)進(jìn)程的 task_struct 都位于該進(jìn)程核心棧的頂端（低址部分），內(nèi)核可以通過(guò)棧寄存器 ESP 輕松訪問(wèn)到當(dāng)前進(jìn)程的 task_struct。在 2.6 中，仍然需要頻繁訪問(wèn)這個(gè)名為 current 的數(shù)據(jù)結(jié)構(gòu)，但現(xiàn)在，進(jìn)程核心棧頂保存的是其中的 thread_info 屬性，而不是完整的 task_struct 了。這樣做的好處是僅將最關(guān)鍵的、訪問(wèn)最頻繁的運(yùn)行環(huán)境保存在核心棧里（仍然是兩個(gè)頁(yè)大小），而將 task_struct 大部分內(nèi)容通過(guò) thread_info::task 指針保存在棧外，以方便擴(kuò)充。thread_info 的分配方式和訪問(wèn)方式與 2.4 中的 task_struct 完全相同，現(xiàn)在的 current 需要這樣來(lái)訪問(wèn)：

/* 節(jié)選自[include/asm-i386/current.h] */
static inline struct task_struct * get_current(void)
{
	return current_thread_info()->task;
}
#define current get_current()
其中current_thread_info()定義為：
/* 節(jié)選自[include/asm-i386/thread_info.h] */
static inline struct thread_info *current_thread_info(void)
{
	struct thread_info *ti;
	__asm__("andl %%esp,%0; ":"=r" (ti) : "0" (~8191UL));
	return ti;
}

圖2：現(xiàn)在的current

4． 新的運(yùn)行時(shí)間片表現(xiàn)
2.6 中，time_slice 變量代替了 2.4 中的 counter 變量來(lái)表示進(jìn)程剩余運(yùn)行時(shí)間片。time_slice 盡管擁有和 counter 相同的含義，但在內(nèi)核中的表現(xiàn)行為已經(jīng)大相徑庭，下面分三個(gè)方面討論新的運(yùn)行時(shí)間片表現(xiàn)：

1) time_slice 基準(zhǔn)值
和 counter 類似，進(jìn)程的缺省時(shí)間片與進(jìn)程的靜態(tài)優(yōu)先級(jí)（在 2.4 中是 nice 值）相關(guān)，使用如下公式得出：

			MIN_TIMESLICE + 	((MAX_TIMESLICE - MIN_TIMESLICE) * 
			(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1))
			

代入各個(gè)宏的值后，結(jié)果如圖所示：

可見(jiàn)，核心將 100~139 的優(yōu)先級(jí)映射到 200ms~10ms 的時(shí)間片上去，優(yōu)先級(jí)數(shù)值越大，則分配的時(shí)間片越小。

和 2.4 中進(jìn)程的缺省時(shí)間片比較，當(dāng) nice 為 0 時(shí)，2.6 的基準(zhǔn)值 100ms 要大于 2.4 的 60ms。

2) time_slice 的變化
進(jìn)程的 time_slice 值代表進(jìn)程的運(yùn)行時(shí)間片剩余大小，在進(jìn)程創(chuàng)建時(shí)與父進(jìn)程平分時(shí)間片，在運(yùn)行過(guò)程中遞減，一旦歸 0，則按 static_prio 值重新賦予上述基準(zhǔn)值，并請(qǐng)求調(diào)度。時(shí)間片的遞減和重置在時(shí)鐘中斷中進(jìn)行（sched_tick()），除此之外，time_slice 值的變化主要在創(chuàng)建進(jìn)程和進(jìn)程退出過(guò)程中：

a) 進(jìn)程創(chuàng)建
和 2.4 類似，為了防止進(jìn)程通過(guò)反復(fù) fork 來(lái)偷取時(shí)間片，子進(jìn)程被創(chuàng)建時(shí)并不分配自己的時(shí)間片，而是與父進(jìn)程平分父進(jìn)程的剩余時(shí)間片。也就是說(shuō)，fork 結(jié)束后，兩者時(shí)間片之和與原先父進(jìn)程的時(shí)間片相等。

b) 進(jìn)程退出
進(jìn)程退出時(shí)（sched_exit()），根據(jù) first_time_slice 的值判斷自己是否從未重新分配過(guò)時(shí)間片，如果是，則將自己的剩余時(shí)間片返還給父進(jìn)程（保證不超過(guò) MAX_TIMESLICE）。這個(gè)動(dòng)作使進(jìn)程不會(huì)因創(chuàng)建短期子進(jìn)程而受到懲罰（與不至于因創(chuàng)建子進(jìn)程而受到"獎(jiǎng)勵(lì)"相對(duì)應(yīng)）。如果進(jìn)程已經(jīng)用完了從父進(jìn)程那分得的時(shí)間片，就沒(méi)有必要返還了（這一點(diǎn)在 2.4 中沒(méi)有考慮）。

3) time_slice 對(duì)調(diào)度的影響
在 2.4 中，進(jìn)程剩余時(shí)間片是除 nice 值以外對(duì)動(dòng)態(tài)優(yōu)先級(jí)影響最大的因素，并且休眠次數(shù)多的進(jìn)程，它的時(shí)間片會(huì)不斷疊加，從而算出的優(yōu)先級(jí)也更大，調(diào)度器正是用這種方式來(lái)體現(xiàn)對(duì)交互式進(jìn)程的優(yōu)先策略。但實(shí)際上休眠次數(shù)多并不表示該進(jìn)程就是交互式的，只能說(shuō)明它是 IO 密集型的，因此，這種方法精度很低，有時(shí)因?yàn)檎`將頻繁訪問(wèn)磁盤的數(shù)據(jù)庫(kù)應(yīng)用當(dāng)作交互式進(jìn)程，反而造成真正的用戶終端響應(yīng)遲緩。

2.6 的調(diào)度器以時(shí)間片是否耗盡為標(biāo)準(zhǔn)將就緒進(jìn)程分成 active、expired 兩大類，分別對(duì)應(yīng)不同的就緒隊(duì)列，前者相對(duì)于后者擁有絕對(duì)的調(diào)度優(yōu)先權(quán)--僅當(dāng)active 進(jìn)程時(shí)間片都耗盡，expired 進(jìn)程才有機(jī)會(huì)運(yùn)行。但在 active 中挑選進(jìn)程時(shí)，調(diào)度器不再將進(jìn)程剩余時(shí)間片作為影響調(diào)度優(yōu)先級(jí)的一個(gè)因素，并且為了滿足內(nèi)核可剝奪的要求，時(shí)間片太長(zhǎng)的非實(shí)時(shí)交互式進(jìn)程還會(huì)被人為地分成好幾段（每一段稱為一個(gè)運(yùn)行粒度，定義見(jiàn)下）運(yùn)行，每一段運(yùn)行結(jié)束后，它都從 cpu 上被剝奪下來(lái)，放置到對(duì)應(yīng)的 active 就緒隊(duì)列的末尾，為其他具有同等優(yōu)先級(jí)的進(jìn)程提供運(yùn)行的機(jī)會(huì)。

這一操作在 schedule_tick() 對(duì)時(shí)間片遞減之后進(jìn)行。此時(shí)，即使進(jìn)程的時(shí)間片沒(méi)耗完，只要該進(jìn)程同時(shí)滿足以下四個(gè)條件，它就會(huì)被強(qiáng)制從 cpu 上剝奪下來(lái)，重新入隊(duì)等候下一次調(diào)度：

• 進(jìn)程當(dāng)前在 active 就緒隊(duì)列中；
• 該進(jìn)程是交互式進(jìn)程（TASK_INTERACTIVE()返回真，見(jiàn)"更精確的交互式進(jìn)程優(yōu)先",nice 大于 12 時(shí)，該宏返回恒假）；
• 該進(jìn)程已經(jīng)耗掉的時(shí)間片（時(shí)間片基準(zhǔn)值減去剩余時(shí)間片）正好是運(yùn)行粒度的整數(shù)倍；
• 剩余時(shí)間片不小于運(yùn)行粒度

5． 優(yōu)化了的優(yōu)先級(jí)計(jì)算方法
在 2.4 內(nèi)核中，優(yōu)先級(jí)的計(jì)算和候選進(jìn)程的選擇集中在調(diào)度器中進(jìn)行，無(wú)法保證調(diào)度器的執(zhí)行時(shí)間，這一點(diǎn)在前面介紹 runqueue 數(shù)據(jù)結(jié)構(gòu)的時(shí)候已經(jīng)提及。2.6 內(nèi)核中候選進(jìn)程是直接從已按算法排序的優(yōu)先級(jí)隊(duì)列數(shù)組中選取出來(lái)的，而優(yōu)先級(jí)的計(jì)算則分散到多處進(jìn)行。這一節(jié)分成兩個(gè)部分對(duì)這種新的優(yōu)先級(jí)計(jì)算方法進(jìn)行描述，一部分是優(yōu)先級(jí)計(jì)算過(guò)程，一部分是優(yōu)先級(jí)計(jì)算（以及進(jìn)程入隊(duì)）的時(shí)機(jī)。

1) 優(yōu)先級(jí)計(jì)算過(guò)程
動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算主要由 effect_prio() 函數(shù)完成，該函數(shù)實(shí)現(xiàn)相當(dāng)簡(jiǎn)單，從中可見(jiàn)非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)僅決定于靜態(tài)優(yōu)先級(jí)（static_prio）和進(jìn)程的sleep_avg 值兩個(gè)因素，而實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)實(shí)際上是在 setscheduler() 中設(shè)置的（詳見(jiàn)"調(diào)度系統(tǒng)的實(shí)時(shí)性能"，以下僅考慮非實(shí)時(shí)進(jìn)程），且一經(jīng)設(shè)定就不再改變。相比較而言，2.4 的 goodness() 函數(shù)甚至要更加復(fù)雜,它考慮的 CPU Cache 失效開(kāi)銷和內(nèi)存切換的開(kāi)銷這里都已經(jīng)不再考慮。

2.6 的動(dòng)態(tài)優(yōu)先級(jí)算法的實(shí)現(xiàn)關(guān)鍵在 sleep_avg 變量上，在 effective_prio() 中，sleep_avg 的范圍是 0~MAX_SLEEP_AVG，經(jīng)過(guò)以下公式轉(zhuǎn)換后變成-MAX_BONUS/2~MAX_BONUS/2 之間的 bonus：

(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG) - MAX_BONUS/2

如下圖所示：

再用這個(gè) bonus 去減靜態(tài)優(yōu)先級(jí)就得到進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)（并限制在 MAX_RT_PRIO和MAX_PRIO 之間），bonus 越小，動(dòng)態(tài)優(yōu)先級(jí)數(shù)值越大，優(yōu)先級(jí)越低。也就是說(shuō)，sleep_avg 越大，優(yōu)先級(jí)也越高。

MAX_BONUS 定義為 MAX_USER_PRIO*PRIO_BONUS_RATIO/100，也就是說(shuō)，sleep_avg 對(duì)動(dòng)態(tài)優(yōu)先級(jí)的影響僅在靜態(tài)優(yōu)先級(jí)的用戶優(yōu)先級(jí)區(qū)（100~140）的1/4區(qū)間（±5）之內(nèi)，相對(duì)而言，靜態(tài)優(yōu)先級(jí)，也就是用戶指定的 nice 值在優(yōu)先級(jí)計(jì)算的比重要大得多。這也是 2.6 調(diào)度系統(tǒng)中變化比較大的一個(gè)地方，調(diào)度器傾向于更多地由用戶自行設(shè)計(jì)進(jìn)程的執(zhí)行優(yōu)先級(jí)。

sleep_avg 反映了調(diào)度系統(tǒng)的兩個(gè)策略：交互式進(jìn)程優(yōu)先和分時(shí)系統(tǒng)的公平共享，在下一節(jié)中我們還要專門分析。

2) 優(yōu)先級(jí)計(jì)算時(shí)機(jī)
優(yōu)先級(jí)的計(jì)算不再集中在調(diào)度器選擇候選進(jìn)程的時(shí)候進(jìn)行了，只要進(jìn)程狀態(tài)發(fā)生改變，核心就有可能計(jì)算并設(shè)置進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)：

a) 創(chuàng)建進(jìn)程

在wake_up_forked_process()中，子進(jìn)程繼承了父進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)，并添加到父進(jìn)程所在的就緒隊(duì)列中。

如果父進(jìn)程不在任何就緒隊(duì)列中（例如它是 IDLE 進(jìn)程），那么就通過(guò) effect_prio() 函數(shù)計(jì)算出子進(jìn)程的優(yōu)先級(jí)，而后根據(jù)計(jì)算結(jié)果將子進(jìn)程放置到相應(yīng)的就緒隊(duì)列中。

b) 喚醒休眠進(jìn)程

核心調(diào)用 recalc_task_prio() 設(shè)置從休眠狀態(tài)中醒來(lái)的進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)，再根據(jù)優(yōu)先級(jí)放置到相應(yīng)就緒隊(duì)列中。

c) 調(diào)度到從 TASK_INTERRUPTIBLE 狀態(tài)中被喚醒的進(jìn)程

實(shí)際上此時(shí)調(diào)度器已經(jīng)選定了候選進(jìn)程，但考慮到這一類型的進(jìn)程很有可能是交互式進(jìn)程，因此此時(shí)仍然調(diào)用 recalc_task_prio() 對(duì)該進(jìn)程的優(yōu)先級(jí)進(jìn)行修正（詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"），修正的結(jié)果將在下一次調(diào)度時(shí)體現(xiàn)。

d) 進(jìn)程因時(shí)間片相關(guān)的原因被剝奪 cpu

在 schedule_tick() 中（由時(shí)鐘中斷啟動(dòng)），進(jìn)程可能因兩種原因被剝奪 cpu，一是時(shí)間片耗盡，一是因時(shí)間片過(guò)長(zhǎng)而分段。這兩種情況都會(huì)調(diào)用effect_prio() 重新計(jì)算優(yōu)先級(jí)，重新入隊(duì)。

e) 其它時(shí)機(jī)

這些其它時(shí)機(jī)包括 IDLE 進(jìn)程初始化（init_idle()）、負(fù)載平衡（move_task_away()，詳見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）以及修改 nice 值（set_user_nice()）、修改調(diào)度策略（setscheduler()）等主動(dòng)要求改變優(yōu)先級(jí)的情況。

由上可見(jiàn)，2.6 中動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算過(guò)程在各個(gè)進(jìn)程運(yùn)行過(guò)程中進(jìn)行，避免了類似 2.4 系統(tǒng)中就緒進(jìn)程很多時(shí)計(jì)算過(guò)程耗時(shí)過(guò)長(zhǎng)，從而無(wú)法預(yù)計(jì)進(jìn)程的響應(yīng)時(shí)間的問(wèn)題。同時(shí)，影響動(dòng)態(tài)優(yōu)先級(jí)的因素集中反映在 sleep_avg 變量上。

6． 進(jìn)程平均等待時(shí)間 sleep_avg
進(jìn)程的 sleep_avg 值是決定進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)的關(guān)鍵，也是進(jìn)程交互程度評(píng)價(jià)的關(guān)鍵，它的設(shè)計(jì)是 2.6 調(diào)度系統(tǒng)中最為復(fù)雜的一個(gè)環(huán)節(jié)，可以說(shuō)，2.6 調(diào)度系統(tǒng)的性能改進(jìn)，很大一部分應(yīng)該歸功于 sleep_avg 的設(shè)計(jì)。這一節(jié)，我們將專門針對(duì) sleep_avg 的變化和它對(duì)調(diào)度的影響進(jìn)行分析。

內(nèi)核中主要有四個(gè)地方會(huì)對(duì) sleep_avg 進(jìn)行修改：休眠進(jìn)程被喚醒時(shí)（activate_task()調(diào)用 recalc_task_prio() 函數(shù)）、TASK_INTERRUPTIBLE 狀態(tài)的進(jìn)程被喚醒后第一次調(diào)度到（schedule()中調(diào)用 recalc_task_prio()）、進(jìn)程從 CPU 上被剝奪下來(lái)（schedule()函數(shù)中）、進(jìn)程創(chuàng)建和進(jìn)程退出，其中recalc_task_prio() 是其中復(fù)雜度最高的，它通過(guò)計(jì)算進(jìn)程的等待時(shí)間（或者是在休眠中等待，或者是在就緒隊(duì)列中等待）對(duì)優(yōu)先級(jí)的影響來(lái)重置優(yōu)先級(jí)。

1) 休眠進(jìn)程被喚醒時(shí)
此時(shí) activate_task() 以喚醒的時(shí)間作為參數(shù)調(diào)用 recalc_task_prio()，計(jì)算休眠等待的時(shí)間對(duì)優(yōu)先級(jí)的影響。

在 recalc_task_prio() 中，sleep_avg 可能有四種賦值，并最終都限制在 NS_MAX_SLEEP_AVG 以內(nèi)：

a) 不變

從 TASK_UNINTERRUPTIBLE 狀態(tài)中被喚醒（activated==-1）、交互程度不夠高（!HIGH_CREDIT(p)）的用戶進(jìn)程(p->mm!=NULL)），如果它的 sleep_avg 已經(jīng)不小于 INTERACTIVE_SLEEP(p) 了，則它的 sleep_avg 不會(huì)因本次等待而改變。

b) INTERACTIVE_SLEEP(p)

從 TASK_UNINTERRUPTIBLE 狀態(tài)中被喚醒（activated==-1）、交互程度不夠高（!HIGH_CREDIT(p)）的用戶進(jìn)程(p->mm!=NULL)），如果它的 sleep_avg 沒(méi)有達(dá)到 INTERACTIVE_SLEEP(p)，但如果加上本次休眠時(shí)間 sleep_time 就達(dá)到了，則它的 sleep_avg 就等于 INTERACTIVE_SLEEP(p)。

c) MAX_SLEEP_AVG-AVG_TIMESLICE

用戶進(jìn)程(p->mm!=NULL)，如果不是從 TASK_UNINTERRUPTIBLE 休眠中被喚醒的（p->activated!=-1），且本次等待的時(shí)間（sleep_time）已經(jīng)超過(guò)了 INTERACTIVE_SLEEP(p)，則它的 sleep_avg 置為 JIFFIES_TO_NS(MAX_SLEEP_AVG-AVG_TIMESLICE)。

d) sleep_avg+sleep_time

如果不滿足上面所有情況，則將 sleep_time 疊加到 sleep_avg 上。此時(shí)，sleep_time 要經(jīng)過(guò)兩次修正：

i. 根據(jù) sleep_avg 的值進(jìn)行修正，sleep_avg 越大，修正后的 sleep_time 越?。?/p>

		sleep_time = 
sleep_time * MAX_BONUS * (1-NS_TO_JIFFIES(sleep_avg)/MAX_SLEEP_AVG)

ii. 如果進(jìn)程交互程度很低（LOW_CREDIT()返回真，見(jiàn)"更精確的交互式進(jìn)程優(yōu)先"），則將 sleep_time 限制在進(jìn)程的基準(zhǔn)時(shí)間片以內(nèi)，以此作為對(duì) cpu-bound 的進(jìn)程的優(yōu)先級(jí)懲罰。

總的來(lái)說(shuō)，本次等待時(shí)間越長(zhǎng)，sleep_avg 就應(yīng)該更大，但核心排除了兩種情況：

• 從 TASK_UNINTERRUPTIBLE 狀態(tài)醒來(lái)的進(jìn)程，尤其是那些休眠時(shí)間比較長(zhǎng)的進(jìn)程，很有可能是等待某種資源而休眠，它們不應(yīng)該受到等待時(shí)間的優(yōu)先級(jí)獎(jiǎng)勵(lì)，它的 sleep_avg 被限制在 INTERACTIVE_SLEEP(p) 范圍內(nèi)（或不超過(guò)太多）（INTERACTIVE_SLEEP(p) 的含義見(jiàn)后），--這一限制對(duì)已經(jīng)認(rèn)定為是交互式的進(jìn)程無(wú)效。
• 不是從 TASK_UNITERRUPTIBLE 狀態(tài)中醒來(lái)的進(jìn)程，如果本次等待時(shí)間過(guò)長(zhǎng)，也不應(yīng)該受到等待時(shí)間的優(yōu)先級(jí)獎(jiǎng)勵(lì)。

NS_TO_JIFFIES(INTERACTIVE_SLEEP(p))=
TASK_NICE(p)*MAX_SLEEP_AVG/40+ 
(INTERACTIVE_DELTA+1+MAX_BONUS/2)*MAX_SLEEP_AVG/MAX_BONUS -1

2) TASK_INTERRUPTIBLE 狀態(tài)的進(jìn)程被喚醒后第一次被調(diào)度到時(shí)
調(diào)度器挑選出候選進(jìn)程之后，如果發(fā)現(xiàn)它是從 TASK_INTERRUPTIBLE 休眠中醒來(lái)后第一次被調(diào)度到（activated>0），調(diào)度器將根據(jù)它在就緒隊(duì)列上等待的時(shí)長(zhǎng)調(diào)用 recalc_task_prio() 重新調(diào)整進(jìn)程的 sleep_avg。

recalc_task_prio() 調(diào)整的過(guò)程與"休眠進(jìn)程被喚醒時(shí)"的情況是一模一樣的，所不同的是，此時(shí)作為等待時(shí)間 sleep_time 參與計(jì)算的不是進(jìn)程的休眠時(shí)間，而是進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間。并且，如果進(jìn)程不是被中斷喚醒的（activated==1），sleep_time 還將受到約束（delta=delta*ON_RUNQUEUE_WEIGHT/100），因?yàn)榇藭r(shí)該進(jìn)程不是交互式進(jìn)程的可能性很大。從上面對(duì) recalc_task_prio() 的分析可知，sleep_time 減小一般來(lái)說(shuō)就意味著優(yōu)先級(jí)會(huì)相應(yīng)降低，所以，這一獎(jiǎng)勵(lì)說(shuō)明調(diào)度器在進(jìn)一步減小進(jìn)程的響應(yīng)時(shí)間，尤其是交互式進(jìn)程。

3) 被切換下來(lái)的進(jìn)程
前面說(shuō)過(guò)，sleep_avg 是進(jìn)程的"平均"等待時(shí)間，recalc_task_prio() 計(jì)算了等待時(shí)間，在 schedule() 中，被切換下來(lái)的進(jìn)程的 sleep_avg 需要減去進(jìn)程本次運(yùn)行的時(shí)間 run_time（并保證結(jié)果不小于 0），這就是對(duì)"平均"的體現(xiàn)：等待得越久，sleep_avg 越大，進(jìn)程越容易被調(diào)度到；而運(yùn)行得越久，sleep_avg 越小，進(jìn)程越不容易調(diào)度到。

run_time 可以用系統(tǒng)當(dāng)前時(shí)間與進(jìn)程 timestamp（上一次被調(diào)度運(yùn)行的時(shí)間）的差值表示，但不能超過(guò) NS_MAX_SLEEP_AVG。對(duì)于交互式進(jìn)程（HIGHT_CREDIT(p) 為真，見(jiàn)"更精確的交互式進(jìn)程優(yōu)先"），run_time 還要根據(jù) sleep_avg 的值進(jìn)行調(diào)整：

run_time = run_time / (sleep_avg*MAX_BONUS/MAX_SLEEP_AVG)

這樣調(diào)整的結(jié)果是交互式進(jìn)程的 run_time 小于實(shí)際運(yùn)行時(shí)間，sleep_avg 越大，則 run_time 減小得越多，因此被切換下來(lái)的進(jìn)程最后計(jì)算所得的 sleep_avg 也就越大，動(dòng)態(tài)優(yōu)先級(jí)也隨之變大。交互式進(jìn)程可以借此獲得更多被執(zhí)行的機(jī)會(huì)。

4) fork 后
在 wake_up_forked_process() 中，父進(jìn)程的 sleep_avg 要乘以 PARENT_PENALTY/100，而子進(jìn)程的 sleep_avg 則乘以 CHILD_PENALTY/100。實(shí)際上PARENT_PENALTY 為 100，CHILD_PENALTY 等于 95，也就是說(shuō)父進(jìn)程的 sleep_avg 不會(huì)變，而子進(jìn)程從父進(jìn)程處繼承過(guò)來(lái)的 sleep_avg 會(huì)減小 5%，因此子進(jìn)程最后的優(yōu)先級(jí)會(huì)比父進(jìn)程稍低（但子進(jìn)程仍然會(huì)置于與父進(jìn)程相同的就緒隊(duì)列上，位置在父進(jìn)程之前--也就是"前言"所說(shuō)"子進(jìn)程先于父進(jìn)程運(yùn)行"）。

5) 進(jìn)程退出時(shí)
一個(gè)進(jìn)程結(jié)束運(yùn)行時(shí)，如果它的交互程度比父進(jìn)程低（sleep_avg 較小），那么核心將在 sched_exit() 中對(duì)其父進(jìn)程的 sleep_avg 進(jìn)行調(diào)整，調(diào)整公式如下（以 child_sleep_avg 表示子進(jìn)程的 sleep_avg）：

sleep_avg= 
sleep_avg*EXIT_WEIGHT/(EXIT_WEIGHT+1) + child_sleep_avg/(EXIT_WEIGHT+1)

其中 EXIT_WEIGHT 等于 3，所以父進(jìn)程的 sleep_avg 將減少自身 sleep_avg 的 1/4，再補(bǔ)償子進(jìn)程 sleep_avg 的 1/4，優(yōu)先級(jí)也將隨之有所下降，子進(jìn)程的交互程度與父進(jìn)程相差越大，則優(yōu)先級(jí)的懲罰也越明顯。

利用進(jìn)程平均等待時(shí)間來(lái)衡量進(jìn)程的優(yōu)先級(jí)，使得宏觀上相同靜態(tài)優(yōu)先級(jí)的所有進(jìn)程的等待時(shí)間和運(yùn)行時(shí)間的比值趨向一致，反映了 Linux 要求各進(jìn)程分時(shí)共享 cpu 的公平性。另一方面，sleep_avg 還是進(jìn)程交互式程度的衡量標(biāo)準(zhǔn)。

7． 更精確的交互式進(jìn)程優(yōu)先
交互式進(jìn)程優(yōu)先策略的實(shí)際效果在 2.4 內(nèi)核中受到廣泛批評(píng)，在 2.6 內(nèi)核中，這一點(diǎn)得到了很大改進(jìn)，總體來(lái)說(shuō)，內(nèi)核有四處對(duì)交互式進(jìn)程的優(yōu)先考慮：

1) sleep_avg
上文已經(jīng)詳細(xì)分析了 sleep_avg 對(duì)進(jìn)程優(yōu)先級(jí)的影響，從中可以看出，交互式進(jìn)程因?yàn)樾菝叽螖?shù)多、時(shí)間長(zhǎng)，它們的 sleep_avg 也會(huì)相應(yīng)地更大一些，所以計(jì)算出來(lái)的優(yōu)先級(jí)也會(huì)相應(yīng)高一些。

2) interactive_credit
系統(tǒng)引入了一個(gè) interactive_credit 的進(jìn)程屬性（見(jiàn)"改進(jìn)后的 task_struct"），用來(lái)表征該進(jìn)程是否是交互式進(jìn)程：只要 interactive_credit 超過(guò)了 CREDIT_LIMIT 的閥值（HIGH_CREDIT()返回真），該進(jìn)程就被認(rèn)為是交互式進(jìn)程。

interactive_credit 的初始值為 0，在兩種情況下它會(huì)加 1，這兩種場(chǎng)合都在 recalc_task_prio() 函數(shù)中：

• 用戶進(jìn)程(p->mm!=NULL)，如果不是從 TASK_UNINTERRUPTIBLE 休眠中被喚醒的（p->activated!=-1），且等待的時(shí)間（包括在休眠中等待和在就緒隊(duì)列中等待，）超過(guò)了一定限度（sleep_time>INTERACTIVE_SLEEP(p)）；
• 除以上情況外，sleep_avg 經(jīng)過(guò) sleep_time 調(diào)整后，如果大于 NS_MAX_SLEEP_AVG。

無(wú)論哪種情況，一旦 interactive_credit 超過(guò)（大于）CREDIT_LIMIT 了，它都不再增加，因此 interactive_credit 最大值就是 CREDIT_LIMIT+1。

interactive_credit 的遞減發(fā)生在 schedule() 函數(shù)中。當(dāng)調(diào)度器用運(yùn)行時(shí)間修正被切換下來(lái)的進(jìn)程的 sleep_avg 之后，如果 sleep_avg 小于等于 0，且interactive_credit 在 -CREDIT_LIMIT 和 CREDIT_LIMIT 之間（-100<=interactive_credit<=100），則 interactive_credit 減 1。可見(jiàn)interactive_credit 最小值為 -101，且一旦它達(dá)到 CREDIT_LIMIT+1 的最大值就不會(huì)再被減下來(lái)--它將保持在 CREDIT_LIMIT+1 的高值上。

這就是說(shuō)，只有進(jìn)程多次休眠，且休眠的時(shí)間足夠長(zhǎng)（長(zhǎng)于運(yùn)行的時(shí)間，長(zhǎng)于"交互式休眠"時(shí)間），進(jìn)程才有可能被列為交互式進(jìn)程；而一旦被認(rèn)為是交互式進(jìn)程，則永遠(yuǎn)按交互式進(jìn)程對(duì)待。

采用 HIGH_CREDIT() 標(biāo)準(zhǔn)斷言的交互式進(jìn)程主要在以下兩處得到優(yōu)先級(jí)計(jì)算上的獎(jiǎng)勵(lì)：

• 當(dāng)進(jìn)程從 cpu 上調(diào)度下來(lái)的時(shí)侯，如果是交互式進(jìn)程，則它參與優(yōu)先級(jí)計(jì)算的運(yùn)行時(shí)間會(huì)比實(shí)際運(yùn)行時(shí)間小，以此獲得較高的優(yōu)先級(jí)（見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"）；
• 交互式進(jìn)程處于 TASK_UNINTERRUPTIBLE 狀態(tài)下的休眠時(shí)間也會(huì)疊加到 sleep_avg 上，從而獲得優(yōu)先級(jí)獎(jiǎng)勵(lì)（見(jiàn)"進(jìn)程平均等待時(shí)間sleep_avg"）；

3) TASK_INTERACTIVE()
核心另有一處不采用 HIGH_CREDIT() 這種累積方式來(lái)判斷的交互式進(jìn)程優(yōu)先機(jī)制，那里使用的是 TASK_INTERACTIVE() 宏（布爾值）：

prio <= static_prio-DELTA(p)

當(dāng)進(jìn)程時(shí)間片耗盡時(shí)，如果該宏返回真(同時(shí) expired 隊(duì)列沒(méi)有等待過(guò)長(zhǎng)的時(shí)間，見(jiàn)"新的數(shù)據(jù)結(jié)構(gòu) runqueue""expired_timestamp"條），則該進(jìn)程不進(jìn)入 expired 隊(duì)列而是保留在 active 隊(duì)列中，以便盡快調(diào)度到這一交互式進(jìn)程。動(dòng)態(tài)優(yōu)先級(jí)在調(diào)度到該進(jìn)程時(shí)在 effective_prio() 中算出：prio=static_prio-bonus(sleep_avg)（bonus(sleep_avg) 表示 bonus 是關(guān)于 sleep_avg 的函數(shù)，見(jiàn)"優(yōu)先級(jí)計(jì)算過(guò)程"），而 DELTA(p) 與進(jìn)程的 nice 值有關(guān)，可表示為delta(nice)。bonus 與 sleep_avg 的關(guān)系在"優(yōu)先級(jí)計(jì)算過(guò)程"一節(jié)中已經(jīng)用圖說(shuō)明了，delta 和 nice 之間的關(guān)系見(jiàn)下圖：

nice 值的范圍是 -20~19，DELTA(p)將其轉(zhuǎn)換到 -5~+5 再加上一個(gè)INTERACTIVE_DELTA常量的范圍內(nèi)：TASK_NICE(p) * MAX_BONUS/40 + INTERACTIVE_DELTA，其中 INTERACTIVE_DELTA 等于 2。

經(jīng)過(guò)轉(zhuǎn)換，TASK_INTERACTIVE(p) 變?yōu)?"delta(nice) 是否不大于 bonus(sleep_avg)"。將 sleep_avg 表示為 JIFFIES 的形式，并代入常數(shù)，delta(nice)<=bonus(sleep_avg) 可以表示為：

nice/4+2 <= bonus，-5<=bonus<=+5

從中可以看出，nice 大于 12 時(shí)，此不等式恒假，也就是說(shuō)此時(shí)進(jìn)程永遠(yuǎn)不會(huì)被當(dāng)作交互式進(jìn)程看待；而進(jìn)程靜態(tài)優(yōu)先級(jí)越高，要被當(dāng)作交互式進(jìn)程所需要的 sleep_avg 上限也越低，即靜態(tài)優(yōu)先級(jí)高的進(jìn)程獲得這種獎(jiǎng)勵(lì)的機(jī)會(huì)更大。

4) 就緒等待時(shí)間的獎(jiǎng)勵(lì)

因?yàn)榻?jīng)常處于 TASK_INTERRUPTIBLE 狀態(tài)的進(jìn)程最有可能是交互式的，因此，這一類進(jìn)程從休眠中醒來(lái)后在就緒隊(duì)列上等待調(diào)度的時(shí)間長(zhǎng)短也將影響進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。

這一工作在調(diào)度器（schedule()）選擇上這一類型的進(jìn)程之后進(jìn)行，并且考慮到交互式進(jìn)程通常都是在中斷中被喚醒的，所以核心還記錄了這一信息，對(duì)不由中斷喚醒的進(jìn)程實(shí)行獎(jiǎng)勵(lì)約束（詳見(jiàn)"進(jìn)程平均等待時(shí)間sleep_avg"）。

8． 調(diào)度器
有了以上的準(zhǔn)備工作之后，現(xiàn)在我們可以看看調(diào)度器的主流程了。

和 2.4 的調(diào)度器相比，2.6 的 schedule()函數(shù)要更加簡(jiǎn)單一些，減少了鎖操作，優(yōu)先級(jí)計(jì)算也拿到調(diào)度器外進(jìn)行了。為減少進(jìn)程在 cpu 間跳躍，2.4 中將被切換下來(lái)的進(jìn)程重新調(diào)度到另一個(gè) cpu 上的動(dòng)作也省略了。調(diào)度器的基本流程仍然可以概括為相同的五步：

• 清理當(dāng)前運(yùn)行中的進(jìn)程（prev）
• 選擇下一個(gè)投入運(yùn)行的進(jìn)程（next）
• 設(shè)置新進(jìn)程的運(yùn)行環(huán)境
• 執(zhí)行進(jìn)程上下文切換
• 后期整理

2.6 的調(diào)度器工作流程保留了很多 2.4 系統(tǒng)中的動(dòng)作，進(jìn)程切換的細(xì)節(jié)也與 2.4 基本相同（由 context_switch() 開(kāi)始）。為了不與 2.4 系統(tǒng)的調(diào)度器分析重復(fù)，我們按照調(diào)度器對(duì)各個(gè)數(shù)據(jù)結(jié)構(gòu)的影響來(lái)分析調(diào)度器的工作流程，重點(diǎn)在與 2.4 調(diào)度器不同的部分，與之相同或相似的部分相信讀者結(jié)合代碼和上文的技術(shù)分析很容易理解。同時(shí)，2.6 的調(diào)度器中還增加了對(duì)負(fù)載平衡和內(nèi)核搶占運(yùn)行的支持，因?yàn)閮?nèi)容比較獨(dú)立，我們也將其放在單獨(dú)的章節(jié)中。

1) 相關(guān)鎖
主要是因?yàn)榫途w隊(duì)列分布到各個(gè) cpu 上了，2.6 調(diào)度器中僅涉及兩個(gè)鎖的操作：就緒隊(duì)列鎖 runqueue::lock，全局核心鎖 kernel_flag。對(duì)就緒隊(duì)列鎖的操作保證了就緒隊(duì)列的操作唯一性，核心鎖的意義與 2.4 中相同：調(diào)度器在執(zhí)行切換之前應(yīng)將核心鎖解開(kāi)（release_kernel_lock()），完成調(diào)度后恢復(fù)鎖狀態(tài)（reacquire_kernel_lock()）。進(jìn)程的鎖狀態(tài)依然保存在task_struct::lock_depth屬性中。

因?yàn)檎{(diào)度器中沒(méi)有任何全局的鎖操作，2.6 調(diào)度器本身的運(yùn)行障礙幾乎不存在了。

2) prev
調(diào)度器主要影響 prev 進(jìn)程的兩個(gè)屬性：

• sleep_avg 減去了本進(jìn)程的運(yùn)行時(shí)間（詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"的"被切換下來(lái)的進(jìn)程"）；
• timestamp 更新為當(dāng)前時(shí)間，記錄被切換下去的時(shí)間，用于計(jì)算進(jìn)程等待時(shí)間。

prev被切換下來(lái)后，即使修改了 sleep_avg，它在就緒隊(duì)列中的位置也不會(huì)改變，它將一直以此優(yōu)先級(jí)參加調(diào)度直至發(fā)生狀態(tài)改變（比如休眠）。

3) next
在前面介紹 runqueue 數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們已經(jīng)分析了 active/expired 兩個(gè)按優(yōu)先級(jí)排序的就緒進(jìn)程隊(duì)列的功能，2.6 的調(diào)度器對(duì)候選進(jìn)程的定位有三種可能：

• active 就緒隊(duì)列中優(yōu)先級(jí)最高且等待時(shí)間最久的進(jìn)程；
• 當(dāng)前 runqueue 中沒(méi)有就緒進(jìn)程了，則啟動(dòng)負(fù)載平衡從別的 cpu 上轉(zhuǎn)移進(jìn)程，再進(jìn)行挑選（詳見(jiàn)"調(diào)度器相關(guān)的負(fù)載平衡"）；
• 如果仍然沒(méi)有就緒進(jìn)程，則將本 cpu 的 IDLE 進(jìn)程設(shè)為候選。

在挑選出 next 之后，如果發(fā)現(xiàn) next 是從 TASK_INTERRUPTIBLE 休眠中醒來(lái)后第一次被調(diào)度到（activated>0），調(diào)度器將根據(jù) next 在就緒隊(duì)列上等待的時(shí)長(zhǎng)重新調(diào)整進(jìn)程的優(yōu)先級(jí)（并存入就緒隊(duì)列中新的位置，詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"）。

除了 sleep_avg 和 prio 的更新外，next 的 timestamp 也更新為當(dāng)前時(shí)間，用于下一次被切換下來(lái)時(shí)計(jì)算運(yùn)行時(shí)長(zhǎng)。

4) 外環(huán)境
這里說(shuō)的外環(huán)境指的是調(diào)度器對(duì)除參與調(diào)度的進(jìn)程以及所在就緒隊(duì)列以外的環(huán)境的影響，主要包括切換計(jì)數(shù)處理和 cpu 狀態(tài)的更新（qsctr）。

9． 調(diào)度器對(duì)內(nèi)核搶占運(yùn)行的支持
在2.4 系統(tǒng)中，在核心態(tài)運(yùn)行的任何進(jìn)程，只有當(dāng)它調(diào)用 schedule() 主動(dòng)放棄控制時(shí)，調(diào)度器才有機(jī)會(huì)選擇其他進(jìn)程運(yùn)行，因此我們說(shuō) Linux 2.4 的內(nèi)核是不可搶占運(yùn)行的。缺乏這一支持，核心就無(wú)法保證實(shí)時(shí)任務(wù)的及時(shí)響應(yīng)，因此也就滿足不了實(shí)時(shí)系統(tǒng)（即使是軟實(shí)時(shí)）的要求。

2.6 內(nèi)核實(shí)現(xiàn)了搶占運(yùn)行，沒(méi)有鎖保護(hù)的任何代碼段都有可能被中斷，它的實(shí)現(xiàn)，對(duì)于調(diào)度技術(shù)來(lái)說(shuō)，主要就是增加了調(diào)度器運(yùn)行的時(shí)機(jī)。我們知道，在 2.4 內(nèi)核里，調(diào)度器有兩種啟動(dòng)方式：主動(dòng)式和被動(dòng)式，其中被動(dòng)方式啟動(dòng)調(diào)度器只能是在控制從核心態(tài)返回用戶態(tài)的時(shí)候，因此才有內(nèi)核不可搶占的特點(diǎn)。2.6 中，調(diào)度器的啟動(dòng)方式仍然可分為主動(dòng)式和被動(dòng)式兩種，所不同的是被動(dòng)啟動(dòng)調(diào)度器的條件放寬了很多。它的修改主要在 entry.S 中：

……
ret_from_exception:		#從異常中返回的入口
	preempt_stop				#解釋為 cli，關(guān)中斷，即從異常中返回過(guò)程中不允許搶占
ret_from_intr:				#從中斷返回的入口
	GET_THREAD_INFO(%ebp)	#取task_struct的thread_info信息
	movl EFLAGS(%esp), %eax
	movb CS(%esp), %al
	testl $(VM_MASK | 3), %eax
	jz resume_kernel			#"返回用戶態(tài)"和"在核心態(tài)中返回"的分路口
ENTRY(resume_userspace)
 	cli
movl TI_FLAGS(%ebp), %ecx
	andl $_TIF_WORK_MASK, %ecx	#
	（_TIF_NOTIFY_RESUME | _TIF_SIGPENDING			 							
	#  | _TIF_NEED_RESCHED）
	jne work_pending
	jmp restore_all
ENTRY(resume_kernel)
	cmpl $0,TI_PRE_COUNT(%ebp)
	jnz restore_all				
	#如果preempt_count非0，則不允許搶占
need_resched:
	movl TI_FLAGS(%ebp), %ecx
	testb $_TIF_NEED_RESCHED, %cl
	jz restore_all				
	#如果沒(méi)有置NEED_RESCHED位，則不需要調(diào)度
	testl $IF_MASK,EFLAGS(%esp)
	jz restore_all				#如果關(guān)中斷了，則不允許調(diào)度
	movl $PREEMPT_ACTIVE,TI_PRE_COUNT(%ebp)		
	#preempt_count 設(shè)為 PREEMPT_ACTIVE，
	通知調(diào)度器目前這次調(diào)度正處在一次搶
                               #占調(diào)度中
	sti							
	call schedule
	movl $0,TI_PRE_COUNT(%ebp)	#preemmpt_count清0
	cli
	jmp need_resched
……
work_pending:					#這也是從系統(tǒng)調(diào)用中返回時(shí)的resched入口
	testb $_TIF_NEED_RESCHED, %cl
	jz work_notifysig			
	#不需要調(diào)度，那么肯定是因?yàn)橛行盘?hào)需要處理才進(jìn)入work_pending的
work_resched:
	call schedule
	cli				
	movl TI_FLAGS(%ebp), %ecx
	andl $_TIF_WORK_MASK, %ecx	
	jz restore_all				#沒(méi)有work要做了，也不需要resched
	testb $_TIF_NEED_RESCHED, %cl
	jnz work_resched				#或者是需要調(diào)度，或者是有信號(hào)要處理
work_notifysig:
……

現(xiàn)在，無(wú)論是返回用戶態(tài)還是返回核心態(tài)，都有可能檢查 NEED_RESCHED 的狀態(tài)；返回核心態(tài)時(shí)，只要 preempt_count 為 0，即當(dāng)前進(jìn)程目前允許搶占，就會(huì)根據(jù) NEED_RESCHED 狀態(tài)選擇調(diào)用 schedule()。在核心中，因?yàn)橹辽贂r(shí)鐘中斷是不斷發(fā)生的，因此，只要有進(jìn)程設(shè)置了當(dāng)前進(jìn)程的 NEED_RESCHED 標(biāo)志，當(dāng)前進(jìn)程馬上就有可能被搶占，而無(wú)論它是否愿意放棄 cpu，即使是核心進(jìn)程也是如此。

10． 調(diào)度器相關(guān)的負(fù)載平衡
在 2.4 內(nèi)核中，進(jìn)程p被切換下來(lái)之后，如果還有 cpu 空閑，或者該 cpu 上運(yùn)行的進(jìn)程優(yōu)先級(jí)比自己低，那么 p 就會(huì)被調(diào)度到那個(gè) cpu 上運(yùn)行，核心正是用這種辦法來(lái)實(shí)現(xiàn)負(fù)載的平衡。

簡(jiǎn)單是這種負(fù)載平衡方式最大的優(yōu)點(diǎn)，但它的缺點(diǎn)也比較明顯：進(jìn)程遷移比較頻繁，交互式進(jìn)程（或高優(yōu)先級(jí)的進(jìn)程）可能還會(huì)在 cpu 之間不斷"跳躍"。即使是在 SMP 的環(huán)境中，進(jìn)程遷移也是有代價(jià)的，2.4 系統(tǒng)的使用經(jīng)驗(yàn)表明，這種負(fù)載平衡方式弊大于利，解決這一"SMP親和"的問(wèn)題是 2.6 系統(tǒng)設(shè)計(jì)的目標(biāo)之一。

2.6 調(diào)度系統(tǒng)采用相對(duì)集中的負(fù)載平衡方案，分為"推"和"拉"兩類操作：

1) "拉"

當(dāng)某個(gè) cpu 負(fù)載過(guò)輕而另一個(gè) cpu 負(fù)載較重時(shí)，系統(tǒng)會(huì)從重載 cpu 上"拉"進(jìn)程過(guò)來(lái)，這個(gè)"拉"的負(fù)載平衡操作實(shí)現(xiàn)在 load_balance() 函數(shù)中。

load_balance() 有兩種調(diào)用方式，分別用于當(dāng)前 cpu 不空閑和空閑兩種狀態(tài)，我們稱之為"忙平衡"和"空閑平衡"：

a) 忙平衡

無(wú)論當(dāng)前 cpu 是否繁忙或空閑，時(shí)鐘中斷（rebalance_tick()函數(shù)中）每隔一段時(shí)間（BUSY_REBALANCE_TICK）都會(huì)啟動(dòng)一次 load_balance() 平衡負(fù)載，這種平衡稱為"忙平衡"。

Linux 2.6 傾向于盡可能不做負(fù)載平衡，因此在判斷是否應(yīng)該"拉"的時(shí)候做了很多限制：

• 系統(tǒng)最繁忙的 cpu 的負(fù)載超過(guò)當(dāng)前 cpu 負(fù)載的 25% 時(shí)才進(jìn)行負(fù)載平衡；
• 當(dāng)前 cpu 的負(fù)載取當(dāng)前真實(shí)負(fù)載和上一次執(zhí)行負(fù)載平衡時(shí)的負(fù)載的較大值，平滑負(fù)載凹值；
• 各 cpu 的負(fù)載情況取當(dāng)前真實(shí)負(fù)載和上一次執(zhí)行負(fù)載平衡時(shí)的負(fù)載的較小值，平滑負(fù)載峰值；
• 對(duì)源、目的兩個(gè)就緒隊(duì)列加鎖之后，再確認(rèn)一次源就緒隊(duì)列負(fù)載沒(méi)有減小，否則取消負(fù)載平衡動(dòng)作；
• 源就緒隊(duì)列中以下三類進(jìn)程參與負(fù)載情況計(jì)算，但不做實(shí)際遷移：
  • 正在運(yùn)行的進(jìn)程
  • 不允許遷移到本 cpu 的進(jìn)程（根據(jù) cpu_allowed 屬性）
  • 進(jìn)程所在 cpu 上一次調(diào)度事件發(fā)生的時(shí)間（runqueue::timestamp_last_tick，在時(shí)鐘中斷中取值）與進(jìn)程被切換下來(lái)的時(shí)間（task_struct::timestamp）之差小于某個(gè)閥值（cache_decay_ticks的nanosecond值），--該進(jìn)程還比較活躍，cache 中的信息還不夠涼。

找到最繁忙的 cpu（源 cpu）之后，確定需要遷移的進(jìn)程數(shù)為源 cpu 負(fù)載與本 cpu 負(fù)載之差的一半（都經(jīng)過(guò)了上述歷史信息平滑），然后按照從 expired 隊(duì)列到 active 隊(duì)列、從低優(yōu)先級(jí)進(jìn)程到高優(yōu)先級(jí)進(jìn)程的順序進(jìn)行遷移。但實(shí)際上真正執(zhí)行遷移的進(jìn)程往往少于計(jì)劃遷移的進(jìn)程，因?yàn)樯鲜鋈?不做實(shí)際遷移"的情況的進(jìn)程不參與遷移。

b) 空閑平衡

空閑狀態(tài)下的負(fù)載平衡有兩個(gè)調(diào)用時(shí)機(jī)：

• 在調(diào)度器中，本 cpu 的就緒隊(duì)列為空；
• 在時(shí)鐘中斷中，本 cpu 的就緒隊(duì)列為空，且當(dāng)前絕對(duì)時(shí)間（jiffies 值）是 IDLE_REBALANCE_TICK 的倍數(shù)（也就是說(shuō)每隔 IDLE_REBALANCE_TICK 執(zhí)行一次）。

此時(shí) load_balance() 的動(dòng)作比較簡(jiǎn)單：尋找當(dāng)前真實(shí)負(fù)載最大的 cpu（runqueue::nr_running 最大），將其中"最適合"（見(jiàn)下）的一個(gè)就緒進(jìn)程遷移到當(dāng)前 cpu 上來(lái)。

"空閑平衡"的候選進(jìn)程的標(biāo)準(zhǔn)和"忙平衡"類似，但因?yàn)榭臻e平衡僅"拉"一個(gè)進(jìn)程過(guò)來(lái)，動(dòng)作要小得多，且執(zhí)行頻率相對(duì)較高（IDLE_REBALANCE_TICK 是BUSY_REBALANCE_TICK 的 200 倍），所以沒(méi)有考慮負(fù)載的歷史情況和負(fù)載差，候選的遷移進(jìn)程也沒(méi)有考慮 Cache 活躍程度。

c) pull_task()

"拉"進(jìn)程的具體動(dòng)作在這個(gè)函數(shù)中實(shí)現(xiàn)。進(jìn)程從源就緒隊(duì)列遷移到目的就緒隊(duì)列之后，pull_task() 更新了進(jìn)程的 timestamp 屬性，使其能繼續(xù)說(shuō)明進(jìn)程相對(duì)于本 cpu 的被切換下來(lái)的時(shí)間。如果被拉來(lái)的進(jìn)程的優(yōu)先級(jí)比本 cpu 上正在運(yùn)行的進(jìn)程優(yōu)先級(jí)要高，就置當(dāng)前進(jìn)程的 NEED_RESCHED 位等待調(diào)度。

2) "推"
a) migration_thread()

與"拉"相對(duì)應(yīng)，2.6 的負(fù)載平衡系統(tǒng)還有一個(gè)"推"的過(guò)程，執(zhí)行"推"的主體是一個(gè)名為 migration_thread() 的核心進(jìn)程。該進(jìn)程在系統(tǒng)啟動(dòng)時(shí)自動(dòng)加載（每個(gè) cpu 一個(gè)），并將自己設(shè)為 SCHED_FIFO 的實(shí)時(shí)進(jìn)程，然后檢查 runqueue::migration_queue 中是否有請(qǐng)求等待處理，如果沒(méi)有，就在 TASK_INTERRUPTIBLE 中休眠，直至被喚醒后再次檢查。

migration_queue 僅在 set_cpu_allowed() 中添加，當(dāng)進(jìn)程（比如通過(guò) APM 關(guān)閉某 CPU 時(shí)）調(diào)用 set_cpu_allowed() 改變當(dāng)前可用 cpu，從而使某進(jìn)程不適于繼續(xù)在當(dāng)前 cpu 上運(yùn)行時(shí)，就會(huì)構(gòu)造一個(gè)遷移請(qǐng)求數(shù)據(jù)結(jié)構(gòu) migration_req_t，將其植入進(jìn)程所在 cpu 就緒隊(duì)列的 migration_queue 中，然后喚醒該就緒隊(duì)列的遷移 daemon（記錄在 runqueue::migration_thread 屬性中），將該進(jìn)程遷移到合適的cpu上去（參見(jiàn)"新的數(shù)據(jù)結(jié)構(gòu) runqueue"）。

在目前的實(shí)現(xiàn)中，目的 cpu 的選擇和負(fù)載無(wú)關(guān)，而是"any_online_cpu(req->task->cpus_allowed)"，也就是按 CPU 編號(hào)順序的第一個(gè) allowed 的CPU。所以，和 load_balance() 與調(diào)度器、負(fù)載平衡策略密切相關(guān)不同，migration_thread() 應(yīng)該說(shuō)僅僅是一個(gè) CPU 綁定以及 CPU 電源管理等功能的一個(gè)接口。

b) move_task_away()

實(shí)際遷移的動(dòng)作在 move_task_away() 函數(shù)中實(shí)現(xiàn)，進(jìn)程進(jìn)入目的就緒隊(duì)列之后，它的 timestamp 被更新為目的 cpu 就緒隊(duì)列的 timestamp_last_tick，說(shuō)明本進(jìn)程是剛開(kāi)始（在目的 cpu 上）等待。因?yàn)?推"的操作是在本地讀遠(yuǎn)地寫(xiě)（與 pull_task() 正相反），因此，在啟動(dòng)遠(yuǎn)地 cpu 的調(diào)度時(shí)需要與遠(yuǎn)地的操作同步，還可能要通過(guò) IPI（Inter-Processor Interrupt）通知目的 cpu，所有這些操作實(shí)現(xiàn)在 resched_task()函數(shù)中。

11． NUMA結(jié)構(gòu)下的調(diào)度
在 Linux 調(diào)度器看來(lái)，NUMA 與 SMP 之間主要的不同在于 NUMA 下的 cpu 被組織到一個(gè)個(gè)節(jié)點(diǎn)中了。不同的體系結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)所包含的 cpu 數(shù)是不同的，例如 2.6 的 i386 平臺(tái)下，NUMAQ 結(jié)構(gòu)每個(gè)節(jié)點(diǎn)上可配置 16 個(gè) cpu，SUMMIT 結(jié)構(gòu)可配置 32 個(gè) cpu。 NUMA 結(jié)構(gòu)正式體現(xiàn)在 Linux 內(nèi)核中是從 2.6 開(kāi)始的，在此之前，Linux 利用已有的"不連續(xù)內(nèi)存"（Discontiguous memory，CONFIG_DISCONTIGMEM）體系結(jié)構(gòu)來(lái)支持 NUMA。除了內(nèi)存分配上的特殊處理以外，以往的內(nèi)核在調(diào)度系統(tǒng)中是等同于 SMP 看待的。2.6 的調(diào)度器除了單個(gè) cpu 的負(fù)載，還考慮了 NUMA 下各個(gè)節(jié)點(diǎn)的負(fù)載情況。

NUMA 結(jié)構(gòu)在新內(nèi)核中有兩處特殊處理，一處是在做負(fù)載平衡時(shí)對(duì)各NUMA節(jié)點(diǎn)進(jìn)行均衡，另一處是在系統(tǒng)執(zhí)行新程序（do_execve()）時(shí)從負(fù)載最輕的節(jié)點(diǎn)中選擇執(zhí)行cpu：

1) balance_node()
節(jié)點(diǎn)間的平衡作為 rebalance_tick() 函數(shù)中的一部分在 load_balance() 之前啟動(dòng)（此時(shí)的 load_balance() 的工作集是節(jié)點(diǎn)內(nèi)的 cpu，也就是說(shuō)，NUMA下不是單純平衡全系統(tǒng)的 cpu 負(fù)載，而是先平衡節(jié)點(diǎn)間負(fù)載，再平衡節(jié)點(diǎn)內(nèi)負(fù)載），同樣分為"忙平衡"和"空閑平衡"兩步，執(zhí)行間隔分別為IDLE_NODE_REBALANCE_TICK（當(dāng)前實(shí)現(xiàn)中是 IDLE_REBALANCE_TICK 的 5 倍）和 BUSY_NODE_REBALANCE_TICK（實(shí)現(xiàn)為 BUSY_NODE_REBALANCE_TICK 的 2 倍）。

balance_node() 先調(diào)用 find_busiest_node() 找到系統(tǒng)中最繁忙的節(jié)點(diǎn)，然后在該節(jié)點(diǎn)和本 cpu 組成的 cpu 集合中進(jìn)行 load_balance()。尋找最繁忙節(jié)點(diǎn)的算法涉及到幾個(gè)數(shù)據(jù)結(jié)構(gòu)：

• node_nr_running[MAX_NUMNODES]，以節(jié)點(diǎn)號(hào)為索引記錄了每個(gè)節(jié)點(diǎn)上的就緒進(jìn)程個(gè)數(shù)，也就是那個(gè)節(jié)點(diǎn)上的實(shí)時(shí)負(fù)載。這個(gè)數(shù)組是一個(gè)全局?jǐn)?shù)據(jù)結(jié)構(gòu)，需要通過(guò) atomic 系列函數(shù)訪問(wèn)。
• runqueue::prev_node_load[MAX_NUMNODES]，就緒隊(duì)列數(shù)據(jù)結(jié)構(gòu)中記錄的系統(tǒng)各個(gè)節(jié)點(diǎn)上一次負(fù)載平衡操作時(shí)的負(fù)載情況，它按照以下公式修正：
  當(dāng)前負(fù)載=上一次的負(fù)載/2 + 10*當(dāng)前實(shí)時(shí)負(fù)載/節(jié)點(diǎn)cpu數(shù)
  采用這種計(jì)算方式可以平滑負(fù)載峰值，也可以考慮到節(jié)點(diǎn)cpu數(shù)不一致的情況。
• NODE_THRESHOLD，負(fù)載的權(quán)值，定義為 125，被選中的最繁忙的節(jié)點(diǎn)的負(fù)載必須超過(guò)當(dāng)前節(jié)點(diǎn)負(fù)載的 125/100，也就是負(fù)載差超過(guò) 25%。

2) sched_balance_exec()
當(dāng) execve() 系統(tǒng)調(diào)用加載另一個(gè)程序投入運(yùn)行時(shí)，核心將在全系統(tǒng)中尋找負(fù)載最輕的一個(gè)節(jié)點(diǎn)中負(fù)載最輕的一個(gè) cpu（sched_best_cpu()），然后調(diào)用sched_migrate_task() 將這個(gè)進(jìn)程遷移到選定的 cpu 上去。這一操作通過(guò) do_execve() 調(diào)用 sched_balance_exec() 來(lái)實(shí)現(xiàn)。

sched_best_cpu() 的選擇標(biāo)準(zhǔn)如下：

• 如果當(dāng)前cpu就緒進(jìn)程個(gè)數(shù)不超過(guò)2，則不做遷移；
• 計(jì)算節(jié)點(diǎn)負(fù)載時(shí)，使用（10*當(dāng)前實(shí)時(shí)負(fù)載/節(jié)點(diǎn)cpu數(shù)）的算法，不考慮負(fù)載的歷史情況；
• 計(jì)算節(jié)點(diǎn)內(nèi)cpu的負(fù)載時(shí)，使用就緒進(jìn)程的實(shí)際個(gè)數(shù)作為負(fù)載指標(biāo)，不考慮負(fù)載的歷史情況。

和"忙平衡"與"空閑平衡"采用不同負(fù)載評(píng)價(jià)標(biāo)準(zhǔn)一樣，sched_balance_exec() 采用了與 balance_node() 不一樣的（更簡(jiǎn)單的）評(píng)價(jià)標(biāo)準(zhǔn)。

sched_migrate_task() 借用了 migration_thread 服務(wù)進(jìn)程來(lái)完成遷移，實(shí)際操作時(shí)將進(jìn)程的 cpu_allowed 暫設(shè)為僅能在目的 cpu 上運(yùn)行，喚醒migration_thread 將進(jìn)程遷移到目的 cpu 之后再恢復(fù) cpu_allowed 屬性。

12． 調(diào)度器的實(shí)時(shí)性能

1) 2.6 對(duì)于實(shí)時(shí)應(yīng)用的加強(qiáng)
2.6 內(nèi)核調(diào)度系統(tǒng)有兩點(diǎn)新特性對(duì)實(shí)時(shí)應(yīng)用至關(guān)重要：內(nèi)核搶占和 O(1) 調(diào)度，這兩點(diǎn)都保證實(shí)時(shí)進(jìn)程能在可預(yù)計(jì)的時(shí)間內(nèi)得到響應(yīng)。這種"限時(shí)響應(yīng)"的特點(diǎn)符合軟實(shí)時(shí)（soft realtime）的要求，離"立即響應(yīng)"的硬實(shí)時(shí)（hard realtime）還有一定距離。并且，2.6 調(diào)度系統(tǒng)仍然沒(méi)有提供除 cpu 以外的其他資源的剝奪運(yùn)行，因此，它的實(shí)時(shí)性并沒(méi)有得到根本改觀。

2) 實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)
2.4 系統(tǒng)中，實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)通過(guò) rt_priority 屬性表示，與非實(shí)時(shí)進(jìn)程不同。2.6 在靜態(tài)優(yōu)先級(jí)之外引入了動(dòng)態(tài)優(yōu)先級(jí)屬性，并用它同時(shí)表示實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)。

從上面的分析我們看到，進(jìn)程的靜態(tài)優(yōu)先級(jí)是計(jì)算進(jìn)程初始時(shí)間片的基礎(chǔ)，動(dòng)態(tài)優(yōu)先級(jí)則決定了進(jìn)程的實(shí)際調(diào)度優(yōu)先順序。無(wú)論是實(shí)時(shí)進(jìn)程還是非實(shí)時(shí)進(jìn)程，靜態(tài)優(yōu)先級(jí)都通過(guò) set_user_nice() 來(lái)設(shè)置和改變，缺省值都是 120（MAX_PRIO-20），也就是說(shuō)，實(shí)時(shí)進(jìn)程的時(shí)間片和非實(shí)時(shí)進(jìn)程在一個(gè)量程內(nèi)。

可區(qū)分實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程的地方有兩處：調(diào)度策略 policy（SCHED_RR或SCHED_FIFO）和動(dòng)態(tài)優(yōu)先級(jí) prio（小于 MAX_USER_RT_PRIO），實(shí)際使用上后者作為檢驗(yàn)標(biāo)準(zhǔn)。實(shí)時(shí)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)在 setscheduler() 中設(shè)置（相當(dāng)于 rt_priority），并且不隨進(jìn)程的運(yùn)行而改變，所以實(shí)時(shí)進(jìn)程總是嚴(yán)格按照設(shè)置的優(yōu)先級(jí)進(jìn)行排序，這一點(diǎn)和非實(shí)時(shí)進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)含義不同?？梢哉J(rèn)為，實(shí)時(shí)進(jìn)程的靜態(tài)優(yōu)先級(jí)僅用于計(jì)算時(shí)間片，而動(dòng)態(tài)優(yōu)先級(jí)則相當(dāng)于靜態(tài)優(yōu)先級(jí)。

3) 實(shí)時(shí)調(diào)度
2.4中SCHED_RR和SCHED_FIFO兩種實(shí)時(shí)調(diào)度策略在2.6中未作改變，兩類實(shí)時(shí)進(jìn)程都會(huì)保持在active就緒隊(duì)列中運(yùn)行，只是因?yàn)?.6內(nèi)核是可搶占的，實(shí)時(shí)進(jìn)程（特別是核心級(jí)的實(shí)時(shí)進(jìn)程）能更迅速地對(duì)環(huán)境的變化（比如出現(xiàn)更高優(yōu)先級(jí)進(jìn)程）做出反應(yīng)。

13． 后記：從調(diào)度器看 Linux 發(fā)展
近年來(lái)，Linux 對(duì)于桌面系統(tǒng)、低端服務(wù)器、高端服務(wù)器以及嵌入式系統(tǒng)都表現(xiàn)出越來(lái)越強(qiáng)的興趣和競(jìng)爭(zhēng)力，對(duì)于一個(gè)仍然處于"集市式"開(kāi)放開(kāi)發(fā)模式的操作系統(tǒng)來(lái)說(shuō)，能做到這一點(diǎn)簡(jiǎn)直就是一個(gè)奇跡。

但從調(diào)度系統(tǒng)的實(shí)現(xiàn)上我感覺(jué)，Linux 的長(zhǎng)項(xiàng)仍然在桌面系統(tǒng)上，它仍然保持著早年開(kāi)發(fā)時(shí)"利己主義"的特點(diǎn)，即自由軟件的開(kāi)發(fā)者的開(kāi)發(fā)動(dòng)力，很大程度上來(lái)自于改變現(xiàn)有系統(tǒng)對(duì)自己"不好用"的現(xiàn)狀。盡管出于種種動(dòng)機(jī)和動(dòng)力，Linux 表現(xiàn)出與 Windows 等商用操作系統(tǒng)競(jìng)爭(zhēng)的強(qiáng)勢(shì)，但從開(kāi)發(fā)者角度來(lái)看，這種愿望與自由軟件的開(kāi)發(fā)特點(diǎn)是有矛盾的。

Ingo Monar 在接受采訪時(shí)說(shuō)，他設(shè)計(jì)的 O(1) 調(diào)度算法，基本上來(lái)自于個(gè)人的創(chuàng)意，沒(méi)有參考市面上以及研究領(lǐng)域中已有的調(diào)度算法。從調(diào)度器設(shè)計(jì)上可以看出，2.6 調(diào)度系統(tǒng)考慮了很多細(xì)節(jié)，但總體上并沒(méi)有清晰的主線，且無(wú)法（或者也無(wú)意于）在理論上對(duì) O(1) 模型進(jìn)行性能分析。從 2.6 的開(kāi)發(fā)過(guò)程中我們也能看到，各種調(diào)度相關(guān)的權(quán)值在不同的版本中一直在微調(diào)，可以認(rèn)為，2.6 調(diào)度系統(tǒng)的性能優(yōu)化主要是實(shí)測(cè)得來(lái)的。

這就是典型的 Linux 開(kāi)發(fā)模式--充滿激情、缺乏規(guī)劃。

對(duì)于 Linux 的市場(chǎng)來(lái)說(shuō)，最緊迫、最活躍的需要在于嵌入式系統(tǒng)，但至少?gòu)恼{(diào)度系統(tǒng)來(lái)看，2.6 并沒(méi)有在這方面下很大功夫，也許開(kāi)發(fā)者本人對(duì)此并無(wú)多大感受和興趣?？梢钥隙?，雖然 Linux 在市場(chǎng)上很火，但它的開(kāi)發(fā)仍然不是市場(chǎng)驅(qū)動(dòng)的。這或許會(huì)影響 Linux 的競(jìng)爭(zhēng)力，但或許也因此能保持 Linux 開(kāi)發(fā)的活力。

就在今年（2004年）3月1日，著名的開(kāi)源網(wǎng)絡(luò)安全項(xiàng)目 FreeS/WAN 宣布停止開(kāi)發(fā)，其原因主要是開(kāi)發(fā)者的意圖和用戶的需求不吻合。對(duì)于網(wǎng)絡(luò)安全系統(tǒng)，用戶更多考慮的是系統(tǒng)功能的完整、強(qiáng)大，而不是它可預(yù)知的先進(jìn)性，因此，F(xiàn)reeS/WAN 新版本中主打推出的 Opportunistic Encryption (OE) 沒(méi)有吸引到足夠數(shù)量的用戶測(cè)試。鑒于此，投資者停止了對(duì) FreeS/WAN 項(xiàng)目的資助，這一為開(kāi)源系統(tǒng)提供了強(qiáng)大的網(wǎng)絡(luò)安全支持的系統(tǒng)也許會(huì)再次轉(zhuǎn)入地下。

至今為止，還沒(méi)有聽(tīng)到 Linux 的開(kāi)發(fā)依賴于某種商業(yè)基金的報(bào)道，因此相對(duì)而言，Linux 的開(kāi)發(fā)更具自由和隨意性，推廣 Linux 的人與開(kāi)發(fā) Linux 的人基本上獨(dú)立運(yùn)作著，Linux 的受益者和 Linux 的開(kāi)發(fā)者也沒(méi)有緊密結(jié)合。這對(duì)于 Linux 或許是福而不是禍。

參考資料

[1][Linus Torvalds，2004] Linux 內(nèi)核源碼 v2.6.2，www.kernel.org

[2][pubb@163.net，2004] Linux 2.4調(diào)度系統(tǒng)分析 ，IBM Developerworks

[3][Ingo Molnar，2002] Goals, Design and Implementation of the new ultra-scalable O(1) scheduler， Linux Documentation，sched-design.txt

[4][Anand K Santhanam (asanthan@in.ibm.com)，2003] 走向 Linux 2.6 ，IBM Developerworks

[5][Robert Love，2003] Linux Kernel Development，SAMS

[6][ bx_bird@sohu.com，2003] 2.5.62 SMP筆記，www.linux-forum.net內(nèi)核技術(shù)版

[7][ Vinayak Hegde，2003] The Linux Kernel，Linux Gazette 2003年4月號(hào)第89篇

[8][ Rick Fujiyama，2003] Analyzing The Linux Scheduler‘s Tunables，kerneltrap.org