進程調度所使用到的數據結構：
1.就緒隊列
內核為每一個cpu創(chuàng)建一個進程就緒隊列，該隊列上的進程均由該cpu執(zhí)行，代碼如下（kernel/sched/core.c）。
1 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
定義了一個struct rq結構體數組，每個數組元素是一個就緒隊列，對應一個cpu。下面看下struct rq結構體（kernel/sched/sched.h）：
該結構體是本地cpu所有進程組成的就緒隊列，在linux內核中，進程被分為普通進程和實時進程，這兩種進程的調度策略是不同的，因此在31-32行可以看到rq結構體中又內嵌了struct cfs_rq cfs和struct rt_rq rt兩個子就緒隊列，分別來組織普通進程和實時進程（普通進程將采用完全公平調度策略cfs，而實時進程將采用實時調度策略），第33行struct dl_rq dl調度空閑進程，暫且不討論。所以，如果咱們研究的是普通進程的調度，需要關心的就是struct cfs_rq cfs隊列；如果研究的是實時進程，就只關心struct rt_rq rt隊列。
1.1普通進程的就緒隊列struct cfs_rq（kernel/sched/sched.h）
cfs_rq就緒隊列是以紅黑樹的形式來組織調度實體。第12行tasks_timeline成員就是紅黑樹的樹根。第13行rb_leftmost指向了紅黑樹最左邊的左孩子（下一個可調度的實體）。第19行curr指向當前正運行的實體，next指向將被喚醒的進程，last指向喚醒next進程的進程，next和last用法后邊會提到。第55行rq指向了該cfs_rq就緒隊列所屬的rq隊列。
1.2實時進程的就緒隊列struct rt_rq（kernel/sched/sched.h）
2.調度實體（include/linux/sched.h）
2.1普通進程的調度實體sched_entity
1 struct sched_entity { 2 struct load_weight load; /* for load-balancing */ 3 struct rb_node run_node; 4 struct list_head group_node; 5 unsigned int on_rq; 6 7 u64 exec_start; 8 u64 sum_exec_runtime; 9 u64 vruntime;10 u64 prev_sum_exec_runtime;11 12 u64 nr_migrations;13 14 #ifdef CONFIG_SCHEDSTATS15 struct sched_statistics statistics;16 #endif17 18 #ifdef CONFIG_FAIR_GROUP_SCHED19 int depth;20 struct sched_entity *parent;21 /* rq on which this entity is (to be) queued: */22 struct cfs_rq *cfs_rq;23 /* rq "owned" by this entity/group: */24 struct cfs_rq *my_q;25 #endif26 27 #ifdef CONFIG_SMP28 /* Per-entity load-tracking */29 struct sched_avg avg;30 #endif31 };
每個進程描述符中均包含一個該結構體變量，內核使用該結構體來將普通進程組織到采用完全公平調度策略的就緒隊列中（struct rq中的cfs隊列中，上邊提到過），該結構體有兩個作用，一是包含有進程調度的信息（比如進程的運行時間，睡眠時間等等，調度程序參考這些信息決定是否調度進程），二是使用該結構體來組織進程，第3行的struct rb_node類型結構體變量run_node是紅黑樹節(jié)點，因此struct sched_entity調度實體將被組織成紅黑樹的形式，同時意味著普通進程也被組織成紅黑樹的形式。第18-25行是和組調度有關的成員，需要開啟組調度。第20行parent顧名思義指向了當前實體的上一級實體，后邊再介紹。第22行的cfs_rq指向了該調度實體所在的就緒隊列。第24行my_q指向了本實體擁有的就緒隊列（調度組），該調度組（包括組員實體）屬于下一個級別，和本實體不在同一個級別，該調度組中所有成員實體的parent域指向了本實體，這就解釋了上邊的parent，此外，第19行depth代表了此隊列（調度組）的深度，每個調度組都比其parent調度組深度大1。內核依賴my_q域實現組調度。
2.2實時進程的調度實體 sched_rt_entity
1 struct sched_rt_entity { 2 struct list_head run_list; 3 unsigned long timeout; 4 unsigned long watchdog_stamp; 5 unsigned int time_slice; 6 7 struct sched_rt_entity *back; 8 #ifdef CONFIG_RT_GROUP_SCHED 9 struct sched_rt_entity *parent;10 /* rq on which this entity is (to be) queued: */11 struct rt_rq *rt_rq;12 /* rq "owned" by this entity/group: */13 struct rt_rq *my_q;14 #endif15 };
該結構體和上個結構體是類似的，只不過用來組織實時進程，實時進程被組織到struct rq中的rt隊列中，上邊有提到。每個進程描述符中也包含一個該結構體。該結構體中并未包含struct rb_node類型結構體變量，而在第1行出現了struct list_head類型結構體變量run_list，因此可以看出實時進程的就緒隊列是雙向鏈表形式，而不是紅黑數的形式。
3.調度類（kernel/sched/sched.h）
1 struct sched_class { 2 const struct sched_class *next; 3 4 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 5 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 6 void (*yield_task) (struct rq *rq); 7 bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt); 8 9 void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);10 11 /*12 * It is the responsibility of the pick_next_task() method that will13 * return the next task to call put_prev_task() on the @prev task or14 * something equivalent.15 *16 * May return RETRY_TASK when it finds a higher prio class has runnable17 * tasks.18 */19 struct task_struct * (*pick_next_task) (struct rq *rq,20 struct task_struct *prev);21 void (*put_prev_task) (struct rq *rq, struct task_struct *p);22 23 #ifdef CONFIG_SMP24 int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);25 void (*migrate_task_rq)(struct task_struct *p, int next_cpu);26 27 void (*post_schedule) (struct rq *this_rq);28 void (*task_waking) (struct task_struct *task);29 void (*task_woken) (struct rq *this_rq, struct task_struct *task);30 31 void (*set_cpus_allowed)(struct task_struct *p,32 const struct cpumask *newmask);33 34 void (*rq_online)(struct rq *rq);35 void (*rq_offline)(struct rq *rq);36 #endif37 38 void (*set_curr_task) (struct rq *rq);39 void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);40 void (*task_fork) (struct task_struct *p);41 void (*task_dead) (struct task_struct *p);42 43 void (*switched_from) (struct rq *this_rq, struct task_struct *task);44 void (*switched_to) (struct rq *this_rq, struct task_struct *task);45 void (*prio_changed) (struct rq *this_rq, struct task_struct *task,46 int oldprio);47 48 unsigned int (*get_rr_interval) (struct rq *rq,49 struct task_struct *task);50 51 #ifdef CONFIG_FAIR_GROUP_SCHED52 void (*task_move_group) (struct task_struct *p, int on_rq);53 #endif54 };
內核聲明了一個調度類sched_class的結構體類型，用來實現不同的調度策略，可以看到該結構體成員都是函數指針，這些指針指向的函數就是調度策略的具體實現，所有和進程調度有關的函數都直接或者間接調用了這些成員函數，來實現進程調度。此外，每個進程描述符中都包含一個指向該結構體類型的指針sched_class，指向了所采用的調度類。下面我們看下完全公平調度策略類的定義和初始化（kernel/sched/fair.c）。
1 const struct sched_class fair_sched_class;
定義了一個全局的調度策略變量。初始化如下：
1 const struct sched_class fair_sched_class = { 2 .next = &idle_sched_class, 3 .enqueue_task = enqueue_task_fair, 4 .dequeue_task = dequeue_task_fair, 5 .yield_task = yield_task_fair, 6 .yield_to_task = yield_to_task_fair, 7 8 .check_preempt_curr = check_preempt_wakeup, 9 10 .pick_next_task = pick_next_task_fair,11 .put_prev_task = put_prev_task_fair,12 13 #ifdef CONFIG_SMP14 .select_task_rq = select_task_rq_fair,15 .migrate_task_rq = migrate_task_rq_fair,16 17 .rq_online = rq_online_fair,18 .rq_offline = rq_offline_fair,19 20 .task_waking = task_waking_fair,21 #endif22 23 .set_curr_task = set_curr_task_fair,24 .task_tick = task_tick_fair,25 .task_fork = task_fork_fair,26 27 .prio_changed = prio_changed_fair,28 .switched_from = switched_from_fair,29 .switched_to = switched_to_fair,30 31 .get_rr_interval = get_rr_interval_fair,32 33 #ifdef CONFIG_FAIR_GROUP_SCHED34 .task_move_group = task_move_group_fair,35 #endif36 };
可以看到該結構體變量中函數成員很多，它們實現了不同的功能，待會用到時我們再做分析。
4.進程描述符task_struct（include/linux/sched.h）
1 struct task_struct { 2 volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ 3 ..... 4 int on_rq; 5 6 int prio, static_prio, normal_prio; 7 unsigned int rt_priority; 8 const struct sched_class *sched_class; 9 struct sched_entity se;10 struct sched_rt_entity rt;11 #ifdef CONFIG_CGROUP_SCHED12 struct task_group *sched_task_group;13 #endif14 struct sched_dl_entity dl;15 .....16 .....17 unsigned int policy;18 .....19 .....20 struct sched_info sched_info;21 .....22 .....23 };
只列出了和進程調度有關的成員。第6行三個變量代表了普通進程的三個優(yōu)先級，第7行的變量代表了實時進程的優(yōu)先級。關于進程優(yōu)先級的概念，大家可以看看《深入理解linux內核架構》這本書的進程管理章節(jié)。第8-10行就是我們上邊提到的那些結構體在進程描述符中的定義。第17行的policy代表了當前進程的調度策略，內核給出了宏定義，它可以在這些宏中取值，關于詳細的講解還是去看《深入理解linux內核架構》這本書的進程管理部分。policy取了什么值，sched_class也應該取相應的調度類指針。
進程調度過程分析：
進程調度過程分為兩部分，一是對進程信息進行修改，主要是修改和調度相關的信息，比如進程的運行時間，睡眠時間，進程的狀態(tài)，cpu的負荷等等，二是進程的切換。和進程調度相關的所有函數中，只有schedule函數是用來進行進程切換的，其他函數都是用來修改進程的調度信息。schedule函數我們在前邊的博文中已經探討過了，這里不再分析。對于其他函數，我們將按照其功能，逐類來分析。
1.scheduler_tick（kernel/sched/core.c ）
1 void scheduler_tick(void) 2 { 3 int cpu = smp_processor_id(); 4 struct rq *rq = cpu_rq(cpu); 5 struct task_struct *curr = rq->curr; 6 7 sched_clock_tick(); 8 9 raw_spin_lock(&rq->lock);10 update_rq_clock(rq);11 curr->sched_class->task_tick(rq, curr, 0);12 update_cpu_load_active(rq);13 raw_spin_unlock(&rq->lock);14 15 perf_event_task_tick();16 17 #ifdef CONFIG_SMP18 rq->idle_balance = idle_cpu(cpu);19 trigger_load_balance(rq);20 #endif21 rq_last_tick_reset(rq);22 }
該函數被時鐘中斷處理程序調用，將當前cpu的負載情況記載到運行隊列struct rq的某些成員中，并更新當前進程的時間片。第3行獲取當前的cpu號，第4行獲取當前cpu的就緒隊列（每個cpu有一個）rq，第5行從就緒隊列中獲取當前運行進程的描述符，第10行更新就緒隊列中的clock和clock_task成員值，代表當前的時間，一般我們會用到clock_task。第11行進入當前進程的調度類的task_tick函數中，更新當前進程的時間片，不同調度類的該函數實現不同，待會我們分析下完全公平調度類的該函數。第12行更新就緒隊列的cpu負載信息。第18行判斷當前cpu是否是空閑的，是的話idle_cpu返回1，否則返回0。第19行掛起SCHED_SOFTIRQ軟中斷函數，去做周期性的負載平衡操作。第21行將最新的時鐘滴答數jiffies存入就緒隊列的last_sched_tick域中。再來看下task_tick_fair函數（kernel/sched/fair.c）：
1 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) 2 { 3 struct cfs_rq *cfs_rq; 4 struct sched_entity *se = &curr->se; 5 6 for_each_sched_entity(se) { 7 cfs_rq = cfs_rq_of(se); 8 entity_tick(cfs_rq, se, queued); 9 }10 11 if (numabalancing_enabled)12 task_tick_numa(rq, curr);13 14 update_rq_runnable_avg(rq, 1);15 }
如果某個進程的調度類采用完全公平調度類的話，那么上個函數scheduler_tick第11行所執(zhí)行的task_tick函數指針，就指向了本函數?？梢曰仡^看看完全公平調度對象的初始化，第24行的賦值語句.task_tick = task_tick_fair?；氐奖竞瘮?，第4行獲取當前進程的普通調度實體，將指針存放到se中，第6-8行遍歷當前調度實體的上一級實體，以及上上一級實體，以此類推，然后在entity_tick函數中更新調度實體的運行時間等信息。在這里用循環(huán)來遍歷的原因是當開啟了組調度后，調度實體的parent域就存儲了它的上一級節(jié)點，該實體和它parent指向的實體不是同一級別，因此使用循環(huán)就把從當前級別（組）到最頂層的級別遍歷完了；如果未選擇組支持，則循環(huán)只執(zhí)行一次，僅對當前調度實體進行更新。下面看下entity_tick的代碼（kernel/sched/fair.c）：
1 static void 2 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) 3 { 4 /* 5 * Update run-time statistics of the 'current'. 6 */ 7 update_curr(cfs_rq); 8 9 /*10 * Ensure that runnable average is periodically updated.11 */12 update_entity_load_avg(curr, 1);13 update_cfs_rq_blocked_load(cfs_rq, 1);14 update_cfs_shares(cfs_rq);15 16 #ifdef CONFIG_SCHED_HRTICK17 /*18 * queued ticks are scheduled to match the slice, so don't bother19 * validating it and just reschedule.20 */21 if (queued) {22 resched_task(rq_of(cfs_rq)->curr);23 return;24 }25 /*26 * don't let the period tick interfere with the hrtick preemption27 */28 if (!sched_feat(DOUBLE_TICK) &&29 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))30 return;31 #endif32 33 if (cfs_rq->nr_running > 1)34 check_preempt_tick(cfs_rq, curr);35 }
在該函數中對調度實體（進程）的運行時間等信息進行更新。第7行update_curr函數對當前進程的運行時間進行更新，隨后分析。 第21行如果傳進來的參數queued不為0的話，當前進程會被無條件設置重新調度標志（允許被搶占了）。第33-34行如果當前cfs_rq隊列等待調度的進程數量大于1，那么就執(zhí)行check_preempt_tick函數檢查當前進程的時間片是否用完，用完的話就需要調度別的進程來運行（具體來說，如果當前進程“真實時間片”用完，該函數給當前進程設置need_resched標志，然后schedule程序就可以重新在就緒隊列中調度新的進程），下面分析update_curr函數（kernel/sched/fair.c）：
1 static void update_curr(struct cfs_rq *cfs_rq) 2 { 3 struct sched_entity *curr = cfs_rq->curr; 4 u64 now = rq_clock_task(rq_of(cfs_rq)); 5 u64 delta_exec; 6 7 if (unlikely(!curr)) 8 return; 9 10 delta_exec = now - curr->exec_start;11 if (unlikely((s64)delta_exec <= 0))12 return;13 14 curr->exec_start = now;15 16 schedstat_set(curr->statistics.exec_max,17 max(delta_exec, curr->statistics.exec_max));18 19 curr->sum_exec_runtime += delta_exec;20 schedstat_add(cfs_rq, exec_clock, delta_exec);21 22 curr->vruntime += calc_delta_fair(delta_exec, curr);23 update_min_vruntime(cfs_rq);24 25 if (entity_is_task(curr)) {26 struct task_struct *curtask = task_of(curr);27 28 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);29 cpuacct_charge(curtask, delta_exec);30 account_group_exec_runtime(curtask, delta_exec);31 }32 33 account_cfs_rq_runtime(cfs_rq, delta_exec);34 }
該函數是更新進程運行時間最核心的一個函數。第3行獲取當前的調度實體，第4行從就緒隊列rq的clock_task成員中獲取當前時間，存入now中，該成員我們在scheduler_tick函數中提到過。第10行用當前時間減去進程在上次時鐘中斷tick中的開始時間得到進程運行的時間間隔，存入delta_exec中。第14行當前時間又成為進程新的開始時間。第19行將進程運行的時間間隔delta_exec累加到調度實體的sum_exec_runtime成員中，該成員代表進程到目前為止運行了多長時間。第20行將進程運行的時間間隔delta_exec也累加到公平調度就緒隊列cfs_rq的exec_clock成員中。第22行calc_delta_fair函數很關鍵，它將進程執(zhí)行的真實運行時間轉換成虛擬運行時間，然后累加到調度實體的vruntime域中，進程的虛擬時間非常重要，完全公平調度策略就是依賴該時間進行調度。關于進程的真實時間和虛擬時間的概念，以及它們之間的轉換算法，文章的后面會提到，詳細的內容大家可以看看《深入理解linux內核架構》的進程管理章節(jié)。第23行更新cfs_rq隊列中的最小虛擬運行時間min_vruntime，該時間是就緒隊列中所有進程包括當前進程的已運行的最小虛擬時間，只能單調遞增，待會我們分析update_min_vruntime函數，該函數比較重要。第25-30行，如果調度單位是進程的話（不是組），會更新進程描述符中的運行時間。第33行更新cfs_rq隊列的剩余運行時間，并計算出期望運行時間，必要的話可以對進程重新調度。下面我們先分析update_min_vruntime函數，然后分析calc_delta_fair函數（kernel/sched/fair.c）：
1 static void update_min_vruntime(struct cfs_rq *cfs_rq) 2 { 3 u64 vruntime = cfs_rq->min_vruntime; 4 5 if (cfs_rq->curr) 6 vruntime = cfs_rq->curr->vruntime; 7 8 if (cfs_rq->rb_leftmost) { 9 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,10 struct sched_entity,11 run_node);12 13 if (!cfs_rq->curr)14 vruntime = se->vruntime;15 else16 vruntime = min_vruntime(vruntime, se->vruntime);17 }18 19 /* ensure we never gain time by being placed backwards. */20 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);21 #ifndef CONFIG_64BIT22 smp_wmb();23 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;24 #endif25 }
每個cfs_rq隊列均有一個min_vruntime成員，裝的是就緒隊列中所有進程包括當前進程已運行的虛擬時間中最小的那個時間。本函數來更新這個時間。第5-6行如果當前有進程正在執(zhí)行，將當前進程已運行的虛擬時間保存在vruntime變量中。第8-17行如果就緒隊列中有下一個要被調度的進程（由rb_leftmost指針指向），則進入if體，第13-16行從當前進程和下個被調度進程中，選擇最小的已運行虛擬時間，保存到vruntime中。第20行從當前隊列的min_vruntime域和vruntime變量中，選最大的保存到隊列的min_vruntime域中，完成更新。其實第13-17行是最關鍵的，保證了隊列的min_vruntime域中存放的是就緒隊列中最小的虛擬運行時間，而第20行的作用僅僅是保證min_vruntime域中的值單調遞增，沒有別的含義了。隊列中的min_vruntime成員非常重要，用于在睡眠進程被喚醒后以及新進程被創(chuàng)建好時，進行虛擬時間補償或者懲罰，后面會分析到。
1 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)2 {3 if (unlikely(se->load.weight != NICE_0_LOAD))4 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);5 6 return delta;7 }
第3行判斷當前進程nice值是否為0，如果是的話，直接返回真實運行時間delta（nice0級別的進程真實運行時間和虛擬運行時間值相等）；如果不是的話，第4行將真實時間轉換成虛擬時間。下面我們分析__calc_delta函數（kernel/sched/fair.c）：
1 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw) 2 { 3 u64 fact = scale_load_down(weight); 4 int shift = WMULT_SHIFT; 5 6 __update_inv_weight(lw); 7 8 if (unlikely(fact >> 32)) { 9 while (fact >> 32) {10 fact >>= 1;11 shift--;12 }13 }14 15 /* hint to use a 32x32->64 mul */16 fact = (u64)(u32)fact * lw->inv_weight;17 18 while (fact >> 32) {19 fact >>= 1;20 shift--;21 }22 23 return mul_u64_u32_shr(delta_exec, fact, shift);24 }
該函數執(zhí)行了兩種算法：要么是delta_exec * weight / lw.weight，要么是(delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT。計算的結果就是轉換后的虛擬時間。至此，scheduler_tick函數大致就分析完了，當然還有一些細節(jié)沒有分析到，進程調度這塊非常龐雜，要想把所有函數分析完非常耗費時間和精力，以后如果分析到的話，再慢慢補充。scheduler_tick函數主要更新進程的運行時間，包括物理時間和虛擬時間。
2.進程優(yōu)先級設置的函數，進程的優(yōu)先級和調度關系密切，通過上邊分析可以看到，計算進程的虛擬運行時間要用到優(yōu)先級，優(yōu)先級決定進程權重，權重決定進程虛擬時間的增加速度，最終決定進程可運行時間的長短。權重越大的進程可以執(zhí)行的時間越長。從effective_prio函數開始（kernel/sched/core.c）：
1 static int effective_prio(struct task_struct *p) 2 { 3 p->normal_prio = normal_prio(p); 4 /* 5 * If we are RT tasks or we were boosted to RT priority, 6 * keep the priority unchanged. Otherwise, update priority 7 * to the normal priority: 8 */ 9 if (!rt_prio(p->prio))10 return p->normal_prio;11 return p->prio;12 }
該函數在進程創(chuàng)建時或者在用戶的nice系統調用中都會被調用到，來設置進程的活動優(yōu)先級（進程的三種優(yōu)先級：活動優(yōu)先級prio，靜態(tài)優(yōu)先級static_prio，普通優(yōu)先級normal_prio），該函數設計的有一定技巧性，函數的返回值是用來設置進程的活動優(yōu)先級，但是在函數體中也把進程的普通優(yōu)先級設置了。第3行設置進程的普通優(yōu)先級，隨后分析normal_prio函數。第9-11行，通過進程的活動優(yōu)先級可以判斷出該進程是不是實時進程，如果是實時進程，則執(zhí)行11行，返回p->prio，實時進程的活動優(yōu)先級不變。否則返回p->normal_prio，這說明普通進程的活動優(yōu)先級等于它的普通優(yōu)先級。下面我們看看normal_prio函數（kernel/sched/core.c）：
1 static inline int normal_prio(struct task_struct *p) 2 { 3 int prio; 4 5 if (task_has_dl_policy(p)) 6 prio = MAX_DL_PRIO-1; 7 else if (task_has_rt_policy(p)) 8 prio = MAX_RT_PRIO-1 - p->rt_priority; 9 else10 prio = __normal_prio(p);11 return prio;12 }
該函數用來設置進程的普通優(yōu)先級。第5行判斷當前進程是不是空閑進程，是的話設置進程的普通優(yōu)先級為-1（-1是空閑進程的優(yōu)先級），否則的話第7行判斷進程是不是實時進程，是的話設置實時進程的普通優(yōu)先級為0-99（數字越小優(yōu)先級越高），可以看到這塊減去了p->rt_priority，比較奇怪，這是因為實時進程描述符的rt_priority成員中事先存放了它自己的優(yōu)先級（數字也是0-99，但在這里數字越大，優(yōu)先級越高），因此往p->prio中倒換的時候，需要處理一下，MAX_RT_PRIO值為100，因此MAX_RT_PRIO-1-（0，99）就倒換成了（99，0），這僅僅是個小技巧。如果當前進程也不是實時進程（說明是普通進程嘍），則第10行將進程的靜態(tài)優(yōu)先級存入prio中，然后返回（也就是說普通進程的普通優(yōu)先級等于其靜態(tài)優(yōu)先級）。
總結下，總共有三種進程：空閑進程，實時進程，普通進程；每種進程都包含三種優(yōu)先級：活動優(yōu)先級，普通優(yōu)先級，靜態(tài)優(yōu)先級?？臻e進程的普通優(yōu)先級永遠-1，實時進程的普通優(yōu)先級是根據p->rt_priority設定的（0-99），普通進程的普通優(yōu)先級是根據其靜態(tài)優(yōu)先級設定的（100-139）。
3.進程權重設置的函數，上邊我們提到，進程的優(yōu)先級決定進程的權重。權重進而決定進程運行時間的長短。我們先分析和權重相關的數據結構。
struct load_weight（include/linux/sched.h）
1 struct load_weight {2 unsigned long weight;3 u32 inv_weight;4 };
每個進程描述符，調度實體，就緒對列中都包含一個該類型變量，用來保存各自的權重。成員weight中存放進程優(yōu)先級所對應的權重。成員inv_weight中存放NICE_0_LOAD/weight的結果，這個結果乘以進程運行的時間間隔delta_exec就是進程運行的虛擬時間。因此引入權重就是為了計算進程的虛擬時間。在這里將中間的計算結果保存下來，后邊就不用再計算了，直接可以用。
數組prio_to_weight[40]（kernel/sched/sched.h）
1 static const int prio_to_weight[40] = { 2 /* -20 */ 88761, 71755, 56483, 46273, 36291, 3 /* -15 */ 29154, 23254, 18705, 14949, 11916, 4 /* -10 */ 9548, 7620, 6100, 4904, 3906, 5 /* -5 */ 3121, 2501, 1991, 1586, 1277, 6 /* 0 */ 1024, 820, 655, 526, 423, 7 /* 5 */ 335, 272, 215, 172, 137, 8 /* 10 */ 110, 87, 70, 56, 45, 9 /* 15 */ 36, 29, 23, 18, 15,10 };
該數組是普通進程的優(yōu)先級和權重對應關系。數組元素是權重值，分別是優(yōu)先級從100-139或者nice值從-20-+19所對應的權重值。nice值（-20-+19）是從用戶空間看到的普通進程的優(yōu)先級，和內核空間的優(yōu)先級（100-139）一一對應。struct load_weight中的weight成員存放正是這些權重值。
中間結果數組prio_to_wmult[40] （kernel/sched/sched.h）
1 static const u32 prio_to_wmult[40] = { 2 /* -20 */ 48388, 59856, 76040, 92818, 118348, 3 /* -15 */ 147320, 184698, 229616, 287308, 360437, 4 /* -10 */ 449829, 563644, 704093, 875809, 1099582, 5 /* -5 */ 1376151, 1717300, 2157191, 2708050, 3363326, 6 /* 0 */ 4194304, 5237765, 6557202, 8165337, 10153587, 7 /* 5 */ 12820798, 15790321, 19976592, 24970740, 31350126, 8 /* 10 */ 39045157, 49367440, 61356676, 76695844, 95443717, 9 /* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153,10 };
該數組元素就是上個數組元素被NICE_0_LOAD除的結果，一一對應。struct load_weight中的inv_weight成員存放正是這些值。
下邊我們分析和權重設置相關的函數。從set_load_weight函數開始（kernel/sched/core.c）：
1 static void set_load_weight(struct task_struct *p) 2 { 3 int prio = p->static_prio - MAX_RT_PRIO; 4 struct load_weight *load = &p->se.load; 5 6 /* 7 * SCHED_IDLE tasks get minimal weight: 8 */ 9 if (p->policy == SCHED_IDLE) {10 load->weight = scale_load(WEIGHT_IDLEPRIO);11 load->inv_weight = WMULT_IDLEPRIO;12 return;13 }14 15 load->weight = scale_load(prio_to_weight[prio]);16 load->inv_weight = prio_to_wmult[prio];17 }
該函數用來設置進程p的權重。第3行將進程p的靜態(tài)優(yōu)先級轉換成數組下標（減去100，從100-139--->0-39）。第4行獲取當前進程的調度實體中的權重結構體指針，存入load中。第9-12行，如果當前進程是空閑進程，則設置相應的權重和中間計算結果。第15-16行，設置實時進程和普通進程的權重和中間計算結果。
由于就緒隊列中也包含權重結構體，所以也要對它們進行設置。使用以下函數（kernel/sched/fair.c）：
1 static inline void update_load_set(struct load_weight *lw, unsigned long w)2 {3 lw->weight = w;4 lw->inv_weight = 0;5 }
該函數用來設置就緒隊列的權重。
1 static inline void update_load_add(struct load_weight *lw, unsigned long inc)2 {3 lw->weight += inc;4 lw->inv_weight = 0;5 }
當有進程加入就緒隊列，使用該函數增加就緒隊列的權重。
1 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)2 {3 lw->weight -= dec;4 lw->inv_weight = 0;5 }
當有進程從就緒隊列移除時，使用該函數減少就緒隊列的權重。就緒隊列的load_weight.inv_weight成員總是0，因為不會使用到就緒隊列的該域。
4.計算進程延遲周期的相關函數。進程的延遲周期指的是將所有進程執(zhí)行一遍的時間。當就緒隊列中的進程數量不超出規(guī)定的時候，內核有一個固定的延遲周期供調度使用，但是當進程數量超出規(guī)定以后，就需要對該固定延遲周期進行擴展（不然隨著進程越多，每個進程分配的執(zhí)行時間會越少）。下面看看sched_slice函數（kernel/sched/fair.c）：
1 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) 2 { 3 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); 4 5 for_each_sched_entity(se) { 6 struct load_weight *load; 7 struct load_weight lw; 8 9 cfs_rq = cfs_rq_of(se);10 load = &cfs_rq->load;11 12 if (unlikely(!se->on_rq)) {13 lw = cfs_rq->load;14 15 update_load_add(&lw, se->load.weight);16 load = &lw;17 }18 slice = __calc_delta(slice, se->load.weight, load);19 }20 return slice;21 }
直接看第18行，__calc_delta用來計算當前進程在延遲周期中可占的時間（相當于“時間片”，就是當前進程可用的時間）。__calc_delta函數很強大，記得前邊在entity_tick函數中也調用過該函數（entity_tick--->update_curr--->calc_delta_fair--->__calc_delta），當時使用該函數是為了將進程運行過的物理時間（真實時間）轉換成虛擬時間；而在此處，我們用它來計算當前進程在延遲周期中可占的時間（相當于“時間片”）。前邊提過，__calc_delta中用到param1 * param2 / param3.weight這個公式（param代表該函數接收的參數），當param2的值固定不變（等于NICE_0_LOAD），param3（代表當前進程的權重）在變化時，該函數是用來轉換真實時間和虛擬時間的；當param3（代表當前cfs_rq的權重，cfs_rq->load->weight）的值固定不變，param2在變化（代表當前進程的權重）時，該函數則是用來計算當前進程應該運行的時間。因此第18行計算結果slice就是當前進程應該運行的真實時間。下面再看一個函數sched_vslice（kernel/sched/fair.c）：
1 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)2 {3 return calc_delta_fair(sched_slice(cfs_rq, se), se);4 }
該函數用來將進程應該運行的真實時間轉換成應該運行的虛擬時間，以供調度使用?？梢钥吹皆摵瘮嫡{用了cals_delta_fair來進行時間轉換，前邊已分析過，不再贅述。
5.選擇下一個需要調度的進程。所使用的函數是pick_next_task_fair，代碼如下（kernel/sched/fair.c）：
該函數會被賦給公平調度類的pick_next_task成員（.pick_next_task = pick_next_task_fair），在schedule函數中會調用該函數選擇下一個需要調用的進程，然后進行進程切換。第11-12行如果當前就緒隊列中的進程數量為0，則退出函數。第25-49行對所有的調度組進行遍歷，從中選擇下一個可調度的進程，而不只局限在當前隊列的當前組。第26行獲取當前調度實體，第34-37行如果存在一個當前調度實體（進程）并且正在運行，則更新進程的運行時間，否則就緒隊列cfs_rq.curr置為null，表示當前無進程運行。第47行獲取下一個調度實體，待會來分析該函數。第48行獲取下個調度實體所擁有的就緒隊列my_q（代表一個調度組），如果調度組非空，則進入下一次循環(huán)，在新的就緒隊列（調度組）中挑選下一個可調度進程，直到某個實體沒有自己的就緒隊列為止（遍歷完所有的調度組了）。退出循環(huán)后，可以發(fā)現此時的se是所遍歷的最后一個調度組的下個可運行實體。第51行獲取se對應的進程描述符，第58-77行，如果當前進程和下一個進程（se所對應的進程）不是同一個的話，則執(zhí)行if體，第59行將當前進程的調度實體指針裝入pse中，第61-72行如果當前進程和下一個調度的進程（se對應的進程）不屬于同一調度組，則進入循環(huán)。否則，執(zhí)行第75-76行，將當前進程放回就緒隊列，將下個進程從就緒隊列中拿出，這兩個函數涉及到了就緒隊列的出隊和入隊操作，我們在下邊分析。第61-73的循環(huán)根據當前實體和下個調度實體的節(jié)點深度進行調整（同一個級別的進程才能切換）。下面看看pick_next_entity，put_prev_entity和set_prev_entity函數代碼（kernel/sched/fair.c）：
1 static struct sched_entity * 2 pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr) 3 { 4 struct sched_entity *left = __pick_first_entity(cfs_rq); 5 struct sched_entity *se; 6 7 /* 8 * If curr is set we have to see if its left of the leftmost entity 9 * still in the tree, provided there was anything in the tree at all.10 */11 if (!left || (curr && entity_before(curr, left)))12 left = curr;13 14 se = left; /* ideally we run the leftmost entity */15 16 /*17 * Avoid running the skip buddy, if running something else can18 * be done without getting too unfair.19 */20 if (cfs_rq->skip == se) {21 struct sched_entity *second;22 23 if (se == curr) {24 second = __pick_first_entity(cfs_rq);25 } else {26 second = __pick_next_entity(se);27 if (!second || (curr && entity_before(curr, second)))28 second = curr;29 }30 31 if (second && wakeup_preempt_entity(second, left) < 1)32 se = second;33 }34 35 /*36 * Prefer last buddy, try to return the CPU to a preempted task.37 */38 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)39 se = cfs_rq->last;40 41 /*42 * Someone really wants this to run. If it's not unfair, run it.43 */44 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)45 se = cfs_rq->next;46 47 clear_buddies(cfs_rq, se);48 49 return se;50 }
該函數選擇下一個調度的實體。第4行將紅黑樹的最左邊實體賦給left，第11-12行如果紅黑樹的最左邊實體為空或者當前實體運行的虛擬時間小于下一個實體（繼續(xù)當前的實體），把當前實體賦給left，實際上left指向的是下一個要執(zhí)行的進程（該進程要么還是當前進程，要么是下一個進程），第14行將left賦給se，第20-33行如果se進程是需要跳過的進程（不能被調度），執(zhí)行if體，如果se進程是當前進程，則選擇紅黑數最左的進程賦給second，否則se進程已經是最左的進程，就把next指向的進程賦給second（next指向的是剛剛被喚醒的進程），第32行將second再次賦給se，se是挑選出來的下個進程。第38-45，再次判斷，要么把last指向的進程賦給se，要么把next指向進程賦給se，內核更傾向于把last賦給se，因為last是喚醒next進程的進程（一般就是當前進程），所以執(zhí)行l(wèi)ast就意味著不用切換進程，效率最高。第47行清理掉next和last域。第31，38，44行使用到的wakeup_preempt_entity函數我們在進程喚醒那塊再分析。
1 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) 2 { 3 /* 4 * If still on the runqueue then deactivate_task() 5 * was not called and update_curr() has to be done: 6 */ 7 if (prev->on_rq) 8 update_curr(cfs_rq); 9 10 /* throttle cfs_rqs exceeding runtime */11 check_cfs_rq_runtime(cfs_rq);12 13 check_spread(cfs_rq, prev);14 if (prev->on_rq) {15 update_stats_wait_start(cfs_rq, prev);16 /* Put 'current' back into the tree. */17 __enqueue_entity(cfs_rq, prev);18 /* in !on_rq case, update occurred at dequeue */19 update_entity_load_avg(prev, 1);20 }21 cfs_rq->curr = NULL;22 }
該函數將當前調度實體放回就緒隊列。第7-8行如果當前實體正在運行，更新其時間片。第17行將當前實體加入到就緒隊列中，待會分析__enqueue_entity函數。第21行將就緒隊列的curr域置為null，因為當前進程已經放回就緒隊列了，就表示當前沒有進程正在執(zhí)行了，因此curr為空。
1 static void 2 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 3 { 4 /* 'current' is not kept within the tree. */ 5 if (se->on_rq) { 6 /* 7 * Any task has to be enqueued before it get to execute on 8 * a CPU. So account for the time it spent waiting on the 9 * runqueue.10 */11 update_stats_wait_end(cfs_rq, se);12 __dequeue_entity(cfs_rq, se);13 }14 15 update_stats_curr_start(cfs_rq, se);16 cfs_rq->curr = se;17 #ifdef CONFIG_SCHEDSTATS18 /*19 * Track our maximum slice length, if the CPU's load is at20 * least twice that of our own weight (i.e. dont track it21 * when there are only lesser-weight tasks around):22 */23 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {24 se->statistics.slice_max = max(se->statistics.slice_max,25 se->sum_exec_runtime - se->prev_sum_exec_runtime);26 }27 #endif28 se->prev_sum_exec_runtime = se->sum_exec_runtime;29 }
該函數將下一個被調度實體從就緒隊列中取出。第12行實現取出操作，待會分析該函數。第16行將取出的調度實體指針賦給就緒隊列的curr，那么此時就有了正在運行的進程了。后邊的代碼更新當前進程的時間統計信息。
6.就緒隊列的入隊和出隊操作（kernel/sched/fair.c）。
1 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 2 { 3 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; 4 struct rb_node *parent = NULL; 5 struct sched_entity *entry; 6 int leftmost = 1; 7 8 /* 9 * Find the right place in the rbtree:10 */11 while (*link) {12 parent = *link;13 entry = rb_entry(parent, struct sched_entity, run_node);14 /*15 * We dont care about collisions. Nodes with16 * the same key stay together.17 */18 if (entity_before(se, entry)) {19 link = &parent->rb_left;20 } else {21 link = &parent->rb_right;22 leftmost = 0;23 }24 }25 26 /*27 * Maintain a cache of leftmost tree entries (it is frequently28 * used):29 */30 if (leftmost)31 cfs_rq->rb_leftmost = &se->run_node;32 33 rb_link_node(&se->run_node, parent, link);34 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);35 }
該函數實現入隊操作。第3行獲取就緒隊列中紅黑樹的根節(jié)點，將樹根指針保存在link中。第12行parent暫時指向樹根。第13行獲得樹根節(jié)點的調度實體，保存在entry中。第18-22行，比較要入隊的實體中的已運行虛擬時間和樹根實體中的該信息，如果前者小的話，就要插入到樹的左子樹上（link指向樹根的左孩子，再次進入循環(huán)，類似于遞歸），否則就要插入到樹的右子樹上（同上）。這塊就將進程的調度策略展現的淋漓盡致：根據進程已運行的虛擬時間來決定進程的調度，紅黑樹的左子樹比右子樹要先被調度，已運行的虛擬時間越小的進程越在樹的左側。第30-31行，如果入隊的實體最終被插在左孩子上（該入隊實體仍是就緒隊列上最靠前的實體，下次就會被調用），那么就要讓就緒隊列的rb_leftmost指向入隊實體。rb_leftmost指針始終指向下次要被調度的實體（進程）。最后兩行要給紅黑數重新著色。
1 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 2 { 3 if (cfs_rq->rb_leftmost == &se->run_node) { 4 struct rb_node *next_node; 5 6 next_node = rb_next(&se->run_node); 7 cfs_rq->rb_leftmost = next_node; 8 } 9 10 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);11 }
該函數實現出隊操作。第3行判斷要出隊的實體是不是紅黑樹最左側的孩子（rb_leftmost所指向的），如果不是的話，第10行直接刪除該出隊實體。否則執(zhí)行if體，第6行找到出隊實體的下一個實體（中序遍歷的下一個節(jié)點，也就是當出隊實體刪除后，最左邊的孩子），賦給next_node。第7行讓rb_leftmost指向next_node。在刪除掉要出隊實體后，下一個需要被調度的實體也就設置好了。
7.睡眠進程被喚醒后搶占當前進程。當某個資源空出來后，等待該資源的進程就會被喚醒，喚醒后也許就要搶占當前進程，因此這塊的函數也需要分析（kernel/sched/core.c）。
1 static int 2 try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) 3 { 4 unsigned long flags; 5 int cpu, success = 0; 6 7 /* 8 * If we are going to wake up a thread waiting for CONDITION we 9 * need to ensure that CONDITION=1 done by the caller can not be10 * reordered with p->state check below. This pairs with mb() in11 * set_current_state() the waiting thread does.12 */13 smp_mb__before_spinlock();14 raw_spin_lock_irqsave(&p->pi_lock, flags);15 if (!(p->state & state))16 goto out;17 18 success = 1; /* we're going to change ->state */19 cpu = task_cpu(p);20 21 if (p->on_rq && ttwu_remote(p, wake_flags))22 goto stat;23 24 #ifdef CONFIG_SMP25 /*26 * If the owning (remote) cpu is still in the middle of schedule() with27 * this task as prev, wait until its done referencing the task.28 */29 while (p->on_cpu)30 cpu_relax();31 /*32 * Pairs with the smp_wmb() in finish_lock_switch().33 */34 smp_rmb();35 36 p->sched_contributes_to_load = !!task_contributes_to_load(p);37 p->state = TASK_WAKING;38 39 if (p->sched_class->task_waking)40 p->sched_class->task_waking(p);41 42 cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);43 if (task_cpu(p) != cpu) {44 wake_flags |= WF_MIGRATED;45 set_task_cpu(p, cpu);46 }47 #endif /* CONFIG_SMP */48 49 ttwu_queue(p, cpu);50 stat:51 ttwu_stat(p, cpu, wake_flags);52 out:53 raw_spin_unlock_irqrestore(&p->pi_lock, flags);54 55 return success;56 }
該函數會喚醒參數p指定的進程，將進程加入就緒隊列中等待調度。第15行判斷p進程的狀態(tài)碼和傳進來的狀態(tài)碼是否一致，不一致的話函數結束（不一致則說明進程等待的條件未滿足）。第19行獲取要喚醒進程p原先所在的cpu號。第37行設置要喚醒進程p的狀態(tài)為TASK_WAKING。第40行執(zhí)行進程p的調度類中的task_waking函數，該函數指針指向了task_waking_fair函數，該函數主要是對睡眠進程的已運行虛擬時間進行補償，待會分析該函數。第42行為剛喚醒進程p選擇一個合適的就緒隊列供其加入，返回就緒隊列所在的cpu號。第43行如果進程p所在的原先cpu和為它挑選的cpu不是同一個的話，第45行更改進程p的cpu號。
1 void wake_up_new_task(struct task_struct *p) 2 { 3 unsigned long flags; 4 struct rq *rq; 5 6 raw_spin_lock_irqsave(&p->pi_lock, flags); 7 #ifdef CONFIG_SMP 8 /* 9 * Fork balancing, do it here and not earlier because:10 * - cpus_allowed can change in the fork path11 * - any previously selected cpu might disappear through hotplug12 */13 set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));14 #endif15 16 /* Initialize new task's runnable average */17 init_task_runnable_average(p);18 rq = __task_rq_lock(p);19 activate_task(rq, p, 0);20 p->on_rq = 1;21 trace_sched_wakeup_new(p, true);22 check_preempt_curr(rq, p, WF_FORK);23 #ifdef CONFIG_SMP24 if (p->sched_class->task_woken)25 p->sched_class->task_woken(rq, p);26 #endif27 task_rq_unlock(rq, p, &flags);28 }
該函數用來喚醒剛創(chuàng)建好的進程，而上個函數是用來喚醒睡眠中的進程。第13行為將喚醒的進程p設置合適的cpu。第17行設置進程p的可運行時間長度（類似“時間片”），第19行activate_task函數主要將喚醒的進程p加入就緒隊列,并更新隊列的時間,初始化進程p的時間等，該函數中的調用關系大致為activate_task->enqueue_task->enqueue_task_fair(p->sched_class->enqueue_task)->enqueue_entity。第22行check_preempt_curr函數調用了check_preempt_wakeup函數，來檢查喚醒進程是否能搶占當前進程，下面分析該函數（kernel/sched/fair.c）。
1 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) 2 { 3 struct task_struct *curr = rq->curr; 4 struct sched_entity *se = &curr->se, *pse = &p->se; 5 struct cfs_rq *cfs_rq = task_cfs_rq(curr); 6 int scale = cfs_rq->nr_running >= sched_nr_latency; 7 int next_buddy_marked = 0; 8 9 if (unlikely(se == pse))10 return;11 12 /*13 * This is possible from callers such as move_task(), in which we14 * unconditionally check_prempt_curr() after an enqueue (which may have15 * lead to a throttle). This both saves work and prevents false16 * next-buddy nomination below.17 */18 if (unlikely(throttled_hierarchy(cfs_rq_of(pse))))19 return;20 21 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {22 set_next_buddy(pse);23 next_buddy_marked = 1;24 }25 26 /*27 * We can come here with TIF_NEED_RESCHED already set from new task28 * wake up path.29 *30 * Note: this also catches the edge-case of curr being in a throttled31 * group (e.g. via set_curr_task), since update_curr() (in the32 * enqueue of curr) will have resulted in resched being set. This33 * prevents us from potentially nominating it as a false LAST_BUDDY34 * below.35 */36 if (test_tsk_need_resched(curr))37 return;38 39 /* Idle tasks are by definition preempted by non-idle tasks. */40 if (unlikely(curr->policy == SCHED_IDLE) &&41 likely(p->policy != SCHED_IDLE))42 goto preempt;43 44 /*45 * do not preempt non-idle tasks (their preemption46 * is driven by the tick):47 */48 if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))49 return;50 51 find_matching_se(&se, &pse);52 update_curr(cfs_rq_of(se));53 BUG_ON(!pse);54 if (wakeup_preempt_entity(se, pse) == 1) {55 /*56 * Bias pick_next to pick the sched entity that is57 * triggering this preemption.58 */59 if (!next_buddy_marked)60 set_next_buddy(pse);61 goto preempt;62 }63 64 return;65 66 preempt:67 resched_task(curr);68 /*69 * Only set the backward buddy when the current task is still70 * on the rq. This can happen when a wakeup gets interleaved71 * with schedule on the ->pre_schedule() or idle_balance()72 * point, either of which can * drop the rq lock.73 *74 * Also, during early boot the idle thread is in the fair class,75 * for obvious reasons its a bad idea to schedule back to it.76 */77 if (unlikely(!se->on_rq || curr == rq->idle))78 return;79 80 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))81 set_last_buddy(se);82 }
第21-24行，如果開啟了NEXT_BUDDY并且喚醒的進程不是新進程（而是睡眠進程），那么第22行就將cfs_rq的next指針指向喚醒的進程，并且設置標記。第36行如果當前進程可以被搶占，函數直接返回。否則，第40-42行如果當前進程是空閑進程并且被喚醒的進程不是空閑進程，則跳到preempt處，設置need_resched標志，完成搶占設置。第48行，如果被喚醒進程是空閑進程或者批處理進程，直接返回，這些進程不能搶占別的進程。第51行如果當前進程和被喚醒進程不在同一級別（同一個調度組），則尋找它們的祖先parent，把它們調整到同一級別，才能進行虛擬運行時間的比較，進而決定能否搶占。第54行，對當前進程和被喚醒進程的虛擬運行時間進行比較，可以搶占的話（喚醒進程的虛擬時間小于當前進程）執(zhí)行if體，跳到preempt處完成搶占。否則所有都不滿足的話，當前進程不能被搶占，執(zhí)行第64行返回，隨后分析該函數。第80-81行如果開啟了LAST_BUDDY，就將cfs_rq的last指針指向喚醒進程的進程。在pick_next_entity函數中，next和last所指的進程會先于就緒隊列的left進程被選擇。下面分析下wakeup_preempt_entity函數（kernel/sched/fair.c）。
1 static int 2 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) 3 { 4 s64 gran, vdiff = curr->vruntime - se->vruntime; 5 6 if (vdiff <= 0) 7 return -1; 8 9 gran = wakeup_gran(curr, se);10 if (vdiff > gran)11 return 1;12 13 return 0;14 }
該函數是要保證在se實體在搶占curr實體時，curr實體已經運行過一段時間（具體而言，物理時間1ms），第9行wakeup_gran函數是將sysctl_sched_wakeup_granularity的值（1ms）轉換成se實體的虛擬時間，保存在gran中，第10行比較vdiff和gran大小，實際上是比較curr->vruntime 和 se->vruntime+gran，因此就是想讓curr實體多執(zhí)行gran時間，才能被搶占。
最后我們再分析下 try_to_wake_up函數中第40行遺留的那個函數指針task_waking，該指針指向了task_waking_fair函數，代碼如下（kernel/sched/fair.c）：
1 static void task_waking_fair(struct task_struct *p) 2 { 3 struct sched_entity *se = &p->se; 4 struct cfs_rq *cfs_rq = cfs_rq_of(se); 5 u64 min_vruntime; 6 7 #ifndef CONFIG_64BIT 8 u64 min_vruntime_copy; 9 10 do {11 min_vruntime_copy = cfs_rq->min_vruntime_copy;12 smp_rmb();13 min_vruntime = cfs_rq->min_vruntime;14 } while (min_vruntime != min_vruntime_copy);15 #else16 min_vruntime = cfs_rq->min_vruntime;17 #endif18 19 se->vruntime -= min_vruntime;20 record_wakee(p);21 }
該函數完成對睡眠進程的虛擬時間補償?？紤]到睡眠時間長時間沒有運行，因此第19行從喚醒進程se的已運行虛擬時間中減去就緒隊列的最小虛擬時間，做點補償，讓其可以多運行一點時間。
8.新進程的處理函數（kernel/sched/fair.c）：
1 static void task_fork_fair(struct task_struct *p) 2 { 3 struct cfs_rq *cfs_rq; 4 struct sched_entity *se = &p->se, *curr; 5 int this_cpu = smp_processor_id(); 6 struct rq *rq = this_rq(); 7 unsigned long flags; 8 9 raw_spin_lock_irqsave(&rq->lock, flags);10 11 update_rq_clock(rq);12 13 cfs_rq = task_cfs_rq(current);14 curr = cfs_rq->curr;15 16 /*17 * Not only the cpu but also the task_group of the parent might have18 * been changed after parent->se.parent,cfs_rq were copied to19 * child->se.parent,cfs_rq. So call __set_task_cpu() to make those20 * of child point to valid ones.21 */22 rcu_read_lock();23 __set_task_cpu(p, this_cpu);24 rcu_read_unlock();25 26 update_curr(cfs_rq);27 28 if (curr)29 se->vruntime = curr->vruntime;30 place_entity(cfs_rq, se, 1);31 32 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {33 /*34 * Upon rescheduling, sched_class::put_prev_task() will place35 * 'current' within the tree based on its new key value.36 */37 swap(curr->vruntime, se->vruntime);38 resched_task(rq->curr);39 }40 41 se->vruntime -= cfs_rq->min_vruntime;42 43 raw_spin_unlock_irqrestore(&rq->lock, flags);44 }
該函數在do_fork--->copy_process函數中調用，用來設置新創(chuàng)建進程的虛擬時間信息。第5行獲取當前的cpu號，第23行為新進程設置該cpu號。第29行將當前進程（父進程）的虛擬運行時間拷貝給新進程（子進程）。第30行的place_entity函數完成新進程的“時間片”計算以及虛擬時間懲罰，之后將新進程加入紅黑數中，待會分析。第32行如果設置了子進程先于父進程運行的標志并且當前進程不為空且當前進程已運行的虛擬時間比新進程小，則執(zhí)行if體，第37行交換當前進程和新進程的虛擬時間（新進程的虛擬時間變小，就排在了紅黑樹的左側，當前進程之前，下次就能被調度），第38行設置重新調度標志。第41行給新進程的虛擬運行時間減去隊列的最小虛擬時間來做一點補償（因為在上邊的place_entity函數中給新進程的虛擬時間加了一次min_vruntime，所以在這里要減去），再來看看place_entity函數（kernel/sched/fair.c）：
1 static void 2 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) 3 { 4 u64 vruntime = cfs_rq->min_vruntime; 5 6 /* 7 * The 'current' period is already promised to the current tasks, 8 * however the extra weight of the new task will slow them down a 9 * little, place the new task so that it fits in the slot that10 * stays open at the end.11 */12 if (initial && sched_feat(START_DEBIT))13 vruntime += sched_vslice(cfs_rq, se);14 15 /* sleeps up to a single latency don't count. */16 if (!initial) {17 unsigned long thresh = sysctl_sched_latency;18 19 /*20 * Halve their sleep time's effect, to allow21 * for a gentler effect of sleepers:22 */23 if (sched_feat(GENTLE_FAIR_SLEEPERS))24 thresh >>= 1;25 26 vruntime -= thresh;27 }28 29 /* ensure we never gain time by being placed backwards. */30 se->vruntime = max_vruntime(se->vruntime, vruntime);31 }
該函數完成新進程的“時間片”計算和虛擬時間懲罰，并且將新進程加入就緒隊列。第4行將就緒隊列的min_vruntime值存入vruntime中，第12-13行，如果initial標志為1的話（說明當前計算的是新進程的時間），將計算出的新進程的虛擬時間片累加到vruntime中，累加到原因是調度系統要保證先把就緒隊列中的所有的進程執(zhí)行一遍之后才能執(zhí)行新進程，一會具體解釋。第16-17行，如果當前計算的不是新進程（睡眠的進程），把一個延遲周期的長度sysctl_sched_latency（6ms）賦給thresh，第24行thresh減半，第26行睡眠進程的虛擬運行時間減去減半后的thresh，因為睡眠進程好長時間未運行，因此要進行虛擬時間補償，把它已運行的虛擬時間減小一點，使得它能多運行一會。第30行將設置好的虛擬時間保存到進程調度實體的vruntime域。下面解釋下為什么要對新進程進行虛擬時間懲罰，其實原因只有一個，就是調度系統要保證將就緒隊列中現有的進程執(zhí)行一遍之后再執(zhí)行新進程，那么就必須使新進程的 vruntime=cfs_rq->min_vruntime+新進程的虛擬時間片，才能使得新進程插入到紅黑樹的右邊，最后參與調度，不然無法保證所有進程在新進程之前執(zhí)行。
最后，分析下和調度相關的這些函數執(zhí)行的時機
前面在介紹這些函數的時候，基本上都提到了會在哪里調用這些函數，最后，我們再系統總結一下：
進程調度分為兩個部分：一是進程信息的修改，二是進程切換。進程切換只有一個函數schedule，schedule的運行時機我們最后分析。其它函數的運行時機如下：
1.scheduler_tick函數是在每個時鐘中斷中被調用，用來更新當前進程運行的時間。
2.effective_prio函數是在創(chuàng)建一個新進程或者用戶使用nice系統調用設置進程的優(yōu)先級時調用，用來設置進程的在內核中優(yōu)先級（不同于nice值）。
3.set_load_weight函數也是在創(chuàng)建新進程或者用戶使用nice()設置進程的優(yōu)先級時調用，用來設置進程的權重。該函數和2中的函數其實是配套使用的，當設置或者改變了一個進程的優(yōu)先級時，要么就要為這個進程設置或者改變該優(yōu)先級對應的權重。
4.sched_slice函數主要是在scheduler_tick->...->check_preempt_tick中調用（別的地方也有），因此也是每個時鐘周期調用一次，用來計算當前進程應該執(zhí)行的“時間片”，進而才能判斷進程是否已經超出它的時間片，超出的話就要設置搶占標志，切換別的進程。
5.pick_next_task_fair函數schedule中調用，用來選擇下一個要被調度的進程，然后才能切換進程。它的執(zhí)行時機就是schedule的執(zhí)行時機，隨后分析。
6.__enqueue_entity/__dequeue_entity函數是在需要入就緒隊列或者出就緒隊列的地方被調用，因此使用它們的地方較多，比如schedule中調用（間接調用），就不一一分析了。
7.try_to_wake_up/wake_up_new_task函數，前者在進程所等待的資源滿足時被調用（一般在中斷內調用）；后者是在創(chuàng)建好新進程后被調用。都是用來喚醒進程的，前者喚醒睡眠進程，后者喚醒新進程并將進程加入就緒隊列。
8.task_fork_fair函數也是在新進程被創(chuàng)建好后調用，用來設置新進程的“時間片”等信息，設置好以后新進程就可以被喚醒了。所以該函數和wake_up_new_task函數調用時機是一樣的。
最后，我們分析schedule函數的調用時機。該函數是唯一實現進程切換的函數。
在分析schedule函數的調用時機之前，我們先為大家介紹下“內核控制路徑“的概念。所謂內核控制路徑，就是由中斷或者異常引出的執(zhí)行路徑，說白了，執(zhí)行中斷或者異常處理程序時就處在內核控制路徑中，此時代表的也是當前進程。內核控制路徑可以嵌套（也就是可以嵌套中斷），但是無論嵌套多少，最終都要回到當前進程中，也就是說要從內核控制路徑中返回，不可以在內核控制路徑中進行進程切換（因此中斷處理程序中不允許調用能引起進程睡眠的函數）。說到底，內核要么處在進程中，要么處在內核控制路徑中（其實內核控制路徑也代表當前進程，因為其有特殊性，所以我們單列出來談），不會再有別的什么路徑了。那么進程切換的時機，或者說schedule函數被調用的時機，也就只可能發(fā)生于上述兩種路徑中。那么，1.當在進程中調用schedule函數時（就是ULK這本書上說的直接調用），表明當前進程因為等待資源或者別的原因需要掛起，主動放棄使用cpu，調用schedule函數切換到別的進程中；2.當在內核控制路徑中調用schedule函數時（上邊說過了，內核控制路徑中不允許切換進程），其實是在內核控制路徑返回進程時調用（該時機就是ULK上說的延遲調用），說明有更重要的進程等待執(zhí)行，需要搶占當前進程，因此在中斷處理程序/異常處理程序返回時都要去檢查當前進程能否被搶占，可以搶占的話就要調用schedule函數進行進程切換，包括從系統調用中返回用戶空間時也要檢查（這是統一的，因為系統調用本身也是異常，因此從系統調用中返回相當于從異常處理程序中返回，通過系統調用進入到內核態(tài)也可以說是內核控制路徑，但是一般不這么叫）當前進程的搶占標志，能發(fā)生搶占的話就要去調用schedule函數。至此，進程切換的時機就分析完了。很好記的，要么是進程上下文發(fā)生進程切換（主動調用schedule），要么是從中斷返回時切換，因此每次中斷返回時必須要檢查能否發(fā)生搶占，包括從系統調用返回也屬于這種情形。
至此，進程調度機制咱們就分析完了（其實只分析了CFS調度）。實時進程調度以后再分析！
參考書籍：《深入理解linux內核》
《深入理解linux內核架構》
參考文章：blog.csdn.net/wudongxu/article/details/8574737
