Linux進程調度的原理解析

進程調度依據
　　調度程序運行時，要在所有可運行狀態的進程中選擇最值得運行的進程投入運行。選擇進程的依據是什么呢？在每個進程的task_strUCt結構中有以下四項：policy、priority、counter、rt_priority。這四項是選擇進程的依據。 其中，policy是進程的調度策略，用來區分實時進程和普通進程，實時進程優先于普通進程運行；priority是進程（包括實時和普通）的靜態優先級；counter是進程剩余的時間片，它的起始值就是priority的值；由于counter在后面計算一個處于可運行狀態的進程值得運行的程度goodness時起重要作用，因此，counter也可以看作是進程的動態優先級。rt_priority是實時進程特有的，用于實時進程間的選擇。
　　Linux用函數goodness（）來衡量一個處于可運行狀態的進程值得運行的程度。該函數綜合了以上提到的四項，還結合了一些其他的因素，給每個處于可運行狀態的進程賦予一個權值（weight），調度程序以這個權值作為選擇進程的唯一依據。關于goodness（）的情況在后面將會詳細分析。
　　進程調度策略
　　調度程序運行時，要在所有處于可運行狀態的進程之中選擇最值得運行的進程投入運行。選擇進程的依據是什么呢？在每個進程的task_struct 結構中有這么四項：
　　policy， priority ， counter， rt_priority
　　這四項就是調度程序選擇進程的依據。其中，policy是進程的調度策略，用來區分兩種進程-實時和普通；priority是進程（實時和普通）的優先級；counter 是進程剩余的時間片，它的大小完全由priority決定;rt_priority是實時優先級，這是實時進程所特有的，用于實時進程間的選擇。
　　首先，Linux 根據policy從整體上區分實時進程和普通進程，因為實時進程和普通進程度調度是不同的，它們兩者之間，實時進程應該先于普通進程而運行，然后，對于同一類型的不同進程，采用不同的標準來選擇進程：
　　對于普通進程，Linux采用動態優先調度，選擇進程的依據就是進程counter的大小。進程創建時，優先級priority被賦一個初值，一般為0～70之間的數字，這個數字同時也是計數器counter的初值，就是說進程創建時兩者是相等的。字面上看，priority是\“優先級\”、counter是\“計數器\”的意思，然而實際上，它們表達的是同一個意思-進程的\“時間片\”。Priority代表分配給該進程的時間片，counter表示該進程剩余的時間片。在進程運行過程中，counter不斷減少，而priority保持不變，以便在counter變為0的時候（該進程用完了所分配的時間片）對counter重新賦值。當一個普通進程的時間片用完以后，并不馬上用priority對counter進行賦值，只有所有處于可運行狀態的普通進程的時間片（p-》counter==0）都用完了以后，才用priority對counter重新賦值，這個普通進程才有了再次被調度的機會。這說明，普通進程運行過程中，counter的減小給了其它進程得以運行的機會，直至counter減為0時才完全放棄對CPU的使用，這就相對于優先級在動態變化，所以稱之為動態優先調度。至于時間片這個概念，和其他不同操作系統一樣的，Linux的時間單位也是\“時鐘滴答\”，只是不同操作系統對一個時鐘滴答的定義不同而已（Linux為10ms）。進程的時間片就是指多少個時鐘滴答，比如，若priority為20，則分配給該進程的時間片就為20個時鐘滴答，也就是20*10ms=200ms。Linux中某個進程的調度策略（policy）、優先級（priority）等可以作為參數由用戶自己決定，具有相當的靈活性。內核創建新進程時分配給進程的時間片缺省為200ms（更準確的，應為210ms），用戶可以通過系統調用改變它。
　　對于實時進程，Linux采用了兩種調度策略，即FIFO（先來先服務調度）和RR（時間片輪轉調度）。因為實時進程具有一定程度的緊迫性，所以衡量一個實時進程是否應該運行，Linux采用了一個比較固定的標準。實時進程的counter只是用來表示該進程的剩余時間片，并不作為衡量它是否值得運行的標準。實時進程的counter只是用來表示該進程的剩余時間片，并不作為衡量它是否值得運行的標準，這和普通進程是有區別的。上面已經看到，每個進程有兩個優先級，實時優先級就是用來衡量實時進程是否值得運行的。
　　這一切看來比較麻煩，但實際上Linux中的實現相當簡單。Linux用函數goodness（）來衡量一個處于可運行狀態的進程值得運行的程度。該函數綜合了上面提到的各個方面，給每個處于可運行狀態的進程賦予一個權值（weight），調度程序以這個權值作為選擇進程的唯一依據。
　　Linux根據policy的值將進程總體上分為實時進程和普通進程，提供了三種調度算法：一種傳統的Unix調度程序和兩個由POSIX.1b（原名為POSIX.4）操作系統標準所規定的\“實時\”調度程序。但這種實時只是軟實時，不滿足諸如中斷等待時間等硬實時要求，只是保證了當實時進程需要時一定只把CPU分配給實時進程。
　　非實時進程有兩種優先級，一種是靜態優先級，另一種是動態優先級。實時進程又增加了第三種優先級，實時優先級。優先級是一些簡單的整數，為了決定應該允許哪一個進程使用CPU的資源，用優先級代表相對權值-優先級越高，它得到CPU時間的機會也就越大。
　　靜態優先級（priority）-不隨時間而改變，只能由用戶進行修改。它指明了在被迫和其他進程競爭CPU之前，該進程所應該被允許的時間片的最大值（但很可能的，在該時間片耗盡之前，進程就被迫交出了CPU）。
　　動態優先級（counter）-只要進程擁有CPU，它就隨著時間不斷減??；當它小于0時，標記進程重新調度。它指明了在這個時間片中所剩余的時間量。
　　實時優先級（rt_priority）-指明這個進程自動把CPU交給哪一個其他進程；較高權值的進程總是優先于較低權值的進程。如果一個進程不是實時進程，其優先級就是0，所以實時進程總是優先于非實時進程的（但實際上，實時進程也會主動放棄CPU）。
　　當policy分別為以下值時：
　　1） SCHED_OTHER：這是普通的用戶進程，進程的缺省類型，采用動態優先調度策略，選擇進程的依據主要是根據進程goodness值的大小。這種進程在運行時，可以被高goodness值的進程搶先。
　　2） SCHED_FIFO：這是一種實時進程，遵守POSIX1.b標準的FIFO（先入先出）調度規則。它會一直運行，直到有一個進程因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個具有更高rt_priority的實時進程搶先。在Linux實現中，SCHED_FIFO進程仍然擁有時間片-只有當時間片用完時它們才被迫釋放CPU。因此，如同POSIX1.b一樣，這樣的進程就象沒有時間片（不是采用分時）一樣運行。Linux中進程仍然保持對其時間片的記錄（不修改counter）主要是為了實現的方便，同時避免在調度代碼的關鍵路徑上出現條件判斷語句 if （?。╟urrent-》policy&SCHED_FIFO））{。..}-要知道，其他大量非FIFO進程都需要記錄時間片，這種多余的檢測只會浪費CPU資源。（一種優化措施，不該將執行時間占10%的代碼的運行時間減少到50%；而是將執行時間占90%的代碼的運行時間減少到95%。0.9+0.1*0.5=0.95》0.1+0.9*0.9=0.91）
　　3） SCHED_RR：這也是一種實時進程，遵守POSIX1.b標準的RR（循環round-robin）調度規則。除了時間片有些不同外，這種策略與SCHED_FIFO類似。當SCHED_RR進程的時間片用完后，就被放到SCHED_FIFO和SCHED_RR隊列的末尾。
　　只要系統中有一個實時進程在運行，則任何SCHED_OTHER進程都不能在任何CPU運行。每個實時進程有一個rt_priority，因此，可以按照rt_priority在所有SCHED_RR進程之間分配CPU。其作用與SCHED_OTHER進程的priority作用一樣。只有root用戶能夠用系統調用sched_setscheduler，來改變當前進程的類型（sys_nice，sys_setpriority）。
　　此外，內核還定義了SCHED_YIELD，這并不是一種調度策略，而是截取調度策略的一個附加位。如同前面說明的一樣，如果有其他進程需要CPU，它就提示調度程序釋放CPU。特別要注意的就是這甚至會引起實時進程把CPU釋放給非實時進程。
　　主要的進程調度的函數分析
　　真正執行調度的函數是schedule（void），它選擇一個最合適的進程執行，并且真正進行上下文切換，使得選中的進程得以執行。而reschedule_idle（struct task_struct *p）的作用是為進程選擇一個合適的CPU來執行，如果它選中了某個CPU，則將該CPU上當前運行進程的need_resched標志置為1，然后向它發出一個重新調度的處理機間中斷，使得選中的CPU能夠在中斷處理返回時執行schedule函數，真正調度進程p在CPU上執行。在schedule（）和reschedule_idle（）中調用了goodness（）函數。goodness（）函數用來衡量一個處于可運行狀態的進程值得運行的程度。此外，在schedule（）函數中還調用了schedule_tail（）函數;在reschedule_idle（）函數中還調用了reschedule_idle_slow（）。這些函數的實現對理解SMP的調度非常重要，下面一一分析這些函數。先給出每個函數的主要流程圖，然后給出源代碼，并加注釋。
　　goodness（）函數分析
　　goodness（）函數計算一個處于可運行狀態的進程值得運行的程度。一個任務的goodness是以下因素的函數：正在運行的任務、想要運行的任務、當前的CPU。goodness返回下面兩類值中的一個：1000以下或者1000以上。1000或者1000以上的值只能賦給\“實時\”進程，從0到999的值只能賦給普通進程。實際上，在單處理器情況下，普通進程的goodness值只使用這個范圍底部的一部分，從0到41。在SMP情況下，SMP模式會優先照顧等待同一個處理器的進程。不過，不管是UP還是SMP，實時進程的goodness值的范圍是從1001到1099。
　　goodness（）函數其實是不會返回-1000的，也不會返回其他負值。由于idle進程的counter值為負，所以如果使用idle進程作為參數調用goodness，就會返回負值，但這是不會發生的。
?