引言

Linux Kernel Development 一書中，關(guān)于 Linux 的進程調(diào)度器并沒有講解的很全面吴菠，只是提到了 CFS 調(diào)度器的基本思想和一些實現(xiàn)細節(jié)奥此；并沒有 Linux 早期的調(diào)度器介紹，以及最近這些年新增的在內(nèi)核源碼樹外維護的調(diào)度器思想搬男。所以在經(jīng)過一番搜尋后经窖，看到了這篇論文 A complete guide to Linux process scheduling坡垫，對 Linux 的調(diào)度器歷史進行了回顧，并且相對細致地講解了 CFS 調(diào)度器画侣。整體來說，雖然比較啰嗦堡妒，但是對于想要知道更多細節(jié)的我來說非常適合配乱，所以就有了翻譯它的沖動。當然，在學(xué)習(xí)過程也參考了其它論文搬泥。下面開啟學(xué)習(xí)之旅吧桑寨，如有任何問題，歡迎指正~

需要注意的是忿檩，在 Linux 中尉尾，線程和進程都是由同一個結(jié)構(gòu)體（task_struct，即任務(wù)描述符）表示的燥透，所以文中會交叉使用進程沙咏、線程和任務(wù)等術(shù)語，可以將它們視作同義詞班套。當然肢藐，也可以將線程（任務(wù)）稱為最小執(zhí)行單元。但 Linux 的調(diào)度算法（如 CFS）可以應(yīng)用更加通用的調(diào)度單元（如線程吱韭、cgroup吆豹、用戶等）±砼瑁總之痘煤，不要過度糾結(jié)這里的術(shù)語，重要的是了解每種調(diào)度算法的思想猿规！

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

Linux 是一個多任務(wù)的操作系統(tǒng)速勇，這就意味著它可以「同時」執(zhí)行多個任務(wù)。在單核處理器上坎拐，任意時刻只能有一個進程可以執(zhí)行（并發(fā)）烦磁；而在多核處理器中，則允許任務(wù)并行執(zhí)行哼勇。然而都伪，不管是何種硬件類型的機器上，可能同時還有很多在內(nèi)存中無法得到執(zhí)行的進程积担，它們正在等待運行陨晶，或者正在睡眠。負責(zé)將 CPU 時間分配給進程的內(nèi)核組件就是「進程調(diào)度器」帝璧。

調(diào)度器負責(zé)維護進程調(diào)度順序先誉，選擇下一個待執(zhí)行的任務(wù)。如同多數(shù)其它的現(xiàn)代操作系統(tǒng)的烁，Linux 實現(xiàn)了搶占式多任務(wù)機制褐耳。也就是說，調(diào)度器可以隨時決定任意進程停止運行渴庆，而讓其它進程獲得 CPU 資源铃芦。這種違背正在運行的進程意愿雅镊，停止其運行的行為就是所謂的「搶占」。搶占通橙凶遥可以在定時器中斷時發(fā)生仁烹，當中斷發(fā)生時，調(diào)度器會檢查是否需要切換任務(wù)咧虎，如果是卓缰，則會完成進程上下文切換。每個進程所獲得的運行時間叫做進程的時間片（timeslice）砰诵。

任務(wù)通痴骰＃可以區(qū)分為交互式（I/O 密集型）和非交互式（CPU 密集型）任務(wù)。交互式任務(wù)通常會重度依賴 I/O 操作（如 GUI 應(yīng)用）胧砰，并且通常用不完分配給它的時間片鳍鸵。而非交互式任務(wù)（如數(shù)學(xué)運算）則需要使用更多的 CPU 資源。它們通常會用完自己的時間片之后被搶占尉间，并不會被 I/O 請求頻繁阻塞偿乖。

當然，現(xiàn)實中的應(yīng)用程序可能同時包含上述兩種分類任務(wù)哲嘲。例如贪薪，文本編輯器，多數(shù)情況下眠副，它會等待用戶輸入画切，但是在執(zhí)行拼寫檢查時也會需要占用大量 CPU 資源。

操作系統(tǒng)的調(diào)度策略就需要均衡這兩種類型的任務(wù)囱怕，并且保證每個任務(wù)都能得到足夠的執(zhí)行資源霍弹，而不會對其它任務(wù)產(chǎn)生明顯的性能影響。 Linux 為了保證 CPU 利用率最大化娃弓，同時又能保證更快的響應(yīng)時間典格，傾向于為非交互式任務(wù)分配更大的時間片芭概，但是以較低的頻率運行它們辛蚊；而針對 I/O 密集型任務(wù)怎茫，則會在較短周期內(nèi)頻繁地執(zhí)行石景。

調(diào)度有關(guān)的進程描述符

進程描述符（task_struct）中的很多字段會被調(diào)度機制直接使用。以下僅列出一些核心的部分菇夸，并在后文詳細討論悼院。

struct task_struct {
    int prio, static_prio, normal_prio;
    unsigned int rt_priority;
    const struct sched_class *sched_class;
    struct sched_entity se;
    struct sched_rt_entity rt;
    …
    unsigned int policy;
    cpumask_t cpus_allowed;
    …
};

關(guān)于這些字段的說明如下：

• prio 表示進程的優(yōu)先級淮逊。進程運行時間侠坎，搶占頻率都依賴于這些值蚁趁。rt_priority 則用于實時（real-time）任務(wù)；
• sched_class 表示進程位于哪個調(diào)度類硅蹦；
• sched_entity 的意義比較特殊荣德。通常把一個線程（Linux 中的進程闷煤、任務(wù)同義詞）叫作最小調(diào)度單元童芹。但是 Linux 調(diào)度器不僅僅只能夠調(diào)度單個任務(wù)涮瞻，而且還可以將一組進程，甚至屬于某個用戶的所有進程作為整體進行調(diào)度假褪。這就允許我們實現(xiàn)組調(diào)度署咽，從而將 CPU 時間先分配到進程組，再在組內(nèi)分配到單個線程生音。當引入這項功能后宁否，可以大幅度提升桌面系統(tǒng)的交互性。比如缀遍，可以將編譯任務(wù)聚集成一個組慕匠，然后進行調(diào)度，從而不會對交互性產(chǎn)生明顯的影響域醇。這里再次強調(diào)下台谊，**Linux 調(diào)度器不僅僅能直接調(diào)度進程，也能對調(diào)度單元（schedulable entities）進行調(diào)度譬挚。這樣的調(diào)度單元正是用 struct sched_entity 來表示的锅铅。需要說明的是，它并非一個指針减宣，而是直接嵌套在進程描述符中的盐须。當然，后面的談?wù)搶⒕劢乖趩芜M程調(diào)度這種簡單場景漆腌。由于調(diào)度器是面向調(diào)度單元設(shè)計的贼邓，所以它會將單個進程也視為調(diào)度單元，因此會使用 sched_entity 結(jié)構(gòu)體操作它們闷尿。sched_rt_entity 則是實時調(diào)度時使用的塑径。
• policy 表明任務(wù)的調(diào)度策略：通常意味著針對某些特定的進程組（如需要更長時間片，更高優(yōu)先級等）應(yīng)用特殊的調(diào)度決策悠砚。Linux 內(nèi)核目前支持的調(diào)度策略如下：
  • SCHED_NORMAL：普通任務(wù)使用的調(diào)度策略晓勇；
  • SCHED_BATCH：不像普通任務(wù)那樣被頻繁搶占，可允許任務(wù)運行盡可能長的時間灌旧，從而更好地利用緩存绑咱，但是代價自然是損失交互性能。這種非常適合批量任務(wù)調(diào)度（批量的 CPU 密集型任務(wù)）;
  • SCHED_IDLE：它要比 nice 19 的任務(wù)優(yōu)先級還要低枢泰，但它并非真的空閑任務(wù);
  • SCHED_FIFO 和 SCHED_RR 是軟實時進程調(diào)度策略描融。它們是由 POSIX 標準定義的，由 <kernel/sched/rt.c> 里面定義的實時調(diào)度器負責(zé)調(diào)度衡蚂。RR 實現(xiàn)的是帶有固定時間片的輪轉(zhuǎn)調(diào)度方式窿克；SCHED_FIFO 則使用的是先進先出的隊列機制骏庸。
• cpus_allowed：用來表示任務(wù)的 CPU 親和性。用戶空間可以通過 sched_setaffinity 系統(tǒng)調(diào)用來設(shè)置年叮。

優(yōu)先級 Priority

進程優(yōu)先級

普通任務(wù)優(yōu)先級

所有的類 Unix 操作系統(tǒng)都實現(xiàn)了優(yōu)先級調(diào)度機制具被。它的核心思想就是給任務(wù)設(shè)定一個值，然后通過該值決定任務(wù)的重要程度只损。如果任務(wù)的優(yōu)先級一致一姿，則一次重復(fù)運行它們。在 Linux 中跃惫，每一個普通任務(wù)都被賦予了一個 nice 值叮叹，它的范圍是 -20 到 +19，任務(wù)默認 nice 值是 0爆存。

image

nice 值越高蛉顽，任務(wù)優(yōu)先級越低（it's nice to others）。Linux 中可以使用 nice(int increment) 系統(tǒng)調(diào)用來修改當前進程的優(yōu)先級先较。該系統(tǒng)調(diào)用的實現(xiàn)位于 <kernel/shced/core.c> 中携冤。默認情況下，用戶只能為該用戶啟動的進程增加 nice 值（即降低優(yōu)先級）拇泣。如果需要增加優(yōu)先級（減少 nice 值）噪叙，或者修改其它用戶進程優(yōu)先級，則必須以 root 身份操作霉翔。

實時任務(wù)優(yōu)先級

在 Linux 中睁蕾，除了普通任務(wù)外，還有一類任務(wù)屬于實時任務(wù)债朵。實時任務(wù)是確保它們能夠在一定時間范圍內(nèi)執(zhí)行的任務(wù)子眶，有兩類實時任務(wù)，列舉如下：

• 硬實時任務(wù)：會有嚴格的時間限制序芦，任務(wù)必須在時限內(nèi)完成臭杰。比如直升機的飛控系統(tǒng)，就需要及時響應(yīng)駕駛員的操控谚中，并做出預(yù)期的動作渴杆。然而，Linux 本身并不支持硬實時任務(wù)宪塔，但是有一些基于它修改的版本磁奖，如 RTLinux（它們通常被稱為 RTOS）則是支持硬實時調(diào)度的。
• 軟實時任務(wù)：軟實時任務(wù)其實也會有時間限制某筐，但不是那么嚴格比搭。也就是說，任務(wù)晚一點運行任務(wù)南誊，并不會造成不可挽回的災(zāi)難性事故身诺。實踐中蜜托，軟實時任務(wù)會提供一定的時間限制保障，但是不要過度依賴這種特性霉赡。例如橄务，VOIP 軟件會使用軟實時保障的協(xié)議傳來送音視頻信號，但是即便因為操作系統(tǒng)負載過高同廉，而產(chǎn)生一點延遲仪糖，也不會造成很大影響柑司。無論如何迫肖，軟實時任務(wù)總會比普通任務(wù)的優(yōu)先級更高。

Linux 中實時任務(wù)的優(yōu)先級范圍是 0~99攒驰，但是有趣的是蟆湖，它和 nice 值的作用剛好相反，這里的優(yōu)先級值越大玻粪，就意味著優(yōu)先級越高隅津。

image

類似其它的 Unix 系統(tǒng)，Linux 也是基于 POSIX 1b 標準定義的 「Real-time Extensions」實現(xiàn)實時優(yōu)先級劲室÷兹裕可以通過如下的命令查看系統(tǒng)中的實時任務(wù)：

$ ps -eo pid, rtprio, cmd

也可通過 chrt -p pid 查看單個進程的詳情。Linux 中可以通過 chrt -p prio pid 更改實時任務(wù)優(yōu)先級很洋。這里需要注意的是充蓝，如果操作的是一個系統(tǒng)進程（通常并不會將普通用戶的進程設(shè)置為實時的），則必須有 root 權(quán)限才可以修改實時優(yōu)先級喉磁。

內(nèi)核視角下的進程優(yōu)先級

實時上谓苟，內(nèi)核看到的任務(wù)優(yōu)先級和用戶看到的并不相同，在計算和管理優(yōu)先級時也需要考慮很多方面协怒。Linux 內(nèi)核中使用 0~139 表示任務(wù)的優(yōu)先級涝焙，并且，值越小孕暇，優(yōu)先級越高（注意和用戶空間的區(qū)別）仑撞。其中 0~99 保留給實時進程，100~139（映射成 nice 值就是 -20~19）保留給普通進程妖滔。

image

我們可以在 <include/linux/sched/prio.h> 頭文件中看到內(nèi)核表示進程優(yōu)先級的單位（scale）和宏定義（macros）隧哮，它們用來將用戶空間優(yōu)先級映射到到內(nèi)核空間。

#define MAX_NICE 19
#define MIN_NICE -20
#define NICE_WIDTH (MAX_NICE - MIN_NICE + 1)
…
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)
/*
* Convert user-nice values [ -20 ... 0 ... 19 ]
* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
* and back.
*/
#define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio) ((prio) - DEFAULT_PRIO)
/*
* 'User priority' is the nice value converted to something we
* can work with better when scaling various scheduler parameters,
* it's a [ 0 ... 39 ] range.
*/
#define USER_PRIO(p) ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))

優(yōu)先級計算

在 task_struct 中有幾個字段用來表示進程優(yōu)先級：

int prio, static_prio, normal_prio;
unsigned int rt_priority;

static_prio 是由用戶或系統(tǒng)設(shè)定的「靜態(tài)」優(yōu)先級映射成內(nèi)核表示的優(yōu)先級：

p->static_prio = NICE_TO_PRIO(nice_value);

normal_prio 存放的是基于 static_prio 和進程調(diào)度策略（實時或普通）決定的優(yōu)先級铛楣，相同的靜態(tài)優(yōu)先級近迁，在不同的調(diào)度策略下，得到的正常優(yōu)先級是不同的簸州。子進程在 fork 時鉴竭，會繼承父進程的 normal_prio歧譬。

prio 則是「動態(tài)優(yōu)先級」，在某些場景下優(yōu)先級會發(fā)生變動搏存。一種場景就是瑰步，系統(tǒng)可以通過給某個任務(wù)優(yōu)先級提升一段時間，從而搶占其它高優(yōu)先級任務(wù)璧眠，一旦 static_prio 確定缩焦，prio 字段就可以通過下面的方式計算：

p->prio = effective_prio(p);
// kernel/sched/core.c 中定義了計算方法
static int effective_prio(struct task_struct *p)
{
    p->normal_prio = normal_prio(p);
    /*
    * If we are RT tasks or we were boosted to RT priority,
    * keep the priority unchanged. Otherwise, update priority
    * to the normal priority:
    */
    if (!rt_prio(p->prio))
        return p->normal_prio;
    return p->prio;
}

static inline int normal_prio(struct task_struct *p)
{
    int prio;
    if (task_has_dl_policy(p))
        prio = MAX_DL_PRIO-1;
    else if (task_has_rt_policy(p))
        prio = MAX_RT_PRIO-1 - p->rt_priority;
    else 
        prio = __normal_prio(p);
    return prio;
}

static inline int __normal_prio(struct task_struct *p)
{
    return p->static_prio;
}

負載權(quán)重（Load Weights）

優(yōu)先級會讓一些任務(wù)比別的任務(wù)更重要，因此也會獲得更多的 CPU 使用時間责静。nice 值和時間片的比例關(guān)系是通過負載權(quán)重（Load Weights）進行維護的袁滥，我們可以在 task_struct->se.load 中看到進程的權(quán)重，定義如下：

struct sched_entity {
    struct load_weight load; /* for load-balancing */
    …
}
struct load_weight {
    unsigned long weight;
    u32 inv_weight;
};

為了讓 nice 值的變化反映到 CPU 時間變化片上更加合理灾螃，Linux 內(nèi)核中定義了一個數(shù)組题翻，用于映射 nice 值到權(quán)重：

static const int 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,
};

來看看如何使用上面的映射表，假設(shè)有兩個優(yōu)先級都是 0 的任務(wù)腰鬼，每個都能獲得 50% 的 CPU 時間（1024 / (1024 + 1024) = 0.5）嵌赠。如果突然給其中的一個任務(wù)優(yōu)先級提升了 1 （nice 值 -1）。此時熄赡，一個任務(wù)應(yīng)該會獲得額外 10% 左右的 CPU 時間姜挺，而另一個則會減少 10% CPU 時間。來看看計算結(jié)果：1277 / (1024 + 1277) ≈ 0.55彼硫，1024 / (1024 + 1277) ≈ 0.45炊豪，二者差距剛好在 10% 左右，符合預(yù)期乌助。完整的計算函數(shù)定義在 <kernel/sched/core.c> 中：

static void set_load_weight(struct task_struct *p)
{
    int prio = p->static_prio - MAX_RT_PRIO;
    struct load_weight *load = &p->se.load;
    /*
    * SCHED_IDLE tasks get minimal weight:
    */
    if (p->policy == SCHED_IDLE) {
        load->weight = scale_load(WEIGHT_IDLEPRIO);
        load->inv_weight = WMULT_IDLEPRIO;
        return;
    }
    load->weight = scale_load(prio_to_weight[prio]);
    load->inv_weight = prio_to_wmult[prio];
}

調(diào)度類 Scheduling Classes

雖說 Linux 內(nèi)核使用的 C 語言并非所謂的 OOP 語言（沒有類似 C++/Java 中的 class 概念）溜在，但是我們可以在內(nèi)核代碼中看到一些使用 C 語言結(jié)構(gòu)體 + 函數(shù)指針（Hooks）的方式來模擬面向?qū)ο蟮姆绞剑橄笮袨楹蛿?shù)據(jù)他托。調(diào)度類也是這樣實現(xiàn)的（此外掖肋，還有 inode_operations, super_block_operations 等），它的定義如下（位于 <kernel/shced/sched.h>）：

// 為了簡單起見赏参，隱藏了部分代碼（如 SMP 相關(guān)的）
struct sched_class {
    // 多個 sched_class 是鏈接在一起的
    const struct sched_class *next;
    // 該 hook 會在任務(wù)進入可運行狀態(tài)時調(diào)用志笼。它會將調(diào)度單元（如一個任務(wù)）放到
    // 隊列中，同時遞增 `nr_running` 變量（該變量表示運行隊列中可運行的任務(wù)數(shù)）
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    // 該 hook 會在任務(wù)不可運行時調(diào)用把篓。它會將任務(wù)移出隊列纫溃，同時遞減 `nr_running`
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    // 該 hook 可以在任務(wù)需要主動放棄 CPU 時調(diào)用，但是需要注意的是韧掩，它不會改變
    // 任務(wù)的可運行狀態(tài)紊浩，也就是說依然會在隊列中等待下次調(diào)度。類似于先 dequeue_task，
    // 再 enqueue_task
    void (*yield_task) (struct rq *rq);
    // 該 hook 會在任務(wù)進入可運行狀態(tài)時調(diào)用并檢查是否需要搶占當前任務(wù)
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
    // 該 hook 用來選擇最適合運行的下一個任務(wù)
    struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev);
    // 該 hook 會在任務(wù)修改自身的調(diào)度類或者任務(wù)組時調(diào)用
    void (*set_curr_task) (struct rq *rq);
    // 通常是在時鐘中斷時調(diào)用坊谁，可能會導(dǎo)致任務(wù)切換
    void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
    // 當任務(wù)被 fork 時通知調(diào)度器
    void (*task_fork) (struct task_struct *p);
    // 當任務(wù)掛掉時通知調(diào)度器
    void (*task_dead) (struct task_struct *p);
};

關(guān)于調(diào)度策略的具體細節(jié)的實現(xiàn)有如下幾個模塊：

• core.c 包含調(diào)度器的核心部分费彼；
• fair.c 實現(xiàn)了 CFS（Comple Faire Scheduler，完全公平任務(wù)調(diào)度器） 調(diào)度器口芍，應(yīng)用于普通任務(wù)箍铲；
• rt.c 實現(xiàn)了實時調(diào)度，應(yīng)用于實時任務(wù)鬓椭；
• idle_task.c 當沒有其它可運行的任務(wù)時颠猴，會運行空閑任務(wù)。
  內(nèi)核是基于任務(wù)的調(diào)度策略（SCHED_*）來決定使用何種調(diào)度類實現(xiàn)小染，并會調(diào)用相應(yīng)的方法翘瓮。SCHED_NORMAL, SCHED_BATCH 和 SCHED_IDLE 進程會映射到 fair_sched_class （由 CFS 實現(xiàn)）；SCHED_RR 和 SCHED_FIFO 則映射的 rt_sched_class （實時調(diào)度器）氧映。

運行隊列 Run Queue

所有可運行的任務(wù)是放在運行隊列中的春畔，并且等待 CPU 運行。每個 CPU 核心都有自己的運行隊列岛都，每個任務(wù)任意時刻只能處于其中一個隊列中。在多處理器機器中振峻，會有負載均衡策略臼疫，任務(wù)就會轉(zhuǎn)移到其它 CPU 上運行的可能。

運行隊列數(shù)據(jù)結(jié)構(gòu)定義如下（位于 <kernel/sched/sched.h>）:

// 為了簡單起見扣孟，隱藏了部分代碼（SMP 相關(guān)）
// 這個是每個 CPU 都會有的一個任務(wù)運行隊列
struct rq
{
    // 表示當前隊列中總共有多少個可運行的任務(wù)（包含所有的 sched class）
    unsigned int nr_running;
#define CPU_LOAD_IDX_MAX 5
    unsigned long cpu_load[CPU_LOAD_IDX_MAX];
    // 運行隊列負載記錄
    struct load_weight load;
    // 嵌套的 CFS 調(diào)度器運行隊列
    struct cfs_rq cfs;
    // 嵌套的實時任務(wù)調(diào)度器運行隊列
    struct rt_rq rt;
    // curr 指向當前正在運行的進程描述符
    // idle 則指向空閑進程描述符（當沒有其它可運行任務(wù)時烫堤，該任務(wù)才會啟動）
    struct task_struct *curr, *idle;
    u64 clock;
    int cpu;
}

何時運行調(diào)度器？

實時上凤价，調(diào)度函數(shù) schedule() 會在很多場景下被調(diào)用鸽斟。有的是直接調(diào)用，有的則是隱式調(diào)用（通過設(shè)置 TIF_NEED_RESCHED 來提示操作系統(tǒng)盡快運行調(diào)度函數(shù)）利诺。以下三個調(diào)度時機值得關(guān)注下：

• 時鐘中斷發(fā)生時富蓄，會調(diào)用 scheduler_tick() 函數(shù)，該函數(shù)會更新一些和調(diào)度有關(guān)的數(shù)據(jù)統(tǒng)計慢逾，并觸發(fā)調(diào)度類的周期調(diào)度方法立倍，從而間接地進行調(diào)度。以 2.6.39 源碼為例侣滩，可能的調(diào)用鏈路如下：

scheduler_tick
└── task_tick
    └── entity_tick
        └── check_preempt_tick
            └── resched_task
                └── set_tsk_need_resched

• 當前正在運行的任務(wù)進入睡眠狀態(tài)口注。在這種情況下，任務(wù)會主動釋放 CPU君珠。通常情況下寝志，該任務(wù)會因為等待指定的事件而睡眠，它可以將自己添加到等待隊列，并啟動循環(huán)檢查期望的條件是否滿足材部。在進入睡眠前悠菜，任務(wù)可以將自己的狀態(tài)設(shè)置為 TASK_INTERRUPTABLE（除了任務(wù)要等待的事件可喚醒外，也可以被信號喚醒）或者 TASK_UNINTERRUPTABLE（自然是不會理會信號咯）败富，然后調(diào)用 schedule() 選擇下一個任務(wù)運行悔醋。

• 睡眠的任務(wù)被喚醒。任務(wù)等待的事件可以在關(guān)聯(lián)的等待隊列上調(diào)用 wake_up() 函數(shù)喚醒任務(wù)：相關(guān)任務(wù)會將自己設(shè)置為可運行狀態(tài)兽叮，并加入運行隊列芬骄。如果當前喚醒的任務(wù)優(yōu)先級比運行隊列中的任何任務(wù)都高，則會設(shè)置 TIF_NEED_RESCHED 標志鹦聪，從而讓操作系統(tǒng)盡快調(diào)用 schedule() 函數(shù)账阻。

Linux 調(diào)度器

早期版本

Linux 0.0.1 版本就已經(jīng)有了一個簡單的調(diào)度器，當然并非適合擁有特別多處理器的系統(tǒng)泽本。該調(diào)度器只維護了一個全局的進程隊列淘太，每次都需要遍歷該隊列來尋找新的進程執(zhí)行，而且對任務(wù)數(shù)量還有嚴格限制（NR_TASKS 在最初的版本中只有 32）规丽。下面來看看這個調(diào)度器是如何實現(xiàn)的吧：

// 'schedule()' is the scheduler function. 
// This is GOOD CODE! There probably won't be any reason to change 
// this, as it should work well in all circumstances (ie gives 
// IO-bound processes good response etc)...
void schedule(void)
{
    int i, next, c;
    struct task_struct **p;
    // 遍歷所有任務(wù)蒲牧，如果有信號，則需要喚醒 `TASK_INTERRUPTABLE` 的任務(wù)
    for (p = &LAST_TASK; p > &FIRST_TASK; --p)
        if (*p) {
            if ((*p)->alarm && (*p)->alarm < jiffies) {
                (*p)->signal |= (1 << (SIGALRM - 1));
                (*p)->alarm = 0;
            }
            if ((*p)->signal && (*p)->state == TASK_INTERRUPTIBLE)
                (*p)->state = TASK_RUNNING;
        }
    while (1)
    {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        // 遍歷所有任務(wù)赌莺，找到時間片最長的那個
        while (--i) {
            if (!*--p)
                continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        if (c)
            break;
        // 遍歷任務(wù)冰抢，重新設(shè)值時間片
        for (p = &LAST_TASK; p > &FIRST_TASK; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
    }
    // 切換到下一個需要執(zhí)行的任務(wù)
    switch_to(next);
}

O(n)

2.4 版本的 Linux 內(nèi)核使用的調(diào)度算法非常簡單和直接，由于每次在尋找下一個任務(wù)時需要遍歷系統(tǒng)中所有的任務(wù)（鏈表）艘狭，因此被稱為 O(n) 調(diào)度器（時間復(fù)雜度）挎扰。

當然，該調(diào)度器要比 0.01 版本內(nèi)核中的調(diào)度算法稍微復(fù)雜點巢音，它引入了 epoch 概念遵倦。也就是將時間分成紀元（epochs），也就是每個進程的生命周期官撼。理論上來說梧躺，每個紀元結(jié)束，每個進程都應(yīng)該運行過一次了歧寺，而且通常用光了它當前的時間片燥狰。但實際上，有些任務(wù)并沒有完全用完時間片斜筐，那么它剩余時間片的一半將會和新的時間片相加龙致，從而在下一個紀元運行更長的時間。

我們來看下 schedule() 算法的核心源碼：

// schedule() 算法會遍歷所有的任務(wù)（O(N)）顷链，并且計算出每個任務(wù)的
// goodness 值目代，且挑選出「最好」的任務(wù)來運行。
// 以下是部分核心源碼，主要是了解下它的思路榛了。
asmlinkage void schedule(void)
{
    // 任務(wù)（進程）描述符：
    // 1. prev: 當前正在運行的任務(wù)
    // 2. next: 下一個將運行的任務(wù)
    // 3. p: 當前正在遍歷的任務(wù)
    struct task_struct *prev, *next, *p;
    int this_cpu, c; // c 表示權(quán)重值
repeat_schedule:
    // 默認選中的任務(wù)
    next = idle_task(this_cpu);
    c = -1000;
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) {
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c)
                c = weight, next = p;
        }
    }
}

源碼中的 goodness() 函數(shù)會計算出一個權(quán)重值在讶，它的算法基本思想就是基于進程所剩余的時鐘節(jié)拍數(shù)（時間片），再加上基于進程優(yōu)先級的權(quán)重值霜大。返回值如下：

• -1000 表示不要選擇該進程運行
• 0 表示時間片用完了构哺，需要重新計算 counters（可能會被選中運行）
• 正整數(shù)：表示 goodness 值（越大越好）
• +1000 表示實時進程，接下來就要選擇它運行

最后战坤，針對 O(n) 調(diào)度器做下總結(jié)：

1. 算法實現(xiàn)非常簡單曙强，但是不高效（任務(wù)越多，遍歷耗費時間越久）
2. 沒有很好的擴展性途茫，多核處理器怎么辦碟嘴？
3. 對于實時任務(wù)調(diào)度支持較弱（無論如何作為優(yōu)先級高的實時任務(wù)都需要在遍歷完列表后才可以知道）

O(1)

Ingo Molnár 大佬在 2.6 版本的內(nèi)核中加入了全新的調(diào)度算法，它能夠在常數(shù)時間內(nèi)調(diào)度任務(wù)囊卜，因此被稱為 O(1) 調(diào)度器娜扇。我們來看看它引入的一些新特性：

• 全局優(yōu)先級單位，范圍是 0~139栅组，數(shù)值越低雀瓢，優(yōu)先級越高
• 將任務(wù)拆分成實時（0_{99）和正常（100}139）兩部分。更高優(yōu)先級任務(wù)獲得更多時間片
• 即刻搶占（early preemption）笑窜。當任務(wù)狀態(tài)變成 TASK_RUNNING 時致燥，內(nèi)核會檢查其優(yōu)先級是否比當前運行的任務(wù)優(yōu)先級更高，如果是的話排截，則搶占當前正在運行的任務(wù)，切換到該任務(wù)
• 實時任務(wù)使用靜態(tài)優(yōu)先級
• 普通任務(wù)使用使用動態(tài)優(yōu)先級辐益。任務(wù)優(yōu)先級會在其使用完自己的時間片后重新計算断傲，內(nèi)核會考慮它過去的行為，決定它的交互性等級智政。交互型任務(wù)更容易得到調(diào)度

O(n) 的調(diào)度器會在每個紀元結(jié)束后（所有任務(wù)的時間片都使用過）认罩，才會重新計算任務(wù)優(yōu)先級。而 O(1) 則是在每個任務(wù)時間片配額用完后就重新計算優(yōu)先級续捂。O(1) 調(diào)度器為每個 CPU 維護了兩個隊列垦垂，即 active 和 expired。active 隊列存放的是時間片尚未用完的任務(wù)牙瓢，而 expired 則是時間片已經(jīng)耗盡的任務(wù)劫拗。當一個任務(wù)的時間片用完后，就會被轉(zhuǎn)到 expired 隊列矾克，而且會重新計算它的優(yōu)先級页慷。當 active 隊列任務(wù)全部轉(zhuǎn)移到 expired 隊列后，會交換二者（讓 active 指向 expired 隊列，expired 指向 active 隊列）酒繁∽艺茫可以看到，優(yōu)先級的計算州袒，隊列切換都和任務(wù)數(shù)量多寡無關(guān)揭绑，能夠在 O(1) 時間復(fù)雜度下完成。

在先前介紹的調(diào)度算法中郎哭，如果想要取一個優(yōu)先級最高的任務(wù)他匪，還需要遍歷整個任務(wù)鏈表才可以。而 O(1) 調(diào)度器則很特別彰居，它為每種優(yōu)先級提供了一個任務(wù)鏈表诚纸。所有的可運行任務(wù)會被分散在不同優(yōu)先級隊應(yīng)的鏈表中。

接下來看看全新的 runqueue 是怎么定義的吧：

struct runqueue {
    unsigned long nr_running; /* 可運行的任務(wù)總數(shù)（某個 CPU） */
    struct prio_array *active; /* 指向 active 的隊列的指針 */
    struct prio_array *expired; /* 指向 expired 的隊列的指針 */
    struct prio_array arrays[2]; /* 實際存放不同優(yōu)先級對應(yīng)的任務(wù)鏈表 */
}

通過下面的圖可以直觀感受下任務(wù)隊列：

image

接下來看看 prio_array 是怎么定義的：

struct prio_array {
    int nr_active; /* 列表中的任務(wù)總數(shù) */
    unsigned long bitmap[BITMAP_SIZE]; /* 位圖表示對應(yīng)優(yōu)先級鏈表是否有任務(wù)存在 */
    struct list_head queue[MAX_PRIO]; /* 任務(wù)隊列（每種優(yōu)先級對應(yīng)一個雙向鏈表） */
};

可以看到陈惰，在 prio_array 中存在一個位圖畦徘，它是用來標記每個 priority 對應(yīng)的任務(wù)鏈表是否存在任務(wù)的。接下來看看為何 O(1) 調(diào)度器可以在常數(shù)時間找到需要運行的任務(wù)：

1. 常數(shù)時間確定優(yōu)先級：首先會在位圖中查找到第一個設(shè)置為 1 的位（總共有 140 bits抬闯，從第一個 bit 開始搜索井辆，這樣可以保證高優(yōu)先級的任務(wù)先得到機會運行），如果找到了就可以確定哪個優(yōu)先級有任務(wù)溶握，假設(shè)找到后的值為 priority杯缺；
2. 常數(shù)時間獲得下一個任務(wù)：在 queue[priority] 對應(yīng)的任務(wù)鏈表中提取第一個任務(wù)來執(zhí)行（多個任務(wù)會輪轉(zhuǎn)執(zhí)行）。
   
   image

好了睡榆，是時候總結(jié)下 O(1) 調(diào)度器的優(yōu)缺點了：

1. 設(shè)計上要比 O(n) 調(diào)度器更加復(fù)雜精妙萍肆；
2. 相對來說擴展性更好，性能更優(yōu)胀屿，在任務(wù)切換上的開銷更刑链А；
3. 用來標記任務(wù)是否為交互類型的算法還是過于復(fù)雜宿崭，且容易出錯亲铡。

Staircase

Staircase Scheduler 是 Con Kolivas 為了改善桌面系統(tǒng)交互應(yīng)用的響應(yīng)時間而實現(xiàn)的調(diào)度器，但它并非內(nèi)核官方支持的調(diào)度器葡兑。它的整體設(shè)計思想類似于 Operating Systems: The Three Easy Pieces 中提到的 MLFQ（Multilevel Feedback Queue奖蔓，多級反饋隊列）。

我們來看下它的設(shè)計思想：

1. 首先讹堤，它也是將任務(wù)按照優(yōu)先級放在不同的任務(wù)鏈表中（類似上面的 active 隊列）
2. 調(diào)度器每次會從最高優(yōu)先級的任務(wù)鏈表中獲取一個要切換執(zhí)行的任務(wù)吆鹤，當任務(wù)時間片使用完畢后，會將其優(yōu)先級調(diào)低一個等級蜕劝，直到其優(yōu)先級降到最低檀头。
3. 當處于最低優(yōu)先級的任務(wù)用光了時間片后轰异，它會被重新放到更高優(yōu)先級的任務(wù)鏈表中（這個新的優(yōu)先級是它之前最高優(yōu)先級減 1 后的值），同時會獲得兩倍于之前的時間片
4. 對于長時間睡眠的任務(wù)暑始，會被放到最高優(yōu)先級任務(wù)鏈表搭独。所以交互式任務(wù)可以保持在最高優(yōu)先級位置，從而保持良好的響應(yīng)性能廊镜；而批處理任務(wù)則處于低優(yōu)先級牙肝，但是會獲得更多的執(zhí)行時間。

CFS

單核調(diào)度

CFS 的全稱是 Complete Fair Scheduler嗤朴，也就是完全公平調(diào)度器配椭。它實現(xiàn)了一個基于權(quán)重的公平隊列算法，從而將 CPU 時間分配給多個任務(wù)（每個任務(wù)的權(quán)重和它的 nice 值有關(guān)雹姊，nice 值越低股缸，權(quán)重值越高）。每個任務(wù)都有一個關(guān)聯(lián)的虛擬運行時間 vruntime吱雏，它表示一個任務(wù)所使用的 CPU 時間除以其優(yōu)先級得到的值敦姻。相同優(yōu)先級和相同 vruntime 的兩個任務(wù)實際運行的時間也是相同的，這就意味著 CPU 資源是由它們均分了歧杏。為了保證所有任務(wù)能夠公平推進镰惦，每當需要搶占當前任務(wù)時，CFS 總會挑選出 vruntime 最小的那個任務(wù)運行犬绒。

內(nèi)核版本在 2.6.38 之前旺入，每個線程（任務(wù)）會被當成獨立的調(diào)度單元，并且和系統(tǒng)中其它線程共享資源凯力，這就意味著一個多線程的應(yīng)用會比單線程的應(yīng)用獲得更多的資源茵瘾。之后，CFS 不斷改進咐鹤，目前已經(jīng)支持將一個應(yīng)用中的線程打包到 cgroup 結(jié)構(gòu)中龄捡，cgroup 的 vruntime 是其中所有線程的 vuntime 之和。然后 CFS 就可以將它的算法應(yīng)用于cgroup 之間慷暂，從而保證公平性。當某個 cgroup 被選中后晨雳，其中擁有最小 vruntime 的線程會被執(zhí)行行瑞，從而保證 cgroup 中的線程之間的公平性。cgroup 還可以嵌套餐禁，例如 systemd 會自動配置 cgroup 來保證不同用戶之間的公平性血久，然后在用戶運行的多個應(yīng)用之間維持公平性。

CFS 通過在一定時間內(nèi)運行調(diào)度所有的線程來避免饑餓問題帮非。當運行的 線程數(shù)在 8 個及以下時氧吐，默認的時間周期是 48ms讹蘑；而當多于 8 個線程時，時間周期就會隨著線程數(shù)量而增加（6ms * 線程數(shù)筑舅，之所以選擇 6ms座慰，是為了避免頻繁搶占，導(dǎo)致上下文切換頻繁切換的開銷）翠拣。由于 CFS 總是會挑選 vruntime 最小的線程執(zhí)行版仔，它就需要避免某個線程的 vruntime 太小，以至于其它線程需要等待很久才能得到調(diào)度（會有饑餓問題）误墓。所以在實踐中蛮粮，CFS 會保證所有線程之間的 vruntime 之差低于搶占時間（6ms），它是通過如下兩點來保證的：

1. 當線程創(chuàng)建時谜慌，它的 vruntime 值等于運行隊列中等待執(zhí)行線程的最大 vruntime然想；
2. 當線程從睡眠中喚醒時，它的 vruntime 值會被更新為大于或等于所有待調(diào)度線程中最小的 vruntime欣范。使用最小 vruntime 還可以保證頻繁睡眠的線程優(yōu)先被調(diào)度变泄，這對于桌面系統(tǒng)非常適合，它會減少交互應(yīng)用的響應(yīng)延遲熙卡。

CFS 還引入了啟發(fā)式調(diào)度思想來改善高速緩存利用率杖刷。例如，當線程被喚醒時驳癌，它會檢查該線程的 vruntime 和正在運行的線程 vruntime 之差是否非常顯著（臨界值是 1ms）滑燃，如果不是的話，則不會搶占當前正在運行的任務(wù)颓鲜。但是這種做法還是以犧牲調(diào)度延遲為代價的表窘，算是一種權(quán)衡吧。

多核負載均衡

在多核環(huán)境中甜滨，Linux CFS 會將工作（work）分攤到多個處理器核心中執(zhí)行乐严。但是這不等同于將線程均分到多個處理器。比如衣摩，一個 CPU 密集型的線程和 10 個頻繁睡眠的線程可能分別在兩個核上執(zhí)行昂验，其中一個專門執(zhí)行 CPU 密集型線程；而另一個則處理那 10 個頻繁睡眠的線程艾扮。

為了多個處理器上的工作量均衡既琴，CFS 使用了 load 指標來衡量線程和處理器的負載情況。線程的負載和線程的 CPU 平均使用率相關(guān)：經(jīng)常睡眠的線程負載要低于不睡眠的線程負載泡嘴。類似 vruntime甫恩，線程的負載也是線程的優(yōu)先級加權(quán)得到的。而處理器的負載是在該處理器上可運行線程的負載之和酌予。CFS 會嘗試均衡處理器的負載磺箕。

CFS 會在線程創(chuàng)建和喚醒時關(guān)注處理器的負載情況奖慌，調(diào)度器首先要決定將任務(wù)放在哪個處理器的運行隊列中。這里也會涉及到啟發(fā)式思想松靡，比如简僧，如果 CFS 檢查到生產(chǎn)者-消費者模型，那么它會將消費者線程盡可能地分散到機器的多個處理器上击困，因為多數(shù)核心都適合處理喚醒的線程涎劈。

負載均衡還會周期性發(fā)生橡类，每隔 4ms猖闪，每個處理器都會嘗試從其它處理器偷取一些工作。當然萝玷，這種 work-stealing 均衡方法還會考慮機器的拓撲結(jié)構(gòu)：處理器會嘗試從距離它們「更近」的其它處理器上嘗試竊取工作脸哀，而非距離「更遠」的處理器（如遠程 NUMA 節(jié)點）蹦浦。當處理器決定要從其它處理器竊取任務(wù)時，它會嘗試在二者之間均衡負載撞蜂，并且會竊取多達 32 個線程盲镶。此外，當處理器進入空閑狀態(tài)時蝌诡，它也會立刻調(diào)用負載均衡器溉贿。

在大型的 NUMA 機器上，CFS 并不會粗暴地比較所有 CPU 的負載浦旱，而是以分層的方式進行負載均衡宇色。以一臺有兩個 NUMA 節(jié)點的機器為例，CFS 會先在 NUMA 節(jié)點內(nèi)部的處理器之間進行負載均衡颁湖，然后比較 NUMA 節(jié)點之間的負載（通過節(jié)點內(nèi)部處理器負載計算得到）宣蠕，再決定要不要在兩個節(jié)點之間進行負載均衡。如果 NUMA 節(jié)點之間的負載差距在 25% 以內(nèi)甥捺，則不會進行負載均衡抢蚀。總結(jié)來說镰禾，如果兩個處理器（或處理器組）之間的距離越遠皿曲，那么只有在不平衡性差距越大的情況下才會考慮負載均衡。

運行隊列

CFS 引入了紅黑樹（本質(zhì)上是一棵半平衡二叉樹吴侦，對于插入和查找都有 O(log(N)) 的時間復(fù)雜度）來維護運行隊列谷饿，樹的節(jié)點值是調(diào)度單元的 vruntime，擁有最小 vruntime 的節(jié)點位于樹的最左下邊妈倔。

image

接下來看看 cfs_rq 數(shù)據(jù)結(jié)構(gòu)的定義（位于 <kernel/sched/sched.h>）：

struct cfs_rq
{
    // 所有任務(wù)的累計權(quán)重值
    struct load_weight load;
    // 表示該隊列中有多少個可運行的任務(wù)
    unsigned int nr_running;
    // 運行隊列中最小的 vruntime
    u64 min_vruntime;
    // 紅黑樹的根節(jié)點，指向運行任務(wù)隊列
    struct rb_root tasks_timeline;
    // 下一個即將被調(diào)度的任務(wù)
    struct rb_node *rb_leftmost;
    // 指向當前正在運行的調(diào)度單元
    struct sched_entity *curr;
}

CFS 算法實際應(yīng)用于調(diào)度單元（這是一個更通用的抽象绸贡，可以是線程盯蝴、cgroups 等）毅哗，調(diào)度單元數(shù)據(jù)結(jié)構(gòu)定義如下（位于 <include/linux/sched.h>）：

struct sched_entity
{
    // 表示調(diào)度單元的負載權(quán)重（比如該調(diào)度單元是一個組，則該值就是該組下所有線程的負載權(quán)重的組合）
    struct load_weight load; /* for load-balancing */
    // 表示紅黑樹的節(jié)點
    struct rb_node run_node;
    // 表示當前調(diào)度單元是否位于運行隊列
    unsigned int on_rq;
    // 開始執(zhí)行時間
    u64 exec_start;
    // 總共運行的時間捧挺，該值是通過 `update_curr()` 更新的虑绵。
    u64 sum_exec_runtime;
    // 基于虛擬時鐘計算出該調(diào)度單元已運行的時間
    u64 vruntime;

    // 用于記錄之前運行的時間之和
    u64 prev_sum_exec_runtime;
};

虛擬時鐘

前面提到的 vruntime 究竟是什么呢？為什么叫作虛擬運行時間呢闽烙？接下來就要揭開它的神秘面紗翅睛。為了更好地實現(xiàn)公平性，CFS 使用了虛擬時鐘來測量一個等待的調(diào)度單元在一個完全公平的處理器上允許執(zhí)行的時間黑竞。然而捕发，虛擬時鐘并沒有真實的實現(xiàn)，它只是一個抽象概念很魂。

我們可以基于真實時間和任務(wù)的負載權(quán)重來計算出虛擬運行時間扎酷，該算法是在 update_cur() 函數(shù)中實現(xiàn)的，它會更新調(diào)度單元的時間記賬信息遏匆，以及 CFS 運行隊列的 min_vruntime（完整定義位于 <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;
    // 計算出調(diào)度單元開始執(zhí)行時間和當前之間的差值法挨，即真實運行時間
    delta_exec = now - curr->exec_start;
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    // 如果任務(wù)的優(yōu)先級是默認的優(yōu)先級（內(nèi)部 nice 值是 120），那么虛擬運行時間
    // 就是真實運行時間幅聘。否則凡纳，會基于 `__calc_delta` 計算出虛擬運行時間。
    if (unlikely(se->load.weight != NICE_0_LOAD))
        // 該計算過程基本等同于：
        // delta = delta_exec * NICE_0_LOAD / cur->load.weight;
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    u64 vruntime = cfs_rq->min_vruntime;
    if (cfs_rq->curr)
        // 如果此時有任務(wù)在運行帝蒿，就更新最小運行時間為當前任務(wù)的 vruntime
        vruntime = cfs_rq->curr->vruntime;
    if (cfs_rq->rb_leftmost)
    {
        // 獲得下一個要運行的調(diào)度單元
        struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
                                           struct sched_entity,
                                           run_node);
        if (!cfs_rq->curr)
            vruntime = se->vruntime;
        else
            // 保證 min_vruntime 是二者之間較小的那個值
            vruntime = min_vruntime(vruntime, se->vruntime);
    }

    // 這里之所以去二者之間的最大值荐糜，是為了保證 min_vruntime 能夠單調(diào)增長
    // 可以想想為什么需要這樣做？
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

最后陵叽，來總結(jié)下使用虛擬時鐘的意義：

• 當任務(wù)運行時狞尔，它的虛擬時間總是會增加，從而保證它會被移動到紅黑樹的右側(cè)巩掺；

• 對于高優(yōu)先級的任務(wù)偏序，虛擬時鐘的節(jié)拍更慢，從而讓它移動到紅黑樹右側(cè)的速度就越慢胖替，因此它們被再次調(diào)度的機會就更大些研儒。

  
  
  image

選擇下一個任務(wù)

CFS 可以在紅黑樹中一直找到最左（leftmost）邊的節(jié)點作為下一個運行的任務(wù)。但是真正實現(xiàn) __pick_first_entity() 的函數(shù)其實并沒有真正地執(zhí)行查找（雖然可以在 O(log(N)) 時間內(nèi)找到）独令，我們可以看下它的定義（完整定義位于 <kernel/sched/fair.c>）：

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    // 其實這里取的是緩存的 leftmost 節(jié)點
    // 所以執(zhí)行就會更快了
    struct rb_node *left = cfs_rq->rb_leftmost;
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

實時調(diào)度器

Linux 實時任務(wù)調(diào)度器實現(xiàn)位于 <kernel/sched/rt.c端朵，對于系統(tǒng)而言，實時任務(wù)屬于貴客燃箭，一旦存在實時任務(wù)需要調(diào)度冲呢，那就應(yīng)當盡可能及時地為它們服務(wù)。對于實時任務(wù)而言招狸，有兩種調(diào)度策略存在：

• SCHED_FIFO: 這個其實就是一個先到先服務(wù)的調(diào)度算法敬拓。這類任務(wù)沒有時間片限制邻薯，它們會一直運行直到阻塞或者主動放棄 CPU，亦或者被更高優(yōu)先級的實時任務(wù)搶占乘凸。該類任務(wù)總會搶占 SCHED_NORMAL 任務(wù)厕诡。如果多個任務(wù)具有相同的優(yōu)先級，那它們會以輪詢的方式調(diào)度（也就是當一個任務(wù)完成后营勤，會被放到隊列尾部等待下次執(zhí)行）灵嫌；

• SCHED_RR: 這種策略類似于 SCHED_FIFO，只是多了時間片限制葛作。相同優(yōu)先級的任務(wù)會以輪詢的方式被調(diào)度寿羞，每個運行的任務(wù)都會一直運行，直到其用光自己的時間片进鸠，或者被更高優(yōu)先級的任務(wù)搶占稠曼。當任務(wù)的時間片用光后，它會重新補充能量客年，并被加入到隊列尾部霞幅。默認的時間片是 100ms，可以在 <include/linux/sched/rt.h> 找到其定義量瓜。

實時任務(wù)的優(yōu)先級是靜態(tài)的司恳，不會像之前提到的算法，會重新計算任務(wù)優(yōu)先級绍傲。用戶可以通過 chrt 命令更改任務(wù)優(yōu)先級扔傅。

實現(xiàn)細節(jié)

實時任務(wù)有自己的調(diào)度單元數(shù)據(jù)結(jié)構(gòu)（位于 <include/linux/sched.h>），其定義如下：

struct sched_rt_entity
{
    struct list_head run_list;
    unsigned long timeout;
    unsigned long watchdog_stamp;
    unsigned int time_slice;
    struct sched_rt_entity *back;
    struct sched_rt_entity *parent;
    /* rq on which this entity is (to be) queued: */
    struct rt_rq *rt_rq;
};

SCHED_FIFO 的時間片是 0烫饼，可以在 <kernel/sched/rt.c> 中看到具體定義：

int sched_rr_timeslice = RR_TIMESLICE;
static unsigned int get_rr_interval_rt(struct rq *rq,
                                       struct task_struct *task)
{
    if (task->policy == SCHED_RR)
        return sched_rr_timeslice;
    else
        return 0;
}

而關(guān)于運行隊列的定義如下：

/* Real-Time classes' related field in a runqueue: */
struct rt_rq
{
    // 所有相同優(yōu)先級的實時任務(wù)都保存在 `active.queue[prio]` 鏈表中
    struct rt_prio_array active;
    unsigned int rt_nr_running;
    struct rq *rq; /* main runqueue */
};

/*
* This is the priority-queue data structure of the RT scheduling class:
*/
struct rt_prio_array
{
    /* include 1 bit for delimiter */
    // 類似 O(1) 調(diào)度器猎塞，使用位圖來標記對應(yīng)優(yōu)先級的鏈表是否為空
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1);
    struct list_head queue[MAX_RT_PRIO];
};

類似于 CFS 中的 update_curr() 函數(shù)，update_curr_rt() 函數(shù)用來跟蹤實時任務(wù)的 CPU 占用情況杠纵，收集一些統(tǒng)計信息荠耽，更新時間片等，但這里使用的是真實時間比藻，而沒有虛擬時間的概念铝量。完整定義可以參考 kernel/sched/rt.c#L955。

BFS & MuqSS

關(guān)于 BFS 和 MuqSS 的精彩介紹可以參考 這篇文章银亲，這里不再贅述慢叨。
總體來說，BFS 是一個適用于桌面或移動設(shè)備的調(diào)度器务蝠，設(shè)計地比較簡潔拍谐，用于改善桌面應(yīng)用的交互性，減小響應(yīng)時間，提升用戶體驗赠尾。它采用了全局單任務(wù)隊列設(shè)計力穗，不再讓每個 CPU 都有獨立的運行隊列。雖然使用單個全局隊列气嫁，需要引入隊列鎖來保證并發(fā)安全性，但是對于桌面系統(tǒng)而言够坐，處理器通常都比較少寸宵，鎖的開銷基本可以忽略。BFS 每次會在任務(wù)鏈表中選擇具有最小 virtual deadline 的任務(wù)運行元咙。

MuqSS 是作者后來基于 BFS 改進的一款調(diào)度器梯影，同樣是用于桌面環(huán)境任務(wù)調(diào)度。它主要解決了 BFS 的兩個問題：

1. 每次需要在對應(yīng)優(yōu)先級鏈表中遍歷查找需要執(zhí)行任務(wù)庶香，這個時間復(fù)雜度為 O(n)甲棍。所以新的調(diào)度器引入了跳表來解決該問題，從而將時間復(fù)雜度降低到 O(1)赶掖。
2. 全局鎖爭奪的開銷優(yōu)化感猛，采用 try_lock 替代 lock。
   
   image

深入學(xué)習(xí)

• 《Linux 設(shè)計與實現(xiàn) 第三版》進程調(diào)度章節(jié)
• A complete guide to Linux process scheduling
• Process Scheduling in Linux
• 內(nèi)核文檔：CFS Scheduler 設(shè)計
• Linux 進程與線程：《Linux 系統(tǒng)編程手冊 第 28 章及后續(xù)》
  • 可以關(guān)注下和進程線程有關(guān)的系統(tǒng)調(diào)用
  • Pthread 線程是怎么在 Linux 中實現(xiàn)的
• Linux 公平調(diào)度
  • 對比了傳統(tǒng)調(diào)度器和 CFS 的區(qū)別
  • 簡單介紹了 CFS 的實現(xiàn)
• The Battle of Schedulers: FreeBSD ULE vs Linux CFS
  • 重點可以看下關(guān)于 CFS 的簡述 & 負載均衡部分
  • 可以簡單看看 ULE 是的實現(xiàn)原理（interactive, batch queue）奢赂，為什么可能會有餓死的情況
• NUMA 架構(gòu)深究
  • 早期的 x86 是 Universal Memory Arch, UMA 架構(gòu)
  • NUMA 架構(gòu)出來后陪白，訪問不同內(nèi)存地址，速度是有差別了膳灶，和硬件架構(gòu)有很大關(guān)系
• Kernel 調(diào)度系統(tǒng)
  • 重點關(guān)注作者關(guān)于 CFS 列出的幾個靈魂拷問
  • vruntime 在什么時候發(fā)生改變咱士？
  • vruntime 初始值是怎么設(shè)定的？
• 兩個非常有意思的適合桌面使用的 Linux task 調(diào)度器: BFS 和 MuqSS

聲明

• 本文鏈接： http://ifaceless.space/2019/11/17/guide-to-linux-scheduler/
• 版權(quán)聲明：本博客所有文章除特別聲明外轧钓，均采用 CC BY-NC-SA 3.0 許可協(xié)議序厉。轉(zhuǎn)載請注明出處！