吐血整理 | 肝翻 Linux 進(jìn)程調(diào)度所有知識(shí)點(diǎn)
前面我們重點(diǎn)分析了如何通過(guò) fork, vfork, pthread_create 去創(chuàng)建一個(gè)進(jìn)程或者線程，以及后面說(shuō)了它們共同調(diào)用 do_fork 的實(shí)現(xiàn)?，F(xiàn)在已經(jīng)知道一個(gè)進(jìn)程是如何創(chuàng)建的，但是進(jìn)程何時(shí)被執(zhí)行，需要調(diào)度器來(lái)選擇。所以這一節(jié)我們介紹下進(jìn)程調(diào)度和進(jìn)程切換的詳情。
進(jìn)程的分類(lèi)
在 CPU 的角度看進(jìn)程行為的話，可以分為兩類(lèi)：
CPU 消耗型：此類(lèi)進(jìn)程就是一直占用 CPU 計(jì)算，CPU 利用率很高 IO 消耗型：此類(lèi)進(jìn)程會(huì)涉及到 IO，需要和用戶(hù)交互，比如鍵盤(pán)輸入，占用 CPU 不是很高，只需要 CPU 的一部分計(jì)算，大多數(shù)時(shí)間是在等待 IO
CPU 消耗型進(jìn)程需要高的吞吐率，IO 消耗型進(jìn)程需要強(qiáng)的響應(yīng)性，這兩點(diǎn)都是調(diào)度器需要考慮的。
為了更快響應(yīng) IO 消耗型進(jìn)程，內(nèi)核提供了一個(gè)搶占(preempt)機(jī)制，使優(yōu)先級(jí)更高的進(jìn)程，去搶占優(yōu)先級(jí)低的進(jìn)程運(yùn)行。內(nèi)核用以下宏來(lái)選擇內(nèi)核是否打開(kāi)搶占機(jī)制：
CONFIG_PREEMPT_NONE: 不打開(kāi)搶占，主要是面向服務(wù)器。此配置下，CPU 在計(jì)算時(shí)，當(dāng)輸入鍵盤(pán)之后，因?yàn)闆](méi)有搶占，可能需要一段時(shí)間等待鍵盤(pán)輸入的進(jìn)程才會(huì)被 CPU 調(diào)度。 CONFIG_PREEMPT : 打開(kāi)搶占，一般多用于手機(jī)設(shè)備。此配置下，雖然會(huì)影響吞吐率，但可以及時(shí)響應(yīng)用戶(hù)的輸入操作。
調(diào)度相關(guān)的數(shù)據(jù)結(jié)構(gòu)
先來(lái)看幾個(gè)相關(guān)的數(shù)據(jù)結(jié)構(gòu)：
task_struct
我們先把 task_struct 中和調(diào)度相關(guān)的結(jié)構(gòu)拎出來(lái)：
struct task_struct {
......
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
......
struct sched_dl_entity dl;
......
unsigned int policy;
......
}
struct sched_class：對(duì)調(diào)度器進(jìn)行抽象，一共分為5類(lèi)。
Stop調(diào)度器：優(yōu)先級(jí)最高的調(diào)度類(lèi)，可以搶占其他所有進(jìn)程，不能被其他進(jìn)程搶占； Deadline調(diào)度器：使用紅黑樹(shù)，把進(jìn)程按照絕對(duì)截止期限進(jìn)行排序，選擇最小進(jìn)程進(jìn)行調(diào)度運(yùn)行； RT調(diào)度器：為每個(gè)優(yōu)先級(jí)維護(hù)一個(gè)隊(duì)列； CFS調(diào)度器：采用完全公平調(diào)度算法，引入虛擬運(yùn)行時(shí)間概念； IDLE-Task調(diào)度器：每個(gè)CPU都會(huì)有一個(gè)idle線程，當(dāng)沒(méi)有其他進(jìn)程可以調(diào)度時(shí)，調(diào)度運(yùn)行idle線程；
unsigned int policy：進(jìn)程的調(diào)度策略有6種，用戶(hù)可以調(diào)用調(diào)度器里的不同調(diào)度策略。
SCHED_DEADLINE：使task選擇Deadline調(diào)度器來(lái)調(diào)度運(yùn)行 SCHED_RR：時(shí)間片輪轉(zhuǎn)，進(jìn)程用完時(shí)間片后加入優(yōu)先級(jí)對(duì)應(yīng)運(yùn)行隊(duì)列的尾部，把CPU讓給同優(yōu)先級(jí)的其他進(jìn)程； SCHED_FIFO：先進(jìn)先出調(diào)度沒(méi)有時(shí)間片，沒(méi)有更高優(yōu)先級(jí)的情況下，只能等待主動(dòng)讓出CPU； SCHED_NORMAL：使task選擇CFS調(diào)度器來(lái)調(diào)度運(yùn)行； SCHED_BATCH：批量處理，使task選擇CFS調(diào)度器來(lái)調(diào)度運(yùn)行； SCHED_IDLE：使task以最低優(yōu)先級(jí)選擇CFS調(diào)度器來(lái)調(diào)度運(yùn)行；
struct sched_entity se：采用CFS算法調(diào)度的普通非實(shí)時(shí)進(jìn)程的調(diào)度實(shí)體。 struct sched_rt_entity rt：采用Roound-Robin或者FIFO算法調(diào)度的實(shí)時(shí)調(diào)度實(shí)體。 struct sched_dl_entity dl：采用EDF算法調(diào)度的實(shí)時(shí)調(diào)度實(shí)體。
分配給 CPU 的 task，作為調(diào)度實(shí)體加入到運(yùn)行隊(duì)列中。
runqueue 運(yùn)行隊(duì)列
runqueue 運(yùn)行隊(duì)列是本 CPU 上所有可運(yùn)行進(jìn)程的隊(duì)列集合。每個(gè) CPU 都有一個(gè)運(yùn)行隊(duì)列，每個(gè)運(yùn)行隊(duì)列中有三個(gè)調(diào)度隊(duì)列，task 作為調(diào)度實(shí)體加入到各自的調(diào)度隊(duì)列中。
struct rq {
......
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
......
}
三個(gè)調(diào)度隊(duì)列：
struct cfs_rq cfs：CFS調(diào)度隊(duì)列 struct rt_rq rt：RT調(diào)度隊(duì)列 struct dl_rq dl：DL調(diào)度隊(duì)列
cfs_rq：跟蹤就緒隊(duì)列信息以及管理就緒態(tài)調(diào)度實(shí)體，并維護(hù)一棵按照虛擬時(shí)間排序的紅黑樹(shù)。tasks_timeline->rb_root是紅黑樹(shù)的根，tasks_timeline->rb_leftmost指向紅黑樹(shù)中最左邊的調(diào)度實(shí)體，即虛擬時(shí)間最小的調(diào)度實(shí)體。
struct cfs_rq {
...
struct rb_root_cached tasks_timeline
...
};
sched_entity：可被內(nèi)核調(diào)度的實(shí)體。每個(gè)就緒態(tài)的調(diào)度實(shí)體sched_entity包含插入紅黑樹(shù)中使用的節(jié)點(diǎn)rb_node，同時(shí)vruntime成員記錄已經(jīng)運(yùn)行的虛擬時(shí)間。
struct sched_entity {
...
struct rb_node run_node;
...
u64 vruntime;
...
};
這些數(shù)據(jù)結(jié)構(gòu)的關(guān)系如下圖所示：
調(diào)度時(shí)刻
調(diào)度的本質(zhì)就是選擇下一個(gè)進(jìn)程，然后切換。在執(zhí)行調(diào)度之前需要設(shè)置調(diào)度標(biāo)記 TIF_NEED_RESCHED，然后在調(diào)度的時(shí)候會(huì)判斷當(dāng)前進(jìn)程有沒(méi)有被設(shè)置 TIF_NEED_RESCHED，如果設(shè)置則調(diào)用函數(shù) schedule 來(lái)進(jìn)行調(diào)度。
1. 設(shè)置調(diào)度標(biāo)記
為 CPU 上正在運(yùn)行的進(jìn)程 thread_info 結(jié)構(gòu)體里的 flags 成員設(shè)置 TIF_NEED_RESCHED。
那么，什么時(shí)候設(shè)置TIF_NEED_RESCHED呢 ？
scheduler_tick 時(shí)鐘中斷
wake_up_process 喚醒進(jìn)程的時(shí)候
do_fork 創(chuàng)建新進(jìn)程的時(shí)候
set_user_nice 修改進(jìn)程nice值的時(shí)候
smp_send_reschedule 負(fù)載均衡的時(shí)候
2. 執(zhí)行調(diào)度
Kernel 判斷當(dāng)前進(jìn)程標(biāo)記是否為 TIF_NEED_RESCHED，是的話調(diào)用 schedule 函數(shù)，執(zhí)行調(diào)度，切換上下文，這也是上面搶占(preempt)機(jī)制的本質(zhì)。那么在哪些情況下會(huì)執(zhí)行 schedule 呢？
用戶(hù)態(tài)搶占
ret_to_user 是異常觸發(fā)，系統(tǒng)調(diào)用，中斷處理完成后都會(huì)調(diào)用的函數(shù)。
內(nèi)核態(tài)搶占
可以看出無(wú)論是用戶(hù)態(tài)搶占，還是內(nèi)核態(tài)搶占，最終都會(huì)調(diào)用 schedule 函數(shù)來(lái)執(zhí)行真正的調(diào)度：
還記得調(diào)度的本質(zhì)嗎？調(diào)度的本質(zhì)就是選擇下一個(gè)進(jìn)程，然后切換。如上圖所示，用函數(shù) pick_next_task 選擇下一個(gè)進(jìn)程，其本質(zhì)就是調(diào)度算法的實(shí)現(xiàn)；用函數(shù) context_switch 完成進(jìn)程的切換，即進(jìn)程上下文的切換。下面我們分別看下這兩個(gè)核心功能。
調(diào)度算法
| 字段 | 版本 |
|---|---|
| O(n) 調(diào)度器 | linux0.11 - 2.4 |
| O(1) 調(diào)度器 | linux2.6 |
| CFS調(diào)度器 | linux2.6至今 |
O(n)
O(n) 調(diào)度器是在內(nèi)核2.4以及更早期版本采用的算法，O(n) 代表的是尋找一個(gè)合適的任務(wù)的時(shí)間復(fù)雜度。調(diào)度器定義了一個(gè) runqueue 的運(yùn)行隊(duì)列，將進(jìn)程的狀態(tài)變?yōu)?Running 的都會(huì)添加到此運(yùn)行隊(duì)列中，但是不管是實(shí)時(shí)進(jìn)程，還是普通進(jìn)程都會(huì)添加到這個(gè)運(yùn)行隊(duì)列中。當(dāng)需要從運(yùn)行隊(duì)列中選擇一個(gè)合適的任務(wù)時(shí)，就需要從隊(duì)列的頭遍歷到尾部，這個(gè)時(shí)間復(fù)雜度是O(n)，運(yùn)行隊(duì)列中的任務(wù)數(shù)目越大，調(diào)度器的效率就越低。
所以 O(n) 調(diào)度器有如下缺陷：
時(shí)間復(fù)雜度是 O(n)，運(yùn)行隊(duì)列中的任務(wù)數(shù)目越大，調(diào)度器的效率就越低。 實(shí)時(shí)進(jìn)程不能及時(shí)調(diào)度，因?yàn)閷?shí)時(shí)進(jìn)程和普通進(jìn)程在一個(gè)列表中，每次查實(shí)時(shí)進(jìn)程時(shí)，都需要全部掃描整個(gè)列表，所以實(shí)時(shí)進(jìn)程不是很“實(shí)時(shí)”。 SMP 系統(tǒng)不好，因?yàn)橹挥幸粋€(gè) runqueue，選擇下一個(gè)任務(wù)時(shí)，需要對(duì)這個(gè) runqueue 隊(duì)列進(jìn)行加鎖操作，當(dāng)任務(wù)較多的時(shí)候，則在臨界區(qū)的時(shí)間就比較長(zhǎng)，導(dǎo)致其余的 CPU 自旋浪費(fèi)。 CPU空轉(zhuǎn)的現(xiàn)象存在，因?yàn)橄到y(tǒng)中只有一個(gè)runqueue，當(dāng)運(yùn)行隊(duì)列中的任務(wù)少于 CPU 的個(gè)數(shù)時(shí)，其余的 CPU 則是 idle 狀態(tài)。
O(1)
內(nèi)核2.6采用了O(1) 調(diào)度器，讓每個(gè) CPU 維護(hù)一個(gè)自己的 runqueue，從而減少了鎖的競(jìng)爭(zhēng)。每一個(gè)runqueue 運(yùn)行隊(duì)列維護(hù)兩個(gè)鏈表，一個(gè)是 active 鏈表，表示運(yùn)行的進(jìn)程都掛載 active 鏈表中；一個(gè)是 expired 鏈表，表示所有時(shí)間片用完的進(jìn)程都掛載 expired 鏈表中。當(dāng) acitve 中無(wú)進(jìn)程可運(yùn)行時(shí)，說(shuō)明系統(tǒng)中所有進(jìn)程的時(shí)間片都已經(jīng)耗光，這時(shí)候則只需要調(diào)整 active 和 expired 的指針即可。每個(gè)優(yōu)先級(jí)數(shù)組包含140個(gè)優(yōu)先級(jí)隊(duì)列，也就是每個(gè)優(yōu)先級(jí)對(duì)應(yīng)一個(gè)隊(duì)列，其中前100個(gè)對(duì)應(yīng)實(shí)時(shí)進(jìn)程，后40個(gè)對(duì)應(yīng)普通進(jìn)程。如下圖所示：
總的來(lái)說(shuō) O(1) 調(diào)度器的出現(xiàn)是為了解決 O(n) 調(diào)度器不能解決的問(wèn)題，但 O(1) 調(diào)度器有個(gè)問(wèn)題，一個(gè)高優(yōu)先級(jí)多線程的應(yīng)用會(huì)比低優(yōu)先級(jí)單線程的應(yīng)用獲得更多的資源，這就會(huì)導(dǎo)致一個(gè)調(diào)度周期內(nèi)，低優(yōu)先級(jí)的應(yīng)用可能一直無(wú)法響應(yīng)，直到高優(yōu)先級(jí)應(yīng)用結(jié)束。CFS調(diào)度器就是站在一視同仁的角度解決了這個(gè)問(wèn)題，保證在一個(gè)調(diào)度周期內(nèi)每個(gè)任務(wù)都有執(zhí)行的機(jī)會(huì)，執(zhí)行時(shí)間的長(zhǎng)短，取決于任務(wù)的權(quán)重。下面詳細(xì)看下CFS調(diào)度器是如何動(dòng)態(tài)調(diào)整任務(wù)的運(yùn)行時(shí)間，達(dá)到公平調(diào)度的。
CFS 調(diào)度器
CFS是 Completely Fair Scheduler 簡(jiǎn)稱(chēng)，即完全公平調(diào)度器。CFS 調(diào)度器和以往的調(diào)度器不同之處在于沒(méi)有固定時(shí)間片的概念，而是公平分配 CPU 使用的時(shí)間。比如：2個(gè)優(yōu)先級(jí)相同的任務(wù)在一個(gè) CPU 上運(yùn)行，那么每個(gè)任務(wù)都將會(huì)分配一半的 CPU 運(yùn)行時(shí)間，這就是要實(shí)現(xiàn)的公平。
但現(xiàn)實(shí)中，必然是有的任務(wù)優(yōu)先級(jí)高，有的任務(wù)優(yōu)先級(jí)低。CFS 調(diào)度器引入權(quán)重 weight 的概念，用 weight 代表任務(wù)的優(yōu)先級(jí)，各個(gè)任務(wù)按照 weight 的比例分配 CPU 的時(shí)間。比如：2個(gè)任務(wù)A和B，A的權(quán)重是1024，B的權(quán)重是2048，則A占 1024/(1024+2048) = 33.3% 的 CPU 時(shí)間，B占 2048/(1024+2048)=66.7% 的 CPU 時(shí)間。
在引入權(quán)重之后，分配給進(jìn)程的時(shí)間計(jì)算公式如下：
實(shí)際運(yùn)行時(shí)間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和
CFS 調(diào)度器用nice值表示優(yōu)先級(jí)，取值范圍是[-20, 19]，nice和權(quán)重是一一對(duì)應(yīng)的關(guān)系。數(shù)值越小代表優(yōu)先級(jí)越大，同時(shí)也意味著權(quán)重值越大，nice值和權(quán)重之間的轉(zhuǎn)換關(guān)系：
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
數(shù)組值計(jì)算公式是：weight = 1024 / 1.25nice。
調(diào)度周期
如果一個(gè) CPU 上有 N 個(gè)優(yōu)先級(jí)相同的進(jìn)程，那么每個(gè)進(jìn)程會(huì)得到 1/N 的執(zhí)行機(jī)會(huì)，每個(gè)進(jìn)程執(zhí)行一段時(shí)間后，就被調(diào)出，換下一個(gè)進(jìn)程執(zhí)行。如果這個(gè) N 的數(shù)量太大，導(dǎo)致每個(gè)進(jìn)程執(zhí)行的時(shí)間很短，就要調(diào)度出去，那么系統(tǒng)的資源就消耗在進(jìn)程上下文切換上去了。
所以對(duì)于此問(wèn)題在 CFS 中則引入了調(diào)度周期，使進(jìn)程至少保證執(zhí)行0.75ms。調(diào)度周期的計(jì)算通過(guò)如下代碼：
static u64 __sched_period(unsigned long nr_running)
{
if (unlikely(nr_running > sched_nr_latency))
return nr_running * sysctl_sched_min_granularity;
else
return sysctl_sched_latency;
}
static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency = 6000000ULL;
unsigned int sysctl_sched_min_granularity = 750000ULL;
當(dāng)進(jìn)程數(shù)目小于8時(shí)，則調(diào)度周期等于6ms。當(dāng)進(jìn)程數(shù)目大于8時(shí)，則調(diào)度周期等于進(jìn)程的數(shù)目乘以0.75ms。
虛擬運(yùn)行時(shí)間
根據(jù)上面進(jìn)程實(shí)際運(yùn)行時(shí)間的公式，可以看出，權(quán)重不同的2個(gè)進(jìn)程的實(shí)際執(zhí)行時(shí)間是不相等的，但是 CFS 想保證每個(gè)進(jìn)程運(yùn)行時(shí)間相等，因此 CFS 引入了虛擬時(shí)間的概念。虛擬時(shí)間(vriture_runtime)和實(shí)際時(shí)間(wall_time)轉(zhuǎn)換公式如下：
vriture_runtime = (wall_time * NICE0_TO_weight) / weight
其中，NICE0_TO_weight 代表的是 nice 值等于0對(duì)應(yīng)的權(quán)重，即1024，weight 是該任務(wù)對(duì)應(yīng)的權(quán)重。
權(quán)重越大的進(jìn)程獲得的虛擬運(yùn)行時(shí)間越小，那么它將被調(diào)度器所調(diào)度的機(jī)會(huì)就越大，所以，CFS 每次調(diào)度原則是：總是選擇 vriture_runtime 最小的任務(wù)來(lái)調(diào)度。
為了能夠快速找到虛擬運(yùn)行時(shí)間最小的進(jìn)程，Linux 內(nèi)核使用紅黑樹(shù)來(lái)保存可運(yùn)行的進(jìn)程。CFS跟蹤調(diào)度實(shí)體sched_entity的虛擬運(yùn)行時(shí)間vruntime，將sched_entity通過(guò)enqueue_entity()和dequeue_entity()來(lái)進(jìn)行紅黑樹(shù)的出隊(duì)入隊(duì)，vruntime少的調(diào)度實(shí)體sched_entity排列到紅黑樹(shù)的左邊。
如上圖所示，紅黑樹(shù)的左節(jié)點(diǎn)比父節(jié)點(diǎn)小，而右節(jié)點(diǎn)比父節(jié)點(diǎn)大。所以查找最小節(jié)點(diǎn)時(shí)，只需要獲取紅黑樹(shù)的最左節(jié)點(diǎn)即可。
相關(guān)步驟如下：
每個(gè)sched_latency周期內(nèi)，根據(jù)各個(gè)任務(wù)的權(quán)重值，可以計(jì)算出運(yùn)行時(shí)間runtime； 運(yùn)行時(shí)間runtime可以轉(zhuǎn)換成虛擬運(yùn)行時(shí)間vruntime； 根據(jù)虛擬運(yùn)行時(shí)間的大小，插入到CFS紅黑樹(shù)中，虛擬運(yùn)行時(shí)間少的調(diào)度實(shí)體放置到左邊；
在下一次任務(wù)調(diào)度的時(shí)候，選擇虛擬運(yùn)行時(shí)間少的調(diào)度實(shí)體來(lái)運(yùn)行。pick_next_task 函數(shù)就是從從就緒隊(duì)列中選擇最適合運(yùn)行的調(diào)度實(shí)體，即虛擬時(shí)間最小的調(diào)度實(shí)體，下面我們看下 CFS 調(diào)度器如何通過(guò) pick_next_task 的回調(diào)函數(shù) pick_next_task_fair 來(lái)選擇下一個(gè)進(jìn)程的。
選擇下一個(gè)進(jìn)程
pick_next_task_fair 會(huì)判斷上一個(gè) task 的調(diào)度器是否是 CFS，這里我們默認(rèn)都是 CFS 調(diào)度：
update_curr
update_curr 函數(shù)用來(lái)更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間信息:
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = now - curr->exec_start; ------(1)
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now; ------(2)
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec; ------(3)
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr); ------(4)
update_min_vruntime(cfs_rq); ------(5)
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
delta_exec = now - curr->exec_start; 計(jì)算出當(dāng)前CFS運(yùn)行隊(duì)列的進(jìn)程，距離上次更新虛擬時(shí)間的差值 curr->exec_start = now; 更新exec_start的值 curr->sum_exec_runtime += delta_exec; 更新當(dāng)前進(jìn)程總共執(zhí)行的時(shí)間 通過(guò) calc_delta_fair 計(jì)算當(dāng)前進(jìn)程虛擬時(shí)間 通過(guò) update_min_vruntime 函數(shù)來(lái)更新CFS運(yùn)行隊(duì)列中最小的 vruntime 的值
pick_next_entity
pick_next_entity 函數(shù)會(huì)從就緒隊(duì)列中選擇最適合運(yùn)行的調(diào)度實(shí)體（虛擬時(shí)間最小的調(diào)度實(shí)體），即從 CFS 紅黑樹(shù)最左邊節(jié)點(diǎn)獲取一個(gè)調(diào)度實(shí)體。
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq); ------(1)
struct sched_entity *se;
/*
* If curr is set we have to see if its left of the leftmost entity
* still in the tree, provided there was anything in the tree at all.
*/
if (!left || (curr && entity_before(curr, left)))
left = curr;
se = left; /* ideally we run the leftmost entity */
/*
* Avoid running the skip buddy, if running something else can
* be done without getting too unfair.
*/
if (cfs_rq->skip == se) {
struct sched_entity *second;
if (se == curr) {
second = __pick_first_entity(cfs_rq); ------(2)
} else {
second = __pick_next_entity(se); ------(3)
if (!second || (curr && entity_before(curr, second)))
second = curr;
}
if (second && wakeup_preempt_entity(second, left) < 1)
se = second;
}
/*
* Prefer last buddy, try to return the CPU to a preempted task.
*/
if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
se = cfs_rq->last;
/*
* Someone really wants this to run. If it's not unfair, run it.
*/
if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
se = cfs_rq->next;
clear_buddies(cfs_rq, se);
return se;
}
從樹(shù)中挑選出最左邊的節(jié)點(diǎn) 選擇最左的那個(gè)調(diào)度實(shí)體 left 摘取紅黑樹(shù)上第二左的進(jìn)程節(jié)點(diǎn)
put_prev_entity
put_prev_entity 會(huì)調(diào)用 __enqueue_entity 將prev進(jìn)程(即current進(jìn)程)加入到 CFS 隊(duì)列 rq 上的紅黑樹(shù)，然后將 cfs_rq->curr 設(shè)置為空。
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node; //紅黑樹(shù)根節(jié)點(diǎn)
struct rb_node *parent = NULL;
struct sched_entity *entry;
bool leftmost = true;
/*
* Find the right place in the rbtree:
*/
while (*link) { ------(1)
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/*
* We dont care about collisions. Nodes with
* the same key stay together.
*/
if (entity_before(se, entry)) { ------(2)
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = false;
}
}
rb_link_node(&se->run_node, parent, link); ------(3)
rb_insert_color_cached(&se->run_node, ------(4)
&cfs_rq->tasks_timeline, leftmost);
}
從紅黑樹(shù)中找到 se 所應(yīng)該在的位置 以 se->vruntime 值為鍵值進(jìn)行紅黑樹(shù)結(jié)點(diǎn)的比較 將新進(jìn)程的節(jié)點(diǎn)加入到紅黑樹(shù)中 為新插入的結(jié)點(diǎn)進(jìn)行著色
set_next_entity
set_next_entity 會(huì)調(diào)用 __dequeue_entity 將下一個(gè)選擇的進(jìn)程從 CFS 隊(duì)列的紅黑樹(shù)中刪除，然后將 CFS 隊(duì)列的 curr 指向進(jìn)程的調(diào)度實(shí)體。
進(jìn)程上下文切換
理解了下一個(gè)進(jìn)程的選擇后，就需要做當(dāng)前進(jìn)程和所選進(jìn)程的上下文切換。
Linux 內(nèi)核用函數(shù) context_switch 進(jìn)行進(jìn)程的上下文切換，進(jìn)程上下文切換主要涉及到兩部分：進(jìn)程地址空間切換和處理器狀態(tài)切換：
進(jìn)程的地址空間切換
將下一個(gè)進(jìn)程的 pgd 虛擬地址轉(zhuǎn)化為物理地址存放在 ttbr0_el1 中(這是用戶(hù)空間的頁(yè)表基址寄存器)，當(dāng)訪問(wèn)用戶(hù)空間地址的時(shí)候 mmu 會(huì)通過(guò)這個(gè)寄存器來(lái)做遍歷頁(yè)表獲得物理地址。完成了這一步，也就完成了進(jìn)程的地址空間切換，確切的說(shuō)是進(jìn)程的虛擬地址空間切換。
寄存器狀態(tài)切換
其中 x19-x28 是 arm64 架構(gòu)規(guī)定需要調(diào)用保存的寄存器，可以看到處理器狀態(tài)切換的時(shí)候?qū)⑶耙粋€(gè)進(jìn)程（prev）的 x19-x28，fp,sp,pc 保存到了進(jìn)程描述符的 cpu_contex 中，然后將即將執(zhí)行的進(jìn)程 (next) 描述符的 cpu_contex 的 x19-x28，fp,sp,pc 恢復(fù)到相應(yīng)寄存器中，而且將 next 進(jìn)程的進(jìn)程描述符 task_struct 地址存放在 sp_el0 中，用于通過(guò) current 找到當(dāng)前進(jìn)程，這樣就完成了處理器的狀態(tài)切換。
