Linux 內(nèi)核筆記 – 進程調(diào)度
1 前言
2 調(diào)度算法
2.1.1 常用概念
2.1.2 進程數(shù)據(jù)結(jié)構(gòu)中相關(guān)內(nèi)容
2.1.3 調(diào)度算法說明
2.1.4 相關(guān)函數(shù)
3 調(diào)度程序的執(zhí)行
3.1.1 直接調(diào)用
3.1.2 延遲調(diào)用
3.1.3 相關(guān)函數(shù)
4 進程調(diào)度示意圖
5 SMP系統(tǒng)的調(diào)度
6 問題與答案
7 參考文獻：

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

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


4 進程調(diào)度示意圖
linux的進程調(diào)度如圖1所示。
 

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

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

Q．高優(yōu)先級(nice)進程和低優(yōu)先級進程在執(zhí)行上有何區(qū)別？例如一個優(yōu)先級為-19（最高優(yōu)先級）的進程和優(yōu)先級為20（最低）的進程有何區(qū)別
A. 進程獲得的CPU時間的絕對數(shù)目取決于它的初始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。
最高優(yōu)先級進程（nice為-19）的初始counter值為10，進程的時間片為100ms。
最低優(yōu)先級進程（nice為20）的初始counter值為1,進程時間片為10ms。
結(jié)論是最高優(yōu)先級進程會獲得最低優(yōu)先級進程10倍的執(zhí)行時間，普通優(yōu)先級進程接近兩倍的執(zhí)行時間。當然，這是在進程不進行任何IO操作的時候的數(shù)據(jù)，在有IO操作的時候，進程會經(jīng)常被迫睡眠來等待IO操作的完成,真正所占用的CPU時間是很難比較的。
我們可以看到每次重新計算counter的時候，新的counter值都要加上它本身剩余值的一半，這種獎勵只適用于通過SCHED_YIELD 主動放棄CPU的進程，只有它在重新計算的時候counter值沒有用完，所以在計算后counter值會增大，但永遠不可能超過20。

SMP系統(tǒng)中的調(diào)度

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

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