開學(xué)之后瓣赂，作息一直很局促劲件，喘不過氣來
借著高操這門課峭沦，應(yīng)該會把Linux源碼好好讀一讀
今天先借膽來談一下Linux下的線程調(diào)度策略
PS: 以下解析的Linux kernel版本號為4.19.25
Thread schedule
Motivation
首先跌造，為什么要有線程調(diào)度這種東西
主要是因為人民日益增長的CPU需求和同落后的I/O速度之間的矛盾
為了不讓沒準備好的CPU上戰(zhàn)場埠胖，也為了降低進程之間的通信成本
設(shè)計了一套線程狀態(tài)體系定罢，從三狀態(tài)笤虫，五狀態(tài)，到七狀態(tài)
于是因為線程帶上了這些狀態(tài)，就需要根據(jù)狀態(tài)對線程進行一系列的操作
一開始想的挺好的琼蚯，把線程按狀態(tài)分堆之后涨缚，各個狀態(tài)應(yīng)該井然有序的工作
但事實上荞驴，隨著工業(yè)技術(shù)的發(fā)展迎变，線程數(shù)量已經(jīng)到了一個十分恐怖的數(shù)量蓖乘，
如何公平的調(diào)度，更高效的調(diào)度峦睡，這成為了設(shè)計OS的一個難點
傳統(tǒng)的線程調(diào)度算法有SJF(短作業(yè)優(yōu)先)翎苫，SRTN(最短剩余時間優(yōu)先), HRRN(最高響應(yīng)比優(yōu)先), RR(輪轉(zhuǎn)), HPF(優(yōu)先級)等等
這些算法都有自己的有點，也有自己的缺點
CFS
Linux使用的是帶時間片的動態(tài)優(yōu)先級搶占式調(diào)度模式, 被稱之為公平調(diào)度CFS的算法
利用nice值+實時優(yōu)先級+時間片共同維護線程的優(yōu)先級
而這個優(yōu)先級隊列榨了，也就是就緒態(tài)隊列煎谍，Linux是用紅黑樹來維護的
(回想一下Java的CurrentHashMap和Linux kernel的schedule都是維護紅黑樹，所以DS要學(xué)學(xué)好呀)
Linux中對nice的處理和Unix不太一樣
在Unix中如果有兩個同nice值的進程龙屉，那么他們都將分配到一半的時間片呐粘，一般為5ms的時間，在這段時間內(nèi)CPU完全屬于占用的進程
理想狀態(tài)下線程調(diào)度應(yīng)該實現(xiàn)均衡劃分任務(wù)叔扼，對待相同優(yōu)先級的進程應(yīng)該是共同使用這段時間片10ms事哭，各占有CPU一半的能力
于是Linux就提出公平算法CFS，通過計算所有就緒態(tài)進程的需要CPU時間瓜富，計算出一個總的CPU需要時間
根據(jù)這個CPU時間去盡可能根據(jù)各個進程的實際需要來進行分配，而原來在Unix中直接當(dāng)做優(yōu)先級的nice值現(xiàn)在用于分配各個進程實際使用權(quán)重的標準
其具體的計算公式見右weight = 1024/(1.25^nice)
可以發(fā)現(xiàn)降盹，這樣的轉(zhuǎn)換能保證各個進程間權(quán)重比與nice的差值之間保持一致
這樣就能減小原來在Unix中單純使用nice值進程權(quán)重劃分造成的權(quán)重與nice值絕對大小有較大關(guān)系的情況
Souce code
CFS的具體實現(xiàn)細節(jié)与柑，需要對Linux kernel的源碼進行閱讀
通過對Linux kernel4.19.25代碼的閱讀，發(fā)現(xiàn)Linux關(guān)于線程調(diào)度的代碼大致可分為時間記錄蓄坏，進程選擇价捧，調(diào)度器入口，睡眠喚醒涡戳，搶占五部分
其中有關(guān)等待態(tài)的操作主要針對紅黑樹進行操作结蟋，有關(guān)掛起態(tài)的主要是鏈表的操作
時間記錄
調(diào)度器需要記錄當(dāng)前調(diào)度周期內(nèi)，進程還剩下多少時間片可用渔彰。
Linux中的調(diào)度器實體class定義于<include/linux/sched.h>文件中嵌屎。
struct sched_entity {
/* For load-balancing: 負責(zé)使得調(diào)度盡量均衡的模塊 */
struct load_weight load; // 優(yōu)先級
unsigned long runnable_weight; // 就緒態(tài)中的權(quán)值
struct rb_node run_node; // 紅黑樹節(jié)點
struct list_head group_node; // 所在進程組
unsigned int on_rq; // 是否在紅黑樹隊列中
u64 exec_start; // 線程開始時間
u64 sum_exec_runtime; // 線程總運行時間
u64 vruntime; // 虛擬運行時間
u64 prev_sum_exec_runtime; // 上個調(diào)度周期總運行時間
u64 nr_migrations;
struct sched_statistics statistics;
};
上面的代碼中有一項叫做vruntime，直譯就是虛擬運行時間恍涂，簡單的理解可以認為是帶權(quán)的運行時間宝惰，利用一個權(quán)值來控制時間的快慢(好像有點恐怖 ??)
CFS利用vruntime來記錄當(dāng)前進程運行時間以及還需要運行的時間。其源碼位于<kernel/sched/fair.c>
/*
* Update the current task's runtime statistics.
*/
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;
// 獲得最后一次Switch Thread至今耗時
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now; // 更新開始執(zhí)行時間
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr); // 計算vruntime
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cgroup_account_cputime(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
上述函數(shù)計算當(dāng)前進程的已執(zhí)行時間再沧，存放于變量delta_exec尼夺，然后調(diào)用函數(shù)calc_delta_fair更新vruntime值
而計算好的vruntime值將會在后面用作FindNextToRun函數(shù)的判斷。
Next進程選擇
選擇NextThread是調(diào)度算法的核心。在Linux中淤堵，通過計算vruntime值來實現(xiàn)CFS算法寝衫。
在Linux中利用紅黑樹來維護可運行進程的隊列。紅黑樹因為其自平衡的特性拐邪，在這個變vruntime的場景下特別適用竞端，而且紅黑樹維護代價，遍歷代價都比較低庙睡。
在這個紅黑樹上存儲了Linux系統(tǒng)中所有可運行的進程事富，每個節(jié)點的值就是他們的vruntime值，那么這棵紅黑樹上最小的節(jié)點乘陪，就是其最左節(jié)點统台。
維護進程等待隊列，就是對紅黑樹進行插入啡邑，刪除操作
這一部分搜索紅黑樹尋找最小節(jié)點的代碼也在<kernel/sched/fair.c>中贱勃。
可以看出其維護了一些規(guī)則，比如說以前換出去過的進程優(yōu)先級比較好谤逼，剛?cè)腙牭倪M程需要單獨比較一下（vruntime值可能還沒有更新）贵扰。
就緒態(tài)進程隊列的新增相對于紅黑樹插入新的節(jié)點。這一部分代碼位于<kernel/sched/fair.c>的enqueue_entity函數(shù)中流部。
從上面的代碼可以看出queue_entity()函數(shù)主要用于更新vruntime戚绕，隊列信息等等。真正做紅黑樹插入的邏輯實際上在__queue_entity()函數(shù)中枝冀。
和插入相似的還有從隊列中刪除節(jié)點舞丛，這個就不再贅述。
調(diào)度器入口
Linux在實現(xiàn)進程調(diào)度的時候提供了一個統(tǒng)一的調(diào)度器入口果漾，在這個入口中選擇最高優(yōu)先級的調(diào)度類球切，每個調(diào)度類擁有自己的進程隊列，相對于一個多隊列調(diào)度算法绒障。
關(guān)于調(diào)度器入口的代碼定義在<kernel/sched/core.c>吨凑，以優(yōu)先級為序，依次檢查每個調(diào)度類中的進程隊列户辱。
睡眠&喚醒
在Linux中進程的掛起態(tài)鸵钝，分為兩種，一種是能收到信號signal焕妙，一種是忽略signal蒋伦。和就緒態(tài)用紅黑樹來維護不一樣，這里的掛起態(tài)隊列用一個簡單的鏈表結(jié)構(gòu)來實現(xiàn)焚鹊。
具體來說是利用wait_queue_head的結(jié)構(gòu)來構(gòu)造一個等待隊列痕届。
struct wait_queue_head {
spinlock_t lock; // 自旋鎖保持一致性
struct list_head head;
};
掛起態(tài)和就緒態(tài)的轉(zhuǎn)換涉及到紅黑樹出樹+鏈表入隊韧献，鏈表出隊+紅黑樹插入，部分代碼和上面所述的就緒態(tài)隊列維護一致
搶占
Linux的線程調(diào)度是可搶占的研叫，在實際操作過程中搶占的現(xiàn)象十分普遍
比如說在Linux系統(tǒng)上開了一個vim編輯器锤窑，然后又在后臺跑了一個shell命令，因為交互的實時性需要嚷炉，你在vim中編輯的時候渊啰，就發(fā)生了搶占現(xiàn)象。
