作者簡(jiǎn)介：

程磊，一線碼農(nóng)，在某手機(jī)公司擔(dān)任系統(tǒng)開發(fā)工程師，日常喜歡研究?jī)?nèi)核基本原理。

目錄

一、進(jìn)程調(diào)度概覽

二、進(jìn)程調(diào)度框架

三、SMP管理

四、基本分時(shí)調(diào)度

五、總結(jié)回顧

一、進(jìn)程調(diào)度概覽

進(jìn)程調(diào)度是操作系統(tǒng)最重要的內(nèi)容之一，也是學(xué)習(xí)操作系統(tǒng)的重點(diǎn)和難點(diǎn)。關(guān)于進(jìn)程調(diào)度，我們首先就會(huì)問出一些問題，什么是進(jìn)程調(diào)度，為什么要進(jìn)程調(diào)度，如何進(jìn)行調(diào)度。下面我們用一幅圖把這些問題關(guān)聯(lián)起來：

這張圖把進(jìn)程調(diào)度的所有問題和知識(shí)點(diǎn)都關(guān)聯(lián)了起來，本文后面所有的內(nèi)容都是對(duì)這張圖的解釋和擴(kuò)展延伸，下面讓我們來一一講解。

1.1 什么是調(diào)度

什么是調(diào)度？調(diào)度是CPU資源管理器。操作系統(tǒng)的作用之一就是系統(tǒng)資源管理器。CPU是計(jì)算機(jī)系統(tǒng)中最重要的資源，當(dāng)然也要管理。所有進(jìn)程的運(yùn)行都需要CPU，對(duì)CPU該如何管理呢？對(duì)于直接共享型的事物，我們有兩種管理方法：一種是時(shí)間分割管理，另一種是空間分割管理。由于CPU自身的特性，沒有空間分割相似性，只有時(shí)間分割相似性，所以我們只能對(duì)CPU進(jìn)行時(shí)間分割管理。對(duì)CPU進(jìn)行時(shí)間分割管理的具體做法就叫做進(jìn)程調(diào)度。

那么調(diào)度的是什么呢？進(jìn)程調(diào)度，調(diào)度的當(dāng)然是進(jìn)程啦，也對(duì)也不對(duì)。我們知道進(jìn)程是資源分配的單位，線程是執(zhí)行的單位。早期的時(shí)候沒有多線程，進(jìn)程就是線程，線程就是進(jìn)程，所以此時(shí)進(jìn)程調(diào)度調(diào)度的是進(jìn)程。但是當(dāng)有了多線程之后，線程變成了執(zhí)行的單位，進(jìn)程不再是執(zhí)行的單位，進(jìn)程調(diào)度調(diào)度的就是線程了。不過由于歷史原因，大家都習(xí)慣叫進(jìn)程調(diào)度，所以現(xiàn)在這個(gè)領(lǐng)域的名稱還是叫進(jìn)程調(diào)度。后文中說到調(diào)度進(jìn)程的地方都是調(diào)度的線程，由于習(xí)慣問題，我們還說調(diào)度進(jìn)程不說調(diào)度線程，請(qǐng)大家要注意。

對(duì)線程的調(diào)度可以有兩種方式：一種是直接調(diào)度線程，不考慮它們所屬的進(jìn)程，這種方式叫做直接調(diào)度或者一級(jí)調(diào)度；另一種是先調(diào)度進(jìn)程，再在進(jìn)程內(nèi)部調(diào)度線程，這種方式叫做間接調(diào)度或者二級(jí)調(diào)度。POSIX規(guī)定，操作系統(tǒng)可以選擇這兩種方式中的任何一種都行。Linux選擇的是一級(jí)調(diào)度，為什么會(huì)這么選擇呢？主要是為了提高進(jìn)程的并發(fā)性，充分利用多CPU多核的優(yōu)勢(shì)。如果使用二級(jí)調(diào)度的話，看似每個(gè)進(jìn)程之間都公平了，但是有些進(jìn)程的計(jì)算量比較大，就無法通過多開線程提高自己的性能，這樣對(duì)系統(tǒng)整體的性能是有害的，也不利用發(fā)揮計(jì)算機(jī)多CPU的優(yōu)勢(shì)。一級(jí)調(diào)度看似對(duì)有些進(jìn)程不公平，但是計(jì)算量小的進(jìn)程少開線程，計(jì)算量大的進(jìn)程多開線程，相對(duì)還是很公平的。

就像國(guó)家希望每個(gè)企業(yè)都做大做強(qiáng)，但是同時(shí)也會(huì)反壟斷一樣。Linux也推出了cgroup組調(diào)度機(jī)制，來限制某個(gè)或者某一類進(jìn)程對(duì)CPU資源的過度占用。本文中不講cgroup組調(diào)度機(jī)制，后文的講解都是假設(shè)沒有cgroup組調(diào)度。

1.2 為什么要調(diào)度

我們知道了什么是調(diào)度，那么為什么要調(diào)度呢，沒有調(diào)度會(huì)怎么樣呢？最早的計(jì)算機(jī)是沒有調(diào)度的，程序只能一個(gè)一個(gè)地運(yùn)行，一個(gè)進(jìn)程死亡之后才能去運(yùn)行下一個(gè)進(jìn)程。這里面首先存在的問題就是我們沒法同時(shí)運(yùn)行多個(gè)進(jìn)程。其次就算我們不需要同時(shí)運(yùn)行多個(gè)進(jìn)程，程序在運(yùn)行的過程中如果要等IO，CPU就只能空轉(zhuǎn)，這也十分浪費(fèi)CPU資源。于是最早的多任務(wù)——協(xié)作式多任務(wù)誕生了，當(dāng)程序由于要等IO而阻塞時(shí)就會(huì)去調(diào)度執(zhí)行其它的進(jìn)程。但是協(xié)作式多任務(wù)存在著很大的問題，就是每個(gè)進(jìn)程運(yùn)行的時(shí)間片長(zhǎng)短是不確定的，而且是很偶然很隨機(jī)的。如果一個(gè)進(jìn)程它一直在做運(yùn)算就是不進(jìn)行IO操作，那么它就會(huì)一直霸占CPU。針對(duì)這個(gè)問題，當(dāng)時(shí)想出的方法是道德解決方案。內(nèi)核向進(jìn)程提供系統(tǒng)調(diào)用sched_yield，它會(huì)使進(jìn)程主動(dòng)放棄CPU讓其它進(jìn)程來執(zhí)行。然后要求所有的程序員在程序中合適的地方盡量多地加入sched_yield調(diào)用。這個(gè)方法在當(dāng)時(shí)是管用的，因?yàn)楫?dāng)時(shí)計(jì)算機(jī)的使用者(同時(shí)也是程序員)僅限于少數(shù)科研機(jī)構(gòu)和政府機(jī)關(guān)的部分人員，一臺(tái)電腦的共同使用者都認(rèn)識(shí)，面子上還得過得去。

后來隨著計(jì)算機(jī)的普及，以及計(jì)算機(jī)的使用者和程序員這兩個(gè)角色的分離，主要靠道德約束的協(xié)作式多任務(wù)已經(jīng)行不通了，我們需要強(qiáng)制性多任務(wù)，也就是搶占式多任務(wù)。搶占式多任務(wù)使得每個(gè)進(jìn)程都可以相對(duì)公平地平分CPU時(shí)間，如果一個(gè)進(jìn)程運(yùn)行了過長(zhǎng)的時(shí)間就會(huì)被強(qiáng)制性地調(diào)度出去，不管這個(gè)進(jìn)程是否愿意。有了搶占式多任務(wù)，我們?cè)诤暧^上不僅可以同時(shí)運(yùn)行多個(gè)進(jìn)程，而且它們會(huì)一起齊頭并進(jìn)地往前運(yùn)行，不會(huì)出現(xiàn)某個(gè)進(jìn)程被餓死的情況，這樣我們使用電腦的體驗(yàn)就非常完美了。搶占式多任務(wù)和協(xié)作式多任務(wù)不是對(duì)立的，它們是相互獨(dú)立的，可以同時(shí)存在于系統(tǒng)中。

搶占又分為用戶搶占和內(nèi)核搶占。由于搶占對(duì)進(jìn)程來說是異步的，進(jìn)程被搶占時(shí)不一定運(yùn)行在什么地方，有可能運(yùn)行在用戶空間，也有可能運(yùn)行在內(nèi)核空間(進(jìn)程通過系統(tǒng)調(diào)用進(jìn)入內(nèi)核空間)。如果搶占點(diǎn)是在用戶空間，那么搶占就是安全的，如果在內(nèi)核空間就不一定安全，這是為什么呢？因?yàn)閷?duì)于用戶空間來說，如果搶占會(huì)導(dǎo)致線程同步問題，那么用戶空間有責(zé)任使用線程同步機(jī)制來保護(hù)臨界區(qū)，只要用戶空間做好同步就不會(huì)出問題。如果內(nèi)核也做好了同步措施，內(nèi)核搶占也不會(huì)出問題，但是內(nèi)核最初的設(shè)計(jì)就沒有考慮內(nèi)核搶占問題，所以剛開始的時(shí)候內(nèi)核是不能搶占的。后來內(nèi)核開發(fā)者對(duì)內(nèi)核進(jìn)行了完善，把內(nèi)核所有的臨界區(qū)都加上了同步措施，然后內(nèi)核就是可搶占的了。內(nèi)核能搶占了不代表內(nèi)核一定會(huì)搶占，內(nèi)核會(huì)不會(huì)搶占由config選項(xiàng)控制，可以開啟也可以關(guān)閉，因?yàn)閮?nèi)核搶占還會(huì)影響系統(tǒng)的響應(yīng)性和性能。開啟內(nèi)核搶占會(huì)提高系統(tǒng)的響應(yīng)性但是會(huì)降低一點(diǎn)性能，關(guān)閉內(nèi)核搶占會(huì)降低系統(tǒng)的響應(yīng)性但是會(huì)提高一點(diǎn)性能。因此把內(nèi)核搶占做成配置項(xiàng)，可以讓大家靈活配置。服務(wù)器系統(tǒng)一般不需要與用戶交互，所以會(huì)關(guān)閉內(nèi)核搶占來提高性能，桌面系統(tǒng)會(huì)開啟內(nèi)核搶占來提高系統(tǒng)的響應(yīng)性，來增加用戶體驗(yàn)。

現(xiàn)在我們?cè)賮砜匆幌聻槭裁匆{(diào)度。因?yàn)槿绻麤]有調(diào)度的話，就不能實(shí)現(xiàn)多任務(wù)，一次就只能運(yùn)行一個(gè)程序，我們使用電腦的體驗(yàn)就會(huì)大大降低。有了調(diào)度就有了多任務(wù)，我們就能同時(shí)在電腦上做很多事情，使用體驗(yàn)就會(huì)非常好。

1.3 為什么能調(diào)度

我們?cè)賮砜纯礊槭裁茨苷{(diào)度呢。我們把協(xié)作式多任務(wù)叫做主動(dòng)調(diào)度，搶占式多任務(wù)叫做被動(dòng)調(diào)度。為什么能調(diào)度分為兩部分：為什么能觸發(fā)調(diào)度和為什么能執(zhí)行調(diào)度。對(duì)于主動(dòng)調(diào)度，調(diào)度是進(jìn)程主動(dòng)觸發(fā)的，這個(gè)是肯定能的。對(duì)于被動(dòng)調(diào)度，在圖靈機(jī)模型中是做不到的，因?yàn)閳D靈機(jī)是一條線性一直往前走的，進(jìn)程在執(zhí)行時(shí)，進(jìn)程要是不主動(dòng)，是不可能跳到其它進(jìn)程來執(zhí)行的。被動(dòng)調(diào)度能做到的原因關(guān)鍵就在于中斷機(jī)制，因?yàn)橹袛嗍菑?qiáng)行在正常的執(zhí)行流中插入了一段代碼，它能改變后續(xù)代碼的走向。有了中斷機(jī)制，我們就可以創(chuàng)建一個(gè)定時(shí)器中斷，以固定的時(shí)間間隔比如每10ms來觸發(fā)中斷，檢測(cè)進(jìn)程是否運(yùn)行時(shí)間過長(zhǎng)，如果過長(zhǎng)就觸發(fā)調(diào)度。這樣任何進(jìn)程都不可能霸占CPU，所以進(jìn)程都能公平地共享CPU時(shí)間。這里引用其中的一幅圖來看一下：

可以看到在純圖靈機(jī)模型中，進(jìn)程如果不主動(dòng)進(jìn)行調(diào)度，是沒有外力強(qiáng)迫進(jìn)程進(jìn)行調(diào)度的，進(jìn)程就能一直霸占CPU。有了中斷機(jī)制之后，在中斷的處理中可以觸發(fā)調(diào)度，在中斷返回的點(diǎn)可以執(zhí)行調(diào)度，這樣就可以避免進(jìn)程霸占CPU了。

前面說的是為何能觸發(fā)進(jìn)程調(diào)度，主動(dòng)調(diào)度是進(jìn)程自己觸發(fā)的，被動(dòng)調(diào)度是在中斷中觸發(fā)的?，F(xiàn)在來看看為何能執(zhí)行調(diào)度，執(zhí)行調(diào)度包括兩部分：選擇進(jìn)程和切換進(jìn)程。選擇進(jìn)程是純軟件的，肯定能實(shí)現(xiàn)。切換進(jìn)程是怎么切換呢？一個(gè)進(jìn)程執(zhí)行的好好的，怎么就切換了呢，需不需要硬件的支持呢？進(jìn)程切換主要是切換執(zhí)行棧和用戶空間，這兩個(gè)都需要用到CPU特定的指令。進(jìn)程切換的具體原理和細(xì)節(jié)我們?cè)?.7節(jié)中講。

1.4 何時(shí)調(diào)度

我們前面已經(jīng)講了主動(dòng)調(diào)度(協(xié)作式多任務(wù))和被動(dòng)調(diào)度(搶占式多任務(wù))。

對(duì)于主動(dòng)調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是同步的、一體的，觸發(fā)即執(zhí)行。主動(dòng)調(diào)度發(fā)生的時(shí)機(jī)有IO等待、加鎖失敗等各種阻塞操作以及用戶空間主動(dòng)調(diào)用sched_yield。

對(duì)于被動(dòng)調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是異步的、分離的，觸發(fā)調(diào)度并不會(huì)立馬執(zhí)行調(diào)度，而是做個(gè)需要調(diào)度的標(biāo)記，然后在之后的某個(gè)合適的地方會(huì)檢測(cè)這個(gè)標(biāo)記，如果被設(shè)置就進(jìn)行調(diào)度。觸發(fā)調(diào)度的點(diǎn)有：在定時(shí)器中斷中發(fā)現(xiàn)當(dāng)前進(jìn)程超時(shí)了，在喚醒進(jìn)程時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程，在遷移進(jìn)程時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程，在改變進(jìn)程優(yōu)先級(jí)時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程。其中第一個(gè)觸發(fā)點(diǎn)是當(dāng)前進(jìn)程需要被搶占，它是用來保證公平調(diào)度，防止進(jìn)程霸占CPU的，后三個(gè)觸發(fā)點(diǎn)是新進(jìn)程需要搶占當(dāng)前進(jìn)程，它是用來提高系統(tǒng)響應(yīng)性的。執(zhí)行調(diào)度的點(diǎn)有：系統(tǒng)調(diào)用完成之后即將返回用戶空間，中斷完成之后即將返回用戶空間，如果開啟了內(nèi)核搶占的話則還有,中斷完成之后即將返回內(nèi)核,如果中斷發(fā)生在禁止搶占臨界區(qū)中，那么中斷完成之后返回內(nèi)核是不會(huì)執(zhí)行調(diào)度的，而是會(huì)在臨界區(qū)結(jié)束的時(shí)候執(zhí)行調(diào)度。下面我們借用《深入理解Linux中斷機(jī)制》中的幾個(gè)圖來看一下這幾個(gè)執(zhí)行調(diào)度檢測(cè)點(diǎn)：

系統(tǒng)調(diào)用完成之后即將返回用戶空間和中斷完成之后即將返回用戶空間，是非常好的執(zhí)行進(jìn)行調(diào)度的點(diǎn)，也就是此圖中的三個(gè)箭頭的地方。CPU異常在意義上不是系統(tǒng)調(diào)用，但是在形式上和邏輯上相當(dāng)于是系統(tǒng)調(diào)用。

中斷發(fā)生在內(nèi)核空間的場(chǎng)景，如果開啟了內(nèi)核搶占，如果被搶占的內(nèi)核代碼不是在禁用搶占臨界區(qū)，中斷返回時(shí)是執(zhí)行調(diào)度的點(diǎn)。如果被搶占的內(nèi)核代碼在禁用搶占臨界區(qū)中，在執(zhí)行調(diào)度的點(diǎn)被推遲到了臨界區(qū)的出口處。

1.5 如何調(diào)度

現(xiàn)在到了執(zhí)行調(diào)度的時(shí)刻了。執(zhí)行調(diào)度分為兩步：一是選擇下一個(gè)要執(zhí)行的進(jìn)程，二是切換進(jìn)程。選擇下一個(gè)要執(zhí)行的進(jìn)程，這就是調(diào)度算法了。首先調(diào)度算法只能從Runnable的進(jìn)程中進(jìn)行選擇，不能選擇Blocked進(jìn)程，因?yàn)檫x擇了也沒有意義。其次算法還要區(qū)分進(jìn)程類型，比如普通進(jìn)程與實(shí)時(shí)進(jìn)程，肯定要優(yōu)先選擇實(shí)時(shí)進(jìn)程，在同一類型的進(jìn)程中還要有具體的算法來決定到底選擇哪個(gè)進(jìn)程。在Linux中一共把進(jìn)程分為了5類，每一類都有一個(gè)具體的算法。類之間的關(guān)系是優(yōu)先選擇高類的進(jìn)程，只有當(dāng)高類沒有Runnable進(jìn)程時(shí)才會(huì)去選擇低類進(jìn)程。

進(jìn)程選擇好了之后就要切換進(jìn)程了。切換進(jìn)程分兩步：第一步是切換用戶空間，第二步是切換執(zhí)行棧(線程棧)。如果要切換的兩個(gè)線程屬于同一個(gè)進(jìn)程就不需要切換用戶空間了。切換用戶空間是一個(gè)CPU架構(gòu)相關(guān)的事情，在x86 CPU上是給CR3寄存器賦值新進(jìn)程的頁表樹的根指針。此時(shí)切換的執(zhí)行棧是線程的內(nèi)核棧，執(zhí)行棧代表的是當(dāng)前線程的執(zhí)行情況，切換執(zhí)行棧就是切換線程。線程的用戶棧信息都在內(nèi)核棧里保存著。切換完內(nèi)核棧之后，線程繼續(xù)執(zhí)行就會(huì)返回用戶空間，由于此時(shí)用戶空間已經(jīng)切換完成，內(nèi)核棧上也保存著用戶棧的信息，所以線程能返回到正確的用戶空間線程上去。

下面我們畫個(gè)圖來看一下：

對(duì)于一個(gè)CPU來說，永遠(yuǎn)只有一個(gè)當(dāng)前進(jìn)程在運(yùn)行，當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí)，需要從其它進(jìn)程中選擇一個(gè)進(jìn)程，把它旋轉(zhuǎn)到最下方作為當(dāng)前進(jìn)程，它就開始運(yùn)行了。

1.6 調(diào)度均衡

前面所說的都是針對(duì)一個(gè)CPU的情況，對(duì)于多個(gè)CPU來說，每個(gè)CPU也是這樣的邏輯。但是有一點(diǎn)不同的是，如果一個(gè)系統(tǒng)上的多個(gè)CPU忙的忙死閑的閑死，顯然不太好，因此多個(gè)CPU之間會(huì)進(jìn)行調(diào)度均衡。調(diào)度均衡可以分為個(gè)體均衡和總體均衡。個(gè)體均衡是從進(jìn)程的角度出發(fā)選擇到一個(gè)相對(duì)清閑的CPU上去運(yùn)行?？傮w均衡是從CPU的角度出發(fā)如何從別的CPU上拉取一些進(jìn)程到自己這來執(zhí)行，使得所有CPU的工作量盡量平均。個(gè)體均衡的觸發(fā)點(diǎn)有三個(gè)：一是新進(jìn)程剛創(chuàng)建時(shí)，二是進(jìn)程要執(zhí)行新程序時(shí)，三是進(jìn)程被喚醒時(shí)，在這三個(gè)點(diǎn)進(jìn)程都可以選擇去哪個(gè)CPU的運(yùn)行隊(duì)列上去等待執(zhí)行。在個(gè)體均衡下，每個(gè)進(jìn)程都盡量選擇相對(duì)清閑的CPU，所以所有CPU的負(fù)載應(yīng)該還是會(huì)比較均衡的。但是時(shí)間長(zhǎng)了可能還是會(huì)出現(xiàn)負(fù)載不均衡的情況，此時(shí)就要進(jìn)行總體均衡了。總體均衡的觸發(fā)點(diǎn)有三個(gè)：一是CPU即將idle前會(huì)去找到最忙的CPU然后拉取一些任務(wù)過來；二是定時(shí)器中斷的周期性檢測(cè)，會(huì)檢查是否所有的CPU都一樣忙，如果忙閑差別太大就會(huì)進(jìn)行進(jìn)程遷移，使得所有CPU忙閑程度接近；三是在idle進(jìn)程中如果CPU發(fā)現(xiàn)自己太忙而有的CPU在idle就會(huì)喚醒那個(gè)CPU進(jìn)行負(fù)載均衡。

1.7 調(diào)度器評(píng)價(jià)

狹義的調(diào)度器指的是具體的調(diào)度算法，廣義的調(diào)度器指的是整個(gè)調(diào)度體系。不過兩者的評(píng)價(jià)指標(biāo)是相同的，所以我們這里不具體區(qū)分調(diào)度器是指調(diào)度算法還是調(diào)度體系。調(diào)度器的評(píng)價(jià)指標(biāo)有以下幾個(gè)：

1.響應(yīng)性，當(dāng)一個(gè)進(jìn)程發(fā)生事件需要去處理的時(shí)候能否及時(shí)被調(diào)度。這一點(diǎn)和使用體驗(yàn)是密切相關(guān)的，當(dāng)我們用鼠標(biāo)點(diǎn)擊一個(gè)程序的時(shí)候，肯定希望程序立即能做出響應(yīng)，如果程序過了好幾秒才有反應(yīng)，那我們肯定會(huì)很煩的。

2.吞吐量，系統(tǒng)在相同的時(shí)間內(nèi)能夠運(yùn)行更多的程序、執(zhí)行更多的指令。這個(gè)首先要求調(diào)度器本身的代碼要盡量的高效。如果調(diào)度器寫得非常復(fù)雜，運(yùn)行一次就需要好幾毫秒的話，那留給進(jìn)程運(yùn)行的時(shí)間就不多了。其次進(jìn)程調(diào)度的頻率要低，如果進(jìn)程調(diào)度的頻率比較高的話，那調(diào)度器執(zhí)行的次數(shù)就比較多，從而占用了較多的CPU時(shí)間，而且頻繁切換進(jìn)程也會(huì)影響緩存的性能。從這一點(diǎn)來看響應(yīng)性和吞吐量是有矛盾的，提高響應(yīng)性會(huì)增加進(jìn)程切換的頻率，而這會(huì)降低系統(tǒng)的吞吐量。

3.公平性，指的是相對(duì)公平性，每個(gè)進(jìn)程實(shí)際獲得的時(shí)間份額與應(yīng)當(dāng)獲得的時(shí)間份額都相差不大。不會(huì)出現(xiàn)有些進(jìn)程饑餓的情況，也不會(huì)出現(xiàn)有些進(jìn)程獲得過多時(shí)間份額的情況。

4.適應(yīng)性，指的是系統(tǒng)無論是調(diào)度幾個(gè)進(jìn)程還是調(diào)度幾萬個(gè)進(jìn)程，都能撐得住，都能收放自如，各項(xiàng)指標(biāo)都不能受到太大的影響。

5.節(jié)能性，自從智能手機(jī)越來越普及，而手機(jī)的電池技術(shù)一直沒有較大的突破，所以省電對(duì)手機(jī)來說就是一項(xiàng)非常重要的任務(wù)，調(diào)度器也不可避免地要考慮省電問題了。

1.8 調(diào)度器歷史

Linux的調(diào)度器經(jīng)歷了長(zhǎng)久的發(fā)展，是內(nèi)核中被優(yōu)化最多目前最完善的模塊之一。下面我們來看一下Linux調(diào)度器發(fā)展的歷史。

Traditional Scheduler: v1.0 – v2.4

這一階段的調(diào)度器和傳統(tǒng)的UNIX上的調(diào)度器邏輯是一樣的。全局只有一個(gè)運(yùn)行隊(duì)列，所有進(jìn)程都放在一個(gè)隊(duì)列上。進(jìn)程區(qū)分IO密集型和CPU密集型，根據(jù)進(jìn)程的睡眠時(shí)間計(jì)算動(dòng)態(tài)優(yōu)先級(jí)，按照動(dòng)態(tài)優(yōu)先級(jí)決定進(jìn)程的調(diào)度順序，按照優(yōu)先級(jí)分配進(jìn)程的時(shí)間片大小，時(shí)間片大小是等差數(shù)列。進(jìn)程在運(yùn)行隊(duì)列上并沒有特定的排序，每次選擇下一個(gè)進(jìn)程的時(shí)候都要遍歷整個(gè)隊(duì)列，所以算法的時(shí)間復(fù)雜度是O(n)。在SMP上也只有一個(gè)運(yùn)行隊(duì)列，當(dāng)CPU比較多進(jìn)程也比較多的時(shí)候，鎖沖突比較嚴(yán)重。

O(1) Scheduler: v2.5 – v2.6.22

此調(diào)度器主要是針對(duì)傳統(tǒng)調(diào)度器進(jìn)行了改進(jìn)。首先把運(yùn)行隊(duì)列從單一變量變成了per-CPU變量，每個(gè)CPU一個(gè)運(yùn)行隊(duì)列，這樣就不會(huì)有鎖沖突了，不過這樣就需要調(diào)度均衡了。其次把運(yùn)行隊(duì)列的一個(gè)鏈表分成了兩個(gè)鏈表數(shù)組：活動(dòng)數(shù)組和過期數(shù)組。時(shí)間片沒用耗盡的進(jìn)程放在活動(dòng)數(shù)組中，時(shí)間片耗盡的進(jìn)程放在過期數(shù)組中，當(dāng)所有進(jìn)程的時(shí)間片都耗盡的時(shí)候交換兩個(gè)數(shù)組，重新分配時(shí)間片。兩個(gè)數(shù)組都使用動(dòng)態(tài)優(yōu)先級(jí)排序，并用bitmap來表示哪個(gè)優(yōu)先級(jí)隊(duì)列中有可運(yùn)行的進(jìn)程，把選擇進(jìn)程的算法復(fù)雜度降低到了O(1)。對(duì)進(jìn)程區(qū)分IO密集型和CPU密集型并計(jì)算動(dòng)態(tài)優(yōu)先級(jí)這一點(diǎn)和傳統(tǒng)調(diào)度器一樣沒有變。

SD Scheduler：(未合入)

樓梯調(diào)度器，它是對(duì)O(1)調(diào)度器的改進(jìn)，算法復(fù)雜還是O(1)。之前的調(diào)度器都區(qū)分IO密集型和CPU密集型，算法要對(duì)進(jìn)程的類型進(jìn)行探測(cè)，根據(jù)探測(cè)結(jié)果調(diào)整動(dòng)態(tài)優(yōu)先級(jí)。這就有很大的問題，探測(cè)不一定準(zhǔn)確，而且進(jìn)程還可以欺騙調(diào)度器，最終會(huì)導(dǎo)致調(diào)度有很大的不公平性。樓梯調(diào)度器是第一次嘗試使用公平調(diào)度算法，它廢除了動(dòng)態(tài)優(yōu)先級(jí)，不再區(qū)分IO密集型進(jìn)程和CPU密集型進(jìn)程，但是仍然讓IO密集型進(jìn)程保持較高的響應(yīng)性。在實(shí)現(xiàn)上，樓梯調(diào)度算法廢棄了過期數(shù)組，只使用一個(gè)數(shù)組。當(dāng)進(jìn)程使用完自己的時(shí)間片之后，其時(shí)間片就會(huì)被減半并下降到下一個(gè)優(yōu)先級(jí)，其本身的優(yōu)先級(jí)還是不變的。當(dāng)進(jìn)程下降到最后一個(gè)優(yōu)先級(jí)之后就再回到它本來的優(yōu)先級(jí)隊(duì)列并重新分配時(shí)間片。整個(gè)過程就像下樓梯一樣，所以這個(gè)算法就叫做樓梯調(diào)度器。此算法雖然沒有合入到標(biāo)準(zhǔn)內(nèi)核，但是它第一次證明了可以采取完全公平的思想進(jìn)行調(diào)度，也就是不區(qū)分IO密集型和CPU密集型進(jìn)程。

RSDL Scheduler：(未合入)

旋轉(zhuǎn)樓梯調(diào)度器，是對(duì)樓梯調(diào)度器的改進(jìn)。又重新引入了過期數(shù)組，為每個(gè)優(yōu)先級(jí)都分配一個(gè)組時(shí)間配額記為Tg，進(jìn)程本身的時(shí)間片記為Tp。當(dāng)進(jìn)程用完自己的時(shí)間片時(shí)會(huì)下降一個(gè)優(yōu)先級(jí)，當(dāng)一個(gè)優(yōu)先級(jí)的Tg被用完時(shí)，組內(nèi)所有的進(jìn)程都會(huì)下降一個(gè)優(yōu)先級(jí)。進(jìn)程下降到最低優(yōu)先級(jí)之后會(huì)被放入過期數(shù)組，當(dāng)活動(dòng)數(shù)組為空時(shí)就會(huì)交換活動(dòng)數(shù)組和過期數(shù)組。由于加了Tg，使得低優(yōu)先級(jí)進(jìn)程的調(diào)度延遲可控，進(jìn)一步增加了公平性。

CFS: Completely Fair Scheduler: v2.6.23 – now

完全公平調(diào)度器，從SD/RSDL中吸取了完全公平的思想，不再區(qū)分IO密集型進(jìn)程與CPU密集型進(jìn)程，不再根據(jù)睡眠時(shí)間調(diào)整動(dòng)態(tài)優(yōu)先級(jí)，所有普通進(jìn)程都按優(yōu)先級(jí)相對(duì)平分CPU時(shí)間，算法復(fù)雜度是O(logn)。此時(shí)對(duì)調(diào)度器框架也進(jìn)行了重構(gòu)，和之前的有很大的不同。之前的調(diào)度器是一個(gè)算法調(diào)度所有進(jìn)程，在算法內(nèi)部區(qū)別對(duì)待實(shí)時(shí)進(jìn)程和普通進(jìn)程?，F(xiàn)在的調(diào)度器框架是先區(qū)分不同類型的進(jìn)程，普通進(jìn)程一個(gè)調(diào)度類，實(shí)時(shí)進(jìn)程一個(gè)調(diào)度類，調(diào)度類里面再去實(shí)現(xiàn)具體的調(diào)度算法。CFS是普通調(diào)度類的算法。

二、進(jìn)程調(diào)度框架

前面我們對(duì)進(jìn)程調(diào)度的概念和邏輯進(jìn)行了講解，現(xiàn)在我們來看一下Linux上進(jìn)程調(diào)度的框架結(jié)構(gòu)。本章只講總體框架，不講具體算法，具體算法在后面的章節(jié)中講。

2.1 調(diào)度隊(duì)列

我們先來看一下進(jìn)程的狀態(tài)轉(zhuǎn)換圖。

處于就緒(Runnable)狀態(tài)的進(jìn)程可以被調(diào)度到CPU上去執(zhí)行。但是處于就緒狀態(tài)的進(jìn)程可能不止一個(gè)，所以我們需要一個(gè)運(yùn)行隊(duì)列來安放所有就緒的進(jìn)程，由于CPU也不止一個(gè)，所以我們需要NR_CPU個(gè)運(yùn)行隊(duì)列。

我們看一下調(diào)度隊(duì)列的定義(代碼經(jīng)過了高度刪減)：

linux-src/kernel/sched/sched.h

linux-src/kernel/sched/core.c

DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

內(nèi)核定義了一個(gè)per-CPU變量runqueues，其類型是struct rq。所有的就緒進(jìn)程都會(huì)被放入某個(gè)CPU的rq上去，具體放到哪個(gè)rq上，這個(gè)在調(diào)度均衡里面講。內(nèi)核一共定義了五個(gè)調(diào)度類(這個(gè)在2.5中細(xì)講)，屬于不同調(diào)度類的進(jìn)程會(huì)被放入不同的子隊(duì)列，所以rq中包含三個(gè)子運(yùn)行隊(duì)列cfs_rq、rt_rq、dl_rq。為啥只有3個(gè)子運(yùn)行隊(duì)列呢？因?yàn)橛袃蓚€(gè)調(diào)度類idle、stop，每個(gè)CPU只能有一個(gè)進(jìn)程，所以沒必要弄個(gè)隊(duì)列，直接關(guān)聯(lián)它們的進(jìn)程就可以了，就是上面代碼中的兩個(gè)struct task_struct * 類型的指針變量idle、stop。

2.2 進(jìn)程喚醒

進(jìn)程是怎么被放入運(yùn)行隊(duì)列的呢？都是通過進(jìn)程喚醒來放入的，包括新創(chuàng)建的進(jìn)程也是。新建喚醒和阻塞喚醒的代碼不太一樣，下面我們分別來看一下。

我們先來看一下新建喚醒的代碼：

linux-src/kernel/sched/core.c

在fork中會(huì)調(diào)用此函數(shù)喚醒新創(chuàng)建的進(jìn)程，把它放入到運(yùn)行隊(duì)列中等待被調(diào)度。此函數(shù)會(huì)先調(diào)用select_task_rq來選擇自己要去哪個(gè)CPU的rq上去，然后調(diào)用activate_task把進(jìn)程加入到相應(yīng)的運(yùn)行隊(duì)列上，最后調(diào)用check_preempt_curr看一下是否需要搶占，如果需要就觸發(fā)搶占。select_task_rq的邏輯我們?cè)谡{(diào)度均衡中講，check_preempt_curr的邏輯我們?cè)谙乱还?jié)的被動(dòng)調(diào)度中講。

我們?cè)賮砜匆幌伦枞麊拘训拇a：

linux-src/kernel/sched/core.c

static inttry_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){  unsigned long flags;  int cpu, success = 0;
  preempt_disable();  if (p == current) {    goto out;  }
  raw_spin_lock_irqsave(&p->pi_lock, flags);  if (!ttwu_state_match(p, state, &success))    goto unlock;
  if (READ_ONCE(p->on_rq) && ttwu_runnable(p, wake_flags))    goto unlock;
  cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);  if (task_cpu(p) != cpu) {    if (p->in_iowait) {      delayacct_blkio_end(p);      atomic_dec(&task_rq(p)->nr_iowait);    }    wake_flags |= WF_MIGRATED;    set_task_cpu(p, cpu);  }
  ttwu_queue(p, cpu, wake_flags);unlock:  raw_spin_unlock_irqrestore(&p->pi_lock, flags);out:  preempt_enable();  return success;}
int wake_up_process(struct task_struct *p){  return try_to_wake_up(p, TASK_NORMAL, 0);}
int wake_up_state(struct task_struct *p, unsigned int state){  return try_to_wake_up(p, state, 0);}
int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flags,        void *key){  WARN_ON_ONCE(IS_ENABLED(CONFIG_SCHED_DEBUG) && wake_flags & ~WF_SYNC);  return try_to_wake_up(curr->private, mode, wake_flags);}

阻塞喚醒的核心邏輯是try_to_wake_up，但是內(nèi)核并不是直接用這個(gè)函數(shù)，而是提供了三個(gè)封裝函數(shù)。wake_up_process是默認(rèn)的通用的進(jìn)程喚醒接口，能喚醒TASK_NORMAL狀態(tài)的進(jìn)程。TASK_NORMAL就是阻塞狀態(tài)的進(jìn)程，包含TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE，前者是前睡眠能被信號(hào)喚醒，后者是深睡眠不能被信號(hào)喚醒。還有一些特殊狀態(tài)的進(jìn)程如被暫停的進(jìn)程是不能通過wake_up_process來喚醒的，所以內(nèi)核還提供了接口wake_up_state，可以自己指定喚醒什么狀態(tài)的進(jìn)程。還有一個(gè)封裝函數(shù)default_wake_function，它是wait_queue的默認(rèn)喚醒函數(shù)。

try_to_wake_up函數(shù)首先進(jìn)行一些檢測(cè)，先檢測(cè)被喚醒的進(jìn)程是否為當(dāng)前進(jìn)程，如果是的話直接go out。再檢測(cè)進(jìn)程的狀態(tài)是否與state相符合，不符合就不喚醒，再看一下進(jìn)程是否已經(jīng)處于喚醒狀態(tài)了，如果是就沒有必要喚醒了。然后調(diào)用select_task_rq選擇要到哪個(gè)CPU的運(yùn)行隊(duì)列上去運(yùn)行，最后調(diào)用ttwu_queue把進(jìn)程放到目標(biāo)運(yùn)行隊(duì)列上去?；具壿嫼蛍ake_up_new_task是一樣的。

2.3 調(diào)度時(shí)機(jī)

進(jìn)程放入運(yùn)行隊(duì)列之后就等著被調(diào)度到CPU上去運(yùn)行了。但是當(dāng)前進(jìn)程正在使用著CPU，它什么時(shí)候能把CPU讓給其它進(jìn)程去運(yùn)行呢？有兩種情況：一是當(dāng)前進(jìn)程主動(dòng)讓出CPU，這叫主動(dòng)調(diào)度；二是當(dāng)前進(jìn)程被動(dòng)讓出CPU，這叫被動(dòng)調(diào)度，也就是進(jìn)程搶占。

主動(dòng)調(diào)度：

主動(dòng)調(diào)度又可以分為自愿性主動(dòng)調(diào)度和非自愿性主動(dòng)調(diào)度。自愿性主動(dòng)調(diào)度是指進(jìn)程主動(dòng)調(diào)用sched_yield讓出CPU，進(jìn)程本身還會(huì)回到運(yùn)行隊(duì)列中去等待下次調(diào)度。如果運(yùn)行隊(duì)列中沒有其它進(jìn)程的話，此進(jìn)程還會(huì)繼續(xù)運(yùn)行。非自愿性主動(dòng)調(diào)度是指進(jìn)程運(yùn)行時(shí)遇到了無法繼續(xù)運(yùn)行的情況，只能進(jìn)行調(diào)度讓其它進(jìn)程運(yùn)行。進(jìn)程無法繼續(xù)運(yùn)行的情況有加鎖失敗、要讀的文件現(xiàn)在不在內(nèi)存中、進(jìn)程死亡等。

下面我們來看一個(gè)非自愿性主動(dòng)調(diào)度的例子，信號(hào)量獲取失敗時(shí)的操作：

linux-src/kernel/locking/semaphore.c

先定義一個(gè)等待項(xiàng)，把自己加入到信號(hào)量的等待列表中，然后調(diào)用schedule_timeout執(zhí)行調(diào)度。schedule_timeout和普通的調(diào)度函數(shù)schedule的區(qū)別是：schedule只能等著被具體的事件喚醒，schedule_timeout可以被事件喚醒，如果事件在規(guī)定的時(shí)間沒有到來就會(huì)被定時(shí)器超時(shí)喚醒。

被動(dòng)調(diào)度：

如果進(jìn)程自己不調(diào)用sched_yield，也不調(diào)用任何會(huì)阻塞的函數(shù)，那么進(jìn)程豈不是就可以一直霸占著CPU了。所以內(nèi)核還提供了被動(dòng)調(diào)度，強(qiáng)制進(jìn)行進(jìn)程調(diào)度，避免一個(gè)進(jìn)程長(zhǎng)時(shí)間霸占CPU。被動(dòng)調(diào)度是被動(dòng)的，不能由進(jìn)程主動(dòng)去調(diào)度，所以被動(dòng)調(diào)度和主動(dòng)調(diào)度的模式差別很大。被動(dòng)調(diào)度的過程分為兩步：觸發(fā)調(diào)度和執(zhí)行調(diào)度。觸發(fā)調(diào)度僅僅是做個(gè)標(biāo)記，告訴系統(tǒng)需要調(diào)度了。執(zhí)行調(diào)度是系統(tǒng)會(huì)在某些特定的點(diǎn)去檢查調(diào)度標(biāo)記，如果被設(shè)置的話就執(zhí)行調(diào)度。觸發(fā)調(diào)度的點(diǎn)有：定時(shí)器中斷、喚醒進(jìn)程時(shí)、遷移進(jìn)程時(shí)、改變進(jìn)程優(yōu)先級(jí)時(shí)。執(zhí)行調(diào)度的點(diǎn)有：從系統(tǒng)調(diào)用返回用戶空間、從中斷返回用戶空間、從中斷返回內(nèi)核、禁用搶占臨界區(qū)結(jié)束、禁用軟中斷臨界區(qū)結(jié)束、cond_resched調(diào)用點(diǎn)。

定時(shí)器中斷是保證搶占式多任務(wù)能實(shí)現(xiàn)的關(guān)鍵。因?yàn)槠渌粍?dòng)調(diào)度的觸發(fā)點(diǎn)是不確定的，只有定時(shí)器中斷是確定的周期性的，因此定時(shí)器中斷也被叫做調(diào)度tick。定時(shí)器中斷的頻率是個(gè)kconfig選項(xiàng)，可選的值有100、250、300、1000。默認(rèn)選項(xiàng)是250，也就是說每4ms就會(huì)有一個(gè)定時(shí)器中斷，這樣就能保證被動(dòng)調(diào)度的及時(shí)性，不會(huì)有進(jìn)程過長(zhǎng)的占用CPU。

下面我們來看一下調(diào)度tick的流程：

linux-src/kernel/sched/core.c

void scheduler_tick(void){  int cpu = smp_processor_id();  struct rq *rq = cpu_rq(cpu);  struct task_struct *curr = rq->curr;
  curr->sched_class->task_tick(rq, curr, 0);
#ifdef CONFIG_SMP  rq->idle_balance = idle_cpu(cpu);  trigger_load_balance(rq);#endif}

在低精度定時(shí)器、高精度定時(shí)器與固定tick、動(dòng)態(tài)tick的不同組合下，定時(shí)器中斷觸發(fā)的方式是不同的，但是最終都會(huì)調(diào)用scheduler_tick。scheduler_tick會(huì)調(diào)用當(dāng)前進(jìn)程的調(diào)度類的task_tick函數(shù)，此函數(shù)根據(jù)具體的情況可能會(huì)觸發(fā)調(diào)度。task_tick函數(shù)的實(shí)現(xiàn)細(xì)節(jié)我們?cè)诰唧w的調(diào)度算法中再講。

喚醒進(jìn)程有新建喚醒和阻塞喚醒，它們都有可能觸發(fā)調(diào)度。我們來看一下：

linux-src/kernel/sched/core.c

linux-src/include/linux/sched.h

static inline void set_tsk_need_resched(struct task_struct *tsk){  set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);}
static inline void set_tsk_thread_flag(struct task_struct *tsk, int flag){  set_ti_thread_flag(task_thread_info(tsk), flag);}

可以看到無論是新建喚醒還是阻塞喚醒，最終都是調(diào)用check_preempt_curr函數(shù)來處理的。如果被喚醒的進(jìn)程和當(dāng)前進(jìn)程是同一個(gè)調(diào)度類的則會(huì)調(diào)用調(diào)度類的函數(shù)來處理，這個(gè)邏輯我們?cè)诰唧w調(diào)度類中再講。如果被喚醒的進(jìn)程比當(dāng)前進(jìn)程的調(diào)度類高，則會(huì)觸發(fā)調(diào)度。resched_curr函數(shù)最終會(huì)在thread_info的flag中設(shè)置TIF_NEED_RESCHED標(biāo)記。

下面我們?cè)賮砜匆幌聢?zhí)行調(diào)度的點(diǎn)，以x86為例。

系統(tǒng)調(diào)用返回用戶空間：

linux-src/arch/x86/entry/common.c

linux-src/kernel/entry/common.c

__visible noinstr void syscall_exit_to_user_mode(struct pt_regs *regs){  instrumentation_begin();  __syscall_exit_to_user_mode_work(regs);  instrumentation_end();  __exit_to_user_mode();}
static __always_inline void __syscall_exit_to_user_mode_work(struct pt_regs *regs){  syscall_exit_to_user_mode_prepare(regs);  local_irq_disable_exit_to_user();  exit_to_user_mode_prepare(regs);}
static void exit_to_user_mode_prepare(struct pt_regs *regs){  unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
  if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))    ti_work = exit_to_user_mode_loop(regs, ti_work);}
static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,              unsigned long ti_work){  while (ti_work & EXIT_TO_USER_MODE_WORK) {    if (ti_work & _TIF_NEED_RESCHED)      schedule();    if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))      handle_signal_work(regs, ti_work);    ti_work = READ_ONCE(current_thread_info()->flags);  }
  return ti_work;}

可以看到系統(tǒng)調(diào)用完成之后返回用戶空間之前會(huì)檢測(cè)thread_info flag中的_TIF_NEED_RESCHED，如果設(shè)置了就會(huì)執(zhí)行調(diào)度。

中斷返回用戶空間或者內(nèi)核空間：

linux-src/arch/x86/include/asm/idtentry.h

linux-src/kernel/entry/common.c

noinstr void irqentry_exit(struct pt_regs *regs, irqentry_state_t state){  if (user_mode(regs)) {    irqentry_exit_to_user_mode(regs);  } else if (!regs_irqs_disabled(regs)) {    if (IS_ENABLED(CONFIG_PREEMPTION)) {      irqentry_exit_cond_resched();    }  } else {    if (state.exit_rcu)      rcu_irq_exit();  }}
noinstr void irqentry_exit_to_user_mode(struct pt_regs *regs){  instrumentation_begin();  exit_to_user_mode_prepare(regs);  instrumentation_end();  __exit_to_user_mode();}
static void exit_to_user_mode_prepare(struct pt_regs *regs){  unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
  if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))    ti_work = exit_to_user_mode_loop(regs, ti_work);}
static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,              unsigned long ti_work){  while (ti_work & EXIT_TO_USER_MODE_WORK) {    if (ti_work & _TIF_NEED_RESCHED)      schedule();    if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))      handle_signal_work(regs, ti_work);    ti_work = READ_ONCE(current_thread_info()->flags);  }
  return ti_work;}
void irqentry_exit_cond_resched(void){  if (!preempt_count()) {    if (need_resched())      preempt_schedule_irq();  }}

關(guān)于中斷的原理請(qǐng)參看《深入理解Linux中斷機(jī)制》。所有中斷和異常的入口函數(shù)都是通過DEFINE_IDTENTRY_IRQ或DEFINE_IDTENTRY(還有其它一些類似的宏)來定義的，其中一定會(huì)調(diào)用irqentry_exit。irqentry_exit又會(huì)根據(jù)寄存器狀態(tài)來判斷是返回到用戶空間還是內(nèi)核空間。如果是返回到用戶空間則會(huì)調(diào)用irqentry_exit_to_user_mode，此函數(shù)的操作和從系統(tǒng)調(diào)用返回用戶空間是相似的，就不再贅述了。如果是返回到內(nèi)核空間則會(huì)調(diào)用irqentry_exit_cond_resched，調(diào)用此函數(shù)會(huì)先檢測(cè)是否配置了CONFIG_PREEMPTION，沒配置就不調(diào)用。CONFIG_PREEMPTION代表的是內(nèi)核搶占，在有些場(chǎng)景中會(huì)說成搶占，但是要明白其代表的是內(nèi)核搶占。

內(nèi)核有時(shí)候?yàn)榱送?，需要臨時(shí)禁用搶占，這個(gè)禁用的是內(nèi)核搶占，因?yàn)橛脩魮屨加肋h(yuǎn)可以。當(dāng)代碼配置了內(nèi)核搶占時(shí)才有效。禁用搶占有引用計(jì)數(shù)，釋放最后一個(gè)引用時(shí)才會(huì)重新開啟內(nèi)核搶占。禁用搶占和開啟搶占分別用宏preempt_disable和preempt_enable。preempt_enable代表臨界區(qū)的結(jié)束，會(huì)去檢測(cè)是否需要調(diào)度。

禁用搶占臨界區(qū)結(jié)束：

linux-src/include/linux/preempt.h

preempt_disable增加引用計(jì)數(shù)，preempt_enable減少引用計(jì)數(shù)并檢測(cè)是否為0，如果為0則執(zhí)行調(diào)度。

禁用軟中斷臨界區(qū)結(jié)束：

linux-src/include/linux/bottom_half.h

static inline void local_bh_enable(void){  __local_bh_enable_ip(_THIS_IP_, SOFTIRQ_DISABLE_OFFSET);}

linux-src/kernel/softirq.c

linux-src/include/linux/preempt.h

#define preempt_check_resched() \do { \  if (should_resched(0)) \    __preempt_schedule(); \} while (0)

在禁用軟中斷的過程中有可能其它地方已經(jīng)觸發(fā)了調(diào)度，因此在重新開啟軟中斷的時(shí)候檢測(cè)一下是否需要調(diào)度。

cond_resched調(diào)用點(diǎn)：

linux-src/include/linux/sched.h

linux-src/kernel/sched/core.c

int __sched __cond_resched(void){  if (should_resched(0)) {    preempt_schedule_common();    return 1;  }
  return 0;}

在很多比較耗時(shí)的內(nèi)核操作中都會(huì)加上cond_resched調(diào)用，用來增加搶占調(diào)度的檢測(cè)點(diǎn)，提高系統(tǒng)的響應(yīng)性。

2.4 調(diào)度流程

前面講了這么多觸發(fā)調(diào)度的時(shí)機(jī)，現(xiàn)在該執(zhí)行調(diào)度了。執(zhí)行調(diào)度的總體邏輯是很簡(jiǎn)單的，就兩個(gè)步驟：選擇進(jìn)程和切換進(jìn)程。選擇進(jìn)程是一個(gè)很麻煩的過程，牽涉到調(diào)度類和調(diào)度算法，這個(gè)在下一節(jié)中講。切換進(jìn)程雖然不太麻煩，但是還是比較難以理解的，這個(gè)在2.7節(jié)中講。執(zhí)行調(diào)度的入口函數(shù)是__schedule，無論是從什么途徑執(zhí)行的調(diào)度，最終都要調(diào)用這個(gè)函數(shù)。

下面我們來看一下它的代碼：

linux-src/kernel/sched/core.c

代碼經(jīng)過刪減，只留下了關(guān)鍵操作。首先是pick_next_task，選擇下一個(gè)要執(zhí)行的進(jìn)程。然后是context_switch，切換進(jìn)程。

2.5 調(diào)度算法

這節(jié)要講的是pick_next_task，在講之前我們要先講一些概念邏輯。

內(nèi)核中有調(diào)度類、調(diào)度策略、調(diào)度算法的概念，這三者是什么意思，又有什么關(guān)系呢？調(diào)度類代表的是進(jìn)程對(duì)調(diào)度器的需求，主要是對(duì)調(diào)度緊迫性的需求。調(diào)度策略是調(diào)度類的子類，是對(duì)調(diào)度類的細(xì)分，是在同一個(gè)調(diào)度需求下的細(xì)微區(qū)別。調(diào)度算法是對(duì)調(diào)度類的實(shí)現(xiàn)，一個(gè)調(diào)度類一個(gè)調(diào)度算法。同一個(gè)調(diào)度類的調(diào)度策略是有很強(qiáng)的相似性的，所以在同一個(gè)算法中實(shí)現(xiàn)，對(duì)于它們不同的部分，算法再去進(jìn)行區(qū)分。下面我們畫個(gè)圖來看一下Linux中的所有調(diào)度類、調(diào)度策略和調(diào)度算法。

Linux中一共有五個(gè)調(diào)度類，分別是stop(禁令調(diào)度類)、deadline(限時(shí)調(diào)度類)、realtime(實(shí)時(shí)調(diào)度類)、time-share(分時(shí)調(diào)度類)、idle(閑時(shí)調(diào)度類)。它們的調(diào)度緊迫性從上到下，依次降低。其中禁令調(diào)度類和閑時(shí)調(diào)度類有特殊的目的，僅用于內(nèi)核，沒有調(diào)度策略，由于這類進(jìn)程在內(nèi)核啟動(dòng)時(shí)就設(shè)置好了，一個(gè)CPU一個(gè)相應(yīng)的進(jìn)程，所以也不需要調(diào)度算法。另外三個(gè)調(diào)度類可用于用戶空間進(jìn)程，有相應(yīng)的調(diào)度策略和調(diào)度算法，也有相應(yīng)的API供用戶空間來設(shè)置一個(gè)進(jìn)程的調(diào)度策略和優(yōu)先級(jí)。調(diào)度類之間的關(guān)系是有高類的進(jìn)程可運(yùn)行的情況下，絕對(duì)不會(huì)去調(diào)度低類的進(jìn)程，只有當(dāng)高類無Runnable的進(jìn)程的時(shí)候才會(huì)去調(diào)度低類的進(jìn)程。這里面也有一個(gè)例外就是內(nèi)核為了防止實(shí)時(shí)進(jìn)程餓死普通進(jìn)程，提供了一個(gè)配置參數(shù)，默認(rèn)值是實(shí)時(shí)進(jìn)程如果已經(jīng)占用了95%的CPU時(shí)間，就會(huì)把剩余5%的CPU時(shí)間分給普通進(jìn)程。

禁令調(diào)度類是內(nèi)核用來執(zhí)行一些特別緊急的事物所使用的。禁令調(diào)度類的進(jìn)程是內(nèi)核在啟動(dòng)時(shí)就創(chuàng)建好的，一個(gè)CPU一個(gè)進(jìn)程，名字叫做[migration/n]，n是CPU_ID，之后就不能再創(chuàng)建此類進(jìn)程了。內(nèi)核提供了一些接口可以向這些進(jìn)程push work。調(diào)度均衡要遷移線程的時(shí)候會(huì)用到這類進(jìn)程，所以它的名字叫做migration。

linux-src/include/linux/stop_machine.h

int stop_one_cpu(unsigned int cpu, cpu_stop_fn_t fn, void *arg);int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *arg);
int stop_machine(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus);int stop_machine_cpuslocked(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus);

由于禁令調(diào)度類的進(jìn)程優(yōu)先級(jí)是最高的，只要此類進(jìn)程變得Runnable了，就會(huì)立馬搶占當(dāng)前進(jìn)程來運(yùn)行，所以這幾個(gè)接口的名字也都叫做stop_cpu、stop_machine之類的。大家不要望文生義地認(rèn)為這幾個(gè)接口能暫定CPU或者關(guān)機(jī)之類的。

限時(shí)調(diào)度類屬于硬實(shí)時(shí)，適用于對(duì)調(diào)度時(shí)間有明確要求的進(jìn)程。它只有一個(gè)調(diào)度策略，限時(shí)調(diào)度策略。一個(gè)進(jìn)程必須通過系統(tǒng)調(diào)用才能把自己設(shè)置為限時(shí)調(diào)度策略，并且還要提供三個(gè)參數(shù)：運(yùn)行周期、運(yùn)行時(shí)間和截止時(shí)間。運(yùn)行周期是說這個(gè)進(jìn)程在多長(zhǎng)時(shí)間內(nèi)想要運(yùn)行一次，運(yùn)行時(shí)間是說這個(gè)進(jìn)程每次想要運(yùn)行多長(zhǎng)時(shí)間，截止時(shí)間是說這個(gè)進(jìn)程每次運(yùn)行結(jié)束不能晚于什么時(shí)間。這三個(gè)參數(shù)都需要進(jìn)程根據(jù)自己的實(shí)際情況向內(nèi)核提供，而且不是說你提供了就一定能設(shè)置成功，內(nèi)核還要檢測(cè)與已有的限時(shí)調(diào)度類進(jìn)程是否沖突，如果有沖突那就無法滿足，就只能返回設(shè)置失敗。還有一點(diǎn)是，運(yùn)行時(shí)間是程序員要提供預(yù)估好的，如果程序?qū)嶋H運(yùn)行時(shí)間超過了預(yù)估時(shí)間則會(huì)被切走，這可能會(huì)導(dǎo)致災(zāi)難性的后果。

實(shí)時(shí)調(diào)度類屬于軟實(shí)時(shí)，適用于那些只要可運(yùn)行就希望立馬能執(zhí)行的進(jìn)程，比如音視頻的解碼進(jìn)程。實(shí)時(shí)調(diào)度類又分為兩個(gè)調(diào)度策略，SCHED_FIFO和SCHED_RR。實(shí)時(shí)調(diào)度類的內(nèi)部邏輯是讓實(shí)時(shí)優(yōu)先級(jí)大的進(jìn)程先運(yùn)行，只要有實(shí)時(shí)優(yōu)先級(jí)大的進(jìn)程可運(yùn)行，就不會(huì)去調(diào)度實(shí)時(shí)優(yōu)先級(jí)小的進(jìn)程。當(dāng)兩個(gè)實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)相同時(shí)，SCHED_RR和SCHED_FIFO這兩個(gè)策略就有區(qū)別了，SCHED_FIFO進(jìn)程如果搶占了CPU，它就會(huì)一直占著CPU，不會(huì)給同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程讓CPU的，而SCHED_RR進(jìn)程會(huì)在運(yùn)行了一定的時(shí)間片之后主動(dòng)讓給同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程。

分時(shí)調(diào)度類是給廣大的普通進(jìn)程來用的，大家共同分享CPU。根據(jù)優(yōu)先級(jí)的不同，可能有的進(jìn)程分的多有的進(jìn)程分的少，但是不會(huì)出現(xiàn)一個(gè)進(jìn)程霸占CPU的情況。分時(shí)調(diào)度類下面有三個(gè)調(diào)度策略：SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE。它們的基本思想都是分時(shí)，但是略有不同，SCHED_BATCH進(jìn)程希望減少調(diào)度次數(shù)，每次調(diào)度能執(zhí)行的時(shí)間長(zhǎng)一點(diǎn)，SCHED_IDLE是優(yōu)先級(jí)特別低的進(jìn)程，其分到的CPU時(shí)間的比例非常低，但是也總是能保證分到。分時(shí)調(diào)度類現(xiàn)在的算法叫做CFS(完全公平調(diào)度)，所以分時(shí)調(diào)度類也叫做公平調(diào)度類。

閑時(shí)調(diào)度類是給內(nèi)核用的，當(dāng)CPU沒有其它進(jìn)程可以執(zhí)行的時(shí)候就會(huì)運(yùn)行閑時(shí)調(diào)度類的進(jìn)程。此類進(jìn)程是在內(nèi)核啟動(dòng)時(shí)就創(chuàng)建好的，一個(gè)CPU一個(gè)進(jìn)程，此后就不能再創(chuàng)建此類進(jìn)程了。閑時(shí)調(diào)度類的進(jìn)程也叫做idle進(jìn)程，它在內(nèi)核中有些特殊的用途，比如CPUIdle的實(shí)現(xiàn)就和idle進(jìn)程密切相關(guān)。

大家要注意，閑時(shí)調(diào)度類和分時(shí)調(diào)度類中SCHED_IDLE調(diào)度策略不是一回事，兩者沒有關(guān)系，大家不要弄混淆了。

系統(tǒng)為每個(gè)調(diào)度類都定義了一些標(biāo)準(zhǔn)的操作，我們來看一下：

linux-src/kernel/sched/sched.h

每個(gè)調(diào)度類在實(shí)現(xiàn)自己的算法的時(shí)候都要實(shí)現(xiàn)這些函數(shù)指針，我們?cè)谥v到具體算法時(shí)再來講解這些函數(shù)指針的含義。

下面我們來看一下pick_next_task的代碼：

linux-src/kernel/sched/core.c

static struct task_struct *pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf){  return __pick_next_task(rq, prev, rf);}
static inline struct task_struct *__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf){  const struct sched_class *class;  struct task_struct *p;
  /*   * Optimization: we know that if all tasks are in the fair class we can   * call that function directly, but only if the @prev task wasn't of a   * higher scheduling class, because otherwise those lose the   * opportunity to pull in more work from other CPUs.   */  if (likely(prev->sched_class <= &fair_sched_class &&       rq->nr_running == rq->cfs.h_nr_running)) {
    p = pick_next_task_fair(rq, prev, rf);    if (unlikely(p == RETRY_TASK))      goto restart;
    /* Assume the next prioritized class is idle_sched_class */    if (!p) {      put_prev_task(rq, prev);      p = pick_next_task_idle(rq);    }
    return p;  }
restart:  put_prev_task_balance(rq, prev, rf);
  for_each_class(class) {    p = class->pick_next_task(rq);    if (p)      return p;  }
  /* The idle class should always have a runnable task: */  BUG();}

__pick_next_task進(jìn)行了一個(gè)優(yōu)化，因?yàn)榇蟛糠謺r(shí)間系統(tǒng)中主要存在的都是普通進(jìn)程，所以先檢測(cè)運(yùn)行隊(duì)列的運(yùn)行數(shù)量和公平運(yùn)行列隊(duì)中的運(yùn)行數(shù)量，如果相等的話就說明系統(tǒng)中目前只有普通進(jìn)程，那么就可以直接調(diào)用pick_next_task_fair。接著就是主邏輯了，先從高調(diào)度類進(jìn)行選擇，如果有可運(yùn)行的進(jìn)程就直接返回，如果沒有就去查詢下一個(gè)調(diào)度類。最后一定能返回一個(gè)進(jìn)程的，因?yàn)閕dle進(jìn)程總是可運(yùn)行的。

每個(gè)調(diào)度類的具體算法邏輯在后面的章節(jié)中講解。

2.6 進(jìn)程優(yōu)先級(jí)

Linux上一共有5種調(diào)度類，其中禁令調(diào)度類和閑時(shí)調(diào)度類只在內(nèi)核里使用，而且一個(gè)CPU只有一個(gè)線程，所以用不到進(jìn)程優(yōu)先級(jí)。限時(shí)調(diào)度類用的是進(jìn)程設(shè)置的三個(gè)調(diào)度參數(shù)作為調(diào)度的依據(jù)，也用不到進(jìn)程優(yōu)先級(jí)。所以就只有實(shí)時(shí)調(diào)度類和分時(shí)調(diào)度類會(huì)用到進(jìn)程優(yōu)先級(jí)。它們使用優(yōu)先級(jí)的方法也并不相同，我們?cè)谥v到具體算法時(shí)再講。

由于歷史原因，實(shí)時(shí)進(jìn)程和普通進(jìn)程的優(yōu)先級(jí)并不是一個(gè)簡(jiǎn)單的數(shù)值，而是有好幾個(gè)數(shù)值體系和變換規(guī)則，我們先來看一下設(shè)置進(jìn)程調(diào)度策略和優(yōu)先級(jí)的API。

sched_setscheduler能同時(shí)設(shè)置實(shí)時(shí)調(diào)度類和分時(shí)調(diào)度類的調(diào)度策略和靜態(tài)優(yōu)先級(jí)，對(duì)于實(shí)時(shí)調(diào)度類，其靜態(tài)優(yōu)先級(jí)范圍是1-99,99最大，對(duì)于分時(shí)調(diào)度類，其靜態(tài)優(yōu)先級(jí)必須設(shè)置為0，其動(dòng)態(tài)優(yōu)先級(jí)也就是nice需要通過nice接口來設(shè)置。sched_setparam可以設(shè)置實(shí)時(shí)進(jìn)程的靜態(tài)優(yōu)先級(jí)，對(duì)于分時(shí)進(jìn)程，其靜態(tài)優(yōu)先級(jí)必須為0。

我們?cè)賮砜匆幌聇ask_struct中記錄優(yōu)先級(jí)的字段。

linux-src/include/linux/sched.h

struct task_struct {  int        prio;  int        static_prio;  int        normal_prio;  unsigned int      rt_priority;}

一共有4個(gè)字段，rt_priority用來記錄實(shí)時(shí)進(jìn)程的用戶空間的靜態(tài)優(yōu)先級(jí)，static_prio用來記錄分時(shí)進(jìn)程的用戶空間的動(dòng)態(tài)優(yōu)先級(jí)并做了轉(zhuǎn)換。然后rt_priority和static_prio一起轉(zhuǎn)化為normal_prio(規(guī)范優(yōu)先級(jí))，此時(shí)實(shí)時(shí)進(jìn)程和分時(shí)進(jìn)程的優(yōu)先級(jí)就在同一個(gè)數(shù)軸上了。最終起作用的是prio(動(dòng)態(tài)優(yōu)先級(jí))，它的值默認(rèn)等于normal_prio，一般不會(huì)變動(dòng)。

下面我們畫圖來看一下進(jìn)程的優(yōu)先級(jí)轉(zhuǎn)換：

在用戶空間的時(shí)候，實(shí)時(shí)進(jìn)程和普通進(jìn)程(分時(shí)進(jìn)程)共享同一個(gè)優(yōu)先級(jí)數(shù)軸，叫靜態(tài)優(yōu)先級(jí)，范圍是0-99，值越大優(yōu)先級(jí)越高，實(shí)時(shí)進(jìn)程占用1-99，普通進(jìn)程占用0。普通進(jìn)程自己又新開了一個(gè)數(shù)軸，叫動(dòng)態(tài)優(yōu)先級(jí)，也叫nice值，范圍是 -20 - 19，值越低優(yōu)先級(jí)越高。

到了內(nèi)核空間的時(shí)候，實(shí)時(shí)進(jìn)程有一個(gè)實(shí)時(shí)優(yōu)先級(jí)，直接復(fù)制用戶空間的靜態(tài)優(yōu)先級(jí)，普通進(jìn)程有一個(gè)靜態(tài)優(yōu)先級(jí)，它是用戶空間的nice值轉(zhuǎn)換過來的，轉(zhuǎn)換規(guī)則是nice+120。然后內(nèi)核又定義了規(guī)范優(yōu)先級(jí)，把它們都統(tǒng)一到同一個(gè)數(shù)軸上來。普通進(jìn)程的規(guī)范優(yōu)先級(jí)是直接復(fù)制其靜態(tài)優(yōu)先級(jí)，實(shí)時(shí)進(jìn)程的規(guī)范優(yōu)先級(jí)等于99減去它的實(shí)時(shí)優(yōu)先級(jí)。在規(guī)范優(yōu)先級(jí)的數(shù)軸上，所有進(jìn)程都可以直接比較優(yōu)先級(jí)了，值越小優(yōu)先級(jí)越大。實(shí)時(shí)進(jìn)程的規(guī)范優(yōu)先級(jí)范圍是0-99，但是由于它是從用戶空間的優(yōu)先級(jí)計(jì)算而來的，所以99這個(gè)值就用不到。

最后是動(dòng)態(tài)優(yōu)先級(jí)，對(duì)進(jìn)程所有的處理都以動(dòng)態(tài)優(yōu)先級(jí)為準(zhǔn)，動(dòng)態(tài)優(yōu)先級(jí)默認(rèn)等于其規(guī)范優(yōu)先級(jí)。以前的時(shí)候調(diào)度算法會(huì)去調(diào)整進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)，現(xiàn)在不會(huì)再調(diào)了。現(xiàn)在只有使用了優(yōu)先級(jí)繼承鎖的時(shí)候才會(huì)去調(diào)整進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。

下面讓我們?cè)佼嬕粋€(gè)圖總結(jié)一下：

對(duì)于禁令調(diào)度類、限時(shí)調(diào)度類和閑時(shí)調(diào)度類，它們用不到進(jìn)程優(yōu)先級(jí)，但是系統(tǒng)在規(guī)范優(yōu)先級(jí)數(shù)軸上為它們提供了象征值，其動(dòng)態(tài)優(yōu)先級(jí)是對(duì)規(guī)范優(yōu)先級(jí)的復(fù)制，也只有象征意義。有一個(gè)特殊的情況是分時(shí)調(diào)度類里面的SCHED_IDLE調(diào)度策略的進(jìn)程，它的優(yōu)先級(jí)無法在規(guī)范優(yōu)先級(jí)數(shù)軸上體現(xiàn)出來，它的優(yōu)先級(jí)是在CFS算法專門處理的，直接設(shè)置的調(diào)度權(quán)重，相當(dāng)于是nice 26。

除了這些復(fù)雜的優(yōu)先級(jí)體系之外，ps和top命令下的優(yōu)先級(jí)體系也不相同。

ps命令優(yōu)先級(jí)：

cls代表的是調(diào)度策略，含義如下：

TS SCHED_OTHER/SCHED_NORMAL

FF SCHED_FIFO

RR SCHED_RR

B SCHED_BATCH

IDL SCHED_IDLE

DLN SCHED_DEADLINE

NI代表的是nice值，范圍：-20 – 19，-20最大，只有SCHED_NORMAL和SCHED_BATCH有意義。

RTPRIO代表的實(shí)時(shí)進(jìn)程的用戶空間優(yōu)先級(jí)，范圍：1 – 99，99最大，只有SCHED_FIFO和SCHED_RR有意義。

PRI，普通進(jìn)程 pri = 19 - nice, 實(shí)時(shí)進(jìn)程 pri = 40 + rtprio，值越大優(yōu)先級(jí)越大，普通進(jìn)程 0 – 39， 實(shí)時(shí)進(jìn)程 41 – 139。

top命令優(yōu)先級(jí)：

NI列是nice值，只對(duì)普通進(jìn)程有效，對(duì)其它進(jìn)程來說沒有意義。

PR，普通進(jìn)程 pr = 20 + nice，實(shí)時(shí)進(jìn)程 pr = -1 - rt，rt是實(shí)時(shí)進(jìn)程的用戶空間優(yōu)先級(jí)，PR值越小優(yōu)先級(jí)越大，普通進(jìn)程 0 – 39，實(shí)時(shí)進(jìn)程 -2 – -100，-100會(huì)顯示為rt，普通進(jìn)程大于等于0，實(shí)時(shí)進(jìn)程小于0。

2.7 進(jìn)程切換

選擇好下一個(gè)要執(zhí)行的進(jìn)程之后，就該切換進(jìn)程了。切換進(jìn)程一共分兩步：一是切換用戶空間，二是切換內(nèi)核棧。下面我們來看一下代碼(代碼經(jīng)過了高度刪減)：

其中switch_mm_irqs_off是切換用戶空間的，switch_to是切換內(nèi)核棧的。

我們繼續(xù)看切換用戶空間是如何執(zhí)行的。

linux-src/arch/x86/mm/tlb.c

void switch_mm_irqs_off(struct mm_struct *prev, struct mm_struct *next,      struct task_struct *tsk){  load_new_mm_cr3(next->pgd, new_asid, false);}
static void load_new_mm_cr3(pgd_t *pgdir, u16 new_asid, bool need_flush){  unsigned long new_mm_cr3;
  if (need_flush) {    invalidate_user_asid(new_asid);    new_mm_cr3 = build_cr3(pgdir, new_asid);  } else {    new_mm_cr3 = build_cr3_noflush(pgdir, new_asid);  }
  write_cr3(new_mm_cr3);}

linux-src/arch/x86/include/asm/special_insns.h

切換進(jìn)程地址空間就是給寄存器CR3賦予新的值。CR3中存放的是根頁表的物理地址，build_cr3會(huì)把虛擬地址轉(zhuǎn)化為物理地址。

下面我們繼續(xù)看內(nèi)核棧是如何切換的。

linux-src/arch/x86/include/asm/switch_to.h

#define switch_to(prev, next, last)          \do {                  \  ((last) = __switch_to_asm((prev), (next)));      \} while (0)

linux-src/arch/x86/entry/entry_64.S

切換內(nèi)核棧是內(nèi)核中最難理解的地方之一，難以理解的有兩點(diǎn)：一是進(jìn)程執(zhí)行是如何切換的；二是switch_to宏為何有三個(gè)參數(shù)，第三個(gè)參數(shù)為啥又是prev。

我們先來解釋第一個(gè)點(diǎn)，進(jìn)程執(zhí)行是如何切換的，先來畫個(gè)圖看一下：

如圖中所示一樣，每個(gè)線程都有一個(gè)線程棧，代表線程的執(zhí)行，CPU只有一個(gè)(線程切換前后是同一個(gè)CPU)。CPU在哪個(gè)線程棧上運(yùn)行，就是在運(yùn)行在哪個(gè)線程，而線程棧上記錄的就是線程的運(yùn)行信息，所以這個(gè)線程就可以繼續(xù)運(yùn)行下去了。如果從單個(gè)進(jìn)程的角度來看，從switch_to開始，我們的進(jìn)程就暫停運(yùn)行了，我們的進(jìn)程就一直在這等，等到我們被喚醒并調(diào)度執(zhí)行才會(huì)繼續(xù)走下去。如果從CPU的角度來看，switch_to切換了內(nèi)核棧，就在新的線程上運(yùn)行了，函數(shù)返回的時(shí)候就會(huì)按照內(nèi)核棧的調(diào)用地址返回，執(zhí)行的就是新的代碼了，就不是原來的代碼了。當(dāng)內(nèi)核棧不停地返回，就會(huì)返回到用戶空間，內(nèi)核棧的底部記錄的有用戶空間的調(diào)用信息，由于前面已經(jīng)切換了用戶空間，所以程序就能返回到之前用戶空間進(jìn)入內(nèi)核的地方。

我們?cè)賮碚f第二點(diǎn)，switch_to宏為啥有三個(gè)參數(shù)，為啥這么難以理解呢？這是因?yàn)閟witch_to實(shí)際上包含了三個(gè)進(jìn)程：一個(gè)是我們自己prev，一個(gè)是即將要切換的進(jìn)程next，一個(gè)是我們下次是從哪個(gè)進(jìn)程切換過來的，我們把這個(gè)進(jìn)程叫做from。而switch_to通過復(fù)用prev變量而把from變量給省略了，這就導(dǎo)致了理解上的混亂。我們來修改一下代碼，把switch_to宏給展開，并把prev改名為curr，把from變量也給顯式地定義出來，來看看效果怎么樣。

static __always_inline struct rq *context_switch(struct rq *rq, struct task_struct *curr,         struct task_struct *next, struct rq_flags *rf){  switch_mm_irqs_off(curr->active_mm, next->mm, next);
  struct task_struct *from = NULL;  from = __switch_to_asm(curr, next);  barrier();
  return finish_task_switch(from);}

這下就好理解多了。從單個(gè)進(jìn)程的角度來看，__switch_to_asm會(huì)切換到next進(jìn)程去執(zhí)行，我們的進(jìn)程就休眠了。很久以后我們的進(jìn)程醒來又重新開始執(zhí)行了，__switch_to_asm返回的是把CPU讓給我們的那個(gè)進(jìn)程。從CPU的角度來看__switch_to_asm函數(shù)前半程在curr進(jìn)程運(yùn)行，后半程在next進(jìn)程運(yùn)行。由于切換了內(nèi)核棧，所以from、curr、next這三個(gè)變量也變了，它們是不同棧上的同名的局部變量，它們的內(nèi)存地址是不一樣的。當(dāng)前進(jìn)程中的curr值會(huì)被作為next進(jìn)程中的from值返回，所以在next進(jìn)程中就知道了是從哪里切換過來的了。

__switch_to_asm中最關(guān)鍵的兩句代碼我們?cè)倌贸鰜矸治鲆幌隆?/p>

linux-src/arch/x86/entry/entry_64.S

linux-src/include/generated/asm-offsets.h

#define TASK_threadsp 3160 /* offsetof(struct task_struct, thread.sp) */

每個(gè)進(jìn)程的內(nèi)核棧的棧指針都在task_struct中的thread.sp保存著，第一個(gè)mov語句是把當(dāng)前進(jìn)程的棧指針保存起來以備后面使用，第二個(gè)mov語句是加載next進(jìn)程的棧指針，這條指令執(zhí)行之后就意味著進(jìn)程切換成功了。后面還有一些語句用來加載之前保存在棧上的寄存器信息。

如果大家對(duì)前面修改的代碼感興趣，想打log驗(yàn)證一下，可以參考下面我加的log。

這里面有兩個(gè)技巧，一是使用jiffies % 1000 == 0來減少log的數(shù)量，內(nèi)核中進(jìn)程切換非常頻繁，過多的log往往難以分析，二是使用1 == smp_processor_id()把log鎖定在一個(gè)CPU上，不然的話多個(gè)CPU上的切換log會(huì)相互干擾，難以理清，我們只看一個(gè)CPU上的log，就會(huì)發(fā)現(xiàn)邏輯很清晰。

下面我畫了一個(gè)圖模擬了一下單個(gè)CPU上的三個(gè)進(jìn)程之間的切換，大家來看一下：

有三個(gè)進(jìn)程pid 分別為1、3、5在CPU0上進(jìn)行切換，切換順序是1->3->5->1->5->3->1。圖中是按照我修改之后的代碼來畫的，有from、curr、next三個(gè)指針變量?？梢钥吹揭粋€(gè)進(jìn)程它必須先切走才能切回，因?yàn)椴磺凶咴趺茨芮谢貋砟?。但是?duì)于剛創(chuàng)建的進(jìn)程它是沒有切走過的，于是內(nèi)核會(huì)為它偽造內(nèi)核棧也就是切點(diǎn)，使得它可以切回。正常的內(nèi)核棧是__schedule函數(shù)調(diào)用了__switch_to_asm函數(shù)，__switch_to_asm函數(shù)還會(huì)返回到__schedule函數(shù)。偽造的內(nèi)核棧是仿佛ret_from_fork調(diào)用了__switch_to_asm函數(shù)，__switch_to_asm函數(shù)在返回的時(shí)候就會(huì)返回到ret_from_fork函數(shù)來執(zhí)行。對(duì)于內(nèi)核線程和普通線程偽造的棧上的數(shù)據(jù)是不一樣的，對(duì)于普通線程其rbx寄存器對(duì)應(yīng)的位置是0，對(duì)于內(nèi)核線程其rbx寄存器對(duì)應(yīng)的位置是入口函數(shù)的指針，具體來說是kthread。ret_from_fork先調(diào)用schedule_tail，然后根據(jù)rbx的不同，其為0時(shí)說明是普通進(jìn)程，調(diào)用syscall_exit_to_user_mode，不為0時(shí)說明是內(nèi)核線程，調(diào)用rbx也就是kthread。kthread函數(shù)一般是不會(huì)返回的，但是如果其中調(diào)用了kernel_execve建立了用戶空間也可以返回，返回到ret_from_fork中后會(huì)調(diào)用syscall_exit_to_user_mode。

對(duì)于這幅圖大家可以只看一個(gè)進(jìn)程的執(zhí)行情況，按照一個(gè)進(jìn)程pid從上往下看就可以了。也可以看整個(gè)CPU的執(zhí)行情況，按照紅色箭頭的標(biāo)號(hào)順序來看，注意觀察from、curr、next三個(gè)值的變化。

三、SMP管理

在繼續(xù)講解之前，我們先來說一下多CPU管理(這里的CPU是指邏輯CPU，在很多語境中CPU都是默認(rèn)指的邏輯CPU，物理CPU要特別強(qiáng)調(diào)是物理CPU)。最開始的時(shí)候計(jì)算機(jī)都是單CPU的，叫做UP(Uni-Processor)，操作系統(tǒng)也只支持UP。后來計(jì)算機(jī)慢慢發(fā)展成了多CPU(包括多物理CPU和多核技術(shù))，于是操作系統(tǒng)也要開始支持多CPU。支持多CPU的方式有兩種：一種是AMP(Aymmetrical Multi-Processing)非對(duì)稱多處理器，是指操作系統(tǒng)給每個(gè)CPU分配的工作任務(wù)不同，比如有的CPU專門運(yùn)行中斷，有的CPU專門運(yùn)行普通進(jìn)程，有的CPU專門運(yùn)行實(shí)時(shí)進(jìn)程；另一種是SMP(Symmetrical Multi-Processing)，操作系統(tǒng)對(duì)待每個(gè)CPU的方式都是一樣的，并不會(huì)把某個(gè)CPU拿來專門做啥任務(wù)，每個(gè)CPU都有可能處理任何類型的任務(wù)。由于AMP的性能和適應(yīng)性都不太好，所以現(xiàn)在流行的操作系統(tǒng)基本都是SMP的。對(duì)于SMP這個(gè)詞來說，在很長(zhǎng)的一段時(shí)間內(nèi)，它既是指CPU在邏輯上是對(duì)稱的(操作系統(tǒng)對(duì)待所有CPU的方式是一樣的)，也指CPU在物理上是對(duì)稱的(CPU在性能等所有方面都是一樣的)，因?yàn)楫?dāng)時(shí)的多CPU技術(shù)實(shí)現(xiàn)上每個(gè)邏輯CPU的性能等各方面都是相同的。但是后來多CPU技術(shù)的實(shí)現(xiàn)出現(xiàn)了HMP(Heterogeneous Multi-Processing)異構(gòu)多處理器，也就是大小核技術(shù)，不同的邏輯CPU它們的性能并不相同?，F(xiàn)在內(nèi)核同時(shí)支持SMP和HMP，因?yàn)閮烧卟⒉幻?，SMP指的是所有的CPU在邏輯上都是一樣的，每個(gè)CPU都有可能執(zhí)行任何類型的任務(wù)，HMP指的是不同的CPU它的能力大小不同，能力大的多干活，能力小的少干活。內(nèi)核選項(xiàng)CONFIG_SMP控制是否開啟SMP，如果不開啟的話就是UP，系統(tǒng)就只能在一個(gè)CPU上運(yùn)行。內(nèi)核選項(xiàng)CONFIG_ENERGY_MODEL控制是否開啟HMP，開啟了之后就可以為不同的設(shè)備建立不同的能耗模型，系統(tǒng)在分配任務(wù)就會(huì)以此為參考決定如何分配任務(wù)，達(dá)到效率更高或者更省電的目的。

3.1 CPU拓?fù)浣Y(jié)構(gòu)

我們先從發(fā)展的角度來看一看CPU的拓?fù)浣Y(jié)構(gòu)。最早的時(shí)候一個(gè)物理CPU就是一個(gè)邏輯CPU，一個(gè)邏輯CPU包含一個(gè)控制器、一個(gè)運(yùn)算器和一些寄存器，一個(gè)物理CPU包含一個(gè)裸芯片(Die)和外面的封裝(Package)。然后出現(xiàn)了多物理CPU，也就是一個(gè)主板上有多個(gè)CPU插槽，這樣計(jì)算機(jī)中就有多個(gè)CPU了。后來發(fā)現(xiàn)，沒必要做多個(gè)物理CPU啊，一個(gè)物理CPU(Package)包含多個(gè)裸芯片(Die)不也是多CPU嘛，省事又方便。后來又發(fā)現(xiàn)，多個(gè)裸芯片封裝在一起也很麻煩啊，直接在一個(gè)裸芯片上做多個(gè)邏輯CPU不是也可以嘛，更省事。從這之后x86和ARM的CPU做法就不一樣了。在x86上是一個(gè)裸芯片(Die)包含多個(gè)核(Core)，一個(gè)核(Core)上包含多個(gè)SMT(Simultaneous Multithreading)，SMT在Intel的文檔里叫做HT(Hyper-Threading)，SMT是最終的邏輯CPU。在ARM上是一個(gè)裸芯片(Die)包含多個(gè)核簇(Cluster)，一個(gè)核簇(Cluster)包含多個(gè)核(Core)。

3.2 CPUMASK

不同架構(gòu)的CPU，其邏輯CPU都有一個(gè)硬件ID，此ID一般是多個(gè)字段的組合。Linux為了方便管理CPU，提出了邏輯CPU的概念，此邏輯CPU的概念是指CPU的ID是邏輯的，從0來編號(hào)一直增長(zhǎng)的。內(nèi)核會(huì)把第一個(gè)啟動(dòng)的CPU作為CPU0，其它CPU的編號(hào)依次為CPU1，CPU2，……。內(nèi)核定義了結(jié)構(gòu)體cpumask來表示各個(gè)CPU編號(hào)的集合，cpumask是個(gè)bitmap，每一個(gè)bit可以代表一個(gè)CPU的某種狀態(tài)。內(nèi)核中定義了五個(gè)cpumask變量，用來表示不同狀態(tài)下的CPU集合。下面我們來看一下：

linux-src/include/linux/cpumask.h

typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;
extern struct cpumask __cpu_possible_mask;extern struct cpumask __cpu_online_mask;extern struct cpumask __cpu_present_mask;extern struct cpumask __cpu_active_mask;extern struct cpumask __cpu_dying_mask;#define cpu_possible_mask ((const struct cpumask *)&__cpu_possible_mask)#define cpu_online_mask   ((const struct cpumask *)&__cpu_online_mask)#define cpu_present_mask  ((const struct cpumask *)&__cpu_present_mask)#define cpu_active_mask   ((const struct cpumask *)&__cpu_active_mask)#define cpu_dying_mask    ((const struct cpumask *)&__cpu_dying_mask)

linux-src/kernel/cpu.c

cpu_possible_mask代表的是操作系統(tǒng)最多能支持的CPU，cpu_present_mask代表的是計(jì)算機(jī)上存在的CPU，cpu_online_mask代表的是已經(jīng)上線的CPU，cpu_active_mask代表的是未被隔離可以參與調(diào)度的CPU，cpu_dying_mask代表的是處于熱下線過程中的CPU。

四、基本分時(shí)調(diào)度

Linux上的分時(shí)調(diào)度算法叫CFS(Completely Fair Scheduler)完全公平調(diào)度。它是內(nèi)核核心開發(fā)者Ingo Molnar基于SD調(diào)度器和RSDL調(diào)度器的公平調(diào)度思想而開發(fā)的一款調(diào)度器，在版本2.6.23中合入內(nèi)核。CFS只負(fù)責(zé)調(diào)度普通進(jìn)程，包括三個(gè)調(diào)度策略NORMAL、BATCH、IDLE。

我們這章只講單個(gè)CPU上的調(diào)度，多CPU之間的調(diào)度均衡在下一章講。

4.1 CFS調(diào)度模型

內(nèi)核文檔對(duì)CFS的定義是：CFS在真實(shí)的硬件上基本模擬了完全理想的多任務(wù)處理器。完全理想的多任務(wù)處理器是指，如果把CPU的執(zhí)行能力看成是100%，則N個(gè)進(jìn)程可以同時(shí)并行執(zhí)行，每個(gè)進(jìn)程獲得了1/N的CPU執(zhí)行能力。例如有2個(gè)進(jìn)程在2GHz的CPU上執(zhí)行了20ms，則每個(gè)進(jìn)程都以1GHz的速度執(zhí)行了20ms。

通過CFS的定義很難理解CFS的操作邏輯是什么。我看了很多CFS的博客，也認(rèn)真看了很多遍CFS的代碼，雖然自己心里明白了其中的意思，但是想要給別人說清楚CFS的操作邏輯還是很難。后來我靈光乍現(xiàn)，突然想到了一個(gè)很好的類比場(chǎng)景，把這個(gè)場(chǎng)景稍微改造一下，就可以打造一個(gè)非常完美的CFS調(diào)度模型，可以讓任何人都能理解CFS的操作邏輯。大家有沒有這種生活體驗(yàn)，夏天的時(shí)候三四個(gè)好友一起去擼串，吃完準(zhǔn)備走的時(shí)候發(fā)現(xiàn)有一瓶啤酒打開了還沒喝。此時(shí)我們會(huì)把這瓶啤酒平分了，具體怎么分呢，比如三個(gè)人分，你不可能一次分完，每個(gè)杯子正好倒三分之一。我們一般會(huì)每個(gè)杯子先倒個(gè)差不多，然后再把剩余的啤酒來回往各個(gè)杯子里面倒，這樣啤酒就會(huì)分的比較均勻了。也許你沒經(jīng)歷過這樣的場(chǎng)景，或者認(rèn)為啤酒隨便分就可以了，沒必要分那么細(xì)。接下來還有一個(gè)場(chǎng)景更生動(dòng)。你有沒有經(jīng)歷過或者見過長(zhǎng)輩們喝白酒劃拳的，此時(shí)一般都會(huì)拿出5到10個(gè)小酒盅，先把每個(gè)酒盅都倒個(gè)差不多，然后再來回地往各個(gè)酒盅里面倒一點(diǎn)，還會(huì)去比較酒盅液面的高低，優(yōu)先往液面低的杯子里面倒。如果你見過或者經(jīng)歷過這種場(chǎng)景，那么接下來的模型就很好理解了。

我們對(duì)倒白酒的這個(gè)場(chǎng)景進(jìn)行改造，把它變成一個(gè)實(shí)驗(yàn)臺(tái)。首先把酒盅變成細(xì)長(zhǎng)(而且非常長(zhǎng))的玻璃杯，再把倒白酒的瓶子變成水龍頭，能無限出水的水龍頭，有一個(gè)桌子可以用來擺放所有的玻璃杯。我們一次只能拿著一個(gè)玻璃杯放到水龍頭下接水。然后向你提出了第一個(gè)要求，在任意時(shí)刻所有的玻璃杯的水位高度都要相同或者盡量相同，越接近越好。此時(shí)你會(huì)怎么辦，肯定是不停地切換玻璃杯啊，越快越好，一個(gè)玻璃杯接一滴水就立馬換下一個(gè)。但是這立馬會(huì)迎來第二個(gè)問題，切換玻璃杯的過程水龍頭的水會(huì)流到地上，過于頻繁的切換玻璃杯會(huì)浪費(fèi)大量的水。向你提出的第二個(gè)要求就是要盡量地少浪費(fèi)水，你該怎么辦，那肯定是減少玻璃杯的切換啊。但是減少玻璃杯的切換又會(huì)使得不同玻璃杯的水位差變大，這真是一個(gè)兩難的選擇。對(duì)此我們只能進(jìn)行折中，切換玻璃杯的頻率不能太大也不能太小，太大浪費(fèi)水，太小容易水位不均。

我們繼續(xù)對(duì)這個(gè)模型進(jìn)行完善。為了減少水位差我們每次都要去拿水位最低的，怎么能最快的時(shí)間拿到最低的玻璃杯呢，肯定是把水杯按照從高到底的順序排列好，我們直接去拿第一個(gè)就好了。玻璃杯代表的是進(jìn)程，不同進(jìn)程的優(yōu)先級(jí)不同，分到的CPU時(shí)間片也不同，為此我們讓不同的玻璃杯有不同的粗細(xì)，這樣比較粗的玻璃杯就能分到更多的水，因?yàn)槲覀冊(cè)诒M量保證它們的水位相同，橫截面積大的玻璃杯就會(huì)占優(yōu)勢(shì)。進(jìn)程有就緒、阻塞、運(yùn)行等狀態(tài)，為此我們?cè)诓ＡП厦婕觽€(gè)蓋子，蓋子有時(shí)候是打開的，有時(shí)候是關(guān)閉的。蓋子關(guān)閉的時(shí)候玻璃杯是沒法接水的，因此我們把它放到一邊，直到有人把它的蓋子打開我們?cè)侔阉诺阶雷由稀?/p>

說到這里，大家在腦海里對(duì)這個(gè)模型應(yīng)該已經(jīng)有個(gè)大概的輪廓了，下面我們畫圖來看一下：

我們繼續(xù)講解這個(gè)圖。我們每次都是從隊(duì)首拿過來一個(gè)玻璃杯開始接水。在接水的過程中有兩種情況可能會(huì)發(fā)生：一是一直接水直到此次接水的份額已經(jīng)滿了，我們把這個(gè)玻璃杯再放回到隊(duì)列中去，由于此時(shí)玻璃杯剛接了不少水，水位比較高，所以會(huì)排的比較靠后；二是接水的過程中，瓶蓋突然關(guān)閉了，這時(shí)就沒法再接水了，我們把玻璃杯送到某個(gè)Wait Box中去，等待某個(gè)事件的發(fā)生。某個(gè)事件發(fā)生之后會(huì)把對(duì)應(yīng)的Wait Box中的一個(gè)或者多個(gè)玻璃杯的瓶蓋打開，然后此玻璃杯就會(huì)被送到Ready Table上。玻璃杯被送到Ready Table并不是隨便一放就行了，也是要參與排序的。大家從圖中可以看到，Wait Box中的玻璃杯的水位都比較低，這是因?yàn)镽eady Table上的玻璃杯一直在接水，水位肯定會(huì)漲的很高，相應(yīng)的Wait Box中的水位就低了。因此WaitBox中的玻璃杯被喚醒放到ReadyTable上基本都能排第一，這也是好事，讓休眠時(shí)間長(zhǎng)的進(jìn)程能迅速得到執(zhí)行。但是這里面也存在一個(gè)問題，就是剛開蓋的玻璃杯水位太低了，它就能一直得到執(zhí)行，這對(duì)其它玻璃杯來說是不公平的。因此ReadyTable上放了一個(gè)最低水位記錄，剛開蓋的玻璃瓶如果水位比這個(gè)值低，我們就往這個(gè)玻璃瓶中填充泡沫，使得它的水位看起來和這個(gè)最低水位記錄一樣高。這樣新開蓋的玻璃杯既能優(yōu)先接水，又不能過分占便宜，非常好。最低水位記錄的值也會(huì)一直更新的，正在接水的玻璃杯每次離開的時(shí)候都會(huì)更新一下這個(gè)最低水位記錄。

現(xiàn)在我們對(duì)這個(gè)玻璃杯接水模型的邏輯已經(jīng)非常清楚了，下面我們一步一步把它和CFS的代碼對(duì)應(yīng)起來，你會(huì)發(fā)現(xiàn)契合度非常高。

4.2 CFS運(yùn)行隊(duì)列

所有的就緒進(jìn)程都要在ReadyTable上按照水位高低排成一排，那么這個(gè)隊(duì)列用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)呢？先想一下這個(gè)隊(duì)列都有什么需求，首先這個(gè)隊(duì)列是排序的，其次我們經(jīng)常對(duì)這個(gè)隊(duì)列進(jìn)程插入和刪除操作。因此我們可以想到用紅黑樹來實(shí)現(xiàn)，因?yàn)榧t黑樹首先是一顆二叉搜索樹，是排序的，其次紅黑樹是平衡的，其插入和刪除操作的效率都是O(logn)，非常高效。所以CFS的運(yùn)行隊(duì)列就是用紅黑樹來實(shí)現(xiàn)的。

下面我們來看一下CFS運(yùn)行隊(duì)列的代碼：

linux-src/kernel/sched/sched.h

struct cfs_rq {  struct load_weight  load;  unsigned int    nr_running;  unsigned int    h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */  unsigned int    idle_h_nr_running; /* SCHED_IDLE */
  u64      exec_clock;  u64      min_vruntime;
  struct rb_root_cached  tasks_timeline;
  struct sched_entity  *curr;  struct sched_entity  *next;  struct sched_entity  *last;  struct sched_entity  *skip;

#ifdef CONFIG_SMP  struct sched_avg  avg;  struct {    raw_spinlock_t  lock ____cacheline_aligned;    int    nr;    unsigned long  load_avg;    unsigned long  util_avg;    unsigned long  runnable_avg;  } removed;#endif /* CONFIG_SMP */};

字段tasks_timeline就是所有分時(shí)進(jìn)程所排隊(duì)的隊(duì)列，類型rb_root_cached就是內(nèi)核中紅黑樹的實(shí)現(xiàn)，curr就是當(dāng)前正在CPU上運(yùn)行的進(jìn)程。還有一些其它字段我們?cè)谥v到時(shí)再進(jìn)行解說。進(jìn)程在紅黑樹中排隊(duì)的鍵值是虛擬運(yùn)行時(shí)間vruntime，這個(gè)在4.5節(jié)中講解。

4.3 進(jìn)程狀態(tài)表示

我們知道進(jìn)程在運(yùn)行的時(shí)候一直是在阻塞、就緒、執(zhí)行三個(gè)狀態(tài)來回轉(zhuǎn)換，如下圖所示：

但是Linux中對(duì)進(jìn)程運(yùn)行狀態(tài)的定義卻和標(biāo)準(zhǔn)的操作系統(tǒng)理論不同。

Linux中的定義如下(刪減了一些狀態(tài))：

linux-src/include/linux/sched.h

在Linux中就緒和執(zhí)行都用TASK_RUNNING來表示，這讓人很疑惑。但是用我們的模型圖來看，這一點(diǎn)卻很好理解，因?yàn)榫途w和執(zhí)行它們都是開蓋的，狀態(tài)一樣，區(qū)別它們的方法是玻璃杯有沒有放在水龍頭下接水，而Linux中也是利用這一點(diǎn)來判斷的。如下代碼所示：

linux-src/kernel/sched/sched.h

static inline int task_current(struct rq *rq, struct task_struct *p){  return rq->curr == p;}
static inline int task_running(struct rq *rq, struct task_struct *p){#ifdef CONFIG_SMP  return p->on_cpu;#else  return task_current(rq, p);#endif}

linux-src/include/linux/sched.h

注意task_is_running和task_running兩者之間的不同，前者判斷的是狀態(tài)字段，代表進(jìn)程處于就緒或者執(zhí)行態(tài)，后者判斷的是進(jìn)程是否處于執(zhí)行態(tài)。

表示進(jìn)程處于阻塞態(tài)的狀態(tài)有兩個(gè)：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。TASK_UNINTERRUPTIBLE表示只有WaitBox對(duì)應(yīng)的事件能把玻璃杯的蓋子打開，其它人誰也打不開。TASK_INTERRUPTIBLE表示除了WaitBox對(duì)應(yīng)的事件之外，信號(hào)(signal)也能把蓋子打開。關(guān)于信號(hào)請(qǐng)參看《深入理解Linux信號(hào)機(jī)制》。

4.4 優(yōu)先級(jí)與權(quán)重

我們?cè)谇懊嬷v過進(jìn)程的優(yōu)先級(jí)，這里只講分時(shí)進(jìn)程的優(yōu)先級(jí)。優(yōu)先級(jí)是如何影響進(jìn)程獲得CPU時(shí)間的多少呢？?jī)?yōu)先級(jí)會(huì)轉(zhuǎn)化為進(jìn)程的權(quán)重，進(jìn)程的權(quán)重也就是玻璃杯的粗細(xì)。橫截面積大的玻璃杯，接收同樣容積的水，它的水位增加就比較小，就容易排到隊(duì)列的前面去，就比較容易獲得調(diào)度。在一段時(shí)間后，所有玻璃杯的水位高度都比較接近，同樣的水位高度，橫截面積大的玻璃杯裝的水就多，也就是進(jìn)程獲得的CPU時(shí)間比較多。

進(jìn)程(線程)的相關(guān)信息是記錄在task_struct中的，內(nèi)核又把和分時(shí)調(diào)度相關(guān)的一些信息抽出來組成了結(jié)構(gòu)體sched_entity，然后把sched_entity內(nèi)嵌到task_struct當(dāng)中，sched_entity中包含有權(quán)重信息的記錄。下面我們來看一下。

linux-src/include/linux/sched.h

struct task_struct {  struct sched_entity    se;}
struct sched_entity {  /* For load-balancing: */  struct load_weight    load;  struct rb_node      run_node;  struct list_head    group_node;  unsigned int      on_rq;
  u64        exec_start;  u64        sum_exec_runtime;  u64        vruntime;  u64        prev_sum_exec_runtime;
  u64        nr_migrations;
  struct sched_statistics    statistics;
#ifdef CONFIG_FAIR_GROUP_SCHED  int        depth;  struct sched_entity    *parent;  /* rq on which this entity is (to be) queued: */  struct cfs_rq      *cfs_rq;  /* rq 'owned' by this entity/group: */  struct cfs_rq      *my_q;  /* cached value of my_q->h_nr_running */  unsigned long      runnable_weight;#endif
#ifdef CONFIG_SMP  /*   * Per entity load average tracking.   *   * Put into separate cache line so it does not   * collide with read-mostly values above.   */  struct sched_avg    avg;#endif};
struct load_weight {  unsigned long      weight;  u32        inv_weight;};

可以看到load_weight中有兩個(gè)字段：weight和inv_weight。weight代表的是權(quán)重，inv_weight是為了方便weight參與除法運(yùn)算時(shí)而添加的，它可以把對(duì)weight的除法運(yùn)算轉(zhuǎn)化為對(duì)inv_weight的乘法運(yùn)算。inv_weight = 232/weight，當(dāng)需要除以weight的時(shí)候，你只需要乘以inv_weight然后再右移32就可以了。inv_weight的值可以提前算出來保存在數(shù)組里，右移操作是個(gè)效率很高的操作，這樣就提高了權(quán)重相關(guān)的運(yùn)算效率。下面我們先來看一下weight的值是怎么來的。

nice值的范圍是-20到19，是等差數(shù)列，轉(zhuǎn)化之后的權(quán)重是等比數(shù)列，以nice 0作為權(quán)重1024，公比為0.8。之前的調(diào)度算法都是把nice值轉(zhuǎn)化為等差數(shù)列的時(shí)間片或者多段等差數(shù)列的時(shí)間片，為何CFS要把這個(gè)轉(zhuǎn)換變?yōu)榈缺葦?shù)列呢？這是因?yàn)槿藗兲烊坏貙?duì)相對(duì)值比較敏感而不是對(duì)絕對(duì)值比較敏感，比如你工資兩千的時(shí)候漲薪200和工資兩萬的時(shí)候漲薪200，心情絕對(duì)是不一樣的。如果系統(tǒng)中只有兩個(gè)進(jìn)程，nice值分別為0和1，時(shí)間片分別為200ms和195ms，幾乎沒啥區(qū)別，但是當(dāng)nice值分為18和19的時(shí)候，時(shí)間片分別為10ms和5ms，兩者的時(shí)間差達(dá)到了一倍，同樣是nice值相差1，它們的時(shí)間差的比例卻如此之大，是讓人無法接受的。因此把nice值轉(zhuǎn)化為等比數(shù)列的權(quán)重，再按照權(quán)重去分配CPU時(shí)間是比較合理的。那么公比為何是0.8呢？這是為了讓兩個(gè)nice值只相差1的進(jìn)程獲得的CPU時(shí)間比例差為10%。我們用等式來計(jì)算一下，假設(shè)x、y是權(quán)重，y對(duì)應(yīng)的nice值比x大1，我們希望 x/(x+y) - y/(x+y) = 10%，我們做一下運(yùn)算，看看y與x的比值是多少。

x/(x+y) - y/(x+y) = 10%

(x-y)/(x+y) = 0.1

x-y = 0.1x + 0.1y

0.9x = 1.1y

y/x = 0.9/1.1

y/x = 0.818181

y/x ≈ 0.8

那么為什么把nice 0 作為權(quán)重1024來進(jìn)行轉(zhuǎn)換呢？這是為了二進(jìn)制運(yùn)算方便。內(nèi)核里并不是每次優(yōu)先級(jí)轉(zhuǎn)權(quán)重都進(jìn)行運(yùn)算，而是提前運(yùn)算好了放在數(shù)組，每次用的時(shí)候查一下就可以了。反權(quán)重的值也提前計(jì)算好了放在了數(shù)組里。下面我們來看一下：

linux-src/kernel/sched/core.c

Nice值從-20到19一共40個(gè)數(shù)，一排5個(gè)權(quán)重值，五八四十正好40個(gè)權(quán)重值?？梢钥吹綑?quán)重?cái)?shù)列的公比并不是標(biāo)準(zhǔn)的0.8，而是作者以0.8為基準(zhǔn)從nice 0開始計(jì)算，之后又進(jìn)行了一些調(diào)整，主要是為了方便計(jì)算。

下面我們?cè)賮砜匆幌略O(shè)置進(jìn)程權(quán)重的函數(shù)：

linux-src/kernel/sched/core.c

static void set_load_weight(struct task_struct *p, bool update_load){  int prio = p->static_prio - MAX_RT_PRIO;  struct load_weight *load = &p->se.load;
  /*   * SCHED_IDLE tasks get minimal weight:   */  if (task_has_idle_policy(p)) {    load->weight = scale_load(WEIGHT_IDLEPRIO);    load->inv_weight = WMULT_IDLEPRIO;    return;  }
  /*   * SCHED_OTHER tasks have to update their load when changing their   * weight   */  if (update_load && p->sched_class == &fair_sched_class) {    reweight_task(p, prio);  } else {    load->weight = scale_load(sched_prio_to_weight[prio]);    load->inv_weight = sched_prio_to_wmult[prio];  }}

我們先看第一行，prio = p->static_prio - MAX_RT_PRIO，由于static_prio = nice + 120，所以prio = nice + 20，nice的范圍是 -20 - 19，所以prio的范圍是 0 - 39，正好可以作為sched_prio_to_weight數(shù)組的下標(biāo)。然后代碼對(duì)SCHED_IDLE調(diào)度策略的進(jìn)程進(jìn)行了特殊處理，直接設(shè)置其權(quán)重為3，相當(dāng)于是nice 26，反權(quán)重值也直接進(jìn)行了設(shè)置。SCHED_IDLE進(jìn)程的權(quán)重特別小意味其分到的CPU時(shí)間會(huì)相當(dāng)?shù)纳?，正好符合這個(gè)調(diào)度策略的本意。scale_load和scale_load_down是對(duì)權(quán)重進(jìn)行縮放，在32位系統(tǒng)上它們是空操作，在64位系統(tǒng)上它們是放大1024倍和縮小1024倍，主要是為了在運(yùn)算時(shí)提高精度，不影響權(quán)重的邏輯。所以在后文中為了敘述方便，我們直接忽略scale_load和scale_load_down。接著往下看，update_load參數(shù)會(huì)影響代碼的流程，當(dāng)進(jìn)程是新fork時(shí)update_load為false，會(huì)走下面的流程直接設(shè)置權(quán)重和反權(quán)重，當(dāng)用戶空間修改進(jìn)程優(yōu)先級(jí)時(shí)update_load為true，會(huì)走上面的流程調(diào)用reweight_task，reweight_task也會(huì)設(shè)置進(jìn)程的權(quán)重，同時(shí)也會(huì)修改運(yùn)行隊(duì)列的權(quán)重。

運(yùn)行隊(duì)列的權(quán)重等于其上所有進(jìn)程的權(quán)重之和。進(jìn)程在入隊(duì)出隊(duì)時(shí)也會(huì)相應(yīng)地從運(yùn)行隊(duì)列中加上減去其自身的權(quán)重。

下面我們來看一下代碼(經(jīng)過高度刪減)：

linux-src/kernel/sched/fair.c

可以看到運(yùn)行隊(duì)列的總權(quán)重和其進(jìn)程數(shù)量是同步更新的。

4.5 虛擬運(yùn)行時(shí)間

我們?cè)賮砜匆幌虏ＡП乃皇侨绻硎镜?。玻璃杯的水位就是進(jìn)程的虛擬運(yùn)行時(shí)間，是進(jìn)程進(jìn)行排隊(duì)的鍵值。玻璃杯的水位等于玻璃杯中水的體積除以玻璃杯的橫截面積，進(jìn)程的虛擬運(yùn)行時(shí)間等于進(jìn)程的實(shí)際運(yùn)行時(shí)間除以相對(duì)權(quán)重。進(jìn)程的實(shí)際運(yùn)行時(shí)間是一段一段的，所以進(jìn)程的虛擬運(yùn)行時(shí)間也是一段一段增長(zhǎng)的。進(jìn)程的虛擬運(yùn)行時(shí)間還會(huì)在進(jìn)程入隊(duì)時(shí)與運(yùn)行隊(duì)列的最小虛擬時(shí)間相比較，如果小的話會(huì)直接進(jìn)行增加，并不對(duì)應(yīng)實(shí)際的運(yùn)行時(shí)間。這也就是我們前面說的對(duì)玻璃杯進(jìn)行填充泡沫的操作。相對(duì)權(quán)重是相對(duì)于nice 0的權(quán)重，所以nice 0的進(jìn)程其虛擬運(yùn)行時(shí)間和實(shí)際運(yùn)行時(shí)間是一致的。但是這種一致只是某一段時(shí)間中的一致，因?yàn)樘摂M運(yùn)行時(shí)間在進(jìn)程入隊(duì)時(shí)可能會(huì)空跳。在更新進(jìn)程的真實(shí)虛擬運(yùn)行時(shí)間的時(shí)候也會(huì)去更新運(yùn)行隊(duì)列的最小運(yùn)行時(shí)間記錄，使得運(yùn)行隊(duì)列的最小運(yùn)行時(shí)間也在一直增長(zhǎng)著。

進(jìn)程的虛擬運(yùn)行時(shí)間保存在task_struct中的sched_entity中的vruntime字段。運(yùn)行隊(duì)列的最小虛擬運(yùn)行時(shí)間保證在cfs_rq的min_vruntime字段。下面我們來看一下它們的更新方法。

linux-src/kernel/sched/fair.c

static void update_curr(struct cfs_rq *cfs_rq){  struct sched_entity *curr = cfs_rq->curr;  u64 now = rq_clock_task(rq_of(cfs_rq));  u64 delta_exec;
  if (unlikely(!curr))    return;
  delta_exec = now - curr->exec_start;  if (unlikely((s64)delta_exec <= 0))    return;
  curr->exec_start = now;
  schedstat_set(curr->statistics.exec_max,          max(delta_exec, curr->statistics.exec_max));
  curr->sum_exec_runtime += delta_exec;  schedstat_add(cfs_rq->exec_clock, delta_exec);
  curr->vruntime += calc_delta_fair(delta_exec, curr);  update_min_vruntime(cfs_rq);
  if (entity_is_task(curr)) {    struct task_struct *curtask = task_of(curr);
    trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);    cgroup_account_cputime(curtask, delta_exec);    account_group_exec_runtime(curtask, delta_exec);  }
  account_cfs_rq_runtime(cfs_rq, delta_exec);}
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se){  if (unlikely(se->load.weight != NICE_0_LOAD))    delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
  return delta;}
/* * delta_exec * weight / lw.weight *   OR * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT * * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case * we're guaranteed shift stays positive because inv_weight is guaranteed to * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22. * * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus * weight/lw.weight <= 1, and therefore our shift will also be positive. */static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw){  u64 fact = scale_load_down(weight);  u32 fact_hi = (u32)(fact >> 32);  int shift = WMULT_SHIFT;  int fs;
  __update_inv_weight(lw);
  if (unlikely(fact_hi)) {    fs = fls(fact_hi);    shift -= fs;    fact >>= fs;  }
  fact = mul_u32_u32(fact, lw->inv_weight);
  fact_hi = (u32)(fact >> 32);  if (fact_hi) {    fs = fls(fact_hi);    shift -= fs;    fact >>= fs;  }
  return mul_u64_u32_shr(delta_exec, fact, shift);}

update_curr只能更新運(yùn)行隊(duì)列的當(dāng)前進(jìn)程，如果進(jìn)程不在運(yùn)行，沒有實(shí)際運(yùn)行時(shí)間就沒有對(duì)應(yīng)的虛擬運(yùn)行時(shí)間。函數(shù)首先獲取了當(dāng)前時(shí)間now，然后用當(dāng)前時(shí)間減去進(jìn)程此次開始執(zhí)行的時(shí)間exec_start，就得到了進(jìn)程此次運(yùn)行的實(shí)際時(shí)間delta_exec。進(jìn)程的exec_start是在進(jìn)程即將獲取CPU的時(shí)候設(shè)置的，具體來說是調(diào)度流程中的pick_next_task設(shè)置的。然后再通過函數(shù)calc_delta_fair把實(shí)際運(yùn)行時(shí)間轉(zhuǎn)化為虛擬運(yùn)行時(shí)間，把得到的結(jié)果加到進(jìn)程的vruntime上。calc_delta_fair中對(duì)nice 0的進(jìn)程直接返回實(shí)際運(yùn)行時(shí)間，對(duì)于其它進(jìn)程則調(diào)用__calc_delta進(jìn)行運(yùn)算。__calc_delta使用了一些復(fù)雜的數(shù)學(xué)運(yùn)算技巧，比較難以理解，但是其邏輯是清晰的，就是虛擬運(yùn)行時(shí)間等于實(shí)際運(yùn)行時(shí)間乘以NICE_0_LOAD與進(jìn)程權(quán)重的比值(delta_exec * weight / lw.weight)。接著就是更新運(yùn)行隊(duì)列的最小虛擬時(shí)間記錄了，再往下是一些統(tǒng)計(jì)代碼就不講了。我們來看一下最小虛擬時(shí)間的更新。

linux-src/kernel/sched/fair.c

此代碼的邏輯是先在當(dāng)前進(jìn)程的vruntime和隊(duì)首進(jìn)程的vruntime之間選擇一個(gè)最小值，如果此值大于原先的min_vruntime，就更新cfs_rq->min_vruntime為此值。

update_curr的調(diào)用時(shí)機(jī)都有哪些？下面我們來一一說明一下：

1. 定時(shí)器中斷，更新當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間，只有更新了之后才知道當(dāng)前進(jìn)程的時(shí)間片有沒有用完。

2.喚醒搶占時(shí)，也要更新當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間，只有更新了之后才能正確判斷是否能搶占。

3.進(jìn)程被搶占離開CPU時(shí)，從觸發(fā)搶占到執(zhí)行搶占還有一段時(shí)間，需要更新一下虛擬運(yùn)行時(shí)間。

4.進(jìn)程阻塞離開CPU時(shí)，需要更新一下虛擬運(yùn)行時(shí)間。

5.主動(dòng)讓出CPU時(shí)，通過sched_yield讓出CPU時(shí)更新一下虛擬運(yùn)行時(shí)間。

6.當(dāng)前進(jìn)程更改優(yōu)先級(jí)時(shí)，更改優(yōu)先級(jí)會(huì)改變權(quán)重，對(duì)已經(jīng)運(yùn)行的時(shí)間先更新一下虛擬運(yùn)行時(shí)間。

7.執(zhí)行fork時(shí)，子進(jìn)程會(huì)繼承父進(jìn)程的vruntime，因此要更新一下父進(jìn)程的vruntime。

8.用戶空間定時(shí)器要統(tǒng)計(jì)進(jìn)程的運(yùn)行時(shí)間時(shí)。

9.調(diào)度均衡中遷移線程時(shí)入隊(duì)和出隊(duì)的隊(duì)列都要調(diào)用update_curr，目的是為了更新min_vruntime，因?yàn)楸贿w移的線程要減去舊隊(duì)列的min_vruntime，加上新隊(duì)列的min_vruntime，所以min_vruntime的要是最新的才好。

4.6 調(diào)度周期與粒度

在以往的調(diào)度算法中，都會(huì)有明確的調(diào)度周期和時(shí)間片的概念。比如說以1秒為一個(gè)調(diào)度周期，把1秒按照進(jìn)程的優(yōu)先級(jí)分成時(shí)間片分給各個(gè)進(jìn)程。進(jìn)程在運(yùn)行的過程中時(shí)間片不斷地減少，當(dāng)減到0的時(shí)候就不再參與調(diào)度了。當(dāng)所有進(jìn)程的時(shí)間片都減到0的時(shí)候，再重新開啟一個(gè)調(diào)度周期，重新分配時(shí)間片。對(duì)于在一個(gè)調(diào)度周期內(nèi)突然創(chuàng)建或者喚醒的進(jìn)程，還要進(jìn)行特殊的處理。在CFS中，你會(huì)發(fā)現(xiàn)好像沒有調(diào)度周期和時(shí)間片的概念了，但是又好像有。沒有，是因?yàn)闆]有統(tǒng)一分配時(shí)間片的地方了，也沒有時(shí)間片遞減的邏輯了。有，是因?yàn)榇a中還有調(diào)度周期和時(shí)間片的函數(shù)和變量。

在CFS調(diào)度模型中玻璃杯的水位是一直在增長(zhǎng)的，沒有時(shí)間片遞減的邏輯，也不存在什么調(diào)度周期。但是一個(gè)玻璃杯總是不能一直接水的，接水時(shí)間長(zhǎng)了也是要把切走的。在CFS中玻璃杯一次接水的最大量就叫做時(shí)間片。這個(gè)時(shí)間片和傳統(tǒng)的時(shí)間片是不一樣的，這個(gè)時(shí)間片是個(gè)檢測(cè)量，沒有遞減的邏輯。那么時(shí)間片是怎么計(jì)算的呢？這就和調(diào)度周期有關(guān)，CFS的調(diào)度周期也和傳統(tǒng)的調(diào)度周期不一樣，CFS的調(diào)度周期僅僅是一個(gè)計(jì)算量。調(diào)度周期的計(jì)算又和調(diào)度粒度有關(guān)。調(diào)度粒度是指玻璃杯一次接水的最小量，也就是進(jìn)程在CPU上至少要運(yùn)行多少時(shí)間才能被搶占。調(diào)度粒度指的是被動(dòng)調(diào)度中進(jìn)程一次運(yùn)行最少的時(shí)間，如果進(jìn)程阻塞發(fā)生主動(dòng)調(diào)度，不受這個(gè)限制。時(shí)間片的計(jì)算依賴調(diào)度周期，調(diào)度周期的計(jì)算依賴調(diào)度粒度，所以我們就先來講講調(diào)度粒度。

內(nèi)核中定義了sysctl_sched_min_granularity，代表調(diào)度粒度，默認(rèn)值是0.75毫秒，但這并不最終使用的值，系統(tǒng)在啟動(dòng)的時(shí)候還會(huì)對(duì)這個(gè)變量進(jìn)行賦值。我們來看一下代碼。

linux-src/kernel/sched/fair.c

unsigned int sysctl_sched_tunable_scaling = SCHED_TUNABLESCALING_LOG;
unsigned int sysctl_sched_min_granularity      = 750000ULL;static unsigned int normalized_sysctl_sched_min_granularity  = 750000ULL;
unsigned int sysctl_sched_latency      = 6000000ULL;static unsigned int normalized_sysctl_sched_latency  = 6000000ULL;static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_wakeup_granularity      = 1000000UL;static unsigned int normalized_sysctl_sched_wakeup_granularity  = 1000000UL;
void __init sched_init_granularity(void){  update_sysctl();}
static void update_sysctl(void){  unsigned int factor = get_update_sysctl_factor();
  sysctl_sched_min_granularity = factor * normalized_sysctl_sched_min_granularity;  sysctl_sched_latency = factor * normalized_sysctl_sched_latency;  sysctl_sched_wakeup_granularity = factor * normalized_sysctl_sched_wakeup_granularity;}
static unsigned int get_update_sysctl_factor(void){  unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);  unsigned int factor;
  switch (sysctl_sched_tunable_scaling) {  case SCHED_TUNABLESCALING_NONE:    factor = 1;    break;  case SCHED_TUNABLESCALING_LINEAR:    factor = cpus;    break;  case SCHED_TUNABLESCALING_LOG:  default:    factor = 1 + ilog2(cpus);    break;  }
  return factor;}

從代碼中可以看出，調(diào)度粒度、喚醒粒度、調(diào)度延遲都是其規(guī)范值乘以一個(gè)因子。這個(gè)因子的值有三種可能：一是固定等于1，二是等于CPU的個(gè)數(shù)，三是等于1加上CPU個(gè)數(shù)對(duì)2的對(duì)數(shù)。具體使用哪種情況由變量sysctl_sched_tunable_scaling的值決定，此變量的值可以通過文件/sys/kernel/debug/sched/tunable_scaling來改變，默認(rèn)值是SCHED_TUNABLESCALING_LOG。我們以8核CPU為例(下文也是如此)，factor的值就是4，因此默認(rèn)的調(diào)度粒度就是0.75 * 4 = 3毫秒。也就是說在一個(gè)8核系統(tǒng)默認(rèn)配置下，調(diào)度粒度是3毫秒，一個(gè)進(jìn)程如果運(yùn)行還不到3毫秒是不能被搶占的。

此代碼中還提到了喚醒粒度，我們也順便講一下。喚醒粒度是指被喚醒的進(jìn)程如果其虛擬運(yùn)行時(shí)間比當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間少的值不大于這個(gè)值的虛擬化時(shí)間就不進(jìn)行搶占。喚醒粒度指的不是是否喚醒這個(gè)進(jìn)程，而是喚醒這個(gè)進(jìn)程之后是否進(jìn)行搶占。只有當(dāng)被喚醒的進(jìn)程的虛擬運(yùn)行時(shí)間比當(dāng)前進(jìn)程的少的足夠多時(shí)才會(huì)進(jìn)行搶占。當(dāng)然這個(gè)也要同時(shí)滿足調(diào)度粒度才會(huì)進(jìn)行搶占。喚醒粒度的規(guī)范值是1毫秒，乘以4就是4毫秒。

此代碼中還有調(diào)度延遲，它和調(diào)度周期有關(guān)，我們先來計(jì)算一下調(diào)度延遲的值。調(diào)度延遲的規(guī)范值是6毫秒，乘以4就是24毫秒。

調(diào)度周期的計(jì)算與調(diào)度粒度和調(diào)度延遲都有關(guān)系，所以我們現(xiàn)在才能開始計(jì)算調(diào)度周期。先來看代碼

linux-src/kernel/sched/fair.c

調(diào)度延遲24毫秒是個(gè)固定值(在默認(rèn)情況都不變的情況下)，當(dāng)運(yùn)行隊(duì)列上的進(jìn)程個(gè)數(shù)小于等于8的時(shí)候，每個(gè)進(jìn)程至少能分到3毫秒，符合調(diào)度粒度是3毫秒的設(shè)定。所以當(dāng)running進(jìn)程的個(gè)數(shù)小于等于8時(shí)，調(diào)度周期就等于調(diào)度延遲，每個(gè)進(jìn)程至少能平分到3毫秒時(shí)間。當(dāng)其個(gè)數(shù)大于8時(shí)，調(diào)度周期就等于運(yùn)行進(jìn)程的個(gè)數(shù)乘以調(diào)度粒度。在一個(gè)調(diào)度周期內(nèi)如果是所有進(jìn)程平分的話，一個(gè)進(jìn)程能分到3毫秒。但是由于有的進(jìn)程權(quán)重高，分到的時(shí)間就會(huì)大于3毫秒，就會(huì)有進(jìn)程分到的時(shí)間少于3毫秒。實(shí)際上是這樣的嗎？我們來看一下計(jì)算時(shí)間片的代碼。

linux-src/kernel/sched/fair.c

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se){  unsigned int nr_running = cfs_rq->nr_running;  u64 slice;
  if (sched_feat(ALT_PERIOD))    nr_running = rq_of(cfs_rq)->cfs.h_nr_running;
  slice = __sched_period(nr_running + !se->on_rq);
  for_each_sched_entity(se) {    struct load_weight *load;    struct load_weight lw;
    cfs_rq = cfs_rq_of(se);    load = &cfs_rq->load;
    if (unlikely(!se->on_rq)) {      lw = cfs_rq->load;
      update_load_add(&lw, se->load.weight);      load = &lw;    }    slice = __calc_delta(slice, se->load.weight, load);  }
  if (sched_feat(BASE_SLICE))    slice = max(slice, (u64)sysctl_sched_min_granularity);
  return slice;}

變量slice被復(fù)用了，首先被用來表示調(diào)度周期。接下來的for循環(huán)，由于我們不考慮組調(diào)度，實(shí)際上只執(zhí)行了一遍。slice的值等于調(diào)度周期乘以進(jìn)程權(quán)重與運(yùn)行隊(duì)列權(quán)重的比值。如果進(jìn)程的權(quán)重低于平均權(quán)重的話，那么其實(shí)將會(huì)小于調(diào)度粒度。再往下有個(gè)判斷，由于BASE_SLICE的值默認(rèn)是true，所以此語句會(huì)執(zhí)行，slice至少等于調(diào)度粒度。由此可以得出結(jié)論，在默認(rèn)情況下，進(jìn)程分到的時(shí)間片不會(huì)小于調(diào)度粒度。那么此時(shí)實(shí)際的調(diào)度周期就會(huì)延長(zhǎng)了。不過很大概率不會(huì)延長(zhǎng)的，因?yàn)橐话愣紩?huì)有進(jìn)程因?yàn)樽枞M(jìn)行主動(dòng)調(diào)度從而讓出來一部分時(shí)間。

我們?cè)賮砜偨Y(jié)一下調(diào)度周期、調(diào)度延遲、調(diào)度粒度、時(shí)間片的概念意義和它們?cè)贑FS中的變量意義以及相互之間的關(guān)系。調(diào)度周期的概念是指運(yùn)行隊(duì)列上所有的進(jìn)程都運(yùn)行一遍的時(shí)間，但是在CFS中沒有了標(biāo)準(zhǔn)的調(diào)度周期，調(diào)度周期是動(dòng)態(tài)的，只是個(gè)計(jì)算量。調(diào)度延遲的概念是指一個(gè)進(jìn)程從加入到運(yùn)行隊(duì)列到被放到CPU上去執(zhí)行之間的時(shí)間差，顯然這個(gè)時(shí)間差受進(jìn)程本身和運(yùn)行隊(duì)列長(zhǎng)短的影響。在CFS中，調(diào)度延遲的概念完全變了，調(diào)度延遲變成了調(diào)度周期的最小值。時(shí)間片的概念是指一個(gè)進(jìn)程一次最多只能運(yùn)行多長(zhǎng)時(shí)間，然后就要被搶占了。在CFS中時(shí)間片的概念沒有變，但是用法和傳統(tǒng)的用法不一樣。調(diào)度粒度是指一個(gè)進(jìn)程一次至少運(yùn)行多少時(shí)間才能被搶占，這個(gè)才CFS中也是如此。在CFS中，它們的計(jì)算關(guān)系是，調(diào)度周期等于調(diào)度粒度乘以Runnable進(jìn)程的數(shù)量，但是不能小于調(diào)度延遲，時(shí)間片等調(diào)度周期乘以進(jìn)程權(quán)重與運(yùn)行隊(duì)列權(quán)重的比值。

4.7 搶占調(diào)度

搶占調(diào)度有兩個(gè)典型的觸發(fā)點(diǎn)：定時(shí)器中斷和進(jìn)程喚醒。我們先來說定時(shí)器中斷，定時(shí)器中斷的主要目的就是為了進(jìn)行搶占調(diào)度，防止有的進(jìn)程一直占著CPU不放手。以前的算法會(huì)在定時(shí)器中斷中檢查進(jìn)程的時(shí)間片是否已耗盡，如果耗盡的話就觸發(fā)調(diào)度，不過在CFS中的具體做法與此有所不同。在CFS中不會(huì)規(guī)定固定的調(diào)度周期，調(diào)度周期都是即時(shí)計(jì)算出來的，不會(huì)給進(jìn)程分配時(shí)間片進(jìn)行遞減，而是在定時(shí)器中斷中統(tǒng)計(jì)進(jìn)程此時(shí)占據(jù)CPU已經(jīng)運(yùn)行了多少時(shí)間，拿這個(gè)時(shí)間去給理論上它應(yīng)當(dāng)運(yùn)行的時(shí)間比，如果超過了就觸發(fā)調(diào)度。進(jìn)程的理論運(yùn)行時(shí)間就等于其權(quán)重與隊(duì)列權(quán)重之比再乘以調(diào)度周期，調(diào)度周期的計(jì)算方法在上一節(jié)中講過了。因此CFS中的調(diào)度周期和時(shí)間片與傳統(tǒng)調(diào)度算法中的概念不同，它是一個(gè)動(dòng)態(tài)的概念，只有當(dāng)發(fā)生定時(shí)器中斷了才會(huì)去計(jì)算一下，會(huì)根據(jù)當(dāng)時(shí)的狀態(tài)進(jìn)行計(jì)算。比如當(dāng)前進(jìn)程在函數(shù)A中喚醒了很多進(jìn)程，那么定時(shí)器中斷是發(fā)生在函數(shù)A之前還是之后，調(diào)度周期和時(shí)間片的計(jì)算結(jié)果會(huì)有很大的不同。

下面我們來看一下定時(shí)器中斷中的搶占邏輯：

linux-src/kernel/sched/core.c

linux-src/kernel/sched/fair.c

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued){  struct cfs_rq *cfs_rq;  struct sched_entity *se = &curr->se;
  for_each_sched_entity(se) {    cfs_rq = cfs_rq_of(se);    entity_tick(cfs_rq, se, queued);  }}
static voidentity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued){  update_curr(cfs_rq);  update_load_avg(cfs_rq, curr, UPDATE_TG);  update_cfs_group(curr);
  if (cfs_rq->nr_running > 1)    check_preempt_tick(cfs_rq, curr);}
static voidcheck_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr){  unsigned long ideal_runtime, delta_exec;  struct sched_entity *se;  s64 delta;
  ideal_runtime = sched_slice(cfs_rq, curr);  delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;  if (delta_exec > ideal_runtime) {    resched_curr(rq_of(cfs_rq));    /*     * The current task ran long enough, ensure it doesn't get     * re-elected due to buddy favours.     */    clear_buddies(cfs_rq, curr);    return;  }
  /*   * Ensure that a task that missed wakeup preemption by a   * narrow margin doesn't have to wait for a full slice.   * This also mitigates buddy induced latencies under load.   */  if (delta_exec < sysctl_sched_min_granularity)    return;
  se = __pick_first_entity(cfs_rq);  delta = curr->vruntime - se->vruntime;
  if (delta < 0)    return;
  if (delta > ideal_runtime)    resched_curr(rq_of(cfs_rq));}

定時(shí)器中斷中會(huì)調(diào)用scheduler_tick，scheduler_tick會(huì)調(diào)用當(dāng)前進(jìn)程的調(diào)度類的task_tick函數(shù)指針，對(duì)于普通進(jìn)程來說就是task_tick_fair函數(shù)。task_tick_fair會(huì)調(diào)用entity_tick，我們這里不考慮組調(diào)度，因此for循環(huán)只會(huì)執(zhí)行一遍。在entity_tick中會(huì)先調(diào)用update_curr更新進(jìn)程的運(yùn)行時(shí)間，然后在當(dāng)運(yùn)行進(jìn)程總數(shù)大于1的時(shí)候調(diào)用check_preempt_tick。check_preempt_tick就是定時(shí)器搶占的核心了。

在check_preempt_tick中會(huì)先計(jì)算出來進(jìn)程的理論運(yùn)行時(shí)間ideal_runtime和實(shí)際運(yùn)行時(shí)間delta_exec。如果實(shí)際運(yùn)行時(shí)間大于理論運(yùn)行時(shí)間，就會(huì)調(diào)用resched_curr來觸發(fā)搶占。如果不大于的話還會(huì)繼續(xù)處理。先判斷實(shí)際運(yùn)行時(shí)間是否小于調(diào)度粒度，如果小于就返回。如果不小于就繼續(xù)。此時(shí)會(huì)計(jì)算當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間與隊(duì)首進(jìn)程的虛擬運(yùn)行時(shí)間的差值，如果差值大于前面計(jì)算出來的理論運(yùn)行時(shí)間就會(huì)調(diào)用resched_curr來觸發(fā)搶占。按照定時(shí)器中斷的目的的話，后面這個(gè)操作是沒有必要的，但是按照我們?cè)贑FS調(diào)度模型中的要求，盡量使所有玻璃杯在任意時(shí)刻的水位都盡量相同，這個(gè)操作是很有必要的，它能提高公平性。

下面我們來看一下喚醒搶占，喚醒分為新建喚醒和阻塞喚醒，最后都會(huì)調(diào)用check_preempt_curr函數(shù)來看一下是否需要搶占。下面我們來看一下代碼：

linux-src/kernel/sched/core.c

linux-src/kernel/sched/fair.c

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags){  struct task_struct *curr = rq->curr;  struct sched_entity *se = &curr->se, *pse = &p->se;  struct cfs_rq *cfs_rq = task_cfs_rq(curr);  int scale = cfs_rq->nr_running >= sched_nr_latency;  int next_buddy_marked = 0;  int cse_is_idle, pse_is_idle;
  if (test_tsk_need_resched(curr))    return;
  /* Idle tasks are by definition preempted by non-idle tasks. */  if (unlikely(task_has_idle_policy(curr)) &&      likely(!task_has_idle_policy(p)))    goto preempt;
  /*   * Batch and idle tasks do not preempt non-idle tasks (their preemption   * is driven by the tick):   */  if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))    return;
  update_curr(cfs_rq_of(se));  if (wakeup_preempt_entity(se, pse) == 1) {    if (!next_buddy_marked)      set_next_buddy(pse);    goto preempt;  }
  return;
preempt:  resched_curr(rq);  if (unlikely(!se->on_rq || curr == rq->idle))    return;
  if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))    set_last_buddy(se);}
static intwakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se){  s64 gran, vdiff = curr->vruntime - se->vruntime;
  if (vdiff <= 0)    return -1;
  gran = wakeup_gran(se);  if (vdiff > gran)    return 1;
  return 0;}
static unsigned long wakeup_gran(struct sched_entity *se){  unsigned long gran = sysctl_sched_wakeup_granularity;  return calc_delta_fair(gran, se);}

在check_preempt_curr中，同類進(jìn)程會(huì)使用調(diào)度類的check_preempt_curr函數(shù)進(jìn)行處理，不同類的進(jìn)程，高類會(huì)搶占低類的進(jìn)程。分時(shí)調(diào)度類中的相應(yīng)函數(shù)是check_preempt_wakeup。此函數(shù)會(huì)先區(qū)分不同的調(diào)度策略，SCHED_IDLE策略的進(jìn)程一定會(huì)被非SCHED_IDLE的進(jìn)程搶占，非SCHED_NORMAL的進(jìn)程一定不會(huì)搶占非SCHED_IDLE的進(jìn)程。接下來會(huì)調(diào)用update_curr更新一下當(dāng)前進(jìn)程的時(shí)間統(tǒng)計(jì)，然后調(diào)用wakeup_preempt_entity來查看一下是否滿足喚醒粒度，如果滿足就觸發(fā)調(diào)度。滿足喚醒粒度的標(biāo)準(zhǔn)是當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間與被喚醒進(jìn)程的虛擬運(yùn)行時(shí)間的差值要大于喚醒粒度對(duì)應(yīng)的虛擬時(shí)間。

4.8 入隊(duì)與出隊(duì)

CFS中排隊(duì)的進(jìn)程都是放在紅黑樹中，我們經(jīng)常要對(duì)其進(jìn)行出隊(duì)入隊(duì)查詢隊(duì)首的操作。

下面我們先來看一下內(nèi)核中紅黑樹的定義與操作：

linux-src/include/linux/rbtree_types.h

linux-src/include/linux/rbtree.h

#define rb_first_cached(root) (root)->rb_leftmost
static __always_inline struct rb_node *rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,        bool (*less)(struct rb_node *, const struct rb_node *));
static inline struct rb_node *rb_erase_cached(struct rb_node *node, struct rb_root_cached *root);

在CFS中經(jīng)常會(huì)對(duì)隊(duì)首進(jìn)程進(jìn)行操作，因此rb_root_cached中用rb_leftmost對(duì)紅黑樹的最下角的節(jié)點(diǎn)(這個(gè)節(jié)點(diǎn)就是vruntime最小的節(jié)點(diǎn)，就是隊(duì)首進(jìn)程)進(jìn)行了緩存，方便查找。

我們經(jīng)常會(huì)對(duì)運(yùn)行隊(duì)列進(jìn)行入隊(duì)出隊(duì)操作，入隊(duì)出隊(duì)操作可以分為兩類。一類是和調(diào)度執(zhí)行相關(guān)的入隊(duì)出隊(duì)，叫做pick_next_task和put_prev_task，pick_next_task是選擇一個(gè)進(jìn)程把它放到CPU上去運(yùn)行，put_prev_task是把正在CPU上運(yùn)行的進(jìn)程放回到運(yùn)行隊(duì)列中去。另一類是和非執(zhí)行相關(guān)的入隊(duì)出隊(duì)，叫做enqueue_task和dequeue_task，enqueue_task是把一個(gè)非正在CPU上執(zhí)行的進(jìn)程放入到隊(duì)列中去，dequeue_task是把一個(gè)進(jìn)程從隊(duì)列中拿出來，但不是拿來去CPU上運(yùn)行的。

pick_next_task和put_prev_task都是在調(diào)度流程中的選擇進(jìn)程過程中調(diào)用的。

下面我們看一下代碼(進(jìn)行了高度刪減)：

linux-src/kernel/sched/core.c

linux-src/kernel/sched/fair.c

struct task_struct *pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf){  struct cfs_rq *cfs_rq = &rq->cfs;  struct sched_entity *se;  struct task_struct *p;  int new_tasks;
  if (prev)    put_prev_task(rq, prev);
  do {    se = pick_next_entity(cfs_rq, NULL);    set_next_entity(cfs_rq, se);    cfs_rq = group_cfs_rq(se);  } while (cfs_rq);
  p = task_of(se);
  return p;}
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev){  struct sched_entity *se = &prev->se;  struct cfs_rq *cfs_rq;
  for_each_sched_entity(se) {    cfs_rq = cfs_rq_of(se);    put_prev_entity(cfs_rq, se);  }}
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev){  if (prev->on_rq) {    __enqueue_entity(cfs_rq, prev);  }  cfs_rq->curr = NULL;}
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){  rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);}
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr){  struct sched_entity *left = __pick_first_entity(cfs_rq);  struct sched_entity *se;  se = left; /* ideally we run the leftmost entity */  return se;}

在執(zhí)行調(diào)度的時(shí)候會(huì)調(diào)用到pick_next_task_fair，此函數(shù)會(huì)先put_prev_task再pick_next_entity。put_prev_task最終會(huì)使用rb_add_cached把被搶占的進(jìn)程放回到隊(duì)列中去，對(duì)于阻塞調(diào)度的則不會(huì)。pick_next_entity最終會(huì)使用rb_first_cached來獲取隊(duì)首進(jìn)程用來調(diào)度。

enqueue_task和dequeue_task這兩個(gè)函數(shù)會(huì)在修改進(jìn)程優(yōu)先級(jí)、設(shè)置進(jìn)程親和性、遷移進(jìn)程等操作中成對(duì)使用。enqueue_task在進(jìn)程喚醒中也會(huì)使用，下面我們來看一下代碼。

linux-src/kernel/sched/core.c

linux-src/kernel/sched/fair.c

static voidenqueue_task_fair(struct rq *rq, struct task_struct *p, int flags){  struct cfs_rq *cfs_rq;  struct sched_entity *se = &p->se;
  for_each_sched_entity(se) {    if (se->on_rq)      break;    cfs_rq = cfs_rq_of(se);    enqueue_entity(cfs_rq, se, flags);  }}
static voidenqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags){  bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);  bool curr = cfs_rq->curr == se;
  update_curr(cfs_rq);  if (!curr)    __enqueue_entity(cfs_rq, se);  se->on_rq = 1;}
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){  rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);}

可以看出enqueue_task最終也是調(diào)用rb_add_cached把進(jìn)程放入到運(yùn)行隊(duì)列中去的。

4.9 CFS算法評(píng)價(jià)

現(xiàn)在我們對(duì)CFS調(diào)度算法的各個(gè)方面都有了基本的了解，讓我們?cè)倏匆幌翪FS調(diào)度模型圖來回憶一下：

回憶完之后，我們對(duì)CFS算法進(jìn)行一下分析和評(píng)價(jià)。首先CFS取消了對(duì)IO密集型和CPU密集型進(jìn)程的探測(cè)，避免了由于誤探而產(chǎn)生的問題。雖然沒有對(duì)IO密集型和CPU密集型進(jìn)程進(jìn)行探測(cè)區(qū)分，但是CFS還是能很好地處理這兩類進(jìn)程。CPU密集型進(jìn)程總是進(jìn)程處于Runnable狀態(tài)，所以能經(jīng)常運(yùn)行。由于其經(jīng)常會(huì)運(yùn)行，水位會(huì)比較高，所以就排到后面，就給其它進(jìn)程留下了機(jī)會(huì)。IO密集型進(jìn)程由于經(jīng)常處于阻塞狀態(tài)，所以其水位就會(huì)比較低，在其喚醒之后進(jìn)入隊(duì)列的時(shí)候經(jīng)常能排在隊(duì)首且很可能會(huì)搶占當(dāng)前進(jìn)程，所以IO密集型的進(jìn)程響應(yīng)性會(huì)比較高。

我們?cè)賮砜垂叫?，CFS的名字就叫做完全公平調(diào)度，所以肯定是很公平的。公平性主要體現(xiàn)在以下幾個(gè)方面。一是取消了對(duì)IO密集型和CPU密集型進(jìn)程的探測(cè)，不會(huì)對(duì)IO密集型進(jìn)程進(jìn)行特殊的照顧，所以進(jìn)程都一視同仁。二是優(yōu)先級(jí)轉(zhuǎn)權(quán)重的時(shí)候采用了等比數(shù)列，使得nice值相差1的進(jìn)程獲得的CPU時(shí)間比例總是相差10%，很公平。三是低優(yōu)先級(jí)的進(jìn)程隨著別人的水位增長(zhǎng)總是會(huì)排到前面的，一定會(huì)在可觀的時(shí)間內(nèi)得到執(zhí)行，不會(huì)產(chǎn)生饑餓。

再來看適應(yīng)性，由于采用了紅黑樹，CFS的出隊(duì)入隊(duì)查找操作都是O(logn)的，當(dāng)進(jìn)程變得很多時(shí)，調(diào)度效率也依然良好。與調(diào)度效率是O(n)的算法相比，適應(yīng)性明顯很強(qiáng)，和O(1)的算法相比，也不算太差。

吞吐量和很多因素有關(guān)，代碼簡(jiǎn)潔，調(diào)度效率是O(logn)也會(huì)提高其吞吐量。

節(jié)能性的話，CFS本身并沒有考慮這個(gè)問題?，F(xiàn)在內(nèi)核已經(jīng)合入了EAS的代碼，EAS是對(duì)CFS的擴(kuò)展，主要是來解決調(diào)度器的節(jié)能問題的。

五、總結(jié)回顧

我們?cè)诖宋闹兄v了非常多關(guān)于進(jìn)程調(diào)度的知識(shí)點(diǎn)，下面我們來總結(jié)一下。

對(duì)著這個(gè)圖讓我們來回顧一下，什么是調(diào)度，為什么要調(diào)度，為什么能調(diào)度。然后是調(diào)度時(shí)機(jī)，包括主動(dòng)調(diào)度和被動(dòng)調(diào)度。再之后是如何調(diào)度，包括選擇進(jìn)程和切換進(jìn)程。切換進(jìn)程的邏輯是通用的，而選擇進(jìn)程要分為5個(gè)調(diào)度類來進(jìn)行選擇。講完了在單個(gè)CPU上的調(diào)度之后，我們還要在多CPU上進(jìn)行調(diào)度均衡。

進(jìn)程調(diào)度是操作系統(tǒng)中非常龐大非常難懂但又非常重要的部分，我們要經(jīng)常理論結(jié)合代碼結(jié)合實(shí)踐、反復(fù)思考琢磨才能更好的理解和掌握它。

參考文獻(xiàn)：

《Linux Kernel Development》

《Understanding the Linux Kernel》

《Professional Linux Kernel Architecture》

《Mastering Linux Kernel Development》

《Understanding the Linux Virtual Memory Manager》

《Linux內(nèi)核深度解析》

《Linux操作系統(tǒng)原理與應(yīng)用》

《深度探索Linux操作系統(tǒng)》

《ARM Linux內(nèi)核源碼剖析》

《奔跑吧Linux內(nèi)核》

《Linux內(nèi)核源代碼情景分析》

《Linux內(nèi)核設(shè)計(jì)的藝術(shù)》

《Linux內(nèi)核完全注釋》