前言

我們描述CFS任務負載均衡的系列文章一共三篇，第一篇是框架部分，第二篇描述了task placement的邏輯過程，第三篇是負載均衡的情景分析，包括tick balance、nohz idle balance和new idle balance。之前已經(jīng)有一篇關于task placement的文檔發(fā)表在本站，為了更精細的講解代碼邏輯，我們這次增加了代碼分析部分。本文作為第二篇任務放置的附篇，深入講解task placement的代碼流程。

本文出現(xiàn)的內(nèi)核代碼來自Linux5.10.61，為了減少篇幅，我們對引用的代碼進行了刪減（例如去掉了NUMA的代碼，畢竟手機平臺上我們暫時不關注這個特性），如果有興趣，讀者可以配合完整的源代碼代碼閱讀本文。

任務放置負載均衡框架

linux內(nèi)核的調(diào)度框架是高度抽象、模塊化的，所有的任務都擁有各自所屬的調(diào)度類（sched class），實時調(diào)度類是rt_sched_class，CFS調(diào)度類是fair_sched_class，不同的調(diào)度類采用不同的調(diào)度策略。上面提到的task placement的三種場景，最終的函數(shù)入口都是core.c中定義的select_task_rq()方法，之后會跳轉至調(diào)度類自己的具體實現(xiàn)。本文以CFS調(diào)度類為分析對象，因為該調(diào)度類的任務在整個系統(tǒng)中占據(jù)較大的比重。

一、能量模型框架及其相關數(shù)據(jù)結構

1、概述

在嵌入式平臺上，為了控制功耗，很多硬件模塊被設計成可以運行在多種頻率下工作（配合對應的電壓，形成不同的performance level），這種硬件的驅動模塊可以感知到在不同performance level下的能耗。系統(tǒng)中的某些模塊可能會希望能感知到硬件能耗從而做出不同的判決。能量模型框架（Energy Model (EM) framework）是一個通用的接口模塊，該接口連接了支持不同perf level的驅動模塊和系統(tǒng)中的其他想要感知能量消耗的模塊。

一個典型的例子就是CPU調(diào)度器和CPU驅動模塊，調(diào)度器希望能夠感知底層CPU能量的消耗，從而做出更優(yōu)的選核策略。對于CPU設備，各個cluster有各自獨立的調(diào)頻機制，cluster內(nèi)的CPU統(tǒng)一工作在一個頻率下。因此每個cluster就會形成一個性能域（performance domain）。調(diào)度器通過EM framework接口可以獲取CPU在各個performance level的能量消耗。在了解了能量模型的基本概念之后，我們一起來看看和調(diào)度器相關的EM數(shù)據(jù)結構。

2、struct root_domain

最初引入root domain的概念是因為rt調(diào)度的問題。對于cfs task，我們只要保證每一個cpu runqueue上的公平就OK了（load balancer也會盡量cpu之間的公平），不需要嚴格保證全局公平。但是對于rt task就不行了，我們必須保證從全局范圍看，優(yōu)先級最高的任務最優(yōu)先得到調(diào)度。然而這樣會引入擴展性問題：隨著cpu core數(shù)據(jù)增大，維持全局的rt調(diào)度策略有些困難，這樣的情況下，我們把CPU分成一個個的區(qū)域，每一個區(qū)域對應一個root domain。對于rt調(diào)度，我們不需要維持全局，只要保證一個root domain中，最高優(yōu)先級的rt任務最優(yōu)先得到調(diào)度即可。當然，后來更多的成員增加到這個數(shù)據(jù)結構中（例如本文要描述的performance domain），豐富了它的含義。在手機平臺上，我們只有一個root domain，有點類似整個系統(tǒng)的味道了。本文只描述和任務放置相關的成員，具體如下：

成員	描述
int overload	該root domain是否處于overload狀態(tài)
int overutilized	該root domain是否處于overutilized狀態(tài)
unsigned long max_cpu_capacity;	該root domain內(nèi)CPU的最大算力
struct perf_domain __rcu *pd	該root domain的perf domain鏈表。通過cpu的runqueue我們可以獲取該cpu對應的root domain，從而可以獲取到整個root domain的性能域鏈表。

這里需要澄清一下overload和overutilized這兩個概念，對于一個CPU而言，其處于overload狀態(tài)則說明其runqueue上有大于等于2個任務，或者雖然只有一個任務，但是是misfit task。對于一個CPU而言，其處于overutilized狀態(tài)說明：該cpu的utility超過其capacity（缺省預留20%的算力，另外，這里的capacity是用于cfs任務的算力）。

在單個cpu overload/overutilized基礎上，我們定義root domain（即整個系統(tǒng)）的overload和overutilized。對于root domain，overload表示至少有一個cpu處于overload狀態(tài)。overutilized表示至少有一個cpu處于overutilized狀態(tài)。overutilized狀態(tài)非常重要，它決定了調(diào)度器是否啟用EAS，只有在系統(tǒng)沒有overutilized的情況下，EAS才會生效。Overload和newidle balance的頻次控制相關，當系統(tǒng)在overload的情況下，newidle balance才會啟動進行均衡。

在CPU拓撲初始化的時候，通過build_perf_domains函數(shù)創(chuàng)建各個perf domain，形成root domain的perf domain鏈表。

3、struct perf_domain

Struct perf_comain表示一個CPU性能域，perf_comain和cpufreq policy是一一對應的，對于一個4+3+1結構的平臺，每一個性能域都是由perf_domain抽象，因此系統(tǒng)共計3個perf domain，形成鏈表，鏈表頭在root domain。Perf_domain的各個成員如下：

成員	描述
struct em_perf_domain *em_pd	EM performance domain
struct perf_domain *next	系統(tǒng)中的perf domain會形成鏈表，這里指向下一個perf domain
struct rcu_head rcu	保護perf domain list的rcu

4、struct em_perf_domain

在EM framework中，我們使用em_perf_domain來抽象一個performance domain：

成員	描述
struct em_perf_state *table	perf states表，記錄了各個performance level的頻率、能耗信息。
int nr_perf_states	該perf domain支持多少個perf states，即上面perf states表格的條目數(shù)
unsigned long cpus[]	該性能域包括哪些cpu？

5、struct em_perf_state

每個性能域都有若干個perf level，每一個perf level對應能耗是不同的，我們用struct em_perf_state來表示一個perf level下的能耗信息：

成員	描述
unsigned long frequency	該perf level對應的運行頻率，單位是KHz
unsigned long power	該perf level對應的功率
unsigned long cost	為了方便能量運算的一個中間參數(shù)，等于power * max_frequency / frequency，下一章會詳細解釋

二、能量計算概述

我們都知道一個基本的能量計算公式，如下：

能量 = 功率 x 時間

對于CPU而言，我們要計算其能量需要進一步細化公式（省略了CPU處于idle狀態(tài)的能耗）：

CPU的能量消耗 = CPU運行頻率對應的功率 x CPU在該頻點運行時間

在內(nèi)核中，EM中記錄了CPU各個頻點的功率，而運行時間是通過cpu utility來呈現(xiàn)的。有一個不太方便的地方就是CPU utility是歸一化到1024的一個值，失去了在某個頻點的運行時間長度的信息，不過沒有關系，我們可以轉換：

CPU在該頻點運行時間 = cpu utility / cpu current capacity

CPU在某個perf state的算力如下：

不考慮idle state的功耗，Cpu在某個perf state的能量估計如下：

把公式（1）帶入公式（2）可以得到：

三、Task placement概述

1、喚醒場景的Task placement

一個線程進入阻塞狀態(tài)后，異步事件或者其他線程會調(diào)用try_to_wake_up函數(shù)喚醒該線程，這時候會引發(fā)一次喚醒場景的task placement，在手機平臺上任務放置大概的選核思路如下：

（1）如果使能了EAS，那么優(yōu)先采用EAS選核。當然，只有在輕載（系統(tǒng)沒有overutilized）才會啟用EAS，重載下（只要有一個cpu處于over utilized狀態(tài)）還是使用傳統(tǒng)內(nèi)核算法

（2）Wake affine場景下的Non-EAS選核。所謂Wake affine就是選擇靠近waker所在的cpu（具體靠近的含義是waker所在CPU的LLC domain范圍），當然也有可能靠近prev cpu？在this cpu和prev cpu中選定一個目標CPU之后，走快速路徑，在目標cpu的LLC domain選擇一個空閑的CPU。

（3）Non-wake affine場景下的Non-EAS選核。走快速路徑，在prev cpu的LLC domain選擇一個空閑的CPU。

一般而言Non-wake affine場景下的Non-EAS選核是要走慢速路徑的，但是在手機平臺，所有的各個level的sched domain都沒有設定SD_BALANCE_WAKE的標記，因此我們無法確定wakeup均衡的范圍，因此走快速路徑。

2、Fork和exec場景的Task placement

對fork后新任務的喚醒，內(nèi)核不是用try_to_wake_up來處理，而是用了wake_up_new_task。這個函數(shù)會調(diào)用fork類型的選核函數(shù)完成任務放置。當新任務調(diào)用exec類函數(shù)開啟自己新的旅程之后，內(nèi)核會調(diào)用sched_exec啟動一次exec類型的placement。這兩種類型的placement選核思路類似：

（1）對于fork場景，找到最高level且支持SD_BALANCE_FORK的sched domain（即找到fork均衡的范圍），走慢速路徑來進行選核

（2）對于exec場景，找到最高level且支持SD_BALANCE_EXEC的sched domain（即找到exec均衡的范圍），走慢速路徑來進行選核

四、select_task_rq_fair函數(shù)代碼分析

if (sd_flag & SD_BALANCE_WAKE) {-----------A
    record_wakee(p);----------B
    if (sched_energy_enabled()) {-----------C
        new_cpu = find_energy_efficient_cpu(p, prev_cpu);
        if (new_cpu >= 0)
            return new_cpu;---------D
        new_cpu = prev_cpu;
    }
    want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, p->cpus_ptr);----E
}

A、對喚醒路徑（通過try_to_wake_up進入該函數(shù)）進行特別的處理，主要包括兩部分內(nèi)容，一是對wake affine的處理（B和E），另外一個是EAS的選核。由此可見，EAS只用于wakeup，fork和exec均衡固定走傳統(tǒng)選核算法。

B、更新current task（waker）的wakee信息，關于wake affine后面會詳細描述。

C、find_energy_efficient_cpu是EAS的主選核路徑，使用EAS選核需要滿足兩個條件：喚醒路徑且enable了energy aware scheduler特性。具體EAS的選核邏輯后面會詳細描述

D、EAS選中了適合的CPU就直接返回。如果EAS選核不成功，那么恢復缺省cpu為prev cpu，走傳統(tǒng)選核路徑。

E、判斷本次喚醒是否想要wake affine（即wakee task靠近waker所在的cpu）。

如果EAS選中了適合的CPU，那么就直接返回了，不需要進行sched domain/cpu的選擇了。如果不需要EAS選核，或者EAS沒有選擇到合適的CPU，那么就需要走傳統(tǒng)的快速或者慢速路徑的選核了，具體走那條路主要是第二段代碼邏輯中是否找到了適合的sched domain。第二段尋找sched domain的代碼如下：

for_each_domain(cpu, tmp) {---------A
    if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
      cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {----------B
        if (cpu != prev_cpu)
            new_cpu = wake_affine(tmp, p, cpu, prev_cpu, sync);
        sd = NULL; /* Prefer wake_affine over balance flags */
        break;
    }
    if (tmp->flags & sd_flag)-------C
        sd = tmp;
    else if (!want_affine)
        break;
}

A、從當前cpu（waker所在的cpu）所在的base sched domain，自下而上，尋找合適的sched domain，從而確定任務放置的范圍。

B、對于wake affine場景，我們需要自下而上遍歷sd找到一個符合要求的sched domain，它必須要滿足：（1）該sched domain支持wake affine，（2）該sched domain包括了prev cpu和當前cpu（即waker所在的cpu）。找到這樣的sched domain之后，我們需要調(diào)用wake_affine快速的在當前cpu和prev cpu中選中其一（如果當前cpu就是prev cpu，那么不需要通過wake_affine選擇了，直接prev cpu即可），作為后續(xù)選核快速路徑的輸入（sd==NULL確保走快速路徑）。

C、對于non wake affine場景，我們一樣也是需要自下而上遍歷sd找到最頂層且支持該sd flag的sched domain。目前手機平臺上，DIE domain和MC domain都沒有設定SD_BALANCE_WAKE，因此在喚醒場景，我們無法找到sched domain，從而走入快速路徑。對于SD_BALANCE_FORK和SD_BALANCE_EXEC場景，DIE domain和MC domain都設置了對應的flag，因此遍歷搜索到了DIE domain，后續(xù)會走入慢速路徑。

至此，我們應該選中了一個sched domain，給后續(xù)的placement定義了一個范圍。當然，也有可能sd等于NULL，表示是快速路徑，直接從LLC doamin選核。第三段代碼邏輯如下：

if (unlikely(sd)) {/* Slow path */--------A
    new_cpu = find_idlest_cpu(sd, p, cpu, prev_cpu, sd_flag);
} else if (sd_flag & SD_BALANCE_WAKE) {/* Fast path */ ---------B
    new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
    if (want_affine)
        current->recent_used_cpu = cpu;
}

A、慢速選核路徑，需要在選定的sched domain中尋找最空閑的group，然后在最空閑的group中選擇最空閑的cpu。然后繼續(xù)在下層sched domain重復上面的過程，最終選擇一個空閑CPU并把任務p放置在這個最空閑的CPU上。

B、快速選核路徑，主要是在LLC domain中選擇距離new_cpu比較近的空閑CPU。對于wake affine，這里的new_cpu就是wake_affine選定的target cpu，對于其他場景new_cpu就是prev cpu。

五、EAS選核

find_energy_efficient_cpu函數(shù)用來為被喚醒的任務找到一個能效比最高的目標CPU。主要搜索的步驟如下：

1、在每一個cluster（performance domain）中找到空閑算力最多的cpu作為備選

2、從備選cpu中通過能量模型找到消耗能量最小的cpu。

這個算法思路也比較簡單，在一個cluster中，選擇一個空閑算力最大cpu放置任務會讓schedutil governor請求較低的CPU頻率，從而消耗較低的能量。在實際中，從能量的角度看，把小任務擠壓到一個CPU core上可以有助于讓其他CPU core進入更深的idle狀態(tài)，但是這樣會讓cluster進入idle的機會大大降低。因此，實際上從能量模型上，我們并不能說明這樣的小任務擠壓的策略是好的還是壞的。因此，find_energy_efficient_cpu函數(shù)還是選擇把任務擠壓在一個cluster內(nèi)，然后在選中的cluster之中，盡量把任務散布到各個cpu上。這樣的策略對延遲而言肯定是好事情。這種策略也和“只有異構系統(tǒng)中的EAS才能帶來的能量節(jié)省”是一致的。這也是為什么我們只在SD_ASYM_CPUCAPACITY的系統(tǒng)中打開EAS的原因。

在fork場景，被fork出來的任務到底放置在哪個CPU并不采用EAS算法，因為它不知道自己的util數(shù)據(jù)，也不太能夠預測出能量的消耗。因此，對fork出來的任務仍然使用慢速路徑（find_idlest_cpu函數(shù)）找到最空閑的group/cpu并將其放置在該cpu上執(zhí)行，在有些用戶場景下，這種方法可能是恰好命中能效比最高的CPU，但未必總是如此。另一種可能的方法是先將新fork出來的任務放置在特定類型的cpu（例如小核），或者嘗試從父任務推斷它們的util_avg，但是這種placement策略也可能損害其他用戶場景。在沒有找到其他更好的方法之前，我們?nèi)匀徊捎脗鹘y(tǒng)的慢速路徑的方式來選核。Exec場景和fork場景類似，不再贅述。

Overutilized主要用來切換EAS調(diào)度器還是傳統(tǒng)調(diào)度器。如果系統(tǒng)處于overutilized的狀態(tài)，那么不再執(zhí)行EAS的task placement的邏輯，如下

struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
rcu_read_lock();
pd = rcu_dereference(rd->pd);
if (!pd || READ_ONCE(rd->overutilized))
    goto fail;

EAS的選核邏輯是先確定一個sched domain，然后從sched domain中選擇一個能效比高的CPU，具體選擇sched domain的方式如下：

sd = rcu_dereference(*this_cpu_ptr(&sd_asym_cpucapacity));
while (sd && !cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
    sd = sd->parent;

從最低level的，并且包括不同算力CPU的domain開始向上搜索，直到該domain覆蓋了this cpu和prev cpu為止。對于手機平臺一般找到的就是Die domain。之所以要求包括異構CPU的domain是因為同構的cpu不需要EAS，不會有功耗的節(jié)省。

因為后面需要任務p的utility參與計算（估計調(diào)頻點和能耗），而該任務在被喚醒之前應該已經(jīng)阻塞了一段時間，它的utility還停留在阻塞前那一點，因此這里需要進行負載更新：

sync_entity_load_avg(&p->se);
if (!task_util_est(p))
    goto unlock;

sync_entity_load_avg函數(shù)用來更新該任務的sched avg，由于任務p從睡眠中被喚醒，因此同步也就是衰減其負載。具體是衰減到其掛入的cfs rq的最近的負載更新時間點（而不是當前時間點）。注意：這里的cfs rq是任務p阻塞之前掛入的隊列。如果任務的utility等于0那么通過能量模型對其進行運算是沒有意義的，所以直接退出。

EAS最核心的代碼如下：

for (; pd; pd = pd->next) {
    base_energy_pd = compute_energy(p, -1, pd);-----A
    base_energy += base_energy_pd;
    for_each_cpu_and(cpu, perf_domain_span(pd), sched_domain_span(sd)) {
        util = cpu_util_next(cpu, p, cpu);-------------B
        cpu_cap = capacity_of(cpu);
        spare_cap = cpu_cap;
        lsub_positive(&spare_cap, util);
        util = uclamp_rq_util_with(cpu_rq(cpu), util, p);
        if (!fits_capacity(util, cpu_cap))---------------C
            continue;
        if (cpu == prev_cpu) {----------------------D
            prev_delta = compute_energy(p, prev_cpu, pd);
            prev_delta -= base_energy_pd;
            best_delta = min(best_delta, prev_delta);
        }

        if (spare_cap > max_spare_cap) {--------E
            max_spare_cap = spare_cap;
            max_spare_cap_cpu = cpu;
        }
    }

    if (max_spare_cap_cpu >= 0 && max_spare_cap_cpu != prev_cpu) {------F
        cur_delta = compute_energy(p, max_spare_cap_cpu, pd);
        cur_delta -= base_energy_pd;
        if (cur_delta < best_delta) {
            best_delta = cur_delta;
            best_energy_cpu = max_spare_cap_cpu;
        }
    }
}

A、計算本performance domain的基礎能量消耗，即未放置任務p的能耗（base_energy_pd）。同時這里會累計各個pd的能耗（base_energy），也就是整個cpu系統(tǒng)消耗的能量。

B、遍歷該pd的各個cpu，計算各個cpu的剩余算力。這里的剩余算力是這樣計算的：獲取該cpu用于cfs task的算力（即原始算力去掉rt irq等消耗的算力），減去該cpu的util（即cfs task的總的utility）。這里的cpu util是把任務p放置在該cpu的預估utility（cpu_util_next）。

C、本身EAS就是在系統(tǒng)沒有overutilized的情況下才啟用的，如果任務p放置該CPU導致該cpu進入overutilized，那么就跳過該CPU。當然，這里的cpu util是經(jīng)過uclamp修正之后的util。上面步驟B中是估計cpu的空閑算力，需要真實的util，所以沒有經(jīng)過uclamp修正。

D、Prev cpu永遠是備選對象，因此這里計算任務p放置在prev cpu上帶來的能耗增量，并且參與到能耗最優(yōu)的對比中。

E、尋找該perf domain中，空閑算力最大的那個CPU，這個cpu也是備選對象之一。

F、對比各個perf domain中選擇的最佳CPU（剩余空閑算力最大）的能耗，選擇一個最小的CPU，賦值給best_energy_cpu。

在EAS選核最后，選出的best_energy_cpu還要和prev cpu進行PK，畢竟prev cpu有可能帶來潛在的性能收益（提高cache命中率），只有當best_energy_cpu相對prev cpu能耗收益大于CPU總耗能的1/16，才選擇best_energy_cpu，否則還是運行在prev cpu上。

六、能量計算

compute_energy函數(shù)原型如下：

static long compute_energy(struct task_struct *p, int dst_cpu, struct perf_domain *pd)

該函數(shù)主要用來計算當任務p放置到dst_cpu的時候，pd所在的perf domain會消耗多少能量。任務p放置到dst cpu的時候，這會影響pd所在的perf domain中各個CPU的utility，進而會驅動cpufreq進行頻率調(diào)整。計算能量的時候，我們必須預測可能的調(diào)頻，并通過這些utility可以估計該perf domain的能耗（任務放置在dst cpu之后）。詳細的代碼邏輯如下：

for_each_cpu_and(cpu, pd_mask, cpu_online_mask) {
    unsigned long cpu_util, util_cfs = cpu_util_next(cpu, p, dst_cpu);---------A
    struct task_struct *tsk = cpu == dst_cpu ? p : NULL;
    sum_util += schedutil_cpu_util(cpu, util_cfs, cpu_cap,
       ENERGY_UTIL, NULL);--------------B
    cpu_util = schedutil_cpu_util(cpu, util_cfs, cpu_cap,
      FREQUENCY_UTIL, tsk);-----------C
    max_util = max(max_util, cpu_util);---------------D
}
return em_cpu_energy(pd->em_pd, max_util, sum_util);-----E

整個能量計算分成兩個部分，首先遍歷perf domain上的cpu，累計整個perf domain中的cpu utility總和。此外，還要記錄最大cpu utility（推測運行頻率）。完成sum_util和max_util之后調(diào)用em_cpu_energy即可。

A、遍歷perf domain上的cpu，通過cpu_util_next計算任務p放置在dst cpu之后，各個cpu上的cfs任務的utility

B、在步驟A中僅僅得到了cfs任務的utility，通過schedutil_cpu_util得到該cpu的utility（累計rt、dl、irq等的util）并累計起來。這里的util是用來計算能量的，因此返回的util要等于真實CPU busy time，不需要uclamp的處理。遍歷perf domain上的所有CPU就得到其上的util總和，用于能量計算。

C、計算該CPU的調(diào)頻util。這里是調(diào)頻需要的util，需要進行utility clamp處理。

D、找到該perf domain中最大的cpu util。

E、調(diào)用em_cpu_energy函數(shù)進行該perf domain的耗能估計。Max_util用來估計該perf domain潛在運行的頻點，sum_util表示該perf domain的總運行時間。具體的運算非常簡單，在第三章已經(jīng)給出，不再贅述。

七、Wake affine

task_struct中有三個成員用來記錄被喚醒線程（wakee）的信息，如下：

成員	描述
unsigned int wakee_flips	該線程喚醒不同wakee的次數(shù)。wakee_flips數(shù)值較大，則說明該該線程喚醒多個不同的任務。并且數(shù)值越大，說明喚醒的頻率越快
unsigned long wakee_flip_decay_ts	wakee_flips會隨時間衰減，這里定義了上次進行衰減的時間點
struct task_struct *last_wakee	該線程上次喚醒的線程

每次waker喚醒wakee的時候都會調(diào)用record_wakee來更新上面的成員，具體代碼如下：

if (time_after(jiffies, current->wakee_flip_decay_ts + HZ)) {-------A
    current->wakee_flips >>= 1;
    current->wakee_flip_decay_ts = jiffies;
}

if (current->last_wakee != p) {------B
    current->last_wakee = p;
    current->wakee_flips++;
}

A、每隔一秒對wakee_flips進行衰減。如果一個線程能夠經(jīng)常的喚醒不同的其他線程，那么該線程的wakee_flips會保持在一個較高的值。相反，如果僅僅是偶爾喚醒一次其他線程，和某個固定的線程有喚醒關系，那么這里的wakee_flips應該會趨向0

B、如果上次喚醒的不是p，那么要切換wakee，并累加wakee翻轉次數(shù)

Waker喚醒wakee的場景中，有兩種placement思路：一種是聚合的思路，即讓waker和wakee盡量的close，從而提高cache hit。另外一種思考是分散，即讓load盡量平均分配在多個cpu上。不同的喚醒模型使用不同的放置策略。我們來看看下面兩種簡單的喚醒模型：

（1）在1：N模型中，一個server會不斷的喚醒多個不同的client

（2）1：1模型，線程A和線程B不斷的喚醒對方

在1：N模型中，如果N是一個較大的數(shù)值，那么讓waker和wakee盡量的close會導致負荷的極度不平均，這會讓waker所在的sched domain會承擔太多的task，從而引起性能下降。在1：1模型中，讓waker和wakee盡量的close不存在這樣的問題，同時還能提高性能。但是，實際的程序中，喚醒關系可能沒有那么簡單，一個wakee可能是另外一個關系中的waker，交互可能是M：N的形式?？紤]這樣一個場景：waker把wakee拉近，而wakee自身的wakee flips比較大，那么更多的線程也會拉近waker所在的sched domain，從而進一步加劇CPU資源的競爭。因此waker和wakee的wakee flips的數(shù)值都不能太大，太大的時候應該禁止wake affine。內(nèi)核中通過wake_wide來判斷是否使能wake affine：

unsigned int master = current->wakee_flips;---------A
unsigned int slave = p->wakee_flips;
int factor = __this_cpu_read(sd_llc_size);-------------B
if (master < slave)
    swap(master, slave);-------------C
if (slave < factor || master < slave * factor)--------D
    return 0;------waker和wakee需要靠近
return 1;

A、這里的場景是current task喚醒任務p的場景，master是current喚醒不同線程的次數(shù)，slave是被喚醒的任務p喚醒不同線程的次數(shù)。

B、Wake affine場景下任務放置要走快速路徑，即在LLC上選擇空閑的CPU。sd_llc_size是LLC domain上CPU的個數(shù)。Wake affine本質(zhì)上是把wakee線程們拉到waker所在的LLC domain，如果超過了LLC domain的cpu個數(shù)，那么必然有任務需要等待，這也就失去了wake affine提升性能的初衷。對于手機平臺，llc domain是MC domain。

C、一般而言，執(zhí)行更多喚醒動作（并且喚醒不同task）的任務是master，因此這里根據(jù)翻轉次數(shù)來交換master和slave，確保master的翻轉次數(shù)大于slave。

D、Slave和master的wakee_flips如果比較小，那么啟動wake affine，否則disable wake affine，走正常選核邏輯。這里的or邏輯是存疑的，因為master和slave其一的wakee_flips比較小就會wake affine，這會使得任務太容易在LLC domain堆積了。在1：N模型中（例如手機轉屏的時候，一個線程會喚醒非常非常多的線程來處理configChange消息），master的wakee_flips巨大無比，slave的wakee_flips非常小，如果仍然wake affine是不合理的。

如果判斷需要進行wake affine，那么我們需要在waking cpu和該任務的prev cpu中選擇一個CPU，后續(xù)在該CPU的LLC domain上進行wake affine。選擇waking cpu還是prev cpu的邏輯是在wake_affine中實現(xiàn)：

int target = nr_cpumask_bits;
if (sched_feat(WA_IDLE))----------------A
    target = wake_affine_idle(this_cpu, prev_cpu, sync);
if (sched_feat(WA_WEIGHT) && target == nr_cpumask_bits)--------------B
    target = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync);

A、這里根據(jù)this_cpu（即waking CPU）和prev cpu的idle狀態(tài)來選擇，哪個cpu處于idle狀態(tài)，那么就選擇那個cpu。如果都idle，那么優(yōu)先prev cpu。this cpu有一個特殊情況：在sync wakeup的場景下，this cpu上如果有唯一的running task（也就是waker了），那么優(yōu)先this cpu，畢竟waker很快就阻塞了。另外，當this cpu處于idle狀態(tài)的時候（中斷喚醒），我們也不能盲目選擇它，畢竟在中斷大量下發(fā)的情況下，有些平臺會把硬件中斷信號只送到this cpu所在的節(jié)點，這會導致 this cpu所在的節(jié)點非常繁忙。

B、當根據(jù)idle狀態(tài)無法完成選核的時候，我們會比拼this cpu和prev cpu上的負載。當然，在計算this cpu和prev cpu負載的時候要考慮任務p的遷移。當this cpu的負載小于prev cpu的負載的時候選擇this cpu。否則，選擇prev cpu。

八、快速選核路徑

快速選核路徑的入口是select_idle_sibling函數(shù)，在這個函數(shù)的開始是一些快速選擇cpu的邏輯，即不需要掃描整個LLC domain的CPU，找idle的cpu，而是直接選擇某個具體的cpu，具體如下：

if (static_branch_unlikely(&sched_asym_cpucapacity)) {----A
    sync_entity_load_avg(&p->se);
    task_util = uclamp_task_util(p);
}
if ((available_idle_cpu(target) || sched_idle_cpu(target)) &&
	sym_fits_capacity(task_util, target))-------B
    return target;

A、在異構系統(tǒng)中，我們后面的代碼邏輯需要使用該任務的utility，看看是否能夠適合CPU的算力，因此，這里需要進行一個負載更新動作，主要是衰減阻塞這段時間的負載。

B、如果之前選定的target cpu（waker所在的cpu或者任務prev cpu）是idle cpu或者雖然沒有idle，但是runqueue中都是SCHED_IDLE的任務，而且該CPU的算力能夠承載該被喚醒的任務，這時候，直接返回target cpu即可。Wake affine的場景下，target cpu是通過wake_affine函數(shù)尋找的target cpu，其他場景下，target CPU其實等于prev CPU。

第二段代碼如下：

if (prev != target && cpus_share_cache(prev, target) &&
    (available_idle_cpu(prev) || sched_idle_cpu(prev)) &&
    asym_fits_capacity(task_util, prev))-----------A
       return prev;
if (is_per_cpu_kthread(current) &&
    prev == smp_processor_id() &&
    this_rq()->nr_running <= 1) {-----------------B
      return prev;
}

A、如果prev cpu是idle狀態(tài)（包括runqueue上僅SCHED_IDLE的任務），并且prev cpu算力能承接該任務的utili，同時prev和target cpu在一個LLC domain，那么優(yōu)選prev cpu

B、當waker是一個per cpu的kthread線程的時候，在wakee的prev cpu也是this cpu的時候，允許把wakee拉到waker所在的cpu，這是為了解決XFS性能問題而引入的提交。這時候kthread很快就會阻塞（類似sync wakeup），wakee也不會在runqueue上等太久。

第三段代碼如下：

recent_used_cpu = p->recent_used_cpu;
if (recent_used_cpu != prev &&
    recent_used_cpu != target &&
    cpus_share_cache(recent_used_cpu, target) &&
    (available_idle_cpu(recent_used_cpu) || sched_idle_cpu(recent_used_cpu)) &&
    cpumask_test_cpu(p->recent_used_cpu, p->cpus_ptr) &&
    asym_fits_capacity(task_util, recent_used_cpu)) {
        p->recent_used_cpu = prev;
        return recent_used_cpu;
}

我們假設有這樣的一個場景，任務A和任務B互相喚醒，如果沒有這段代碼，選核如下：

（1）任務A（在CPU0上）喚醒任務B并將其放置在CPU1

（2）任務B（在CPU1上）喚醒任務A并將其放置在CPU2

（3）任務A（在CPU2上）喚醒任務B并將其放置在CPU3

（4）......

這樣的選核讓任務A和任務B相互拉扯，均勻的使用LLC domain中的各個CPU。這會導致任務的util平均散布在各個CPU上，從而導致CPU util比較小，處于比較低的頻率，影響性能。有了上面的這段代碼邏輯，任務A和任務B的喚醒過程如下：

（1）任務A（在CPU0上）喚醒任務B并將其放置在CPU1

（2）任務B（在CPU1上）喚醒任務A并將其放置在CPU0

（3）......

至此，快速選擇CPU的場景結束了，后續(xù)代碼是在LLC domain上選擇合適CPU的過程。對于異構平臺（例如手機），我們更喜歡idle CPU，這時候我們擴大搜尋范圍，從LLC擴大到sd_asym_cpucapacity（DIE domain），代碼如下：

if (static_branch_unlikely(&sched_asym_cpucapacity)) {
    sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, target));
    if (sd) {
        i = select_idle_capacity(p, sd, target);
        return ((unsigned)i < nr_cpumask_bits) ? i : target;
   }
}

通過select_idle_capacity我們在DIE domain尋找第一個能夠承載該任務的idle cpu，如果雖然找到idle cpu，但是cpu capacity不足，這種情況下，我們返回算力最大的CPU即可。如果找不到idle cpu，那么選擇之前選擇的target cpu。

對于同構平臺，我們需要通過掃描llc domain尋找最空閑CPU，代碼邏輯如下（刪去了SMT代碼）：

sd = rcu_dereference(per_cpu(sd_llc, target));
i = select_idle_cpu(p, sd, target);
if ((unsigned)i < nr_cpumask_bits)
    return i;

select_idle_cpu邏輯比較簡單，就是從LLC domain中找到第一個idle的cpu。為了防止不必要的scan開銷，在掃描之前需要對比該cpu rq的平均idle時間和掃描開銷，如果掃描開銷相對于平均idle時間太大，那么就不再進行掃描。

九、慢速選核路徑

1、概覽

和快速路徑不同，慢速路徑在一個指定的sched domain開始，層層遞進，不斷搜索最空閑的group，然后在這個group中搜索最不忙的CPU，直到base domain。這樣的結果就是在各個level的sched domain上都達到了均衡的效果。慢速路徑的入口是find_idlest_cpu，其函數(shù)原型是：

int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p, int cpu, int prev_cpu, int sd_flag)

該函數(shù)的參數(shù)以及返回值解釋如下

參數(shù)及返回值	描述
Sd	掃描范圍，即從這個sched domain覆蓋的cpu中選擇任務放置的目標cpu
P	需要選擇目標CPU的那個任務
Cpu	當前cpu，即喚醒任務p的CPU
Prev_cpu	任務p上次運行的CPU
sd_flag	標示任務p的喚醒場景
返回值	找到的最適合任務放置的CPU

我們分兩段來解析find_idlest_cpu的邏輯。第一段代碼流程如下：

if (!cpumask_intersects(sched_domain_span(sd), p->cpus_ptr))
    return prev_cpu;---------------A

if (!(sd_flag & SD_BALANCE_FORK))
    sync_entity_load_avg(&p->se);-----------B

A、如果任務p由于affinity的原因無法在sd指定的sched domain中運行，那么直接選擇prev_cpu

B、由于后續(xù)需要進行cpu util的比拼，不同的選核會導致任務p util從一個cpu移動到另外的cpu，因此需要調(diào)用sync_entity_load_avg來更新任務p的負載。當然，新fork出來的任務沒有必要更新，使用初始負載即可

第二段代碼流程如下：

while (sd) {---------------A
    group = find_idlest_group(sd, p, cpu);------------B
    if (!group) {
        sd = sd->child; continue;
    }
    new_cpu = find_idlest_group_cpu(group, p, cpu);--------C
    if (new_cpu == cpu) {
        sd = sd->child; continue;
    }
    cpu = new_cpu;
    weight = sd->span_weight;
    sd = NULL;
    for_each_domain(cpu, tmp) {---------------D
        if (weight <= tmp->span_weight)
            break;
        if (tmp->flags & sd_flag)
            sd = tmp;
    }
}

A、Task placement也是均衡中的一個環(huán)節(jié)，而均衡是一個層層遞進的過程：從指定的sched domain為起點，遍歷其child sched domain，直到base domain。

B、首先在參數(shù)sd中指定的domain中調(diào)用find_idlest_group函數(shù)找到最空閑的sched group，如果local group最閑，那么直接進入下一級的child domain繼續(xù)搜尋。

C、在找到的最空閑的sched group中調(diào)用find_idlest_group_cpu函數(shù)尋找最空閑的CPU，如果不需要切換CPU，那么進入下一級的child domain繼續(xù)搜尋。

D、如果需要切換CPU，那么尋找該CPU對應的下一級child domain，繼續(xù)進行搜尋，直到base domain。

2、尋找最空閑組

find_idlest_group的代碼邏輯主要分成兩個部分：第一部分是更新各個group上的負載并記錄non-local中最空閑的group和local group（總是備選）。第二部分是idlest group和local group的比拼。我們先看第一段代碼：

do {
    int local_group;
    if (!cpumask_intersects(sched_group_span(group), p->cpus_ptr))
        continue;------------------A
    local_group = cpumask_test_cpu(this_cpu, ---------------B
       sched_group_span(group));
    if (local_group) {
        sgs = &local_sgs; local = group;
    } else sgs = &tmp_sgs;
    update_sg_wakeup_stats(sd, group, sgs, p);--------C
    if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) {
        idlest = group;
        idlest_sgs = *sgs;
    }--------------------------D
} while (group = group->next, group != sd->groups);

A、任務至少要能在該group中的一個cpu上運行，否則就不考慮該group

B、判斷是否是local group。我們區(qū)別對待local group和non-local group，對于non-local group要找到最空閑的group。

C、更新該group上的負載信息。這里和load_balance中更新group負載的概念是一樣的，有興趣的可以看看內(nèi)核工匠之前發(fā)布的load_balance詳解的文章。不再贅述。

D、尋找最空閑的idlest group。

至此，我們已經(jīng)拿到了兩個group的統(tǒng)計信息：local group和non-group中idlest group。那么下一級進入那個group對應的domain就需要在這兩個group中比拼，有些選擇是顯而易見的，例如當idlest group不存在或者雖然idlest group存在，但是local group更空閑，這時候選擇local group，可以使得該level的sched domain更加均衡。而當local group不存在，或者idlest group比local group更空閑，這時候選擇idlest group。比較困難的場景是當idlest group和local group空閑程度差不多（group_type相對），這又分成集中情況：

（1）group_overloaded或者group_fully_busy的情況下，對比group的平均負載，選擇平均負載輕的

（2）group_misfit_task情況下，選擇算力大的group

（3）group_has_spare情況下，看哪個group中的idle cpu數(shù)量多

3、尋找最空閑CPU

find_idlest_group_cpu的基本邏輯過程如下：

（1）如果group內(nèi)只有一個cpu（base domain），那么直接返回該cpu

（2）如果group內(nèi)有多個cpu，那么需要遍歷進行比拼

（3）如果一個cpu上只有SCHED_IDLE類型的任務，那么直接返回該cpu。

（4）如果有處于idle狀態(tài)的cpu，那么選擇退出延時最小的那個idle cpu（即睡眠最淺的）。如果有多個cpu處于同等深度的idle狀態(tài)，那么選擇最近那個進入idle的cpu（cache的狀態(tài)會好一些）

（5）如果所有的cpu都忙碌中，那么選擇cpu load最小的那個。