Linux 內核筆記 – 進程調度
1 前言
2 調度算法
2.1.1 常用概念
2.1.2 進程數據結構中相關內容
2.1.3 調度算法說明
2.1.4 相關函數
3 調度程序的執行
3.1.1 直接調用
3.1.2 延遲調用
3.1.3 相關函數
4 進程調度示意圖
5 SMP系統的調度
6 問題與答案
7 參考文獻：

1 前言
本文的許可協議遵循GNU Free Document License。協議的具體內容請參見http://www.gnu.org/copyleft/fdl.html。在遵循GNU Free Document License的基礎上，可以自由地傳播或發行本文，但請保留本文的完整性。
歡迎大家對這篇文章提出意見和指正，我的email是：shisheng_liu@yahoo.com.cn。

2 調度算法
2.1.1 常用概念
2.1.1.1 定時中斷
通過硬件的可編程中斷控制器8254來實現，定時中斷發生的頻率由HZ定義，發生的時間間隔被稱為tick。
2.1.1.2 CPU節拍（tick）
計算機內部時間的一個計數單位，表示發生一次時鐘中斷的時間間隔。
2.1.1.3 HZ
時鐘中斷發生的頻率。在i386機器上，HZ被定義為100，因此時鐘中斷每10ms一次。
2.1.1.4 CPU時期
調度是以CPU時期為周期的，在一個CPU時期/調度周期內，系統中所有程序都被執行直到用完當前的時間片，然后所有進程的counter值被重新計算，并開始另一個CPU時期。
2.1.1.5 進程的分類
在調度程序看來，系統中的進程分為兩大類，分別是實時進程和普通進程。在任何時候實時進程的執行都高于普通進程。進程數據結構中的policy成 員變量表示了進程是哪一類，而sched_set(/get)scheduler提供了控制進程調度policy的用戶級編程接口。
2.1.2 進程數據結構中相關內容
2.1.2.1 1．nice
進程的優先級，影響進程獲得CPU事件的多少，20為最低，-19為最高。
2.1.2.2 2．counter
進程時間片所剩余的CPU節拍數。初始值根據進程的nice值決定，在每次時鐘中斷發生時，也就是一個CPU節拍（tick）的時候，當前進程的counter值減1，如果counter值變為0則表示當前進程的時間片已經用完，系統會重新調度，決定下一個執行的進程。
2.1.2.3 3．need_resched
標志位。該位在從中斷和系統調用中返回的時候被檢查，need_resched為1的時候表示要求啟動調度程序，這通常發生在進程的時間片已經用完，或者因為IO事件發生而強行搶占當前進程的時候。
2.1.2.4 4．policy
進程的調度策略。如果調度策略為SCHED_RR或者SCHED_FIFO則表示當前進程為實時進程，否則(SCHED_OTHER)為普通進程。
2.1.3 調度算法說明
Linux采用相當簡單但實際證明效果不錯的調度算法。在調度的時候，所有正在運行進程的執行權值(goodness)都被計算，最終權值最高的 進程獲得執行的機會。假設得到的最大權值為0，就認為本次CPU時期已經執行完畢，會重新計算所有進程的counter值，開始新的CPU時期。調度算法 的核心就是goodness的計算，計算的基本思路如下：
如果等待調度的進程是實時進程，它的goodness為1000 + 本身的優先級,而普通進程的goodness遠小于1000，這就保證了實時進程總是優先于普通進程執行。
如果進程剩余的counter為0,就認為它已經用光了自己在該時期的CPU時間片，goodness返回0。
對于其他的情況，用下面的公式來計算goodness:
goodness = counter + 20 – nice；
2.1.4 相關函數
1．schedule() in kernel/sched.c
主調度函數，選擇要運行的進程
2．goodness() in kernel/sched.c
由schedule()調用，計算進程的執行權值
3 調度程序的執行
可以通過兩種方式來激活調度程序，分別是直接調用和延遲調用。
3.1.1 直接調用
當current進程準備主動放棄CPU的時候，它會直接調用調度程序schedule()，將CPU讓給另一個進程。
促使current進程主動放棄CPU的原因有兩種，一種情況是current需要睡眠（阻塞）來等待所需的資源準備好，此時current的狀 態被設置為TASK_INTERRUPTABLE或TASK_UNINTERRUPTABLE，在調用schedule()后進程進入睡眠狀態；另一種情 況下進程設置SCHED_YIELD的調度策略，然后調用schedule()，此時進程只是短暫的放棄CPU，在下一次schedule()被調用的時 候進程會繼續參與CPU的競爭。
3.1.2 延遲調用
通過設置當前進程的need_resched標志來在其后的某個時刻激活調度程序。前面說過，在從中斷/異常/系統調用中返回 時，need_resched標志被檢查，在標志不為0的時候會激活調度程序。例如：當時鐘中斷發生時，中斷處理程序檢查到當前進程的時間片已經執行完 畢，它就會設置當前進程的need_resched標志；另一個例子是當某個IO中斷發生時，中斷處理程序發現有進程在等待該IO事件，它會將正在等待的 進程的狀態變為執行態，并設置當前進程的need_resched標志。當中斷處理程序一結束，系統會重新調度，在這種情況下，新轉入執行態的進程很可能 會獲得執行機會，從而使系統保持對IO事件的快速響應。
3.1.3 相關函數
1．wake_up_common() in kernel/sched.c
激活IO等待隊列中的進程，它會順序調用try_to_wake_up()，reschedule_idle()等函數來要求對進程進程重新調度。
2．do_timer() in kernel/timer.c
定時時鐘中斷程序，減少當前進程的counter值，如果counter已經用完，則設置進程的need_resched域要求重新調度。
3．ret_from_intr/sys_call/exception in arch/i386/entry.S
匯編語言中的程序點，在從中斷/異常/系統調用中返回時都會執行這一段程序，檢查當前進程的need_resched域，如果不為0就會激活schedule()重新調度。


4 進程調度示意圖
linux的進程調度如圖1所示。
 

6 問題與答案
Q．在當前系統下，調度時間片的長度是多少？
A. 與2.2.x版的內核相比，kernel2.4.x的時間片長度縮短了，對于最高優先級的進程來說，時間片的長度為100ms，默認優先級進程的時間片長度為60ms，而最低優先級進程的時間片長度為10ms。

Q. Linux如何保證對I/O事件相對比較快的響應速度，這個響應速度是否與調度時間片的長短有關？
A．當I/O事件發生的是時候，對應的中斷處理程序被激活，當它發現有進程在等待這個I/O事件的時候，它會激活等待進程，并且設置當前正在執行 進程的need_resched標志，這樣在中斷處理程序返回的時候，調度程序被激活，原來在等待I/O事件的進程（很可能）獲得執行權，從而保證了對I /O事件的相對快速響應（毫秒級）。
從上面的說明可以看出，在I/O事件發生的時候，I/O事件的處理進程會搶占當前進程，響應速度與調度時間片的長度無關。

Q．高優先級(nice)進程和低優先級進程在執行上有何區別？例如一個優先級為-19（最高優先級）的進程和優先級為20（最低）的進程有何區別
A. 進程獲得的CPU時間的絕對數目取決于它的初始counter值，初始的counter的計算公式(sched.c in kernel 2.4.14)如下：
p->counter = (p->counter >> 1) + ((20 - p->nice) >> 2) +1)
由公式可以計算出，對于標準進程（p->nice 為0）， 得到的初始counter為6，即進程獲得的時間片為60ms。
最高優先級進程（nice為-19）的初始counter值為10，進程的時間片為100ms。
最低優先級進程（nice為20）的初始counter值為1,進程時間片為10ms。
結論是最高優先級進程會獲得最低優先級進程10倍的執行時間，普通優先級進程接近兩倍的執行時間。當然，這是在進程不進行任何IO操作的時候的數據，在有IO操作的時候，進程會經常被迫睡眠來等待IO操作的完成,真正所占用的CPU時間是很難比較的。
我們可以看到每次重新計算counter的時候，新的counter值都要加上它本身剩余值的一半，這種獎勵只適用于通過SCHED_YIELD 主動放棄CPU的進程，只有它在重新計算的時候counter值沒有用完，所以在計算后counter值會增大，但永遠不可能超過20。

SMP系統中的調度

7 參考文獻：
1． linux內核源代碼版本2.4.14
在任何時候真實的代碼總是提供給我們最準確和詳細的資料。感謝Linus Torvalds，Alan Cox和其它linux開發者的辛勤勞動。
2．DANIEL P.BOVET & MARCO CESATI
<<UNDERSTANDING THE LINUX KERNEL>> ISBN: 0-596-00002-2 O’REILLY 2001
中譯版 《深入理解Linux內核》 陳莉君等譯 ISBN: 7-5083-0719-4 中國電力出版社 2001。
本書是專門介紹linux內核結構的書中最詳盡的一本，對代碼分析講解的也比較深入，基于2.2的內核版本
3．W.Richard Stevens
《UNIX環境高級編程》 尤晉元譯 ISBN: 7-111-07579-X 機械工業出版社 2000
UNIX編程圣經，程序員手頭必備的書籍之一,對所有UNIX開發人員，無論水平高低，都有參考價值。翻譯的水準也難得一見的高明。

from:
http://www.linuxforum.net/forum/gshowflat.php?Cat=&Board=linuxK&Number=294463&page=16&view=collapsed&sb=5&o=all&fpart=