什么是調(diào)度？為什么要調(diào)度？

什么是調(diào)度？按照某種調(diào)度算法，從進(jìn)程的ready隊(duì)列中選擇進(jìn)程給CPU。

為什么要調(diào)度？為了最大限度的利用CPU。

調(diào)度相關(guān)結(jié)構(gòu)體

task_struct

我們先把task_struct中和調(diào)度相關(guān)的結(jié)構(gòu)拎出來(lái)：

structtask_struct{ ...... /* *調(diào)度類。用 sched_class 對(duì)調(diào)度器進(jìn)行抽象 *Stop調(diào)度器:stop_sched_class *Deadline調(diào)度器:dl_sched_class *RT調(diào)度器:rt_sched_class *CFS調(diào)度器:cfs_sched_class *IDLE-Task調(diào)度器:idle_sched_class */ conststructsched_class*sched_class; //CFS調(diào)度實(shí)體 structsched_entityse; //RT調(diào)度實(shí)體 structsched_rt_entityrt; ...... #ifdefCONFIG_CGROUP_SCHED //任務(wù)組（在每個(gè)CPU上都會(huì)維護(hù)一個(gè)CFS調(diào)度實(shí)體、CFS運(yùn)行隊(duì)列;RT調(diào)度實(shí)體，RT運(yùn)行隊(duì)列） structtask_group*sched_task_group; #endif //DL調(diào)度實(shí)體 structsched_dl_entitydl; ...... /* *進(jìn)程的調(diào)度策略,有6種。 *限期進(jìn)程調(diào)度策略:SCHED_DEADLINE。DL調(diào)度器 *實(shí)時(shí)進(jìn)程調(diào)度策略:SCHED_FIFO，SCHED_RR。RT調(diào)度器 *普通進(jìn)程調(diào)度策略:SCHED_NORMAL，SCHED_BATCH，SCHED_IDLE。CFS調(diào)度器 */ unsignedintpolicy; ...... }

struct sched_class 對(duì)調(diào)度器進(jìn)行抽象，一共分為5類：

Stop調(diào)度器：優(yōu)先級(jí)最高的調(diào)度類，可以搶占其他所有進(jìn)程，不能被其他進(jìn)程搶占；

Deadline調(diào)度器：使用紅黑樹，把進(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種，用戶可以調(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ì)列

structrq{ ...... //三個(gè)調(diào)度隊(duì)列：CFS調(diào)度，RT調(diào)度，DL調(diào)度 structcfs_rqcfs; structrt_rqrt; structdl_rqdl; ...... //idle指向空閑內(nèi)核線程,stop指向遷移內(nèi)核線程 structtask_struct*curr,*idle,*stop; ...... }

三個(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ì)列

每個(gè)CPU都有一個(gè)運(yùn)行隊(duì)列，每個(gè)運(yùn)行隊(duì)列中有三個(gè)調(diào)度隊(duì)列，task作為調(diào)度實(shí)體加入到各自的調(diào)度隊(duì)列中。

調(diào)度流程

調(diào)度的本質(zhì)就是選擇下一個(gè)進(jìn)程來(lái)運(yùn)行，調(diào)度的過(guò)程分為兩步：

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í)候

smp_send_reschedule 負(fù)載均衡的時(shí)候

set_user_nice 修改進(jìn)程nice值的時(shí)候

以上情況下都會(huì)通過(guò) resched_curr 來(lái)設(shè)置進(jìn)程thread_info結(jié)構(gòu)體里的flags成員為TIF_NEED_RESCHED。以 scheduler_tick 和 wake_up_process 為例：

關(guān)于是否需要設(shè)置TIF_NEED_RESCHED的依據(jù)涉及到具體的調(diào)度算法，等我們講到具體調(diào)度器時(shí)再詳細(xì)講。

2. 執(zhí)行調(diào)度

kernel判斷當(dāng)前進(jìn)程標(biāo)記是否為TIF_NEED_RESCHED，是的話調(diào)用 schedule 函數(shù)切換上下文，kernel空間是可以關(guān)搶占的，user空間是無(wú)法關(guān)搶占的。搶占可分為內(nèi)核態(tài)搶占和用戶態(tài)搶占

用戶態(tài)搶占

ret_to_user是系統(tǒng)調(diào)用，異常觸發(fā)，中斷處理完成后都會(huì)調(diào)用的函數(shù)。

內(nèi)核態(tài)搶占

進(jìn)程切換上下文 context_switch

通過(guò)上面我們知道執(zhí)行調(diào)度的時(shí)候發(fā)生在 _schedule 函數(shù)里。

重點(diǎn)是其中的兩個(gè)函數(shù)，一個(gè)是選擇需要切換任務(wù)的 pick_next_task，另外一個(gè)是完成進(jìn)程上下文切換 context_switch。

關(guān)于選擇task的策略涉及到不同的調(diào)度類，等我們講到具體調(diào)度器的時(shí)候再展開，這里重點(diǎn)講下上下文切換的函數(shù) context_switch，進(jìn)程上下文切換主要涉及到兩部分主要過(guò)程：進(jìn)程地址空間切換和處理器狀態(tài)切換：

進(jìn)程的地址空間切換

將下一個(gè)進(jìn)程的pgd虛擬地址轉(zhuǎn)化為物理地址存放在ttbr0_el1中(這是用戶空間的頁(yè)表基址寄存器)，當(dāng)訪問(wèn)用戶空間地址的時(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)切換。

責(zé)任編輯：lq6