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