一文講解Linux進(jìn)程調(diào)度器-基礎(chǔ)
說明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
1. 概念
1.1 進(jìn)程
從教科書上，我們都能知道：進(jìn)程是資源分配的最小單位，而線程是CPU調(diào)度的的最小單位。
進(jìn)程不僅包括可執(zhí)行程序的代碼段，還包括一系列的資源，比如：打開的文件、內(nèi)存、CPU時(shí)間、信號(hào)量、多個(gè)執(zhí)行線程流等等。而線程可以共享進(jìn)程內(nèi)的資源空間。
在Linux內(nèi)核中，進(jìn)程和線程都使用
struct task_struct結(jié)構(gòu)來進(jìn)行抽象描述。進(jìn)程的虛擬地址空間分為用戶虛擬地址空間和內(nèi)核虛擬地址空間，所有進(jìn)程共享內(nèi)核虛擬地址空間，沒有用戶虛擬地址空間的進(jìn)程稱為內(nèi)核線程。
Linux內(nèi)核使用task_struct結(jié)構(gòu)來抽象，該結(jié)構(gòu)包含了進(jìn)程的各類信息及所擁有的資源，比如進(jìn)程的狀態(tài)、打開的文件、地址空間信息、信號(hào)資源等等。task_struct結(jié)構(gòu)很復(fù)雜，下邊只針對(duì)與調(diào)度相關(guān)的某些字段進(jìn)行介紹。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?
1.2 進(jìn)程狀態(tài)
上圖中左側(cè)為操作系統(tǒng)中通俗的進(jìn)程三狀態(tài)模型，右側(cè)為L(zhǎng)inux對(duì)應(yīng)的進(jìn)程狀態(tài)切換。每一個(gè)標(biāo)志描述了進(jìn)程的當(dāng)前狀態(tài)，這些狀態(tài)都是互斥的；
Linux中的
就緒態(tài)和運(yùn)行態(tài)對(duì)應(yīng)的都是TASK_RUNNING標(biāo)志位，就緒態(tài)表示進(jìn)程正處在隊(duì)列中，尚未被調(diào)度；運(yùn)行態(tài)則表示進(jìn)程正在CPU上運(yùn)行；
內(nèi)核中主要的狀態(tài)字段定義如下
1.3 scheduler 調(diào)度器
所謂調(diào)度，就是按照某種調(diào)度的算法，從進(jìn)程的就緒隊(duì)列中選取進(jìn)程分配CPU，主要是協(xié)調(diào)對(duì)CPU等的資源使用。進(jìn)程調(diào)度的目標(biāo)是最大限度利用CPU時(shí)間。
內(nèi)核默認(rèn)提供了5個(gè)調(diào)度器，Linux內(nèi)核使用struct sched_class來對(duì)調(diào)度器進(jìn)行抽象：
Stop調(diào)度器， stop_sched_class：優(yōu)先級(jí)最高的調(diào)度類，可以搶占其他所有進(jìn)程，不能被其他進(jìn)程搶占；Deadline調(diào)度器， dl_sched_class：使用紅黑樹，把進(jìn)程按照絕對(duì)截止期限進(jìn)行排序，選擇最小進(jìn)程進(jìn)行調(diào)度運(yùn)行；RT調(diào)度器， rt_sched_class：實(shí)時(shí)調(diào)度器，為每個(gè)優(yōu)先級(jí)維護(hù)一個(gè)隊(duì)列；CFS調(diào)度器， cfs_sched_class：完全公平調(diào)度器，采用完全公平調(diào)度算法，引入虛擬運(yùn)行時(shí)間概念；IDLE-Task調(diào)度器， idle_sched_class：空閑調(diào)度器，每個(gè)CPU都會(huì)有一個(gè)idle線程，當(dāng)沒有其他進(jìn)程可以調(diào)度時(shí)，調(diào)度運(yùn)行idle線程；
Linux內(nèi)核提供了一些調(diào)度策略供用戶程序來選擇調(diào)度器，其中Stop調(diào)度器和IDLE-Task調(diào)度器，僅由內(nèi)核使用，用戶無法進(jìn)行選擇：
SCHED_DEADLINE：限期進(jìn)程調(diào)度策略，使task選擇Deadline調(diào)度器來調(diào)度運(yùn)行；SCHED_RR：實(shí)時(shí)進(jìn)程調(diào)度策略，時(shí)間片輪轉(zhuǎn)，進(jìn)程用完時(shí)間片后加入優(yōu)先級(jí)對(duì)應(yīng)運(yùn)行隊(duì)列的尾部，把CPU讓給同優(yōu)先級(jí)的其他進(jìn)程；SCHED_FIFO：實(shí)時(shí)進(jìn)程調(diào)度策略，先進(jìn)先出調(diào)度沒有時(shí)間片，沒有更高優(yōu)先級(jí)的情況下，只能等待主動(dòng)讓出CPU；SCHED_NORMAL：普通進(jìn)程調(diào)度策略，使task選擇CFS調(diào)度器來調(diào)度運(yùn)行；SCHED_BATCH：普通進(jìn)程調(diào)度策略，批量處理，使task選擇CFS調(diào)度器來調(diào)度運(yùn)行；SCHED_IDLE：普通進(jìn)程調(diào)度策略，使task以最低優(yōu)先級(jí)選擇CFS調(diào)度器來調(diào)度運(yùn)行；
1.4 runqueue 運(yùn)行隊(duì)列
每個(gè)CPU都有一個(gè)運(yùn)行隊(duì)列，每個(gè)調(diào)度器都作用于運(yùn)行隊(duì)列；
分配給CPU的task，作為調(diào)度實(shí)體加入到運(yùn)行隊(duì)列中；
task首次運(yùn)行時(shí)，如果可能，盡量將它加入到父task所在的運(yùn)行隊(duì)列中（分配給相同的CPU，緩存affinity會(huì)更高，性能會(huì)有改善）；
Linux內(nèi)核使用struct rq結(jié)構(gòu)來描述運(yùn)行隊(duì)列，關(guān)鍵字段如下：
2.5 task_group 任務(wù)分組
利用任務(wù)分組的機(jī)制，可以設(shè)置或限制任務(wù)組對(duì)CPU的利用率，比如將某些任務(wù)限制在某個(gè)區(qū)間內(nèi)，從而不去影響其他任務(wù)的執(zhí)行效率；
引入
task_group后，調(diào)度器的調(diào)度對(duì)象不僅僅是進(jìn)程了，Linux內(nèi)核抽象出了sched_entity/sched_rt_entity/sched_dl_entity描述調(diào)度實(shí)體，調(diào)度實(shí)體可以是進(jìn)程或task_group；使用數(shù)據(jù)結(jié)構(gòu)
struct task_group來描述任務(wù)組，任務(wù)組在每個(gè)CPU上都會(huì)維護(hù)一個(gè)CFS調(diào)度實(shí)體、CFS運(yùn)行隊(duì)列，RT調(diào)度實(shí)體，RT運(yùn)行隊(duì)列；
Linux內(nèi)核使用struct task_group來描述任務(wù)組，關(guān)鍵的字段如下：
2. 調(diào)度程序
調(diào)度程序依靠幾個(gè)函數(shù)來完成調(diào)度工作的，下邊將介紹幾個(gè)關(guān)鍵的函數(shù)。
主動(dòng)調(diào)度 -?
schedule()
schedule()函數(shù)，是進(jìn)程調(diào)度的核心函數(shù)，大體的流程如上圖所示。核心的邏輯：選擇另外一個(gè)進(jìn)程來替換掉當(dāng)前運(yùn)行的進(jìn)程。進(jìn)程的選擇是通過進(jìn)程所使用的調(diào)度器中的
pick_next_task函數(shù)來實(shí)現(xiàn)的，不同的調(diào)度器實(shí)現(xiàn)的方法不一樣；進(jìn)程的替換是通過context_switch()來完成切換的，具體的細(xì)節(jié)后續(xù)的文章再深入分析。
2. 周期調(diào)度 -?schedule_tick()
時(shí)鐘中斷處理程序中，調(diào)用
schedule_tick()函數(shù)；時(shí)鐘中斷是調(diào)度器的脈搏，內(nèi)核依靠周期性的時(shí)鐘來處理器CPU的控制權(quán)；
時(shí)鐘中斷處理程序，檢查當(dāng)前進(jìn)程的執(zhí)行時(shí)間是否超額，如果超額則設(shè)置重新調(diào)度標(biāo)志(
_TIF_NEED_RESCHED)；時(shí)鐘中斷處理函數(shù)返回時(shí)，被中斷的進(jìn)程如果在用戶模式下運(yùn)行，需要檢查是否有重新調(diào)度標(biāo)志，設(shè)置了則調(diào)用
schedule()調(diào)度；
3. 高精度時(shí)鐘調(diào)度 -?hrtick()
高精度時(shí)鐘調(diào)度，與周期性調(diào)度類似，不同點(diǎn)在于周期調(diào)度的精度為ms級(jí)別，而高精度調(diào)度的精度為ns級(jí)別；
高精度時(shí)鐘調(diào)度，需要有對(duì)應(yīng)的硬件支持；
4. 進(jìn)程喚醒時(shí)調(diào)度 -?wake_up_process()
喚醒進(jìn)程時(shí)調(diào)用
wake_up_process()函數(shù)，被喚醒的進(jìn)程可能搶占當(dāng)前的進(jìn)程；
上述講到的幾個(gè)函數(shù)都是常用于調(diào)度時(shí)調(diào)用。此外，在創(chuàng)建新進(jìn)程時(shí)，或是在內(nèi)核搶占時(shí)，也會(huì)出現(xiàn)一些調(diào)度點(diǎn)。
原文作者：LoyenWang
