深入分析Linux內(nèi)核源碼－進(jìn)程調(diào)度(2)
3 Linux的調(diào)度程序－Schedule( )
3.1基本原理
調(diào)度的實(shí)質(zhì)就是資源的分配。系統(tǒng)通過(guò)不同的調(diào)度算法（Scheduling Algorithm）來(lái)實(shí)現(xiàn)這種資源的分配。通常來(lái)說(shuō)，選擇什么樣的調(diào)度算法取決于的資源分配的策略（Scheduling Policy），在這里只說(shuō)明與Linux調(diào)度相關(guān)的幾種算法及這些算法的原理。
一個(gè)好的調(diào)度算法應(yīng)當(dāng)考慮以下幾個(gè)方面：
（1）公平：保證每個(gè)進(jìn)程得到合理的CPU時(shí)間。
（2）高效：使CPU保持忙碌狀態(tài)，即總是有進(jìn)程在CPU上運(yùn)行。
（3）響應(yīng)時(shí)間：使交互用戶的響應(yīng)時(shí)間盡可能短。
（4）周轉(zhuǎn)時(shí)間：使批處理用戶等待輸出的時(shí)間盡可能短。
（5）吞吐量：使單位時(shí)間內(nèi)處理的進(jìn)程數(shù)量盡可能多。
很顯然，這5個(gè)目標(biāo)不可能同時(shí)達(dá)到，所以，不同的操作系統(tǒng)會(huì)在這幾個(gè)方面中作出相應(yīng)的取舍，從而確定自己的調(diào)度算法，例如UNIX采用動(dòng)態(tài)優(yōu)先數(shù)調(diào)度、BSD采用多級(jí)反饋隊(duì)列調(diào)度、Windows采用搶先多任務(wù)調(diào)度等等。
下面來(lái)了解一下主要的調(diào)度算法及其基本原理：
1．時(shí)間片輪轉(zhuǎn)調(diào)度算法
時(shí)間片（Time Slice）就是分配給進(jìn)程運(yùn)行的一段時(shí)間。在通常的輪轉(zhuǎn)法中，系統(tǒng)將所有的可運(yùn)行（即就緒）進(jìn)程按先來(lái)先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，系統(tǒng)發(fā)出信號(hào)，通知調(diào)度程序，調(diào)度程序便據(jù)此信號(hào)來(lái)停止該進(jìn)程的執(zhí)行，并將它送到運(yùn)行隊(duì)列的末尾，等待下一次執(zhí)行；然后，把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證運(yùn)行隊(duì)列中的所有進(jìn)程，在一個(gè)給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。
2．優(yōu)先權(quán)調(diào)度算法
為了照顧到緊迫型進(jìn)程在進(jìn)入系統(tǒng)后便能獲得優(yōu)先處理，引入了***優(yōu)先權(quán)調(diào)度算法。當(dāng)將該算法用于進(jìn)程調(diào)度時(shí)，系統(tǒng)將把處理機(jī)分配給運(yùn)行隊(duì)列中優(yōu)先權(quán)***的進(jìn)程，這時(shí)，又可進(jìn)一步把該算法分成兩種方式：
(1) 非搶占式優(yōu)先權(quán)算法（又稱不可剝奪調(diào)度：Nonpreemptive Scheduling）
在這種方式下，系統(tǒng)一旦將處理機(jī)（CPU）分配給運(yùn)行隊(duì)列中優(yōu)先權(quán)***的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可將處理機(jī)分配給另一個(gè)優(yōu)先權(quán)高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中，也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。
(2) 搶占式優(yōu)先權(quán)調(diào)度算法（又稱可剝奪調(diào)度：Preemptive Scheduling）
該算法的本質(zhì)就是系統(tǒng)中當(dāng)前運(yùn)行的進(jìn)程永遠(yuǎn)是可運(yùn)行進(jìn)程中優(yōu)先權(quán)***的那個(gè)。在采用這種調(diào)度算法時(shí)，每當(dāng)出現(xiàn)一新的可運(yùn)行進(jìn)程，就將它和當(dāng)前運(yùn)行進(jìn)程進(jìn)行優(yōu)先權(quán)比較，如果高于當(dāng)前進(jìn)程，將觸發(fā)進(jìn)程調(diào)度。這種方式的優(yōu)先權(quán)調(diào)度算法，能更好的滿足緊迫進(jìn)程的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。Linux也采用這種調(diào)度算法。
3．多級(jí)反饋隊(duì)列調(diào)度
這是時(shí)下最時(shí)髦的一種調(diào)度算法。其本質(zhì)是：綜合了時(shí)間片輪轉(zhuǎn)調(diào)度和搶占式優(yōu)先權(quán)調(diào)度的優(yōu)點(diǎn)，即：優(yōu)先權(quán)高的進(jìn)程先運(yùn)行給定的時(shí)間片，相同優(yōu)先權(quán)的進(jìn)程輪流運(yùn)行給定的時(shí)間片。
4．實(shí)時(shí)調(diào)度
***我們來(lái)看一下實(shí)時(shí)系統(tǒng)中的調(diào)度。什么叫實(shí)時(shí)系統(tǒng)，就是系統(tǒng)對(duì)外部事件有求必應(yīng)、盡快響應(yīng)。在實(shí)時(shí)系統(tǒng)中，廣泛采用搶占調(diào)度方式，特別是對(duì)于那些要求嚴(yán)格的實(shí)時(shí)系統(tǒng)。因?yàn)檫@種調(diào)度方式既具有較大的靈活性，又能獲得很小的調(diào)度延遲；但是這種調(diào)度方式也比較復(fù)雜。
3.2 Linux進(jìn)程調(diào)度時(shí)機(jī)
Linux的調(diào)度程序是一個(gè)叫Schedule（）的函數(shù)，這個(gè)函數(shù)被調(diào)用的頻率很高，由它來(lái)決定是否要進(jìn)行進(jìn)程的切換，如果要切換的話，切換到哪個(gè)進(jìn)程等等。我們先來(lái)看在什么情況下要執(zhí)行調(diào)度程序，我們把這種情況叫做調(diào)度時(shí)機(jī)。
Linux調(diào)度時(shí)機(jī)主要有：
1、進(jìn)程狀態(tài)轉(zhuǎn)換的時(shí)刻：進(jìn)程終止、進(jìn)程睡眠；
2、當(dāng)前進(jìn)程的時(shí)間片用完時(shí)（current->counter=0）；
3、設(shè)備驅(qū)動(dòng)程序主動(dòng)調(diào)用schedule；
4、進(jìn)程從中斷、異常及系統(tǒng)調(diào)用返回到用戶態(tài)時(shí)；
時(shí)機(jī)1，進(jìn)程要調(diào)用sleep（）或exit（）等函數(shù)進(jìn)行狀態(tài)轉(zhuǎn)換，這些函數(shù)會(huì)主動(dòng)調(diào)用調(diào)度程序進(jìn)行進(jìn)程調(diào)度；
時(shí)機(jī)2，由于進(jìn)程的時(shí)間片是由時(shí)鐘中斷來(lái)更新的，因此，這種情況和時(shí)機(jī)4是一樣的。
#p#時(shí)機(jī)3，當(dāng)設(shè)備驅(qū)動(dòng)程序執(zhí)行長(zhǎng)而重復(fù)的任務(wù)時(shí)，直接調(diào)用調(diào)度程序。在每次反復(fù)循環(huán)中，驅(qū)動(dòng)程序都檢查need_resched的值，如果必要，則調(diào)用調(diào)度程序schedule()主動(dòng)放棄CPU。
時(shí)機(jī)4，如前所述，不管是從中斷、異常還是系統(tǒng)調(diào)用返回，最終都調(diào)用ret_from_sys_call（），由這個(gè)函數(shù)進(jìn)行調(diào)度標(biāo)志的檢測(cè)，如果必要，則調(diào)用調(diào)度程序。那么，為什么從系統(tǒng)調(diào)用返回時(shí)要調(diào)用調(diào)度程序呢？這當(dāng)然是從效率考慮。從系統(tǒng)調(diào)用返回意味著要離開(kāi)內(nèi)核態(tài)而返回到用戶態(tài)，而狀態(tài)的轉(zhuǎn)換要花費(fèi)一定的時(shí)間，因此，在返回到用戶態(tài)前，系統(tǒng)把在內(nèi)核態(tài)該處理的事全部做完。
每個(gè)時(shí)鐘中斷（timer interrupt）發(fā)生時(shí)，由三個(gè)函數(shù)協(xié)同工作，共同完成進(jìn)程的選擇和切換，它們是：schedule（）、do_timer（）及ret_form_sys_call（）。我們先來(lái)解釋一下這三個(gè)函數(shù)：
schedule（）：進(jìn)程調(diào)度函數(shù)，由它來(lái)完成進(jìn)程的選擇（調(diào)度）；
do_timer（）：暫且稱之為時(shí)鐘函數(shù)，該函數(shù)在時(shí)鐘中斷服務(wù)程序中被調(diào)用，被調(diào)用的頻率就是時(shí)鐘中斷的頻率即每秒鐘100次（簡(jiǎn)稱100赫茲或100Hz）；
ret_from_sys_call（）：系統(tǒng)調(diào)用返回函數(shù)。當(dāng)一個(gè)系統(tǒng)調(diào)用或中斷完成時(shí)，該函數(shù)被調(diào)用，用于處理一些收尾工作，例如信號(hào)處理、核心任務(wù)等等。
這三個(gè)函數(shù)是如何協(xié)調(diào)工作的呢？
前面我們看到，時(shí)鐘中斷是一個(gè)中斷服務(wù)程序，它的主要組成部分就是時(shí)鐘函數(shù)do_timer（），由這個(gè)函數(shù)完成系統(tǒng)時(shí)間的更新、進(jìn)程時(shí)間片的更新等工作，更新后的進(jìn)程時(shí)間片counter作為調(diào)度的主要依據(jù)。在時(shí)鐘中斷返回時(shí)，要調(diào)用函數(shù)ret_from_sys_call（），前面我們已經(jīng)討論過(guò)這個(gè)函數(shù)，在這個(gè)函數(shù)中有如下幾行：
cmpl $0， _need_resched
jne reschedule
……
restore_all:
RESTORE_ALL
reschedule:
call SYMBOL_NAME(schedule)
jmp ret_from_sys_call
這幾行的意思很明顯：檢測(cè) need_resched 標(biāo)志，如果此標(biāo)志為非0，那么就轉(zhuǎn)到reschedule處調(diào)用調(diào)度程序schedule（）進(jìn)行進(jìn)程的選擇。調(diào)度程序schedule（）會(huì)根據(jù)具體的標(biāo)準(zhǔn)在運(yùn)行隊(duì)列中選擇下一個(gè)應(yīng)該運(yùn)行的進(jìn)程。當(dāng)從調(diào)度程序返回時(shí)，如果發(fā)現(xiàn)又有調(diào)度標(biāo)志被設(shè)置，則又調(diào)用調(diào)度程序，直到調(diào)度標(biāo)志為0，這時(shí)，從調(diào)度程序返回時(shí)由RESTORE_ALL恢復(fù)被選定進(jìn)程的環(huán)境，返回到被選定進(jìn)程的用戶空間，使之得到運(yùn)行。
Linux 調(diào)度程序和其他的UNIX調(diào)度程序不同，尤其是在“nice level”優(yōu)先級(jí)的處理上，與優(yōu)先權(quán)調(diào)度（priority高的進(jìn)程***運(yùn)行）不同，Linux用的是時(shí)間片輪轉(zhuǎn)調(diào)度（Round Robing），但同時(shí)又保證了高優(yōu)先級(jí)的進(jìn)程運(yùn)行的既快、時(shí)間又長(zhǎng)（both sooner and longer）。而標(biāo)準(zhǔn)的UNIX調(diào)度程序都用到了多級(jí)進(jìn)程隊(duì)列。大多數(shù)的實(shí)現(xiàn)都用到了二級(jí)優(yōu)先隊(duì)列：一個(gè)標(biāo)準(zhǔn)隊(duì)列和一個(gè)實(shí)時(shí)（“real time”）隊(duì)列。一般情況下，如果實(shí)時(shí)隊(duì)列中的進(jìn)程未被阻塞，它們都要在標(biāo)準(zhǔn)隊(duì)列中的進(jìn)程之前被執(zhí)行，并且，每個(gè)隊(duì)列中，“nice level”高的進(jìn)程先被執(zhí)行。
3.3 進(jìn)程調(diào)度的依據(jù)
調(diào)度程序運(yùn)行時(shí)，要在所有處于可運(yùn)行狀態(tài)的進(jìn)程之中選擇最值得運(yùn)行的進(jìn)程投入運(yùn)行。選擇進(jìn)程的依據(jù)是什么呢？在每個(gè)進(jìn)程的task_struct結(jié)構(gòu)中有這么五項(xiàng)：
need_resched、nice、counter、policy 及rt_priority
need_resched: 在調(diào)度時(shí)機(jī)到來(lái)時(shí)，檢測(cè)這個(gè)域的值，如果為1，則調(diào)用schedule() 。
counter: 進(jìn)程處于運(yùn)行狀態(tài)時(shí)所剩余的時(shí)鐘滴答數(shù)，每次時(shí)鐘中斷到來(lái)時(shí)，這個(gè)值就減1。當(dāng)這個(gè)域的值變得越來(lái)越小，直至為0時(shí)，就把need_resched 域置1，因此，也把這個(gè)域叫做進(jìn)程的“動(dòng)態(tài)優(yōu)先級(jí)”。
nice: 進(jìn)程的“靜態(tài)優(yōu)先級(jí)”，這個(gè)域決定counter 的初值。只有通過(guò)nice()， sched_setparam()系統(tǒng)調(diào)用才能改變進(jìn)程的靜態(tài)優(yōu)先級(jí)。
rt_priority: 實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)
policy: 從整體上區(qū)分實(shí)時(shí)進(jìn)程和普通進(jìn)程，因?yàn)閷?shí)時(shí)進(jìn)程和普通進(jìn)程的調(diào)度是不同的，它們兩者之間，實(shí)時(shí)進(jìn)程應(yīng)該先于普通進(jìn)程而運(yùn)行，可以通過(guò)系統(tǒng)調(diào)用sched_setscheduler( )來(lái)改變調(diào)度的策略。對(duì)于同一類型的不同進(jìn)程，采用不同的標(biāo)準(zhǔn)來(lái)選擇進(jìn)程。對(duì)于普通進(jìn)程，選擇進(jìn)程的主要依據(jù)為counter和nice 。對(duì)于實(shí)時(shí)進(jìn)程，Linux采用了兩種調(diào)度策略，即FIFO（先來(lái)先服務(wù)調(diào)度）和RR（時(shí)間片輪轉(zhuǎn)調(diào)度）。因?yàn)閷?shí)時(shí)進(jìn)程具有一定程度的緊迫性，所以衡量一個(gè)實(shí)時(shí)進(jìn)程是否應(yīng)該運(yùn)行，Linux采用了一個(gè)比較固定的標(biāo)準(zhǔn)。實(shí)時(shí)進(jìn)程的counter只是用來(lái)表示該進(jìn)程的剩余滴答數(shù)，并不作為衡量它是否值得運(yùn)行的標(biāo)準(zhǔn)，這和普通進(jìn)程是有區(qū)別的。
3.4 進(jìn)程可運(yùn)行程度的衡量
函數(shù)goodness（）就是用來(lái)衡量一個(gè)處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度。該函數(shù)綜合使用了上面我們提到的五項(xiàng)，給每個(gè)處于可運(yùn)行狀態(tài)的進(jìn)程賦予一個(gè)權(quán)值（weight），調(diào)度程序以這個(gè)權(quán)值作為選擇進(jìn)程的唯一依據(jù)。函數(shù)主體如下：
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{ int weight; ／* 權(quán)值，作為衡量進(jìn)程是否運(yùn)行的唯一依據(jù) *
weight=-1;
if (p->policy&SCHED_YIELD)
goto out; /*如果該進(jìn)程愿意“禮讓（yield）”，則讓其權(quán)值為－1 *／
switch(p->policy)
{
/* 實(shí)時(shí)進(jìn)程*/
case SCHED_FIFO:
case SCHED_RR:
weight = 1000 + p->rt_priority;
/* 普通進(jìn)程 */
case SCHED_OTHER:
{ weight = p->counter;
if(!weight)
goto out
/* 做細(xì)微的調(diào)整*/
if (p->mm=this_mm||!p->mm)
weight = weight+1;
weight+=20-p->nice; /*在剩余counter一樣的情況下，短進(jìn)程優(yōu)先*/
}
}
out:
return weight; /*返回權(quán)值*/
}
其中，在sched.h中對(duì)調(diào)度策略定義如下：
#define SCHED_OTHER 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_YIELD 0x10
這個(gè)函數(shù)比較很簡(jiǎn)單。首先，根據(jù)policy區(qū)分實(shí)時(shí)進(jìn)程和普通進(jìn)程。實(shí)時(shí)進(jìn)程的權(quán)值取決于其實(shí)時(shí)優(yōu)先級(jí)，其至少是1000，與conter和nice無(wú)關(guān)。普通進(jìn)程的權(quán)值需特別說(shuō)明兩點(diǎn)：
為什么進(jìn)行細(xì)微的調(diào)整？如果p->mm為空，則意味著該進(jìn)程無(wú)用戶空間（例如內(nèi)核線程），則無(wú)需切換到用戶空間。如果p->mm=this_mm，則說(shuō)明該進(jìn)程的用戶空間就是當(dāng)前進(jìn)程的用戶空間，該進(jìn)程完全有可能再次得到運(yùn)行。對(duì)于以上兩種情況，都給其權(quán)值加1，算是對(duì)它們小小的獎(jiǎng)勵(lì)。
進(jìn)程的優(yōu)先級(jí)nice是從早期Unix沿用下來(lái)的負(fù)向優(yōu)先級(jí)，其數(shù)值標(biāo)志“謙讓”的程度，其值越大，就表示其越“謙讓”，也就是優(yōu)先級(jí)越低，其取值范圍為－20～＋19，因此，（20-p->nice）的取值范圍就是0～40。可以看出，普通進(jìn)程的權(quán)值不僅考慮了其剩余的時(shí)間片，還考慮了其優(yōu)先級(jí)，優(yōu)先級(jí)越高，其權(quán)值越大。
根據(jù)進(jìn)程調(diào)度的依據(jù)，調(diào)度程序就可以控制系統(tǒng)中的所有處于可運(yùn)行狀態(tài)的進(jìn)程并在它們之間進(jìn)行選擇。
【編輯推薦】
