Linux 內(nèi)核筆記 – 進(jìn)程調(diào)度
1 前言
2 調(diào)度算法
2.1.1 常用概念
2.1.2 進(jìn)程數(shù)據(jù)結(jié)構(gòu)中相關(guān)內(nèi)容
2.1.3 調(diào)度算法說(shuō)明
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 進(jìn)程調(diào)度示意圖
5 SMP系統(tǒng)的調(diào)度
6 問題與答案
7 參考文獻(xiàn)：

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

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


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

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

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

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

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

7 參考文獻(xiàn)：
1． linux內(nèi)核源代碼版本2.4.14
在任何時(shí)候真實(shí)的代碼總是提供給我們最準(zhǔn)確和詳細(xì)的資料。感謝Linus Torvalds，Alan Cox和其它linux開發(fā)者的辛勤勞動(dòng)。
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 中國(guó)電力出版社 2001。
本書是專門介紹linux內(nèi)核結(jié)構(gòu)的書中最詳盡的一本，對(duì)代碼分析講解的也比較深入，基于2.2的內(nèi)核版本
3．W.Richard Stevens
《UNIX環(huán)境高級(jí)編程》 尤晉元譯 ISBN: 7-111-07579-X 機(jī)械工業(yè)出版社 2000
UNIX編程圣經(jīng)，程序員手頭必備的書籍之一,對(duì)所有UNIX開發(fā)人員，無(wú)論水平高低，都有參考價(jià)值。翻譯的水準(zhǔn)也難得一見的高明。

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