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