這篇文章主要介紹“Linux進(jìn)程調(diào)度的邏輯是什么”，在日常操作中，相信很多人在Linux進(jìn)程調(diào)度的邏輯是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對(duì)大家解答”Linux進(jìn)程調(diào)度的邏輯是什么”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！
成都創(chuàng)新互聯(lián)是一家成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)，提供網(wǎng)頁設(shè)計(jì)，網(wǎng)站設(shè)計(jì)，網(wǎng)站制作，建網(wǎng)站，按需定制，網(wǎng)站開發(fā)公司，自2013年起是互聯(lián)行業(yè)建設(shè)者，服務(wù)者。以提升客戶品牌價(jià)值為核心業(yè)務(wù)，全程參與項(xiàng)目的網(wǎng)站策劃設(shè)計(jì)制作，前端開發(fā)，后臺(tái)程序制作以及后期項(xiàng)目運(yùn)營并提出專業(yè)建議和思路。
內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)首先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒有，執(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ì)算出來的。
進(jìn)程上下文切換，核心要切換的是虛擬內(nèi)存及一些通用寄存器。
進(jìn)程切換虛擬內(nèi)存，需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁表，頁表也即不同進(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)程的切換。
學(xué)過操作系統(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ì)簡要概括。
這篇文章，我們從內(nèi)核源碼的角度來剖析 Linux 是如何來實(shí)現(xiàn)進(jìn)程調(diào)度的核心邏輯，基本上遵從操作系統(tǒng)理論。
Linux 進(jìn)程調(diào)度的主函數(shù)是 schedule() 和 __schedule()，從源碼中可以看出兩者的關(guān)系：
重慶分公司
重慶分公司
// kernel/sched/core.c:3522
void schedule(void) {
...
// 調(diào)度過程中禁止搶占
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)度的過程中，禁止其他進(jìn)程搶占當(dāng)前進(jìn)程，說白了就是讓當(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)度邏輯之后，開啟搶占，也就是說，其他進(jìn)程可以剝奪當(dāng)前進(jìn)程的 CPU 了。
而如果某個(gè)進(jìn)程像個(gè)強(qiáng)盜一樣一直占著 CPU 不讓，內(nèi)核會(huì)通過搶占機(jī)制（比如上一篇文章提到的周期調(diào)度機(jī)制）進(jìn)行一次進(jìn)程調(diào)度，從而把當(dāng)前進(jìn)程從 CPU 上踢出去。
__schedule() 方法的框架便是這篇文章分析的主要內(nèi)容，由于代碼較多，我會(huì)挑選核心部分來描述。
我們先來看看 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)程切換的過程中，內(nèi)核會(huì)根據(jù)是主動(dòng)發(fā)起調(diào)度（preempt 為 fasle）還是被動(dòng)發(fā)起調(diào)度，來統(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 中，我們可以通過 pidstat 命令來查看一個(gè)進(jìn)程的主動(dòng)和被動(dòng)上下文切換的次數(shù)，我們寫一個(gè)簡單的 c 程序來做個(gè)測試：
// test.c #include#include int main() { while (1) { // 每隔一秒主動(dòng)休眠一次 // 即主動(dòng)讓出 CPU // 理論上每秒都會(huì)主動(dòng)切換一次 sleep(1) } }
然后編譯運(yùn)行
gcc test.c -o test ./test
通過 pidstat 來查看
可以看到，test 應(yīng)用程序每秒主動(dòng)切換一次進(jìn)程上下文，和我們的預(yù)期相符，對(duì)應(yīng)的上下文切換數(shù)據(jù)就是從 task_struct 中獲取的。
接下來，詳細(xì)分析進(jìn)程調(diào)度的兩個(gè)核心步驟:
通過 pick_next_task() 從就緒隊(duì)列中選中一個(gè)進(jìn)程。
通過 context_switch 執(zhí)行上下文切換。
我們回顧一下 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)度類型都是公平調(diào)度，我們拿公平調(diào)度相關(guān)的邏輯來分析。
從上述的核心框架中可以看到，3331 行先嘗試從公平調(diào)度類型的隊(duì)列中獲取進(jìn)程，3337 行，如果沒有找到，就把每個(gè) CPU 上的 IDLE 進(jìn)程取出來運(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
}接下來，我們聚焦公平調(diào)度類的進(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)度類隊(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ì)列沒有進(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:
// 通過負(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 上已無進(jìn)程可調(diào)度，則執(zhí)行負(fù)載邏輯，從其他 CPU 上遷移進(jìn)程過來；
如果當(dāng)前 CPU 上有進(jìn)程可調(diào)度，從隊(duì)列中選擇一個(gè)高優(yōu)進(jìn)程，所謂高優(yōu)進(jìn)程，即虛擬時(shí)間最小的進(jìn)程；
下面，我們分兩步拆解上述步驟。
內(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)程無法遷移。
負(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)度域。
內(nèi)核根據(jù)處理器與主存的距離將處理器分為兩個(gè) NUMA 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有兩個(gè)處理器。NUMA 指的是非一致性訪問，每個(gè) NUMA 節(jié)點(diǎ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。
我們在應(yīng)用程序里面，通過系統(tǒng) API 拿到的都是超線程，也可以叫做邏輯 CPU，下文統(tǒng)稱邏輯 CPU。
進(jìn)程在訪問一個(gè)某個(gè)地址的數(shù)據(jù)的時(shí)候，會(huì)先在 L1 Cache 中找，若未找到，則在 L2 Cache 中找，再未找到，則在 L3 Cache 上找，最后都沒找到，就訪問主存，而訪問速度方面 L1 > L2 > L3 > 主存，內(nèi)核遷移進(jìn)程的目標(biāo)是盡可能讓遷移出來的進(jìn)程能夠命中緩存。
內(nè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)，可見，內(nèi)核為了提升應(yīng)用性能真是煞費(fèi)苦心。
經(jīng)過負(fù)載均衡之后，當(dāng)前空閑的邏輯 CPU 進(jìn)程隊(duì)列很有可能已經(jīng)存在就緒進(jìn)程了，于是，接下來從這個(gè)隊(duì)列中獲取最合適的進(jìn)程。
接下來，我們把重點(diǎn)放到如何選擇高優(yōu)進(jìn)程，而在公平調(diào)度類中，會(huì)通過進(jìn)程的實(shí)際優(yōu)先級(jí)和運(yùn)行時(shí)間，來計(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)度類隊(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）開始，逐層選擇虛擬時(shí)間較少的調(diào)度實(shí)體進(jìn)行調(diào)度，直到最后一個(gè)調(diào)度實(shí)體是進(jìn)程。
內(nèi)核這樣做的原因是希望盡可能在每個(gè)層次上，都能夠保證調(diào)度是公平的。
拿 Docker 容器的例子來說，一個(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í)間總和來和宿主機(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;
// 如果沒找到或者樹中的最小虛擬時(shí)間的進(jìn)程
// 還沒當(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)。
而下面通過 __pick_first_entity() 方法，我們了解到，公平調(diào)度隊(duì)列 cfs_rq 中的調(diào)度實(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
// 緩存了紅黑樹最左側(cè)節(jié)點(diǎn)
#define rb_first_cached(root) (root)->rb_leftmost通過以上分析，我們依然通過一個(gè) Docker 的例子來分析： 一個(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，下面我們分情況來討論進(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é)束了，我們來做下小結(jié)。
內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒有，執(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ì)算出來的。
選中一個(gè)合適的進(jìn)程之后，接下來就要執(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)，下面，我們展開這兩段邏輯。
首先，簡要介紹一下虛擬內(nèi)存的幾個(gè)知識(shí)點(diǎn)：
進(jìn)程無法直接訪問到物理內(nèi)存，而是通過虛擬內(nèi)存到物理內(nèi)存的映射機(jī)制間接訪問到物理內(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)程即可通過內(nèi)存共享進(jìn)程通信。
進(jìn)程通過多級(jí)頁表機(jī)制來執(zhí)行虛擬內(nèi)存到物理內(nèi)存的映射，如果我們簡單地把這個(gè)機(jī)制當(dāng)做一個(gè) map<虛擬地址，物理地址> 數(shù)據(jù)結(jié)構(gòu)的話，那么可以理解為不同的進(jìn)程有維護(hù)著不同的 map；
map<虛擬地址，物理地址> 的翻譯是通過多級(jí)頁表來實(shí)現(xiàn)的，訪問多級(jí)頁表需要多次訪問內(nèi)存，效率太差，因此，內(nèi)核使用 TLB 緩存頻繁被訪問的 <虛擬地址，物理地址> 的項(xiàng)目，感謝局部性原理。
由于不同進(jìn)程可以有相同的虛擬地址，這些虛擬地址往往指向了不同的物理地址，因此，TLB 實(shí)際上是通過
進(jìn)程的虛擬地址空間用數(shù)據(jù)結(jié)構(gòu) mm_struct 來描述，進(jìn)程數(shù)據(jù)結(jié)構(gòu) task_struct 中的 mm 字段就指向此數(shù)據(jù)結(jié)構(gòu)，而上述所說的進(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);
}接下來，調(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
// 切換頁表，及切換我們上述中的 "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 通過虛擬地址翻譯出來的物理地址，就屬于下個(gè)進(jìn)程的。
拿到下一個(gè)進(jìn)程的 "map"，也就是頁表，對(duì)應(yīng)的字段是 "mm->pgd"，然后執(zhí)行頁表切換邏輯，這樣后續(xù)如果 TLB 沒命中，當(dāng)前 CPU 就能夠知道通過哪個(gè) "map" 來翻譯虛擬地址。
cpu_switch_mm 涉及的匯編代碼較多，這里就不貼了，本質(zhì)上就是將 ASID 和頁表（"map"）的信息綁定到對(duì)應(yīng)的寄存器。
虛擬內(nè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è)進(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));
我們來分析一下對(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ǔ)就可以分析出來。
上述匯編中，最后一行 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é)。
進(jìn)程上下文切換，核心要切換的是虛擬內(nèi)存及一些通用寄存器。
進(jìn)程切換虛擬內(nèi)存，需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁表，頁表也即不同進(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)程的切換。
到此，關(guān)于“Linux進(jìn)程調(diào)度的邏輯是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
