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