楊沙洲
國防科技大學(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é)，并對與調(diào)度系統(tǒng)相關(guān)的負(fù)載平衡、NUMA 結(jié)構(gòu)以及實(shí)時性能進(jìn)行了分析和評價。文末，作者從調(diào)度系統(tǒng)的發(fā)展和實(shí)現(xiàn)出發(fā)，對 Linux 的發(fā)展特點(diǎn)和方向提出了自己的看法。

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

2.6 調(diào)度系統(tǒng)從設(shè)計(jì)之初就把開發(fā)重點(diǎn)放在更好滿足實(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)先級調(diào)度
  • 高 CPU 使用率
  • SMP 高效親和
  • 實(shí)時調(diào)度和 cpu 綁定等調(diào)度手段
• 在此基礎(chǔ)之上的新特性：
  • O(1)調(diào)度算法，調(diào)度器開銷恒定（與當(dāng)前系統(tǒng)負(fù)載無關(guān)），實(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)度器的開發(fā)一直受到廣泛關(guān)注，實(shí)測證明它的確使系統(tǒng)性能得到很大改善。本文就從新設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)開始，圍繞 2.6 對于 2.4 所作的改進(jìn)，對 2.6 調(diào)度系統(tǒng)的原理和實(shí)現(xiàn)細(xì)節(jié)進(jìn)行分析。2.6 調(diào)度器設(shè)計(jì)相當(dāng)復(fù)雜，文中還存在很多需要繼續(xù)研究的地方，特別是各個調(diào)度參數(shù)的設(shè)定，隨著核心版本的升級，可能還會繼續(xù)修正。

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

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

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

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

runqueue 中最關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。每個 CPU 的就緒隊(duì)列按時間片是否用完分為兩部分，分別通過 active 指針和 expired 指針訪問，active 指向時間片沒用完、當(dāng)前可被調(diào)度的就緒進(jìn)程，expired 指向時間片已用完的就緒進(jìn)程。每一類就緒進(jìn)程都用一個 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)先級為索引的 HASH 表，見下 */
		unsigned long bitmap[BITMAP_SIZE];
							/* 加速以上 HASH 表訪問的位圖，見下 */
};

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

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

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

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

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

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

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

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

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

2) spinlock_t lock

runqueue 的自旋鎖，當(dāng)需要對 runqueue 進(jìn)行操作時，仍然應(yīng)該鎖定，但這個鎖定操作只影響一個 CPU 上的就緒隊(duì)列，因此，競爭發(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)先級（數(shù)值最小）。該變量在進(jìn)程進(jìn)入 expired 隊(duì)列的時候保存（schedule_tick()），用途見 "expired_timestamp"的解釋）。

6) unsigned long expired_timestamp

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

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

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

7) struct mm_struct *prev_mm

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

8) unsigned long nr_running

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

9) unsigned long nr_switches

記錄了本 CPU 上自調(diào)度器運(yùn)行以來發(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)度事件的時間，在負(fù)載平衡的時候會用到（見"調(diào)度器相關(guān)的負(fù)載平衡"）。

13) int prev_cpu_load[NR_CPUS]

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

14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]

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

15) task_t *migration_thread

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

16) struct list_head migration_queue

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

3． 改進(jìn)后的 task_struct
2.6 版的內(nèi)核仍然用 task_struct 來表征進(jìn)程，盡管對線程進(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)程來回收的進(jìn)程。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9) time_slice

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

10) first_time_slice

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

11) run_list

前面提到，優(yōu)先級數(shù)組 prio_array 結(jié)構(gòu)中按順序排列了各個優(yōu)先級下的所有進(jìn)程，但實(shí)際上數(shù)組中每一個元素都是 list_head 結(jié)構(gòu)，以它為表頭的鏈表中的每一個元素也是 list_head，其中鏈接的就是 task_struct 中的 run_list 成員。這是一個節(jié)省空間、加速訪問的小技巧：調(diào)度器在 prio_array 中找到相應(yīng)的 run_list，然后通過 run_list 在 task_struct 中的固定偏移量找到對應(yīng)的 task_struct（參見 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)境信息，其中有兩個結(jié)構(gòu)成員與調(diào)度關(guān)系緊密：

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

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

/* 節(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)行時間片表現(xiàn)
2.6 中，time_slice 變量代替了 2.4 中的 counter 變量來表示進(jìn)程剩余運(yùn)行時間片。time_slice 盡管擁有和 counter 相同的含義，但在內(nèi)核中的表現(xiàn)行為已經(jīng)大相徑庭，下面分三個方面討論新的運(yùn)行時間片表現(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如下圖所示：

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

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

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

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

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

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

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

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

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

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

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

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

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

e) 其它時機(jī)

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

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

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

內(nèi)核中主要有四個地方會對 sleep_avg 進(jìn)行修改：休眠進(jìn)程被喚醒時（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 上被剝奪下來（schedule()函數(shù)中）、進(jìn)程創(chuàng)建和進(jìn)程退出，其中recalc_task_prio() 是其中復(fù)雜度最高的，它通過計(jì)算進(jìn)程的等待時間（或者是在休眠中等待，或者是在就緒隊(duì)列中等待）對優(yōu)先級的影響來重置優(yōu)先級。

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

在 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 不會因本次等待而改變。

b) INTERACTIVE_SLEEP(p)

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

c) MAX_SLEEP_AVG-AVG_TIMESLICE

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

d) sleep_avg+sleep_time

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

i. 根據(jù) sleep_avg 的值進(jìn)行修正，sleep_avg 越大，修正后的 sleep_time 越小：

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

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

總的來說，本次等待時間越長，sleep_avg 就應(yīng)該更大，但核心排除了兩種情況：

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

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)度到時
調(diào)度器挑選出候選進(jìn)程之后，如果發(fā)現(xiàn)它是從 TASK_INTERRUPTIBLE 休眠中醒來后第一次被調(diào)度到（activated>0），調(diào)度器將根據(jù)它在就緒隊(duì)列上等待的時長調(diào)用 recalc_task_prio() 重新調(diào)整進(jìn)程的 sleep_avg。

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

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

run_time 可以用系統(tǒng)當(dāng)前時間與進(jìn)程 timestamp（上一次被調(diào)度運(yùn)行的時間）的差值表示，但不能超過 NS_MAX_SLEEP_AVG。對于交互式進(jìn)程（HIGHT_CREDIT(p) 為真，見"更精確的交互式進(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)行時間，sleep_avg 越大，則 run_time 減小得越多，因此被切換下來的進(jìn)程最后計(jì)算所得的 sleep_avg 也就越大，動態(tài)優(yōu)先級也隨之變大。交互式進(jìn)程可以借此獲得更多被執(zhí)行的機(jī)會。

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，也就是說父進(jìn)程的 sleep_avg 不會變，而子進(jìn)程從父進(jìn)程處繼承過來的 sleep_avg 會減小 5%，因此子進(jìn)程最后的優(yōu)先級會比父進(jìn)程稍低（但子進(jìn)程仍然會置于與父進(jìn)程相同的就緒隊(duì)列上，位置在父進(jìn)程之前--也就是"前言"所說"子進(jìn)程先于父進(jìn)程運(yùn)行"）。

5) 進(jìn)程退出時
一個進(jìn)程結(jié)束運(yùn)行時，如果它的交互程度比父進(jìn)程低（sleep_avg 較?。敲春诵膶⒃?sched_exit() 中對其父進(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ìn)程的交互程度與父進(jìn)程相差越大，則優(yōu)先級的懲罰也越明顯。

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

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

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

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

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

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

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

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

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

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

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

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

prio <= static_prio-DELTA(p)

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

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

經(jīng)過轉(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 時，此不等式恒假，也就是說此時進(jìn)程永遠(yuǎn)不會被當(dāng)作交互式進(jìn)程看待；而進(jìn)程靜態(tài)優(yōu)先級越高，要被當(dāng)作交互式進(jìn)程所需要的 sleep_avg 上限也越低，即靜態(tài)優(yōu)先級高的進(jìn)程獲得這種獎勵的機(jī)會更大。

4) 就緒等待時間的獎勵

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

……
ret_from_exception:		#從異常中返回的入口
	preempt_stop				#解釋為 cli，關(guān)中斷，即從異常中返回過程中不允許搶占
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				
	#如果沒有置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)用中返回時的resched入口
	testb $_TIF_NEED_RESCHED, %cl
	jz work_notifysig			
	#不需要調(diào)度，那么肯定是因?yàn)橛行盘栃枰幚聿胚M(jìn)入work_pending的
work_resched:
	call schedule
	cli				
	movl TI_FLAGS(%ebp), %ecx
	andl $_TIF_WORK_MASK, %ecx	
	jz restore_all				#沒有work要做了，也不需要resched
	testb $_TIF_NEED_RESCHED, %cl
	jnz work_resched				#或者是需要調(diào)度，或者是有信號要處理
work_notifysig:
……

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

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

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

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

1) "拉"

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

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

a) 忙平衡

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

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

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

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

b) 空閑平衡

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

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

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

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

c) pull_task()

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

2) "推"
a) migration_thread()

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

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

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

b) move_task_away()

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

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

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

1) balance_node()
節(jié)點(diǎn)間的平衡作為 rebalance_tick() 函數(shù)中的一部分在 load_balance() 之前啟動（此時的 load_balance() 的工作集是節(jié)點(diǎn)內(nèi)的 cpu，也就是說，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)的算法涉及到幾個數(shù)據(jù)結(jié)構(gòu)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于 Linux 的市場來說，最緊迫、最活躍的需要在于嵌入式系統(tǒng)，但至少從調(diào)度系統(tǒng)來看，2.6 并沒有在這方面下很大功夫，也許開發(fā)者本人對此并無多大感受和興趣?？梢钥隙?，雖然 Linux 在市場上很火，但它的開發(fā)仍然不是市場驅(qū)動的。這或許會影響 Linux 的競爭力，但或許也因此能保持 Linux 開發(fā)的活力。

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

至今為止，還沒有聽到 Linux 的開發(fā)依賴于某種商業(yè)基金的報道，因此相對而言，Linux 的開發(fā)更具自由和隨意性，推廣 Linux 的人與開發(fā) Linux 的人基本上獨(dú)立運(yùn)作著，Linux 的受益者和 Linux 的開發(fā)者也沒有緊密結(jié)合。這對于 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月號第89篇

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