電子發(fā)燒友App
作者簡介：
程磊，一線碼農(nóng)，在某手機公司擔(dān)任系統(tǒng)開發(fā)工程師，日常喜歡研究內(nèi)核基本原理。
目錄
一、進程調(diào)度概覽
1.1 什么是調(diào)度 1.2 為什么要調(diào)度 1.3 為什么能調(diào)度 1.4 何時調(diào)度 1.5 如何調(diào)度 1.6 調(diào)度均衡 1.7 調(diào)度器評價 1.8 調(diào)度器歷史
二、進程調(diào)度框架
2.1 調(diào)度隊列 2.2 進程喚醒 2.3 調(diào)度時機 2.4 調(diào)度流程 2.5 調(diào)度算法 2.6 進程優(yōu)先級 2.7 進程切換
三、SMP管理
3.1 CPU拓撲結(jié)構(gòu) 3.2 CPUMASK
四、基本分時調(diào)度
4.1 CFS調(diào)度模型 4.2 CFS運行隊列 4.3 進程狀態(tài)表示 4.4 優(yōu)先級與權(quán)重 4.5 虛擬運行時間 4.6 調(diào)度周期與粒度 4.7 搶占調(diào)度 4.8 入隊與出隊 4.9 CFS算法評價
五、總結(jié)回顧
? 一、進程調(diào)度概覽 ? ?
進程調(diào)度是操作系統(tǒng)最重要的內(nèi)容之一，也是學(xué)習(xí)操作系統(tǒng)的重點和難點。關(guān)于進程調(diào)度，我們首先就會問出一些問題，什么是進程調(diào)度，為什么要進程調(diào)度，如何進行調(diào)度。下面我們用一幅圖把這些問題關(guān)聯(lián)起來：
這張圖把進程調(diào)度的所有問題和知識點都關(guān)聯(lián)了起來，本文后面所有的內(nèi)容都是對這張圖的解釋和擴展延伸，下面讓我們來一一講解。
1.1 什么是調(diào)度
什么是調(diào)度？調(diào)度是CPU資源管理器。操作系統(tǒng)的作用之一就是系統(tǒng)資源管理器。CPU是計算機系統(tǒng)中最重要的資源，當(dāng)然也要管理。所有進程的運行都需要CPU，對CPU該如何管理呢？對于直接共享型的事物，我們有兩種管理方法：一種是時間分割管理，另一種是空間分割管理。由于CPU自身的特性，沒有空間分割相似性，只有時間分割相似性，所以我們只能對CPU進行時間分割管理。對CPU進行時間分割管理的具體做法就叫做進程調(diào)度。
那么調(diào)度的是什么呢？進程調(diào)度，調(diào)度的當(dāng)然是進程啦，也對也不對。我們知道進程是資源分配的單位，線程是執(zhí)行的單位。早期的時候沒有多線程，進程就是線程，線程就是進程，所以此時進程調(diào)度調(diào)度的是進程。但是當(dāng)有了多線程之后，線程變成了執(zhí)行的單位，進程不再是執(zhí)行的單位，進程調(diào)度調(diào)度的就是線程了。不過由于歷史原因，大家都習(xí)慣叫進程調(diào)度，所以現(xiàn)在這個領(lǐng)域的名稱還是叫進程調(diào)度。后文中說到調(diào)度進程的地方都是調(diào)度的線程，由于習(xí)慣問題，我們還說調(diào)度進程不說調(diào)度線程，請大家要注意。
對線程的調(diào)度可以有兩種方式：一種是直接調(diào)度線程，不考慮它們所屬的進程，這種方式叫做直接調(diào)度或者一級調(diào)度；另一種是先調(diào)度進程，再在進程內(nèi)部調(diào)度線程，這種方式叫做間接調(diào)度或者二級調(diào)度。POSIX規(guī)定，操作系統(tǒng)可以選擇這兩種方式中的任何一種都行。Linux選擇的是一級調(diào)度，為什么會這么選擇呢？主要是為了提高進程的并發(fā)性，充分利用多CPU多核的優(yōu)勢。如果使用二級調(diào)度的話，看似每個進程之間都公平了，但是有些進程的計算量比較大，就無法通過多開線程提高自己的性能，這樣對系統(tǒng)整體的性能是有害的，也不利用發(fā)揮計算機多CPU的優(yōu)勢。一級調(diào)度看似對有些進程不公平，但是計算量小的進程少開線程，計算量大的進程多開線程，相對還是很公平的。
就像國家希望每個企業(yè)都做大做強，但是同時也會反壟斷一樣。Linux也推出了cgroup組調(diào)度機制，來限制某個或者某一類進程對CPU資源的過度占用。本文中不講cgroup組調(diào)度機制，后文的講解都是假設(shè)沒有cgroup組調(diào)度。
1.2 為什么要調(diào)度
我們知道了什么是調(diào)度，那么為什么要調(diào)度呢，沒有調(diào)度會怎么樣呢？最早的計算機是沒有調(diào)度的，程序只能一個一個地運行，一個進程死亡之后才能去運行下一個進程。這里面首先存在的問題就是我們沒法同時運行多個進程。其次就算我們不需要同時運行多個進程，程序在運行的過程中如果要等IO，CPU就只能空轉(zhuǎn)，這也十分浪費CPU資源。于是最早的多任務(wù)——協(xié)作式多任務(wù)誕生了，當(dāng)程序由于要等IO而阻塞時就會去調(diào)度執(zhí)行其它的進程。但是協(xié)作式多任務(wù)存在著很大的問題，就是每個進程運行的時間片長短是不確定的，而且是很偶然很隨機的。如果一個進程它一直在做運算就是不進行IO操作，那么它就會一直霸占CPU。針對這個問題，當(dāng)時想出的方法是道德解決方案。內(nèi)核向進程提供系統(tǒng)調(diào)用sched_yield，它會使進程主動放棄CPU讓其它進程來執(zhí)行。然后要求所有的程序員在程序中合適的地方盡量多地加入sched_yield調(diào)用。這個方法在當(dāng)時是管用的，因為當(dāng)時計算機的使用者(同時也是程序員)僅限于少數(shù)科研機構(gòu)和政府機關(guān)的部分人員，一臺電腦的共同使用者都認識，面子上還得過得去。
后來隨著計算機的普及，以及計算機的使用者和程序員這兩個角色的分離，主要靠道德約束的協(xié)作式多任務(wù)已經(jīng)行不通了，我們需要強制性多任務(wù)，也就是搶占式多任務(wù)。搶占式多任務(wù)使得每個進程都可以相對公平地平分CPU時間，如果一個進程運行了過長的時間就會被強制性地調(diào)度出去，不管這個進程是否愿意。有了搶占式多任務(wù)，我們在宏觀上不僅可以同時運行多個進程，而且它們會一起齊頭并進地往前運行，不會出現(xiàn)某個進程被餓死的情況，這樣我們使用電腦的體驗就非常完美了。搶占式多任務(wù)和協(xié)作式多任務(wù)不是對立的，它們是相互獨立的，可以同時存在于系統(tǒng)中。
搶占又分為用戶搶占和內(nèi)核搶占。由于搶占對進程來說是異步的，進程被搶占時不一定運行在什么地方，有可能運行在用戶空間，也有可能運行在內(nèi)核空間(進程通過系統(tǒng)調(diào)用進入內(nèi)核空間)。如果搶占點是在用戶空間，那么搶占就是安全的，如果在內(nèi)核空間就不一定安全，這是為什么呢？因為對于用戶空間來說，如果搶占會導(dǎo)致線程同步問題，那么用戶空間有責(zé)任使用線程同步機制來保護臨界區(qū)，只要用戶空間做好同步就不會出問題。如果內(nèi)核也做好了同步措施，內(nèi)核搶占也不會出問題，但是內(nèi)核最初的設(shè)計就沒有考慮內(nèi)核搶占問題，所以剛開始的時候內(nèi)核是不能搶占的。后來內(nèi)核開發(fā)者對內(nèi)核進行了完善，把內(nèi)核所有的臨界區(qū)都加上了同步措施，然后內(nèi)核就是可搶占的了。內(nèi)核能搶占了不代表內(nèi)核一定會搶占，內(nèi)核會不會搶占由config選項控制，可以開啟也可以關(guān)閉，因為內(nèi)核搶占還會影響系統(tǒng)的響應(yīng)性和性能。開啟內(nèi)核搶占會提高系統(tǒng)的響應(yīng)性但是會降低一點性能，關(guān)閉內(nèi)核搶占會降低系統(tǒng)的響應(yīng)性但是會提高一點性能。因此把內(nèi)核搶占做成配置項，可以讓大家靈活配置。服務(wù)器系統(tǒng)一般不需要與用戶交互，所以會關(guān)閉內(nèi)核搶占來提高性能，桌面系統(tǒng)會開啟內(nèi)核搶占來提高系統(tǒng)的響應(yīng)性，來增加用戶體驗。
現(xiàn)在我們再來看一下為什么要調(diào)度。因為如果沒有調(diào)度的話，就不能實現(xiàn)多任務(wù)，一次就只能運行一個程序，我們使用電腦的體驗就會大大降低。有了調(diào)度就有了多任務(wù)，我們就能同時在電腦上做很多事情，使用體驗就會非常好。
1.3 為什么能調(diào)度
我們再來看看為什么能調(diào)度呢。我們把協(xié)作式多任務(wù)叫做主動調(diào)度，搶占式多任務(wù)叫做被動調(diào)度。為什么能調(diào)度分為兩部分：為什么能觸發(fā)調(diào)度和為什么能執(zhí)行調(diào)度。對于主動調(diào)度，調(diào)度是進程主動觸發(fā)的，這個是肯定能的。對于被動調(diào)度，在圖靈機模型中是做不到的，因為圖靈機是一條線性一直往前走的，進程在執(zhí)行時，進程要是不主動，是不可能跳到其它進程來執(zhí)行的。被動調(diào)度能做到的原因關(guān)鍵就在于中斷機制，因為中斷是強行在正常的執(zhí)行流中插入了一段代碼，它能改變后續(xù)代碼的走向。有了中斷機制，我們就可以創(chuàng)建一個定時器中斷，以固定的時間間隔比如每10ms來觸發(fā)中斷，檢測進程是否運行時間過長，如果過長就觸發(fā)調(diào)度。這樣任何進程都不可能霸占CPU，所以進程都能公平地共享CPU時間。這里引用其中的一幅圖來看一下：
可以看到在純圖靈機模型中，進程如果不主動進行調(diào)度，是沒有外力強迫進程進行調(diào)度的，進程就能一直霸占CPU。有了中斷機制之后，在中斷的處理中可以觸發(fā)調(diào)度，在中斷返回的點可以執(zhí)行調(diào)度，這樣就可以避免進程霸占CPU了。
前面說的是為何能觸發(fā)進程調(diào)度，主動調(diào)度是進程自己觸發(fā)的，被動調(diào)度是在中斷中觸發(fā)的。現(xiàn)在來看看為何能執(zhí)行調(diào)度，執(zhí)行調(diào)度包括兩部分：選擇進程和切換進程。選擇進程是純軟件的，肯定能實現(xiàn)。切換進程是怎么切換呢？一個進程執(zhí)行的好好的，怎么就切換了呢，需不需要硬件的支持呢？進程切換主要是切換執(zhí)行棧和用戶空間，這兩個都需要用到CPU特定的指令。進程切換的具體原理和細節(jié)我們在2.7節(jié)中講。
1.4 何時調(diào)度
我們前面已經(jīng)講了主動調(diào)度(協(xié)作式多任務(wù))和被動調(diào)度(搶占式多任務(wù))。
對于主動調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是同步的、一體的，觸發(fā)即執(zhí)行。主動調(diào)度發(fā)生的時機有IO等待、加鎖失敗等各種阻塞操作以及用戶空間主動調(diào)用sched_yield。
對于被動調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是異步的、分離的，觸發(fā)調(diào)度并不會立馬執(zhí)行調(diào)度，而是做個需要調(diào)度的標(biāo)記，然后在之后的某個合適的地方會檢測這個標(biāo)記，如果被設(shè)置就進行調(diào)度。觸發(fā)調(diào)度的點有：在定時器中斷中發(fā)現(xiàn)當(dāng)前進程超時了，在喚醒進程時發(fā)現(xiàn)新進程需要搶占當(dāng)前進程，在遷移進程時發(fā)現(xiàn)新進程需要搶占當(dāng)前進程，在改變進程優(yōu)先級時發(fā)現(xiàn)新進程需要搶占當(dāng)前進程。其中第一個觸發(fā)點是當(dāng)前進程需要被搶占，它是用來保證公平調(diào)度，防止進程霸占CPU的，后三個觸發(fā)點是新進程需要搶占當(dāng)前進程，它是用來提高系統(tǒng)響應(yīng)性的。執(zhí)行調(diào)度的點有：系統(tǒng)調(diào)用完成之后即將返回用戶空間，中斷完成之后即將返回用戶空間，如果開啟了內(nèi)核搶占的話則還有,中斷完成之后即將返回內(nèi)核,如果中斷發(fā)生在禁止搶占臨界區(qū)中，那么中斷完成之后返回內(nèi)核是不會執(zhí)行調(diào)度的，而是會在臨界區(qū)結(jié)束的時候執(zhí)行調(diào)度。下面我們借用《深入理解Linux中斷機制》中的幾個圖來看一下這幾個執(zhí)行調(diào)度檢測點：
系統(tǒng)調(diào)用完成之后即將返回用戶空間和中斷完成之后即將返回用戶空間，是非常好的執(zhí)行進行調(diào)度的點，也就是此圖中的三個箭頭的地方。CPU異常在意義上不是系統(tǒng)調(diào)用，但是在形式上和邏輯上相當(dāng)于是系統(tǒng)調(diào)用。
中斷發(fā)生在內(nèi)核空間的場景，如果開啟了內(nèi)核搶占，如果被搶占的內(nèi)核代碼不是在禁用搶占臨界區(qū)，中斷返回時是執(zhí)行調(diào)度的點。如果被搶占的內(nèi)核代碼在禁用搶占臨界區(qū)中，在執(zhí)行調(diào)度的點被推遲到了臨界區(qū)的出口處。
1.5 如何調(diào)度
現(xiàn)在到了執(zhí)行調(diào)度的時刻了。執(zhí)行調(diào)度分為兩步：一是選擇下一個要執(zhí)行的進程，二是切換進程。選擇下一個要執(zhí)行的進程，這就是調(diào)度算法了。首先調(diào)度算法只能從Runnable的進程中進行選擇，不能選擇Blocked進程，因為選擇了也沒有意義。其次算法還要區(qū)分進程類型，比如普通進程與實時進程，肯定要優(yōu)先選擇實時進程，在同一類型的進程中還要有具體的算法來決定到底選擇哪個進程。在Linux中一共把進程分為了5類，每一類都有一個具體的算法。類之間的關(guān)系是優(yōu)先選擇高類的進程，只有當(dāng)高類沒有Runnable進程時才會去選擇低類進程。
進程選擇好了之后就要切換進程了。切換進程分兩步：第一步是切換用戶空間，第二步是切換執(zhí)行棧(線程棧)。如果要切換的兩個線程屬于同一個進程就不需要切換用戶空間了。切換用戶空間是一個CPU架構(gòu)相關(guān)的事情，在x86 CPU上是給CR3寄存器賦值新進程的頁表樹的根指針。此時切換的執(zhí)行棧是線程的內(nèi)核棧，執(zhí)行棧代表的是當(dāng)前線程的執(zhí)行情況，切換執(zhí)行棧就是切換線程。線程的用戶棧信息都在內(nèi)核棧里保存著。切換完內(nèi)核棧之后，線程繼續(xù)執(zhí)行就會返回用戶空間，由于此時用戶空間已經(jīng)切換完成，內(nèi)核棧上也保存著用戶棧的信息，所以線程能返回到正確的用戶空間線程上去。
下面我們畫個圖來看一下：
對于一個CPU來說，永遠只有一個當(dāng)前進程在運行，當(dāng)執(zhí)行進程調(diào)度時，需要從其它進程中選擇一個進程，把它旋轉(zhuǎn)到最下方作為當(dāng)前進程，它就開始運行了。
1.6 調(diào)度均衡
前面所說的都是針對一個CPU的情況，對于多個CPU來說，每個CPU也是這樣的邏輯。但是有一點不同的是，如果一個系統(tǒng)上的多個CPU忙的忙死閑的閑死，顯然不太好，因此多個CPU之間會進行調(diào)度均衡。調(diào)度均衡可以分為個體均衡和總體均衡。個體均衡是從進程的角度出發(fā)選擇到一個相對清閑的CPU上去運行。總體均衡是從CPU的角度出發(fā)如何從別的CPU上拉取一些進程到自己這來執(zhí)行，使得所有CPU的工作量盡量平均。個體均衡的觸發(fā)點有三個：一是新進程剛創(chuàng)建時，二是進程要執(zhí)行新程序時，三是進程被喚醒時，在這三個點進程都可以選擇去哪個CPU的運行隊列上去等待執(zhí)行。在個體均衡下，每個進程都盡量選擇相對清閑的CPU，所以所有CPU的負載應(yīng)該還是會比較均衡的。但是時間長了可能還是會出現(xiàn)負載不均衡的情況，此時就要進行總體均衡了。總體均衡的觸發(fā)點有三個：一是CPU即將idle前會去找到最忙的CPU然后拉取一些任務(wù)過來；二是定時器中斷的周期性檢測，會檢查是否所有的CPU都一樣忙，如果忙閑差別太大就會進行進程遷移，使得所有CPU忙閑程度接近；三是在idle進程中如果CPU發(fā)現(xiàn)自己太忙而有的CPU在idle就會喚醒那個CPU進行負載均衡。
1.7 調(diào)度器評價
狹義的調(diào)度器指的是具體的調(diào)度算法，廣義的調(diào)度器指的是整個調(diào)度體系。不過兩者的評價指標(biāo)是相同的，所以我們這里不具體區(qū)分調(diào)度器是指調(diào)度算法還是調(diào)度體系。調(diào)度器的評價指標(biāo)有以下幾個：
1.響應(yīng)性，當(dāng)一個進程發(fā)生事件需要去處理的時候能否及時被調(diào)度。這一點和使用體驗是密切相關(guān)的，當(dāng)我們用鼠標(biāo)點擊一個程序的時候，肯定希望程序立即能做出響應(yīng)，如果程序過了好幾秒才有反應(yīng)，那我們肯定會很煩的。
2.吞吐量，系統(tǒng)在相同的時間內(nèi)能夠運行更多的程序、執(zhí)行更多的指令。這個首先要求調(diào)度器本身的代碼要盡量的高效。如果調(diào)度器寫得非常復(fù)雜，運行一次就需要好幾毫秒的話，那留給進程運行的時間就不多了。其次進程調(diào)度的頻率要低，如果進程調(diào)度的頻率比較高的話，那調(diào)度器執(zhí)行的次數(shù)就比較多，從而占用了較多的CPU時間，而且頻繁切換進程也會影響緩存的性能。從這一點來看響應(yīng)性和吞吐量是有矛盾的，提高響應(yīng)性會增加進程切換的頻率，而這會降低系統(tǒng)的吞吐量。
3.公平性，指的是相對公平性，每個進程實際獲得的時間份額與應(yīng)當(dāng)獲得的時間份額都相差不大。不會出現(xiàn)有些進程饑餓的情況，也不會出現(xiàn)有些進程獲得過多時間份額的情況。
4.適應(yīng)性，指的是系統(tǒng)無論是調(diào)度幾個進程還是調(diào)度幾萬個進程，都能撐得住，都能收放自如，各項指標(biāo)都不能受到太大的影響。
5.節(jié)能性，自從智能手機越來越普及，而手機的電池技術(shù)一直沒有較大的突破，所以省電對手機來說就是一項非常重要的任務(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)度器邏輯是一樣的。全局只有一個運行隊列，所有進程都放在一個隊列上。進程區(qū)分IO密集型和CPU密集型，根據(jù)進程的睡眠時間計算動態(tài)優(yōu)先級，按照動態(tài)優(yōu)先級決定進程的調(diào)度順序，按照優(yōu)先級分配進程的時間片大小，時間片大小是等差數(shù)列。進程在運行隊列上并沒有特定的排序，每次選擇下一個進程的時候都要遍歷整個隊列，所以算法的時間復(fù)雜度是O(n)。在SMP上也只有一個運行隊列，當(dāng)CPU比較多進程也比較多的時候，鎖沖突比較嚴(yán)重。
O(1) Scheduler: v2.5 – v2.6.22
此調(diào)度器主要是針對傳統(tǒng)調(diào)度器進行了改進。首先把運行隊列從單一變量變成了per-CPU變量，每個CPU一個運行隊列，這樣就不會有鎖沖突了，不過這樣就需要調(diào)度均衡了。其次把運行隊列的一個鏈表分成了兩個鏈表數(shù)組：活動數(shù)組和過期數(shù)組。時間片沒用耗盡的進程放在活動數(shù)組中，時間片耗盡的進程放在過期數(shù)組中，當(dāng)所有進程的時間片都耗盡的時候交換兩個數(shù)組，重新分配時間片。兩個數(shù)組都使用動態(tài)優(yōu)先級排序，并用bitmap來表示哪個優(yōu)先級隊列中有可運行的進程，把選擇進程的算法復(fù)雜度降低到了O(1)。對進程區(qū)分IO密集型和CPU密集型并計算動態(tài)優(yōu)先級這一點和傳統(tǒng)調(diào)度器一樣沒有變。
SD Scheduler：(未合入)
樓梯調(diào)度器，它是對O(1)調(diào)度器的改進，算法復(fù)雜還是O(1)。之前的調(diào)度器都區(qū)分IO密集型和CPU密集型，算法要對進程的類型進行探測，根據(jù)探測結(jié)果調(diào)整動態(tài)優(yōu)先級。這就有很大的問題，探測不一定準(zhǔn)確，而且進程還可以欺騙調(diào)度器，最終會導(dǎo)致調(diào)度有很大的不公平性。樓梯調(diào)度器是第一次嘗試使用公平調(diào)度算法，它廢除了動態(tài)優(yōu)先級，不再區(qū)分IO密集型進程和CPU密集型進程，但是仍然讓IO密集型進程保持較高的響應(yīng)性。在實現(xiàn)上，樓梯調(diào)度算法廢棄了過期數(shù)組，只使用一個數(shù)組。當(dāng)進程使用完自己的時間片之后，其時間片就會被減半并下降到下一個優(yōu)先級，其本身的優(yōu)先級還是不變的。當(dāng)進程下降到最后一個優(yōu)先級之后就再回到它本來的優(yōu)先級隊列并重新分配時間片。整個過程就像下樓梯一樣，所以這個算法就叫做樓梯調(diào)度器。此算法雖然沒有合入到標(biāo)準(zhǔn)內(nèi)核，但是它第一次證明了可以采取完全公平的思想進行調(diào)度，也就是不區(qū)分IO密集型和CPU密集型進程。
RSDL Scheduler：(未合入)
旋轉(zhuǎn)樓梯調(diào)度器，是對樓梯調(diào)度器的改進。又重新引入了過期數(shù)組，為每個優(yōu)先級都分配一個組時間配額記為Tg，進程本身的時間片記為Tp。當(dāng)進程用完自己的時間片時會下降一個優(yōu)先級，當(dāng)一個優(yōu)先級的Tg被用完時，組內(nèi)所有的進程都會下降一個優(yōu)先級。進程下降到最低優(yōu)先級之后會被放入過期數(shù)組，當(dāng)活動數(shù)組為空時就會交換活動數(shù)組和過期數(shù)組。由于加了Tg，使得低優(yōu)先級進程的調(diào)度延遲可控，進一步增加了公平性。
CFS: Completely Fair Scheduler: v2.6.23 – now
完全公平調(diào)度器，從SD/RSDL中吸取了完全公平的思想，不再區(qū)分IO密集型進程與CPU密集型進程，不再根據(jù)睡眠時間調(diào)整動態(tài)優(yōu)先級，所有普通進程都按優(yōu)先級相對平分CPU時間，算法復(fù)雜度是O(logn)。此時對調(diào)度器框架也進行了重構(gòu)，和之前的有很大的不同。之前的調(diào)度器是一個算法調(diào)度所有進程，在算法內(nèi)部區(qū)別對待實時進程和普通進程。現(xiàn)在的調(diào)度器框架是先區(qū)分不同類型的進程，普通進程一個調(diào)度類，實時進程一個調(diào)度類，調(diào)度類里面再去實現(xiàn)具體的調(diào)度算法。CFS是普通調(diào)度類的算法。
? 二、進程調(diào)度框架 ? ?
前面我們對進程調(diào)度的概念和邏輯進行了講解，現(xiàn)在我們來看一下Linux上進程調(diào)度的框架結(jié)構(gòu)。本章只講總體框架，不講具體算法，具體算法在后面的章節(jié)中講。
2.1 調(diào)度隊列
我們先來看一下進程的狀態(tài)轉(zhuǎn)換圖。
處于就緒(Runnable)狀態(tài)的進程可以被調(diào)度到CPU上去執(zhí)行。但是處于就緒狀態(tài)的進程可能不止一個，所以我們需要一個運行隊列來安放所有就緒的進程，由于CPU也不止一個，所以我們需要NR_CPU個運行隊列。
我們看一下調(diào)度隊列的定義(代碼經(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)核定義了一個per-CPU變量runqueues，其類型是struct rq。所有的就緒進程都會被放入某個CPU的rq上去，具體放到哪個rq上，這個在調(diào)度均衡里面講。內(nèi)核一共定義了五個調(diào)度類(這個在2.5中細講)，屬于不同調(diào)度類的進程會被放入不同的子隊列，所以rq中包含三個子運行隊列cfs_rq、rt_rq、dl_rq。為啥只有3個子運行隊列呢？因為有兩個調(diào)度類idle、stop，每個CPU只能有一個進程，所以沒必要弄個隊列，直接關(guān)聯(lián)它們的進程就可以了，就是上面代碼中的兩個struct task_struct * 類型的指針變量idle、stop。
2.2 進程喚醒
進程是怎么被放入運行隊列的呢？都是通過進程喚醒來放入的，包括新創(chuàng)建的進程也是。新建喚醒和阻塞喚醒的代碼不太一樣，下面我們分別來看一下。
我們先來看一下新建喚醒的代碼：
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中會調(diào)用此函數(shù)喚醒新創(chuàng)建的進程，把它放入到運行隊列中等待被調(diào)度。此函數(shù)會先調(diào)用select_task_rq來選擇自己要去哪個CPU的rq上去，然后調(diào)用activate_task把進程加入到相應(yīng)的運行隊列上，最后調(diào)用check_preempt_curr看一下是否需要搶占，如果需要就觸發(fā)搶占。select_task_rq的邏輯我們在調(diào)度均衡中講，check_preempt_curr的邏輯我們在下一節(jié)的被動調(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)核并不是直接用這個函數(shù)，而是提供了三個封裝函數(shù)。wake_up_process是默認的通用的進程喚醒接口，能喚醒TASK_NORMAL狀態(tài)的進程。TASK_NORMAL就是阻塞狀態(tài)的進程，包含TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE，前者是前睡眠能被信號喚醒，后者是深睡眠不能被信號喚醒。還有一些特殊狀態(tài)的進程如被暫停的進程是不能通過wake_up_process來喚醒的，所以內(nèi)核還提供了接口wake_up_state，可以自己指定喚醒什么狀態(tài)的進程。還有一個封裝函數(shù)default_wake_function，它是wait_queue的默認喚醒函數(shù)。
try_to_wake_up函數(shù)首先進行一些檢測，先檢測被喚醒的進程是否為當(dāng)前進程，如果是的話直接go out。再檢測進程的狀態(tài)是否與state相符合，不符合就不喚醒，再看一下進程是否已經(jīng)處于喚醒狀態(tài)了，如果是就沒有必要喚醒了。然后調(diào)用select_task_rq選擇要到哪個CPU的運行隊列上去運行，最后調(diào)用ttwu_queue把進程放到目標(biāo)運行隊列上去。基本邏輯和wake_up_new_task是一樣的。
2.3 調(diào)度時機
進程放入運行隊列之后就等著被調(diào)度到CPU上去運行了。但是當(dāng)前進程正在使用著CPU，它什么時候能把CPU讓給其它進程去運行呢？有兩種情況：一是當(dāng)前進程主動讓出CPU，這叫主動調(diào)度；二是當(dāng)前進程被動讓出CPU，這叫被動調(diào)度，也就是進程搶占。
主動調(diào)度：
主動調(diào)度又可以分為自愿性主動調(diào)度和非自愿性主動調(diào)度。自愿性主動調(diào)度是指進程主動調(diào)用sched_yield讓出CPU，進程本身還會回到運行隊列中去等待下次調(diào)度。如果運行隊列中沒有其它進程的話，此進程還會繼續(xù)運行。非自愿性主動調(diào)度是指進程運行時遇到了無法繼續(xù)運行的情況，只能進行調(diào)度讓其它進程運行。進程無法繼續(xù)運行的情況有加鎖失敗、要讀的文件現(xiàn)在不在內(nèi)存中、進程死亡等。
下面我們來看一個非自愿性主動調(diào)度的例子，信號量獲取失敗時的操作：
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;}
?
先定義一個等待項，把自己加入到信號量的等待列表中，然后調(diào)用schedule_timeout執(zhí)行調(diào)度。schedule_timeout和普通的調(diào)度函數(shù)schedule的區(qū)別是：schedule只能等著被具體的事件喚醒，schedule_timeout可以被事件喚醒，如果事件在規(guī)定的時間沒有到來就會被定時器超時喚醒。
被動調(diào)度：
如果進程自己不調(diào)用sched_yield，也不調(diào)用任何會阻塞的函數(shù)，那么進程豈不是就可以一直霸占著CPU了。所以內(nèi)核還提供了被動調(diào)度，強制進行進程調(diào)度，避免一個進程長時間霸占CPU。被動調(diào)度是被動的，不能由進程主動去調(diào)度，所以被動調(diào)度和主動調(diào)度的模式差別很大。被動調(diào)度的過程分為兩步：觸發(fā)調(diào)度和執(zhí)行調(diào)度。觸發(fā)調(diào)度僅僅是做個標(biāo)記，告訴系統(tǒng)需要調(diào)度了。執(zhí)行調(diào)度是系統(tǒng)會在某些特定的點去檢查調(diào)度標(biāo)記，如果被設(shè)置的話就執(zhí)行調(diào)度。觸發(fā)調(diào)度的點有：定時器中斷、喚醒進程時、遷移進程時、改變進程優(yōu)先級時。執(zhí)行調(diào)度的點有：從系統(tǒng)調(diào)用返回用戶空間、從中斷返回用戶空間、從中斷返回內(nèi)核、禁用搶占臨界區(qū)結(jié)束、禁用軟中斷臨界區(qū)結(jié)束、cond_resched調(diào)用點。
定時器中斷是保證搶占式多任務(wù)能實現(xiàn)的關(guān)鍵。因為其它被動調(diào)度的觸發(fā)點是不確定的，只有定時器中斷是確定的周期性的，因此定時器中斷也被叫做調(diào)度tick。定時器中斷的頻率是個kconfig選項，可選的值有100、250、300、1000。默認選項是250，也就是說每4ms就會有一個定時器中斷，這樣就能保證被動調(diào)度的及時性，不會有進程過長的占用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}
?
在低精度定時器、高精度定時器與固定tick、動態(tài)tick的不同組合下，定時器中斷觸發(fā)的方式是不同的，但是最終都會調(diào)用scheduler_tick。scheduler_tick會調(diào)用當(dāng)前進程的調(diào)度類的task_tick函數(shù)，此函數(shù)根據(jù)具體的情況可能會觸發(fā)調(diào)度。task_tick函數(shù)的實現(xiàn)細節(jié)我們在具體的調(diào)度算法中再講。
喚醒進程有新建喚醒和阻塞喚醒，它們都有可能觸發(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ù)來處理的。如果被喚醒的進程和當(dāng)前進程是同一個調(diào)度類的則會調(diào)用調(diào)度類的函數(shù)來處理，這個邏輯我們在具體調(diào)度類中再講。如果被喚醒的進程比當(dāng)前進程的調(diào)度類高，則會觸發(fā)調(diào)度。resched_curr函數(shù)最終會在thread_info的flag中設(shè)置TIF_NEED_RESCHED標(biāo)記。
下面我們再來看一下執(zhí)行調(diào)度的點，以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)用完成之后返回用戶空間之前會檢測thread_info flag中的_TIF_NEED_RESCHED，如果設(shè)置了就會執(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中斷機制》。所有中斷和異常的入口函數(shù)都是通過DEFINE_IDTENTRY_IRQ或DEFINE_IDTENTRY(還有其它一些類似的宏)來定義的，其中一定會調(diào)用irqentry_exit。irqentry_exit又會根據(jù)寄存器狀態(tài)來判斷是返回到用戶空間還是內(nèi)核空間。如果是返回到用戶空間則會調(diào)用irqentry_exit_to_user_mode，此函數(shù)的操作和從系統(tǒng)調(diào)用返回用戶空間是相似的，就不再贅述了。如果是返回到內(nèi)核空間則會調(diào)用irqentry_exit_cond_resched，調(diào)用此函數(shù)會先檢測是否配置了CONFIG_PREEMPTION，沒配置就不調(diào)用。CONFIG_PREEMPTION代表的是內(nèi)核搶占，在有些場景中會說成搶占，但是要明白其代表的是內(nèi)核搶占。
內(nèi)核有時候為了同步，需要臨時禁用搶占，這個禁用的是內(nèi)核搶占，因為用戶搶占永遠可以。當(dāng)代碼配置了內(nèi)核搶占時才有效。禁用搶占有引用計數(shù)，釋放最后一個引用時才會重新開啟內(nèi)核搶占。禁用搶占和開啟搶占分別用宏preempt_disable和preempt_enable。preempt_enable代表臨界區(qū)的結(jié)束，會去檢測是否需要調(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增加引用計數(shù)，preempt_enable減少引用計數(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)度，因此在重新開啟軟中斷的時候檢測一下是否需要調(diào)度。
cond_resched調(diào)用點：
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;}
?
在很多比較耗時的內(nèi)核操作中都會加上cond_resched調(diào)用，用來增加搶占調(diào)度的檢測點，提高系統(tǒng)的響應(yīng)性。
2.4 調(diào)度流程
前面講了這么多觸發(fā)調(diào)度的時機，現(xiàn)在該執(zhí)行調(diào)度了。執(zhí)行調(diào)度的總體邏輯是很簡單的，就兩個步驟：選擇進程和切換進程。選擇進程是一個很麻煩的過程，牽涉到調(diào)度類和調(diào)度算法，這個在下一節(jié)中講。切換進程雖然不太麻煩，但是還是比較難以理解的，這個在2.7節(jié)中講。執(zhí)行調(diào)度的入口函數(shù)是__schedule，無論是從什么途徑執(zhí)行的調(diào)度，最終都要調(diào)用這個函數(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，選擇下一個要執(zhí)行的進程。然后是context_switch，切換進程。
2.5 調(diào)度算法
這節(jié)要講的是pick_next_task，在講之前我們要先講一些概念邏輯。
內(nèi)核中有調(diào)度類、調(diào)度策略、調(diào)度算法的概念，這三者是什么意思，又有什么關(guān)系呢？調(diào)度類代表的是進程對調(diào)度器的需求，主要是對調(diào)度緊迫性的需求。調(diào)度策略是調(diào)度類的子類，是對調(diào)度類的細分，是在同一個調(diào)度需求下的細微區(qū)別。調(diào)度算法是對調(diào)度類的實現(xiàn)，一個調(diào)度類一個調(diào)度算法。同一個調(diào)度類的調(diào)度策略是有很強的相似性的，所以在同一個算法中實現(xiàn)，對于它們不同的部分，算法再去進行區(qū)分。下面我們畫個圖來看一下Linux中的所有調(diào)度類、調(diào)度策略和調(diào)度算法。
Linux中一共有五個調(diào)度類，分別是stop(禁令調(diào)度類)、deadline(限時調(diào)度類)、realtime(實時調(diào)度類)、time-share(分時調(diào)度類)、idle(閑時調(diào)度類)。它們的調(diào)度緊迫性從上到下，依次降低。其中禁令調(diào)度類和閑時調(diào)度類有特殊的目的，僅用于內(nèi)核，沒有調(diào)度策略，由于這類進程在內(nèi)核啟動時就設(shè)置好了，一個CPU一個相應(yīng)的進程，所以也不需要調(diào)度算法。另外三個調(diào)度類可用于用戶空間進程，有相應(yīng)的調(diào)度策略和調(diào)度算法，也有相應(yīng)的API供用戶空間來設(shè)置一個進程的調(diào)度策略和優(yōu)先級。調(diào)度類之間的關(guān)系是有高類的進程可運行的情況下，絕對不會去調(diào)度低類的進程，只有當(dāng)高類無Runnable的進程的時候才會去調(diào)度低類的進程。這里面也有一個例外就是內(nèi)核為了防止實時進程餓死普通進程，提供了一個配置參數(shù)，默認值是實時進程如果已經(jīng)占用了95%的CPU時間，就會把剩余5%的CPU時間分給普通進程。
禁令調(diào)度類是內(nèi)核用來執(zhí)行一些特別緊急的事物所使用的。禁令調(diào)度類的進程是內(nèi)核在啟動時就創(chuàng)建好的，一個CPU一個進程，名字叫做[migration/n]，n是CPU_ID，之后就不能再創(chuàng)建此類進程了。內(nèi)核提供了一些接口可以向這些進程push work。調(diào)度均衡要遷移線程的時候會用到這類進程，所以它的名字叫做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)度類的進程優(yōu)先級是最高的，只要此類進程變得Runnable了，就會立馬搶占當(dāng)前進程來運行，所以這幾個接口的名字也都叫做stop_cpu、stop_machine之類的。大家不要望文生義地認為這幾個接口能暫定CPU或者關(guān)機之類的。
限時調(diào)度類屬于硬實時，適用于對調(diào)度時間有明確要求的進程。它只有一個調(diào)度策略，限時調(diào)度策略。一個進程必須通過系統(tǒng)調(diào)用才能把自己設(shè)置為限時調(diào)度策略，并且還要提供三個參數(shù)：運行周期、運行時間和截止時間。運行周期是說這個進程在多長時間內(nèi)想要運行一次，運行時間是說這個進程每次想要運行多長時間，截止時間是說這個進程每次運行結(jié)束不能晚于什么時間。這三個參數(shù)都需要進程根據(jù)自己的實際情況向內(nèi)核提供，而且不是說你提供了就一定能設(shè)置成功，內(nèi)核還要檢測與已有的限時調(diào)度類進程是否沖突，如果有沖突那就無法滿足，就只能返回設(shè)置失敗。還有一點是，運行時間是程序員要提供預(yù)估好的，如果程序?qū)嶋H運行時間超過了預(yù)估時間則會被切走，這可能會導(dǎo)致災(zāi)難性的后果。
實時調(diào)度類屬于軟實時，適用于那些只要可運行就希望立馬能執(zhí)行的進程，比如音視頻的解碼進程。實時調(diào)度類又分為兩個調(diào)度策略，SCHED_FIFO和SCHED_RR。實時調(diào)度類的內(nèi)部邏輯是讓實時優(yōu)先級大的進程先運行，只要有實時優(yōu)先級大的進程可運行，就不會去調(diào)度實時優(yōu)先級小的進程。當(dāng)兩個實時進程的優(yōu)先級相同時，SCHED_RR和SCHED_FIFO這兩個策略就有區(qū)別了，SCHED_FIFO進程如果搶占了CPU，它就會一直占著CPU，不會給同優(yōu)先級的實時進程讓CPU的，而SCHED_RR進程會在運行了一定的時間片之后主動讓給同優(yōu)先級的實時進程。
分時調(diào)度類是給廣大的普通進程來用的，大家共同分享CPU。根據(jù)優(yōu)先級的不同，可能有的進程分的多有的進程分的少，但是不會出現(xiàn)一個進程霸占CPU的情況。分時調(diào)度類下面有三個調(diào)度策略：SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE。它們的基本思想都是分時，但是略有不同，SCHED_BATCH進程希望減少調(diào)度次數(shù)，每次調(diào)度能執(zhí)行的時間長一點，SCHED_IDLE是優(yōu)先級特別低的進程，其分到的CPU時間的比例非常低，但是也總是能保證分到。分時調(diào)度類現(xiàn)在的算法叫做CFS(完全公平調(diào)度)，所以分時調(diào)度類也叫做公平調(diào)度類。
閑時調(diào)度類是給內(nèi)核用的，當(dāng)CPU沒有其它進程可以執(zhí)行的時候就會運行閑時調(diào)度類的進程。此類進程是在內(nèi)核啟動時就創(chuàng)建好的，一個CPU一個進程，此后就不能再創(chuàng)建此類進程了。閑時調(diào)度類的進程也叫做idle進程，它在內(nèi)核中有些特殊的用途，比如CPUIdle的實現(xiàn)就和idle進程密切相關(guān)。
大家要注意，閑時調(diào)度類和分時調(diào)度類中SCHED_IDLE調(diào)度策略不是一回事，兩者沒有關(guān)系，大家不要弄混淆了。
系統(tǒng)為每個調(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);};
?
每個調(diào)度類在實現(xiàn)自己的算法的時候都要實現(xiàn)這些函數(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進行了一個優(yōu)化，因為大部分時間系統(tǒng)中主要存在的都是普通進程，所以先檢測運行隊列的運行數(shù)量和公平運行列隊中的運行數(shù)量，如果相等的話就說明系統(tǒng)中目前只有普通進程，那么就可以直接調(diào)用pick_next_task_fair。接著就是主邏輯了，先從高調(diào)度類進行選擇，如果有可運行的進程就直接返回，如果沒有就去查詢下一個調(diào)度類。最后一定能返回一個進程的，因為idle進程總是可運行的。
每個調(diào)度類的具體算法邏輯在后面的章節(jié)中講解。
2.6 進程優(yōu)先級
Linux上一共有5種調(diào)度類，其中禁令調(diào)度類和閑時調(diào)度類只在內(nèi)核里使用，而且一個CPU只有一個線程，所以用不到進程優(yōu)先級。限時調(diào)度類用的是進程設(shè)置的三個調(diào)度參數(shù)作為調(diào)度的依據(jù)，也用不到進程優(yōu)先級。所以就只有實時調(diào)度類和分時調(diào)度類會用到進程優(yōu)先級。它們使用優(yōu)先級的方法也并不相同，我們在講到具體算法時再講。
由于歷史原因，實時進程和普通進程的優(yōu)先級并不是一個簡單的數(shù)值，而是有好幾個數(shù)值體系和變換規(guī)則，我們先來看一下設(shè)置進程調(diào)度策略和優(yōu)先級的API。
?
#includeint 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è)置實時調(diào)度類和分時調(diào)度類的調(diào)度策略和靜態(tài)優(yōu)先級，對于實時調(diào)度類，其靜態(tài)優(yōu)先級范圍是1-99,99最大，對于分時調(diào)度類，其靜態(tài)優(yōu)先級必須設(shè)置為0，其動態(tài)優(yōu)先級也就是nice需要通過nice接口來設(shè)置。sched_setparam可以設(shè)置實時進程的靜態(tài)優(yōu)先級，對于分時進程，其靜態(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個字段，rt_priority用來記錄實時進程的用戶空間的靜態(tài)優(yōu)先級，static_prio用來記錄分時進程的用戶空間的動態(tài)優(yōu)先級并做了轉(zhuǎn)換。然后rt_priority和static_prio一起轉(zhuǎn)化為normal_prio(規(guī)范優(yōu)先級)，此時實時進程和分時進程的優(yōu)先級就在同一個數(shù)軸上了。最終起作用的是prio(動態(tài)優(yōu)先級)，它的值默認等于normal_prio，一般不會變動。
下面我們畫圖來看一下進程的優(yōu)先級轉(zhuǎn)換：
在用戶空間的時候，實時進程和普通進程(分時進程)共享同一個優(yōu)先級數(shù)軸，叫靜態(tài)優(yōu)先級，范圍是0-99，值越大優(yōu)先級越高，實時進程占用1-99，普通進程占用0。普通進程自己又新開了一個數(shù)軸，叫動態(tài)優(yōu)先級，也叫nice值，范圍是 -20 - 19，值越低優(yōu)先級越高。
到了內(nèi)核空間的時候，實時進程有一個實時優(yōu)先級，直接復(fù)制用戶空間的靜態(tài)優(yōu)先級，普通進程有一個靜態(tài)優(yōu)先級，它是用戶空間的nice值轉(zhuǎn)換過來的，轉(zhuǎn)換規(guī)則是nice+120。然后內(nèi)核又定義了規(guī)范優(yōu)先級，把它們都統(tǒng)一到同一個數(shù)軸上來。普通進程的規(guī)范優(yōu)先級是直接復(fù)制其靜態(tài)優(yōu)先級，實時進程的規(guī)范優(yōu)先級等于99減去它的實時優(yōu)先級。在規(guī)范優(yōu)先級的數(shù)軸上，所有進程都可以直接比較優(yōu)先級了，值越小優(yōu)先級越大。實時進程的規(guī)范優(yōu)先級范圍是0-99，但是由于它是從用戶空間的優(yōu)先級計算而來的，所以99這個值就用不到。
最后是動態(tài)優(yōu)先級，對進程所有的處理都以動態(tài)優(yōu)先級為準(zhǔn)，動態(tài)優(yōu)先級默認等于其規(guī)范優(yōu)先級。以前的時候調(diào)度算法會去調(diào)整進程的動態(tài)優(yōu)先級，現(xiàn)在不會再調(diào)了。現(xiàn)在只有使用了優(yōu)先級繼承鎖的時候才會去調(diào)整進程的動態(tài)優(yōu)先級。
下面讓我們再畫一個圖總結(jié)一下：
對于禁令調(diào)度類、限時調(diào)度類和閑時調(diào)度類，它們用不到進程優(yōu)先級，但是系統(tǒng)在規(guī)范優(yōu)先級數(shù)軸上為它們提供了象征值，其動態(tài)優(yōu)先級是對規(guī)范優(yōu)先級的復(fù)制，也只有象征意義。有一個特殊的情況是分時調(diào)度類里面的SCHED_IDLE調(diào)度策略的進程，它的優(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代表的實時進程的用戶空間優(yōu)先級，范圍：1 – 99，99最大，只有SCHED_FIFO和SCHED_RR有意義。
PRI，普通進程 pri = 19 - nice, 實時進程 pri = 40 + rtprio，值越大優(yōu)先級越大，普通進程 0 – 39， 實時進程 41 – 139。
top命令優(yōu)先級：
NI列是nice值，只對普通進程有效，對其它進程來說沒有意義。
PR，普通進程 pr = 20 + nice，實時進程 pr = -1 - rt，rt是實時進程的用戶空間優(yōu)先級，PR值越小優(yōu)先級越大，普通進程 0 – 39，實時進程 -2 – -100，-100會顯示為rt，普通進程大于等于0，實時進程小于0。
2.7 進程切換
選擇好下一個要執(zhí)行的進程之后，就該切換進程了。切換進程一共分兩步：一是切換用戶空間，二是切換內(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");}
?
切換進程地址空間就是給寄存器CR3賦予新的值。CR3中存放的是根頁表的物理地址，build_cr3會把虛擬地址轉(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)核中最難理解的地方之一，難以理解的有兩點：一是進程執(zhí)行是如何切換的；二是switch_to宏為何有三個參數(shù)，第三個參數(shù)為啥又是prev。
我們先來解釋第一個點，進程執(zhí)行是如何切換的，先來畫個圖看一下：
如圖中所示一樣，每個線程都有一個線程棧，代表線程的執(zhí)行，CPU只有一個(線程切換前后是同一個CPU)。CPU在哪個線程棧上運行，就是在運行在哪個線程，而線程棧上記錄的就是線程的運行信息，所以這個線程就可以繼續(xù)運行下去了。如果從單個進程的角度來看，從switch_to開始，我們的進程就暫停運行了，我們的進程就一直在這等，等到我們被喚醒并調(diào)度執(zhí)行才會繼續(xù)走下去。如果從CPU的角度來看，switch_to切換了內(nèi)核棧，就在新的線程上運行了，函數(shù)返回的時候就會按照內(nèi)核棧的調(diào)用地址返回，執(zhí)行的就是新的代碼了，就不是原來的代碼了。當(dāng)內(nèi)核棧不停地返回，就會返回到用戶空間，內(nèi)核棧的底部記錄的有用戶空間的調(diào)用信息，由于前面已經(jīng)切換了用戶空間，所以程序就能返回到之前用戶空間進入內(nèi)核的地方。
我們再來說第二點，switch_to宏為啥有三個參數(shù)，為啥這么難以理解呢？這是因為switch_to實際上包含了三個進程：一個是我們自己prev，一個是即將要切換的進程next，一個是我們下次是從哪個進程切換過來的，我們把這個進程叫做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);}
?
這下就好理解多了。從單個進程的角度來看，__switch_to_asm會切換到next進程去執(zhí)行，我們的進程就休眠了。很久以后我們的進程醒來又重新開始執(zhí)行了，__switch_to_asm返回的是把CPU讓給我們的那個進程。從CPU的角度來看__switch_to_asm函數(shù)前半程在curr進程運行，后半程在next進程運行。由于切換了內(nèi)核棧，所以from、curr、next這三個變量也變了，它們是不同棧上的同名的局部變量，它們的內(nèi)存地址是不一樣的。當(dāng)前進程中的curr值會被作為next進程中的from值返回，所以在next進程中就知道了是從哪里切換過來的了。
__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) */
?
每個進程的內(nèi)核棧的棧指針都在task_struct中的thread.sp保存著，第一個mov語句是把當(dāng)前進程的棧指針保存起來以備后面使用，第二個mov語句是加載next進程的棧指針，這條指令執(zhí)行之后就意味著進程切換成功了。后面還有一些語句用來加載之前保存在棧上的寄存器信息。
如果大家對前面修改的代碼感興趣，想打log驗證一下，可以參考下面我加的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);}
?
這里面有兩個技巧，一是使用jiffies % 1000 == 0來減少log的數(shù)量，內(nèi)核中進程切換非常頻繁，過多的log往往難以分析，二是使用1 == smp_processor_id()把log鎖定在一個CPU上，不然的話多個CPU上的切換log會相互干擾，難以理清，我們只看一個CPU上的log，就會發(fā)現(xiàn)邏輯很清晰。
下面我畫了一個圖模擬了一下單個CPU上的三個進程之間的切換，大家來看一下：
有三個進程pid 分別為1、3、5在CPU0上進行切換，切換順序是1->3->5->1->5->3->1。圖中是按照我修改之后的代碼來畫的，有from、curr、next三個指針變量。可以看到一個進程它必須先切走才能切回，因為不切走怎么能切回來呢。但是對于剛創(chuàng)建的進程它是沒有切走過的，于是內(nèi)核會為它偽造內(nèi)核棧也就是切點，使得它可以切回。正常的內(nèi)核棧是__schedule函數(shù)調(diào)用了__switch_to_asm函數(shù)，__switch_to_asm函數(shù)還會返回到__schedule函數(shù)。偽造的內(nèi)核棧是仿佛ret_from_fork調(diào)用了__switch_to_asm函數(shù)，__switch_to_asm函數(shù)在返回的時候就會返回到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時說明是普通進程，調(diào)用syscall_exit_to_user_mode，不為0時說明是內(nèi)核線程，調(diào)用rbx也就是kthread。kthread函數(shù)一般是不會返回的，但是如果其中調(diào)用了kernel_execve建立了用戶空間也可以返回，返回到ret_from_fork中后會調(diào)用syscall_exit_to_user_mode。
對于這幅圖大家可以只看一個進程的執(zhí)行情況，按照一個進程pid從上往下看就可以了。也可以看整個CPU的執(zhí)行情況，按照紅色箭頭的標(biāo)號順序來看，注意觀察from、curr、next三個值的變化。
? 三、SMP管理 ? ?
在繼續(xù)講解之前，我們先來說一下多CPU管理(這里的CPU是指邏輯CPU，在很多語境中CPU都是默認指的邏輯CPU，物理CPU要特別強調(diào)是物理CPU)。最開始的時候計算機都是單CPU的，叫做UP(Uni-Processor)，操作系統(tǒng)也只支持UP。后來計算機慢慢發(fā)展成了多CPU(包括多物理CPU和多核技術(shù))，于是操作系統(tǒng)也要開始支持多CPU。支持多CPU的方式有兩種：一種是AMP(Aymmetrical Multi-Processing)非對稱多處理器，是指操作系統(tǒng)給每個CPU分配的工作任務(wù)不同，比如有的CPU專門運行中斷，有的CPU專門運行普通進程，有的CPU專門運行實時進程；另一種是SMP(Symmetrical Multi-Processing)，操作系統(tǒng)對待每個CPU的方式都是一樣的，并不會把某個CPU拿來專門做啥任務(wù)，每個CPU都有可能處理任何類型的任務(wù)。由于AMP的性能和適應(yīng)性都不太好，所以現(xiàn)在流行的操作系統(tǒng)基本都是SMP的。對于SMP這個詞來說，在很長的一段時間內(nèi)，它既是指CPU在邏輯上是對稱的(操作系統(tǒng)對待所有CPU的方式是一樣的)，也指CPU在物理上是對稱的(CPU在性能等所有方面都是一樣的)，因為當(dāng)時的多CPU技術(shù)實現(xiàn)上每個邏輯CPU的性能等各方面都是相同的。但是后來多CPU技術(shù)的實現(xiàn)出現(xiàn)了HMP(Heterogeneous Multi-Processing)異構(gòu)多處理器，也就是大小核技術(shù)，不同的邏輯CPU它們的性能并不相同。現(xiàn)在內(nèi)核同時支持SMP和HMP，因為兩者并不矛盾，SMP指的是所有的CPU在邏輯上都是一樣的，每個CPU都有可能執(zhí)行任何類型的任務(wù)，HMP指的是不同的CPU它的能力大小不同，能力大的多干活，能力小的少干活。內(nèi)核選項CONFIG_SMP控制是否開啟SMP，如果不開啟的話就是UP，系統(tǒng)就只能在一個CPU上運行。內(nèi)核選項CONFIG_ENERGY_MODEL控制是否開啟HMP，開啟了之后就可以為不同的設(shè)備建立不同的能耗模型，系統(tǒng)在分配任務(wù)就會以此為參考決定如何分配任務(wù)，達到效率更高或者更省電的目的。
3.1 CPU拓撲結(jié)構(gòu)
我們先從發(fā)展的角度來看一看CPU的拓撲結(jié)構(gòu)。最早的時候一個物理CPU就是一個邏輯CPU，一個邏輯CPU包含一個控制器、一個運算器和一些寄存器，一個物理CPU包含一個裸芯片(Die)和外面的封裝(Package)。然后出現(xiàn)了多物理CPU，也就是一個主板上有多個CPU插槽，這樣計算機中就有多個CPU了。后來發(fā)現(xiàn)，沒必要做多個物理CPU啊，一個物理CPU(Package)包含多個裸芯片(Die)不也是多CPU嘛，省事又方便。后來又發(fā)現(xiàn)，多個裸芯片封裝在一起也很麻煩啊，直接在一個裸芯片上做多個邏輯CPU不是也可以嘛，更省事。從這之后x86和ARM的CPU做法就不一樣了。在x86上是一個裸芯片(Die)包含多個核(Core)，一個核(Core)上包含多個SMT(Simultaneous Multithreading)，SMT在Intel的文檔里叫做HT(Hyper-Threading)，SMT是最終的邏輯CPU。在ARM上是一個裸芯片(Die)包含多個核簇(Cluster)，一個核簇(Cluster)包含多個核(Core)。
3.2 CPUMASK
不同架構(gòu)的CPU，其邏輯CPU都有一個硬件ID，此ID一般是多個字段的組合。Linux為了方便管理CPU，提出了邏輯CPU的概念，此邏輯CPU的概念是指CPU的ID是邏輯的，從0來編號一直增長的。內(nèi)核會把第一個啟動的CPU作為CPU0，其它CPU的編號依次為CPU1，CPU2，……。內(nèi)核定義了結(jié)構(gòu)體cpumask來表示各個CPU編號的集合，cpumask是個bitmap，每一個bit可以代表一個CPU的某種狀態(tài)。內(nèi)核中定義了五個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代表的是計算機上存在的CPU，cpu_online_mask代表的是已經(jīng)上線的CPU，cpu_active_mask代表的是未被隔離可以參與調(diào)度的CPU，cpu_dying_mask代表的是處于熱下線過程中的CPU。
? 四、基本分時調(diào)度 ? ?
Linux上的分時調(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只負責(zé)調(diào)度普通進程，包括三個調(diào)度策略NORMAL、BATCH、IDLE。
我們這章只講單個CPU上的調(diào)度，多CPU之間的調(diào)度均衡在下一章講。
4.1 CFS調(diào)度模型
內(nèi)核文檔對CFS的定義是：CFS在真實的硬件上基本模擬了完全理想的多任務(wù)處理器。完全理想的多任務(wù)處理器是指，如果把CPU的執(zhí)行能力看成是100%，則N個進程可以同時并行執(zhí)行，每個進程獲得了1/N的CPU執(zhí)行能力。例如有2個進程在2GHz的CPU上執(zhí)行了20ms，則每個進程都以1GHz的速度執(zhí)行了20ms。
通過CFS的定義很難理解CFS的操作邏輯是什么。我看了很多CFS的博客，也認真看了很多遍CFS的代碼，雖然自己心里明白了其中的意思，但是想要給別人說清楚CFS的操作邏輯還是很難。后來我靈光乍現(xiàn)，突然想到了一個很好的類比場景，把這個場景稍微改造一下，就可以打造一個非常完美的CFS調(diào)度模型，可以讓任何人都能理解CFS的操作邏輯。大家有沒有這種生活體驗，夏天的時候三四個好友一起去擼串，吃完準(zhǔn)備走的時候發(fā)現(xiàn)有一瓶啤酒打開了還沒喝。此時我們會把這瓶啤酒平分了，具體怎么分呢，比如三個人分，你不可能一次分完，每個杯子正好倒三分之一。我們一般會每個杯子先倒個差不多，然后再把剩余的啤酒來回往各個杯子里面倒，這樣啤酒就會分的比較均勻了。也許你沒經(jīng)歷過這樣的場景，或者認為啤酒隨便分就可以了，沒必要分那么細。接下來還有一個場景更生動。你有沒有經(jīng)歷過或者見過長輩們喝白酒劃拳的，此時一般都會拿出5到10個小酒盅，先把每個酒盅都倒個差不多，然后再來回地往各個酒盅里面倒一點，還會去比較酒盅液面的高低，優(yōu)先往液面低的杯子里面倒。如果你見過或者經(jīng)歷過這種場景，那么接下來的模型就很好理解了。
我們對倒白酒的這個場景進行改造，把它變成一個實驗臺。首先把酒盅變成細長(而且非常長)的玻璃杯，再把倒白酒的瓶子變成水龍頭，能無限出水的水龍頭，有一個桌子可以用來擺放所有的玻璃杯。我們一次只能拿著一個玻璃杯放到水龍頭下接水。然后向你提出了第一個要求，在任意時刻所有的玻璃杯的水位高度都要相同或者盡量相同，越接近越好。此時你會怎么辦，肯定是不停地切換玻璃杯啊，越快越好，一個玻璃杯接一滴水就立馬換下一個。但是這立馬會迎來第二個問題，切換玻璃杯的過程水龍頭的水會流到地上，過于頻繁的切換玻璃杯會浪費大量的水。向你提出的第二個要求就是要盡量地少浪費水，你該怎么辦，那肯定是減少玻璃杯的切換啊。但是減少玻璃杯的切換又會使得不同玻璃杯的水位差變大，這真是一個兩難的選擇。對此我們只能進行折中，切換玻璃杯的頻率不能太大也不能太小，太大浪費水，太小容易水位不均。
我們繼續(xù)對這個模型進行完善。為了減少水位差我們每次都要去拿水位最低的，怎么能最快的時間拿到最低的玻璃杯呢，肯定是把水杯按照從高到底的順序排列好，我們直接去拿第一個就好了。玻璃杯代表的是進程，不同進程的優(yōu)先級不同，分到的CPU時間片也不同，為此我們讓不同的玻璃杯有不同的粗細，這樣比較粗的玻璃杯就能分到更多的水，因為我們在盡量保證它們的水位相同，橫截面積大的玻璃杯就會占優(yōu)勢。進程有就緒、阻塞、運行等狀態(tài)，為此我們在玻璃杯上面加個蓋子，蓋子有時候是打開的，有時候是關(guān)閉的。蓋子關(guān)閉的時候玻璃杯是沒法接水的，因此我們把它放到一邊，直到有人把它的蓋子打開我們再把它放到桌子上。
說到這里，大家在腦海里對這個模型應(yīng)該已經(jīng)有個大概的輪廓了，下面我們畫圖來看一下：
我們繼續(xù)講解這個圖。我們每次都是從隊首拿過來一個玻璃杯開始接水。在接水的過程中有兩種情況可能會發(fā)生：一是一直接水直到此次接水的份額已經(jīng)滿了，我們把這個玻璃杯再放回到隊列中去，由于此時玻璃杯剛接了不少水，水位比較高，所以會排的比較靠后；二是接水的過程中，瓶蓋突然關(guān)閉了，這時就沒法再接水了，我們把玻璃杯送到某個Wait Box中去，等待某個事件的發(fā)生。某個事件發(fā)生之后會把對應(yīng)的Wait Box中的一個或者多個玻璃杯的瓶蓋打開，然后此玻璃杯就會被送到Ready Table上。玻璃杯被送到Ready Table并不是隨便一放就行了，也是要參與排序的。大家從圖中可以看到，Wait Box中的玻璃杯的水位都比較低，這是因為Ready Table上的玻璃杯一直在接水，水位肯定會漲的很高，相應(yīng)的Wait Box中的水位就低了。因此WaitBox中的玻璃杯被喚醒放到ReadyTable上基本都能排第一，這也是好事，讓休眠時間長的進程能迅速得到執(zhí)行。但是這里面也存在一個問題，就是剛開蓋的玻璃杯水位太低了，它就能一直得到執(zhí)行，這對其它玻璃杯來說是不公平的。因此ReadyTable上放了一個最低水位記錄，剛開蓋的玻璃瓶如果水位比這個值低，我們就往這個玻璃瓶中填充泡沫，使得它的水位看起來和這個最低水位記錄一樣高。這樣新開蓋的玻璃杯既能優(yōu)先接水，又不能過分占便宜，非常好。最低水位記錄的值也會一直更新的，正在接水的玻璃杯每次離開的時候都會更新一下這個最低水位記錄。
現(xiàn)在我們對這個玻璃杯接水模型的邏輯已經(jīng)非常清楚了，下面我們一步一步把它和CFS的代碼對應(yīng)起來，你會發(fā)現(xiàn)契合度非常高。
4.2 CFS運行隊列
所有的就緒進程都要在ReadyTable上按照水位高低排成一排，那么這個隊列用什么數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)呢？先想一下這個隊列都有什么需求，首先這個隊列是排序的，其次我們經(jīng)常對這個隊列進程插入和刪除操作。因此我們可以想到用紅黑樹來實現(xiàn)，因為紅黑樹首先是一顆二叉搜索樹，是排序的，其次紅黑樹是平衡的，其插入和刪除操作的效率都是O(logn)，非常高效。所以CFS的運行隊列就是用紅黑樹來實現(xiàn)的。
下面我們來看一下CFS運行隊列的代碼：
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就是所有分時進程所排隊的隊列，類型rb_root_cached就是內(nèi)核中紅黑樹的實現(xiàn)，curr就是當(dāng)前正在CPU上運行的進程。還有一些其它字段我們在講到時再進行解說。進程在紅黑樹中排隊的鍵值是虛擬運行時間vruntime，這個在4.5節(jié)中講解。
4.3 進程狀態(tài)表示
我們知道進程在運行的時候一直是在阻塞、就緒、執(zhí)行三個狀態(tài)來回轉(zhuǎn)換，如下圖所示：
但是Linux中對進程運行狀態(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來表示，這讓人很疑惑。但是用我們的模型圖來看，這一點卻很好理解，因為就緒和執(zhí)行它們都是開蓋的，狀態(tài)一樣，區(qū)別它們的方法是玻璃杯有沒有放在水龍頭下接水，而Linux中也是利用這一點來判斷的。如下代碼所示：
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)字段，代表進程處于就緒或者執(zhí)行態(tài)，后者判斷的是進程是否處于執(zhí)行態(tài)。
表示進程處于阻塞態(tài)的狀態(tài)有兩個：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。TASK_UNINTERRUPTIBLE表示只有WaitBox對應(yīng)的事件能把玻璃杯的蓋子打開，其它人誰也打不開。TASK_INTERRUPTIBLE表示除了WaitBox對應(yīng)的事件之外，信號(signal)也能把蓋子打開。關(guān)于信號請參看《深入理解Linux信號機制》。
4.4 優(yōu)先級與權(quán)重
我們在前面講過進程的優(yōu)先級，這里只講分時進程的優(yōu)先級。優(yōu)先級是如何影響進程獲得CPU時間的多少呢？優(yōu)先級會轉(zhuǎn)化為進程的權(quán)重，進程的權(quán)重也就是玻璃杯的粗細。橫截面積大的玻璃杯，接收同樣容積的水，它的水位增加就比較小，就容易排到隊列的前面去，就比較容易獲得調(diào)度。在一段時間后，所有玻璃杯的水位高度都比較接近，同樣的水位高度，橫截面積大的玻璃杯裝的水就多，也就是進程獲得的CPU時間比較多。
進程(線程)的相關(guān)信息是記錄在task_struct中的，內(nèi)核又把和分時調(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中有兩個字段：weight和inv_weight。weight代表的是權(quán)重，inv_weight是為了方便weight參與除法運算時而添加的，它可以把對weight的除法運算轉(zhuǎn)化為對inv_weight的乘法運算。inv_weight = 232/weight，當(dāng)需要除以weight的時候，你只需要乘以inv_weight然后再右移32就可以了。inv_weight的值可以提前算出來保存在數(shù)組里，右移操作是個效率很高的操作，這樣就提高了權(quán)重相關(guā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ù)列的時間片，為何CFS要把這個轉(zhuǎn)換變?yōu)榈缺葦?shù)列呢？這是因為人們天然地對相對值比較敏感而不是對絕對值比較敏感，比如你工資兩千的時候漲薪200和工資兩萬的時候漲薪200，心情絕對是不一樣的。如果系統(tǒng)中只有兩個進程，nice值分別為0和1，時間片分別為200ms和195ms，幾乎沒啥區(qū)別，但是當(dāng)nice值分為18和19的時候，時間片分別為10ms和5ms，兩者的時間差達到了一倍，同樣是nice值相差1，它們的時間差的比例卻如此之大，是讓人無法接受的。因此把nice值轉(zhuǎn)化為等比數(shù)列的權(quán)重，再按照權(quán)重去分配CPU時間是比較合理的。那么公比為何是0.8呢？這是為了讓兩個nice值只相差1的進程獲得的CPU時間比例差為10%。我們用等式來計算一下，假設(shè)x、y是權(quán)重，y對應(yīng)的nice值比x大1，我們希望 x/(x+y) - y/(x+y) = 10%，我們做一下運算，看看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來進行轉(zhuǎn)換呢？這是為了二進制運算方便。內(nèi)核里并不是每次優(yōu)先級轉(zhuǎn)權(quán)重都進行運算，而是提前運算好了放在數(shù)組，每次用的時候查一下就可以了。反權(quán)重的值也提前計算好了放在了數(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個數(shù)，一排5個權(quán)重值，五八四十正好40個權(quán)重值。可以看到權(quán)重數(shù)列的公比并不是標(biāo)準(zhǔn)的0.8，而是作者以0.8為基準(zhǔn)從nice 0開始計算，之后又進行了一些調(diào)整，主要是為了方便計算。
下面我們再來看一下設(shè)置進程權(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)度策略的進程進行了特殊處理，直接設(shè)置其權(quán)重為3，相當(dāng)于是nice 26，反權(quán)重值也直接進行了設(shè)置。SCHED_IDLE進程的權(quán)重特別小意味其分到的CPU時間會相當(dāng)?shù)纳伲梅线@個調(diào)度策略的本意。scale_load和scale_load_down是對權(quán)重進行縮放，在32位系統(tǒng)上它們是空操作，在64位系統(tǒng)上它們是放大1024倍和縮小1024倍，主要是為了在運算時提高精度，不影響權(quán)重的邏輯。所以在后文中為了敘述方便，我們直接忽略scale_load和scale_load_down。接著往下看，update_load參數(shù)會影響代碼的流程，當(dāng)進程是新fork時update_load為false，會走下面的流程直接設(shè)置權(quán)重和反權(quán)重，當(dāng)用戶空間修改進程優(yōu)先級時update_load為true，會走上面的流程調(diào)用reweight_task，reweight_task也會設(shè)置進程的權(quán)重，同時也會修改運行隊列的權(quán)重。
運行隊列的權(quán)重等于其上所有進程的權(quán)重之和。進程在入隊出隊時也會相應(yīng)地從運行隊列中加上減去其自身的權(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--;}
?
可以看到運行隊列的總權(quán)重和其進程數(shù)量是同步更新的。
4.5 虛擬運行時間
我們再來看一下玻璃杯的水位是如果表示的。玻璃杯的水位就是進程的虛擬運行時間，是進程進行排隊的鍵值。玻璃杯的水位等于玻璃杯中水的體積除以玻璃杯的橫截面積，進程的虛擬運行時間等于進程的實際運行時間除以相對權(quán)重。進程的實際運行時間是一段一段的，所以進程的虛擬運行時間也是一段一段增長的。進程的虛擬運行時間還會在進程入隊時與運行隊列的最小虛擬時間相比較，如果小的話會直接進行增加，并不對應(yīng)實際的運行時間。這也就是我們前面說的對玻璃杯進行填充泡沫的操作。相對權(quán)重是相對于nice 0的權(quán)重，所以nice 0的進程其虛擬運行時間和實際運行時間是一致的。但是這種一致只是某一段時間中的一致，因為虛擬運行時間在進程入隊時可能會空跳。在更新進程的真實虛擬運行時間的時候也會去更新運行隊列的最小運行時間記錄，使得運行隊列的最小運行時間也在一直增長著。
進程的虛擬運行時間保存在task_struct中的sched_entity中的vruntime字段。運行隊列的最小虛擬運行時間保證在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只能更新運行隊列的當(dāng)前進程，如果進程不在運行，沒有實際運行時間就沒有對應(yīng)的虛擬運行時間。函數(shù)首先獲取了當(dāng)前時間now，然后用當(dāng)前時間減去進程此次開始執(zhí)行的時間exec_start，就得到了進程此次運行的實際時間delta_exec。進程的exec_start是在進程即將獲取CPU的時候設(shè)置的，具體來說是調(diào)度流程中的pick_next_task設(shè)置的。然后再通過函數(shù)calc_delta_fair把實際運行時間轉(zhuǎn)化為虛擬運行時間，把得到的結(jié)果加到進程的vruntime上。calc_delta_fair中對nice 0的進程直接返回實際運行時間，對于其它進程則調(diào)用__calc_delta進行運算。__calc_delta使用了一些復(fù)雜的數(shù)學(xué)運算技巧，比較難以理解，但是其邏輯是清晰的，就是虛擬運行時間等于實際運行時間乘以NICE_0_LOAD與進程權(quán)重的比值(delta_exec * weight / lw.weight)。接著就是更新運行隊列的最小虛擬時間記錄了，再往下是一些統(tǒng)計代碼就不講了。我們來看一下最小虛擬時間的更新。
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)前進程的vruntime和隊首進程的vruntime之間選擇一個最小值，如果此值大于原先的min_vruntime，就更新cfs_rq->min_vruntime為此值。
update_curr的調(diào)用時機都有哪些？下面我們來一一說明一下：
定時器中斷，更新當(dāng)前進程的虛擬運行時間，只有更新了之后才知道當(dāng)前進程的時間片有沒有用完。
2.喚醒搶占時，也要更新當(dāng)前進程的虛擬運行時間，只有更新了之后才能正確判斷是否能搶占。
3.進程被搶占離開CPU時，從觸發(fā)搶占到執(zhí)行搶占還有一段時間，需要更新一下虛擬運行時間。
4.進程阻塞離開CPU時，需要更新一下虛擬運行時間。
5.主動讓出CPU時，通過sched_yield讓出CPU時更新一下虛擬運行時間。
6.當(dāng)前進程更改優(yōu)先級時，更改優(yōu)先級會改變權(quán)重，對已經(jīng)運行的時間先更新一下虛擬運行時間。
7.執(zhí)行fork時，子進程會繼承父進程的vruntime，因此要更新一下父進程的vruntime。
8.用戶空間定時器要統(tǒng)計進程的運行時間時。
9.調(diào)度均衡中遷移線程時入隊和出隊的隊列都要調(diào)用update_curr，目的是為了更新min_vruntime，因為被遷移的線程要減去舊隊列的min_vruntime，加上新隊列的min_vruntime，所以min_vruntime的要是最新的才好。
4.6 調(diào)度周期與粒度
在以往的調(diào)度算法中，都會有明確的調(diào)度周期和時間片的概念。比如說以1秒為一個調(diào)度周期，把1秒按照進程的優(yōu)先級分成時間片分給各個進程。進程在運行的過程中時間片不斷地減少，當(dāng)減到0的時候就不再參與調(diào)度了。當(dāng)所有進程的時間片都減到0的時候，再重新開啟一個調(diào)度周期，重新分配時間片。對于在一個調(diào)度周期內(nèi)突然創(chuàng)建或者喚醒的進程，還要進行特殊的處理。在CFS中，你會發(fā)現(xiàn)好像沒有調(diào)度周期和時間片的概念了，但是又好像有。沒有，是因為沒有統(tǒng)一分配時間片的地方了，也沒有時間片遞減的邏輯了。有，是因為代碼中還有調(diào)度周期和時間片的函數(shù)和變量。
在CFS調(diào)度模型中玻璃杯的水位是一直在增長的，沒有時間片遞減的邏輯，也不存在什么調(diào)度周期。但是一個玻璃杯總是不能一直接水的，接水時間長了也是要把切走的。在CFS中玻璃杯一次接水的最大量就叫做時間片。這個時間片和傳統(tǒng)的時間片是不一樣的，這個時間片是個檢測量，沒有遞減的邏輯。那么時間片是怎么計算的呢？這就和調(diào)度周期有關(guān)，CFS的調(diào)度周期也和傳統(tǒng)的調(diào)度周期不一樣，CFS的調(diào)度周期僅僅是一個計算量。調(diào)度周期的計算又和調(diào)度粒度有關(guān)。調(diào)度粒度是指玻璃杯一次接水的最小量，也就是進程在CPU上至少要運行多少時間才能被搶占。調(diào)度粒度指的是被動調(diào)度中進程一次運行最少的時間，如果進程阻塞發(fā)生主動調(diào)度，不受這個限制。時間片的計算依賴調(diào)度周期，調(diào)度周期的計算依賴調(diào)度粒度，所以我們就先來講講調(diào)度粒度。
內(nèi)核中定義了sysctl_sched_min_granularity，代表調(diào)度粒度，默認值是0.75毫秒，但這并不最終使用的值，系統(tǒng)在啟動的時候還會對這個變量進行賦值。我們來看一下代碼。
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ī)范值乘以一個因子。這個因子的值有三種可能：一是固定等于1，二是等于CPU的個數(shù)，三是等于1加上CPU個數(shù)對2的對數(shù)。具體使用哪種情況由變量sysctl_sched_tunable_scaling的值決定，此變量的值可以通過文件/sys/kernel/debug/sched/tunable_scaling來改變，默認值是SCHED_TUNABLESCALING_LOG。我們以8核CPU為例(下文也是如此)，factor的值就是4，因此默認的調(diào)度粒度就是0.75 * 4 = 3毫秒。也就是說在一個8核系統(tǒng)默認配置下，調(diào)度粒度是3毫秒，一個進程如果運行還不到3毫秒是不能被搶占的。
此代碼中還提到了喚醒粒度，我們也順便講一下。喚醒粒度是指被喚醒的進程如果其虛擬運行時間比當(dāng)前進程的虛擬運行時間少的值不大于這個值的虛擬化時間就不進行搶占。喚醒粒度指的不是是否喚醒這個進程，而是喚醒這個進程之后是否進行搶占。只有當(dāng)被喚醒的進程的虛擬運行時間比當(dāng)前進程的少的足夠多時才會進行搶占。當(dāng)然這個也要同時滿足調(diào)度粒度才會進行搶占。喚醒粒度的規(guī)范值是1毫秒，乘以4就是4毫秒。
此代碼中還有調(diào)度延遲，它和調(diào)度周期有關(guān)，我們先來計算一下調(diào)度延遲的值。調(diào)度延遲的規(guī)范值是6毫秒，乘以4就是24毫秒。
調(diào)度周期的計算與調(diào)度粒度和調(diào)度延遲都有關(guān)系，所以我們現(xiàn)在才能開始計算調(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毫秒是個固定值(在默認情況都不變的情況下)，當(dāng)運行隊列上的進程個數(shù)小于等于8的時候，每個進程至少能分到3毫秒，符合調(diào)度粒度是3毫秒的設(shè)定。所以當(dāng)running進程的個數(shù)小于等于8時，調(diào)度周期就等于調(diào)度延遲，每個進程至少能平分到3毫秒時間。當(dāng)其個數(shù)大于8時，調(diào)度周期就等于運行進程的個數(shù)乘以調(diào)度粒度。在一個調(diào)度周期內(nèi)如果是所有進程平分的話，一個進程能分到3毫秒。但是由于有的進程權(quán)重高，分到的時間就會大于3毫秒，就會有進程分到的時間少于3毫秒。實際上是這樣的嗎？我們來看一下計算時間片的代碼。
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)度，實際上只執(zhí)行了一遍。slice的值等于調(diào)度周期乘以進程權(quán)重與運行隊列權(quán)重的比值。如果進程的權(quán)重低于平均權(quán)重的話，那么其實將會小于調(diào)度粒度。再往下有個判斷，由于BASE_SLICE的值默認是true，所以此語句會執(zhí)行，slice至少等于調(diào)度粒度。由此可以得出結(jié)論，在默認情況下，進程分到的時間片不會小于調(diào)度粒度。那么此時實際的調(diào)度周期就會延長了。不過很大概率不會延長的，因為一般都會有進程因為阻塞而進行主動調(diào)度從而讓出來一部分時間。
我們再來總結(jié)一下調(diào)度周期、調(diào)度延遲、調(diào)度粒度、時間片的概念意義和它們在CFS中的變量意義以及相互之間的關(guān)系。調(diào)度周期的概念是指運行隊列上所有的進程都運行一遍的時間，但是在CFS中沒有了標(biāo)準(zhǔn)的調(diào)度周期，調(diào)度周期是動態(tài)的，只是個計算量。調(diào)度延遲的概念是指一個進程從加入到運行隊列到被放到CPU上去執(zhí)行之間的時間差，顯然這個時間差受進程本身和運行隊列長短的影響。在CFS中，調(diào)度延遲的概念完全變了，調(diào)度延遲變成了調(diào)度周期的最小值。時間片的概念是指一個進程一次最多只能運行多長時間，然后就要被搶占了。在CFS中時間片的概念沒有變，但是用法和傳統(tǒng)的用法不一樣。調(diào)度粒度是指一個進程一次至少運行多少時間才能被搶占，這個才CFS中也是如此。在CFS中，它們的計算關(guān)系是，調(diào)度周期等于調(diào)度粒度乘以Runnable進程的數(shù)量，但是不能小于調(diào)度延遲，時間片等調(diào)度周期乘以進程權(quán)重與運行隊列權(quán)重的比值。
4.7 搶占調(diào)度
搶占調(diào)度有兩個典型的觸發(fā)點：定時器中斷和進程喚醒。我們先來說定時器中斷，定時器中斷的主要目的就是為了進行搶占調(diào)度，防止有的進程一直占著CPU不放手。以前的算法會在定時器中斷中檢查進程的時間片是否已耗盡，如果耗盡的話就觸發(fā)調(diào)度，不過在CFS中的具體做法與此有所不同。在CFS中不會規(guī)定固定的調(diào)度周期，調(diào)度周期都是即時計算出來的，不會給進程分配時間片進行遞減，而是在定時器中斷中統(tǒng)計進程此時占據(jù)CPU已經(jīng)運行了多少時間，拿這個時間去給理論上它應(yīng)當(dāng)運行的時間比，如果超過了就觸發(fā)調(diào)度。進程的理論運行時間就等于其權(quán)重與隊列權(quán)重之比再乘以調(diào)度周期，調(diào)度周期的計算方法在上一節(jié)中講過了。因此CFS中的調(diào)度周期和時間片與傳統(tǒng)調(diào)度算法中的概念不同，它是一個動態(tài)的概念，只有當(dāng)發(fā)生定時器中斷了才會去計算一下，會根據(jù)當(dāng)時的狀態(tài)進行計算。比如當(dāng)前進程在函數(shù)A中喚醒了很多進程，那么定時器中斷是發(fā)生在函數(shù)A之前還是之后，調(diào)度周期和時間片的計算結(jié)果會有很大的不同。
下面我們來看一下定時器中斷中的搶占邏輯：
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));}
?
定時器中斷中會調(diào)用scheduler_tick，scheduler_tick會調(diào)用當(dāng)前進程的調(diào)度類的task_tick函數(shù)指針，對于普通進程來說就是task_tick_fair函數(shù)。task_tick_fair會調(diào)用entity_tick，我們這里不考慮組調(diào)度，因此for循環(huán)只會執(zhí)行一遍。在entity_tick中會先調(diào)用update_curr更新進程的運行時間，然后在當(dāng)運行進程總數(shù)大于1的時候調(diào)用check_preempt_tick。check_preempt_tick就是定時器搶占的核心了。
在check_preempt_tick中會先計算出來進程的理論運行時間ideal_runtime和實際運行時間delta_exec。如果實際運行時間大于理論運行時間，就會調(diào)用resched_curr來觸發(fā)搶占。如果不大于的話還會繼續(xù)處理。先判斷實際運行時間是否小于調(diào)度粒度，如果小于就返回。如果不小于就繼續(xù)。此時會計算當(dāng)前進程的虛擬運行時間與隊首進程的虛擬運行時間的差值，如果差值大于前面計算出來的理論運行時間就會調(diào)用resched_curr來觸發(fā)搶占。按照定時器中斷的目的的話，后面這個操作是沒有必要的，但是按照我們在CFS調(diào)度模型中的要求，盡量使所有玻璃杯在任意時刻的水位都盡量相同，這個操作是很有必要的，它能提高公平性。
下面我們來看一下喚醒搶占，喚醒分為新建喚醒和阻塞喚醒，最后都會調(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中，同類進程會使用調(diào)度類的check_preempt_curr函數(shù)進行處理，不同類的進程，高類會搶占低類的進程。分時調(diào)度類中的相應(yīng)函數(shù)是check_preempt_wakeup。此函數(shù)會先區(qū)分不同的調(diào)度策略，SCHED_IDLE策略的進程一定會被非SCHED_IDLE的進程搶占，非SCHED_NORMAL的進程一定不會搶占非SCHED_IDLE的進程。接下來會調(diào)用update_curr更新一下當(dāng)前進程的時間統(tǒng)計，然后調(diào)用wakeup_preempt_entity來查看一下是否滿足喚醒粒度，如果滿足就觸發(fā)調(diào)度。滿足喚醒粒度的標(biāo)準(zhǔn)是當(dāng)前進程的虛擬運行時間與被喚醒進程的虛擬運行時間的差值要大于喚醒粒度對應(yīng)的虛擬時間。
4.8 入隊與出隊
CFS中排隊的進程都是放在紅黑樹中，我們經(jīng)常要對其進行出隊入隊查詢隊首的操作。
下面我們先來看一下內(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)常會對隊首進程進行操作，因此rb_root_cached中用rb_leftmost對紅黑樹的最下角的節(jié)點(這個節(jié)點就是vruntime最小的節(jié)點，就是隊首進程)進行了緩存，方便查找。
我們經(jīng)常會對運行隊列進行入隊出隊操作，入隊出隊操作可以分為兩類。一類是和調(diào)度執(zhí)行相關(guān)的入隊出隊，叫做pick_next_task和put_prev_task，pick_next_task是選擇一個進程把它放到CPU上去運行，put_prev_task是把正在CPU上運行的進程放回到運行隊列中去。另一類是和非執(zhí)行相關(guān)的入隊出隊，叫做enqueue_task和dequeue_task，enqueue_task是把一個非正在CPU上執(zhí)行的進程放入到隊列中去，dequeue_task是把一個進程從隊列中拿出來，但不是拿來去CPU上運行的。
pick_next_task和put_prev_task都是在調(diào)度流程中的選擇進程過程中調(diào)用的。
下面我們看一下代碼(進行了高度刪減)：
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)度的時候會調(diào)用到pick_next_task_fair，此函數(shù)會先put_prev_task再pick_next_entity。put_prev_task最終會使用rb_add_cached把被搶占的進程放回到隊列中去，對于阻塞調(diào)度的則不會。pick_next_entity最終會使用rb_first_cached來獲取隊首進程用來調(diào)度。
enqueue_task和dequeue_task這兩個函數(shù)會在修改進程優(yōu)先級、設(shè)置進程親和性、遷移進程等操作中成對使用。enqueue_task在進程喚醒中也會使用，下面我們來看一下代碼。
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把進程放入到運行隊列中去的。
4.9 CFS算法評價
現(xiàn)在我們對CFS調(diào)度算法的各個方面都有了基本的了解，讓我們再看一下CFS調(diào)度模型圖來回憶一下：
回憶完之后，我們對CFS算法進行一下分析和評價。首先CFS取消了對IO密集型和CPU密集型進程的探測，避免了由于誤探而產(chǎn)生的問題。雖然沒有對IO密集型和CPU密集型進程進行探測區(qū)分，但是CFS還是能很好地處理這兩類進程。CPU密集型進程總是進程處于Runnable狀態(tài)，所以能經(jīng)常運行。由于其經(jīng)常會運行，水位會比較高，所以就排到后面，就給其它進程留下了機會。IO密集型進程由于經(jīng)常處于阻塞狀態(tài)，所以其水位就會比較低，在其喚醒之后進入隊列的時候經(jīng)常能排在隊首且很可能會搶占當(dāng)前進程，所以IO密集型的進程響應(yīng)性會比較高。
我們再來看公平性，CFS的名字就叫做完全公平調(diào)度，所以肯定是很公平的。公平性主要體現(xiàn)在以下幾個方面。一是取消了對IO密集型和CPU密集型進程的探測，不會對IO密集型進程進行特殊的照顧，所以進程都一視同仁。二是優(yōu)先級轉(zhuǎn)權(quán)重的時候采用了等比數(shù)列，使得nice值相差1的進程獲得的CPU時間比例總是相差10%，很公平。三是低優(yōu)先級的進程隨著別人的水位增長總是會排到前面的，一定會在可觀的時間內(nèi)得到執(zhí)行，不會產(chǎn)生饑餓。
再來看適應(yīng)性，由于采用了紅黑樹，CFS的出隊入隊查找操作都是O(logn)的，當(dāng)進程變得很多時，調(diào)度效率也依然良好。與調(diào)度效率是O(n)的算法相比，適應(yīng)性明顯很強，和O(1)的算法相比，也不算太差。
吞吐量和很多因素有關(guān)，代碼簡潔，調(diào)度效率是O(logn)也會提高其吞吐量。
節(jié)能性的話，CFS本身并沒有考慮這個問題。現(xiàn)在內(nèi)核已經(jīng)合入了EAS的代碼，EAS是對CFS的擴展，主要是來解決調(diào)度器的節(jié)能問題的。
? 五、總結(jié)回顧 ? ?
我們在此文中講了非常多關(guān)于進程調(diào)度的知識點，下面我們來總結(jié)一下。
對著這個圖讓我們來回顧一下，什么是調(diào)度，為什么要調(diào)度，為什么能調(diào)度。然后是調(diào)度時機，包括主動調(diào)度和被動調(diào)度。再之后是如何調(diào)度，包括選擇進程和切換進程。切換進程的邏輯是通用的，而選擇進程要分為5個調(diào)度類來進行選擇。講完了在單個CPU上的調(diào)度之后，我們還要在多CPU上進行調(diào)度均衡。
進程調(diào)度是操作系統(tǒng)中非常龐大非常難懂但又非常重要的部分，我們要經(jīng)常理論結(jié)合代碼結(jié)合實踐、反復(fù)思考琢磨才能更好的理解和掌握它。
工商網(wǎng)監(jiān)
評論