948
kernel 2.6 調度算法
Linux Kernel 2.6進程調度的分析(揭示了幾乎所有2.6調度的東西)第一章 Kernel 2.4存在的不 足
根據對2.4進程調度的分析，我們總結出看出2.4內核總的特點就是：
內核調度簡單有效
內核不可搶占
但是經過對2.4內核的分析，我們也明顯看到了它的缺點：
1.調度算法複雜度是O(n)，與係統負荷關係較大。而且調度算法在設計上也有缺陷
，比如：
(1) 2.4進程調度隻設置了一個進程就緒隊列，這樣有的進程用完了自己時間片以後還要呆在就緒進程隊列裏麵。這樣這個進程雖然在這一輪調度循環裏麵已經無法取得CPU的使用權，但是還要參與goodness()值的計算，這樣就白白浪費了時間。
(2) 就緒進程隊列是一個全局數據結構，多個CPU隻有一個就緒隊列runqueue，因而調度器對它的所有操作都會因全局自旋鎖而導致係統各個處理機之間的等待，使得就緒隊列成為一個明顯的瓶頸。
2.調度算法在內核態不可搶占。如果某個進程一旦進了內核態那麼再高優先級的進程都無法剝奪，隻有等進程返回內核態的時候才可以進行調度。缺乏對實時進程的支持。
第二章Kernel 2.6進程調度分析
一、基本思想
Kernel2.6調度算法仍然是基於優先級的調度，它的算法複雜度為O(1)，也就是說是調度器的開銷是恒定的，與係統當前的負載沒有關係。
1. 就緒隊列的改進
每個CPU有兩個按優先級排序的數組：一個是active array；一個是expired array。
Active array是當前CPU可能選擇執行的運行進程隊列，隊列中的每個進程都有時間片剩下。Expired array是那些用戶時間片的就緒進程隊列。一旦active array裏麵
某個普通進程的時間片用完了，調度器將重新計算進程的時間片、優先級，將它從active array中刪除，插入到expired array中相應得優先級隊列中。Active array和expired array是通過兩個指向每個CPU運行隊列的指針來訪問的。所以當active array中所有的進程都用完時間片，隻需將兩個指針切換一下就可以了，這比Kernel 2.4的切換要改進了很多。
2. 快速查找應該執行的進程
係統中往往有很多的就緒進程，如何快速找到CPU即將運行的進程就成了關係到係統性能的一個重要因素。針對2.4的缺點，Kernel 2.6進行了重新設計：引進了一個64bit的bitmap作為進程隊列的索引，用bitmap來記載某個優先級的進程隊列上有無進程，如果有則為1。這 樣使得尋找優先級最高的任務隻需要兩個BSFL命令。
3. 引進"load estimator"
在一個負載很重的係統上有一個很好的交互感是一件很困難的事情，設計者經過研究發現一味的激勵（boost）交互任務並不夠，還需懲罰（punish）那 些需求大於可獲得CPU時間的進程。調度器通過對用戶睡眠時間和運行時間的紀錄來判斷進程是否是交互進程，一旦被認為是交互進程，調度器會給進程很多"獎 勵"（bonus）。
4. 內核可搶占
內核可搶占可以說是2.6內核調度器優於2.4內核的一個很重要的原因。當內核進程沒有訪問內核的關鍵數據，也就是內核沒有被加鎖，此時內核代碼是可重入的，因此更高優先級的進程可以在此時中斷正在執行的進程，從而達到搶占的目的。
5. 調度器相關的負載均衡
負載均衡有兩種策略，一種是從別的CPU上將進程遷移過來，稱為"pull"；一種是將本CPU上的進程遷移出去，稱為"push"。
二、數據結構
1. 進程優先級的劃分
Kernel 2.6將進程優先級作了以下規定：進程優先級範圍是從0 ~ MAX_PRIO-1，其中實時進程的優先級的範圍是0 ~ MAX_RT_PRIO-1，普通進程的優先級是MAX_RT_PRIO ~ MAX_PRIO-1。數值越小優先級越高。
2. 就緒隊列runqueue（kernel/sched.c）
struct runqueue是2.6調度器中一個非常重要的數據結構，它主要用於存放每個CPU的就緒隊列信息。限於篇幅，這裏隻介紹其中相對重要的部分：
(1) prio_array_t *active, *expired, arrays[2]
這是runqueue中最重要的部分。每個CPU的就緒隊列都是一個數組，按照時間片是否用完將就緒隊列分為兩個部分，分別用指針active和expired來指向數組的兩個下標。prio_array_t的結構如下：
struct prio_array {
int nr_active; /*本進程組中進程個數*/
struct list_head queue[MAX_PRIO]; /*每個優先級的進程隊列*/
unsigned long bitmap[BITMAP_SIZE]; /*上述進程隊列的索引位圖*/
};
數組queue[MAX_PRIO]裏麵存放的是優先級為i（MAX_PRIO>i>=0）的進程隊列的鏈表頭，即task_struct::runlist（通過runnlist即可找到task_struct）。
那麼調度器在執行調度的任務時是怎麼找到優先級最高的進程呢？
在結構體struct prio_array中有一個重要的數據unsigned long bitmap[BITMAP_SIZE]，這個數據是用來作為進程隊列queue[MAX_PRIO]的索引位圖，bitmap的每一位（bit
）都與queue[i]對應。當queue[i]的進程隊列不為空時，bitmap的相應位就為1；否則就為0。這樣我們隻需要通過匯編指令從進程優先級 由高到低的方向找到第一個為1的位置idx即為當前就緒隊列中最高的優先級（函數sched_find_first_bit()就是用來完成這一工作 的），那麼queue[i]->next就是我們要找的task_struct::runlist。
當一個普通進程的時間片用完以後將重新計算進程的時間片和優先級，將該進程從active array中刪除，添加到expired array中相應優先級的進程隊列中。當Active array中沒有進程時，則將active和expired指針調換一下就完成了切換工作。而在2.4內核中重新計算時間片是在所有就緒進程的時間片都用 完以後才統一進行的，因而進程時間片的計算非常耗時，而在2.6中計算時間片是分散的，而且通過以上的方法來實現時間片的輪轉，這也是2.6調度器一個亮 點。
另外，程序將struct runqueue定義在sched.c裏麵而沒有定義在sched.h裏麵是為了讓抽象調度器部分的代碼，使得內核的其他部分使用調度器提供的接口即可。
(2) spinlock_t lock
runqueue的自旋鎖，當對runqueue進行操作的時候，需要對其加鎖。由於每個CPU都有一個runqueue，這樣會大大減少競爭的機會。
(3) task_t *curr
CPU當前運行的進程。在程序中還有一個全局變量current也是CPU當前運行的進程，它在通常情況下和runqueue的curr指針是相同的，但 是當調度器進行調度的時，如果已經找到最高優先級的進程，則此時做rq->curr = next;可見在進行任務切換之前，rq->curr和current的值是不同的。當喚醒一個進程的時候，很明顯將喚醒進程與 rq->curr的優先級進行比較更有意義。
(4) unsigned long expired_timestamp
此變量是用來記錄active array中最早用完時間片的時間（賦值jiffies）。因此，用這個量就可以記錄expired array中等時間最長的進程的等待時間。這個值的主要
用處是用於宏EXPIRED_STARVING()（這個宏主要是用來判斷expired array中的進程是否已經等待了足夠長的時間，詳見"進程調度的生與死"一節中"scheduler_tick()"函數的介紹）。
(5) unsigned long nr_running, nr_switches, nr_uninterruptible,timestamp_last_tick
用來記錄該CPU進程相關數據。具體作用如下
nr_running
記錄該CPU上就緒進程總數，是active array和expired array進程總數和
nr_switches
記錄該CPU運行以來發生的進程切換次數
nr_uninterruptible
記錄該CPU不可中斷狀態進程的個數
timestamp_last_tick
記錄就緒進程隊列上次發生調度的時間，用於負載均衡
(6) struct list_head migration_queue
這個是存放希望遷移到其他CPU上的進程隊列，實際遷移的數據類型是migration_req_t，這裏是通過將migration_req_t::list連接起來。詳見"負載均衡"中"push"一節。
3. 進程標識task_struct(include/linux/sched.h)
Linux是一個多任務的操作係統，在多任務操作係統中每一個進程都由一個PCB程序控製塊來標識在Linux中PCB實際上是一個名為 task_struct的結構體。task_struct有上百個域，主要包括了10個方麵的信息：1.進程狀態；2.調度信息，如調度策略，優先級，時 間片，交互值等；3.進程的通訊狀況；4.進程樹中的父子兄
弟的指針；5.時間信息，如睡眠時間，上一次發生調度時間等；6.標號，決定該進程歸屬；7.打開的一些文件信息；8.進程上下文和內核上下文；9.處理器上下文；10.內存信息。
由於task_struct結構體比較複雜，因此我們隻注意它與進程調度相關的重要部分。
(1) volatile long state
進程所處的狀態。在include/linux/sched.h中包含6種狀態：
#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是表示已經退出且不需父進程回收的進程的狀態。
(2) struct thread_info *thread_info
當前進程運行的一些環境信息。其中有兩個結構成員非常重要，與調度密切相關：
__s32 preempt_count;
unsigned long flags;
preempt_count是用來表示內核能否被搶占的使能成員。如果它大於0，表示內核不能被搶占；如果等於0，則表示內核處於安全狀態（即沒有加 鎖），可以搶占。flags裏麵有一個TIF_NEED_RESCHED位，它和Kernel 2.4中need_resched作用一樣。如果此標誌位為1，則表示應該盡快啟動調度器。
(3) int prio, static_prio
prio是進程的動態優先級，相當於Kernel2.4中用goodness()函數計算出來的結果；在Kernel2.6 中不再是由調度器統一計算，而是獨立計算；prio的計算和許多因素有關，詳見"進程優先級的計算"一節。static_prio則是進程的靜態優先級， 與nice意義相同。nice的取值仍然是-20 ~ 19，數值越小，進程優先級越高。kernel/sched.c中定義了兩個宏來完成將nice轉換到prio的取值區間和將prioity轉換到 nice取值區間。
#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
可見prioity和nice的關係是：
priority = MAX_RT_PRIO+nice+20
(4) struct list_head run_list
前麵提到過，就緒進程都是按照優先級進行排列，prio_array中的queue[MAX_PRIO]存放的是指向每個優先級隊列的鏈頭list_head；而同一優先級的進程則是通過run_list鏈接在一起。
include/linux/list.h定義了一種抽象的雙向鏈表struct list_head，通過它可以將任意類型的結構體鏈接到一起。task_struct也是通過這種方式鏈接起來的。
(5) prio_array_t *array
指向當前CPU的active array的指針。在進程控製塊裏麵又加了一個指向active array的指針，看似重複，其實不然。比如說對於下麵的代碼（kernel/sched.c）：
array = next->array;
dequeue_task(next, array);
recalc_task_prio(next, next->timestamp + delta);
enqueue_task(next, array);
對於單處理器（UP）的情況，我們確實可以通過runqueue::active直接得到當前的active array；但是對於SMP，就不是這樣了，需要引用next的thread_info，再依靠thread_info中的cpu找到next所在的處理 器，找到以後再找到這個cpu上的runqueue，最後得到active。對於schedule這樣頻繁調用的函數，這種浪費是不能容忍的。
(6) unsigned long sleep_avg
進程的平均等待時間，單位是納秒（nanosecond），在0 ~ NS_MAX_SLEEP_AVG範圍內。它的實質是進程等待時間和運行時間的差值。當進程處於等待或者睡眠狀態時，該
值變大；當進程運行時，該值變小。sleep_avg是Kernel 2.6中衡量進程的一個關鍵指標，它既可以用來衡量進程的交互程度，也可以用來衡量進程的緊急程度。具體內容將在"平均等待時間sleep_avg"一節作詳細介紹。
(7) long interactive_credit
表示進程交互程度，取值範圍在-CREDIT_LIMIT ~ CREDIT_LIMIT+1之間。進程創建的時候值為1，以後根據不同的情況進行不同的增1、減1；如果一個進程的 interactive_credit超過CREDIT_LIMIT之後，這個進程就會被認為是交互式進程，同時interactive_credit的 值也就不再改變了（恒為CREDIT_LIMIT+1）。下麵將在"交互進程優化"一節詳細介紹。
(8) unsigned long long timestamp
進程發生調度的時間，單位和sleep_avg一樣，也是納秒。它負責紀錄以下四種情況的時間：
a. 進程被喚醒的時間：
在activate_task()（kernel/sched.c）中記錄（p->timestamp = now）。
b. 進程被切換到expired array的時間：
在schedule()（kernel/sched.c）中記錄，當準備進行進程切換的時候，記錄下該進程被切換到expired array的時間（prev->timestamp = now）。
c. 進程被切換到active array的時間：
在schedule()（kernel/sched.c）中記錄，進行進程切換的開始，記錄下下一個進程被切換到active array的時間（next->timestamp = now）。
d. 負載均衡相關的賦值
在進行負載均衡的時候，當把一個進程從其他CPU上pull過來的時候需要將該進程的timestamp設成sched_clock() - (src_rq->timestamp_last_tick - p->timestamp)，即相對於本CPU被切換下來的時間。
(9) int activated
表示該進程被喚醒的類別：
actived=-1 表示該進程並非自願sleep，其先前狀態是TASK_UNINTERRUPTIBLE。在try_to_wake_up()中設置。
actived=0 缺省值，表示進程本來就是處於就緒狀態。
actived=1 進程先前狀態是TASK_INTERRUPTIBLE，但是不是由中斷喚醒；這樣的進程在第一次運行時有credit，以後就沒有了。在activate_task()中設置。
actived=2 進程先前狀態是TASK_INTERRUPTIBLE，進程被中斷喚醒。這樣的進程非常像交互式進程。在activate_task()中設置。
(10) unsigned long policy
進程的調度策略和2.4一樣，有以下幾種：
SCHED_FIFO 先進先出式調度，除非有更高優先級進程申請運行，否則該進程將保持運行至退出才讓出CPU
SCHED_RR 輪轉式調度，該進程被調度下來後將被置於運行隊列的末尾，以保證其他實時進程有機會運行）
SCHED_OTHER 常規的分時調度策略
(11) unsigned int time_slice, first_time_slice
ime_slice是進程剩餘的時間片，相當於Kernel 2.4裏麵counter，但是時間片不再影響進程的優先級。first_time_slice用來記錄時間片是否是第一次分配（進程創建時），如果值不為0，進程退出時將時間片交還給父進程。
三、調度策略
1. 進程優先級
(1) 優先級的計算
前麵已經說過，優先級由兩部分構成，一是靜態優先級static_prio，一是動態優先級prio。靜態優先級在進程創建的時候就被賦值，並且不變（除非用係統調用改變進
程的nice值）；而進程的動態優先級則是跟static_prio和sleep_avg有關。對於實時進程的優先級在創建的時候就確定了，而且一旦確定以後就不再改變，所以下麵部分
僅對於非實時進程而言。具體的計算由函數effecitve_prio()（kernel/sched.c）完成。
函數將進程的sleep_avg映射成範圍是-MAX_BONUS/2 ~ MAX_BONUS/2的變量bonus，而MAX_BONUS是等於 ，可見sleep_avg僅能影響的優先級範圍在-5 ~ 5之間。具體的映射是由以下規則完成的：
那麼進程的動態優先級就等於： （當然必須在MAX_RT_PRIO和MAX_PRIO-1之間）。可見，sleep_avg和bonus是一個線性關係。進程的sleep_avg越大，bonus越大，從而進程的動態優先級也就越高。
(2) 何時計算優先級
計算進程的動態優先級一般調用兩個函數，一個是effective_prio()，一個是recalc_task_prio()。函數 recalc_task_prio ()先要根據進程被喚醒前的狀態（即actived）、interactive_credit等來計算進程的sleep_avg（詳見"平均等待時間 sleep_avg"一節），在最後調用effective_prio()來計算函數的動態優先級。總的來說，有以下幾種情況需要計算進程的優先級：
a. 創建新進程，使用函數effective_prio()（因為此時進程尚未進行調度，沒有sleep_avg和interactive_credit可言）；
b. 喚醒等待進程時，使用函數recalc_task_prio ()來計算進程動態優先級。
c. 進程用完時間片以後，被重新插入到active array或者expired array的時候需要重新計算動態優先級，以便將進程插入到隊列的相應位置。此時，使用函數effective_prio()；
d. 其他情況，如IDLE進程初始化等時候。
2. 進程時間片
(1) 時間片的計算
進程的時間片time_slice是基於進程靜態優先級的，靜態優先級越高（值越小），時間片就越大。計算時間片是同過函數task_timeslice()（kernel/sched.c）來完成的
。該函數也是使用線性映射的方法，將進程優先級[MAX_RT_PRIO, MAX_PRIO-1]映射到時間片[MIN_TIMESLICE, MAX_TIMESLICE]範圍內。通過優先級來計算時間片的等式為：
timeslice = MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) *(MAX_PRIO-1- (p)->static_prio) / (MAX_USER_PRIO-1))
(2) 何時計算時間片
當就緒進程的所有進程的時間片都是0的時候，許多操作係統（包括舊版本的Linux）是使用下麵的循環來給進程隊列計算時間片的：
for (each task on the system) {
recalculate priority;
recalculate timeslice
}
這樣的循環計算會導致以下問題：
循環可能會花很長時間，而且算法的複雜度O(n)；
計算過程中必須給進程隊列和task_struct上鎖，這樣可能導致大量的競爭；
因為計算時間不可預計，所以可能給實時進程帶來問題；
在Kernel 2.6中時間片的計算是分散的，具體的計算既可以用task_timeslice()，也可以用其他方法。
a. 進程創建時，將父進程的時間片分一半給子進程，同時父進程的時間片減半。（詳見"sched_fork"一節）；
b. 進程用完時間片以後，需要重新計算時間片，並將進程插入到相應的運行隊列。（詳見"scheduler_tick"一節）；
c. 進程退出時，根據first_timeslice的值來決定是否將子進程的時間片返還給父進程。（詳見"退出調度"一節）。
可見Kernel2.6通過分散計算時間片的辦法很好解決了上麵循環計算所帶來的幾個問題。
3. 平均等待時間sleep_avg
平均等待時間sleep_avg既決定了進程優先級，又影響了進程交互程度的，因此它是Kernel 2.6調度係統裏麵很複雜的一塊。下麵將跟蹤調度器中sleep_avg的變化情況。
(1) 進程創建
當一個進程被創建的時候，父進程的sleep_avg要乘以"PARENT_PENALTY / 100"，子進程的sleep_avg要乘以"CHILD_PENALTY / 100"，PARENT_PENALTY=100，而
CHILD_PENALTY = 95，可見創建以後子進程的sleep_avg要降低，而父進程則不變。
(2) 進程被喚醒
當一個進程被喚醒以後，acitvate_task()將調用函數recalc_task_prio()來計算進程的sleep_avg，參數是進程的睡 眠時間，從而進一步計算進程的動態優先級。計算sleep_avg有以下幾種可能（當然都需在0 ~ NS_MAX_SLEEP_AVG範圍內）：
a. MAX_SLEEP_AVG - AVG_TIMESLICE
當用戶進程（p->mm）不是由UNINTERRUPTIBLE狀態喚醒（p->activated != -1），且睡眠時間大於INTERACTIVE_SLEEP(p)，則做此賦值；
b. 不變
當用戶進程（p->mm）是由UNINTERRUPTIBLE狀態喚醒（p->activated == -1），且"交互程度"不高（!HIGH_CREDIT(p)），如果原來的sleep_avg已經大於INTERACTIVE_SLEEP(p)，則不 變（對非自願睡眠的進程進行懲罰）； 否則見下麵一條；
c. INTERACTIVE_SLEEP(p)
如果加上此次的睡眠時間後大於INTERACTIVE_SLEEP(p)，則sleep_avg賦值為INTERACTIVE_SLEEP(p)；
d. sleep_avg+sleep_time
如果以上條件全都不滿足，則直接將本次睡眠時間加到sleep_avg上。
(3) 進程調度過程中
在schedule()過程中，如果發現優先級最高的程序是剛剛從TASK_INTERRUPTIBLE狀態被喚醒的進程（actived>0，參 見"actived"的定義），那麼將調用recalc_task_prio()，運算過程與(2)相同，所不同的就是調用時的參數sleep_time 是進程在就緒隊列的等待時間。如果進程不是被中斷喚醒的（actived=1），那麼sleep_time還將受到" (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128"的限製，因為該進程很可能不是交互式進程。
(4) 進程被剝奪CPU使用權
當進行進程切換的時候，被剝奪CPU使用權的進程的sleep_avg將會被減去進程的運行時間run_time（這裏的run_time對於交互式進程也有獎勵的，詳見"交互式進程優先
"一節），從而保證調度器的公平性。進程運行的時間越長，sleep_avg就越小（底限是0），進程的動態優先級也就越低，從而被調度器調度到的機會也就會越小。
(5) 進程退出
當一個進程退出時，如果該進程的sleep_avg比父進程要小（也就是運行時間長），那麼父進程將得到懲罰。具體懲罰的規則為：
p->parent->sleep_avg = p->parent->sleep_avg / (EXIT_WEIGHT+1) * EXIT_WEIGHT + p->sleep_avg / (EXIT_WEIGHT + 1);
父進程的sleep_avg將變為原來的1/( EXIT_WEIGHT+1)，再加上子進程的sleep_avg的1/( EXIT_WEIGHT+1)，可見子進程運行的越多，父進程得到的懲罰也就越大。這樣也是為了保證調度器的公正性。
4. 交互進程優化
Kernel 2.6為了增加係統在高負載情況下的交互感受，做了以下三點優化。
(1) interactive_credit -- 獎勵sleep_avg
interactive_credit是設置在task_struct裏麵用來標記進程的"交互程度"的，它在進程創建時候被置為0，以後隨著不同的情況 而增加，減少。增加interactive_credit有兩處增1的地方，都在函數recalc_task_prio()裏麵。
a. 進程所擁有的內存區域不為空(p->mm!=NULL)，即進程不是內核進程，如果不是從 TASK_UNINTERRUPTIBLE狀態中被喚醒的（p->activated!=-1），且等待的時間（包括在休眠中等待時間和在就緒隊列 中等待時間）超過了一定限度（sleep_time>INTERACTIVE_SLEEP(p)）；此時將interactive_credit增 1；
b. 進程的等待時間大於NS_MAX_SLEEP_AVG了，這種進程很可能是交互進程，所以interactive_credit增1。減少 interactive_credit隻有一處地方減1，在函數schedule()裏麵。當進程將要被切換出CPU的時候，要計算進程的運行時間 run_time，並將進程的sleep_avg進行調整，如果調整後的sleep_avg小於0（說明進程的運行時間大於等待時間），而且該進程的 interactive_credit在HIGH_CREDIT(p)和LOW_CREDIT(p)之間（說明該進程非交互進程），則將 interactive_credit減1作為對進程的懲罰。從上麵的分析可以看出，無論interactive_credit如何增減，它都在 -(CREDIT_LIMIT+1) ~ (CREDIT_LIMIT+1)範圍內；而且當interactive_credit增大到CREDIT_LIMIT+1，即調度器認定該進程為交互進 程以後，interactive_credit就不再變化。調度器采用宏HIGH_CREDIT()來判斷一個進程是否是交互進程，如果是，則該進程將得 到以下獎勵：
a. 當進程被剝奪CPU使用權時，如果發現該進程是交互進程，則將該進程的運行時間減小，run_time /= (CURRENT_BONUS(prev) ? : 1)。即sleep_avg減去的運行時間比實際的運行時間要小，從而增加進程的sleep_avg。
b. 交互式進程在就緒隊列上等待的時間也將增加到sleep_avg裏麵，p->sleep_avg+= sleep_time；從而增加進程的sleep_avg。
可見，對於交互進程都是獎勵sleep_avg的，從而達到提高優先級的目的。對於交互式進程，調度器並沒有在時間片上進行獎勵，而是在優先級上進行獎 勵，是因為交互式進程通常是運行時間短、睡眠時間長，而且要求響應快，而獎勵優先級可以給交互進程更多的運行機會，因此，調度器對於交互進程的獎勵辦法是 非常公平和科學的。
(2) 平均等待時間sleep_avg -- 獎勵動態優先級
在"平均等待時間"一節已做詳細介紹。對於交互進程來說，因為它睡眠的時間較長，所以sleep_avg要大一些。另外，經常處於TASK_INTERRUPTIBLE狀態，而且是被中斷喚醒的進程最有可能是交互進程，而這種進程的衡量因素也是sleep_avg。
總之，由於交互進程一般sleep_avg較大，所以調度器通過獎勵動態優先級的方式來使得進程獲得更多執行的機會。
(3) TASK_INTERACTIVE() -- 獎勵再次被插入active array
這個宏是根據進程的動態優先級和靜態優先級來判斷該進程的"交互程度"。在進程時間片用完時，使用這個宏作為一個參考因素來決定是否將進程重新插入active array。它的定義是：
(p)->prio <= (p)->static_prio - DELTA(p)
DELTA(p) = (SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA)
SCALE(v1,v1_max,v2_max) = (v1) * (v2_max) / (v1_max)
可以看出這個宏是將進程的動態優先級和進程的靜態優先級做比較，以判斷nice值為n（靜態優先級）時，進程p需要多大的動態優先級才能具有"足夠的交互 性"。從宏的定義可以看出當進程的nice值大於12時，進程是不可能被認為是具有足夠的交互性（因為nice>12 時，DELTA(p)>5，而由於sleep_avg給進程帶來的動態優先級上的獎勵最大隻有5，所以TASK_INTERACTIVE(p)永 假）；當進程的nice值為-20時，進程的sleep_avg必須非常小才可能使得TASK_INTERACTIVE(p)值為假。
從以上分析可以看出，這三種獎勵辦法一個比一個獎勵力度大，獎勵條件也一個比一個苛刻。而且調度器將用戶的意願放在了第一位（因為nice值是可以通過係 統調用改變的），由於用戶的意願而給予的獎勵（再次被插入active array）最大，而調度器所給予的獎勵占的比例並不大。
4. 調度器主函數schedule()（kernel/sched.c）
schedule()是用來挑選出下一個應該執行的進程，並且完成進程切換的工作，是進程調度的主要執行者，也是操作係統Kernel很重要的一個函數，它的性能將直接決定操作係統的性能。
(1) 函數主要流程
兩個重要數據：prev和next
prev 當前進程，也就是即將被切換出CPU的進程
next 下一個進程，也就是即將被切換進CPU的進程
準備工作
a. 做原子操作方麵的檢查（主要是檢查內核搶占和內核鎖的深度是否一致）；
b. 關閉內核搶占（通過函數preempt_disable()，詳見"內核可搶占"一節），因為此時將要對內核一係列重要數據進行操作，所以必須將內核搶占關閉；
c. 將當前進程current賦值給prev，獲取當前CPU的運行隊列rq，釋放prev的內核鎖（因為即將對prev做一係列操作），計算prev的運行 時間（如果是交互進程則給予run_time上的獎勵，詳見"interactive_credit"一節），給rq上自旋鎖（防止其他進程訪問rq）；
d. 進行內核的數據統計（如上下文切換次數等），如果prev處於可中斷狀態，而且有信號等待處理，則將prev狀態置為TASK_RUNNING，否則將 prev從rq中刪除。（這一部分的代碼主要是因為在進程在轉入睡眠狀態時，需要主動調用schedule()函數）；
e. 如果rq中就緒進程個數為0，而且係統是SMP，則進行負載均衡的操作（詳見"負載均衡"一節），否則將next置為idle進程，賦值 rq->expired_timestamp = 0（具體含義參見"expired_timestamp"的介紹一節），然後直接進行進程切換。
尋找最高優先級進程
a. 如果rq的active array中進程個數為0，則將active array和expired array進行切換。具體的過程由以下代碼完成：
array = rq->active;
rq->active = rq->expired;
rq->expired = array;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
b. 用函數sched_find_first_bit()找到優先級最高的進程隊列的偏移量idx，那麼queue[idx]->next即為所找的next，可以通過以下三行代碼快速完成：
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
c. 如果next是從TASK_INTERRUPTIBLE狀態中被喚醒的（actived>0），則將進程從就緒隊列中刪除，將進程在就緒隊列上的等 待時間也加在等待時間裏麵重新計算進程的prio（詳見"平均等待時間"一節），再根據新的優先級將進程插入相應就緒隊列。
進程切換
a. 如果prev!=next，則進行進程切換；
b. 進行進程切換前的準備：將當前時間賦給next->timestamp，並且將rq->curr=next；可見此時的rq->curr與current不再相同；
c. 進程切換，包括內存、堆棧切換等。具體過程和Kernel 2.4大致相同，在這裏不再贅述；
完成進程切換後
完成進程切換過後，還需要進行釋放prev的mm，給rq解鎖，重新給current獲得內核鎖（注意在此時current=next=rq-> curr），使能內核搶占；最後檢查TIF_NEED_RESCHED位，如果已被置位，則重新開始進行調度，重複上述過程；否則調度結束。
(2) 函數執行時機
schedule()函數何時被調用，如何被調用也是一個非常重要的問題。在Kernel 2.4裏麵，schedule()函數可以通過兩種方式調用：
一種是主動調度，直接調用函數schedule()，如進程退出，或者進入睡眠狀態等。
一種是強製性調度，置位當前進程task_struct裏麵的need_resched。當是從內核態返回用戶態的時候將檢查這個位，如果發現已經被置位，會調用schedule()；有以下
三種情況可能會置位need_resched：
a. 時鍾中斷服務程序中，發現進程已經用完自己的時間片，需要被切出CPU；
b. 當喚醒一個睡眠進程時，發現該進程比當前占有CPU的進程更有運行資格；
c. 一個進程通過係統調用改變調度政策、nice值等。
和主動調度相比，強製性調度有一定的調度延時。Kernel2.6的調度時機包含了Kernel 2.4的調度時機（不同的就是need_resched變成了一個bit）同時加入了一個重要的特性--內核可搶占，具體的分析見"內核可搶占"一節。
5. 進程調度的生與死
這一部分分析了係統調度器開始工作的時機，以及一個進程從創建到滅亡過程中和進程調度相關的信息和函數。
(1) 係統啟動時進程調度的初始化 -- sched_init()
係統進程調度的初始化由sched_init()函數完成，它被init/main.c中函數start_kernel()調用，該函數主要完成以下工作：
a. 對於所有的CPU，完成runqueue的初始化工作；
b. 對於SMP，要獲取第一個進程的CPU號；
c. 調用wake_up_forked_process()（參見下麵"wake_up_forked_process"一節）來喚醒當前進程；
d. 初始化timer
(2) 創建新進程時的調度信息改變 -- sched_fork(task_t *p)當當前進程fork出一個新進程的時候，需要改變新進程的調度信息，該函數主要的調用關係是：kenel/fork.c - do_fork()->copy_process->sched_fork()，函數主要完成：
a. 將進程狀態置為TASK_RUNNIG，但並未將它加入runqueue，主要是為了保證沒有其他人運行該程序，並且信號或者其他外部事件都不能將它喚醒；
b. 初始化進程的runlist、array、自旋鎖（開子進程的自旋鎖，直到fork結束，返回用戶態時調用函數sched_tail來解鎖），preempt_count賦1；
c. 將子進程的first_timeslice置1，標誌這是子進程第一次分配到時間片；
d. 將父進程時間片的一半賦給子進程，同時父進程的時間片減半（這樣是為了防止一個進程通過不停的fork出子進程來占有CPU）；如果父進程的時間片此時變 為0，則將其時間片置為1，相當於此時父進程即將用完其時間片，調用scheduler_tick()來開始新的調度（具體 見"scheduler_tick"一節）。
(3) 初始化新進程的統計信息 -- wake_up_forked_process(task_t * p)
該函數是每一個剛被fork出來的進程必須執行的函數，被kernel/fork.c中的do_fork
()函數調用，函數主要完成一些fork出的新進程統計信息的初始化，主要包括：
a. 父進程和子進程sleep_avg的變化（請參照"sleep_avg進程創建"一節）；
b. 子進程的interactive_credit置為0，重新計算子進程的prio，設置子進程的cpu號；
c. 如果當前進程不在任何active array中（如idle進程），則調用__activate_task(p, rq)將子進程加入到active array裏麵；否則將父進程的動態優先級賦給子進程，並且將子進程添加到父進程的運行隊列中去。
(4) 創建進程完畢 -- schedule_tail()
這個函數是在fork()係統調用即將完成，返回用戶態之前，經過entry.S時調用的。函數主要完成一些fork完畢需做的清理工作，如釋放上文所說的自旋鎖等。
(5) 進程運行過程中 -- scheduler_tick()
update_process_time()（被時鍾中斷服務程序調用）調用該函數來更新當前進程的時間片，並且根據減小後的結果進行相應的處理。函數主要完成：
a. 完成當前進程使用的係統時間、用戶時間的統計信息；
b. 如果當前進程是實時進程，調度策略是SCHED_RR（調度策略是SCHED_FIFO的進程不需要重新分配時間片），且已經用完時間片，則重新計算時間 片，將（表明該進程退出時不會把時間片交還給父進程），置位TIF_NEED_RESCHED，將進程放到進程隊列的末尾；
c. 如果不是實時進程，且用完時間片：
a). 置位TIF_NEED_RESCHED，重新計算進程的動態優先級和時間片，將first_timeslice置0，記錄rq-> expired_timestamp的值（意義參見"expired_timestamp"一節）；
b). 根據TASK_INTERACTIVE()（宏的意義參見"TASK_INTERACTIVE"一節）判斷是否交互進程，用宏EXPIRED_STARVING(rq)判斷expired array是否已經饑餓，將該宏展開後為：
(STARVATION_LIMIT && ((rq)->expired_timestamp&&(jiffies-
(rq)->expired_timestamp >= STARVATION_LIMIT * ((rq)->nr_running) + 1)))
|| ((rq)->curr->static_prio > (rq)->best_expired_prio)
可見如果EXPIRED_STARVING()的是否為真與三個因素有關：
a. STARVATION_LIMIT為真；
b. (rq)->expired_timestamp為真；
c. 若(rq)->expired_timestamp >= STARVATION_LIMIT * ((rq)->nr_running) + 1)（說明expired array上的進程已經等了足夠長的時間）為真，或者((rq)->curr->static_prio > (rq)->best_expired_prio)（說明當前進程的靜態優先級比expired array中最高的優先級低）為真。
c). 如果進程被認為是交互進程，而且EXPIRED_STARVING()為假，則將當前進程重新插入到active array裏麵（參見"TASK_INTERACTIVE"一節）；否則，將進程插入到expired array。
d) 如果進程尚未用完時間片，該進程是交互式進程，且剩餘的時間片是該進程時間片粒度的整數倍（至少1倍），則強行剝奪該進程CPU使用權，且放到active array裏麵運行隊列的末尾（實際上是在交互式進程內部實行RR策略了）。時間片粒度的和兩個因素有關：
a. sleep_avg sleep_avg越大，粒度越大，因為越大說明該進程是交互進程的可能性越大，交互式進程的特點就是時間片小，頻率高；反之，如果是一個CPU-bound進程就應該少分片或者不分片（盡量避免cache失配），應該有高的粒度；
b. CPU個數 CPU個數越多，運行粒度就越大。
(6) 進程狀態的相互轉換（sleep和wake up）
這裏簡單的介紹函數wait_for_completion()和try_to_wake_up()。
wait_for_completion()
該函數是標準的將用戶由就緒狀態轉為睡眠狀態的函數，主要經過以下幾個步驟：
a. 通過DECLARE_WAITQUEUE()創建一個等待隊列入口；
b. 通過函數__add_wait_queue_tail()將進程加入到等待隊列；
c. 將進程狀態置為TASK_UNINTERRUPTIBLE；
d. 調用schedule()函數進行調度；
e. 利用循環檢查進程等待條件是否滿足，如果滿足通過函數__remove_wait_queue()將進程從等待隊列中刪除；否則，繼續通過schedule()進行調度。
try_to_wake_up()
函數調用activate_task()將進程加到就緒隊列中，如果新喚醒的進程的優先級比rq->curr高（具體原因請參見"curr"一節），則置位TIF_NEED_RESCHED，最後將進程的
狀態置為TASK_RUNNING。
(7) 進程結束，退出調度 -- sched_exit(task_t *p)
被release_task()調用，用於處理進程銷毀前調度信息的清理，包括：
a. 根據p->first_timeslice來判斷是否將時間片交還給父進程；如果first_timeslice的值為1，則說明p尚未用完fork時從父進程分來的時間片，此時應該將時間片交還父進程；否則，說明子進程已經重新分配過時間片，無須交還；
b. 如果子進程（p）的執行時間過長（p->sleep_avg < p->parent->sleep_avg），則給予父進程一定的懲罰（稍稍減小父進程的sleep_avg）。
6. 內核可搶占
Kernel 2.6的一大亮點就是內核可搶占，是Kernel 2.6進程調度優於2.4的一個重要表現。
(1) 何時可以搶占內核
在前麵我們已經講了內核何時可以搶占：當內核進程沒有訪問內核的關鍵數據，也就是內核沒有被加鎖，此時內核代碼是可重入的，可以搶占內核。對內核搶占加鎖 是通過preempt_disable()來實現的，這個宏隻是簡單的將preempt_count增1就實現了內核的加鎖，表明此時已經進入內核的關鍵 數據區域，內核不可被搶占。
(2) 如何搶占內核
中斷返回內核時
在前麵介紹"preempt_count"的時候已經提到，內核能否搶占是通過操作preempt_count來實現的。注意arch/i386/kernel/entry.S裏麵以下程序：
ENTRY(resume_kernel)
cmpl $0,TI_PRE_COUNT(%ebp) # non-zero preempt_count ?
jnz restore_all
need_resched:
movl TI_FLAGS(%ebp), %ecx # need_resched set ?
testb $_TIF_NEED_RESCHED, %cl
jz restore_all
testl $IF_MASK,EFLAGS(%esp) # interrupts off (exception path) ?
jz restore_all
movl $PREEMPT_ACTIVE,TI_PRE_COUNT(%ebp)
sti
call schedule
movl $0,TI_PRE_COUNT(%ebp)
cli
jmp need_resched
程序中可以看出，在中斷或者異常返回內核空間以後，首先檢查preempt_count是否為0，如果不為0，說明已經內核已經禁止被搶占；如果為0，則 檢查TIF_NEED_RESCHED位，如果已經被置位則檢查此次是否是通過中斷（通過檢查堆棧中EFLAGS的IF位來檢查發生此次"中斷"前IF是 否被置位，如果被置位說明是中斷；否則說明是由異常返回內核）返回內核空間的，如果是，則調用schedule()函數進行調度。可見，搶占內核是發生在 由中斷返回內核空間的時候。
解鎖時
解鎖通過宏preempt_enable()來完成，此函數完成以下功能：
a. 將當前進程的preempt_count減1
b. 檢查TIF_NEED_RESCHED位，如果是0，則返回；否則調用函數preempt_schedule()，此函數將preempt_count置 為PREEMPT_ACTIVE（表明正在執行內核搶占），然後直接調用schedule()進行調度。內核代碼中直接調用函數schedule()這種 情況下是沒有任何保護措施的，也就是說調用的代碼必須清楚此時進行內核搶占是否安全。
最後更新：2017-04-03 20:51:31