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

進(jìn)程調度依據

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

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

　　
　　進(jìn)程調度策略

　　
　　調度程序運行時(shí),要在所有處于可運行狀態(tài)的進(jìn)程之中選擇最值得運行的進(jìn)程投入運行。選擇進(jìn)程的依據是什么呢?在每個(gè)進(jìn)程的task_struct 結構中有這么四項：
　　
　　policy, priority , counter, rt_priority
　　
　　這四項就是調度程序選擇進(jìn)程的依據.其中,policy是進(jìn)程的調度策略,用來(lái)區分兩種進(jìn)程-實(shí)時(shí)和普通；priority是進(jìn)程(實(shí)時(shí)和普通)的優(yōu)先級；counter 是進(jìn)程剩余的時(shí)間片,它的大小完全由priority決定;rt_priority是實(shí)時(shí)優(yōu)先級,這是實(shí)時(shí)進(jìn)程所特有的，用于實(shí)時(shí)進(jìn)程間的選擇。
　　
　　首先，Linux 根據policy從整體上區分實(shí)時(shí)進(jìn)程和普通進(jìn)程，因為實(shí)時(shí)進(jìn)程和普通進(jìn)程度調度是不同的，它們兩者之間，實(shí)時(shí)進(jìn)程應該先于普通進(jìn)程而運行，然后，對于同一類(lèi)型的不同進(jìn)程，采用不同的標準來(lái)選擇進(jìn)程：
　　
　　對于普通進(jìn)程，Linux采用動(dòng)態(tài)優(yōu)先調度，選擇進(jìn)程的依據就是進(jìn)程counter的大小。進(jìn)程創(chuàng )建時(shí)，優(yōu)先級priority被賦一個(gè)初值，一般為0～70之間的數字，這個(gè)數字同時(shí)也是計數器counter的初值，就是說(shuō)進(jìn)程創(chuàng )建時(shí)兩者是相等的。字面上看，priority是優(yōu)先級、counter是計數器的意思，然而實(shí)際上，它們表達的是同一個(gè)意思-進(jìn)程的時(shí)間片。Priority代表分配給該進(jìn)程的時(shí)間片，counter表示該進(jìn)程剩余的時(shí)間片。在進(jìn)程運行過(guò)程中，counter不斷減少，而priority保持不變，以便在counter變?yōu)?的時(shí)候（該進(jìn)程用完了所分配的時(shí)間片）對counter重新賦值。當一個(gè)普通進(jìn)程的時(shí)間片用完以后，并不馬上用priority對counter進(jìn)行賦值，只有所有處于可運行狀態(tài)的普通進(jìn)程的時(shí)間片(p->counter==0)都用完了以后，才用priority對counter重新賦值，這個(gè)普通進(jìn)程才有了再次被調度的機會(huì )。這說(shuō)明，普通進(jìn)程運行過(guò)程中，counter的減小給了其它進(jìn)程得以運行的機會(huì )，直至counter減為0時(shí)才完全放棄對CPU的使用，這就相對于優(yōu)先級在動(dòng)態(tài)變化，所以稱(chēng)之為動(dòng)態(tài)優(yōu)先調度。至于時(shí)間片這個(gè)概念，和其他不同操作系統一樣的，Linux的時(shí)間單位也是時(shí)鐘滴答，只是不同操作系統對一個(gè)時(shí)鐘滴答的定義不同而已（Linux為10ms）。進(jìn)程的時(shí)間片就是指多少個(gè)時(shí)鐘滴答，比如，若priority為20，則分配給該進(jìn)程的時(shí)間片就為20個(gè)時(shí)鐘滴答，也就是20*10ms=200ms。Linux中某個(gè)進(jìn)程的調度策略(policy)、優(yōu)先級(priority)等可以作為參數由用戶(hù)自己決定，具有相當的靈活性。內核創(chuàng )建新進(jìn)程時(shí)分配給進(jìn)程的時(shí)間片缺省為200ms(更準確的，應為210ms)，用戶(hù)可以通過(guò)系統調用改變它。
　　
　　對于實(shí)時(shí)進(jìn)程，Linux采用了兩種調度策略，即FIFO(先來(lái)先服務(wù)調度)和RR（時(shí)間片輪轉調度）。因為實(shí)時(shí)進(jìn)程具有一定程度的緊迫性，所以衡量一個(gè)實(shí)時(shí)進(jìn)程是否應該運行，Linux采用了一個(gè)比較固定的標準。實(shí)時(shí)進(jìn)程的counter只是用來(lái)表示該進(jìn)程的剩余時(shí)間片，并不作為衡量它是否值得運行的標準。實(shí)時(shí)進(jìn)程的counter只是用來(lái)表示該進(jìn)程的剩余時(shí)間片，并不作為衡量它是否值得運行的標準，這和普通進(jìn)程是有區別的。上面已經(jīng)看到，每個(gè)進(jìn)程有兩個(gè)優(yōu)先級，實(shí)時(shí)優(yōu)先級就是用來(lái)衡量實(shí)時(shí)進(jìn)程是否值得運行的。
　　
　　這一切看來(lái)比較麻煩，但實(shí)際上Linux中的實(shí)現相當簡(jiǎn)單。Linux用函數goodness()來(lái)衡量一個(gè)處于可運行狀態(tài)的進(jìn)程值得運行的程度。該函數綜合了上面提到的各個(gè)方面，給每個(gè)處于可運行狀態(tài)的進(jìn)程賦予一個(gè)權值(weight)，調度程序以這個(gè)權值作為選擇進(jìn)程的唯一依據。
　　
　　Linux根據policy的值將進(jìn)程總體上分為實(shí)時(shí)進(jìn)程和普通進(jìn)程，提供了三種調度算法：一種傳統的Unix調度程序和兩個(gè)由POSIX.1b(原名為POSIX.4)操作系統標準所規定的實(shí)時(shí)調度程序。但這種實(shí)時(shí)只是軟實(shí)時(shí)，不滿(mǎn)足諸如中斷等待時(shí)間等硬實(shí)時(shí)要求，只是保證了當實(shí)時(shí)進(jìn)程需要時(shí)一定只把CPU分配給實(shí)時(shí)進(jìn)程。
　　
　　非實(shí)時(shí)進(jìn)程有兩種優(yōu)先級，一種是靜態(tài)優(yōu)先級，另一種是動(dòng)態(tài)優(yōu)先級。實(shí)時(shí)進(jìn)程又增加了第三種優(yōu)先級，實(shí)時(shí)優(yōu)先級。優(yōu)先級是一些簡(jiǎn)單的整數，為了決定應該允許哪一個(gè)進(jìn)程使用CPU的資源，用優(yōu)先級代表相對權值-優(yōu)先級越高，它得到CPU時(shí)間的機會(huì )也就越大。
　　
　　靜態(tài)優(yōu)先級(priority)-不隨時(shí)間而改變，只能由用戶(hù)進(jìn)行修改。它指明了在被迫和其他進(jìn)程競爭CPU之前，該進(jìn)程所應該被允許的時(shí)間片的最大值（但很可能的，在該時(shí)間片耗盡之前，進(jìn)程就被迫交出了CPU）。
　　
　　動(dòng)態(tài)優(yōu)先級(counter)-只要進(jìn)程擁有CPU，它就隨著(zhù)時(shí)間不斷減??；當它小于0時(shí)，標記進(jìn)程重新調度。它指明了在這個(gè)時(shí)間片中所剩余的時(shí)間量。
　　
　　實(shí)時(shí)優(yōu)先級(rt_priority)-指明這個(gè)進(jìn)程自動(dòng)把CPU交給哪一個(gè)其他進(jìn)程；較高權值的進(jìn)程總是優(yōu)先于較低權值的進(jìn)程。如果一個(gè)進(jìn)程不是實(shí)時(shí)進(jìn)程，其優(yōu)先級就是0，所以實(shí)時(shí)進(jìn)程總是優(yōu)先于非實(shí)時(shí)進(jìn)程的（但實(shí)際上，實(shí)時(shí)進(jìn)程也會(huì )主動(dòng)放棄CPU）。
　　
　　當policy分別為以下值時(shí)：
　　
　　1) SCHED_OTHER：這是普通的用戶(hù)進(jìn)程，進(jìn)程的缺省類(lèi)型，采用動(dòng)態(tài)優(yōu)先調度策略，選擇進(jìn)程的依據主要是根據進(jìn)程goodness值的大小。這種進(jìn)程在運行時(shí)，可以被高goodness值的進(jìn)程搶先。
　　
　　2) SCHED_FIFO：這是一種實(shí)時(shí)進(jìn)程，遵守POSIX1.b標準的FIFO(先入先出)調度規則。它會(huì )一直運行，直到有一個(gè)進(jìn)程因I/O阻塞，或者主動(dòng)釋放CPU，或者是CPU被另一個(gè)具有更高rt_priority的實(shí)時(shí)進(jìn)程搶先。在Linux實(shí)現中，SCHED_FIFO進(jìn)程仍然擁有時(shí)間片-只有當時(shí)間片用完時(shí)它們才被迫釋放CPU。因此，如同POSIX1.b一樣，這樣的進(jìn)程就象沒(méi)有時(shí)間片(不是采用分時(shí))一樣運行。Linux中進(jìn)程仍然保持對其時(shí)間片的記錄（不修改counter）主要是為了實(shí)現的方便，同時(shí)避免在調度代碼的關(guān)鍵路徑上出現條件判斷語(yǔ)句 if (!(current->policySCHED_FIFO)){...}-要知道，其他大量非FIFO進(jìn)程都需要記錄時(shí)間片，這種多余的檢測只會(huì )浪費CPU資源。（一種優(yōu)化措施，不該將執行時(shí)間占10%的代碼的運行時(shí)間減少到50%；而是將執行時(shí)間占90%的代碼的運行時(shí)間減少到95%。0.9+0.1*0.5=0.95>0.1+0.9*0.9=0.91）
　　
　　3) SCHED_RR：這也是一種實(shí)時(shí)進(jìn)程，遵守POSIX1.b標準的RR(循環(huán)round-robin)調度規則。除了時(shí)間片有些不同外，這種策略與SCHED_FIFO類(lèi)似。當SCHED_RR進(jìn)程的時(shí)間片用完后，就被放到SCHED_FIFO和SCHED_RR隊列的末尾。
　　
　　只要系統中有一個(gè)實(shí)時(shí)進(jìn)程在運行，則任何SCHED_OTHER進(jìn)程都不能在任何CPU運行。每個(gè)實(shí)時(shí)進(jìn)程有一個(gè)rt_priority，因此，可以按照rt_priority在所有SCHED_RR進(jìn)程之間分配CPU。其作用與SCHED_OTHER進(jìn)程的priority作用一樣。只有root用戶(hù)能夠用系統調用sched_setscheduler，來(lái)改變當前進(jìn)程的類(lèi)型(sys_nice,sys_setpriority)。
　　此外，內核還定義了SCHED_YIELD，這并不是一種調度策略，而是截取調度策略的一個(gè)附加位。如同前面說(shuō)明的一樣，如果有其他進(jìn)程需要CPU，它就提示調度程序釋放CPU。特別要注意的就是這甚至會(huì )引起實(shí)時(shí)進(jìn)程把CPU釋放給非實(shí)時(shí)進(jìn)程。

　　
　　主要的進(jìn)程調度的函數分析

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

　　
　　goodness()函數分析

　　
　　goodness()函數計算一個(gè)處于可運行狀態(tài)的進(jìn)程值得運行的程度。一個(gè)任務(wù)的goodness是以下因素的函數：正在運行的任務(wù)、想要運行的任務(wù)、當前的CPU。goodness返回下面兩類(lèi)值中的一個(gè)：1000以下或者1000以上。1000或者1000以上的值只能賦給實(shí)時(shí)進(jìn)程，從0到999的值只能賦給普通進(jìn)程。實(shí)際上，在單處理器情況下，普通進(jìn)程的goodness值只使用這個(gè)范圍底部的一部分，從0到41。在SMP情況下，SMP模式會(huì )優(yōu)先照顧等待同一個(gè)處理器的進(jìn)程。不過(guò)，不管是UP還是SMP，實(shí)時(shí)進(jìn)程的goodness值的范圍是從1001到1099。
　　
　　goodness()函數其實(shí)是不會(huì )返回-1000的，也不會(huì )返回其他負值。由于idle進(jìn)程的counter值為負，所以如果使用idle進(jìn)程作為參數調用goodness，就會(huì )返回負值，但這是不會(huì )發(fā)生的。