圖解｜Linux 組排程

語言: CN / TW / HK

時間 2022-01-24 19:00:05 Linux核心那些事

在介紹 組排程 前，我們先來重溫下什麼是 程序排程 。

本文基於 Linux-2.6.26 版本

什麼是程序排程

一般來說，在作業系統中會執行多個程序（幾個到幾千個不等），但一臺計算機的 CPU 資源是有限的，如 8 核的 CPU 只能同時執行 8 個程序。那麼當程序數大於 CPU 核心數時，作業系統是如何同時執行這些程序的呢？

這裡就涉及 程序排程 問題。

作業系統執行程序的時候，是按 時間片 來執行的。 時間片 是指一段很短的時間段（如20毫秒），作業系統會為每個程序分配一些時間片。當程序的時間片用完後，作業系統將會把當前執行的程序切換出去，然後從程序佇列中選擇一個合適的程序執行，這就是所謂的 程序排程 。如下圖所示：

什麼是組排程

一般來說，作業系統排程的實體是 程序 ，也就是說按程序作為單位來排程。但如果按程序作為排程實體，就會出現以下情況：

Linux 是一個支援多使用者的作業系統，如果 A 使用者運行了 10 個程序，而 B 使用者只運行了 2 個程序，那麼就會出現 A 使用者使用的 CPU 時間是 B 使用者的 5 倍。如果 A 使用者和 B 使用者都是花同樣的錢來買的虛擬主機，那麼對 B 使用者來說是非常不公平的。

為了解決這個問題，Linux 實現了 組排程 這個功能。那麼什麼是 組排程 呢？

組排程 的實質是：排程時候不再以程序作為排程實體，而是以 程序組 作為排程實體。比如上面的例子，可以把 A 使用者執行的程序劃分為 程序組A ，而 B 使用者執行的程序劃分為 程序組B 。

排程的時候， 程序組A 和 程序組B 分配到相同的可執行 時間片 ，如 程序組A 和 程序組B 各分配到 100 毫秒的可執行時間片。由於 程序組A 有 10 個程序，所以每個程序分配到的可執行時間片為 10 毫秒。而 程序組B 只有 2 個程序，所以每個程序分配到的可執行時間片為 50 毫秒。

下圖是 組排程 的原理：

如上圖所示，當核心進行排程時，首先以 程序組 作為排程實體。當選擇出最優的 程序組 後，再從 程序組 中選擇出最優的程序進行執行，而被切換出來的程序將會放置回原來的 程序組 。

由於 組排程 是建立在 cgroup 機制之上的，而 cgroup 又是基於 虛擬檔案系統 ，所以 程序組 是以樹結構存在的。也就是說， 程序組 除了可以包含程序，還可以包含程序組。如下圖所示：

cgroup 相關的知識點可以參考文章：《cgroup介紹》和《cgroup實現原理》

在 Linux 系統啟動時，會建立一個根程序組 init_task_group 。然後，我們可以通過使用 cgroup 的 CPU 子系統建立新的程序組，如下命令：

$ mkdir /sys/cgroup/cpu/A                     # 在根程序組中建立程序組A
$ mkdir /sys/cgroup/cpu/B                     # 在根程序組中建立程序組B
$ mkdir /sys/cgroup/cpu/A/C                   # 在程序組A中建立程序組C
$ echo 1923 > /sys/cgroup/cpu/A/cgroup.procs  # 向程序組A中新增程序ID為1923的程序

Linux 在排程的時候，首先會根據 完全公平排程演算法 從根程序組中篩選出一個最優的程序或者程序組進行排程。

如果篩選出來的是程序，那麼可以直接把當前執行的程序切換到篩選出來的程序執行即可。
如果篩選出來的是程序組，那麼就繼續根據 完全公平排程演算法 從程序組中篩選出一個最優的程序或者程序組進行排程（重複進行第一步操作），如此類推。

組排程實現

接下來，我們將介紹 組排程 是如何實現的。在分析之前，為了對 完全公平排程演算法 有個大體瞭解，建議先看看這篇文章：《 Linux完全公平排程演算法》。

1. 程序組

在 Linux 核心中，使用 task_group 結構表示一個程序組。其定義如下：

struct task_group {
    struct cgroup_subsys_state css; // cgroup相關結構

    struct sched_entity **se;       // 排程實體(每個CPU分配一個)
    struct cfs_rq **cfs_rq;         // 完全公平排程執行佇列(每個CPU分配一個)
    unsigned long shares;           // 當前程序組權重(用於獲取時間片)
    ...

    // 由於程序組支援巢狀, 也就是說程序組可以包含程序組
    // 所以, 程序組可以通過下面3個成員組成一個樹結構
    struct task_group *parent;  // 父程序組
    struct list_head siblings;  // 兄弟程序組
    struct list_head children;  // 子程序組
};

下面介紹一下 task_group 結構各個欄位的作用：

se
完全公平排程演算法
sched_entity
sched_entity
sched_entity
sched_entity

cfs_rq ： 完全公平排程演算法 的執行佇列。 完全公平排程演算法 在排程時是通過 cfs_rq 結構完成的， cfs_rq 結構使用一棵紅黑樹將需要排程的程序或者程序組組織起來，然後選擇最左端的節點作為要執行的程序或程序組，詳情可以參考文章：《 Linux完全公平排程演算法》。由於程序組可能在不同的 CPU 上排程，所以程序組也為每個 CPU 分配一個執行佇列。
shares ：程序組的權重，用於計算當前程序組的可執行時間片。
```
parent
siblings
children
```

task_group 、 sched_entity 和 cfs_rq 這三個結構的關係如下圖所示：

從上圖可以看出，每個程序組都為每個 CPU 分配一個可執行佇列，可執行佇列中儲存著可執行的程序和程序組。Linux 排程的時候，就是從上而下（從根程序組開始）地篩選出最優的程序進行執行。

2. 排程過程

當 Linux 需要進行程序排程時，會呼叫 schedule() 函式來完成，其實現如下（經精簡後）：

void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct rq *rq;
    int cpu;
    ...

    rq = cpu_rq(cpu); // 獲取當前CPU的可執行佇列
    ...

    prev->sched_class->put_prev_task(rq, prev); // 把當前執行的程序放回到執行佇列
    next = pick_next_task(rq, prev);            // 從可執行佇列篩選一個最優的可執行的程序

    if (likely(prev != next)) {
        ...
        // 將舊程序切換到新程序
        context_switch(rq, prev, next); /* unlocks the rq */
        ...
    }

    ...
}

schedule() 函式會呼叫 pick_next_task() 函式來篩選最優的可執行程序，我們來看看 pick_next_task() 函式的實現過程：

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 如果所有程序都是使用完全公平排程
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }
    ...
}

從 pick_next_task() 函式的實現來看，其最終會呼叫 完全公平排程演算法 的 pick_next_task() 方法來完成篩選工作，我們來看看這個方法的實現：

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    ...

    do {
        se = pick_next_entity(cfs_rq); // 從可執行佇列中獲取最優的可執行實體

        // 如果最優可執行實體是一個程序組,
        // 那麼將繼續從程序組中獲取到當前CPU對應的可執行佇列
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se); // 最後一定會獲取一個程序
    ...

    return p; // 返回最優可執行程序
}

我們來分析下 pick_next_task_fair() 函式到流程：

從根程序組中篩選出最優的可執行實體（程序或程序組）。
如果篩選出來的實體是程序，那麼直接返回這個程序。
如果篩選出來的實體是程序組，那麼將會繼續對這個程序組中的可執行佇列進行篩選，直至篩選出一個可執行的程序。

怎麼區分 sched_entity 實體是程序或者程序組？ sched_entity 結構中有個 my_q 的欄位，當這個欄位設定為 NULL 時，說明這個實體是一個程序。如果這個欄位指向一個可執行佇列時，說明這個實體是一個程序組。

「其他文章」