CFS調度器（1）-基本原理_ZenDei技術網路在線

首先需要思考的問題是：什麼是調度器（scheduler）？調度器的作用是什麼？調度器是一個操作系統的核心部分。可以比作是CPU時間的管理員。調度器主要負責選擇某些就緒的進程來執行。不同的調度器根據不同的方法挑選出最適合運行的進程。目前Linux支持的調度器就有RT scheduler、Deadlin ...

首先需要思考的問題是：什麼是調度器（scheduler）？調度器的作用是什麼？調度器是一個操作系統的核心部分。可以比作是CPU時間的管理員。調度器主要負責選擇某些就緒的進程來執行。不同的調度器根據不同的方法挑選出最適合運行的進程。目前Linux支持的調度器就有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。我想用一系列文章呈現Linux 調度器的設計原理。

註：文章代碼分析基於Linux-4.18.0。

什麼是調度類

從Linux 2.6.23開始，Linux引入scheduling class的概念，目的是將調度器模塊化。這樣提高了擴展性，添加一個新的調度器也變得簡單起來。一個系統中還可以共存多個調度器。在Linux中，將調度器公共的部分抽象，使用struct sched_class結構體描述一個具體的調度類。系統核心調度代碼會通過struct sched_class結構體的成員調用具體調度類的核心演算法。先簡單的介紹下struct sched_class部分成員作用。

struct sched_class {
    const struct sched_class *next;
    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 (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
    struct task_struct * (*pick_next_task)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
    /* ... */
};

next：next成員指向下一個調度類（比自己低一個優先順序）。在Linux中，每一個調度類都是有明確的優先順序關係，高優先順序調度類管理的進程會優先獲得cpu使用權。

enqueue_task：向該調度器管理的runqueue中添加一個進程。我們把這個操作稱為入隊。

dequeue_task：向該調度器管理的runqueue中刪除一個進程。我們把這個操作稱為出隊。

check_preempt_curr：當一個進程被喚醒或者創建的時候，需要檢查當前進程是否可以搶占當前cpu上正在運行的進程，如果可以搶占需要標記TIF_NEED_RESCHED flag。

pick_next_task：從runqueue中選擇一個最適合運行的task。這也算是調度器比較核心的一個操作。例如，我們依據什麼挑選最適合運行的進程呢？這就是每一個調度器需要關註的問題。

Linux中有哪些調度類

Linux中主要包含dl_sched_class、rt_sched_class、fair_sched_class及idle_sched_class等調度類。每一個進程都對應一種調度策略，每一種調度策略又對應一種調度類（每一個調度類可以對應多種調度策略）。例如實時調度器以優先順序為導向選擇優先順序最高的進程運行。每一個進程在創建之後，總是要選擇一種調度策略。針對不同的調度策略，選擇的調度器也是不一樣的。不同的調度策略對應的調度類如下表。

調度類	描述	調度策略
dl_sched_class	deadline調度器	SCHED_DEADLINE
rt_sched_class	實時調度器	SCHED_FIFO、SCHED_RR
fair_sched_class	完全公平調度器	SCHED_NORMAL、SCHED_BATCH
idle_sched_class	idle task	SCHED_IDLE

針對以上調度類，系統中有明確的優先順序概念。每一個調度類利用next成員構建單項鏈表。優先順序從高到低示意圖如下：

sched_class_highest----->stop_sched_class
                         .next---------->dl_sched_class
                                         .next---------->rt_sched_class
                                                         .next--------->fair_sched_class
                                                                        .next----------->idle_sched_class
                                                                                         .next = NULL

Linux調度核心在選擇下一個合適的task運行的時候，會按照優先順序的順序便利調度類的pick_next_task函數。因此，SCHED_FIFO調度策略的實時進程永遠比SCHED_NORMAL調度策略的普通進程優先運行。代碼中pick_next_task函數也有體現。pick_next_task函數就是負責選擇一個即將運行的進程，以下貼出省略版代碼。

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;
 
    for_each_class(class) {          /* 按照優先順序順序便利所有的調度類，通過next指針便利單鏈表 */
        p = class->pick_next_task(rq, prev, rf);
        if (p)
            return p;
    }
}

針對CFS調度器，管理的進程都屬於SCHED_NORMAL或者SCHED_BATCH策略。後面的部分主要針對CFS調度器講解。

普通進程的優先順序

CFS是Completely Fair Scheduler簡稱，即完全公平調度器。CFS的設計理念是在真實硬體上實現理想的、精確的多任務CPU。CFS調度器和以往的調度器不同之處在於沒有時間片的概念，而是分配cpu使用時間的比例。例如：2個相同優先順序的進程在一個cpu上運行，那麼每個進程都將會分配50%的cpu運行時間。這就是要實現的公平。

以上舉例是基於同等優先順序的情況下。但是現實卻並非如此，有些任務優先順序就是比較高。那麼CFS調度器的優先順序是如何實現的呢？首先，我們引入權重的概念，權重代表著進程的優先順序。各個進程之間按照權重的比例分配cpu時間。例如：2個進程A和B。A的權重是1024，B的權重是2048。那麼A獲得cpu的時間比例是1024/(1024+2048) = 33.3%。B進程獲得的cpu時間比例是2048/(1024+2048)=66.7%。我們可以看出，權重越大分配的時間比例越大，相當於優先順序越高。在引入權重之後，分配給進程的時間計算公式如下：

分配給進程的時間 = 總的cpu時間 * 進程的權重/就緒隊列（runqueue）所有進程權重之和

CFS調度器針對優先順序又提出了nice值的概念，其實和權重是一一對應的關係。nice值就是一個具體的數字，取值範圍是[-20, 19]。數值越小代表優先順序越大，同時也意味著權重值越大，nice值和權重之間可以互相轉換。內核提供了一個表格轉換nice值和權重。

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

數組的值可以看作是公式：weight = 1024 / 1.25^nice計算得到。公式中的1.25取值依據是：進程每降低一個nice值，將多獲得10% cpu的時間。公式中以1024權重為基準值計算得來，1024權重對應nice值為0，其權重被稱為NICE_0_LOAD。預設情況下，大部分進程的權重基本都是NICE_0_LOAD。

調度延遲

什麼是調度延遲？調度延遲就是保證每一個可運行進程都至少運行一次的時間間隔。例如，每個進程都運行10ms，系統中總共有2個進程，那麼調度延遲就是20ms。如果有5個進程，那麼調度延遲就是50ms。如果現在保證調度延遲不變，固定是6ms，那麼系統中如果有2個進程，那麼每個進程運行3ms。如果有6個進程，那麼每個進程運行1ms。如果有100個進程，那麼每個進程分配到的時間就是0.06ms。隨著進程的增加，每個進程分配的時間在減少，進程調度過於頻繁，上下文切換時間開銷就會變大。因此，CFS調度器的調度延遲時間的設定並不是固定的。當系統處於就緒態的進程少於一個定值（預設值8）的時候，調度延遲也是固定一個值不變（預設值6ms）。當系統就緒態進程個數超過這個值時，我們保證每個進程至少運行一定的時間才讓出cpu。這個“至少一定的時間”被稱為最小粒度時間。在CFS預設設置中，最小粒度時間是0.75ms。用變數sysctl_sched_min_granularity記錄。因此，調度周期是一個動態變化的值。調度周期計算函數是__sched_period()。

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

nr_running是系統中就緒進程數量，當超過sched_nr_latency時，我們無法保證調度延遲，因此轉為保證調度最小粒度。如果nr_running並沒有超過sched_nr_latency，那麼調度周期就等於調度延遲sysctl_sched_latency（6ms）。

虛擬時間（virtual time）

CFS調度器的目標是保證每一個進程的完全公平調度。CFS調度器就像是一個母親，她有很多個孩子（進程）。但是，手上只有一個玩具（cpu）需要公平的分配給孩子玩。假設有2個孩子，那麼一個玩具怎麼才可以公平讓2個孩子玩呢？簡單點的思路就是第一個孩子玩10分鐘，然後第二個孩子玩10分鐘，以此迴圈下去。CFS調度器也是這樣記錄每一個進程的執行時間，保證每個進程獲取CPU執行時間的公平。因此，哪個進程運行的時間最少，應該讓哪個進程運行。

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight

進程A的虛擬時間3.3 * 1024 / 1024 = 3.3ms，我們可以看出nice值為0的進程的虛擬時間和實際時間是相等的。進程B的虛擬時間是2.7 * 1024 / 820 = 3.3ms。我們可以看出儘管A和B進程的權重值不一樣，但是計算得到的虛擬時間是一樣的。因此CFS主要保證每一個進程獲得執行的虛擬時間一致即可。在選擇下一個即將運行的進程的時候，只需要找到虛擬時間最小的進程即可。為了避免浮點數運算，因此我們採用先放大再縮小的方法以保證計算精度。內核又對公式做瞭如下轉換。

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight
  
                                   NICE_0_LOAD * 2^32
                = (wall_time * -------------------------) >> 32
                                        weight
                                                                                        2^32
                = (wall_time * NICE_0_LOAD * inv_weight) >> 32        (inv_weight = ------------ )
                                                                                        weight

權重的值已經計算保存到sched_prio_to_weight數組中，根據這個數組我們可以很容易計算inv_weight的值。內核中使用sched_prio_to_wmult數組保存inv_weight的值。計算公式是：sched_prio_to_wmult[i] = 232/sched_prio_to_weight[i]。

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

系統中使用struct load_weight結構體描述進程的權重信息。weight代表進程的權重，inv_weight等於232/weight。

struct load_weight {
    unsigned long       weight;
    u32         inv_weight;
};

將實際時間轉換成虛擬時間的實現函數是calc_delta_fair()。calc_delta_fair()調用__calc_delta()函數，__calc_delta()主要功能是實現如下公式的計算。

__calc_delta() = (delta_exec * weight * lw->inv_weight) >> 32
 
                                  weight                                 2^32
               = delta_exec * ----------------    (lw->inv_weight = --------------- )
                                lw->weight                             lw->weight

和上面計算虛擬時間計算公式對比發現。如果需要計算進程的虛擬時間，這裡的weight只需要傳遞參數NICE_0_LOAD，lw參數是進程對應的struct load_weight結構體。

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = 32;
 
    __update_inv_weight(lw);
 
    if (unlikely(fact >> 32)) {
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }
 
    fact = (u64)(u32)fact * lw->inv_weight;
 
    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }
 
    return mul_u64_u32_shr(delta_exec, fact, shift);
}

按照上面說的理論，calc_delta_fair()函數調用__calc_delta()的時候傳遞的weight參數是NICE_0_LOAD，lw參數是進程對應的struct load_weight結構體。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))             /* 1 */
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);  /* 2 */
 
    return delta;
}

按照之前的理論，nice值為0（權重是NICE_0_LOAD）的進程的虛擬時間和實際時間是相等的。因此如果進程的權重是NICE_0_LOAD，進程對應的虛擬時間就不用計算。

調用__calc_delta()函數。

Linux通過struct task_struct結構體描述每一個進程。但是調度類管理和調度的單位是調度實體，並不是task_struct。在支持組調度的時候，一個組也會抽象成一個調度實體，它並不是一個task。所以，我們在struct task_struct結構體中可以找到以下不同調度類的調度實體。

struct task_struct {
         struct sched_entity        se;
    struct sched_rt_entity      rt;
    struct sched_dl_entity      dl;
    /* ... */
}

se、rt、dl分別對應CFS調度器、RT調度器、Deadline調度器的調度實體。

struct sched_entity結構體描述調度實體，包括struct load_weight用來記錄權重信息。除此以外我們一直關心的時間信息，肯定也要一起記錄。struct sched_entity結構體簡化後如下：

struct sched_entity {
    struct load_weight      load;
    struct rb_node      run_node;
    unsigned int        on_rq;
    u64         sum_exec_runtime;
    u64         vruntime;
};

load：權重信息，在計算虛擬時間的時候會用到inv_weight成員。

run_node：CFS調度器的每個就緒隊列維護了一顆紅黑樹，上面掛滿了就緒等待執行的task，run_node就是掛載點。

on_rq：調度實體se加入就緒隊列後，on_rq置1。從就緒隊列刪除後，on_rq置0。

sum_exec_runtime：調度實體已經運行實際時間總合。

vruntime：調度實體已經運行的虛擬時間總合。

就緒隊列（runqueue）

系統中每個CPU都會有一個全局的就緒隊列（cpu runqueue），使用struct rq結構體描述，它是per-cpu類型，即每個cpu上都會有一個struct rq結構體。每一個調度類也有屬於自己管理的就緒隊列。例如，struct cfs_rq是CFS調度類的就緒隊列，管理就緒態的struct sched_entity調度實體，後續通過pick_next_task介面從就緒隊列中選擇最適合運行的調度實體（虛擬時間最小的調度實體）。struct rt_rq是實時調度器就緒隊列。struct dl_rq是Deadline調度器就緒隊列。

struct rq {
         struct cfs_rq cfs;
    struct rt_rq rt;
    struct dl_rq dl;
};
 
struct rb_root_cached {
    struct rb_root rb_root;
    struct rb_node *rb_leftmost;
};
 
struct cfs_rq {
    struct load_weight load;
    unsigned int nr_running;
    u64 min_vruntime;
    struct rb_root_cached tasks_timeline;
};

load：就緒隊列權重，就緒隊列管理的所有調度實體權重之和。

nr_running：就緒隊列上調度實體的個數。

min_vruntime：跟蹤就緒隊列上所有調度實體的最小虛擬時間。

tasks_timeline：用於跟蹤調度實體按虛擬時間大小排序的紅黑樹的信息（包含紅黑樹的根以及紅黑樹中最左邊節點）。

CFS維護了一個按照虛擬時間排序的紅黑樹，所有可運行的調度實體按照p->se.vruntime排序插入紅黑樹。如下圖所示。

CFS選擇紅黑樹最左邊的進程運行。隨著系統時間的推移，原來左邊運行過的進程慢慢的會移動到紅黑樹的右邊，原來右邊的進程也會最終跑到最左邊。因此紅黑樹中的每個進程都有機會運行。

現在我們總結一下。Linux中所有的進程使用task_struct描述。task_struct包含很多進程相關的信息（例如，優先順序、進程狀態以及調度實體等）。但是，每一個調度類並不是直接管理task_struct，而是引入調度實體的概念。CFS調度器使用sched_entity跟蹤調度信息。CFS調度器使用cfs_rq跟蹤就緒隊列信息以及管理就緒態調度實體，並維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root是紅黑樹的根，tasks_timeline->rb_leftmost指向紅黑樹中最左邊的調度實體，即虛擬時間最小的調度實體（為了更快的選擇最適合運行的調度實體，因此rb_leftmost相當於一個緩存）。每個就緒態的調度實體sched_entity包含插入紅黑樹中使用的節點rb_node，同時vruntime成員記錄已經運行的虛擬時間。我們將這幾個數據結構簡單梳理，如下圖所示。