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