Linux 2.6 調度系統分析
在 2.4 之上進(jìn)步
楊沙洲國防科技大學(xué)計算機學(xué)院, 2004 年 4 月
2004 年 4 月
本文從 Linux 2.4 調度系統的缺陷入手，詳細分析了 Linux 2.6 調度系統的原理和實(shí)現細節，并對與調度系統相關(guān)的負載平衡、NUMA 結構以及實(shí)時(shí)性能進(jìn)行了分析和評價(jià)。文末，作者從調度系統的發(fā)展和實(shí)現出發(fā)，對 Linux 的發(fā)展特點(diǎn)和方向提出了自己的看法。
Linux 的市場(chǎng)非常廣闊，從桌面工作站到低端服務(wù)器，它都是任何商用操作系統的有力競爭對手。目前，Linux 正全力進(jìn)軍嵌入式系統和高端服務(wù)器系統領(lǐng)域，但它的技術(shù)缺陷限制了它的競爭力：缺乏對實(shí)時(shí)任務(wù)的支持，多處理機可擴展性差。在 2.4 內核中，造成這兩個(gè)弱項的關(guān)鍵原因之一就是調度器設計上的缺陷。
2.6 調度系統從設計之初就把開(kāi)發(fā)重點(diǎn)放在更好滿(mǎn)足實(shí)時(shí)性和多處理機并行性上，并且基本實(shí)現了它的設計目標。主要設計者，傳奇式人物 Ingo Molnar 將新調度系統的特性概括為如下幾點(diǎn)：
繼承和發(fā)揚 2.4 版調度器的特點(diǎn)： 交互式作業(yè)優(yōu)先
輕載條件下調度/喚醒的高性能
公平共享
基于優(yōu)先級調度
高 CPU 使用率
SMP 高效親和
實(shí)時(shí)調度和 cpu 綁定等調度手段
在此基礎之上的新特性： O(1)調度算法，調度器開(kāi)銷(xiāo)恒定（與當前系統負載無(wú)關(guān)），實(shí)時(shí)性能更好
高可擴展性，鎖粒度大幅度減小
新設計的 SMP 親和方法
優(yōu)化計算密集型的批處理作業(yè)的調度
重載條件下調度器工作更平滑
子進(jìn)程先于父進(jìn)程運行等其他改進(jìn)
在 2.5.x 的試驗版本中，新的調度器的開(kāi)發(fā)一直受到廣泛關(guān)注，實(shí)測證明它的確使系統性能得到很大改善。本文就從新設計的數據結構開(kāi)始，圍繞 2.6 對于 2.4 所作的改進(jìn)，對 2.6 調度系統的原理和實(shí)現細節進(jìn)行分析。2.6 調度器設計相當復雜，文中還存在很多需要繼續研究的地方，特別是各個(gè)調度參數的設定，隨著(zhù)核心版本的升級，可能還會(huì )繼續修正。
我們知道，在 2.4 內核中，就緒進(jìn)程隊列是一個(gè)全局數據結構，調度器對它的所有操作都會(huì )因全局自旋鎖而導致系統各個(gè)處理機之間的等待，使得就緒隊列成為一個(gè)明顯的瓶頸。
2.4 的就緒隊列是一個(gè)簡(jiǎn)單的以 runqueue_head 為頭的雙向鏈表，在 2.6 中，就緒隊列定義為一個(gè)復雜得多的數據結構 struct runqueue，并且，尤為關(guān)鍵的是，每一個(gè) CPU 都將維護一個(gè)自己的就緒隊列，--這將大大減小競爭。
O(1)算法中很多關(guān)鍵技術(shù)都與 runqueue 有關(guān)，所以，我們對調度器的分析就先從 runqueue 結構開(kāi)始。
1) prio_array_t *active, *expired, arrays[2]
runqueue 中最關(guān)鍵的數據結構。每個(gè) CPU 的就緒隊列按時(shí)間片是否用完分為兩部分，分別通過(guò) active 指針和 expired 指針訪(fǎng)問(wèn)，active 指向時(shí)間片沒(méi)用完、當前可被調度的就緒進(jìn)程，expired 指向時(shí)間片已用完的就緒進(jìn)程。每一類(lèi)就緒進(jìn)程都用一個(gè) struct prio_array 的結構表示：
struct prio_array { int nr_active; /* 本進(jìn)程組中的進(jìn)程數 */ struct list_head queue[MAX_PRIO]; /* 以?xún)?yōu)先級為索引的 HASH 表，見(jiàn)下 */ unsigned long bitmap[BITMAP_SIZE]; /* 加速以上 HASH 表訪(fǎng)問(wèn)的位圖，見(jiàn)下 */};
圖中的 task 并不是 task_struct 結構指針，而是 task_struct::run_list，這是一個(gè)小技巧，詳見(jiàn)下文 run_list 的解釋。
在 2.4 版的內核里，查找最佳候選就緒進(jìn)程的過(guò)程是在調度器 schedule() 中進(jìn)行的，每一次調度都要進(jìn)行一次（在 for 循環(huán)中調用 goodness()），這種查找過(guò)程與當前就緒進(jìn)程的個(gè)數相關(guān)，因此，查找所耗費的時(shí)間是 O(n) 級的，n 是當前就緒進(jìn)程個(gè)數。正因為如此，調度動(dòng)作的執行時(shí)間就和當前系統負載相關(guān)，無(wú)法給定一個(gè)上限，這與實(shí)時(shí)性的要求相違背。
在新的 O(1) 調度中，這一查找過(guò)程分解為 n 步，每一步所耗費的時(shí)間都是 O(1) 量級的。
prio_array 中包含一個(gè)就緒隊列數組，數組的索引是進(jìn)程的優(yōu)先級（共 140 級，詳見(jiàn)下 "static_prio" 屬性的說(shuō)明），相同優(yōu)先級的進(jìn)程放置在相應數組元素的鏈表 queue 中。調度時(shí)直接給出就緒隊列 active 中具有最高優(yōu)先級的鏈表中的第一項作為候選進(jìn)程（參見(jiàn)"調度器"），而優(yōu)先級的計算過(guò)程則分布到各個(gè)進(jìn)程的執行過(guò)程中進(jìn)行（見(jiàn)"優(yōu)化了的優(yōu)先級計算方法"）。
為了加速尋找存在就緒進(jìn)程的鏈表，2.6 核心又建立了一個(gè)位映射數組來(lái)對應每一個(gè)優(yōu)先級鏈表，如果該優(yōu)先級鏈表非空，則對應位為 1，否則為 0。核心還要求每個(gè)體系結構都構造一個(gè) sched_find_first_bit() 函數來(lái)執行這一搜索操作，快速定位第一個(gè)非空的就緒進(jìn)程鏈表。
采用這種將集中計算過(guò)程分散進(jìn)行的算法，保證了調度器運行的時(shí)間上限，同時(shí)在內存中保留更加豐富的信息的做法也加速了候選進(jìn)程的定位過(guò)程。這一變化簡(jiǎn)單而又高效，是 2.6 內核中的亮點(diǎn)之一。
arrays 二元數組是兩類(lèi)就緒隊列的容器，active 和 expired 分別指向其中一個(gè)。active 中的進(jìn)程一旦用完了自己的時(shí)間片，就被轉移到 expired 中，并設置好新的初始時(shí)間片；而當 active 為空時(shí)，則表示當前所有進(jìn)程的時(shí)間片都消耗完了，此時(shí)，active 和 expired 進(jìn)行一次對調，重新開(kāi)始下一輪的時(shí)間片遞減過(guò)程（參見(jiàn)"調度器"）。
回憶一下 2.4 調度系統，進(jìn)程時(shí)間片的計算是比較耗時(shí)的，在早期內核版本中，一旦時(shí)間片耗盡，就在時(shí)鐘中斷中重新計算時(shí)間片，后來(lái)為了提高效率，減小時(shí)鐘中斷的處理時(shí)間，2.4 調度系統在所有就緒進(jìn)程的時(shí)間片都耗完以后在調度器中一次性重算。這又是一個(gè) O(n) 量級的過(guò)程。為了保證 O(1) 的調度器執行時(shí)間，2.6 的時(shí)間片計算在各個(gè)進(jìn)程耗盡時(shí)間片時(shí)單獨進(jìn)行，而通過(guò)以上所述簡(jiǎn)單的對調來(lái)完成時(shí)間片的輪轉（參見(jiàn)"調度器"）。這又是 2.6 調度系統的一個(gè)亮點(diǎn)。
2) spinlock_t lock
runqueue 的自旋鎖，當需要對 runqueue 進(jìn)行操作時(shí)，仍然應該鎖定，但這個(gè)鎖定操作只影響一個(gè) CPU 上的就緒隊列，因此，競爭發(fā)生的概率要小多了。
3) task_t *curr
本 CPU 正在運行的進(jìn)程。
4) tast_t *idle
指向本 CPU 的 idle 進(jìn)程，相當于 2.4 中 init_tasks[this_cpu()] 的作用。
5) int best_expired_prio
記錄 expired 就緒進(jìn)程組中的最高優(yōu)先級（數值最?。?。該變量在進(jìn)程進(jìn)入 expired 隊列的時(shí)候保存（schedule_tick()），用途見(jiàn) "expired_timestamp"的解釋?zhuān)?div style="height:15px;">
6) unsigned long expired_timestamp
當新一輪的時(shí)間片遞減開(kāi)始后，這一變量記錄著(zhù)最早發(fā)生的進(jìn)程耗完時(shí)間片事件的時(shí)間（jiffies 的絕對值，在 schedule_tick() 中賦），它用來(lái)表征 expired 中就緒進(jìn)程的最長(cháng)等待時(shí)間。它的使用體現在 EXPIRED_STARVING(rq) 宏上。
上面已經(jīng)提到，每個(gè) CPU 上維護了兩個(gè)就緒隊列，active 和 expired。一般情況下，時(shí)間片結束的進(jìn)程應該從 active 隊列轉移到 expired 隊列中（schedule_tick()），但如果該進(jìn)程是交互式進(jìn)程，調度器就會(huì )讓其保持在 active 隊列上以提高它的響應速度。這種措施不應該讓其他就緒進(jìn)程等待過(guò)長(cháng)時(shí)間，也就是說(shuō)，如果 expired 隊列中的進(jìn)程已經(jīng)等待了足夠長(cháng)時(shí)間了，即使是交互式進(jìn)程也應該轉移到 expired 隊列上來(lái)，排空 active。這個(gè)閥值就體現在EXPIRED_STARVING(rq) 上：在 expired_timestamp 和 STARVATION_LIMIT 都不等于 0 的前提下，如果以下兩個(gè)條件都滿(mǎn)足，則 EXPIRED_STARVING() 返回真：
（當前絕對時(shí)間 - expired_timestamp） >= （STARVATION_LIMIT * 隊列中所有就緒進(jìn)程總數 + 1），也就是說(shuō) expired 隊列中至少有一個(gè)進(jìn)程已經(jīng)等待了足夠長(cháng)的時(shí)間；
正在運行的進(jìn)程的靜態(tài)優(yōu)先級比 expired 隊列中最高優(yōu)先級要低（best_expired_prio，數值要大），此時(shí)當然應該盡快排空 active 切換到expired 上來(lái)。
7) struct mm_struct *prev_mm
保存進(jìn)程切換后被調度下來(lái)的進(jìn)程（稱(chēng)之為 prev）的 active_mm 結構指針。因為在 2.6 中 prev 的 active_mm 是在進(jìn)程切換完成之后釋放的（mmdrop()），而此時(shí) prev 的 active_mm 項可能為 NULL，所以有必要在 runqueue 中預先保留。
8) unsigned long nr_running
本 CPU 上的就緒進(jìn)程數，該數值是 active 和 expired 兩個(gè)隊列中進(jìn)程數的總和，是說(shuō)明本 CPU 負載情況的重要參數（詳見(jiàn)"調度器相關(guān)的負載平衡"）。
9) unsigned long nr_switches
記錄了本 CPU 上自調度器運行以來(lái)發(fā)生的進(jìn)程切換的次數。
10) unsigned long nr_uninterruptible
記錄本 CPU 尚處于 TASK_UNINTERRUPTIBLE 狀態(tài)的進(jìn)程數，和負載信息有關(guān)。
11) atomic_t nr_iowait
記錄本 CPU 因等待 IO 而處于休眠狀態(tài)的進(jìn)程數。
12) unsigned long timestamp_last_tick
本就緒隊列最近一次發(fā)生調度事件的時(shí)間，在負載平衡的時(shí)候會(huì )用到（見(jiàn)"調度器相關(guān)的負載平衡"）。
13) int prev_cpu_load[NR_CPUS]
記錄進(jìn)行負載平衡時(shí)各個(gè) CPU 上的負載狀態(tài)（此時(shí)就緒隊列中的 nr_running 值），以便分析負載情況（見(jiàn)"調度器相關(guān)的負載平衡"）。
14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]
這兩個(gè)屬性?xún)H在 NUMA 體系結構下有效，記錄各個(gè) NUMA 節點(diǎn)上的就緒進(jìn)程數和上一次負載平衡操作時(shí)的負載情況（見(jiàn)"NUMA 結構下的調度"）。
15) task_t *migration_thread
指向本 CPU 的遷移進(jìn)程。每個(gè) CPU 都有一個(gè)核心線(xiàn)程用于執行進(jìn)程遷移操作（見(jiàn)"調度器相關(guān)的負載平衡"）。
16) struct list_head migration_queue
需要進(jìn)行遷移的進(jìn)程列表（見(jiàn)"調度器相關(guān)的負載平衡"）。
調度系統代碼結構 絕大多數調度系統的實(shí)現代碼，包括 runqueue 結構的定義，都在[kernel/sched.c]文件中，這樣做的目的是將所有調度系統的代碼集中起來(lái)，便于更新和替換。除非特別注明，本文所引代碼和函數實(shí)現均位于[kernel/sched.c]中。
2.6 版的內核仍然用 task_struct 來(lái)表征進(jìn)程，盡管對線(xiàn)程進(jìn)行了優(yōu)化，但線(xiàn)程的內核表示仍然與進(jìn)程相同。隨著(zhù)調度器的改進(jìn)，task_struct 的內容也有了改進(jìn)，交互式進(jìn)程優(yōu)先支持、內核搶占支持等新特性，在 task_struct 中都有所體現。在 task_struct 中，有的屬性是新增加的，有的屬性的值的含義發(fā)生了變化，而有的屬性?xún)H僅是改了一下名字。
進(jìn)程的狀態(tài)仍然用 state 表示，不同的是，2.6 里的狀態(tài)常量重新定義了，以方便位操作：
/* 節選自[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)程。
進(jìn)程發(fā)生調度事件的時(shí)間（單位是 nanosecond，見(jiàn)下）。包括以下幾類(lèi)：
被喚醒的時(shí)間（在 activate_task() 中設置）；
被切換下來(lái)的時(shí)間（schedule()）；
被切換上去的時(shí)間（schedule()）；
負載平衡相關(guān)的賦值（見(jiàn)"調度器相關(guān)的負載平衡"）。
從這個(gè)值與當前時(shí)間的差值中可以分別獲得"在就緒隊列中等待運行的時(shí)長(cháng)"、"運行時(shí)長(cháng)"等與優(yōu)先級計算相關(guān)的信息（見(jiàn)"優(yōu)化了的優(yōu)先級計算方法"）。
兩種時(shí)間單位 系統的時(shí)間是以 nanosecond（十億分之一秒）為單位的，但這一數值粒度過(guò)細，大部分核心應用僅能取得它的絕對值，感知不到它的精度。
時(shí)間相關(guān)的核心應用通常圍繞時(shí)鐘中斷進(jìn)行，在 Linux 2.6 中，系統時(shí)鐘每 1 毫秒中斷一次（時(shí)鐘頻率，用 HZ 宏表示，定義為 1000，即每秒中斷 1000 次，--2.4 中定義為 100，很多應用程序也仍然沿用 100 的時(shí)鐘頻率），這個(gè)時(shí)間單位稱(chēng)為一個(gè) jiffie。很多核心應用都是以 jiffies 作為時(shí)間單位，例如進(jìn)程的運行時(shí)間片。
jiffies 與絕對時(shí)間之間的轉換公式如下：
nanosecond=jiffies*1000000
核心用兩個(gè)宏來(lái)完成兩種時(shí)間單位的互換：JIFFIES_TO_NS()、NS_TO_JIFFIES()，很多時(shí)間宏也有兩種形式，例如 NS_MAX_SLEEP_AVG 和 MAX_SLEEP_AVG。
優(yōu)先級，相當于 2.4 中 goodness() 的計算結果，在 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)程。數值越大，表示進(jìn)程優(yōu)先級越小。
2.6 中，動(dòng)態(tài)優(yōu)先級不再統一在調度器中計算和比較，而是獨立計算，并存儲在進(jìn)程的 task_struct 中，再通過(guò)上面描述的 priority_array 結構自動(dòng)排序。
prio 的計算和很多因素相關(guān)，在"優(yōu)化了的優(yōu)先級計算方法"中會(huì )詳細討論。
靜態(tài)優(yōu)先級，與 2.4 的 nice 值意義相同，但轉換到與 prio 相同的取值區間。
nice 值沿用 Linux 的傳統，在 -20 到 19 之間變動(dòng)，數值越大，進(jìn)程的優(yōu)先級越小。nice 是用戶(hù)可維護的，但僅影響非實(shí)時(shí)進(jìn)程的優(yōu)先級。2.6 內核中不再存儲 nice 值，而代之以 static_prio。進(jìn)程初始時(shí)間片的大小僅決定于進(jìn)程的靜態(tài)優(yōu)先級，這一點(diǎn)不論是實(shí)時(shí)進(jìn)程還是非實(shí)時(shí)進(jìn)程都一樣，不過(guò)實(shí)時(shí)進(jìn)程的static_prio 不參與優(yōu)先級計算。
nice 與 static_prio 之間的關(guān)系如下：
static_prio = MAX_RT_PRIO + nice + 20
內核定義了兩個(gè)宏用來(lái)完成這一轉換：PRIO_TO_NICE()、NICE_TO_PRIO()。
表示進(jìn)程因什么原因進(jìn)入就緒態(tài)，這一原因會(huì )影響到調度優(yōu)先級的計算。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() 中，被恢復為 0，另一個(gè)就是 activate_task()，這個(gè)函數由 try_to_wake_up() 函數調用，用于激活休眠進(jìn)程：
如果是中斷服務(wù)程序調用的 activate_task()，也就是說(shuō)進(jìn)程由中斷激活，則該進(jìn)程最有可能是交互式的，因此，置 activated=2；否則置activated=1。
如果進(jìn)程是從 TASK_UNINTERRUPTIBLE 狀態(tài)中被喚醒的，則 activated=-1（在try_to_wake_up()函數中）。
activated 變量的具體含義和使用見(jiàn)"優(yōu)化了的優(yōu)先級計算方式"。
進(jìn)程的平均等待時(shí)間（以 nanosecond 為單位），在 0 到 NS_MAX_SLEEP_AVG 之間取值，初值為 0，相當于進(jìn)程等待時(shí)間與運行時(shí)間的差值。sleep_avg 所代表的含義比較豐富，既可用于評價(jià)該進(jìn)程的"交互程度"，又可用于表示該進(jìn)程需要運行的緊迫性。這個(gè)值是動(dòng)態(tài)優(yōu)先級計算的關(guān)鍵因子，sleep_avg 越大，計算出來(lái)的進(jìn)程優(yōu)先級也越高（數值越?。?。在下文"進(jìn)程平均等待時(shí)間 sleep_avg" 中會(huì )詳細分析 sleep_avg 的變化過(guò)程。
這個(gè)變量記錄了本進(jìn)程的"交互程度"，在 -CREDIT_LIMIT 到 CREDIT_LIMIT+1 之間取值。進(jìn)程被創(chuàng )建出來(lái)時(shí)，初值為 0，而后根據不同的條件加 1 減 1，一旦超過(guò) CREDIT_LIMIT（只可能等于 CREDIT_LIMIT+1），它就不會(huì )再降下來(lái)，表示進(jìn)程已經(jīng)通過(guò)了"交互式"測試，被認為是交互式進(jìn)程了。interactive_credit具體的變化過(guò)程在"更精確的交互式進(jìn)程優(yōu)先"中會(huì )詳細描述。
進(jìn)程切換計數。
9) time_slice
進(jìn)程的時(shí)間片余額，相當于 2.4 的 counter，但不再直接影響進(jìn)程的動(dòng)態(tài)優(yōu)先級。在"新的運行時(shí)間片表現"中專(zhuān)門(mén)分析了 time_slice 的行為。
10) first_time_slice
0 或 1，表示是否是第一次擁有時(shí)間片（剛創(chuàng )建的進(jìn)程）。這一變量用來(lái)判斷進(jìn)程結束時(shí)是否應當將自己的剩余時(shí)間片返還給父進(jìn)程（見(jiàn)"新的運行時(shí)間片表現"）。
11) run_list
前面提到，優(yōu)先級數組 prio_array 結構中按順序排列了各個(gè)優(yōu)先級下的所有進(jìn)程，但實(shí)際上數組中每一個(gè)元素都是 list_head 結構，以它為表頭的鏈表中的每一個(gè)元素也是 list_head，其中鏈接的就是 task_struct 中的 run_list 成員。這是一個(gè)節省空間、加速訪(fǎng)問(wèn)的小技巧：調度器在 prio_array 中找到相應的 run_list，然后通過(guò) run_list 在 task_struct 中的固定偏移量找到對應的 task_struct（參見(jiàn) enqueue_task()、dequeue_task() 和 list.h 中的操作）。
記錄當前 CPU 的活躍就緒隊列（runqueue::active）。
當前進(jìn)程的一些運行環(huán)境信息，其中有兩個(gè)結構成員與調度關(guān)系緊密：
preempt_count：初值為 0 的非負計數器，大于 0 表示核心不宜被搶占；
flags：其中有一個(gè) TIF_NEED_RESCHED 位，相當于 2.4 中的 need_resched 屬性，如果當前運行中的進(jìn)程此位為 1，則表示應該盡快啟動(dòng)調度器。
在 2.4 中，每個(gè)進(jìn)程的 task_struct 都位于該進(jìn)程核心棧的頂端（低址部分），內核可以通過(guò)棧寄存器 ESP 輕松訪(fǎng)問(wèn)到當前進(jìn)程的 task_struct。在 2.6 中，仍然需要頻繁訪(fǎng)問(wèn)這個(gè)名為 current 的數據結構，但現在，進(jìn)程核心棧頂保存的是其中的 thread_info 屬性，而不是完整的 task_struct 了。這樣做的好處是僅將最關(guān)鍵的、訪(fǎng)問(wèn)最頻繁的運行環(huán)境保存在核心棧里（仍然是兩個(gè)頁(yè)大?。?，而將 task_struct 大部分內容通過(guò) thread_info::task 指針保存在棧外，以方便擴充。thread_info 的分配方式和訪(fǎng)問(wèn)方式與 2.4 中的 task_struct 完全相同，現在的 current 需要這樣來(lái)訪(fǎng)問(wèn)：
/* 節選自[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()定義為：/* 節選自[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.6 中，time_slice 變量代替了 2.4 中的 counter 變量來(lái)表示進(jìn)程剩余運行時(shí)間片。time_slice 盡管擁有和 counter 相同的含義，但在內核中的表現行為已經(jīng)大相徑庭，下面分三個(gè)方面討論新的運行時(shí)間片表現：
和 counter 類(lèi)似，進(jìn)程的缺省時(shí)間片與進(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))
代入各個(gè)宏的值后，結果如圖所示：
可見(jiàn)，核心將 100~139 的優(yōu)先級映射到 200ms~10ms 的時(shí)間片上去，優(yōu)先級數值越大，則分配的時(shí)間片越小。
和 2.4 中進(jìn)程的缺省時(shí)間片比較，當 nice 為 0 時(shí)，2.6 的基準值 100ms 要大于 2.4 的 60ms。
進(jìn)程的平均時(shí)間片
核心定義進(jìn)程的平均時(shí)間片 AVG_TIMESLICE 為 nice 值為 0 的時(shí)間片長(cháng)度，根據上述公式計算所得大約是 102ms。這一數值將作為進(jìn)程運行時(shí)間的一個(gè)基準值參與優(yōu)先級計算。
進(jìn)程的 time_slice 值代表進(jìn)程的運行時(shí)間片剩余大小，在進(jìn)程創(chuàng )建時(shí)與父進(jìn)程平分時(shí)間片，在運行過(guò)程中遞減，一旦歸 0，則按 static_prio 值重新賦予上述基準值，并請求調度。時(shí)間片的遞減和重置在時(shí)鐘中斷中進(jìn)行（sched_tick()），除此之外，time_slice 值的變化主要在創(chuàng )建進(jìn)程和進(jìn)程退出過(guò)程中：
a) 進(jìn)程創(chuàng )建
和 2.4 類(lèi)似，為了防止進(jìn)程通過(guò)反復 fork 來(lái)偷取時(shí)間片，子進(jìn)程被創(chuàng )建時(shí)并不分配自己的時(shí)間片，而是與父進(jìn)程平分父進(jìn)程的剩余時(shí)間片。也就是說(shuō)，fork 結束后，兩者時(shí)間片之和與原先父進(jìn)程的時(shí)間片相等。
b) 進(jìn)程退出
進(jìn)程退出時(shí)（sched_exit()），根據 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)程而受到"獎勵"相對應）。如果進(jìn)程已經(jīng)用完了從父進(jìn)程那分得的時(shí)間片，就沒(méi)有必要返還了（這一點(diǎn)在 2.4 中沒(méi)有考慮）。
在 2.4 中，進(jìn)程剩余時(shí)間片是除 nice 值以外對動(dòng)態(tài)優(yōu)先級影響最大的因素，并且休眠次數多的進(jìn)程，它的時(shí)間片會(huì )不斷疊加，從而算出的優(yōu)先級也更大，調度器正是用這種方式來(lái)體現對交互式進(jìn)程的優(yōu)先策略。但實(shí)際上休眠次數多并不表示該進(jìn)程就是交互式的，只能說(shuō)明它是 IO 密集型的，因此，這種方法精度很低，有時(shí)因為誤將頻繁訪(fǎng)問(wèn)磁盤(pán)的數據庫應用當作交互式進(jìn)程，反而造成真正的用戶(hù)終端響應遲緩。
2.6 的調度器以時(shí)間片是否耗盡為標準將就緒進(jìn)程分成 active、expired 兩大類(lèi)，分別對應不同的就緒隊列，前者相對于后者擁有絕對的調度優(yōu)先權--僅當active 進(jìn)程時(shí)間片都耗盡，expired 進(jìn)程才有機會(huì )運行。但在 active 中挑選進(jìn)程時(shí)，調度器不再將進(jìn)程剩余時(shí)間片作為影響調度優(yōu)先級的一個(gè)因素，并且為了滿(mǎn)足內核可剝奪的要求，時(shí)間片太長(cháng)的非實(shí)時(shí)交互式進(jìn)程還會(huì )被人為地分成好幾段（每一段稱(chēng)為一個(gè)運行粒度，定義見(jiàn)下）運行，每一段運行結束后，它都從 cpu 上被剝奪下來(lái)，放置到對應的 active 就緒隊列的末尾，為其他具有同等優(yōu)先級的進(jìn)程提供運行的機會(huì )。
這一操作在 schedule_tick() 對時(shí)間片遞減之后進(jìn)行。此時(shí)，即使進(jìn)程的時(shí)間片沒(méi)耗完，只要該進(jìn)程同時(shí)滿(mǎn)足以下四個(gè)條件，它就會(huì )被強制從 cpu 上剝奪下來(lái)，重新入隊等候下一次調度：
進(jìn)程當前在 active 就緒隊列中；
該進(jìn)程是交互式進(jìn)程（TASK_INTERACTIVE()返回真，見(jiàn)"更精確的交互式進(jìn)程優(yōu)先",nice 大于 12 時(shí)，該宏返回恒假）；
該進(jìn)程已經(jīng)耗掉的時(shí)間片（時(shí)間片基準值減去剩余時(shí)間片）正好是運行粒度的整數倍；
剩余時(shí)間片不小于運行粒度
運行粒度的定義運行粒度 TIMESLICE_GRANULARITY 被定義為與進(jìn)程的 sleep_avg 和系統總 CPU 數相關(guān)的宏。因為 sleep_avg 實(shí)際上代表著(zhù)進(jìn)程的非運行時(shí)間與運行時(shí)間的差值，與交互程度判斷關(guān)系密切，所以，運行粒度的定義說(shuō)明了內核的以下兩個(gè)調度策略： 進(jìn)程交互程度越高，運行粒度越小，這是交互式進(jìn)程的運行特點(diǎn)所允許的；與之對應，CPU-bound 的進(jìn)程為了避免 Cache 刷新，不應該分片；
系統 CPU 數越多，運行粒度越大。
在 2.4 內核中，優(yōu)先級的計算和候選進(jìn)程的選擇集中在調度器中進(jìn)行，無(wú)法保證調度器的執行時(shí)間，這一點(diǎn)在前面介紹 runqueue 數據結構的時(shí)候已經(jīng)提及。2.6 內核中候選進(jìn)程是直接從已按算法排序的優(yōu)先級隊列數組中選取出來(lái)的，而優(yōu)先級的計算則分散到多處進(jìn)行。這一節分成兩個(gè)部分對這種新的優(yōu)先級計算方法進(jìn)行描述，一部分是優(yōu)先級計算過(guò)程，一部分是優(yōu)先級計算（以及進(jìn)程入隊）的時(shí)機。
動(dòng)態(tài)優(yōu)先級的計算主要由 effect_prio() 函數完成，該函數實(shí)現相當簡(jiǎn)單，從中可見(jiàn)非實(shí)時(shí)進(jìn)程的優(yōu)先級僅決定于靜態(tài)優(yōu)先級（static_prio）和進(jìn)程的sleep_avg 值兩個(gè)因素，而實(shí)時(shí)進(jìn)程的優(yōu)先級實(shí)際上是在 setscheduler() 中設置的（詳見(jiàn)"調度系統的實(shí)時(shí)性能"，以下僅考慮非實(shí)時(shí)進(jìn)程），且一經(jīng)設定就不再改變。相比較而言，2.4 的 goodness() 函數甚至要更加復雜,它考慮的 CPU Cache 失效開(kāi)銷(xiāo)和內存切換的開(kāi)銷(xiāo)這里都已經(jīng)不再考慮。
2.6 的動(dòng)態(tài)優(yōu)先級算法的實(shí)現關(guān)鍵在 sleep_avg 變量上，在 effective_prio() 中，sleep_avg 的范圍是 0~MAX_SLEEP_AVG，經(jīng)過(guò)以下公式轉換后變成-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ìn)程的動(dòng)態(tài)優(yōu)先級（并限制在 MAX_RT_PRIO和MAX_PRIO 之間），bonus 越小，動(dòng)態(tài)優(yōu)先級數值越大，優(yōu)先級越低。也就是說(shuō)，sleep_avg 越大，優(yōu)先級也越高。
MAX_BONUS 定義為 MAX_USER_PRIO*PRIO_BONUS_RATIO/100，也就是說(shuō)，sleep_avg 對動(dòng)態(tài)優(yōu)先級的影響僅在靜態(tài)優(yōu)先級的用戶(hù)優(yōu)先級區（100~140）的1/4區間（±5）之內，相對而言，靜態(tài)優(yōu)先級，也就是用戶(hù)指定的 nice 值在優(yōu)先級計算的比重要大得多。這也是 2.6 調度系統中變化比較大的一個(gè)地方，調度器傾向于更多地由用戶(hù)自行設計進(jìn)程的執行優(yōu)先級。
sleep_avg 反映了調度系統的兩個(gè)策略：交互式進(jìn)程優(yōu)先和分時(shí)系統的公平共享，在下一節中我們還要專(zhuān)門(mén)分析。
優(yōu)先級的計算不再集中在調度器選擇候選進(jìn)程的時(shí)候進(jìn)行了，只要進(jìn)程狀態(tài)發(fā)生改變，核心就有可能計算并設置進(jìn)程的動(dòng)態(tài)優(yōu)先級：
a) 創(chuàng )建進(jìn)程
在wake_up_forked_process()中，子進(jìn)程繼承了父進(jìn)程的動(dòng)態(tài)優(yōu)先級，并添加到父進(jìn)程所在的就緒隊列中。
如果父進(jìn)程不在任何就緒隊列中（例如它是 IDLE 進(jìn)程），那么就通過(guò) effect_prio() 函數計算出子進(jìn)程的優(yōu)先級，而后根據計算結果將子進(jìn)程放置到相應的就緒隊列中。
b) 喚醒休眠進(jìn)程
核心調用 recalc_task_prio() 設置從休眠狀態(tài)中醒來(lái)的進(jìn)程的動(dòng)態(tài)優(yōu)先級，再根據優(yōu)先級放置到相應就緒隊列中。
c) 調度到從 TASK_INTERRUPTIBLE 狀態(tài)中被喚醒的進(jìn)程
實(shí)際上此時(shí)調度器已經(jīng)選定了候選進(jìn)程，但考慮到這一類(lèi)型的進(jìn)程很有可能是交互式進(jìn)程，因此此時(shí)仍然調用 recalc_task_prio() 對該進(jìn)程的優(yōu)先級進(jìn)行修正（詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"），修正的結果將在下一次調度時(shí)體現。
d) 進(jìn)程因時(shí)間片相關(guān)的原因被剝奪 cpu
在 schedule_tick() 中（由時(shí)鐘中斷啟動(dòng)），進(jìn)程可能因兩種原因被剝奪 cpu，一是時(shí)間片耗盡，一是因時(shí)間片過(guò)長(cháng)而分段。這兩種情況都會(huì )調用effect_prio() 重新計算優(yōu)先級，重新入隊。
e) 其它時(shí)機
這些其它時(shí)機包括 IDLE 進(jìn)程初始化（init_idle()）、負載平衡（move_task_away()，詳見(jiàn)"調度器相關(guān)的負載平衡"）以及修改 nice 值（set_user_nice()）、修改調度策略（setscheduler()）等主動(dòng)要求改變優(yōu)先級的情況。
由上可見(jiàn)，2.6 中動(dòng)態(tài)優(yōu)先級的計算過(guò)程在各個(gè)進(jìn)程運行過(guò)程中進(jìn)行，避免了類(lèi)似 2.4 系統中就緒進(jìn)程很多時(shí)計算過(guò)程耗時(shí)過(guò)長(cháng)，從而無(wú)法預計進(jìn)程的響應時(shí)間的問(wèn)題。同時(shí)，影響動(dòng)態(tài)優(yōu)先級的因素集中反映在 sleep_avg 變量上。
進(jìn)程的 sleep_avg 值是決定進(jìn)程動(dòng)態(tài)優(yōu)先級的關(guān)鍵，也是進(jìn)程交互程度評價(jià)的關(guān)鍵，它的設計是 2.6 調度系統中最為復雜的一個(gè)環(huán)節，可以說(shuō)，2.6 調度系統的性能改進(jìn)，很大一部分應該歸功于 sleep_avg 的設計。這一節，我們將專(zhuān)門(mén)針對 sleep_avg 的變化和它對調度的影響進(jìn)行分析。
內核中主要有四個(gè)地方會(huì )對 sleep_avg 進(jìn)行修改：休眠進(jìn)程被喚醒時(shí)（activate_task()調用 recalc_task_prio() 函數）、TASK_INTERRUPTIBLE 狀態(tài)的進(jìn)程被喚醒后第一次調度到（schedule()中調用 recalc_task_prio()）、進(jìn)程從 CPU 上被剝奪下來(lái)（schedule()函數中）、進(jìn)程創(chuàng )建和進(jìn)程退出，其中recalc_task_prio() 是其中復雜度最高的，它通過(guò)計算進(jìn)程的等待時(shí)間（或者是在休眠中等待，或者是在就緒隊列中等待）對優(yōu)先級的影響來(lái)重置優(yōu)先級。
此時(shí) activate_task() 以喚醒的時(shí)間作為參數調用 recalc_task_prio()，計算休眠等待的時(shí)間對優(yōu)先級的影響。
在 recalc_task_prio() 中，sleep_avg 可能有四種賦值，并最終都限制在 NS_MAX_SLEEP_AVG 以?xún)龋?div style="height:15px;">
a) 不變
從 TASK_UNINTERRUPTIBLE 狀態(tài)中被喚醒（activated==-1）、交互程度不夠高（!HIGH_CREDIT(p)）的用戶(hù)進(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)）的用戶(hù)進(jìn)程(p->mm!=NULL)），如果它的 sleep_avg 沒(méi)有達到 INTERACTIVE_SLEEP(p)，但如果加上本次休眠時(shí)間 sleep_time 就達到了，則它的 sleep_avg 就等于 INTERACTIVE_SLEEP(p)。
c) MAX_SLEEP_AVG-AVG_TIMESLICE
用戶(hù)進(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
如果不滿(mǎn)足上面所有情況，則將 sleep_time 疊加到 sleep_avg 上。此時(shí)，sleep_time 要經(jīng)過(guò)兩次修正：
i. 根據 sleep_avg 的值進(jìn)行修正，sleep_avg 越大，修正后的 sleep_time 越?。?div style="height:15px;">
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)程的基準時(shí)間片以?xún)?，以此作為?cpu-bound 的進(jìn)程的優(yōu)先級懲罰。
總的來(lái)說(shuō)，本次等待時(shí)間越長(cháng)，sleep_avg 就應該更大，但核心排除了兩種情況：
從 TASK_UNINTERRUPTIBLE 狀態(tài)醒來(lái)的進(jìn)程，尤其是那些休眠時(shí)間比較長(cháng)的進(jìn)程，很有可能是等待某種資源而休眠，它們不應該受到等待時(shí)間的優(yōu)先級獎勵，它的 sleep_avg 被限制在 INTERACTIVE_SLEEP(p) 范圍內（或不超過(guò)太多）（INTERACTIVE_SLEEP(p) 的含義見(jiàn)后），--這一限制對已經(jīng)認定為是交互式的進(jìn)程無(wú)效。
不是從 TASK_UNITERRUPTIBLE 狀態(tài)中醒來(lái)的進(jìn)程，如果本次等待時(shí)間過(guò)長(cháng)，也不應該受到等待時(shí)間的優(yōu)先級獎勵。
INTERACTIVE_SLEEP(p) 與 nice 的關(guān)系
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
這個(gè)宏與進(jìn)程 nice 值成正比，說(shuō)明優(yōu)先級越低的進(jìn)程，允許它在"交互式休眠"狀態(tài)下的時(shí)間越長(cháng)。
調度器挑選出候選進(jìn)程之后，如果發(fā)現它是從 TASK_INTERRUPTIBLE 休眠中醒來(lái)后第一次被調度到（activated>0），調度器將根據它在就緒隊列上等待的時(shí)長(cháng)調用 recalc_task_prio() 重新調整進(jìn)程的 sleep_avg。
recalc_task_prio() 調整的過(guò)程與"休眠進(jìn)程被喚醒時(shí)"的情況是一模一樣的，所不同的是，此時(shí)作為等待時(shí)間 sleep_time 參與計算的不是進(jìn)程的休眠時(shí)間，而是進(jìn)程在就緒隊列上等待調度的時(shí)間。并且，如果進(jìn)程不是被中斷喚醒的（activated==1），sleep_time 還將受到約束（delta=delta*ON_RUNQUEUE_WEIGHT/100），因為此時(shí)該進(jìn)程不是交互式進(jìn)程的可能性很大。從上面對 recalc_task_prio() 的分析可知，sleep_time 減小一般來(lái)說(shuō)就意味著(zhù)優(yōu)先級會(huì )相應降低，所以，這一獎勵說(shuō)明調度器在進(jìn)一步減小進(jìn)程的響應時(shí)間，尤其是交互式進(jìn)程。
前面說(shuō)過(guò)，sleep_avg 是進(jìn)程的"平均"等待時(shí)間，recalc_task_prio() 計算了等待時(shí)間，在 schedule() 中，被切換下來(lái)的進(jìn)程的 sleep_avg 需要減去進(jìn)程本次運行的時(shí)間 run_time（并保證結果不小于 0），這就是對"平均"的體現：等待得越久，sleep_avg 越大，進(jìn)程越容易被調度到；而運行得越久，sleep_avg 越小，進(jìn)程越不容易調度到。
run_time 可以用系統當前時(shí)間與進(jìn)程 timestamp（上一次被調度運行的時(shí)間）的差值表示，但不能超過(guò) NS_MAX_SLEEP_AVG。對于交互式進(jìn)程（HIGHT_CREDIT(p) 為真，見(jiàn)"更精確的交互式進(jìn)程優(yōu)先"），run_time 還要根據 sleep_avg 的值進(jìn)行調整：
run_time = run_time / (sleep_avg*MAX_BONUS/MAX_SLEEP_AVG)
這樣調整的結果是交互式進(jìn)程的 run_time 小于實(shí)際運行時(shí)間，sleep_avg 越大，則 run_time 減小得越多，因此被切換下來(lái)的進(jìn)程最后計算所得的 sleep_avg 也就越大，動(dòng)態(tài)優(yōu)先級也隨之變大。交互式進(jìn)程可以借此獲得更多被執行的機會(huì )。
在 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)先級會(huì )比父進(jìn)程稍低（但子進(jìn)程仍然會(huì )置于與父進(jìn)程相同的就緒隊列上，位置在父進(jìn)程之前--也就是"前言"所說(shuō)"子進(jìn)程先于父進(jìn)程運行"）。
一個(gè)進(jìn)程結束運行時(shí)，如果它的交互程度比父進(jìn)程低（sleep_avg 較?。?，那么核心將在 sched_exit() 中對其父進(jìn)程的 sleep_avg 進(jìn)行調整，調整公式如下（以 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，再補償子進(jìn)程 sleep_avg 的 1/4，優(yōu)先級也將隨之有所下降，子進(jìn)程的交互程度與父進(jìn)程相差越大，則優(yōu)先級的懲罰也越明顯。
利用進(jìn)程平均等待時(shí)間來(lái)衡量進(jìn)程的優(yōu)先級，使得宏觀(guān)上相同靜態(tài)優(yōu)先級的所有進(jìn)程的等待時(shí)間和運行時(shí)間的比值趨向一致，反映了 Linux 要求各進(jìn)程分時(shí)共享 cpu 的公平性。另一方面，sleep_avg 還是進(jìn)程交互式程度的衡量標準。
交互式進(jìn)程優(yōu)先策略的實(shí)際效果在 2.4 內核中受到廣泛批評，在 2.6 內核中，這一點(diǎn)得到了很大改進(jìn)，總體來(lái)說(shuō)，內核有四處對交互式進(jìn)程的優(yōu)先考慮：
上文已經(jīng)詳細分析了 sleep_avg 對進(jìn)程優(yōu)先級的影響，從中可以看出，交互式進(jìn)程因為休眠次數多、時(shí)間長(cháng)，它們的 sleep_avg 也會(huì )相應地更大一些，所以計算出來(lái)的優(yōu)先級也會(huì )相應高一些。
系統引入了一個(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)程就被認為是交互式進(jìn)程。
interactive_credit 的初始值為 0，在兩種情況下它會(huì )加 1，這兩種場(chǎng)合都在 recalc_task_prio() 函數中：
用戶(hù)進(jìn)程(p->mm!=NULL)，如果不是從 TASK_UNINTERRUPTIBLE 休眠中被喚醒的（p->activated!=-1），且等待的時(shí)間（包括在休眠中等待和在就緒隊列中等待，）超過(guò)了一定限度（sleep_time>INTERACTIVE_SLEEP(p)）；
除以上情況外，sleep_avg 經(jīng)過(guò) sleep_time 調整后，如果大于 NS_MAX_SLEEP_AVG。
無(wú)論哪種情況，一旦 interactive_credit 超過(guò)（大于）CREDIT_LIMIT 了，它都不再增加，因此 interactive_credit 最大值就是 CREDIT_LIMIT+1。
interactive_credit 的遞減發(fā)生在 schedule() 函數中。當調度器用運行時(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，且一旦它達到 CREDIT_LIMIT+1 的最大值就不會(huì )再被減下來(lái)--它將保持在 CREDIT_LIMIT+1 的高值上。
這就是說(shuō)，只有進(jìn)程多次休眠，且休眠的時(shí)間足夠長(cháng)（長(cháng)于運行的時(shí)間，長(cháng)于"交互式休眠"時(shí)間），進(jìn)程才有可能被列為交互式進(jìn)程；而一旦被認為是交互式進(jìn)程，則永遠按交互式進(jìn)程對待。
采用 HIGH_CREDIT() 標準斷言的交互式進(jìn)程主要在以下兩處得到優(yōu)先級計算上的獎勵：
當進(jìn)程從 cpu 上調度下來(lái)的時(shí)侯，如果是交互式進(jìn)程，則它參與優(yōu)先級計算的運行時(shí)間會(huì )比實(shí)際運行時(shí)間小，以此獲得較高的優(yōu)先級（見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"）；
交互式進(jìn)程處于 TASK_UNINTERRUPTIBLE 狀態(tài)下的休眠時(shí)間也會(huì )疊加到 sleep_avg 上，從而獲得優(yōu)先級獎勵（見(jiàn)"進(jìn)程平均等待時(shí)間sleep_avg"）；
核心另有一處不采用 HIGH_CREDIT() 這種累積方式來(lái)判斷的交互式進(jìn)程優(yōu)先機制，那里使用的是 TASK_INTERACTIVE() 宏（布爾值）：
prio <= static_prio-DELTA(p)
當進(jìn)程時(shí)間片耗盡時(shí)，如果該宏返回真(同時(shí) expired 隊列沒(méi)有等待過(guò)長(cháng)的時(shí)間，見(jiàn)"新的數據結構 runqueue""expired_timestamp"條），則該進(jìn)程不進(jìn)入 expired 隊列而是保留在 active 隊列中，以便盡快調度到這一交互式進(jìn)程。動(dòng)態(tài)優(yōu)先級在調度到該進(jìn)程時(shí)在 effective_prio() 中算出：prio=static_prio-bonus(sleep_avg)（bonus(sleep_avg) 表示 bonus 是關(guān)于 sleep_avg 的函數，見(jiàn)"優(yōu)先級計算過(guò)程"），而 DELTA(p) 與進(jìn)程的 nice 值有關(guān)，可表示為delta(nice)。bonus 與 sleep_avg 的關(guān)系在"優(yōu)先級計算過(guò)程"一節中已經(jīng)用圖說(shuō)明了，delta 和 nice 之間的關(guān)系見(jiàn)下圖：
nice 值的范圍是 -20~19，DELTA(p)將其轉換到 -5~+5 再加上一個(gè)INTERACTIVE_DELTA常量的范圍內：TASK_NICE(p) * MAX_BONUS/40 + INTERACTIVE_DELTA，其中 INTERACTIVE_DELTA 等于 2。
經(jīng)過(guò)轉換，TASK_INTERACTIVE(p) 變?yōu)?"delta(nice) 是否不大于 bonus(sleep_avg)"。將 sleep_avg 表示為 JIFFIES 的形式，并代入常數，delta(nice)<=bonus(sleep_avg) 可以表示為：
nice/4+2 <= bonus，-5<=bonus<=+5
從中可以看出，nice 大于 12 時(shí)，此不等式恒假，也就是說(shuō)此時(shí)進(jìn)程永遠不會(huì )被當作交互式進(jìn)程看待；而進(jìn)程靜態(tài)優(yōu)先級越高，要被當作交互式進(jìn)程所需要的 sleep_avg 上限也越低，即靜態(tài)優(yōu)先級高的進(jìn)程獲得這種獎勵的機會(huì )更大。
4) 就緒等待時(shí)間的獎勵
因為經(jīng)常處于 TASK_INTERRUPTIBLE 狀態(tài)的進(jìn)程最有可能是交互式的，因此，這一類(lèi)進(jìn)程從休眠中醒來(lái)后在就緒隊列上等待調度的時(shí)間長(cháng)短也將影響進(jìn)程的動(dòng)態(tài)優(yōu)先級。
這一工作在調度器（schedule()）選擇上這一類(lèi)型的進(jìn)程之后進(jìn)行，并且考慮到交互式進(jìn)程通常都是在中斷中被喚醒的，所以核心還記錄了這一信息，對不由中斷喚醒的進(jìn)程實(shí)行獎勵約束（詳見(jiàn)"進(jìn)程平均等待時(shí)間sleep_avg"）。
有了以上的準備工作之后，現在我們可以看看調度器的主流程了。
和 2.4 的調度器相比，2.6 的 schedule()函數要更加簡(jiǎn)單一些，減少了鎖操作，優(yōu)先級計算也拿到調度器外進(jìn)行了。為減少進(jìn)程在 cpu 間跳躍，2.4 中將被切換下來(lái)的進(jìn)程重新調度到另一個(gè) cpu 上的動(dòng)作也省略了。調度器的基本流程仍然可以概括為相同的五步：
清理當前運行中的進(jìn)程（prev）
選擇下一個(gè)投入運行的進(jìn)程（next）
設置新進(jìn)程的運行環(huán)境
執行進(jìn)程上下文切換
后期整理
2.6 的調度器工作流程保留了很多 2.4 系統中的動(dòng)作，進(jìn)程切換的細節也與 2.4 基本相同（由 context_switch() 開(kāi)始）。為了不與 2.4 系統的調度器分析重復，我們按照調度器對各個(gè)數據結構的影響來(lái)分析調度器的工作流程，重點(diǎn)在與 2.4 調度器不同的部分，與之相同或相似的部分相信讀者結合代碼和上文的技術(shù)分析很容易理解。同時(shí)，2.6 的調度器中還增加了對負載平衡和內核搶占運行的支持，因為內容比較獨立，我們也將其放在單獨的章節中。
主要是因為就緒隊列分布到各個(gè) cpu 上了，2.6 調度器中僅涉及兩個(gè)鎖的操作：就緒隊列鎖 runqueue::lock，全局核心鎖 kernel_flag。對就緒隊列鎖的操作保證了就緒隊列的操作唯一性，核心鎖的意義與 2.4 中相同：調度器在執行切換之前應將核心鎖解開(kāi)（release_kernel_lock()），完成調度后恢復鎖狀態(tài)（reacquire_kernel_lock()）。進(jìn)程的鎖狀態(tài)依然保存在task_struct::lock_depth屬性中。
因為調度器中沒(méi)有任何全局的鎖操作，2.6 調度器本身的運行障礙幾乎不存在了。
調度器主要影響 prev 進(jìn)程的兩個(gè)屬性：
sleep_avg 減去了本進(jìn)程的運行時(shí)間（詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"的"被切換下來(lái)的進(jìn)程"）；
timestamp 更新為當前時(shí)間，記錄被切換下去的時(shí)間，用于計算進(jìn)程等待時(shí)間。
prev被切換下來(lái)后，即使修改了 sleep_avg，它在就緒隊列中的位置也不會(huì )改變，它將一直以此優(yōu)先級參加調度直至發(fā)生狀態(tài)改變（比如休眠）。
在前面介紹 runqueue 數據結構的時(shí)候，我們已經(jīng)分析了 active/expired 兩個(gè)按優(yōu)先級排序的就緒進(jìn)程隊列的功能，2.6 的調度器對候選進(jìn)程的定位有三種可能：
active 就緒隊列中優(yōu)先級最高且等待時(shí)間最久的進(jìn)程；
當前 runqueue 中沒(méi)有就緒進(jìn)程了，則啟動(dòng)負載平衡從別的 cpu 上轉移進(jìn)程，再進(jìn)行挑選（詳見(jiàn)"調度器相關(guān)的負載平衡"）；
如果仍然沒(méi)有就緒進(jìn)程，則將本 cpu 的 IDLE 進(jìn)程設為候選。
在挑選出 next 之后，如果發(fā)現 next 是從 TASK_INTERRUPTIBLE 休眠中醒來(lái)后第一次被調度到（activated>0），調度器將根據 next 在就緒隊列上等待的時(shí)長(cháng)重新調整進(jìn)程的優(yōu)先級（并存入就緒隊列中新的位置，詳見(jiàn)"進(jìn)程平均等待時(shí)間 sleep_avg"）。
除了 sleep_avg 和 prio 的更新外，next 的 timestamp 也更新為當前時(shí)間，用于下一次被切換下來(lái)時(shí)計算運行時(shí)長(cháng)。
這里說(shuō)的外環(huán)境指的是調度器對除參與調度的進(jìn)程以及所在就緒隊列以外的環(huán)境的影響，主要包括切換計數處理和 cpu 狀態(tài)的更新（qsctr）。
在2.4 系統中，在核心態(tài)運行的任何進(jìn)程，只有當它調用 schedule() 主動(dòng)放棄控制時(shí)，調度器才有機會(huì )選擇其他進(jìn)程運行，因此我們說(shuō) Linux 2.4 的內核是不可搶占運行的。缺乏這一支持，核心就無(wú)法保證實(shí)時(shí)任務(wù)的及時(shí)響應，因此也就滿(mǎn)足不了實(shí)時(shí)系統（即使是軟實(shí)時(shí)）的要求。
2.6 內核實(shí)現了搶占運行，沒(méi)有鎖保護的任何代碼段都有可能被中斷，它的實(shí)現，對于調度技術(shù)來(lái)說(shuō)，主要就是增加了調度器運行的時(shí)機。我們知道，在 2.4 內核里，調度器有兩種啟動(dòng)方式：主動(dòng)式和被動(dòng)式，其中被動(dòng)方式啟動(dòng)調度器只能是在控制從核心態(tài)返回用戶(hù)態(tài)的時(shí)候，因此才有內核不可搶占的特點(diǎn)。2.6 中，調度器的啟動(dòng)方式仍然可分為主動(dòng)式和被動(dòng)式兩種，所不同的是被動(dòng)啟動(dòng)調度器的條件放寬了很多。它的修改主要在 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 #"返回用戶(hù)態(tài)"和"在核心態(tài)中返回"的分路口ENTRY(resume_userspace) climovl TI_FLAGS(%ebp), %ecx andl $_TIF_WORK_MASK, %ecx # （_TIF_NOTIFY_RESUME | _TIF_SIGPENDING # | _TIF_NEED_RESCHED） jne work_pending jmp restore_allENTRY(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位，則不需要調度 testl $IF_MASK,EFLAGS(%esp) jz restore_all #如果關(guān)中斷了，則不允許調度 movl $PREEMPT_ACTIVE,TI_PRE_COUNT(%ebp) #preempt_count 設為 PREEMPT_ACTIVE， 通知調度器目前這次調度正處在一次搶 #占調度中 sti call schedule movl $0,TI_PRE_COUNT(%ebp) #preemmpt_count清0 cli jmp need_resched……work_pending: #這也是從系統調用中返回時(shí)的resched入口 testb $_TIF_NEED_RESCHED, %cl jz work_notifysig #不需要調度，那么肯定是因為有信號需要處理才進(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 #或者是需要調度，或者是有信號要處理work_notifysig:……
現在，無(wú)論是返回用戶(hù)態(tài)還是返回核心態(tài)，都有可能檢查 NEED_RESCHED 的狀態(tài)；返回核心態(tài)時(shí)，只要 preempt_count 為 0，即當前進(jìn)程目前允許搶占，就會(huì )根據 NEED_RESCHED 狀態(tài)選擇調用 schedule()。在核心中，因為至少時(shí)鐘中斷是不斷發(fā)生的，因此，只要有進(jìn)程設置了當前進(jìn)程的 NEED_RESCHED 標志，當前進(jìn)程馬上就有可能被搶占，而無(wú)論它是否愿意放棄 cpu，即使是核心進(jìn)程也是如此。
調度器的工作時(shí)機
除核心應用主動(dòng)調用調度器之外，核心還在應用不完全感知的情況下在以下三種時(shí)機中啟動(dòng)調度器工作：
從中斷或系統調用中返回；
進(jìn)程重新允許搶占（preempt_enable()調用preempt_schedule()）；
主動(dòng)進(jìn)入休眠（例如wait_event_interruptible()接口）
在 2.4 內核中，進(jìn)程p被切換下來(lái)之后，如果還有 cpu 空閑，或者該 cpu 上運行的進(jìn)程優(yōu)先級比自己低，那么 p 就會(huì )被調度到那個(gè) cpu 上運行，核心正是用這種辦法來(lái)實(shí)現負載的平衡。
簡(jiǎn)單是這種負載平衡方式最大的優(yōu)點(diǎn)，但它的缺點(diǎn)也比較明顯：進(jìn)程遷移比較頻繁，交互式進(jìn)程（或高優(yōu)先級的進(jìn)程）可能還會(huì )在 cpu 之間不斷"跳躍"。即使是在 SMP 的環(huán)境中，進(jìn)程遷移也是有代價(jià)的，2.4 系統的使用經(jīng)驗表明，這種負載平衡方式弊大于利，解決這一"SMP親和"的問(wèn)題是 2.6 系統設計的目標之一。
2.6 調度系統采用相對集中的負載平衡方案，分為"推"和"拉"兩類(lèi)操作：
1) "拉"
當某個(gè) cpu 負載過(guò)輕而另一個(gè) cpu 負載較重時(shí)，系統會(huì )從重載 cpu 上"拉"進(jìn)程過(guò)來(lái)，這個(gè)"拉"的負載平衡操作實(shí)現在 load_balance() 函數中。
load_balance() 有兩種調用方式，分別用于當前 cpu 不空閑和空閑兩種狀態(tài)，我們稱(chēng)之為"忙平衡"和"空閑平衡"：
a) 忙平衡
無(wú)論當前 cpu 是否繁忙或空閑，時(shí)鐘中斷（rebalance_tick()函數中）每隔一段時(shí)間（BUSY_REBALANCE_TICK）都會(huì )啟動(dòng)一次 load_balance() 平衡負載，這種平衡稱(chēng)為"忙平衡"。
Linux 2.6 傾向于盡可能不做負載平衡，因此在判斷是否應該"拉"的時(shí)候做了很多限制：
系統最繁忙的 cpu 的負載超過(guò)當前 cpu 負載的 25% 時(shí)才進(jìn)行負載平衡；
當前 cpu 的負載取當前真實(shí)負載和上一次執行負載平衡時(shí)的負載的較大值，平滑負載凹值；
各 cpu 的負載情況取當前真實(shí)負載和上一次執行負載平衡時(shí)的負載的較小值，平滑負載峰值；
對源、目的兩個(gè)就緒隊列加鎖之后，再確認一次源就緒隊列負載沒(méi)有減小，否則取消負載平衡動(dòng)作；
源就緒隊列中以下三類(lèi)進(jìn)程參與負載情況計算，但不做實(shí)際遷移： 正在運行的進(jìn)程
不允許遷移到本 cpu 的進(jìn)程（根據 cpu_allowed 屬性）
進(jìn)程所在 cpu 上一次調度事件發(fā)生的時(shí)間（runqueue::timestamp_last_tick，在時(shí)鐘中斷中取值）與進(jìn)程被切換下來(lái)的時(shí)間（task_struct::timestamp）之差小于某個(gè)閥值（cache_decay_ticks的nanosecond值），--該進(jìn)程還比較活躍，cache 中的信息還不夠涼。
負載的歷史信息 為了避免競爭，調度器將全系統各個(gè) CPU 進(jìn)行負載平衡時(shí)的負載情況（就緒進(jìn)程個(gè)數）保存在本 cpu 就緒隊列的 prev_cpu_load 數組的對應元素中，在計算當前負載時(shí)會(huì )參考這一歷史信息。
找到最繁忙的 cpu（源 cpu）之后，確定需要遷移的進(jìn)程數為源 cpu 負載與本 cpu 負載之差的一半（都經(jīng)過(guò)了上述歷史信息平滑），然后按照從 expired 隊列到 active 隊列、從低優(yōu)先級進(jìn)程到高優(yōu)先級進(jìn)程的順序進(jìn)行遷移。但實(shí)際上真正執行遷移的進(jìn)程往往少于計劃遷移的進(jìn)程，因為上述三類(lèi)"不做實(shí)際遷移"的情況的進(jìn)程不參與遷移。
b) 空閑平衡
空閑狀態(tài)下的負載平衡有兩個(gè)調用時(shí)機：
在調度器中，本 cpu 的就緒隊列為空；
在時(shí)鐘中斷中，本 cpu 的就緒隊列為空，且當前絕對時(shí)間（jiffies 值）是 IDLE_REBALANCE_TICK 的倍數（也就是說(shuō)每隔 IDLE_REBALANCE_TICK 執行一次）。
此時(shí) load_balance() 的動(dòng)作比較簡(jiǎn)單：尋找當前真實(shí)負載最大的 cpu（runqueue::nr_running 最大），將其中"最適合"（見(jiàn)下）的一個(gè)就緒進(jìn)程遷移到當前 cpu 上來(lái)。
"空閑平衡"的候選進(jìn)程的標準和"忙平衡"類(lèi)似，但因為空閑平衡僅"拉"一個(gè)進(jìn)程過(guò)來(lái)，動(dòng)作要小得多，且執行頻率相對較高（IDLE_REBALANCE_TICK 是BUSY_REBALANCE_TICK 的 200 倍），所以沒(méi)有考慮負載的歷史情況和負載差，候選的遷移進(jìn)程也沒(méi)有考慮 Cache 活躍程度。
計算最繁忙 cpu 算法中的問(wèn)題
實(shí)際上有可能成為平衡源的 cpu 的負載至少應該比當前 cpu 的負載要大，因此 find_busiest_queue() 函數中 max_load 的初值如果是 nr_running，且同時(shí)保證 load 最少為 1，那么計算會(huì )稍少一點(diǎn)。
c) pull_task()
"拉"進(jìn)程的具體動(dòng)作在這個(gè)函數中實(shí)現。進(jìn)程從源就緒隊列遷移到目的就緒隊列之后，pull_task() 更新了進(jìn)程的 timestamp 屬性，使其能繼續說(shuō)明進(jìn)程相對于本 cpu 的被切換下來(lái)的時(shí)間。如果被拉來(lái)的進(jìn)程的優(yōu)先級比本 cpu 上正在運行的進(jìn)程優(yōu)先級要高，就置當前進(jìn)程的 NEED_RESCHED 位等待調度。
a) migration_thread()
與"拉"相對應，2.6 的負載平衡系統還有一個(gè)"推"的過(guò)程，執行"推"的主體是一個(gè)名為 migration_thread() 的核心進(jìn)程。該進(jìn)程在系統啟動(dòng)時(shí)自動(dòng)加載（每個(gè) cpu 一個(gè)），并將自己設為 SCHED_FIFO 的實(shí)時(shí)進(jìn)程，然后檢查 runqueue::migration_queue 中是否有請求等待處理，如果沒(méi)有，就在 TASK_INTERRUPTIBLE 中休眠，直至被喚醒后再次檢查。
migration_queue 僅在 set_cpu_allowed() 中添加，當進(jìn)程（比如通過(guò) APM 關(guān)閉某 CPU 時(shí)）調用 set_cpu_allowed() 改變當前可用 cpu，從而使某進(jìn)程不適于繼續在當前 cpu 上運行時(shí)，就會(huì )構造一個(gè)遷移請求數據結構 migration_req_t，將其植入進(jìn)程所在 cpu 就緒隊列的 migration_queue 中，然后喚醒該就緒隊列的遷移 daemon（記錄在 runqueue::migration_thread 屬性中），將該進(jìn)程遷移到合適的cpu上去（參見(jiàn)"新的數據結構 runqueue"）。
在目前的實(shí)現中，目的 cpu 的選擇和負載無(wú)關(guān)，而是"any_online_cpu(req->task->cpus_allowed)"，也就是按 CPU 編號順序的第一個(gè) allowed 的CPU。所以，和 load_balance() 與調度器、負載平衡策略密切相關(guān)不同，migration_thread() 應該說(shuō)僅僅是一個(gè) CPU 綁定以及 CPU 電源管理等功能的一個(gè)接口。
b) move_task_away()
實(shí)際遷移的動(dòng)作在 move_task_away() 函數中實(shí)現，進(jìn)程進(jìn)入目的就緒隊列之后，它的 timestamp 被更新為目的 cpu 就緒隊列的 timestamp_last_tick，說(shuō)明本進(jìn)程是剛開(kāi)始（在目的 cpu 上）等待。因為"推"的操作是在本地讀遠地寫(xiě)（與 pull_task() 正相反），因此，在啟動(dòng)遠地 cpu 的調度時(shí)需要與遠地的操作同步，還可能要通過(guò) IPI（Inter-Processor Interrupt）通知目的 cpu，所有這些操作實(shí)現在 resched_task()函數中。
兩個(gè) runqueue 的鎖同步
在遷移進(jìn)程時(shí)會(huì )牽涉到兩個(gè) cpu 上的就緒隊列，通常在操作之前需要對兩個(gè)就緒隊列都加鎖，為了避免死鎖，內核提供了一套保證加鎖順序的double_rq_lock()/double_rq_unlock() 函數。這套函數并沒(méi)有操作 IRQ，因此開(kāi)關(guān)中斷的動(dòng)作需要用戶(hù)自己做。
這套函數在 move_task_away() 中采用了，而 pull_task() 中使用的是 double_lock_balance()，但原理與 double_rq_lock()/double_rq_unlock() 相同。
在 Linux 調度器看來(lái)，NUMA 與 SMP 之間主要的不同在于 NUMA 下的 cpu 被組織到一個(gè)個(gè)節點(diǎn)中了。不同的體系結構，每個(gè)節點(diǎn)所包含的 cpu 數是不同的，例如 2.6 的 i386 平臺下，NUMAQ 結構每個(gè)節點(diǎn)上可配置 16 個(gè) cpu，SUMMIT 結構可配置 32 個(gè) cpu。 NUMA 結構正式體現在 Linux 內核中是從 2.6 開(kāi)始的，在此之前，Linux 利用已有的"不連續內存"（Discontiguous memory，CONFIG_DISCONTIGMEM）體系結構來(lái)支持 NUMA。除了內存分配上的特殊處理以外，以往的內核在調度系統中是等同于 SMP 看待的。2.6 的調度器除了單個(gè) cpu 的負載，還考慮了 NUMA 下各個(gè)節點(diǎn)的負載情況。
NUMA 結構在新內核中有兩處特殊處理，一處是在做負載平衡時(shí)對各NUMA節點(diǎn)進(jìn)行均衡，另一處是在系統執行新程序（do_execve()）時(shí)從負載最輕的節點(diǎn)中選擇執行cpu：
節點(diǎn)間的平衡作為 rebalance_tick() 函數中的一部分在 load_balance() 之前啟動(dòng)（此時(shí)的 load_balance() 的工作集是節點(diǎn)內的 cpu，也就是說(shuō)，NUMA下不是單純平衡全系統的 cpu 負載，而是先平衡節點(diǎn)間負載，再平衡節點(diǎn)內負載），同樣分為"忙平衡"和"空閑平衡"兩步，執行間隔分別為IDLE_NODE_REBALANCE_TICK（當前實(shí)現中是 IDLE_REBALANCE_TICK 的 5 倍）和 BUSY_NODE_REBALANCE_TICK（實(shí)現為 BUSY_NODE_REBALANCE_TICK 的 2 倍）。
balance_node() 先調用 find_busiest_node() 找到系統中最繁忙的節點(diǎn)，然后在該節點(diǎn)和本 cpu 組成的 cpu 集合中進(jìn)行 load_balance()。尋找最繁忙節點(diǎn)的算法涉及到幾個(gè)數據結構：
node_nr_running[MAX_NUMNODES]，以節點(diǎn)號為索引記錄了每個(gè)節點(diǎn)上的就緒進(jìn)程個(gè)數，也就是那個(gè)節點(diǎn)上的實(shí)時(shí)負載。這個(gè)數組是一個(gè)全局數據結構，需要通過(guò) atomic 系列函數訪(fǎng)問(wèn)。
runqueue::prev_node_load[MAX_NUMNODES]，就緒隊列數據結構中記錄的系統各個(gè)節點(diǎn)上一次負載平衡操作時(shí)的負載情況，它按照以下公式修正：
當前負載=上一次的負載/2 + 10*當前實(shí)時(shí)負載/節點(diǎn)cpu數
采用這種計算方式可以平滑負載峰值，也可以考慮到節點(diǎn)cpu數不一致的情況。
NODE_THRESHOLD，負載的權值，定義為 125，被選中的最繁忙的節點(diǎn)的負載必須超過(guò)當前節點(diǎn)負載的 125/100，也就是負載差超過(guò) 25%。
當 execve() 系統調用加載另一個(gè)程序投入運行時(shí)，核心將在全系統中尋找負載最輕的一個(gè)節點(diǎn)中負載最輕的一個(gè) cpu（sched_best_cpu()），然后調用sched_migrate_task() 將這個(gè)進(jìn)程遷移到選定的 cpu 上去。這一操作通過(guò) do_execve() 調用 sched_balance_exec() 來(lái)實(shí)現。
sched_best_cpu() 的選擇標準如下：
如果當前cpu就緒進(jìn)程個(gè)數不超過(guò)2，則不做遷移；
計算節點(diǎn)負載時(shí)，使用（10*當前實(shí)時(shí)負載/節點(diǎn)cpu數）的算法，不考慮負載的歷史情況；
計算節點(diǎn)內cpu的負載時(shí)，使用就緒進(jìn)程的實(shí)際個(gè)數作為負載指標，不考慮負載的歷史情況。
和"忙平衡"與"空閑平衡"采用不同負載評價(jià)標準一樣，sched_balance_exec() 采用了與 balance_node() 不一樣的（更簡(jiǎn)單的）評價(jià)標準。
sched_migrate_task() 借用了 migration_thread 服務(wù)進(jìn)程來(lái)完成遷移，實(shí)際操作時(shí)將進(jìn)程的 cpu_allowed 暫設為僅能在目的 cpu 上運行，喚醒migration_thread 將進(jìn)程遷移到目的 cpu 之后再恢復 cpu_allowed 屬性。
2.6 內核調度系統有兩點(diǎn)新特性對實(shí)時(shí)應用至關(guān)重要：內核搶占和 O(1) 調度，這兩點(diǎn)都保證實(shí)時(shí)進(jìn)程能在可預計的時(shí)間內得到響應。這種"限時(shí)響應"的特點(diǎn)符合軟實(shí)時(shí)（soft realtime）的要求，離"立即響應"的硬實(shí)時(shí)（hard realtime）還有一定距離。并且，2.6 調度系統仍然沒(méi)有提供除 cpu 以外的其他資源的剝奪運行，因此，它的實(shí)時(shí)性并沒(méi)有得到根本改觀(guān)。
2.4 系統中，實(shí)時(shí)進(jìn)程的優(yōu)先級通過(guò) rt_priority 屬性表示，與非實(shí)時(shí)進(jìn)程不同。2.6 在靜態(tài)優(yōu)先級之外引入了動(dòng)態(tài)優(yōu)先級屬性，并用它同時(shí)表示實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程的優(yōu)先級。
從上面的分析我們看到，進(jìn)程的靜態(tài)優(yōu)先級是計算進(jìn)程初始時(shí)間片的基礎，動(dòng)態(tài)優(yōu)先級則決定了進(jìn)程的實(shí)際調度優(yōu)先順序。無(wú)論是實(shí)時(shí)進(jìn)程還是非實(shí)時(shí)進(jìn)程，靜態(tài)優(yōu)先級都通過(guò) set_user_nice() 來(lái)設置和改變，缺省值都是 120（MAX_PRIO-20），也就是說(shuō)，實(shí)時(shí)進(jìn)程的時(shí)間片和非實(shí)時(shí)進(jìn)程在一個(gè)量程內。
可區分實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程的地方有兩處：調度策略 policy（SCHED_RR或SCHED_FIFO）和動(dòng)態(tài)優(yōu)先級 prio（小于 MAX_USER_RT_PRIO），實(shí)際使用上后者作為檢驗標準。實(shí)時(shí)進(jìn)程的動(dòng)態(tài)優(yōu)先級在 setscheduler() 中設置（相當于 rt_priority），并且不隨進(jìn)程的運行而改變，所以實(shí)時(shí)進(jìn)程總是嚴格按照設置的優(yōu)先級進(jìn)行排序，這一點(diǎn)和非實(shí)時(shí)進(jìn)程動(dòng)態(tài)優(yōu)先級含義不同?？梢哉J為，實(shí)時(shí)進(jìn)程的靜態(tài)優(yōu)先級僅用于計算時(shí)間片，而動(dòng)態(tài)優(yōu)先級則相當于靜態(tài)優(yōu)先級。
2.4中SCHED_RR和SCHED_FIFO兩種實(shí)時(shí)調度策略在2.6中未作改變，兩類(lèi)實(shí)時(shí)進(jìn)程都會(huì )保持在active就緒隊列中運行，只是因為2.6內核是可搶占的，實(shí)時(shí)進(jìn)程（特別是核心級的實(shí)時(shí)進(jìn)程）能更迅速地對環(huán)境的變化（比如出現更高優(yōu)先級進(jìn)程）做出反應。
近年來(lái)，Linux 對于桌面系統、低端服務(wù)器、高端服務(wù)器以及嵌入式系統都表現出越來(lái)越強的興趣和競爭力，對于一個(gè)仍然處于"集市式"開(kāi)放開(kāi)發(fā)模式的操作系統來(lái)說(shuō)，能做到這一點(diǎn)簡(jiǎn)直就是一個(gè)奇跡。
但從調度系統的實(shí)現上我感覺(jué)，Linux 的長(cháng)項仍然在桌面系統上，它仍然保持著(zhù)早年開(kāi)發(fā)時(shí)"利己主義"的特點(diǎn)，即自由軟件的開(kāi)發(fā)者的開(kāi)發(fā)動(dòng)力，很大程度上來(lái)自于改變現有系統對自己"不好用"的現狀。盡管出于種種動(dòng)機和動(dòng)力，Linux 表現出與 Windows 等商用操作系統競爭的強勢，但從開(kāi)發(fā)者角度來(lái)看，這種愿望與自由軟件的開(kāi)發(fā)特點(diǎn)是有矛盾的。
Ingo Monar 在接受采訪(fǎng)時(shí)說(shuō)，他設計的 O(1) 調度算法，基本上來(lái)自于個(gè)人的創(chuàng )意，沒(méi)有參考市面上以及研究領(lǐng)域中已有的調度算法。從調度器設計上可以看出，2.6 調度系統考慮了很多細節，但總體上并沒(méi)有清晰的主線(xiàn)，且無(wú)法（或者也無(wú)意于）在理論上對 O(1) 模型進(jìn)行性能分析。從 2.6 的開(kāi)發(fā)過(guò)程中我們也能看到，各種調度相關(guān)的權值在不同的版本中一直在微調，可以認為，2.6 調度系統的性能優(yōu)化主要是實(shí)測得來(lái)的。
這就是典型的 Linux 開(kāi)發(fā)模式--充滿(mǎn)激情、缺乏規劃。
對于 Linux 的市場(chǎng)來(lái)說(shuō)，最緊迫、最活躍的需要在于嵌入式系統，但至少從調度系統來(lái)看，2.6 并沒(méi)有在這方面下很大功夫，也許開(kāi)發(fā)者本人對此并無(wú)多大感受和興趣?？梢钥隙?，雖然 Linux 在市場(chǎng)上很火，但它的開(kāi)發(fā)仍然不是市場(chǎng)驅動(dòng)的。這或許會(huì )影響 Linux 的競爭力，但或許也因此能保持 Linux 開(kāi)發(fā)的活力。
就在今年（2004年）3月1日，著(zhù)名的開(kāi)源網(wǎng)絡(luò )安全項目 FreeS/WAN 宣布停止開(kāi)發(fā)，其原因主要是開(kāi)發(fā)者的意圖和用戶(hù)的需求不吻合。對于網(wǎng)絡(luò )安全系統，用戶(hù)更多考慮的是系統功能的完整、強大，而不是它可預知的先進(jìn)性，因此，FreeS/WAN 新版本中主打推出的 Opportunistic Encryption (OE) 沒(méi)有吸引到足夠數量的用戶(hù)測試。鑒于此，投資者停止了對 FreeS/WAN 項目的資助，這一為開(kāi)源系統提供了強大的網(wǎng)絡(luò )安全支持的系統也許會(huì )再次轉入地下。
至今為止，還沒(méi)有聽(tīng)到 Linux 的開(kāi)發(fā)依賴(lài)于某種商業(yè)基金的報道，因此相對而言，Linux 的開(kāi)發(fā)更具自由和隨意性，推廣 Linux 的人與開(kāi)發(fā) Linux 的人基本上獨立運作著(zhù)，Linux 的受益者和 Linux 的開(kāi)發(fā)者也沒(méi)有緊密結合。這對于 Linux 或許是福而不是禍。
[1][Linus Torvalds，2004] Linux 內核源碼 v2.6.2，www.kernel.org
[2][pubb@163.net，2004]
Linux 2.4調度系統分析 ，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內核技術(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
關(guān)于作者
楊沙洲，目前在國防科技大學(xué)計算機學(xué)院攻讀軟件方向博士學(xué)位。對文中存在的技術(shù)問(wèn)題，歡迎向
pubb@163.net質(zhì)疑，謝謝。
