久久久久久久视色,久久电影免费精品,中文亚洲欧美乱码在线观看,在线免费播放AV片

<center id="vfaef"><input id="vfaef"><table id="vfaef"></table></input></center>

    <p id="vfaef"><kbd id="vfaef"></kbd></p>

    
    
    <pre id="vfaef"><u id="vfaef"></u></pre>

      <thead id="vfaef"><input id="vfaef"></input></thead>

    1. 站長(zhǎng)資訊網(wǎng)
      最全最豐富的資訊網(wǎng)站

      Linux內(nèi)核源碼分析之進(jìn)程調(diào)度的邏輯(總結(jié)分享)

      本篇文章給大家?guī)?lái)了關(guān)于linux中內(nèi)核源碼分析進(jìn)程調(diào)度邏輯的相關(guān)知識(shí),希望對(duì)大家有幫助。

      Linux內(nèi)核源碼分析之進(jìn)程調(diào)度的邏輯(總結(jié)分享)

      0.1 本文目錄結(jié)構(gòu)

      1 操作系統(tǒng)理論層面

      2 調(diào)度主函數(shù)

      3 __schedule() 方法核心邏輯概覽

      4 pick_next_task():從就緒隊(duì)列中選中一個(gè)進(jìn)程

      • 4.1 負(fù)載均衡邏輯

      • 4.2 選中高優(yōu)進(jìn)程

      • 4.3 pick_next_task() 小結(jié)

      5 context_switch():執(zhí)行上下文切換

      • 5.1 切換虛擬內(nèi)存

      • 5.2 切換通用寄存器

      • 5.3 context_switch() 小結(jié)

      6 本文總結(jié)

      0.2 pick_next_task():從就緒隊(duì)列中選中一個(gè)進(jìn)程

      內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候,會(huì)首先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度,如果沒(méi)有,執(zhí)行進(jìn)程遷移邏輯,從其他 CPU 遷移進(jìn)程,如果有,則選擇虛擬時(shí)間較小的進(jìn)程進(jìn)行調(diào)度。

      內(nèi)核在選擇邏輯 CPU 進(jìn)行遷移進(jìn)程的時(shí)候,為了提升被遷移進(jìn)程的性能,即避免遷移之后 L1 L2 L3 高速緩存失效,盡可能遷移那些和當(dāng)前邏輯 CPU 共享高速緩存的目標(biāo)邏輯 CPU,離當(dāng)前邏輯 CPU 越近越好。

      內(nèi)核將進(jìn)程抽象為調(diào)度實(shí)體,為的是可以將一批進(jìn)程進(jìn)行統(tǒng)一調(diào)度,在每一個(gè)調(diào)度層次上,都保證公平。

      所謂選中高優(yōu)進(jìn)程,實(shí)際上選中的是虛擬時(shí)間較小的進(jìn)程,進(jìn)程的虛擬時(shí)間是根據(jù)進(jìn)程的實(shí)際優(yōu)先級(jí)和進(jìn)程的運(yùn)行時(shí)間等信息動(dòng)態(tài)計(jì)算出來(lái)的。

      0.3 5 context_switch():執(zhí)行上下文切換

      進(jìn)程上下文切換,核心要切換的是虛擬內(nèi)存及一些通用寄存器。

      進(jìn)程切換虛擬內(nèi)存,需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁(yè)表,頁(yè)表也即不同進(jìn)程的虛擬內(nèi)存翻譯需要的 "map"。

      進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中,有一個(gè)間接字段 cpu_context 保存了通用寄存器的值,寄存器切換的本質(zhì)就是將上一個(gè)進(jìn)程的寄存器保存到 cpu_context 字段,然后再將下一個(gè)進(jìn)程的 cpu_context 數(shù)據(jù)結(jié)構(gòu)中的字段加載到寄存器中,至此完成進(jìn)程的切換。

      1 操作系統(tǒng)理論層面

      學(xué)過(guò)操作系統(tǒng)的同學(xué)應(yīng)該都知道,進(jìn)程調(diào)度分為如下兩個(gè)步驟:

      根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程。

      執(zhí)行進(jìn)程上下文切換。

      其中第二個(gè)步驟又可以分為:

      切換虛擬內(nèi)存。

      切換寄存器,即保存上一個(gè)進(jìn)程的寄存器到進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中,加載下一個(gè)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)到寄存器中。

      關(guān)于虛擬內(nèi)存相關(guān)的邏輯,后續(xù)文章會(huì)詳細(xì)剖析,這篇文章會(huì)簡(jiǎn)要概括。

      這篇文章,我們從內(nèi)核源碼的角度來(lái)剖析 Linux 是如何來(lái)實(shí)現(xiàn)進(jìn)程調(diào)度的核心邏輯,基本上遵從操作系統(tǒng)理論。

      2 調(diào)度主函數(shù)

      Linux 進(jìn)程調(diào)度的主函數(shù)是 schedule() 和 __schedule(),從源碼中可以看出兩者的關(guān)系:

      // kernel/sched/core.c:3522 void schedule(void) {     ...     // 調(diào)度過(guò)程中禁止搶占     preempt_disable();      __schedule(false); //:3529     // 調(diào)度完了,可以搶占了     sched_preempt_enable_no_resched();     ... } // kernel/sched/core.c:3395 __schedule(bool preempt) {      ...  }

      當(dāng)一個(gè)進(jìn)程主動(dòng)讓出 CPU,比如 yield 系統(tǒng)調(diào)用,會(huì)執(zhí)行 schedule() 方法,在執(zhí)行進(jìn)程調(diào)度的過(guò)程中,禁止其他進(jìn)程搶占當(dāng)前進(jìn)程,說(shuō)白了就是讓當(dāng)前進(jìn)程好好完成這一次進(jìn)程切換,不要?jiǎng)儕Z它的 CPU;

      3529 行代碼表示 schedule() 調(diào)用了 __schedule(false) 方法,傳遞 fasle 參數(shù),表示這是進(jìn)程的一次主動(dòng)調(diào)度,不可搶占。

      等當(dāng)前的進(jìn)程執(zhí)行完調(diào)度邏輯之后,開(kāi)啟搶占,也就是說(shuō),其他進(jìn)程可以剝奪當(dāng)前進(jìn)程的 CPU 了。

      而如果某個(gè)進(jìn)程像個(gè)強(qiáng)盜一樣一直占著 CPU 不讓?zhuān)瑑?nèi)核會(huì)通過(guò)搶占機(jī)制(比如上一篇文章提到的周期調(diào)度機(jī)制)進(jìn)行一次進(jìn)程調(diào)度,從而把當(dāng)前進(jìn)程從 CPU 上踢出去。

      __schedule() 方法的框架便是這篇文章分析的主要內(nèi)容,由于代碼較多,我會(huì)挑選核心部分來(lái)描述。

      3 __schedule() 方法核心邏輯概覽

      我們先來(lái)看看 Linux 內(nèi)核中,進(jìn)程調(diào)度核心函數(shù) __schedule() 的框架:

      // kernel/sched/core.c:3395 void __schedule(bool preempt) {     struct task_struct *prev, *next;     unsigned long *switch_count;     struct rq *rq;     int cpu;     // 獲取當(dāng)前 CPU     cpu = smp_processor_id();     // 獲取當(dāng)前 CPU 上的進(jìn)程隊(duì)列     rq = cpu_rq(cpu);     // 獲取當(dāng)前隊(duì)列上正在運(yùn)行的進(jìn)程     prev = rq->curr;     ...     // nivcsw:進(jìn)程非主動(dòng)切換次數(shù)     switch_count = &prev->nivcsw; // :3430     if (!preempt ...) {         ...         // nvcsw:進(jìn)程主動(dòng)切換次數(shù)          switch_count = &prev->nvcsw; // :3456     }     ...     // 1 根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程     next = pick_next_task(rq, prev, &rf);     ...     if (prev != next) {         rq->nr_switches++;         rq->curr = next;         ++*switch_count;         // 2 執(zhí)行進(jìn)程上下文切換         rq = context_switch(rq, prev, next, &rf);     }      ... }

      可以看到,__schedule() 方法中,進(jìn)程切換的核心步驟和操作系統(tǒng)理論中是一致的(1 和 2 兩個(gè)核心步驟)。

      此外,進(jìn)程切換的過(guò)程中,內(nèi)核會(huì)根據(jù)是主動(dòng)發(fā)起調(diào)度(preempt 為 fasle)還是被動(dòng)發(fā)起調(diào)度,來(lái)統(tǒng)計(jì)進(jìn)程上下文切換的次數(shù),分別保存在進(jìn)程的數(shù)據(jù)結(jié)構(gòu) task_struct 中:

      // include/linux/sched.h:592 struct task_struct {     ...     // 主動(dòng)切換:Number of Voluntary(自愿) Context Switches     unsigned long nvcsw; // :811     // 非主動(dòng)切換:Number of InVoluntary(非自愿) Context Switches     unsigned long nivcsw; // :812     ... };

      在 Linux 中,我們可以通過(guò) pidstat 命令來(lái)查看一個(gè)進(jìn)程的主動(dòng)和被動(dòng)上下文切換的次數(shù),我們寫(xiě)一個(gè)簡(jiǎn)單的 c 程序來(lái)做個(gè)測(cè)試:

      // test.c #include <stdlib.h> #include <stdio.h> int main() {     while (1) {         // 每隔一秒主動(dòng)休眠一次         // 即主動(dòng)讓出 CPU         // 理論上每秒都會(huì)主動(dòng)切換一次         sleep(1)     } }

      然后編譯運(yùn)行

      gcc test.c -o test ./test

      通過(guò) pidstat 來(lái)查看

      Linux內(nèi)核源碼分析之進(jìn)程調(diào)度的邏輯(總結(jié)分享)

      可以看到,test 應(yīng)用程序每秒主動(dòng)切換一次進(jìn)程上下文,和我們的預(yù)期相符,對(duì)應(yīng)的上下文切換數(shù)據(jù)就是從 task_struct 中獲取的。

      接下來(lái),詳細(xì)分析進(jìn)程調(diào)度的兩個(gè)核心步驟:

      通過(guò) pick_next_task() 從就緒隊(duì)列中選中一個(gè)進(jìn)程。

      通過(guò) context_switch 執(zhí)行上下文切換。

      4 pick_next_task():從就緒隊(duì)列中選中一個(gè)進(jìn)程

      我們回顧一下 pick_next_task() 在 __schedule() 方法中的位置

      // kernel/sched/core.c:3395 void __schedule(bool preempt) {     ...     // rq 是當(dāng)前 cpu 上的進(jìn)程隊(duì)列     next = pick_next_task(rq, pre ...); // :3459     ... }

      跟著調(diào)用鏈往下探索:

      // kernel/sched/core.c:3316 /*   * 找出優(yōu)先級(jí)最高的進(jìn)程  * Pick up the highest-prio task:  */ struct task_struct *pick_next_task(rq, pre ...) {     struct task_struct *p;     ...     p = fair_sched_class.pick_next_task(rq, prev ...); // :3331     ...     if (!p)         p = idle_sched_class.pick_next_task(rq, prev ...); // :3337     return p; }

      從 pick_next_task() 方法的注釋上也能看到,這個(gè)方法的目的就是找出優(yōu)先級(jí)最高的進(jìn)程,由于系統(tǒng)中大多數(shù)進(jìn)程的調(diào)度類(lèi)型都是公平調(diào)度,我們拿公平調(diào)度相關(guān)的邏輯來(lái)分析。

      從上述的核心框架中可以看到,3331 行先嘗試從公平調(diào)度類(lèi)型的隊(duì)列中獲取進(jìn)程,3337 行,如果沒(méi)有找到,就把每個(gè) CPU 上的 IDLE 進(jìn)程取出來(lái)運(yùn)行:

      // kernel/sched/idle.c:442 const struct sched_class idle_sched_class = {     ...         .pick_next_task    = pick_next_task_idle, // :451     ... }; // kernel/sched/idle.c:385 struct task_struct * pick_next_task_idle(struct rq *rq ...) {     ...     // 每一個(gè) CPU 運(yùn)行隊(duì)列中都有一個(gè) IDLE 進(jìn)程      return rq->idle; // :383 }

      接下來(lái),我們聚焦公平調(diào)度類(lèi)的進(jìn)程選中算法 fair_sched_class.pick_next_task()

      // kernel/sched/fair.c:10506 const struct sched_class fair_sched_class = {    ...    .pick_next_task = pick_next_task_fair, // : 10515     ... } // kernel/sched/fair.c:6898 static struct task_struct * pick_next_task_fair(struct rq *rq ...) {     // cfs_rq 是當(dāng)前 CPU 上公平調(diào)度類(lèi)隊(duì)列     struct cfs_rq *cfs_rq = &rq->cfs;     struct sched_entity *se;     struct task_struct *p;     int new_tasks; again:     // 1 當(dāng)前 CPU 進(jìn)程隊(duì)列沒(méi)有進(jìn)程可調(diào)度,則執(zhí)行負(fù)載均衡邏輯     if (!cfs_rq->nr_running)          goto idle;     // 2. 當(dāng)前 CPU 進(jìn)程隊(duì)列有進(jìn)程可調(diào)度,選中一個(gè)高優(yōu)進(jìn)程 p     do {         struct sched_entity *curr = cfs_rq->curr;         ...         se = pick_next_entity(cfs_rq, curr);          cfs_rq = group_cfs_rq(se);     } while (cfs_rq);      p = task_of(se);     ... idle:     // 通過(guò)負(fù)載均衡遷移進(jìn)程     new_tasks = idle_balance(rq, rf); // :7017     ...          if (new_tasks > 0)         goto again;     return NULL; }

      pick_next_task_fair() 的邏輯相對(duì)還是比較復(fù)雜的,但是,其中的核心思想分為兩步:

      如果當(dāng)前 CPU 上已無(wú)進(jìn)程可調(diào)度,則執(zhí)行負(fù)載邏輯,從其他 CPU 上遷移進(jìn)程過(guò)來(lái);

      如果當(dāng)前 CPU 上有進(jìn)程可調(diào)度,從隊(duì)列中選擇一個(gè)高優(yōu)進(jìn)程,所謂高優(yōu)進(jìn)程,即虛擬時(shí)間最小的進(jìn)程;

      下面,我們分兩步拆解上述步驟。

      4.1 負(fù)載均衡邏輯

      內(nèi)核為了讓各 CPU 負(fù)載能夠均衡,在某些 CPU 較為空閑的時(shí)候,會(huì)從繁忙的 CPU 上遷移進(jìn)程到空閑 CPU 上運(yùn)行,當(dāng)然,如果進(jìn)程設(shè)置了 CPU 的親和性,即進(jìn)程只能在某些 CPU 上運(yùn)行,則此進(jìn)程無(wú)法遷移。

      負(fù)載均衡的核心邏輯是 idle_balance 方法:

      // kernel/sched/fair.c:9851 static int idle_balance(struct rq *this_rq ...) {     int this_cpu = this_rq->cpu;     struct sched_domain *sd;     int pulled_task = 0;          ...     for_each_domain(this_cpu, sd) { // :9897         ...         pulled_task = load_balance(this_cpu...);         ...         if (pulled_task ...) // :9912             break;     }          ...     return pulled_task; }

      idle_balance() 方法的邏輯也相對(duì)比較復(fù)雜:但是大體上概括就是,遍歷當(dāng)前 CPU 的所有調(diào)度域,直到遷移出進(jìn)程位置。

      這里涉及到一個(gè)核心概念:sched_domain,即調(diào)度域,下面用一張圖介紹一下什么是調(diào)度域。

      Linux內(nèi)核源碼分析之進(jìn)程調(diào)度的邏輯(總結(jié)分享)

      內(nèi)核根據(jù)處理器與主存的距離將處理器分為兩個(gè) NUMA 節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)有兩個(gè)處理器。NUMA 指的是非一致性訪問(wèn),每個(gè) NUMA 節(jié)點(diǎn)中的處理器訪問(wèn)內(nèi)存節(jié)點(diǎn)的速度不一致,不同 NUMA 節(jié)點(diǎn)之間不共享 L1 L2 L3 Cache。

      每個(gè) NUMA 節(jié)點(diǎn)下有兩個(gè)處理器,同一個(gè) NUMA 下的不同處理器共享 L3 Cache。

      每個(gè)處理器下有兩個(gè) CPU 核,同個(gè)處理器下的不同核共享 L2 L3 Cache。

      每個(gè)核下面有兩個(gè)超線程,同一個(gè)核的不同超線程共享 L1 L2 L3 Cache。

      我們?cè)趹?yīng)用程序里面,通過(guò)系統(tǒng) API 拿到的都是超線程,也可以叫做邏輯 CPU,下文統(tǒng)稱(chēng)邏輯 CPU。

      進(jìn)程在訪問(wèn)一個(gè)某個(gè)地址的數(shù)據(jù)的時(shí)候,會(huì)先在 L1 Cache 中找,若未找到,則在 L2 Cache 中找,再未找到,則在 L3 Cache 上找,最后都沒(méi)找到,就訪問(wèn)主存,而訪問(wèn)速度方面 L1 > L2 > L3 > 主存,內(nèi)核遷移進(jìn)程的目標(biāo)是盡可能讓遷移出來(lái)的進(jìn)程能夠命中緩存。

      內(nèi)核按照上圖中被虛線框起來(lái)的部分,抽象出調(diào)度域的概念,越靠近上層,調(diào)度域的范圍越大,緩存失效的概率越大,因此,遷移進(jìn)程的一個(gè)目標(biāo)是,盡可能在低級(jí)別的調(diào)度域中獲取可遷移的進(jìn)程。

      上述代碼 idle_balance() 方法的 9897 行:for_each_domain(this_cpu, sd),this_cpu 就是邏輯 CPU(也即是最底層的超線程概念),sd 是調(diào)度域,這行代碼的邏輯就是逐層往上擴(kuò)大調(diào)度域;

      // kernel/sched/sched.h:1268 #define for_each_domain(cpu, __sd)      for (__sd = cpu_rq(cpu)->sd);              __sd; __sd = __sd->parent)

      而 idle_balance() 方法的 9812 行,如果在某個(gè)調(diào)度域中,成功遷移出了進(jìn)程到當(dāng)前邏輯 CPU,就終止循環(huán),可見(jiàn),內(nèi)核為了提升應(yīng)用性能真是煞費(fèi)苦心。

      經(jīng)過(guò)負(fù)載均衡之后,當(dāng)前空閑的邏輯 CPU 進(jìn)程隊(duì)列很有可能已經(jīng)存在就緒進(jìn)程了,于是,接下來(lái)從這個(gè)隊(duì)列中獲取最合適的進(jìn)程。

      4.2 選中高優(yōu)進(jìn)程

      接下來(lái),我們把重點(diǎn)放到如何選擇高優(yōu)進(jìn)程,而在公平調(diào)度類(lèi)中,會(huì)通過(guò)進(jìn)程的實(shí)際優(yōu)先級(jí)和運(yùn)行時(shí)間,來(lái)計(jì)算一個(gè)虛擬時(shí)間,虛擬時(shí)間越少,被選中的概率越高,所以叫做公平調(diào)度。

      以下是選擇高優(yōu)進(jìn)程的核心邏輯:

      // kernel/sched/fair.c:6898 static struct task_struct * pick_next_task_fair(struct rq *rq ...) {     // cfs_rq 是當(dāng)前 CPU 上公平調(diào)度類(lèi)隊(duì)列     struct cfs_rq *cfs_rq = &rq->cfs;     struct sched_entity *se;     struct task_struct *p;     // 2. 當(dāng)前 CPU 進(jìn)程隊(duì)列有進(jìn)程可調(diào)度,選中一個(gè)高優(yōu)進(jìn)程 p     do {         struct sched_entity *curr = cfs_rq->curr;         ...         se = pick_next_entity(cfs_rq, curr);          cfs_rq = group_cfs_rq(se);     } while (cfs_rq);      // 拿到被調(diào)度實(shí)體包裹的進(jìn)程     p = task_of(se); // :6956     ...     return p; }

      內(nèi)核提供一個(gè)調(diào)度實(shí)體的的概念,對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)叫 sched_entity,內(nèi)核實(shí)際上是根據(jù)調(diào)度實(shí)體為單位進(jìn)行調(diào)度的:

      // include/linux/sched.h:447 struct sched_entity {     ...     // 當(dāng)前調(diào)度實(shí)體的父親     struct sched_entity    *parent;     // 當(dāng)前調(diào)度實(shí)體所在隊(duì)列     struct cfs_rq *cfs_rq;  // :468     // 當(dāng)前調(diào)度實(shí)體擁有的隊(duì)列,及子調(diào)度實(shí)體隊(duì)列     // 進(jìn)程是底層實(shí)體,不擁有隊(duì)列     struct cfs_rq *my_q;     ... };

      每一個(gè)進(jìn)程對(duì)應(yīng)一個(gè)調(diào)度實(shí)體,若干調(diào)度實(shí)體綁定到一起可以形成一個(gè)更高層次的調(diào)度實(shí)體,因此有個(gè)遞歸的效應(yīng),上述 do while 循環(huán)的邏輯就是從當(dāng)前邏輯 CPU 頂層的公平調(diào)度實(shí)體(cfs_rq->curr)開(kāi)始,逐層選擇虛擬時(shí)間較少的調(diào)度實(shí)體進(jìn)行調(diào)度,直到最后一個(gè)調(diào)度實(shí)體是進(jìn)程。

      內(nèi)核這樣做的原因是希望盡可能在每個(gè)層次上,都能夠保證調(diào)度是公平的。

      拿 Docker 容器的例子來(lái)說(shuō),一個(gè) Docker 容器中運(yùn)行了若干個(gè)進(jìn)程,這些進(jìn)程屬于同一個(gè)調(diào)度實(shí)體,和宿主機(jī)上的進(jìn)程的調(diào)度實(shí)體屬于同一層級(jí),所以,如果 Docker 容器中瘋狂 fork 進(jìn)程,內(nèi)核會(huì)計(jì)算這些進(jìn)程的虛擬時(shí)間總和來(lái)和宿主機(jī)其他進(jìn)程進(jìn)行公平抉擇,這些進(jìn)程休想一直霸占著 CPU!

      選擇虛擬時(shí)間最少的進(jìn)程的邏輯是 se = pick_next_entity(cfs_rq, curr); ,相應(yīng)邏輯如下:

      // kernel/sched/fair.c:4102 struct sched_entity * pick_next_entity(cfs_rq *cfs_rq, sched_entity *curr) {     // 公平運(yùn)行隊(duì)列中虛擬時(shí)間最小的調(diào)度實(shí)體     struct sched_entity *left = __pick_first_entity(cfs_rq);     struct sched_entity *se;     // 如果沒(méi)找到或者樹(shù)中的最小虛擬時(shí)間的進(jìn)程     // 還沒(méi)當(dāng)前調(diào)度實(shí)體小,那就選擇當(dāng)前實(shí)體     if (!left || (curr && entity_before(curr, left)))          left = curr;     se = left;      return se; } // kernel/sched/fair.c:489 int entity_before(struct sched_entity *a, struct sched_entity *b) {     // 比較兩者虛擬時(shí)間     return (s64)(a->vruntime - b->vruntime) < 0; }

      上述代碼,我們可以分析出,pick_next_entity() 方法會(huì)在當(dāng)前公平調(diào)度隊(duì)列 cfs_rq 中選擇最靠左的調(diào)度實(shí)體,最靠左的調(diào)度實(shí)體的虛擬時(shí)間越小,即最優(yōu)。

      而下面通過(guò) __pick_first_entity() 方法,我們了解到,公平調(diào)度隊(duì)列 cfs_rq 中的調(diào)度實(shí)體被組織為一棵紅黑樹(shù),這棵樹(shù)的最左側(cè)節(jié)點(diǎn)即為最小節(jié)點(diǎn):

      // kernel/sched/fair.c:565 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) {     struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);     if (!left)         return NULL;     return rb_entry(left, struct sched_entity, run_node); } // include/linux/rbtree.h:91 // 緩存了紅黑樹(shù)最左側(cè)節(jié)點(diǎn) #define rb_first_cached(root) (root)->rb_leftmost

      通過(guò)以上分析,我們依然通過(guò)一個(gè) Docker 的例子來(lái)分析: 一個(gè)宿主機(jī)中有兩個(gè)普通進(jìn)程分別為 A,B,一個(gè) Docker 容器,容器中有 c1、c2、c3 進(jìn)程。

      這種情況下,系統(tǒng)中有兩個(gè)層次的調(diào)度實(shí)體,最高層為 A、B、c1+c2+c3,再往下為 c1、c2、c3,下面我們分情況來(lái)討論進(jìn)程選中的邏輯:

      1)若虛擬時(shí)間分布為:A:100s,B:200s,c1:50s,c2:100s,c3:80s

      選中邏輯:先比較 A、B、c1+c2+c3 的虛擬時(shí)間,發(fā)現(xiàn) A 最小,由于 A 已經(jīng)是進(jìn)程,選中 A,如果 A 比當(dāng)前運(yùn)行進(jìn)程虛擬時(shí)間還小,下一個(gè)運(yùn)行的進(jìn)程就是 A,否則保持當(dāng)前進(jìn)程不變。

      2)若虛擬時(shí)間分布為:A:100s,B:200s,c1:50s,c2:30s,c3:10s

      選中邏輯:先比較 A、B、c1+c2+c3 的虛擬時(shí)間,發(fā)現(xiàn) c1+c2+c3 最小,由于選中的調(diào)度實(shí)體非進(jìn)程,而是一組進(jìn)程,繼續(xù)往下一層調(diào)度實(shí)體進(jìn)行選擇,比較 c1、c2、c3 的虛擬時(shí)間,發(fā)現(xiàn) c3 的虛擬時(shí)間最小,如果 c3 的虛擬時(shí)間小于當(dāng)前進(jìn)程的虛擬時(shí)間,下一個(gè)運(yùn)行的進(jìn)程就是 c3,否則保持當(dāng)前進(jìn)程不變。

      到這里,選中高優(yōu)進(jìn)程進(jìn)行調(diào)度的邏輯就結(jié)束了,我們來(lái)做下小結(jié)。

      4.3 pick_next_task() 小結(jié)

      內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候,會(huì)先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度,如果沒(méi)有,執(zhí)行進(jìn)程遷移邏輯,從其他 CPU 遷移進(jìn)程,如果有,則選擇虛擬時(shí)間較小的進(jìn)程進(jìn)行調(diào)度。

      內(nèi)核在選擇邏輯 CPU 進(jìn)行遷移進(jìn)程的時(shí)候,為了提升被遷移進(jìn)程的性能,即避免遷移之后 L1 L2 L3 高速緩存失效,盡可能遷移那些和當(dāng)前邏輯 CPU 共享高速緩存的目標(biāo)邏輯 CPU,離當(dāng)前邏輯 CPU 越近越好。

      內(nèi)核將進(jìn)程抽象為調(diào)度實(shí)體,為的是可以將一批進(jìn)程進(jìn)行統(tǒng)一調(diào)度,在每一個(gè)調(diào)度層次上,都保證公平。

      所謂選中高優(yōu)進(jìn)程,實(shí)際上選中的是虛擬時(shí)間較小的進(jìn)程,進(jìn)程的虛擬時(shí)間是根據(jù)進(jìn)程的實(shí)際優(yōu)先級(jí)和進(jìn)程的運(yùn)行時(shí)間等信息動(dòng)態(tài)計(jì)算出來(lái)的。

      5 context_switch():執(zhí)行上下文切換

      選中一個(gè)合適的進(jìn)程之后,接下來(lái)就要執(zhí)行實(shí)際的進(jìn)程切換了,我們把目光重新聚焦到 __schedule() 方法

      // kernel/sched/core.c:3395 void __schedule(bool preempt) {     struct task_struct *prev, *next;     ...     // 1 根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程     next = pick_next_task(rq, prev,...); // :3459     ...     if (prev != next) {         rq->curr = next;         // 2 執(zhí)行進(jìn)程上下文切換         rq = context_switch(rq, prev, next ...); // ::3485     }      ... }

      其中,進(jìn)程上下文切換的核心邏輯就是 context_switch,對(duì)應(yīng)邏輯如下:

      // kernel/sched/core.c:2804 struct rq *context_switch(... task_struct *prev, task_struct *next ...) {     struct mm_struct *mm, *oldmm;     ...     mm = next->mm;     oldmm = prev->active_mm;     ...     // 1 切換虛擬內(nèi)存     switch_mm_irqs_off(oldmm, mm, next);     ...     // 2 切換寄存器狀態(tài)     switch_to(prev, next, prev);     ... }

      上述代碼,我略去了一些細(xì)節(jié),保留我們關(guān)心的核心邏輯。context_switch() 核心邏輯分為兩個(gè)步驟,切換虛擬內(nèi)存和寄存器狀態(tài),下面,我們展開(kāi)這兩段邏輯。

      5.1 切換虛擬內(nèi)存

      首先,簡(jiǎn)要介紹一下虛擬內(nèi)存的幾個(gè)知識(shí)點(diǎn):

      進(jìn)程無(wú)法直接訪問(wèn)到物理內(nèi)存,而是通過(guò)虛擬內(nèi)存到物理內(nèi)存的映射機(jī)制間接訪問(wèn)到物理內(nèi)存的。

      每個(gè)進(jìn)程都有自己獨(dú)立的虛擬內(nèi)存地址空間。如,進(jìn)程 A 可以有一個(gè)虛擬地址 0x1234 映射到物理地址 0x4567,進(jìn)程 B 也可以有一個(gè)虛擬地址 0x1234 映射到 0x3456,即不同進(jìn)程可以有相同的虛擬地址。如果他們指向的物理內(nèi)存相同,則兩個(gè)進(jìn)程即可通過(guò)內(nèi)存共享進(jìn)程通信。

      進(jìn)程通過(guò)多級(jí)頁(yè)表機(jī)制來(lái)執(zhí)行虛擬內(nèi)存到物理內(nèi)存的映射,如果我們簡(jiǎn)單地把這個(gè)機(jī)制當(dāng)做一個(gè) map<虛擬地址,物理地址> 數(shù)據(jù)結(jié)構(gòu)的話,那么可以理解為不同的進(jìn)程有維護(hù)著不同的 map;

      map<虛擬地址,物理地址> 的翻譯是通過(guò)多級(jí)頁(yè)表來(lái)實(shí)現(xiàn)的,訪問(wèn)多級(jí)頁(yè)表需要多次訪問(wèn)內(nèi)存,效率太差,因此,內(nèi)核使用 TLB 緩存頻繁被訪問(wèn)的 <虛擬地址,物理地址> 的項(xiàng)目,感謝局部性原理。

      由于不同進(jìn)程可以有相同的虛擬地址,這些虛擬地址往往指向了不同的物理地址,因此,TLB 實(shí)際上是通過(guò) <ASID + 虛擬地址,物理地址> 的方式來(lái)唯一確定某個(gè)進(jìn)程的物理地址的,ASID 叫做地址空間 ID(Address Space ID),每個(gè)進(jìn)程唯一,等價(jià)于多租戶(hù)概念中的租戶(hù) ID。

      進(jìn)程的虛擬地址空間用數(shù)據(jù)結(jié)構(gòu) mm_struct 來(lái)描述,進(jìn)程數(shù)據(jù)結(jié)構(gòu) task_struct 中的 mm 字段就指向此數(shù)據(jù)結(jié)構(gòu),而上述所說(shuō)的進(jìn)程的 "map" 的信息就藏在 mm_struct 中。

      關(guān)于虛擬內(nèi)存的介紹,后續(xù)的文章會(huì)繼續(xù)分析,這里,我們只需要了解上述幾個(gè)知識(shí)點(diǎn)即可,我們進(jìn)入到切換虛擬內(nèi)存核心邏輯:

      // include/linux/mmu_context.h:14 # define switch_mm_irqs_off switch_mm // arch/arm64/include/asm/mmu_context.h:241 void switch_mm(mm_struct *prev, mm_struct *next) {     // 如果兩個(gè)進(jìn)程不是同一個(gè)進(jìn)程     if (prev != next)         __switch_mm(next);     ... } // arch/arm64/include/asm/mmu_context.h:224 void __switch_mm(struct mm_struct *next) {     unsigned int cpu = smp_processor_id();     check_and_switch_context(next, cpu); }

      接下來(lái),調(diào)用 check_and_switch_context 做實(shí)際的虛擬內(nèi)存切換操作:

      // arch/arm64/mm/context.c:194 void check_and_switch_context(struct mm_struct *mm, unsigned int cpu) {     ...     u64 asid;     // 拿到要將下一個(gè)進(jìn)程的 ASID     asid = atomic64_read(&mm->context.id); // :218     ...     // 將下一個(gè)進(jìn)程的 ASID 綁定到當(dāng)前 CPU     atomic64_set(&per_cpu(active_asids, cpu), asid);  // :236     // 切換頁(yè)表,及切換我們上述中的 "map",     // 將 ASID 和 "map" 設(shè)置到對(duì)應(yīng)的寄存器     cpu_switch_mm(mm->pgd, mm); // :248 }

      check_and_switch_context 總體上分為兩塊邏輯:

      • 將下一個(gè)進(jìn)程的 ASID 綁定到當(dāng)前的 CPU,這樣 TLB 通過(guò)虛擬地址翻譯出來(lái)的物理地址,就屬于下個(gè)進(jìn)程的。

      • 拿到下一個(gè)進(jìn)程的 "map",也就是頁(yè)表,對(duì)應(yīng)的字段是 "mm->pgd",然后執(zhí)行頁(yè)表切換邏輯,這樣后續(xù)如果 TLB 沒(méi)命中,當(dāng)前 CPU 就能夠知道通過(guò)哪個(gè) "map" 來(lái)翻譯虛擬地址。

      cpu_switch_mm 涉及的匯編代碼較多,這里就不貼了,本質(zhì)上就是將 ASID 和頁(yè)表("map")的信息綁定到對(duì)應(yīng)的寄存器。

      5.2 切換通用寄存器

      虛擬內(nèi)存切換完畢之后,接下來(lái)切換進(jìn)程執(zhí)行相關(guān)的通用寄存器,對(duì)應(yīng)邏輯為 switch_to(prev, next …); 方法,這個(gè)方法也是切換進(jìn)程的分水嶺,調(diào)用完之后的那一刻,當(dāng)前 CPU 上執(zhí)行就是 next 的代碼了。

      拿 arm64 為例:

      // arch/arm64/kernel/process.c:422 struct task_struct *__switch_to(task_struct *prev, task_struct *next) {     ...     // 實(shí)際切換方法     cpu_switch_to(prev, next); // :444     ... }

      cpu_switch_to 對(duì)應(yīng)的是一段經(jīng)典的匯編邏輯,看著很多,其實(shí)并不難理解。

      // arch/arm64/kernel/entry.S:1040 // x0 -> pre // x1 -> next ENTRY(cpu_switch_to)     // x10 存放 task_struct->thread.cpu_context 字段偏移量     mov    x10, #THREAD_CPU_CONTEXT // :1041          // ===保存 pre 上下文===     // x8 存放 prev->thread.cpu_context     add    x8, x0, x10      // 保存 prev 內(nèi)核棧指針到 x9     mov    x9, sp     // 將 x19 ~ x28 保存在 cpu_context 字段中     // stp 是 store pair 的意思     stp    x19, x20, [x8], #16     stp    x21, x22, [x8], #16     stp    x23, x24, [x8], #16     stp    x25, x26, [x8], #16     stp    x27, x28, [x8], #16     // 將 x29 存在 fp 字段,x9 存在 sp 字段     stp    x29, x9, [x8], #16      // 將 pc 寄存器 lr 保存到 cpu_context 的 pc 字段     str    lr, [x8]                // ===加載 next 上下文===     // x8 存放 next->thread.cpu_context     add    x8, x1, x10     // 將 cpu_context 中字段載入到 x19 ~ x28     // ldp 是 load pair 的意思     ldp    x19, x20, [x8], #16     ldp    x21, x22, [x8], #16     ldp    x23, x24, [x8], #16     ldp    x25, x26, [x8], #16     ldp    x27, x28, [x8], #16     ldp    x29, x9, [x8], #16     // 設(shè)置 pc 寄存器     ldr    lr, [x8]     // 切換到 next 的內(nèi)核棧     mov    sp, x9          // 將 next 指針保存到 sp_el0 寄存器     msr    sp_el0, x1      ret ENDPROC(cpu_switch_to)

      上述匯編的邏輯可以和操作系統(tǒng)理論課里的內(nèi)容一一對(duì)應(yīng),即先將通用寄存器的內(nèi)容保存到進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中對(duì)應(yīng)的字段,然后再?gòu)南乱粋€(gè)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中對(duì)應(yīng)的字段加載到通用寄存器中。

      1041 行代碼是拿到 task_struct 結(jié)構(gòu)中的 thread_struct thread 字段的 cpu_contxt 字段:

      // arch/arm64/kernel/asm-offsets.c:53 DEFINE(THREAD_CPU_CONTEXT,    offsetof(struct task_struct, thread.cpu_context));

      我們來(lái)分析一下對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu):

      // include/linux/sched.h:592 struct task_struct {     ...     struct thread_struct thread; // :1212     ... }; // arch/arm64/include/asm/processor.h:129 struct thread_struct {     struct cpu_context  cpu_context;     ... }

      而 cpu_context 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)就是為了保存與進(jìn)程有關(guān)的一些通用寄存器的值:

      // arch/arm64/include/asm/processor.h:113 struct cpu_context {     unsigned long x19;     unsigned long x20;     unsigned long x21;     unsigned long x22;     unsigned long x23;     unsigned long x24;     unsigned long x25;     unsigned long x26;     unsigned long x27;     unsigned long x28;     // 對(duì)應(yīng) x29 寄存器     unsigned long fp;     unsigned long sp;     // 對(duì)應(yīng) lr 寄存器     unsigned long pc; };

      這些值剛好與上述匯編片段的代碼一一對(duì)應(yīng)上,讀者應(yīng)該不需要太多匯編基礎(chǔ)就可以分析出來(lái)。

      上述匯編中,最后一行 msr sp_el0, x1,x1 寄存器中保存了 next 的指針,這樣后續(xù)再調(diào)用 current 宏的時(shí)候,就指向了下一個(gè)指針:

      // arch/arm64/include/asm/current.h:15 static struct task_struct *get_current(void) {     unsigned long sp_el0;     asm ("mrs %0, sp_el0" : "=r" (sp_el0));     return (struct task_struct *)sp_el0; } // current 宏,很多地方會(huì)使用到 #define current get_current()

      進(jìn)程上下文切換的核心邏輯到這里就結(jié)束了,最后我們做下小結(jié)。

      5.3 context_switch() 小結(jié)

      進(jìn)程上下文切換,核心要切換的是虛擬內(nèi)存及一些通用寄存器。

      進(jìn)程切換虛擬內(nèi)存,需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁(yè)表,頁(yè)表也即不同進(jìn)程的虛擬內(nèi)存翻譯需要的 "map"。

      進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中,有一個(gè)間接字段 cpu_context 保存了通用寄存器的值,寄存器切換的本質(zhì)就是將上一個(gè)進(jìn)程的寄存器保存到 cpu_context 字段,然后再將下一個(gè)進(jìn)程的 cpu_context 數(shù)據(jù)結(jié)構(gòu)中的字段加載到寄存器中,至此完成進(jìn)程的切換。

      6 本文總結(jié)

      最后,我們?nèi)淖鱿驴偨Y(jié):

      進(jìn)程調(diào)度分為主動(dòng)(非搶占)和被動(dòng)調(diào)度(搶占),調(diào)度的核心邏輯在 __schedule() 方法中。

      進(jìn)程調(diào)度的核心邏輯分為兩個(gè)大步驟,其一是選擇一個(gè)合適的進(jìn)程,其二是進(jìn)行進(jìn)程切換。

      在選擇合適的進(jìn)程中,如果當(dāng)前邏輯 CPU 沒(méi)有可調(diào)度的進(jìn)程,就從其他 CPU 來(lái)調(diào)度,遷移的進(jìn)程盡可能靠近當(dāng)前 CPU。

      進(jìn)程調(diào)度的單位其實(shí)是調(diào)度實(shí)體,一個(gè)調(diào)度實(shí)體對(duì)應(yīng)一個(gè)或多個(gè)進(jìn)程,這樣就能夠在各個(gè)層次上完成公平調(diào)度,通過(guò)調(diào)度實(shí)體的虛擬時(shí)間選擇最優(yōu)調(diào)度實(shí)體對(duì)應(yīng)的進(jìn)程。

      進(jìn)程切換,本質(zhì)上就是切換虛擬內(nèi)存及通用寄存器。

      進(jìn)程調(diào)度的邏輯幾乎都完全遵循操作系統(tǒng)理論來(lái)設(shè)計(jì)的,學(xué)完操作系統(tǒng)之后,希望大家能夠理論聯(lián)系實(shí)際,對(duì)照著內(nèi)核去翻一翻源碼。

      贊(0)
      分享到: 更多 (0)
      網(wǎng)站地圖   滬ICP備18035694號(hào)-2    滬公網(wǎng)安備31011702889846號(hào)