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