《Linux內(nèi)核源碼分析》(3)調(diào)度器及CFS調(diào)度器

一、調(diào)度器

1、調(diào)度器

• Linux內(nèi)核中用來(lái)安排調(diào)度進(jìn)程（一段程序的執(zhí)行過(guò)程）執(zhí)行的模塊稱為調(diào)度器(Scheduler),它可以切換進(jìn)程狀態(tài)(Process status)。比如：執(zhí)行、可中斷睡眠、不可中斷睡眠、退出、暫停等。

• 調(diào)度器相當(dāng)于CPU中央處理器的管理員，主要負(fù)責(zé)完成做兩件事情:
  • 選擇某些就緒進(jìn)程來(lái)執(zhí)行
  • 打斷某些執(zhí)行的進(jìn)程讓它們變?yōu)榫途w狀態(tài)

2、調(diào)度類sched_class結(jié)構(gòu)體

• 調(diào)度器類提供了通用調(diào)度器和各個(gè)調(diào)度方法之間的關(guān)聯(lián)，Linux內(nèi)核抽象一個(gè)調(diào)度類struct sched_class結(jié)構(gòu)體表示調(diào)度類，具體內(nèi)核源碼如下：
  kernel/sched/<sched.h>

  struct sched_class {/*系統(tǒng)當(dāng)中有多個(gè)調(diào)度類，按照調(diào)度優(yōu)先級(jí)排成一個(gè)鏈表,下一優(yōu)先級(jí)的高類*/const struct sched_class *next;#ifdef CONFIG_UCLAMP_TASKint uclamp_enabled;
  #endif/*將進(jìn)程加入到執(zhí)行隊(duì)列當(dāng)中,即將調(diào)度實(shí)體(進(jìn)程)存放到紅黑樹(shù)中,并對(duì)nr_running變量自動(dòng)會(huì)加1。（nr_running指定了隊(duì)列上可運(yùn)行進(jìn)程的數(shù)目，不考慮其優(yōu)先級(jí)或調(diào)度類）*/void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);/*從執(zhí)行隊(duì)列當(dāng)中刪除進(jìn)程，并對(duì)nr_running變量自動(dòng)減1 */void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);/*放棄CPU執(zhí)行權(quán)，實(shí)際上該函數(shù)執(zhí)行先出隊(duì)后入隊(duì)，在這種情況下，它直接將調(diào)度實(shí)體放在紅黑樹(shù)的最右端*/void (*yield_task)   (struct rq *rq);bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);/*用于檢杳當(dāng)前進(jìn)程是否可被新進(jìn)程搶占*/void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);/*選擇下一個(gè)應(yīng)用要運(yùn)行的進(jìn)程*/struct task_struct *(*pick_next_task)(struct rq *rq);/*將進(jìn)程放回到運(yùn)行隊(duì)列當(dāng)中*/void (*put_prev_task)(struct rq *rq, struct task_struct *p);void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);#ifdef CONFIG_SMPint (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);/*為進(jìn)程選擇一個(gè)合適的CPU */int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);/*遷移任務(wù)到處一個(gè)CPU */void (*migrate_task_rq)(struct task_struct *p, int new_cpu);/*專門用于喚醍進(jìn)程*/void (*task_woken)(struct rq *this_rq, struct task_struct *task);/*修改進(jìn)程在CPU的親和力*/void (*set_cpus_allowed)(struct task_struct *p,const struct cpumask *newmask);/*啟動(dòng)運(yùn)行隊(duì)列*/void (*rq_online)(struct rq *rq);/*禁止運(yùn)行隊(duì)列*/void (*rq_offline)(struct rq *rq);
  #endif/*調(diào)用自time tick函數(shù)，它可能引起進(jìn)程切換，將驅(qū)動(dòng)運(yùn)行時(shí)(running)搶占*/void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);/* 進(jìn)程創(chuàng)建時(shí)調(diào)用，不同調(diào)度策略的進(jìn)程初始化也是不一樣的 */void (*task_fork)(struct task_struct *p);/*進(jìn)程退出時(shí)會(huì)使用*/void (*task_dead)(struct task_struct *p);/** The switched_from() call is allowed to drop rq->lock, therefore we* cannot assume the switched_from/switched_to pair is serliazed by* rq->lock. They are however serialized by p->pi_lock.*//*專門用于進(jìn)程切換操作*/void (*switched_from)(struct rq *this_rq, struct task_struct *task);void (*switched_to)  (struct rq *this_rq, struct task_struct *task);/*更改進(jìn)程的優(yōu)先級(jí)*/void (*prio_changed) (struct rq *this_rq, struct task_struct *task,int oldprio);unsigned int (*get_rr_interval)(struct rq *rq,struct task_struct *task);void (*update_curr)(struct rq *rq);#define TASK_SET_GROUP		0
  #define TASK_MOVE_GROUP		1#ifdef CONFIG_FAIR_GROUP_SCHEDvoid (*task_change_group)(struct task_struct *p, int type);
  #endif
  };
  

• 調(diào)度器類可分為：stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class和idle_sched_class
  kernel/sched/<sched.h>

  extern const struct sched_class stop_sched_class;//停機(jī)調(diào)度類
  extern const struct sched_class dl_sched_class;//限期調(diào)度類
  extern const struct sched_class rt_sched_class;//實(shí)時(shí)調(diào)度類
  extern const struct sched_class fair_sched_class;//公平調(diào)度類
  extern const struct sched_class idle_sched_class;//空閑調(diào)度類
  

  這5種調(diào)度類的優(yōu)先級(jí)從高到低依次為：停機(jī)調(diào)度類、限期調(diào)度類、實(shí)時(shí)調(diào)度類、公平調(diào)度類、空閑調(diào)度類。其中，SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE直接被映射到fair_sched_class；SCHED_FIFO和SCHED_RR與rt_sched_class向關(guān)聯(lián)。Linux調(diào)度核心選擇下一個(gè)合適的task運(yùn)行時(shí)，會(huì)按照優(yōu)先級(jí)順序遍歷調(diào)度類的pick_next_task函數(shù)

  • 停機(jī)調(diào)度類：優(yōu)先級(jí)是最高的調(diào)度類，停機(jī)進(jìn)程是優(yōu)先級(jí)最高的進(jìn)程，可以搶占所有其它進(jìn)程，其他進(jìn)程不可能搶占停機(jī)進(jìn)程.

    const struct sched_class stop_sched_class = {.next			= &dl_sched_class,.enqueue_task		= enqueue_task_stop,.dequeue_task		= dequeue_task_stop,.yield_task		= yield_task_stop,.check_preempt_curr	= check_preempt_curr_stop,.pick_next_task		= pick_next_task_stop,.put_prev_task		= put_prev_task_stop,.set_next_task          = set_next_task_stop,...
    };
    

  • 限期調(diào)度類：最早使用優(yōu)先算法，使用紅黑樹(shù)把進(jìn)程按照絕對(duì)截止期限從小到大排序，每次調(diào)度時(shí)選擇絕對(duì)截止期限最小的進(jìn)程。

    const struct sched_class dl_sched_class = {.next			= &rt_sched_class,.enqueue_task		= enqueue_task_dl,.dequeue_task		= dequeue_task_dl,.yield_task		= yield_task_dl,.check_preempt_curr	= check_preempt_curr_dl,.pick_next_task		= pick_next_task_dl,.put_prev_task		= put_prev_task_dl,.set_next_task		= set_next_task_dl,...
    };
    

  • 實(shí)時(shí)調(diào)度類：為每個(gè)調(diào)度優(yōu)先級(jí)維護(hù)一個(gè)隊(duì)列。

    const struct sched_class rt_sched_class = {.next			= &fair_sched_class,.enqueue_task		= enqueue_task_rt,.dequeue_task		= dequeue_task_rt,.yield_task		= yield_task_rt,.check_preempt_curr	= check_preempt_curr_rt,.pick_next_task		= pick_next_task_rt,.put_prev_task		= put_prev_task_rt,.set_next_task          = set_next_task_rt,...
    };
    

  • 公平調(diào)度類：使用完全公平調(diào)度算法。完全公平調(diào)度算法引入虛擬運(yùn)行時(shí)間的相關(guān)概念：虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 * nice為0對(duì)應(yīng)的權(quán)重 / 進(jìn)程的權(quán)重。

    const struct sched_class fair_sched_class = {.next			= &idle_sched_class,.enqueue_task		= enqueue_task_fair,.dequeue_task		= dequeue_task_fair,.yield_task		= yield_task_fair,.yield_to_task		= yield_to_task_fair,.check_preempt_curr	= check_preempt_wakeup,.pick_next_task		= __pick_next_task_fair,.put_prev_task		= put_prev_task_fair,.set_next_task          = set_next_task_fair,...
    };
    

  • 空閑調(diào)度類：每個(gè)CPU上有一個(gè)空閑線程，即0號(hào)線程。空閑調(diào)度類優(yōu)先級(jí)最低，僅當(dāng)沒(méi)有其他進(jìn)程可以調(diào)度的時(shí)候，才會(huì)調(diào)度空閑線程。

    const struct sched_class idle_sched_class = {/* .next is NULL *//* no enqueue/yield_task for idle tasks *//* dequeue is not valid, we print a debug message there: */.dequeue_task		= dequeue_task_idle,.check_preempt_curr	= check_preempt_curr_idle,.pick_next_task		= pick_next_task_idle,.put_prev_task		= put_prev_task_idle,.set_next_task          = set_next_task_idle,...
    };
    

• 觀察上述5個(gè)調(diào)度類的next成員變量，可以發(fā)現(xiàn)他們是串聯(lián)在一起的。Linux調(diào)度核心選擇下一個(gè)合適的task運(yùn)行時(shí)，會(huì)按照優(yōu)先級(jí)順序遍歷調(diào)度類的pick_next_task函數(shù)。

3、優(yōu)先級(jí)

• 在用戶空間可以通過(guò)nice命令設(shè)置進(jìn)程的靜態(tài)優(yōu)先級(jí)，這在內(nèi)部會(huì)調(diào)用nice系統(tǒng)調(diào)用。進(jìn)程的nice值為[-20,+19]。值越低，表明優(yōu)先級(jí)越高。內(nèi)核使用范圍[0,139]來(lái)表示內(nèi)部?jī)?yōu)先級(jí)。同樣是值越低，優(yōu)先級(jí)越高。實(shí)時(shí)進(jìn)程范圍為[0,99]。nice值[-20, +19]映射到范圍100到139。如下圖所示，實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)總是比普通進(jìn)程更高。
  
• Linux內(nèi)核優(yōu)先級(jí)源碼如下：
  include/linux/sched/<prio.h>

  #define MAX_NICE	19
  #define MIN_NICE	-20/*nice值的范圍*/
  #define NICE_WIDTH	(MAX_NICE - MIN_NICE + 1)/*實(shí)時(shí)進(jìn)程最大優(yōu)先級(jí)（不包含）*/
  #define MAX_USER_RT_PRIO	100 
  #define MAX_RT_PRIO		MAX_USER_RT_PRIO/*普通進(jìn)程最大優(yōu)先級(jí)（不包含）*/
  #define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH) // 140#define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2)
  

4、內(nèi)核調(diào)度策略

• struct task_struct中有成員變量unsigned int policy，指代保存進(jìn)程的調(diào)度策略。
• Linux內(nèi)核提供一些調(diào)度策略供用戶應(yīng)用程序來(lái)選擇調(diào)度器。Linux內(nèi)核調(diào)度策略源碼分析如下：
  include/uapi/linux/<sched.h>

  /** Scheduling policies*//*用于普通進(jìn)程，通過(guò)CFS調(diào)度器實(shí)現(xiàn)。*/
  #define SCHED_NORMAL		0/* 先進(jìn)先出調(diào)度算法（實(shí)時(shí)調(diào)度策略），相同優(yōu)先級(jí)任務(wù)先到先服務(wù)，高優(yōu)先級(jí)的任務(wù)可以搶占低優(yōu)先級(jí)的任務(wù) */
  #define SCHED_FIFO		1/*輪流調(diào)度算法（實(shí)時(shí)調(diào)度策略）*/
  #define SCHED_RR		2/*用于非交互處理器消耗型進(jìn)程，相當(dāng)于SCHED_NORMAL分化版本，采用分時(shí)策略，根據(jù)動(dòng)態(tài)優(yōu)先級(jí)，分配CPU運(yùn)行需要資源*/
  #define SCHED_BATCH		3/* SCHED_ISO: reserved but not implemented yet *//*普通迸程調(diào)度策略，使task以最低優(yōu)先級(jí)選擇CFS調(diào)度器來(lái)調(diào)度運(yùn)行*/
  #define SCHED_IDLE		5/*限期進(jìn)程調(diào)度策略，使task選擇Deadline調(diào)度器來(lái)調(diào)度運(yùn)行*/
  #define SCHED_DEADLINE		6
  

  • 備注：其中stop調(diào)度器和DLE-task調(diào)度器，僅使用于內(nèi)核，用戶沒(méi)有辦法進(jìn)行選擇。

二、CFS調(diào)度器

1、CFS調(diào)度器基本原理

• 完全公平調(diào)度算法體現(xiàn)在對(duì)待每個(gè)進(jìn)程都是公平的，讓每個(gè)進(jìn)程都運(yùn)行—段相同的時(shí)間片，這就是基于時(shí)間片輪詢調(diào)度算法。CFS定義一種新調(diào)度模型，它給cfs_rq (cfs的run queue)中的每一個(gè)進(jìn)程都設(shè)置一個(gè)虛擬時(shí)鐘:vruntime(virtual runtime)。如果一個(gè)進(jìn)程得以執(zhí)行，隨著執(zhí)行時(shí)間的不斷增長(zhǎng)，其vruntime也將不斷增大，沒(méi)有得到執(zhí)行的進(jìn)程vruntime 將保持不變。
• 下圖說(shuō)明了調(diào)度器如何記錄哪個(gè)進(jìn)程已經(jīng)等待了多長(zhǎng)時(shí)間。由于可運(yùn)行進(jìn)程是排隊(duì)的，該結(jié)構(gòu)稱之為就緒隊(duì)列
  
  所有的可運(yùn)行進(jìn)程都按時(shí)間在一個(gè)紅黑樹(shù)中排序，所謂時(shí)間即其等待時(shí)間。等待CPU時(shí)間最長(zhǎng)的進(jìn)程是最左側(cè)的項(xiàng)，調(diào)度器下一次會(huì)考慮該進(jìn)程。等待時(shí)間稍短的進(jìn)程在該樹(shù)上從左至右排序。在一個(gè)調(diào)度周期里面，所有進(jìn)程的虛擬運(yùn)行時(shí)間是相同的，所以在進(jìn)程調(diào)度時(shí)，只需要找到虛擬運(yùn)行時(shí)間最小的進(jìn)程調(diào)度運(yùn)行即可。
• 實(shí)現(xiàn)完全公平調(diào)度算法，要為進(jìn)程定義兩個(gè)時(shí)間

  • 實(shí)際運(yùn)行時(shí)間
    實(shí)際運(yùn)行時(shí)間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和
    調(diào)度周期：指所有進(jìn)程運(yùn)行一遍所需要的時(shí)間；
    進(jìn)程權(quán)重：根據(jù)進(jìn)程的重要性，分配給每個(gè)進(jìn)程不同的權(quán)重

    eg：調(diào)度周期為60ms，進(jìn)程A的權(quán)重為1，而且進(jìn)程B的權(quán)重為2,那么：
    進(jìn)程A實(shí)際運(yùn)行時(shí)間為：60ms * 1/（1 +2）=20ms
    進(jìn)程B實(shí)際運(yùn)行時(shí)間為：60ms * 2/（1 +2）=40ms

  • 虛擬運(yùn)行時(shí)間
    虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 * nice為0對(duì)應(yīng)的權(quán)重（1024） / 進(jìn)程的權(quán)重 =（調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和 * 1024 / 進(jìn)程權(quán)重 = 調(diào)度周期 * 1024 / 所有進(jìn)程總權(quán)重。

2、調(diào)度子系統(tǒng)各個(gè)組件模塊

• 調(diào)度器通過(guò)各個(gè)組件模塊及一系列數(shù)據(jù)結(jié)構(gòu)，來(lái)排序和管理系統(tǒng)中的進(jìn)程。它們之間關(guān)系如下：
  
  • 主調(diào)度器：通過(guò)調(diào)用schedule()函數(shù)來(lái)完成進(jìn)程的選擇和切換。
  • 周期性調(diào)度器：根據(jù)固定頻率自動(dòng)調(diào)用scheduler_tick函數(shù)，不時(shí)檢測(cè)是否有必要進(jìn)行進(jìn)程切換。
  • 上下文切換：主要做兩個(gè)事情（切換地址空間、切換寄存器和?？臻g）

3、CFS調(diào)度器就緒隊(duì)列內(nèi)核源碼

struct cfs_rq {/*CFS運(yùn)行隊(duì)列中所有進(jìn)程總負(fù)我*/struct load_weight	load;unsigned long		runnable_weight;/*cfs_rq中調(diào)度實(shí)體數(shù)量*/unsigned int		nr_running;unsigned int		h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */unsigned int		idle_h_nr_running; /* SCHED_IDLE */u64			exec_clock;u64			min_vruntime;
#ifndef CONFIG_64BITu64			min_vruntime_copy;
#endif/*紅黑樹(shù)的root*/struct rb_root_cached	tasks_timeline;/*下一個(gè)調(diào)度結(jié)點(diǎn)(紅黑樹(shù)最左邊結(jié)點(diǎn)就是下個(gè)調(diào)度實(shí)體）*/struct rb node *rb leftmost;...