Linux 進(jìn)程調(diào)度原理

進(jìn)程調(diào)度依據(jù)


調(diào)度程序運(yùn)行時，要在所有可運(yùn)行狀態(tài)的進(jìn)程中選擇最值得運(yùn)行的進(jìn)程投入運(yùn)行。選擇進(jìn)程的依據(jù)是什么呢？在每個進(jìn)程的task_strUCt結(jié)構(gòu)中有以下四項：policy、priority、counter、rt_priority。這四項是選擇進(jìn)程的依據(jù)。 其中，policy是進(jìn)程的調(diào)度策略，用來區(qū)分實時進(jìn)程和普通進(jìn)程，實時進(jìn)程優(yōu)先于普通進(jìn)程運(yùn)行；priority是進(jìn)程(包括實時和普通)的靜態(tài)優(yōu)先級；counter是進(jìn)程剩余的時間片，它的起始值就是priority的值；由于counter在后面計算一個處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度goodness時起重要作用，因此，counter也可以看作是進(jìn)程的動態(tài)優(yōu)先級。rt_priority是實時進(jìn)程特有的，用于實時進(jìn)程間的選擇。

Linux用函數(shù)goodness()來衡量一個處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度。該函數(shù)綜合了以上提到的四項，還結(jié)合了一些其他的因素，給每個處于可運(yùn)行狀態(tài)的進(jìn)程賦予一個權(quán)值(weight)，調(diào)度程序以這個權(quán)值作為選擇進(jìn)程的唯一依據(jù)。關(guān)于goodness()的情況在后面將會詳細(xì)分析。


進(jìn)程調(diào)度策略


調(diào)度程序運(yùn)行時,要在所有處于可運(yùn)行狀態(tài)的進(jìn)程之中選擇最值得運(yùn)行的進(jìn)程投入運(yùn)行。選擇進(jìn)程的依據(jù)是什么呢?在每個進(jìn)程的task_struct 結(jié)構(gòu)中有這么四項：

policy, priority , counter, rt_priority

這四項就是調(diào)度程序選擇進(jìn)程的依據(jù).其中,policy是進(jìn)程的調(diào)度策略,用來區(qū)分兩種進(jìn)程-實時和普通；priority是進(jìn)程(實時和普通)的優(yōu)先級；counter 是進(jìn)程剩余的時間片,它的大小完全由priority決定;rt_priority是實時優(yōu)先級,這是實時進(jìn)程所特有的，用于實時進(jìn)程間的選擇。

首先，Linux 根據(jù)policy從整體上區(qū)分實時進(jìn)程和普通進(jìn)程，因為實時進(jìn)程和普通進(jìn)程度調(diào)度是不同的，它們兩者之間，實時進(jìn)程應(yīng)該先于普通進(jìn)程而運(yùn)行，然后，對于同一類型的不同進(jìn)程，采用不同的標(biāo)準(zhǔn)來選擇進(jìn)程：

對于普通進(jìn)程，Linux采用動態(tài)優(yōu)先調(diào)度，選擇進(jìn)程的依據(jù)就是進(jìn)程counter的大小。進(jìn)程創(chuàng)建時，優(yōu)先級priority被賦一個初值，一般為0～70之間的數(shù)字，這個數(shù)字同時也是計數(shù)器counter的初值，就是說進(jìn)程創(chuàng)建時兩者是相等的。字面上看，priority是\"優(yōu)先級\"、counter是\"計數(shù)器\"的意思，然而實際上，它們表達(dá)的是同一個意思-進(jìn)程的\"時間片\"。Priority代表分配給該進(jìn)程的時間片，counter表示該進(jìn)程剩余的時間片。在進(jìn)程運(yùn)行過程中，counter不斷減少，而priority保持不變，以便在counter變?yōu)?的時候（該進(jìn)程用完了所分配的時間片）對counter重新賦值。當(dāng)一個普通進(jìn)程的時間片用完以后，并不馬上用priority對counter進(jìn)行賦值，只有所有處于可運(yùn)行狀態(tài)的普通進(jìn)程的時間片(p->counter==0)都用完了以后，才用priority對counter重新賦值，這個普通進(jìn)程才有了再次被調(diào)度的機(jī)會。這說明，普通進(jìn)程運(yùn)行過程中，counter的減小給了其它進(jìn)程得以運(yùn)行的機(jī)會，直至counter減為0時才完全放棄對CPU的使用，這就相對于優(yōu)先級在動態(tài)變化，所以稱之為動態(tài)優(yōu)先調(diào)度。至于時間片這個概念，和其他不同操作系統(tǒng)一樣的，Linux的時間單位也是\"時鐘滴答\"，只是不同操作系統(tǒng)對一個時鐘滴答的定義不同而已（Linux為10ms）。進(jìn)程的時間片就是指多少個時鐘滴答，比如，若priority為20，則分配給該進(jìn)程的時間片就為20個時鐘滴答，也就是20*10ms=200ms。Linux中某個進(jìn)程的調(diào)度策略(policy)、優(yōu)先級(priority)等可以作為參數(shù)由用戶自己決定，具有相當(dāng)?shù)撵`活性。內(nèi)核創(chuàng)建新進(jìn)程時分配給進(jìn)程的時間片缺省為200ms(更準(zhǔn)確的，應(yīng)為210ms)，用戶可以通過系統(tǒng)調(diào)用改變它。

對于實時進(jìn)程，Linux采用了兩種調(diào)度策略，即FIFO(先來先服務(wù)調(diào)度)和RR（時間片輪轉(zhuǎn)調(diào)度）。因為實時進(jìn)程具有一定程度的緊迫性，所以衡量一個實時進(jìn)程是否應(yīng)該運(yùn)行，Linux采用了一個比較固定的標(biāo)準(zhǔn)。實時進(jìn)程的counter只是用來表示該進(jìn)程的剩余時間片，并不作為衡量它是否值得運(yùn)行的標(biāo)準(zhǔn)。實時進(jìn)程的counter只是用來表示該進(jìn)程的剩余時間片，并不作為衡量它是否值得運(yùn)行的標(biāo)準(zhǔn)，這和普通進(jìn)程是有區(qū)別的。上面已經(jīng)看到，每個進(jìn)程有兩個優(yōu)先級，實時優(yōu)先級就是用來衡量實時進(jìn)程是否值得運(yùn)行的。

這一切看來比較麻煩，但實際上Linux中的實現(xiàn)相當(dāng)簡單。Linux用函數(shù)goodness()來衡量一個處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度。該函數(shù)綜合了上面提到的各個方面，給每個處于可運(yùn)行狀態(tài)的進(jìn)程賦予一個權(quán)值(weight)，調(diào)度程序以這個權(quán)值作為選擇進(jìn)程的唯一依據(jù)。

Linux根據(jù)policy的值將進(jìn)程總體上分為實時進(jìn)程和普通進(jìn)程，提供了三種調(diào)度算法：一種傳統(tǒng)的Unix調(diào)度程序和兩個由POSIX.1b(原名為POSIX.4)操作系統(tǒng)標(biāo)準(zhǔn)所規(guī)定的\"實時\"調(diào)度程序。但這種實時只是軟實時，不滿足諸如中斷等待時間等硬實時要求，只是保證了當(dāng)實時進(jìn)程需要時一定只把CPU分配給實時進(jìn)程。

非實時進(jìn)程有兩種優(yōu)先級，一種是靜態(tài)優(yōu)先級，另一種是動態(tài)優(yōu)先級。實時進(jìn)程又增加了第三種優(yōu)先級，實時優(yōu)先級。優(yōu)先級是一些簡單的整數(shù)，為了決定應(yīng)該允許哪一個進(jìn)程使用CPU的資源，用優(yōu)先級代表相對權(quán)值-優(yōu)先級越高，它得到CPU時間的機(jī)會也就越大。

靜態(tài)優(yōu)先級(priority)-不隨時間而改變，只能由用戶進(jìn)行修改。它指明了在被迫和其他進(jìn)程競爭CPU之前，該進(jìn)程所應(yīng)該被允許的時間片的最大值（但很可能的，在該時間片耗盡之前，進(jìn)程就被迫交出了CPU）。

動態(tài)優(yōu)先級(counter)-只要進(jìn)程擁有CPU，它就隨著時間不斷減??；當(dāng)它小于0時，標(biāo)記進(jìn)程重新調(diào)度。它指明了在這個時間片中所剩余的時間量。

實時優(yōu)先級(rt_priority)-指明這個進(jìn)程自動把CPU交給哪一個其他進(jìn)程；較高權(quán)值的進(jìn)程總是優(yōu)先于較低權(quán)值的進(jìn)程。如果一個進(jìn)程不是實時進(jìn)程，其優(yōu)先級就是0，所以實時進(jìn)程總是優(yōu)先于非實時進(jìn)程的（但實際上，實時進(jìn)程也會主動放棄CPU）。

當(dāng)policy分別為以下值時：

1) SCHED_OTHER：這是普通的用戶進(jìn)程，進(jìn)程的缺省類型，采用動態(tài)優(yōu)先調(diào)度策略，選擇進(jìn)程的依據(jù)主要是根據(jù)進(jìn)程goodness值的大小。這種進(jìn)程在運(yùn)行時，可以被高goodness值的進(jìn)程搶先。

2) SCHED_FIFO：這是一種實時進(jìn)程，遵守POSIX1.b標(biāo)準(zhǔn)的FIFO(先入先出)調(diào)度規(guī)則。它會一直運(yùn)行，直到有一個進(jìn)程因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個具有更高rt_priority的實時進(jìn)程搶先。在Linux實現(xiàn)中，SCHED_FIFO進(jìn)程仍然擁有時間片-只有當(dāng)時間片用完時它們才被迫釋放CPU。因此，如同POSIX1.b一樣，這樣的進(jìn)程就象沒有時間片(不是采用分時)一樣運(yùn)行。Linux中進(jìn)程仍然保持對其時間片的記錄（不修改counter）主要是為了實現(xiàn)的方便，同時避免在調(diào)度代碼的關(guān)鍵路徑上出現(xiàn)條件判斷語句 if (!(current->policy&SCHED_FIFO)){...}-要知道，其他大量非FIFO進(jìn)程都需要記錄時間片，這種多余的檢測只會浪費CPU資源。（一種優(yōu)化措施，不該將執(zhí)行時間占10%的代碼的運(yùn)行時間減少到50%；而是將執(zhí)行時間占90%的代碼的運(yùn)行時間減少到95%。0.9+0.1*0.5=0.95>0.1+0.9*0.9=0.91）

3) SCHED_RR：這也是一種實時進(jìn)程，遵守POSIX1.b標(biāo)準(zhǔn)的RR(循環(huán)round-robin)調(diào)度規(guī)則。除了時間片有些不同外，這種策略與SCHED_FIFO類似。當(dāng)SCHED_RR進(jìn)程的時間片用完后，就被放到SCHED_FIFO和SCHED_RR隊列的末尾。

只要系統(tǒng)中有一個實時進(jìn)程在運(yùn)行，則任何SCHED_OTHER進(jìn)程都不能在任何CPU運(yùn)行。每個實時進(jìn)程有一個rt_priority，因此，可以按照rt_priority在所有SCHED_RR進(jìn)程之間分配CPU。其作用與SCHED_OTHER進(jìn)程的priority作用一樣。只有root用戶能夠用系統(tǒng)調(diào)用sched_setscheduler，來改變當(dāng)前進(jìn)程的類型(sys_nice,sys_setpriority)。
此外，內(nèi)核還定義了SCHED_YIELD，這并不是一種調(diào)度策略，而是截取調(diào)度策略的一個附加位。如同前面說明的一樣，如果有其他進(jìn)程需要CPU，它就提示調(diào)度程序釋放CPU。特別要注意的就是這甚至?xí)饘崟r進(jìn)程把CPU釋放給非實時進(jìn)程。


主要的進(jìn)程調(diào)度的函數(shù)分析


真正執(zhí)行調(diào)度的函數(shù)是schedule(void),它選擇一個最合適的進(jìn)程執(zhí)行，并且真正進(jìn)行上下文切換，使得選中的進(jìn)程得以執(zhí)行。而reschedule_idle(struct task_struct *p)的作用是為進(jìn)程選擇一個合適的CPU來執(zhí)行，如果它選中了某個CPU，則將該CPU上當(dāng)前運(yùn)行進(jìn)程的need_resched標(biāo)志置為1,然后向它發(fā)出一個重新調(diào)度的處理機(jī)間中斷，使得選中的CPU能夠在中斷處理返回時執(zhí)行schedule函數(shù)，真正調(diào)度進(jìn)程p在CPU上執(zhí)行。在schedule()和reschedule_idle()中調(diào)用了goodness()函數(shù)。goodness()函數(shù)用來衡量一個處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度。此外，在schedule()函數(shù)中還調(diào)用了schedule_tail()函數(shù);在reschedule_idle()函數(shù)中還調(diào)用了reschedule_idle_slow()。這些函數(shù)的實現(xiàn)對理解SMP的調(diào)度非常重要，下面一一分析這些函數(shù)。先給出每個函數(shù)的主要流程圖，然后給出源代碼，并加注釋。


goodness()函數(shù)分析


goodness()函數(shù)計算一個處于可運(yùn)行狀態(tài)的進(jìn)程值得運(yùn)行的程度。一個任務(wù)的goodness是以下因素的函數(shù)：正在運(yùn)行的任務(wù)、想要運(yùn)行的任務(wù)、當(dāng)前的CPU。goodness返回下面兩類值中的一個：1000以下或者1000以上。1000或者1000以上的值只能賦給\"實時\"進(jìn)程，從0到999的值只能賦給普通進(jìn)程。實際上，在單處理器情況下，普通進(jìn)程的goodness值只使用這個范圍底部的一部分，從0到41。在SMP情況下，SMP模式會優(yōu)先照顧等待同一個處理器的進(jìn)程。不過，不管是UP還是SMP，實時進(jìn)程的goodness值的范圍是從1001到1099。

goodness()函數(shù)其實是不會返回-1000的，也不會返回其他負(fù)值。由于idle進(jìn)程的counter值為負(fù)，所以如果使用idle進(jìn)程作為參數(shù)調(diào)用goodness，就會返回負(fù)值，但這是不會發(fā)生的。