作者簡介：

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

目錄

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

1.1 什么是調(diào)度 1.2 為什么要調(diào)度 1.3 為什么能調(diào)度 1.4 何時(shí)調(diào)度 1.5 如何調(diào)度 1.6 調(diào)度均衡 1.7 調(diào)度器評價(jià) 1.8 調(diào)度器歷史

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

2.1 調(diào)度隊(duì)列 2.2 進(jìn)程喚醒 2.3 調(diào)度時(shí)機(jī) 2.4 調(diào)度流程 2.5 調(diào)度算法 2.6 進(jìn)程優(yōu)先級 2.7 進(jìn)程切換

三、SMP管理

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

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

4.1 CFS調(diào)度模型 4.2 CFS運(yùn)行隊(duì)列 4.3 進(jìn)程狀態(tài)表示 4.4 優(yōu)先級與權(quán)重 4.5 虛擬運(yùn)行時(shí)間 4.6 調(diào)度周期與粒度 4.7 搶占調(diào)度 4.8 入隊(duì)與出隊(duì) 4.9 CFS算法評價(jià)

五、總結(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)容都是對這張圖的解釋和擴(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，對CPU該如何管理呢？對于直接共享型的事物，我們有兩種管理方法：一種是時(shí)間分割管理，另一種是空間分割管理。由于CPU自身的特性，沒有空間分割相似性，只有時(shí)間分割相似性，所以我們只能對CPU進(jìn)行時(shí)間分割管理。對CPU進(jìn)行時(shí)間分割管理的具體做法就叫做進(jìn)程調(diào)度。

那么調(diào)度的是什么呢？進(jìn)程調(diào)度，調(diào)度的當(dāng)然是進(jìn)程啦，也對也不對。我們知道進(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)度線程，請大家要注意。

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

就像國家希望每個(gè)企業(yè)都做大做強(qiáng)，但是同時(shí)也會(huì)反壟斷一樣。Linux也推出了cgroup組調(diào)度機(jī)制，來限制某個(gè)或者某一類進(jìn)程對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í)間片長短是不確定的，而且是很偶然很隨機(jī)的。如果一個(gè)進(jìn)程它一直在做運(yùn)算就是不進(jìn)行IO操作，那么它就會(huì)一直霸占CPU。針對這個(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)程都可以相對公平地平分CPU時(shí)間，如果一個(gè)進(jìn)程運(yùn)行了過長的時(shí)間就會(huì)被強(qiáng)制性地調(diào)度出去，不管這個(gè)進(jìn)程是否愿意。有了搶占式多任務(wù)，我們在宏觀上不僅可以同時(shí)運(yùn)行多個(gè)進(jìn)程，而且它們會(huì)一起齊頭并進(jìn)地往前運(yùn)行，不會(huì)出現(xiàn)某個(gè)進(jìn)程被餓死的情況，這樣我們使用電腦的體驗(yàn)就非常完美了。搶占式多任務(wù)和協(xié)作式多任務(wù)不是對立的，它們是相互獨(dú)立的，可以同時(shí)存在于系統(tǒng)中。

搶占又分為用戶搶占和內(nèi)核搶占。由于搶占對進(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)閷τ谟脩艨臻g來說，如果搶占會(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ā)者對內(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)在我們再來看一下為什么要調(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)度

我們再來看看為什么能調(diào)度呢。我們把協(xié)作式多任務(wù)叫做主動(dòng)調(diào)度，搶占式多任務(wù)叫做被動(dòng)調(diào)度。為什么能調(diào)度分為兩部分：為什么能觸發(fā)調(diào)度和為什么能執(zhí)行調(diào)度。對于主動(dòng)調(diào)度，調(diào)度是進(jìn)程主動(dòng)觸發(fā)的，這個(gè)是肯定能的。對于被動(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ā)中斷，檢測進(jìn)程是否運(yùn)行時(shí)間過長，如果過長就觸發(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é)我們在2.7節(jié)中講。

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

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

對于主動(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。

對于被動(dòng)調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是異步的、分離的，觸發(fā)調(diào)度并不會(huì)立馬執(zhí)行調(diào)度，而是做個(gè)需要調(diào)度的標(biāo)記，然后在之后的某個(gè)合適的地方會(huì)檢測這個(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)先級時(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)度檢測點(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)核空間的場景，如果開啟了內(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è)圖來看一下：

對于一個(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)度均衡

前面所說的都是針對一個(gè)CPU的情況，對于多個(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è)相對清閑的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)程都盡量選擇相對清閑的CPU，所以所有CPU的負(fù)載應(yīng)該還是會(huì)比較均衡的。但是時(shí)間長了可能還是會(huì)出現(xiàn)負(fù)載不均衡的情況，此時(shí)就要進(jìn)行總體均衡了?？傮w均衡的觸發(fā)點(diǎn)有三個(gè)：一是CPU即將idle前會(huì)去找到最忙的CPU然后拉取一些任務(wù)過來；二是定時(shí)器中斷的周期性檢測，會(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)度器評價(jià)

狹義的調(diào)度器指的是具體的調(diào)度算法，廣義的調(diào)度器指的是整個(gè)調(diào)度體系。不過兩者的評價(jià)指標(biāo)是相同的，所以我們這里不具體區(qū)分調(diào)度器是指調(diào)度算法還是調(diào)度體系。調(diào)度器的評價(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.公平性，指的是相對公平性，每個(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ù)一直沒有較大的突破，所以省電對手機(jī)來說就是一項(xiàng)非常重要的任務(wù)，調(diào)度器也不可避免地要考慮省電問題了。

1.8 調(diào)度器歷史

Linux的調(diào)度器經(jī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)先級，按照動(dòng)態(tài)優(yōu)先級決定進(jìn)程的調(diào)度順序，按照優(yōu)先級分配進(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)度器主要是針對傳統(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)先級排序，并用bitmap來表示哪個(gè)優(yōu)先級隊(duì)列中有可運(yùn)行的進(jìn)程，把選擇進(jìn)程的算法復(fù)雜度降低到了O(1)。對進(jìn)程區(qū)分IO密集型和CPU密集型并計(jì)算動(dòng)態(tài)優(yōu)先級這一點(diǎn)和傳統(tǒng)調(diào)度器一樣沒有變。

SD Scheduler：(未合入)

樓梯調(diào)度器，它是對O(1)調(diào)度器的改進(jìn)，算法復(fù)雜還是O(1)。之前的調(diào)度器都區(qū)分IO密集型和CPU密集型，算法要對進(jìn)程的類型進(jìn)行探測，根據(jù)探測結(jié)果調(diào)整動(dòng)態(tài)優(yōu)先級。這就有很大的問題，探測不一定準(zhǔn)確，而且進(jìn)程還可以欺騙調(diào)度器，最終會(huì)導(dǎo)致調(diào)度有很大的不公平性。樓梯調(diào)度器是第一次嘗試使用公平調(diào)度算法，它廢除了動(dòng)態(tài)優(yōu)先級，不再區(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)先級，其本身的優(yōu)先級還是不變的。當(dāng)進(jìn)程下降到最后一個(gè)優(yōu)先級之后就再回到它本來的優(yōu)先級隊(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)度器，是對樓梯調(diào)度器的改進(jìn)。又重新引入了過期數(shù)組，為每個(gè)優(yōu)先級都分配一個(gè)組時(shí)間配額記為Tg，進(jìn)程本身的時(shí)間片記為Tp。當(dāng)進(jìn)程用完自己的時(shí)間片時(shí)會(huì)下降一個(gè)優(yōu)先級，當(dāng)一個(gè)優(yōu)先級的Tg被用完時(shí)，組內(nèi)所有的進(jìn)程都會(huì)下降一個(gè)優(yōu)先級。進(jìn)程下降到最低優(yōu)先級之后會(huì)被放入過期數(shù)組，當(dāng)活動(dòng)數(shù)組為空時(shí)就會(huì)交換活動(dòng)數(shù)組和過期數(shù)組。由于加了Tg，使得低優(yōu)先級進(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ìn)程都按優(yōu)先級相對平分CPU時(shí)間，算法復(fù)雜度是O(logn)。此時(shí)對調(diào)度器框架也進(jìn)行了重構(gòu)，和之前的有很大的不同。之前的調(diào)度器是一個(gè)算法調(diào)度所有進(jìn)程，在算法內(nèi)部區(qū)別對待實(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)度框架 ? ?

前面我們對進(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

?

struct rq {  raw_spinlock_t    __lock;  unsigned int    nr_running;
  struct cfs_rq    cfs;  struct rt_rq    rt;  struct dl_rq    dl;
  struct task_struct __rcu  *curr;  struct task_struct  *idle;  struct task_struct  *stop;
  int      cpu;  int      online;};

?

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

?

void wake_up_new_task(struct task_struct *p){  struct rq_flags rf;  struct rq *rq;
  raw_spin_lock_irqsave(&p->pi_lock, rf.flags);  WRITE_ONCE(p->__state, TASK_RUNNING);
  p->recent_used_cpu = task_cpu(p);  rseq_migrate(p);  __set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));
  rq = __task_rq_lock(p, &rf);  update_rq_clock(rq);
  activate_task(rq, p, ENQUEUE_NOCLOCK);
  check_preempt_curr(rq, p, WF_FORK);  task_rq_unlock(rq, p, &rf);}

?

在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的邏輯我們在調(diào)度均衡中講，check_preempt_curr的邏輯我們在下一節(jié)的被動(dòng)調(diào)度中講。

我們再來看一下阻塞喚醒的代碼：

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)行一些檢測，先檢測被喚醒的進(jìn)程是否為當(dāng)前進(jìn)程，如果是的話直接go out。再檢測進(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

?

static inline int __sched __down_common(struct semaphore *sem, long state, long timeout){  struct semaphore_waiter waiter;
  list_add_tail(&waiter.list, &sem->wait_list);  waiter.task = current;  waiter.up = false;
  for (;;) {    if (signal_pending_state(state, current))      goto interrupted;    if (unlikely(timeout <= 0))      goto timed_out;    __set_current_state(state);    raw_spin_unlock_irq(&sem->lock);    timeout = schedule_timeout(timeout);    raw_spin_lock_irq(&sem->lock);    if (waiter.up)      return 0;  }
 timed_out:  list_del(&waiter.list);  return -ETIME;
 interrupted:  list_del(&waiter.list);  return -EINTR;}

?

先定義一個(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)程長時(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)先級時(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)程過長的占用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é)我們在具體的調(diào)度算法中再講。

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

linux-src/kernel/sched/core.c

?

void wake_up_new_task(struct task_struct *p){  struct rq_flags rf;  struct rq *rq;
  __set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));  activate_task(rq, p, ENQUEUE_NOCLOCK);  check_preempt_curr(rq, p, WF_FORK);}
static inttry_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){  unsigned long flags;  int cpu, success = 0;
  cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);  if (task_cpu(p) != cpu) {      set_task_cpu(p, cpu);  }  ttwu_queue(p, cpu, wake_flags);  return success;}
static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags){  struct rq *rq = cpu_rq(cpu);  struct rq_flags rf;
  ttwu_do_activate(rq, p, wake_flags, &rf);}
static voidttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,     struct rq_flags *rf){  int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
  activate_task(rq, p, en_flags);  ttwu_do_wakeup(rq, p, wake_flags, rf);}
static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,         struct rq_flags *rf){  check_preempt_curr(rq, p, wake_flags);  WRITE_ONCE(p->__state, TASK_RUNNING);}
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags){  if (p->sched_class == rq->curr->sched_class)    rq->curr->sched_class->check_preempt_curr(rq, p, flags);  else if (p->sched_class > rq->curr->sched_class)    resched_curr(rq);}
void resched_curr(struct rq *rq){  struct task_struct *curr = rq->curr;  int cpu;
  cpu = cpu_of(rq);
  if (cpu == smp_processor_id()) {    set_tsk_need_resched(curr);    set_preempt_need_resched();    return;  }}

?

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è)邏輯我們在具體調(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)記。

下面我們再來看一下執(zhí)行調(diào)度的點(diǎn)，以x86為例。

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

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

?

__visible noinstr void do_syscall_64(struct pt_regs *regs, int nr){  nr = syscall_enter_from_user_mode(regs, nr);  if (!do_syscall_x64(regs, nr) && !do_syscall_x32(regs, nr) && nr != -1) {    /* Invalid system call, but still a system call. */    regs->ax = __x64_sys_ni_syscall(regs);  }  syscall_exit_to_user_mode(regs);}
static noinstr bool __do_fast_syscall_32(struct pt_regs *regs){  int nr = syscall_32_enter(regs);  int res;
  syscall_enter_from_user_mode_prepare(regs);  do_syscall_32_irqs_on(regs, nr);  syscall_exit_to_user_mode(regs);  return true;}
__visible noinstr void do_int80_syscall_32(struct pt_regs *regs){  int nr = syscall_32_enter(regs);
  nr = syscall_enter_from_user_mode(regs, nr);  do_syscall_32_irqs_on(regs, nr);  syscall_exit_to_user_mode(regs);}

?

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ì)檢測thread_info flag中的_TIF_NEED_RESCHED，如果設(shè)置了就會(huì)執(zhí)行調(diào)度。

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

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

?

#define DEFINE_IDTENTRY_IRQ(func)          static void __##func(struct pt_regs *regs, u32 vector);                        __visible noinstr void func(struct pt_regs *regs,                unsigned long error_code)      {                    irqentry_state_t state = irqentry_enter(regs);        u32 vector = (u32)(u8)error_code;                            instrumentation_begin();            kvm_set_cpu_l1tf_flush_l1d();            run_irq_on_irqstack_cond(__##func, regs, vector);      instrumentation_end();              irqentry_exit(regs, state);          }
#define DEFINE_IDTENTRY(func)            static __always_inline void __##func(struct pt_regs *regs);                      __visible noinstr void func(struct pt_regs *regs)      {                    irqentry_state_t state = irqentry_enter(regs);                          instrumentation_begin();            __##func (regs);              instrumentation_end();              irqentry_exit(regs, state);          }

?

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)于中斷的原理請參看《深入理解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ì)先檢測是否配置了CONFIG_PREEMPTION，沒配置就不調(diào)用。CONFIG_PREEMPTION代表的是內(nèi)核搶占，在有些場景中會(huì)說成搶占，但是要明白其代表的是內(nèi)核搶占。

內(nèi)核有時(shí)候?yàn)榱送剑枰R時(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ì)去檢測是否需要調(diào)度。

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

linux-src/include/linux/preempt.h

?

#define preempt_disable() do {   preempt_count_inc();   barrier(); } while (0)
#define preempt_enable() do {   barrier();   if (unlikely(preempt_count_dec_and_test()))     __preempt_schedule(); } while (0)

?

preempt_disable增加引用計(jì)數(shù)，preempt_enable減少引用計(jì)數(shù)并檢測是否為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

?

void __local_bh_enable_ip(unsigned long ip, unsigned int cnt){  WARN_ON_ONCE(in_irq());
  if (unlikely(!in_interrupt() && local_softirq_pending())) {    /*     * Run softirq if any pending. And do it in its own stack     * as we may be calling this deep in a task call stack already.     */    do_softirq();  }
  preempt_count_dec();
  preempt_check_resched();}

?

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í)候檢測一下是否需要調(diào)度。

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

linux-src/include/linux/sched.h

?

#define cond_resched() ({        ___might_sleep(__FILE__, __LINE__, 0);    _cond_resched();      })
static inline int _cond_resched(void){  return __cond_resched();}

?

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)度的檢測點(diǎn)，提高系統(tǒng)的響應(yīng)性。

2.4 調(diào)度流程

前面講了這么多觸發(fā)調(diào)度的時(shí)機(jī)，現(xiàn)在該執(zhí)行調(diào)度了。執(zhí)行調(diào)度的總體邏輯是很簡單的，就兩個(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

?

static void __sched notrace __schedule(unsigned int sched_mode){  struct task_struct *prev, *next;  struct rq_flags rf;  struct rq *rq;  int cpu;
  cpu = smp_processor_id();  rq = cpu_rq(cpu);  prev = rq->curr;
  next = pick_next_task(rq, prev, &rf);
  if (likely(prev != next)) {    rq = context_switch(rq, prev, next, &rf);  } else {    __balance_callbacks(rq);  }}

?

代碼經(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)程對調(diào)度器的需求，主要是對調(diào)度緊迫性的需求。調(diào)度策略是調(diào)度類的子類，是對調(diào)度類的細(xì)分，是在同一個(gè)調(diào)度需求下的細(xì)微區(qū)別。調(diào)度算法是對調(diào)度類的實(shí)現(xiàn)，一個(gè)調(diào)度類一個(gè)調(diào)度算法。同一個(gè)調(diào)度類的調(diào)度策略是有很強(qiáng)的相似性的，所以在同一個(gè)算法中實(shí)現(xiàn)，對于它們不同的部分，算法再去進(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)先級。調(diào)度類之間的關(guān)系是有高類的進(jìn)程可運(yùn)行的情況下，絕對不會(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ì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í)，適用于對調(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)程在多長時(shí)間內(nèi)想要運(yùn)行一次，運(yùn)行時(shí)間是說這個(gè)進(jìn)程每次想要運(yùn)行多長時(shí)間，截止時(shí)間是說這個(gè)進(jìn)程每次運(yùn)行結(jié)束不能晚于什么時(shí)間。這三個(gè)參數(shù)都需要進(jìn)程根據(jù)自己的實(shí)際情況向內(nèi)核提供，而且不是說你提供了就一定能設(shè)置成功，內(nèi)核還要檢測與已有的限時(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ìn)程先運(yùn)行，只要有實(shí)時(shí)優(yōu)先級大的進(jìn)程可運(yùn)行，就不會(huì)去調(diào)度實(shí)時(shí)優(yōu)先級小的進(jìn)程。當(dāng)兩個(gè)實(shí)時(shí)進(jìn)程的優(yōu)先級相同時(shí)，SCHED_RR和SCHED_FIFO這兩個(gè)策略就有區(qū)別了，SCHED_FIFO進(jìn)程如果搶占了CPU，它就會(huì)一直占著CPU，不會(huì)給同優(yōu)先級的實(shí)時(shí)進(jìn)程讓CPU的，而SCHED_RR進(jìn)程會(huì)在運(yùn)行了一定的時(shí)間片之后主動(dòng)讓給同優(yōu)先級的實(shí)時(shí)進(jìn)程。

分時(shí)調(diào)度類是給廣大的普通進(jìn)程來用的，大家共同分享CPU。根據(jù)優(yōu)先級的不同，可能有的進(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í)間長一點(diǎn)，SCHED_IDLE是優(yōu)先級特別低的進(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

?

struct sched_class {  void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);  void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);  void (*yield_task)   (struct rq *rq);  bool (*yield_to_task)(struct rq *rq, struct task_struct *p);
  void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
  struct task_struct *(*pick_next_task)(struct rq *rq);
  void (*put_prev_task)(struct rq *rq, struct task_struct *p);  void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
#ifdef CONFIG_SMP  int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);  int  (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
  struct task_struct * (*pick_task)(struct rq *rq);
  void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
  void (*task_woken)(struct rq *this_rq, struct task_struct *task);
  void (*set_cpus_allowed)(struct task_struct *p,         const struct cpumask *newmask,         u32 flags);
  void (*rq_online)(struct rq *rq);  void (*rq_offline)(struct rq *rq);
  struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);#endif
  void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);  void (*task_fork)(struct task_struct *p);  void (*task_dead)(struct task_struct *p);
  void (*switched_from)(struct rq *this_rq, struct task_struct *task);  void (*switched_to)  (struct rq *this_rq, struct task_struct *task);  void (*prio_changed) (struct rq *this_rq, struct task_struct *task, int oldprio);
  unsigned int (*get_rr_interval)(struct rq *rq, struct task_struct *task);
  void (*update_curr)(struct rq *rq);};

?

每個(gè)調(diào)度類在實(shí)現(xiàn)自己的算法的時(shí)候都要實(shí)現(xiàn)這些函數(shù)指針，我們在講到具體算法時(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)程，所以先檢測運(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)先級

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

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

?

#include int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);int sched_getscheduler(pid_t pid);
#include int sched_setparam(pid_t pid, const struct sched_param *param);int sched_getparam(pid_t pid, struct sched_param *param);
struct sched_param {    int sched_priority;};
#include int?nice(int?inc);

?

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

我們再來看一下task_struct中記錄優(yōu)先級的字段。

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

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

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

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

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

下面讓我們再畫一個(gè)圖總結(jié)一下：

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

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

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

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)先級，范圍：1 – 99，99最大，只有SCHED_FIFO和SCHED_RR有意義。

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

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

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

PR，普通進(jìn)程 pr = 20 + nice，實(shí)時(shí)進(jìn)程 pr = -1 - rt，rt是實(shí)時(shí)進(jìn)程的用戶空間優(yōu)先級，PR值越小優(yōu)先級越大，普通進(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)過了高度刪減)：

?

static __always_inline struct rq *context_switch(struct rq *rq, struct task_struct *prev,         struct task_struct *next, struct rq_flags *rf){
  switch_mm_irqs_off(prev->active_mm, next->mm, next);
  switch_to(prev, next, prev);
  return finish_task_switch(prev);}  switch_to(prev, next, prev);  barrier();
  return finish_task_switch(prev);}

?

其中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

?

tatic inline void write_cr3(unsigned long x){  native_write_cr3(x);}
static inline void native_write_cr3(unsigned long val){  asm volatile("mov %0,%%cr3": : "r" (val) : "memory");}

?

切換進(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

?

SYM_FUNC_START(__switch_to_asm)  /*   * Save callee-saved registers   * This must match the order in inactive_task_frame   */  pushq  %rbp  pushq  %rbx  pushq  %r12  pushq  %r13  pushq  %r14  pushq  %r15
  /* switch stack */  movq  %rsp, TASK_threadsp(%rdi)  movq  TASK_threadsp(%rsi), %rsp
#ifdef CONFIG_STACKPROTECTOR  movq  TASK_stack_canary(%rsi), %rbx  movq  %rbx, PER_CPU_VAR(fixed_percpu_data) + stack_canary_offset#endif
#ifdef CONFIG_RETPOLINE  /*   * When switching from a shallower to a deeper call stack   * the RSB may either underflow or use entries populated   * with userspace addresses. On CPUs where those concerns   * exist, overwrite the RSB with entries which capture   * speculative execution to prevent attack.   */  FILL_RETURN_BUFFER %r12, RSB_CLEAR_LOOPS, X86_FEATURE_RSB_CTXSW#endif
  /* restore callee-saved registers */  popq  %r15  popq  %r14  popq  %r13  popq  %r12  popq  %rbx  popq  %rbp
  jmp  __switch_toSYM_FUNC_END(__switch_to_asm)

?

切換內(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)核的地方。

我們再來說第二點(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)鍵的兩句代碼我們再拿出來分析一下。

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

?

  /* switch stack */  movq  %rsp, TASK_threadsp(%rdi)  movq  TASK_threadsp(%rsi), %rsp

?

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)程切換成功了。后面還有一些語句用來加載之前保存在棧上的寄存器信息。

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

?

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;  if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {    pr_err("AAAAAA, -------------------------------------------");    pr_err("AAAAAA, start");    pr_err("AAAAAA, &curr:%p", &curr);    pr_err("AAAAAA, &next:%p", &next);    pr_err("AAAAAA, &from:%p", &from);    pr_err("AAAAAA,  from:%p", from);    pr_err("AAAAAA,  curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);    pr_err("AAAAAA,  next:%p, pid:%d, comm:%s", next, next->pid, next->comm);    dump_stack();    pr_err("AAAAAA, -------------------------------------------");  }  from = __switch_to_asm(curr, next);  barrier();  if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {    pr_err("AAAAAA, &curr:%p", &curr);    pr_err("AAAAAA, &next:%p", &next);    pr_err("AAAAAA, &from:%p", &from);    pr_err("AAAAAA,  from:%p, pid:%d, comm:%s", from, from->pid, from->comm);    pr_err("AAAAAA,  curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);    pr_err("AAAAAA,  next:%p, pid:%d, comm:%s", next, next->pid, next->comm);    dump_stack();    pr_err("AAAAAA, end");    pr_err("AAAAAA, -------------------------------------------");  }
  return finish_task_switch(from);}

?

這里面有兩個(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)椴磺凶咴趺茨芮谢貋砟?。但是對于剛?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í)行。對于內(nèi)核線程和普通線程偽造的棧上的數(shù)據(jù)是不一樣的，對于普通線程其rbx寄存器對應(yīng)的位置是0，對于內(nèi)核線程其rbx寄存器對應(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。

對于這幅圖大家可以只看一個(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)非對稱多處理器，是指操作系統(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)對待每個(gè)CPU的方式都是一樣的，并不會(huì)把某個(gè)CPU拿來專門做啥任務(wù)，每個(gè)CPU都有可能處理任何類型的任務(wù)。由于AMP的性能和適應(yīng)性都不太好，所以現(xiàn)在流行的操作系統(tǒng)基本都是SMP的。對于SMP這個(gè)詞來說，在很長的一段時(shí)間內(nèi)，它既是指CPU在邏輯上是對稱的(操作系統(tǒng)對待所有CPU的方式是一樣的)，也指CPU在物理上是對稱的(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)一直增長的。內(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

?

struct cpumask __cpu_possible_mask __read_mostly;EXPORT_SYMBOL(__cpu_possible_mask);
struct cpumask __cpu_online_mask __read_mostly;EXPORT_SYMBOL(__cpu_online_mask);
struct cpumask __cpu_present_mask __read_mostly;EXPORT_SYMBOL(__cpu_present_mask);
struct cpumask __cpu_active_mask __read_mostly;EXPORT_SYMBOL(__cpu_active_mask);
struct cpumask __cpu_dying_mask __read_mostly;EXPORT_SYMBOL(__cpu_dying_mask);

?

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)核文檔對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è)很好的類比場景，把這個(gè)場景稍微改造一下，就可以打造一個(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)歷過這樣的場景，或者認(rèn)為啤酒隨便分就可以了，沒必要分那么細(xì)。接下來還有一個(gè)場景更生動(dòng)。你有沒有經(jīng)歷過或者見過長輩們喝白酒劃拳的，此時(shí)一般都會(huì)拿出5到10個(gè)小酒盅，先把每個(gè)酒盅都倒個(gè)差不多，然后再來回地往各個(gè)酒盅里面倒一點(diǎn)，還會(huì)去比較酒盅液面的高低，優(yōu)先往液面低的杯子里面倒。如果你見過或者經(jīng)歷過這種場景，那么接下來的模型就很好理解了。

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

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

說到這里，大家在腦海里對這個(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ì)把對應(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í)間長的進(jìn)程能迅速得到執(zhí)行。但是這里面也存在一個(gè)問題，就是剛開蓋的玻璃杯水位太低了，它就能一直得到執(zhí)行，這對其它玻璃杯來說是不公平的。因此ReadyTable上放了一個(gè)最低水位記錄，剛開蓋的玻璃瓶如果水位比這個(gè)值低，我們就往這個(gè)玻璃瓶中填充泡沫，使得它的水位看起來和這個(gè)最低水位記錄一樣高。這樣新開蓋的玻璃杯既能優(yōu)先接水，又不能過分占便宜，非常好。最低水位記錄的值也會(huì)一直更新的，正在接水的玻璃杯每次離開的時(shí)候都會(huì)更新一下這個(gè)最低水位記錄。

現(xiàn)在我們對這個(gè)玻璃杯接水模型的邏輯已經(jīng)非常清楚了，下面我們一步一步把它和CFS的代碼對應(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)常對這個(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)程。還有一些其它字段我們在講到時(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中對進(jìn)程運(yùn)行狀態(tài)的定義卻和標(biāo)準(zhǔn)的操作系統(tǒng)理論不同。

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

linux-src/include/linux/sched.h

?

/* Used in tsk->state: */#define TASK_RUNNING      0x0000#define TASK_INTERRUPTIBLE    0x0001#define TASK_UNINTERRUPTIBLE    0x0002#define TASK_DEAD      0x0080#define TASK_NEW      0x0800

?

在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

?

#define task_is_running(task)    (READ_ONCE((task)->__state) == TASK_RUNNING)

?

注意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對應(yīng)的事件能把玻璃杯的蓋子打開，其它人誰也打不開。TASK_INTERRUPTIBLE表示除了WaitBox對應(yīng)的事件之外，信號(hào)(signal)也能把蓋子打開。關(guān)于信號(hào)請參看《深入理解Linux信號(hào)機(jī)制》。

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

我們在前面講過進(jìn)程的優(yōu)先級，這里只講分時(shí)進(jìn)程的優(yōu)先級。優(yōu)先級是如何影響進(jìn)程獲得CPU時(shí)間的多少呢？優(yōu)先級會(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í)而添加的，它可以把對weight的除法運(yùn)算轉(zhuǎn)化為對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)槿藗兲烊坏貙ο鄬χ当容^敏感而不是對絕對值比較敏感，比如你工資兩千的時(shí)候漲薪200和工資兩萬的時(shí)候漲薪200，心情絕對是不一樣的。如果系統(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對應(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)先級轉(zhuǎn)權(quán)重都進(jìn)行運(yùn)算，而是提前運(yùn)算好了放在數(shù)組，每次用的時(shí)候查一下就可以了。反權(quán)重的值也提前計(jì)算好了放在了數(shù)組里。下面我們來看一下：

linux-src/kernel/sched/core.c

?

const int sched_prio_to_weight[40] = { /* -20 */     88761,     71755,     56483,     46273,     36291, /* -15 */     29154,     23254,     18705,     14949,     11916, /* -10 */      9548,      7620,      6100,      4904,      3906, /*  -5 */      3121,      2501,      1991,      1586,      1277, /*   0 */      1024,       820,       655,       526,       423, /*   5 */       335,       272,       215,       172,       137, /*  10 */       110,        87,        70,        56,        45, /*  15 */        36,        29,        23,        18,        15,};
const u32 sched_prio_to_wmult[40] = { /* -20 */     48388,     59856,     76040,     92818,    118348, /* -15 */    147320,    184698,    229616,    287308,    360437, /* -10 */    449829,    563644,    704093,    875809,   1099582, /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326, /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587, /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126, /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717, /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,};

?

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ì)算。

下面我們再來看一下設(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)。然后代碼對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是對權(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)先級時(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

?

static voidenqueue_task_fair(struct rq *rq, struct task_struct *p, int flags){  enqueue_entity(cfs_rq, se, flags);}
static voidenqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags){  account_entity_enqueue(cfs_rq, se);}
static voidaccount_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se){  update_load_add(&cfs_rq->load, se->load.weight);  cfs_rq->nr_running++;}
static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags){  dequeue_entity(cfs_rq, se, flags);}
static voiddequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags){  account_entity_dequeue(cfs_rq, se);}
static voidaccount_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se){  update_load_sub(&cfs_rq->load, se->load.weight);  cfs_rq->nr_running--;}

?

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

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

我們再來看一下玻璃杯的水位是如果表示的。玻璃杯的水位就是進(jìn)程的虛擬運(yùn)行時(shí)間，是進(jìn)程進(jìn)行排隊(duì)的鍵值。玻璃杯的水位等于玻璃杯中水的體積除以玻璃杯的橫截面積，進(jìn)程的虛擬運(yùn)行時(shí)間等于進(jìn)程的實(shí)際運(yùn)行時(shí)間除以相對權(quán)重。進(jìn)程的實(shí)際運(yùn)行時(shí)間是一段一段的，所以進(jìn)程的虛擬運(yùn)行時(shí)間也是一段一段增長的。進(jìn)程的虛擬運(yùn)行時(shí)間還會(huì)在進(jìn)程入隊(duì)時(shí)與運(yùn)行隊(duì)列的最小虛擬時(shí)間相比較，如果小的話會(huì)直接進(jìn)行增加，并不對應(yīng)實(shí)際的運(yùn)行時(shí)間。這也就是我們前面說的對玻璃杯進(jìn)行填充泡沫的操作。相對權(quán)重是相對于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í)間也在一直增長著。

進(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í)間就沒有對應(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中對nice 0的進(jìn)程直接返回實(shí)際運(yùn)行時(shí)間，對于其它進(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

?

static void update_min_vruntime(struct cfs_rq *cfs_rq){  struct sched_entity *curr = cfs_rq->curr;  struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);
  u64 vruntime = cfs_rq->min_vruntime;
  if (curr) {    if (curr->on_rq)      vruntime = curr->vruntime;    else      curr = NULL;  }
  if (leftmost) { /* non-empty tree */    struct sched_entity *se = __node_2_se(leftmost);
    if (!curr)      vruntime = se->vruntime;    else      vruntime = min_vruntime(vruntime, se->vruntime);  }
  /* ensure we never gain time by being placed backwards. */  cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);#ifndef CONFIG_64BIT  smp_wmb();  cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;#endif}

?

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

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

定時(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)先級時(shí)，更改優(yōu)先級會(huì)改變權(quán)重，對已經(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)先級分成時(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í)間片。對于在一個(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)度模型中玻璃杯的水位是一直在增長的，沒有時(shí)間片遞減的邏輯，也不存在什么調(diào)度周期。但是一個(gè)玻璃杯總是不能一直接水的，接水時(shí)間長了也是要把切走的。在CFS中玻璃杯一次接水的最大量就叫做時(shí)間片。這個(gè)時(shí)間片和傳統(tǒng)的時(shí)間片是不一樣的，這個(gè)時(shí)間片是個(gè)檢測量，沒有遞減的邏輯。那么時(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ì)對這個(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ù)對2的對數(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

?

static unsigned int sched_nr_latency = 8;
static u64 __sched_period(unsigned long nr_running){  if (unlikely(nr_running > sched_nr_latency))    return nr_running * sysctl_sched_min_granularity;  else    return sysctl_sched_latency;}

?

調(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ì)延長了。不過很大概率不會(huì)延長的，因?yàn)橐话愣紩?huì)有進(jìn)程因?yàn)樽枞M(jìn)行主動(dòng)調(diào)度從而讓出來一部分時(shí)間。

我們再來總結(jié)一下調(diào)度周期、調(diào)度延遲、調(diào)度粒度、時(shí)間片的概念意義和它們在CFS中的變量意義以及相互之間的關(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ì)列長短的影響。在CFS中，調(diào)度延遲的概念完全變了，調(diào)度延遲變成了調(diào)度周期的最小值。時(shí)間片的概念是指一個(gè)進(jìn)程一次最多只能運(yùn)行多長時(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

?

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);}

?

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ù)指針，對于普通進(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è)操作是沒有必要的，但是按照我們在CFS調(diào)度模型中的要求，盡量使所有玻璃杯在任意時(shí)刻的水位都盡量相同，這個(gè)操作是很有必要的，它能提高公平性。

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

linux-src/kernel/sched/core.c

?

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags){  if (p->sched_class == rq->curr->sched_class)    rq->curr->sched_class->check_preempt_curr(rq, p, flags);  else if (p->sched_class > rq->curr->sched_class)    resched_curr(rq);}

?

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í)間的差值要大于喚醒粒度對應(yīng)的虛擬時(shí)間。

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

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

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

linux-src/include/linux/rbtree_types.h

?

struct rb_root_cached {  struct rb_root rb_root;  struct rb_node *rb_leftmost;};
struct rb_root {  struct rb_node *rb_node;};
struct rb_node {  unsigned long  __rb_parent_color;  struct rb_node *rb_right;  struct rb_node *rb_left;}

?

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ì)首進(jìn)程進(jìn)行操作，因此rb_root_cached中用rb_leftmost對紅黑樹的最下角的節(jié)點(diǎn)(這個(gè)節(jié)點(diǎn)就是vruntime最小的節(jié)點(diǎn)，就是隊(duì)首進(jìn)程)進(jìn)行了緩存，方便查找。

我們經(jīng)常會(huì)對運(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

?

static void __sched notrace __schedule(unsigned int sched_mode){  struct task_struct *prev, *next;  unsigned long *switch_count;  unsigned long prev_state;  struct rq_flags rf;  struct rq *rq;  int cpu;
  cpu = smp_processor_id();  rq = cpu_rq(cpu);  prev = rq->curr;
  prev_state = READ_ONCE(prev->__state);  if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {    if (signal_pending_state(prev_state, prev)) {      WRITE_ONCE(prev->__state, TASK_RUNNING);    } else {      deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);    }  }
  next = pick_next_task(rq, prev, &rf);
  if (likely(prev != next)) {    rq = context_switch(rq, prev, next, &rf);  } else {      }}
void deactivate_task(struct rq *rq, struct task_struct *p, int flags){  p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;
  dequeue_task(rq, p, flags);}
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;
  if (likely(prev->sched_class <= &fair_sched_class &&       rq->nr_running == rq->cfs.h_nr_running)) {    p = pick_next_task_fair(rq, prev, rf);    return p;  }}

?

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ì)列中去，對于阻塞調(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)先級、設(shè)置進(jìn)程親和性、遷移進(jìn)程等操作中成對使用。enqueue_task在進(jìn)程喚醒中也會(huì)使用，下面我們來看一下代碼。

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;
  cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);  if (task_cpu(p) != cpu) {    set_task_cpu(p, cpu);  }
  ttwu_queue(p, cpu, wake_flags);  return success;}
static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags){  struct rq *rq = cpu_rq(cpu);  struct rq_flags rf;
  ttwu_do_activate(rq, p, wake_flags, &rf);}
static voidttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,     struct rq_flags *rf){  activate_task(rq, p, en_flags);  ttwu_do_wakeup(rq, p, wake_flags, rf);}
void activate_task(struct rq *rq, struct task_struct *p, int flags){  enqueue_task(rq, p, flags);
  p->on_rq = TASK_ON_RQ_QUEUED;}
static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags){  p->sched_class->enqueue_task(rq, p, flags);}

?

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算法評價(jià)

現(xiàn)在我們對CFS調(diào)度算法的各個(gè)方面都有了基本的了解，讓我們再看一下CFS調(diào)度模型圖來回憶一下：

回憶完之后，我們對CFS算法進(jìn)行一下分析和評價(jià)。首先CFS取消了對IO密集型和CPU密集型進(jìn)程的探測，避免了由于誤探而產(chǎn)生的問題。雖然沒有對IO密集型和CPU密集型進(jìn)程進(jìn)行探測區(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ì)比較高。

我們再來看公平性，CFS的名字就叫做完全公平調(diào)度，所以肯定是很公平的。公平性主要體現(xiàn)在以下幾個(gè)方面。一是取消了對IO密集型和CPU密集型進(jìn)程的探測，不會(huì)對IO密集型進(jìn)程進(jìn)行特殊的照顧，所以進(jìn)程都一視同仁。二是優(yōu)先級轉(zhuǎn)權(quán)重的時(shí)候采用了等比數(shù)列，使得nice值相差1的進(jìn)程獲得的CPU時(shí)間比例總是相差10%，很公平。三是低優(yōu)先級的進(jìn)程隨著別人的水位增長總是會(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)，代碼簡潔，調(diào)度效率是O(logn)也會(huì)提高其吞吐量。

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

? 五、總結(jié)回顧 ? ?

我們在此文中講了非常多關(guān)于進(jìn)程調(diào)度的知識(shí)點(diǎn)，下面我們來總結(jié)一下。

對著這個(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ù)思考琢磨才能更好的理解和掌握它。