圖解|Linux 組調度

語言: CN / TW / HK

在介紹 組調度 前,我們先來重温下什麼是  進程調度

本文基於 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 在調度的時候,首先會根據 完全公平調度算法 從根進程組中篩選出一個最優的進程或者進程組進行調度。

  1. 如果篩選出來的是進程,那麼可以直接把當前運行的進程切換到篩選出來的進程運行即可。

  2. 如果篩選出來的是進程組,那麼就繼續根據  完全公平調度算法 從進程組中篩選出一個最優的進程或者進程組進行調度(重複進行第一步操作),如此類推。

組調度實現

接下來,我們將介紹 組調度 是如何實現的。在分析之前,為了對  完全公平調度算法 有個大體瞭解,建議先看看這篇文章:《 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_groupsched_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() 函數到流程:

  1. 從根進程組中篩選出最優的可運行實體(進程或進程組)。

  2. 如果篩選出來的實體是進程,那麼直接返回這個進程。

  3. 如果篩選出來的實體是進程組,那麼將會繼續對這個進程組中的可運行隊列進行篩選,直至篩選出一個可運行的進程。

怎麼區分 sched_entity 實體是進程或者進程組? sched_entity 結構中有個  my_q 的字段,當這個字段設置為 NULL 時,説明這個實體是一個進程。如果這個字段指向一個可運行隊列時,説明這個實體是一個進程組。