本文檔基于linux3.14 ,linux內(nèi)核調(diào)度詳解
1、概述
1.1、調(diào)度策略
定義位于
SCHED_NORMAL:普通的分時進(jìn)程,使用的fair_sched_class調(diào)度類
SCHED_FIFO:先進(jìn)先出的實(shí)時進(jìn)程。當(dāng)調(diào)用程序把CPU分配給進(jìn)程的時候,它把該進(jìn)程描述符保留在運(yùn)行隊(duì)列鏈表的當(dāng)前位置。此調(diào)度策略的進(jìn)程一旦使用CPU則一直運(yùn)行。如果沒有其他可運(yùn)行的更高優(yōu)先級實(shí)時進(jìn)程,進(jìn)程就繼續(xù)使用CPU,想用多久就用多久,即使還有其他具有相同優(yōu)先級的實(shí)時進(jìn)程處于可運(yùn)行狀態(tài)。使用的是rt_sched_class調(diào)度類。
SCHED_RR:時間片輪轉(zhuǎn)的實(shí)時進(jìn)程。當(dāng)調(diào)度程序把CPU分配給進(jìn)程的時候,它把該進(jìn)程的描述符放在運(yùn)行隊(duì)列鏈表的末尾。這種策略保證對所有具有相同優(yōu)先級的SCHED_RR實(shí)時進(jìn)程進(jìn)行公平分配CPU時間,使用的rt_sched_class調(diào)度類
SCHED_BATCH:是SCHED_NORMAL的分化版本。采用分時策略,根據(jù)動態(tài)優(yōu)先級,分配CPU資源。在有實(shí)時進(jìn)程的時候,實(shí)時進(jìn)程優(yōu)先調(diào)度。但針對吞吐量優(yōu)化,除了不能搶占外與常規(guī)進(jìn)程一樣,允許任務(wù)運(yùn)行更長時間,更好使用高速緩存,適合于成批處理的工作,使用的fair_shed_class調(diào)度類
SCHED_IDLE:優(yōu)先級最低,在系統(tǒng)空閑時運(yùn)行,使用的是idle_sched_class調(diào)度類,給0號進(jìn)程使用
SCHED_DEADLINE:新支持的實(shí)時進(jìn)程調(diào)度策略,針對突發(fā)型計(jì)算,并且對延遲和完成時間敏感的任務(wù)使用,基于EDF(earliest deadline first),使用的是dl_sched_class調(diào)度類。
1.2、調(diào)度類
Next:指向下一個調(diào)度類,用于在函數(shù)pick_next_task、check_preempt_curr、set_rq_online、set_rq_offline用于遍歷整個調(diào)度類根據(jù)調(diào)度類的優(yōu)先級選擇調(diào)度類。優(yōu)先級為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:主動放棄CPU
check_preempt_curr:檢查當(dāng)前進(jìn)程是否可被強(qiáng)占
pick_next_task:從調(diào)度類中選出下一個要運(yùn)行的進(jìn)程
put_prev_task:將進(jìn)程放回到調(diào)度類中
select_task_rq:為進(jìn)程選擇一個合適的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:啟動運(yùn)行隊(duì)列
rq_offline:關(guān)閉運(yùn)行隊(duì)列
set_curr_task:當(dāng)進(jìn)程改變調(diào)度類或者進(jìn)程組時被調(diào)用
task_tick:將會引起進(jìn)程切換,驅(qū)動運(yùn)行running強(qiáng)占。由time_tick調(diào)用
task_fork:進(jìn)程創(chuàng)建時調(diào)用,不同調(diào)度策略的進(jìn)程初始化不一樣
task_dead:進(jìn)程結(jié)束時調(diào)用
switched_from、switched_to:進(jìn)程改變調(diào)度器時使用
prio_changed:改變進(jìn)程優(yōu)先級
1.3、調(diào)度觸發(fā)
調(diào)度的觸發(fā)主要有兩種方式,一種是本地定時中斷觸發(fā)調(diào)用scheduler_tick函數(shù),然后使用當(dāng)前運(yùn)行進(jìn)程的調(diào)度類中的task_tick,另外一種則是主動調(diào)用schedule,不管是哪一種最終都會調(diào)用到__schedule函數(shù),該函數(shù)調(diào)用pick_netx_task,通過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說明大部分情況都是滿足該條件的)。如果運(yùn)行隊(duì)列不都在cfs中,則通過優(yōu)先級stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sched_class遍歷選出下一個需要運(yùn)行的進(jìn)程。然后進(jìn)程任務(wù)切換。
處于TASK_RUNNING狀態(tài)的進(jìn)程才會被進(jìn)程調(diào)度器選擇,其他狀態(tài)不會進(jìn)入調(diào)度器。系統(tǒng)發(fā)生調(diào)度的時機(jī)如下:
à調(diào)用cond_resched()時
à顯式調(diào)用schedule()時
à從中斷上下文返回時
當(dāng)內(nèi)核開啟搶占時,會多出幾個調(diào)度時機(jī)如下:
à在系統(tǒng)調(diào)用或者中斷上下文中調(diào)用preemt_enable()時(多次調(diào)用系統(tǒng)只會在最后一次調(diào)用時會調(diào)度)
à在中斷上下文中,從中斷處理函數(shù)返回到可搶占的上下文時
1.4、__schedule的實(shí)現(xiàn)
分析_schedule的實(shí)現(xiàn)有利于理解調(diào)度類的實(shí)體如果在
其中有幾個重要的與調(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 將前一個進(jìn)程調(diào)度以前放回調(diào)度器中
pick_next_taskà class->pick_next_task從調(diào)度器中選出下一個需要運(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,這個是CFS的調(diào)度類定義的對象。其中基本包含了CFS調(diào)度的所有實(shí)現(xiàn)。
CFS實(shí)現(xiàn)三個調(diào)度策略:
1> SCHED_NORMAL這個調(diào)度策略是被常規(guī)任務(wù)使用
2> SCHED_BATCH 這個策略不像常規(guī)的任務(wù)那樣頻繁的搶占,以犧牲交互性為代價下,因而允許任務(wù)運(yùn)行更長的時間以更好的利用緩存,這種策略適合批處理
3> SCHED_IDLE 這是nice值甚至比19還弱,但是為了避免陷入優(yōu)先級導(dǎo)致問題,這個問題將會死鎖這個調(diào)度器,因而這不是一個真正空閑定時調(diào)度器
CFS調(diào)度類:
n enqueue_task(…) 當(dāng)任務(wù)進(jìn)入runnable狀態(tài),這個回調(diào)將把這個任務(wù)的調(diào)度實(shí)體(entity)放入紅黑樹并且增加nr_running變量的值
n dequeue_task(…) 當(dāng)任務(wù)不再是runnable狀態(tài),這個回調(diào)將會把這個任務(wù)的調(diào)度實(shí)體從紅黑樹中取出,并且減少nr_running變量的值
n yield_task(…) 除非compat_yield sysctl是打開的,這個回調(diào)函數(shù)基本上就是一個dequeue后跟一個enqueue,這那種情況下,他將任務(wù)的調(diào)度實(shí)體放入紅黑樹的最右端
n check_preempt_curr(…) 這個回調(diào)函數(shù)是檢查一個任務(wù)進(jìn)入runnable狀態(tài)是否應(yīng)該搶占當(dāng)前運(yùn)行的任務(wù)
n pick_next_task(…) 這個回調(diào)函數(shù)選出下一個最合適運(yùn)行的任務(wù)
n set_curr_task(…) 當(dāng)任務(wù)改變他的調(diào)度類或者改變他的任務(wù)組,將調(diào)用該回調(diào)函數(shù)
n task_tick(…) 這個回調(diào)函數(shù)大多數(shù)是被time tick調(diào)用。他可能引起進(jìn)程切換。這就驅(qū)動了運(yùn)行時搶占
2.1、調(diào)度實(shí)體
其中幾個重要的變量
每一個進(jìn)程的task_struct中都嵌入了sched_entry對象,所以進(jìn)程是可調(diào)度的實(shí)體,但是可調(diào)度的實(shí)體不一定是進(jìn)程,也可能是進(jìn)程組。
2.2、CFS調(diào)度
Tcik 中斷,主要會更新調(diào)度信息,然后調(diào)整當(dāng)前進(jìn)程在紅黑樹中的位置。調(diào)整完成以后如果當(dāng)前進(jìn)程不再是最左邊的葉子,就標(biāo)記為Need_resched標(biāo)志,中斷返回時就會調(diào)用scheduler()完成切換、否則當(dāng)前進(jìn)程繼續(xù)占用CPU。從這里可以看出CFS拋棄了傳統(tǒng)時間片概念。Tick中斷只需要更新紅黑樹。
紅黑樹鍵值即為vruntime,該值通過調(diào)用update_curr函數(shù)進(jìn)行更新。這個值為64位的變量,會一直遞增,__enqueue_entity中會將vruntime作為鍵值將要入隊(duì)的實(shí)體插入到紅黑樹中。__pick_first_entity會將紅黑樹中最左側(cè)即vruntime最小的實(shí)體取出。
更多信息可以來這里獲取==>>電子技術(shù)應(yīng)用-AET<<