本文檔基于linux3.14 ，linux內(nèi)核調(diào)度詳解

　　1、概述

　　1.1、調(diào)度策略

　　定義位于

　　SCHED_NORMAL：普通的分時(shí)進(jìn)程，使用的fair_sched_class調(diào)度類

　　SCHED_FIFO：先進(jìn)先出的實(shí)時(shí)進(jìn)程。當(dāng)調(diào)用程序把CPU分配給進(jìn)程的時(shí)候，它把該進(jìn)程描述符保留在運(yùn)行隊(duì)列鏈表的當(dāng)前位置。此調(diào)度策略的進(jìn)程一旦使用CPU則一直運(yùn)行。如果沒(méi)有其他可運(yùn)行的更高優(yōu)先級(jí)實(shí)時(shí)進(jìn)程，進(jìn)程就繼續(xù)使用CPU，想用多久就用多久，即使還有其他具有相同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程處于可運(yùn)行狀態(tài)。使用的是rt_sched_class調(diào)度類。

　　SCHED_RR：時(shí)間片輪轉(zhuǎn)的實(shí)時(shí)進(jìn)程。當(dāng)調(diào)度程序把CPU分配給進(jìn)程的時(shí)候，它把該進(jìn)程的描述符放在運(yùn)行隊(duì)列鏈表的末尾。這種策略保證對(duì)所有具有相同優(yōu)先級(jí)的SCHED_RR實(shí)時(shí)進(jìn)程進(jìn)行公平分配CPU時(shí)間，使用的rt_sched_class調(diào)度類

　　SCHED_BATCH：是SCHED_NORMAL的分化版本。采用分時(shí)策略，根據(jù)動(dòng)態(tài)優(yōu)先級(jí)，分配CPU資源。在有實(shí)時(shí)進(jìn)程的時(shí)候，實(shí)時(shí)進(jìn)程優(yōu)先調(diào)度。但針對(duì)吞吐量?jī)?yōu)化，除了不能搶占外與常規(guī)進(jìn)程一樣，允許任務(wù)運(yùn)行更長(zhǎng)時(shí)間，更好使用高速緩存，適合于成批處理的工作，使用的fair_shed_class調(diào)度類

　　SCHED_IDLE：優(yōu)先級(jí)最低，在系統(tǒng)空閑時(shí)運(yùn)行，使用的是idle_sched_class調(diào)度類，給0號(hào)進(jìn)程使用

　　SCHED_DEADLINE：新支持的實(shí)時(shí)進(jìn)程調(diào)度策略，針對(duì)突發(fā)型計(jì)算，并且對(duì)延遲和完成時(shí)間敏感的任務(wù)使用，基于EDF（earliest deadline first）,使用的是dl_sched_class調(diào)度類。

　　1.2、調(diào)度類

　　Next:指向下一個(gè)調(diào)度類,用于在函數(shù)pick_next_task、check_preempt_curr、set_rq_online、set_rq_offline用于遍歷整個(gè)調(diào)度類根據(jù)調(diào)度類的優(yōu)先級(jí)選擇調(diào)度類。優(yōu)先級(jí)為stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sc*hed_class

　　enqueue_task:將任務(wù)加入到調(diào)度類中

　　dequeue_task:將任務(wù)從調(diào)度類中移除

　　yield_task/ yield_to_task:主動(dòng)放棄CPU

　　check_preempt_curr:檢查當(dāng)前進(jìn)程是否可被強(qiáng)占

　　pick_next_task:從調(diào)度類中選出下一個(gè)要運(yùn)行的進(jìn)程

　　put_prev_task:將進(jìn)程放回到調(diào)度類中

　　select_task_rq:為進(jìn)程選擇一個(gè)合適的cpu的運(yùn)行隊(duì)列

　　migrate_task_rq:遷移到另外的cpu運(yùn)行隊(duì)列

　　pre_schedule:調(diào)度以前調(diào)用

　　post_schedule:通知調(diào)度器完成切換

　　task_waking、task_woken:用于進(jìn)程喚醒

　　set_cpus_allowed:修改進(jìn)程cpu親和力affinity

　　rq_online:啟動(dòng)運(yùn)行隊(duì)列

　　rq_offline:關(guān)閉運(yùn)行隊(duì)列

　　set_curr_task:當(dāng)進(jìn)程改變調(diào)度類或者進(jìn)程組時(shí)被調(diào)用

　　task_tick:將會(huì)引起進(jìn)程切換，驅(qū)動(dòng)運(yùn)行running強(qiáng)占。由time_tick調(diào)用

　　task_fork:進(jìn)程創(chuàng)建時(shí)調(diào)用，不同調(diào)度策略的進(jìn)程初始化不一樣

　　task_dead:進(jìn)程結(jié)束時(shí)調(diào)用

　　switched_from、switched_to:進(jìn)程改變調(diào)度器時(shí)使用

　　prio_changed:改變進(jìn)程優(yōu)先級(jí)

　　1.3、調(diào)度觸發(fā)

　　調(diào)度的觸發(fā)主要有兩種方式，一種是本地定時(shí)中斷觸發(fā)調(diào)用scheduler_tick函數(shù)，然后使用當(dāng)前運(yùn)行進(jìn)程的調(diào)度類中的task_tick，另外一種則是主動(dòng)調(diào)用schedule，不管是哪一種最終都會(huì)調(diào)用到__schedule函數(shù)，該函數(shù)調(diào)用pick_netx_task，通過(guò)rq->nr_running ==rq->cfs.h_nr_running判斷出如果當(dāng)前運(yùn)行隊(duì)列中的進(jìn)程都在cfs調(diào)度器中，則直接調(diào)用cfs的調(diào)度類（內(nèi)核代碼里面這一判斷使用了likely說(shuō)明大部分情況都是滿足該條件的）。如果運(yùn)行隊(duì)列不都在cfs中，則通過(guò)優(yōu)先級(jí)stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sched_class遍歷選出下一個(gè)需要運(yùn)行的進(jìn)程。然后進(jìn)程任務(wù)切換。

　　處于TASK_RUNNING狀態(tài)的進(jìn)程才會(huì)被進(jìn)程調(diào)度器選擇，其他狀態(tài)不會(huì)進(jìn)入調(diào)度器。系統(tǒng)發(fā)生調(diào)度的時(shí)機(jī)如下：

　　à調(diào)用cond_resched()時(shí)

　　à顯式調(diào)用schedule()時(shí)

　　à從中斷上下文返回時(shí)

　　當(dāng)內(nèi)核開啟搶占時(shí)，會(huì)多出幾個(gè)調(diào)度時(shí)機(jī)如下：

　　à在系統(tǒng)調(diào)用或者中斷上下文中調(diào)用preemt_enable()時(shí)（多次調(diào)用系統(tǒng)只會(huì)在最后一次調(diào)用時(shí)會(huì)調(diào)度）

　　à在中斷上下文中，從中斷處理函數(shù)返回到可搶占的上下文時(shí)

　　1.4、__schedule的實(shí)現(xiàn)

　　分析_schedule的實(shí)現(xiàn)有利于理解調(diào)度類的實(shí)體如果在

　　其中有幾個(gè)重要的與調(diào)度器密切相關(guān)的函數(shù)：

　　pre_scheduleà prev->sched_class->pre_schedule 在調(diào)度以前調(diào)用

　　put_prev_taskàprev->sched_class->put_prev_task 將前一個(gè)進(jìn)程調(diào)度以前放回調(diào)度器中

　　pick_next_taskà class->pick_next_task從調(diào)度器中選出下一個(gè)需要運(yùn)行的進(jìn)程

　　post_scheduleà rq->curr->sched_class->post_scheduleCFS中為NULL

　　2、 CFS調(diào)度

　　該部分代碼位于linux/kernel/sched/fair.c中

　　定義了const struct

　　sched_classfair_sched_class，這個(gè)是CFS的調(diào)度類定義的對(duì)象。其中基本包含了CFS調(diào)度的所有實(shí)現(xiàn)。

　　CFS實(shí)現(xiàn)三個(gè)調(diào)度策略：

　　1> SCHED_NORMAL這個(gè)調(diào)度策略是被常規(guī)任務(wù)使用

　　2> SCHED_BATCH 這個(gè)策略不像常規(guī)的任務(wù)那樣頻繁的搶占，以犧牲交互性為代價(jià)下，因而允許任務(wù)運(yùn)行更長(zhǎng)的時(shí)間以更好的利用緩存，這種策略適合批處理

　　3> SCHED_IDLE 這是nice值甚至比19還弱，但是為了避免陷入優(yōu)先級(jí)導(dǎo)致問(wèn)題，這個(gè)問(wèn)題將會(huì)死鎖這個(gè)調(diào)度器，因而這不是一個(gè)真正空閑定時(shí)調(diào)度器

　　CFS調(diào)度類：

　　n enqueue_task(…) 當(dāng)任務(wù)進(jìn)入runnable狀態(tài)，這個(gè)回調(diào)將把這個(gè)任務(wù)的調(diào)度實(shí)體（entity）放入紅黑樹并且增加nr_running變量的值

　　n dequeue_task(…) 當(dāng)任務(wù)不再是runnable狀態(tài)，這個(gè)回調(diào)將會(huì)把這個(gè)任務(wù)的調(diào)度實(shí)體從紅黑樹中取出，并且減少nr_running變量的值

　　n yield_task(…) 除非compat_yield sysctl是打開的，這個(gè)回調(diào)函數(shù)基本上就是一個(gè)dequeue后跟一個(gè)enqueue，這那種情況下，他將任務(wù)的調(diào)度實(shí)體放入紅黑樹的最右端

　　n check_preempt_curr(…) 這個(gè)回調(diào)函數(shù)是檢查一個(gè)任務(wù)進(jìn)入runnable狀態(tài)是否應(yīng)該搶占當(dāng)前運(yùn)行的任務(wù)

　　n pick_next_task(…) 這個(gè)回調(diào)函數(shù)選出下一個(gè)最合適運(yùn)行的任務(wù)

　　n set_curr_task(…) 當(dāng)任務(wù)改變他的調(diào)度類或者改變他的任務(wù)組，將調(diào)用該回調(diào)函數(shù)

　　n task_tick(…) 這個(gè)回調(diào)函數(shù)大多數(shù)是被time tick調(diào)用。他可能引起進(jìn)程切換。這就驅(qū)動(dòng)了運(yùn)行時(shí)搶占

　　2.1、調(diào)度實(shí)體

　　其中幾個(gè)重要的變量

　　每一個(gè)進(jìn)程的task_struct中都嵌入了sched_entry對(duì)象，所以進(jìn)程是可調(diào)度的實(shí)體，但是可調(diào)度的實(shí)體不一定是進(jìn)程，也可能是進(jìn)程組。

　　2.2、CFS調(diào)度

　　Tcik 中斷，主要會(huì)更新調(diào)度信息，然后調(diào)整當(dāng)前進(jìn)程在紅黑樹中的位置。調(diào)整完成以后如果當(dāng)前進(jìn)程不再是最左邊的葉子，就標(biāo)記為Need_resched標(biāo)志，中斷返回時(shí)就會(huì)調(diào)用scheduler()完成切換、否則當(dāng)前進(jìn)程繼續(xù)占用CPU。從這里可以看出CFS拋棄了傳統(tǒng)時(shí)間片概念。Tick中斷只需要更新紅黑樹。

　　紅黑樹鍵值即為vruntime，該值通過(guò)調(diào)用update_curr函數(shù)進(jìn)行更新。這個(gè)值為64位的變量，會(huì)一直遞增，__enqueue_entity中會(huì)將vruntime作為鍵值將要入隊(duì)的實(shí)體插入到紅黑樹中。__pick_first_entity會(huì)將紅黑樹中最左側(cè)即vruntime最小的實(shí)體取出。

　　更多信息可以來(lái)這里獲取==>>電子技術(shù)應(yīng)用-AET<<