分析Linux內核調度器源碼之初始化

目錄

一、導語(yǔ)

調度器(Scheduler)子系統是內核的核心子系統之一，負責系統內 CPU 資源的合理分配，需要能處理紛繁復雜的不同類(lèi)型任務(wù)的調度需求，還需要能處理各種復雜的并發(fā)競爭環(huán)境，同時(shí)還需要兼顧整體吞吐性能和實(shí)時(shí)性要求(本身是一對矛盾體)，其設計與實(shí)現都極具挑戰。

為了能夠理解 Linux 調度器的設計與實(shí)現，我們將以 Linux kernel 5.4 版本(TencentOS Server3 默認內核版本)為對象，從調度器子系統的初始化代碼開(kāi)始，分析 Linux 內核調度器的設計與實(shí)現。

二、調度器的基本概念

在分析調度器的相關(guān)代碼之前，需要先了解一下調度器涉及的核心數據(結構)以及它們的作用

2.1、運行隊列（rq）

內核會(huì )為每個(gè) CPU 創(chuàng )建一個(gè)運行隊列，系統中的就緒態(tài)(處于 Running 狀態(tài)的)進(jìn)程(task)都會(huì )被組織到內核運行隊列上，然后根據相應的策略，調度運行隊列上的進(jìn)程到 CPU 上執行。

2.2、調度類(lèi)(sched_class)

內核將調度策略（sched_class）進(jìn)行了高度的抽象，形成調度類(lèi)(sched_class)。通過(guò)調度類(lèi)可以將調度器的公共代碼(機制)和具體不同調度類(lèi)提供的調度策略進(jìn)行充分解耦，是典型的 OO(面向對象)的思想。通過(guò)這樣的設計，可以讓內核調度器極具擴展性，開(kāi)發(fā)者通過(guò)很少的代碼(基本不需改動(dòng)公共代碼)就可以增加一個(gè)新的調度類(lèi)，從而實(shí)現一種全新的調度器(類(lèi))，比如，deadline調度類(lèi)就是3.x中新增的，從代碼層面看只是增加了 dl_sched_class 這個(gè)結構體的相關(guān)實(shí)現函數，就很方便的添加了一個(gè)新的實(shí)時(shí)調度類(lèi)型。

目前的5.4內核，有5種調度類(lèi)，優(yōu)先級從高到底分布如下：

stop_sched_class:

優(yōu)先級最高的調度類(lèi)，它與 idle_sched_class 一樣，是一個(gè)專(zhuān)用的調度類(lèi)型（除了 migration 線(xiàn)程之外，其他的 task 都是不能或者說(shuō)不應該被設置為 stop 調度類(lèi)）。該調度類(lèi)專(zhuān)用于實(shí)現類(lèi)似 active balance 或 stop machine 等依賴(lài)于 migration 線(xiàn)程執行的“緊急”任務(wù)。

dl_sched_class:

deadline 調度類(lèi)的優(yōu)先級僅次于 stop 調度類(lèi)，它是一種基于 EDL 算法實(shí)現的實(shí)時(shí)調度器（或者說(shuō)調度策略）。

rt_sched_class:

rt 調度類(lèi)的優(yōu)先級要低于 dl 調度類(lèi)，是一種基于優(yōu)先級實(shí)現的實(shí)時(shí)調度器。

fair_sched_class:

CFS 調度器的優(yōu)先級要低于上面的三個(gè)調度類(lèi)，它是基于公平調度思想而設計的調度類(lèi)型，是 Linux 內核的默認調度類(lèi)。

idle_sched_class:

idle 調度類(lèi)型是 swapper 線(xiàn)程，主要是讓 swapper 線(xiàn)程接管 CPU，通過(guò) cpuidle/nohz 等框架讓 CPU 進(jìn)入節能狀態(tài)。

2.3、調度域(sched_domain)

調度域是在2.6里引入內核的，通過(guò)多級調度域引入，能夠讓調度器更好的適應硬件的物理特性（調度域可以更好的適配 CPU 多級緩存以及 NUMA 物理特性對負載均衡所帶來(lái)的挑戰），實(shí)現更好的調度性能（sched_domain 是為 CFS 調度類(lèi)負載均衡而開(kāi)發(fā)的機制）。

2.4、調度組(sched_group)

調度組是與調度域一起被引入內核的，它會(huì )與調度域一起配合，協(xié)助 CFS 調度器完成多核間的負載均衡。

2.5、根域(root_domain)

根域主要是負責實(shí)時(shí)調度類(lèi)（包括 dl 和 rt 調度類(lèi)）負載均衡而設計的數據結構，協(xié)助 dl 和 rt 調度類(lèi)完成實(shí)時(shí)任務(wù)的合理調度。在沒(méi)有用 isolate 或者 cpuset cgroup 修改調度域的時(shí)候，那么默認情況下所有的CPU都會(huì )處于同一個(gè)根域。

2.6、組調度（group_sched）

為了能夠對系統里的資源進(jìn)行更精細的控制，內核引入了 cgroup 機制來(lái)進(jìn)行資源控制。而 group_sched 就是 cpu cgroup 的底層實(shí)現機制，通過(guò) cpu cgroup 我們可以將一些進(jìn)程設置為一個(gè) cgroup，并且通過(guò) cpu cgroup 的控制接口配置相應的帶寬和 share 等參數，這樣我們就可以按照 group 為單位，對 CPU 資源進(jìn)行精細的控制。

三、調度器初始化(sched_init)

下面進(jìn)入正題，開(kāi)始分析內核調度器的初始化流程，希望能通過(guò)這里的分析，讓大家了解：

1、運行隊列是如何被初始化的

2、組調度是如何與 rq 關(guān)聯(lián)起來(lái)的(只有關(guān)聯(lián)之后才能通過(guò) group_sched 進(jìn)行組調度)

3、CFS 軟中斷 SCHED_SOFTIRQ 注冊

調度初始化(sched_init)

start_kernel

​ |----setup_arch

​ |----build_all_zonelists

​ |----mm_init

​ |----sched_init 調度初始化

調度初始化位于 start_kernel 相對靠后的位置，這個(gè)時(shí)候內存初始化已經(jīng)完成，所以可以看到 sched_init 里面已經(jīng)可以調用 kzmalloc 等內存申請函數了。

sched_init 需要為每個(gè) CPU 初始化運行隊列(rq)、dl/rt 的全局默認帶寬、各個(gè)調度類(lèi)的運行隊列以及 CFS 軟中斷注冊等工作。

接下來(lái)我們看看 sched_init 的具體實(shí)現（省略了部分代碼）：

void __init sched_init(void)
{
    unsigned long ptr = 0;
    int i;
 
    /*
     * 初始化全局默認的rt和dl的CPU帶寬控制數據結構
     *
     * 這里的rt_bandwidth和dl_bandwidth是用來(lái)控制全局的DL和RT的使用帶寬，防止實(shí)時(shí)進(jìn)程
     * CPU使用過(guò)多，從而導致普通的CFS進(jìn)程出現饑餓的情況
     */
    init_rt_bandwidth(&def_rt_bandwidth, global_rt_period(), global_rt_runtime());
    init_dl_bandwidth(&def_dl_bandwidth, global_rt_period(), global_rt_runtime());
 
#ifdef CONFIG_SMP
    /*
     * 初始化默認的根域
     *
     * 根域是dl/rt等實(shí)時(shí)進(jìn)程做全局均衡的重要數據結構，以rt為例
     * root_domain->cpupri 是這個(gè)根域范圍內每個(gè)CPU上運行的RT任務(wù)的最高優(yōu)先級，以及
     * 各個(gè)優(yōu)先級任務(wù)在CPU上的分布情況，通過(guò)cpupri的數據，那么在rt enqueue/dequeue
     * 的時(shí)候，rt調度器就可以根據這個(gè)rt任務(wù)分布情況來(lái)保證高優(yōu)先級的任務(wù)得到優(yōu)先
     * 運行
     */
    init_defrootdomain();
#endif
 
#ifdef CONFIG_RT_GROUP_SCHED
    /*
     * 如果內核支持rt組調度(RT_GROUP_SCHED), 那么對RT任務(wù)的帶寬控制將可以用cgroup
     * 的粒度來(lái)控制每個(gè)group里rt任務(wù)的CPU帶寬使用情況
     *
     * RT_GROUP_SCHED可以讓rt任務(wù)以cpu cgroup的形式來(lái)整體控制帶寬
     * 這樣可以為RT帶寬控制帶來(lái)更大的靈活性(沒(méi)有RT_GROUP_SCHED的時(shí)候，只能控制RT的全局
     * 帶寬使用，不能通過(guò)指定group的形式控制部分RT進(jìn)程帶寬)
     */
    init_rt_bandwidth(&root_task_group.rt_bandwidth,
            global_rt_period(), global_rt_runtime());
#endif /* CONFIG_RT_GROUP_SCHED */
 
    /* 為每個(gè)CPU初始化它的運行隊列 */
    for_each_possible_cpu(i) {
        struct rq *rq;
 
        rq = cpu_rq(i);
        raw_spin_lock_init(&rq->lock);
        /*
         * 初始化rq上cfs/rt/dl的運行隊列
         * 每個(gè)調度類(lèi)型在rq上都有各自的運行隊列，每個(gè)調度類(lèi)都是各自管理自己的進(jìn)程
         * 在pick_next_task()的時(shí)候，內核根據調度類(lèi)優(yōu)先級的順序，從高到底選擇任務(wù)
         * 這樣就保證了高優(yōu)先級調度類(lèi)任務(wù)會(huì )優(yōu)先得到運行
         *
         * stop和idle是特殊的調度類(lèi)型，是為專(zhuān)門(mén)的目的而設計的調度類(lèi)，并不允許用戶(hù)
         * 創(chuàng  )建相應類(lèi)型的進(jìn)程，所以?xún)群艘矝](méi)有在rq里設計對應的運行隊列
         */
        init_cfs_rq(&rq->cfs);
        init_rt_rq(&rq->rt);
        init_dl_rq(&rq->dl);
#ifdef CONFIG_FAIR_GROUP_SCHED
        /*
         * CFS的組調度(group_sched)，可以通過(guò)cpu cgroup來(lái)對CFS進(jìn)行進(jìn)行控制
         * 可以通過(guò)cpu.shares來(lái)提供group之間的CPU比例控制(讓不同的cgroup按照對應
         * 的比例來(lái)分享CPU)，也可以通過(guò)cpu.cfs_quota_us來(lái)進(jìn)行配額設定(與RT的
         * 帶寬控制類(lèi)似)。CFS group_sched帶寬控制是容器實(shí)現的基礎底層技術(shù)之一
         *
         * root_task_group 是默認的根task_group，其他的cpu cgroup都會(huì )以它做為
         * parent或者ancestor。這里的初始化將root_task_group與rq的cfs運行隊列
         * 關(guān)聯(lián)起來(lái)，這里做的很有意思，直接將root_task_group->cfs_rq[cpu] = &rq->cfs
         * 這樣在cpu cgroup根下的進(jìn)程或者cgroup tg的sched_entity會(huì )直接加入到rq->cfs
         * 隊列里，可以減少一層查找開(kāi)銷(xiāo)。
         */
        root_task_group.shares = ROOT_TASK_GROUP_LOAD;
        INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
        rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
        init_cfs_bandwidth(&root_task_group.cfs_bandwidth);
        init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL);
#endif /* CONFIG_FAIR_GROUP_SCHED */
 
        rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
#ifdef CONFIG_RT_GROUP_SCHED
        /* 初始化rq上的rt運行隊列，與上面的CFS的組調度初始化類(lèi)似 */
        init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, NULL);
#endif
 
#ifdef CONFIG_SMP
        /*
         * 這里將rq與默認的def_root_domain進(jìn)行關(guān)聯(lián)，如果是SMP系統，那么后面
         * 在sched_init_smp的時(shí)候，內核會(huì )創(chuàng  )建新的root_domain，然后替換這里
         * def_root_domain
         */
        rq_attach_root(rq, &def_root_domain);
#endif /* CONFIG_SMP */
    }
 
    /*
     * 注冊CFS的SCHED_SOFTIRQ軟中斷服務(wù)函數
     * 這個(gè)軟中斷住要是周期性負載均衡以及nohz idle load balance而準備的
     */
    init_sched_fair_class();
 
    scheduler_running = 1;
}

四、多核調度初始化(sched_init_smp)

start_kernel

​ |----rest_init

​ |----kernel_init

​ |----kernel_init_freeable

​ |----smp_init

​ |----sched_init_smp

​ |---- sched_init_numa

​ |---- sched_init_domains

​ |---- build_sched_domains

多核調度初始化主要是完成調度域/調度組的初始化（當然根域也會(huì )做，但相對而言，根域的初始化會(huì )比較簡(jiǎn)單）。

Linux 是一個(gè)可以跑在多種芯片架構，多種內存架構（UMA/NUMA）上運行的操作系統，所以 Linu x需要能夠適配多種物理結構，所以它的調度域設計與實(shí)現也是相對比較復雜的。

4.1、調度域實(shí)現原理

在講具體的調度域初始化代碼之前，我們需要先了解調度域與物理拓撲結構之間的關(guān)系（因為調度域的設計是與物理拓撲結構息息相關(guān)的，如果不理解物理拓撲結構，那么就沒(méi)有辦法真正理解調度域的實(shí)現）

CPU的物理拓撲圖

我們假設一個(gè)計算機系統(與 intel 芯片類(lèi)似，但縮小 CPU 核心數，以方便表示)：

雙 socket 的計算機系統，每個(gè) socket 都是2核4線(xiàn)程組成，那么這個(gè)計算機系統就應該是一個(gè)4核8線(xiàn)程的 NUMA 系統（上面只是 intel 的物理拓撲結構，而像 AMD ZEN 架構采用了 chiplet 的設計，它在 MC 與 NUMA 域之間會(huì )多一層 DIE 域）。

第一層（SMT 域）：

如上圖的 CORE0，2個(gè)超線(xiàn)程構成了 SMT 域。對于 intel cpu 而言，超線(xiàn)程共享了 L1 與 L2（甚至連 store buffe 都在一定程度上共享），所以 SMT 域之間互相遷移是沒(méi)有任何緩存熱度損失的

第二層（MC 域）：

如上圖 CORE0 與 CORE1，他們位于同一個(gè) SOCKET，屬于 MC 域。對于 intel cpu 而言，他們一般共享 LLC（一般是 L3），在這個(gè)域里進(jìn)程遷移雖然會(huì )失去 L1 與 L2 的熱度，但 L3 的緩存熱度還是可以保持的

第三層（NUMA域）：

如上圖的 SOCKET0 和 SOCKET1，它們之間的進(jìn)程遷移會(huì )導致所有緩存熱度的損失，會(huì )有較大的開(kāi)銷(xiāo)，所以 NUMA 域的遷移需要相對的謹慎。

正是由于這樣的硬件物理特性（不同層級的緩存熱度、NUMA 訪(fǎng)問(wèn)延遲等硬件因素），所以?xún)群顺橄罅?sched_domain 和 sched_group 來(lái)表示這樣的物理特性。在做負載均衡的時(shí)候，根據相應的調度域特性，做不同的調度策略(例如負載均衡的頻率、不平衡的因子以及喚醒選核邏輯等)，從而在CPU 負載與緩存親和性上做更好的平衡。

調度域具體實(shí)現

接下來(lái)我們可以看看內核如何在上面的物理拓撲結構上建立調度域與調度組的

內核會(huì )根據物理拓撲結構建立對應層次的調度域，然后在每層調度域上再建立相應的調度組。調度域在做負載均衡，是在對應層次的調度域里找到負載最重的 busiest sg(sched_group)，然后再判斷 buiest sg 與 local sg（但前 CPU 所在的調度組）的負載是否不均。如果存在負載不均的情況，則會(huì )從 buiest sg 里選擇 buisest cpu，然后進(jìn)行2個(gè) CPU 間的負載平衡。

SMT 域是最底層的調度域，可以看到每個(gè)超線(xiàn)程對就是一個(gè) smt domain。smt domain 里有2個(gè) sched_group，而每個(gè) sched_group 則只會(huì )有一個(gè)CPU。所以 smt 域的負載均衡就是執行超線(xiàn)程間的進(jìn)程遷移，這個(gè)負載均衡的時(shí)間最短，條件最寬松。

而對于不存在超線(xiàn)程的架構（或者說(shuō)芯片沒(méi)有開(kāi)啟超線(xiàn)程），那么最底層域就是MC域(這個(gè)時(shí)候就只有2層域，MC 與 NUMA)。這樣 MC 域里每個(gè) CORE 都是一個(gè) sched_group，內核在調度的時(shí)候也可以很好的適應這樣的場(chǎng)景。

MC 域則是 socket 上 CPU 所有的 CPU 組成，而其中每個(gè) sg 則為上級 smt domain 的所有CPU構成。所以對于上圖而言，MC 的 sg 則由2個(gè) CPU 組成。內核在 MC 域這樣設計，可以讓 CFS 調度類(lèi)在喚醒負載均衡以及空閑負載均衡時(shí)，要求 MC 域的 sg 間需要均衡。

這個(gè)設計對于超線(xiàn)程來(lái)說(shuō)很重要，我們在一些實(shí)際的業(yè)務(wù)里也可以觀(guān)察到這樣的情況。例如，我們有一項編解碼的業(yè)務(wù)，發(fā)現它在某些虛擬機里的測試數據較好，而在某些虛擬機里的測試數據較差。通過(guò)分析后發(fā)現，這是由于是否往虛擬機透傳超線(xiàn)程信息導致的。當我們向虛擬機透傳超線(xiàn)程信息后，虛擬機會(huì )形成2層調度域（SMT 與 MC域），而在喚醒負載均衡的時(shí)候，CFS 會(huì )傾向于將業(yè)務(wù)調度到空閑的 sg 上（即空閑的物理 CORE，而不是空閑的 CPU），這個(gè)時(shí)候業(yè)務(wù)在 CPU 利用率不高（沒(méi)有超過(guò)40%）的時(shí)候，可以更加充分的利用物理CORE的性能（還是老問(wèn)題，一個(gè)物理CORE上的超線(xiàn)程對，它們同時(shí)運行 CPU 消耗型業(yè)務(wù)時(shí)，所獲得的性能增益只相當于單線(xiàn)程1.2倍左右。），從而獲得較好的性能增益。而如果沒(méi)有透傳超線(xiàn)程信息，那么虛擬機只有一層物理拓撲結構(MC域)，那么由于業(yè)務(wù)很可能被調度通過(guò)一個(gè)物理 CORE 的超線(xiàn)程對上，這樣會(huì )導致系統無(wú)法充分利用物理CORE 的性能，從而導致業(yè)務(wù)性能偏低。

NUMA 域則是由系統里的所有 CPU 構成，SOCKET 上的所有 CPU 構成一個(gè) sg，上圖的 NUMA 域由2個(gè) sg 構成。NUMA 的 sg 之間需要有較大的不平衡時(shí)（并且這里的不平衡是 sg 級別的，即要 sg 上所有CPU負載總和與另外一個(gè) sg 不平衡），才能進(jìn)行跨 NUMA 的進(jìn)程遷移（因為跨 NUMA 的遷移會(huì )導致 L1 L2 L3 的所有緩存熱度損失，以及可能引發(fā)更多的跨 NUMA 內存訪(fǎng)問(wèn)，所以需要小心應對）。

從上面的介紹可以看到，通過(guò) sched_domain 與 sched_group 的配合，內核能夠適配各種物理拓撲結構（是否開(kāi)啟超線(xiàn)程、是否開(kāi)啟使用 NUMA），高效的使用 CPU 資源。

smp_init

/*
 * Called by boot processor to activate the rest.
 *
 * 在SMP架構里，BSP需要將其他的非boot cp全部bring up
 */
void __init smp_init(void)
{
    int num_nodes, num_cpus;
    unsigned int cpu;
 
    /* 為每個(gè)CPU創(chuàng  )建其idle thread */
    idle_threads_init();
    /* 向內核注冊cpuhp線(xiàn)程 */
    cpuhp_threads_init();
 
    pr_info("Bringing up secondary CPUs ...\n");
 
    /*
     * FIXME: This should be done in userspace --RR
     *
     * 如果CPU沒(méi)有online，則用cpu_up將其bring up
     */
    for_each_present_cpu(cpu) {
        if (num_online_cpus() >= setup_max_cpus)
            break;
        if (!cpu_online(cpu))
            cpu_up(cpu);
    }
     
    .............
}

在真正開(kāi)始 sched_init_smp 調度域初始化之前，需要先 bring up 所有非 boot cpu，保證這些 CPU 處于 ready 狀態(tài)，然后才能開(kāi)始多核調度域的初始化。

sched_init_smp

那這里我們來(lái)看看多核調度初始化具體的代碼實(shí)現（如果沒(méi)有配置 CONFIG_SMP，那么則不會(huì )執行到這里的相關(guān)實(shí)現）

sched_init_numa

sched_init_numa() 是用來(lái)檢測系統里是否為 NUMA，如果是的則需要動(dòng)態(tài)添加 NUMA 域。

/*
 * Topology list, bottom-up.
 *
 * Linux默認的物理拓撲結構
 *
 * 這里只有三級物理拓撲結構，NUMA域是在sched_init_numa()自動(dòng)檢測的
 * 如果存在NUMA域，則會(huì )添加對應的NUMA調度域
 *
 * 注：這里默認的 default_topology 調度域可能會(huì )存在一些問(wèn)題，例如
 * 有的平臺不存在DIE域(intel平臺)，那么就可能出現LLC與DIE域重疊的情況
 * 所以?xún)群藭?huì )在調度域建立好后，在cpu_attach_domain()里掃描所有調度
 * 如果存在調度重疊的情況，則會(huì )destroy_sched_domain對應的重疊調度域
 */
static struct sched_domain_topology_level default_topology[] = {
#ifdef CONFIG_SCHED_SMT
    { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
#endif
#ifdef CONFIG_SCHED_MC
    { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif
    { cpu_cpu_mask, SD_INIT_NAME(DIE) },
    { NULL, },
};

Linux默認的物理拓撲結構

/*
 * NUMA調度域初始化(根據硬件信息創(chuàng  )建新的sched_domain_topology物理拓撲結構)
 *
 * 內核在默認情況下并不會(huì )主動(dòng)添加NUMA topology，需要根據配置(如果開(kāi)啟了NUMA)
 * 如果開(kāi)啟了NUMA，這里就要根據硬件拓撲信息來(lái)判斷是否需要添加
 * sched_domain_topology_level 域(只有添加了這個(gè)域之后，內核才會(huì )在后面初始化
 * sched_domain的時(shí)候創(chuàng  )建NUMA DOMAIN)
 */
void sched_init_numa(void)
{
    ...................
    /*
     * 這里會(huì )根據distance檢查是否存在NUMA域(甚至存在多級NUMA域)，然后根據
     * 情況將其更新到物理拓撲結構里。后面的建立調度域的時(shí)候，就會(huì )這個(gè)新的
     * 物理拓撲結構來(lái)建立新的調度域
     */
    for (j = 1; j < level; i++, j++) {
        tl[i] = (struct sched_domain_topology_level){
            .mask = sd_numa_mask,
            .sd_flags = cpu_numa_flags,
            .flags = SDTL_OVERLAP,
            .numa_level = j,
            SD_INIT_NAME(NUMA)
        };
    }
 
    sched_domain_topology = tl;
 
    sched_domains_numa_levels = level;
    sched_max_numa_distance = sched_domains_numa_distance[level - 1];
 
    init_numa_topology_type();
}

檢測系統的物理拓撲結構，如果存在 NUMA 域則需要將其加到 sched_domain_topology 里，后面就會(huì )根據 sched_domain_topology 這個(gè)物理拓撲結構來(lái)建立相應的調度域。

sched_init_domains

下面接著(zhù)分析 sched_init_domains 這個(gè)調度域建立函數

/*
 * Set up scheduler domains and groups.  For now this just excludes isolated
 * CPUs, but could be used to exclude other special cases in the future.
 */
int sched_init_domains(const struct cpumask *cpu_map)
{
    int err;
 
    zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
    zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
    zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
 
    arch_update_cpu_topology();
    ndoms_cur = 1;
    doms_cur = alloc_sched_domains(ndoms_cur);
    if (!doms_cur)
        doms_cur = &fallback_doms;
    /*
     * doms_cur[0] 表示調度域需要覆蓋的cpumask
     *
     * 如果系統里用isolcpus=對某些CPU進(jìn)行了隔離，那么這些CPU是不會(huì )加入到調度
     * 域里面，即這些CPU不會(huì )參于到負載均衡(這里的負載均衡包括DL/RT以及CFS)。
     * 這里用 cpu_map & housekeeping_cpumask(HK_FLAG_DOMAIN) 的方式將isolate
     * cpu去除掉，從而在保證建立的調度域里不包含isolate cpu
     */
    cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN));
    /* 調度域建立的實(shí)現函數 */
    err = build_sched_domains(doms_cur[0], NULL);
    register_sched_domain_sysctl();
 
    return err;
}

/*
 * Build sched domains for a given set of CPUs and attach the sched domains
 * to the individual CPUs
 */
static int
build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
{
    enum s_alloc alloc_state = sa_none;
    struct sched_domain *sd;
    struct s_data d;
    struct rq *rq = NULL;
    int i, ret = -ENOMEM;
    struct sched_domain_topology_level *tl_asym;
    bool has_asym = false;
 
    if (WARN_ON(cpumask_empty(cpu_map)))
        goto error;
 
    /*
     * Linux里的絕大部分進(jìn)程都為CFS調度類(lèi)，所以CFS里的sched_domain將會(huì )被頻繁
     * 的訪(fǎng)問(wèn)與修改(例如nohz_idle以及sched_domain里的各種統計)，所以sched_domain
     * 的設計需要優(yōu)先考慮到效率問(wèn)題，于是內核采用了percpu的方式來(lái)實(shí)現sched_domain
     * CPU間的每級sd都是獨立申請的percpu變量，這樣可以利用percpu的特性解決它們
     * 間的并發(fā)競爭問(wèn)題(1、不需要鎖保護 2、沒(méi)有cachline偽共享)
     */
    alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
    if (alloc_state != sa_rootdomain)
        goto error;
 
    tl_asym = asym_cpu_capacity_level(cpu_map);
 
    /*
     * Set up domains for CPUs specified by the cpu_map:
     *
     * 這里會(huì )遍歷cpu_map里所有CPU，為這些CPU創(chuàng  )建與物理拓撲結構對應(
     * for_each_sd_topology)的多級調度域。
     *
     * 在調度域建立的時(shí)候，會(huì )通過(guò)tl->mask(cpu)獲得cpu在該級調度域對應
     * 的span(即cpu與其他對應的cpu組成了這個(gè)調度域)，在同一個(gè)調度域里
     * 的CPU對應的sd在剛開(kāi)始的時(shí)候會(huì )被初始化成一樣的(包括sd->pan、
     * sd->imbalance_pct以及sd->flags等參數)。
     */
    for_each_cpu(i, cpu_map) {
        struct sched_domain_topology_level *tl;
 
        sd = NULL;
        for_each_sd_topology(tl) {
            int dflags = 0;
 
            if (tl == tl_asym) {
                dflags |= SD_ASYM_CPUCAPACITY;
                has_asym = true;
            }
 
            sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);
 
            if (tl == sched_domain_topology)
                *per_cpu_ptr(d.sd, i) = sd;
            if (tl->flags & SDTL_OVERLAP)
                sd->flags |= SD_OVERLAP;
            if (cpumask_equal(cpu_map, sched_domain_span(sd)))
                break;
        }
    }
 
    /*
     * Build the groups for the domains
     *
     * 創(chuàng  )建調度組
     *
     * 我們可以從2個(gè)調度域的實(shí)現看到sched_group的作用
     * 1、NUMA域 2、LLC域
     *
     * numa sched_domain->span會(huì )包含NUMA域上所有的CPU，當需要進(jìn)行均衡的時(shí)候
     * NUMA域不應該以cpu為單位，而是應該以socket為單位，即只有socket1與socket2
     * 極度不平衡的時(shí)候才在這兩個(gè)SOCKET間遷移CPU。如果用sched_domain來(lái)實(shí)現這個(gè)
     * 抽象則會(huì )導致靈活性不夠(后面的MC域可以看到)，所以?xún)群藭?huì )以sched_group來(lái)
     * 表示一個(gè)cpu集合，每個(gè)socket屬于一個(gè)sched_group。當這兩個(gè)sched_group不平衡
     * 的時(shí)候才會(huì )允許遷移
     *
     * MC域也是類(lèi)似的，CPU可能是超線(xiàn)程，而超線(xiàn)程的性能與物理核不是對等的。一對
     * 超線(xiàn)程大概等于1.2倍于物理核的性能。所以在調度的時(shí)候，我們需要考慮超線(xiàn)程
     * 對之間的均衡性，即先要滿(mǎn)足CPU間均衡，然后才是CPU內的超線(xiàn)程均衡。這個(gè)時(shí)候
     * 用sched_group來(lái)做抽象，一個(gè)sched_group表示一個(gè)物理CPU(2個(gè)超線(xiàn)程)，這個(gè)時(shí)候
     * LLC保證CPU間的均衡，從而避免一種極端情況：超線(xiàn)程間均衡，但是物理核上不均衡
     * 的情況，同時(shí)可以保證調度選核的時(shí)候，內核會(huì )優(yōu)先實(shí)現物理線(xiàn)程，只有物理線(xiàn)程
     * 用完之后再考慮使用另外的超線(xiàn)程，讓系統可以更充分的利用CPU算力
     */
    for_each_cpu(i, cpu_map) {
        for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
            sd->span_weight = cpumask_weight(sched_domain_span(sd));
            if (sd->flags & SD_OVERLAP) {
                if (build_overlap_sched_groups(sd, i))
                    goto error;
            } else {
                if (build_sched_groups(sd, i))
                    goto error;
            }
        }
    }
 
    /*
     * Calculate CPU capacity for physical packages and nodes
     *
     * sched_group_capacity 是用來(lái)表示sg可使用的CPU算力
     *
     * sched_group_capacity 是考慮了每個(gè)CPU本身的算力不同(最高主頻設置不同、
     * ARM的大小核等等)、去除掉RT進(jìn)程所使用的CPU(sg是為CFS準備的，所以需要
     * 去掉CPU上DL/RT進(jìn)程等所使用的CPU算力)等因素之后，留給CFS sg的可用算力(因為
     * 在負載均衡的時(shí)候，不僅應該考慮到CPU上的負載，還應該考慮這個(gè)sg上的CFS
     * 可用算力。如果這個(gè)sg上進(jìn)程較少，但是sched_group_capacity也較小，也是
     * 不應該遷移進(jìn)程到這個(gè)sg上的)
     */
    for (i = nr_cpumask_bits-1; i >= 0; i--) {
        if (!cpumask_test_cpu(i, cpu_map))
            continue;
 
        for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
            claim_allocations(i, sd);
            init_sched_groups_capacity(i, sd);
        }
    }
 
    /* Attach the domains */
    rcu_read_lock();
    /*
     * 將每個(gè)CPU的rq與rd(root_domain)進(jìn)行綁定，并且會(huì )檢查sd是否有重疊
     * 如果是的則需要用destroy_sched_domain()將其去掉(所以我們可以看到
     * intel的服務(wù)器是只有3層調度域，DIE域其實(shí)與LLC域重疊了，所以在這里
     * 會(huì )被去掉)
     */
    for_each_cpu(i, cpu_map) {
        rq = cpu_rq(i);
        sd = *per_cpu_ptr(d.sd, i);
 
        /* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */
        if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity))
            WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig);
 
        cpu_attach_domain(sd, d.rd, i);
    }
    rcu_read_unlock();
 
    if (has_asym)
        static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
 
    if (rq && sched_debug_enabled) {
        pr_info("root domain span: %*pbl (max cpu_capacity = %lu)\n",
            cpumask_pr_args(cpu_map), rq->rd->max_cpu_capacity);
    }
 
    ret = 0;
error:
    __free_domain_allocs(&d, alloc_state, cpu_map);
 
    return ret;
}

到目前為止，我們已經(jīng)將內核的調度域構建起來(lái)了，CFS 可以利用 sched_domain 來(lái)完成多核間的負載均衡了。

五、結語(yǔ)

本文主要介紹了內核調度器的基本概念，并通過(guò)分析5.4內核中調度器的初始化代碼，介紹了調度域、調度組等基本概念的具體落地方式。整體上，5.4內核相比3.x內核，在調度器初始化邏輯，以及調度器相關(guān)的基本設計(概念/關(guān)鍵結構)上沒(méi)有本質(zhì)的變化，也從側面印證了內核調度器設計的“穩定”和“優(yōu)雅”。

以上就是分析Linux內核調度器源碼之初始化的詳細內容，更多關(guān)于Linux內核調度器源碼 初始化的資料請關(guān)注腳本之家其它相關(guān)文章！