點(diǎn)擊左上方藍(lán)色“一口Linux”，選擇“設(shè)為星標(biāo)”
本文檔基于linux3.14 ，linux內(nèi)核調(diào)度詳解
定義位于
linux/include/uapi/linux/sched.h中
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6SCHED_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)行。如果沒有其他可運(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)度類。
定義調(diào)度類struct sched class
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*yield_task) (struct rq *rq);
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
struct task_struct * (*pick_next_task) (struct rq *rq);
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
void (*post_schedule) (struct rq *this_rq);
void (*task_waking) (struct task_struct *task);
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
void (*set_cpus_allowed)(struct task_struct *p,
const struct cpumask *newmask);
void (*rq_online)(struct rq *rq);
void (*rq_offline)(struct rq *rq);
#endif
void (*set_curr_task) (struct rq *rq);
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
void (*task_fork) (struct task_struct *p);
void (*task_dead) (struct task_struct *p);
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
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);
#ifdef CONFIG_FAIR_GROUP_SCHED
void (*task_move_group) (struct task_struct *p, int on_rq);
#endif
};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í)
調(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，通過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)先級(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í)
分析_schedule的實(shí)現(xiàn)有利于理解調(diào)度類的實(shí)體如果在
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
/*關(guān)閉搶占*/
preempt_disable();
/*獲取當(dāng)前CPU*/
cpu = smp_processor_id();
/*取得當(dāng)前cpu的運(yùn)行隊(duì)列rq*/
rq = cpu_rq(cpu);
/*更新全局狀態(tài)，標(biāo)識(shí)當(dāng)前CPU發(fā)生上下文切換*/
rcu_note_context_switch(cpu);
prev = rq->curr; /*當(dāng)前運(yùn)行的進(jìn)程存入Prev中*/
schedule_debug(prev);
if (sched_feat(HRTICK)) //取消為當(dāng)前進(jìn)程運(yùn)行的hrtimer
hrtick_clear(rq);
/*
* Make sure that signal_pending_state()->signal_pending() below
* can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
* done by the caller to avoid the race with signal_wake_up().
*/
smp_mb__before_spinlock(); //內(nèi)存屏障
raw_spin_lock_irq(&rq->lock); //上鎖該隊(duì)列
switch_count = &prev->nivcsw; //記錄當(dāng)前進(jìn)程切換次數(shù)
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { //當(dāng)前進(jìn)程非運(yùn)行狀態(tài)，并且非內(nèi)核搶占
if (unlikely(signal_pending_state(prev->state, prev))) { //當(dāng)前進(jìn)程有信號(hào)待處理，設(shè)置進(jìn)程為就緒態(tài)
prev->state = TASK_RUNNING; //設(shè)置為RUNNING
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP); //將其從隊(duì)列中刪除
prev->on_rq = 0; //將在運(yùn)行隊(duì)列中變量置為0
/*
* If a worker went to sleep, notify and ask workqueue
* whether it wants to wake up a task to maintain
* concurrency.
*/
if (prev->flags & PF_WQ_WORKER) { //判斷是否是工作隊(duì)列進(jìn)程
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev, cpu); //如果有工作隊(duì)列進(jìn)程喚醒則嘗試喚醒
if (to_wakeup)
try_to_wake_up_local(to_wakeup);
}
}
switch_count = &prev->nvcsw;
}
pre_schedule(rq, prev); //通知調(diào)度器，即將發(fā)生進(jìn)程切換
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
put_prev_task(rq, prev); //通知調(diào)度器，即將用另一個(gè)進(jìn)程替換當(dāng)前進(jìn)程
next = pick_next_task(rq); //挑選一個(gè)優(yōu)先級(jí)高的任務(wù)，使用調(diào)度類的方法
clear_tsk_need_resched(prev); //清空TIF_NEED_RESCHED標(biāo)志
clear_preempt_need_resched(); //清空PREEMPT_NEED_RESCHED標(biāo)志
rq->skip_clock_update = 0;
if (likely(prev != next)) { //如果如果選出的進(jìn)程和當(dāng)前進(jìn)程不是同一個(gè)進(jìn)程
rq->nr_switches++; //隊(duì)列切換次數(shù)更新
rq->curr = next; //將當(dāng)前進(jìn)程換成剛才挑選的進(jìn)程
++*switch_count; //進(jìn)程切換次數(shù)更新
context_switch(rq, prev, next); /* unlocks the rq */ /*進(jìn)程上下文切換 */
/*
* The context switch have flipped the stack from under us
* and restored the local variables which were saved when
* this task called schedule() in the past. prev == current
* is still correct, but it can be moved to another cpu/rq.
*/
/*上下文切換以后當(dāng)前運(yùn)行CPU也可能會(huì)改變，需要從新獲取當(dāng)前運(yùn)行進(jìn)程的運(yùn)行隊(duì)列*/
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock); //解鎖該隊(duì)列
post_schedule(rq); //通知調(diào)度器，完成了進(jìn)程切換
sched_preempt_enable_no_resched(); //開啟內(nèi)核搶占
if (need_resched()) //如果該進(jìn)程被其他進(jìn)程設(shè)置了TIF_NEED_RESCHED,則需要重新調(diào)度
goto need_resched;
}其中有幾個(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
該部分代碼位于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)致問題，這個(gè)問題將會(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í)搶占
/*
一個(gè)調(diào)度實(shí)體（紅黑樹的一個(gè)節(jié)點(diǎn)），其包含一組或一個(gè)指定的進(jìn)程，包含一個(gè)自己的運(yùn)行隊(duì)列，一個(gè)父親指針，一個(gè)指向需要調(diào)度的隊(duì)列
*/
struct sched_entity {
/*權(quán)重，在數(shù)組prio_to_weight[]包含優(yōu)先級(jí)轉(zhuǎn)權(quán)重的數(shù)值*/
struct load_weight load; /* for load-balancing */
/*實(shí)體在紅黑樹對(duì)應(yīng)的節(jié)點(diǎn)信息*/
struct rb_node run_node;
/*實(shí)體所在的進(jìn)程組*/
struct list_head group_node;
/*實(shí)體是否處于紅黑樹運(yùn)行隊(duì)列中*/
unsigned int on_rq;
/*開始運(yùn)行時(shí)間*/
u64 exec_start;
/*總運(yùn)行時(shí)間*/
u64 sum_exec_runtime;
/*
虛擬運(yùn)行時(shí)間，在時(shí)間中斷或者任務(wù)狀態(tài)發(fā)生改變時(shí)會(huì)更新
其會(huì)不停的增長(zhǎng)，增長(zhǎng)速度與load權(quán)重成反比，load越高，增長(zhǎng)速度越慢，就越可能處于紅黑樹最左邊被調(diào)度
每次時(shí)鐘中斷都會(huì)修改其值
具體見calc_delta_fair()函數(shù)
*/
u64 vruntime;
/*進(jìn)程在切換進(jìn)cpu時(shí)的sum_exec_runtime值*/
u64 prev_sum_exec_runtime;
/*此調(diào)度實(shí)體中進(jìn)程移到其他cpu組的數(shù)量*/
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
/*用于統(tǒng)計(jì)一些數(shù)據(jù)*/
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
父親調(diào)度實(shí)體指針，如果是進(jìn)程則指向其運(yùn)行隊(duì)列的調(diào)度實(shí)體，如果是進(jìn)程組則指向其上一個(gè)進(jìn)程組的調(diào)度實(shí)體
在set_task_rq函數(shù)中設(shè)置
*/
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
/*實(shí)體所處紅黑樹運(yùn)行隊(duì)列*/
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
/*實(shí)體的紅黑樹運(yùn)行隊(duì)列，如果為NULL表明其是一個(gè)進(jìn)程，若非NULL表明其是調(diào)度組*/
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
/* Per-entity load-tracking */
struct sched_avg avg;
#endif
};其中幾個(gè)重要的變量
字段 | 描述 |
load | 指定了權(quán)重, 決定了各個(gè)實(shí)體占隊(duì)列總負(fù)荷的比重, 計(jì)算負(fù)荷權(quán)重是調(diào)度器的一項(xiàng)重任, 因?yàn)镃FS所需的虛擬時(shí)鐘的速度最終依賴于負(fù)荷, 權(quán)重通過優(yōu)先級(jí)轉(zhuǎn)換而成，是vruntime計(jì)算的關(guān)鍵 |
Run_node | 調(diào)度實(shí)體在紅黑樹對(duì)應(yīng)的結(jié)點(diǎn)信息, 使得調(diào)度實(shí)體可以在紅黑樹上排序 |
Sum_exec_runtime | 記錄程序運(yùn)行所消耗的CPU時(shí)間, 以用于完全公平調(diào)度器CFS |
On_rq | 調(diào)度實(shí)體是否在就緒隊(duì)列上接受檢查, 表明是否處于CFS紅黑樹運(yùn)行隊(duì)列中，需要明確一個(gè)觀點(diǎn)就是，CFS運(yùn)行隊(duì)列里面包含有一個(gè)紅黑樹，但這個(gè)紅黑樹并不是CFS運(yùn)行隊(duì)列的全部，因?yàn)榧t黑樹僅僅是用于選擇出下一個(gè)調(diào)度程序的算法。很簡(jiǎn)單的一個(gè)例子，普通程序運(yùn)行時(shí)，其并不在紅黑樹中，但是還是處于CFS運(yùn)行隊(duì)列中，其on_rq為真。只有準(zhǔn)備退出、即將睡眠等待和轉(zhuǎn)為實(shí)時(shí)進(jìn)程的進(jìn)程其CFS運(yùn)行隊(duì)列的on_rq為假 |
vruntime | 虛擬運(yùn)行時(shí)間，調(diào)度的關(guān)鍵，其計(jì)算公式：一次調(diào)度間隔的虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 * (NICE_0_LOAD / 權(quán)重)?？梢钥闯龈鷮?shí)際運(yùn)行時(shí)間和權(quán)重有關(guān)，紅黑樹就是以此作為排序的標(biāo)準(zhǔn)，優(yōu)先級(jí)越高的進(jìn)程在運(yùn)行時(shí)其vruntime增長(zhǎng)的越慢，其可運(yùn)行時(shí)間相對(duì)就長(zhǎng)，而且也越有可能處于紅黑樹的最左結(jié)點(diǎn)，調(diào)度器每次都選擇最左邊的結(jié)點(diǎn)為下一個(gè)調(diào)度進(jìn)程。注意其值為單調(diào)遞增，在每個(gè)調(diào)度器的時(shí)鐘中斷時(shí)當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間都會(huì)累加。單純的說就是進(jìn)程們都在比誰(shuí)的vruntime最小，最小的將被調(diào)度 |
Cfs_rq | 此調(diào)度實(shí)體所處于的CFS運(yùn)行隊(duì)列 |
My_q | 如果此調(diào)度實(shí)體代表的是一個(gè)進(jìn)程組，那么此調(diào)度實(shí)體就包含有一個(gè)自己的CFS運(yùn)行隊(duì)列，其CFS運(yùn)行隊(duì)列中存放的是此進(jìn)程組中的進(jìn)程，這些進(jìn)程就不會(huì)在其他CFS運(yùn)行隊(duì)列的紅黑樹中被包含(包括頂層紅黑樹也不會(huì)包含他們，他們只屬于這個(gè)進(jìn)程組的紅黑樹) |
Sum_exec_runtime |
|
每一個(gè)進(jìn)程的task_struct中都嵌入了sched_entry對(duì)象，所以進(jìn)程是可調(diào)度的實(shí)體，但是可調(diào)度的實(shí)體不一定是進(jìn)程，也可能是進(jìn)程組。
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，該值通過調(diào)用update_curr函數(shù)進(jìn)行更新。這個(gè)值為64位的變量，會(huì)一直遞增，__enqueue_entity中會(huì)將vruntime作為鍵值將要入隊(duì)的實(shí)體插入到紅黑樹中。__pick_first_entity會(huì)將紅黑樹中最左側(cè)即vruntime最小的實(shí)體取出。
end
一口Linux?
關(guān)注，回復(fù)【1024】海量Linux資料贈(zèng)送
精彩文章合集
文章推薦
