linux 內核調度詳解
本文檔基於 linux3.14 ,linux 內核調度詳解
1、概述
1.1、調度策略
定義位於
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 6
SCHED_NORMAL:普通的分時進程,使用的 fair_sched_class 調度類
SCHED_FIFO:先進先出的實時進程。當調用程序把 CPU 分配給進程的時候,它把該進程描述符保留在運行隊列鏈表的當前位置。此調度策略的進程一旦使用 CPU 則一直運行。如果沒有其他可運行的更高優先級實時進程,進程就繼續使用 CPU,想用多久就用多久,即使還有其他具有相同優先級的實時進程處於可運行狀態。使用的是 rt_sched_class 調度類。
SCHED_RR:時間片輪轉的實時進程。當調度程序把 CPU 分配給進程的時候,它把該進程的描述符放在運行隊列鏈表的末尾。這種策略保證對所有具有相同優先級的 SCHED_RR 實時進程進行公平分配 CPU 時間,使用的 rt_sched_class 調度類
SCHED_BATCH:是 SCHED_NORMAL 的分化版本。採用分時策略,根據動態優先級,分配 CPU 資源。在有實時進程的時候,實時進程優先調度。但針對吞吐量優化,除了不能搶佔外與常規進程一樣,允許任務運行更長時間,更好使用高速緩存,適合於成批處理的工作,使用的 fair_shed_class 調度類
SCHED_IDLE:優先級最低,在系統空閒時運行,使用的是 idle_sched_class 調度類,給 0 號進程使用
SCHED_DEADLINE:新支持的實時進程調度策略,針對突發型計算,並且對延遲和完成時間敏感的任務使用,基於 EDF(earliest deadline first), 使用的是 dl_sched_class 調度類。
1.2、調度類
定義調度類 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: 指向下一個調度類, 用於在函數 pick_next_task、check_preempt_curr、set_rq_online、set_rq_offline 用於遍歷整個調度類根據調度類的優先級選擇調度類。優先級爲 stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sc*hed_class
enqueue_task: 將任務加入到調度類中
dequeue_task: 將任務從調度類中移除
yield_task/ yield_to_task: 主動放棄 CPU
check_preempt_curr: 檢查當前進程是否可被強佔
pick_next_task: 從調度類中選出下一個要運行的進程
put_prev_task: 將進程放回到調度類中
select_task_rq: 爲進程選擇一個合適的 cpu 的運行隊列
migrate_task_rq: 遷移到另外的 cpu 運行隊列
pre_schedule: 調度以前調用
post_schedule: 通知調度器完成切換
task_waking、task_woken: 用於進程喚醒
set_cpus_allowed: 修改進程 cpu 親和力 affinity
rq_online: 啓動運行隊列
rq_offline: 關閉運行隊列
set_curr_task: 當進程改變調度類或者進程組時被調用
task_tick: 將會引起進程切換,驅動運行 running 強佔。由 time_tick 調用
task_fork: 進程創建時調用,不同調度策略的進程初始化不一樣
task_dead: 進程結束時調用
switched_from、switched_to: 進程改變調度器時使用
prio_changed: 改變進程優先級
1.3、調度觸發
調度的觸發主要有兩種方式,一種是本地定時中斷觸發調用 scheduler_tick 函數,然後使用當前運行進程的調度類中的 task_tick,另外一種則是主動調用 schedule,不管是哪一種最終都會調用到__schedule 函數,該函數調用 pick_netx_task,通過 rq->nr_running ==rq->cfs.h_nr_running 判斷出如果當前運行隊列中的進程都在 cfs 調度器中,則直接調用 cfs 的調度類(內核代碼裏面這一判斷使用了 likely 說明大部分情況都是滿足該條件的)。如果運行隊列不都在 cfs 中,則通過優先級 stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sched_class 遍歷選出下一個需要運行的進程。然後進程任務切換。
處於 TASK_RUNNING 狀態的進程纔會被進程調度器選擇,其他狀態不會進入調度器。系統發生調度的時機如下:
à 調用 cond_resched() 時
à 顯式調用 schedule() 時
à 從中斷上下文返回時
當內核開啓搶佔時,會多出幾個調度時機如下:
à 在系統調用或者中斷上下文中調用 preemt_enable() 時(多次調用系統只會在最後一次調用時會調度)
à 在中斷上下文中,從中斷處理函數返回到可搶佔的上下文時
1.4、__schedule 的實現
分析_schedule 的實現有利於理解調度類的實體如果在
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
/*關閉搶佔*/
preempt_disable();
/*獲取當前CPU*/
cpu = smp_processor_id();
/*取得當前cpu的運行隊列rq*/
rq = cpu_rq(cpu);
/*更新全局狀態,標識當前CPU發生上下文切換*/
rcu_note_context_switch(cpu);
prev = rq->curr; /*當前運行的進程存入Prev中*/
schedule_debug(prev);
if (sched_feat(HRTICK)) //取消爲當前進程運行的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(); //內存屏障
raw_spin_lock_irq(&rq->lock); //上鎖該隊列
switch_count = &prev->nivcsw; //記錄當前進程切換次數
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { //當前進程非運行狀態,並且非內核搶佔
if (unlikely(signal_pending_state(prev->state, prev))) { //當前進程有信號待處理,設置進程爲就緒態
prev->state = TASK_RUNNING; //設置爲RUNNING
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP); //將其從隊列中刪除
prev->on_rq = 0; //將在運行隊列中變量置爲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) { //判斷是否是工作隊列進程
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev, cpu); //如果有工作隊列進程喚醒則嘗試喚醒
if (to_wakeup)
try_to_wake_up_local(to_wakeup);
}
}
switch_count = &prev->nvcsw;
}
pre_schedule(rq, prev); //通知調度器,即將發生進程切換
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
put_prev_task(rq, prev); //通知調度器,即將用另一個進程替換當前進程
next = pick_next_task(rq); //挑選一個優先級高的任務,使用調度類的方法
clear_tsk_need_resched(prev); //清空TIF_NEED_RESCHED標誌
clear_preempt_need_resched(); //清空PREEMPT_NEED_RESCHED標誌
rq->skip_clock_update = 0;
if (likely(prev != next)) { //如果如果選出的進程和當前進程不是同一個進程
rq->nr_switches++; //隊列切換次數更新
rq->curr = next; //將當前進程換成剛纔挑選的進程
++*switch_count; //進程切換次數更新
context_switch(rq, prev, next); /* unlocks the rq */ /*進程上下文切換 */
/*
* 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.
*/
/*上下文切換以後當前運行CPU也可能會改變,需要從新獲取當前運行進程的運行隊列*/
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock); //解鎖該隊列
post_schedule(rq); //通知調度器,完成了進程切換
sched_preempt_enable_no_resched(); //開啓內核搶佔
if (need_resched()) //如果該進程被其他進程設置了TIF_NEED_RESCHED,則需要重新調度
goto need_resched;
}
其中有幾個重要的與調度器密切相關的函數:
pre_scheduleà prev->sched_class->pre_schedule 在調度以前調用
put_prev_taskàprev->sched_class->put_prev_task 將前一個進程調度以前放回調度器中
pick_next_taskà class->pick_next_task 從調度器中選出下一個需要運行的進程
post_scheduleà rq->curr->sched_class->post_scheduleCFS 中爲 NULL
2、 CFS 調度
該部分代碼位於 linux/kernel/sched/fair.c 中
定義了 const struct
sched_classfair_sched_class,這個是 CFS 的調度類定義的對象。其中基本包含了 CFS 調度的所有實現。
CFS 實現三個調度策略:
1> SCHED_NORMAL 這個調度策略是被常規任務使用
2> SCHED_BATCH 這個策略不像常規的任務那樣頻繁的搶佔,以犧牲交互性爲代價下,因而允許任務運行更長的時間以更好的利用緩存,這種策略適合批處理
3> SCHED_IDLE 這是 nice 值甚至比 19 還弱,但是爲了避免陷入優先級導致問題,這個問題將會死鎖這個調度器,因而這不是一個真正空閒定時調度器
CFS 調度類:
n enqueue_task(…) 當任務進入 runnable 狀態,這個回調將把這個任務的調度實體(entity)放入紅黑樹並且增加 nr_running 變量的值
n dequeue_task(…) 當任務不再是 runnable 狀態,這個回調將會把這個任務的調度實體從紅黑樹中取出,並且減少 nr_running 變量的值
n yield_task(…) 除非 compat_yield sysctl 是打開的,這個回調函數基本上就是一個 dequeue 後跟一個 enqueue,這那種情況下,他將任務的調度實體放入紅黑樹的最右端
n check_preempt_curr(…) 這個回調函數是檢查一個任務進入 runnable 狀態是否應該搶佔當前運行的任務
n pick_next_task(…) 這個回調函數選出下一個最合適運行的任務
n set_curr_task(…) 當任務改變他的調度類或者改變他的任務組,將調用該回調函數
n task_tick(…) 這個回調函數大多數是被 time tick 調用。他可能引起進程切換。這就驅動了運行時搶佔
2.1、調度實體
/*
一個調度實體(紅黑樹的一個節點),其包含一組或一個指定的進程,包含一個自己的運行隊列,一個父親指針,一個指向需要調度的隊列
*/
struct sched_entity {
/*權重,在數組prio_to_weight[]包含優先級轉權重的數值*/
struct load_weight load; /* for load-balancing */
/*實體在紅黑樹對應的節點信息*/
struct rb_node run_node;
/*實體所在的進程組*/
struct list_head group_node;
/*實體是否處於紅黑樹運行隊列中*/
unsigned int on_rq;
/*開始運行時間*/
u64 exec_start;
/*總運行時間*/
u64 sum_exec_runtime;
/*
虛擬運行時間,在時間中斷或者任務狀態發生改變時會更新
其會不停的增長,增長速度與load權重成反比,load越高,增長速度越慢,就越可能處於紅黑樹最左邊被調度
每次時鐘中斷都會修改其值
具體見calc_delta_fair()函數
*/
u64 vruntime;
/*進程在切換進cpu時的sum_exec_runtime值*/
u64 prev_sum_exec_runtime;
/*此調度實體中進程移到其他cpu組的數量*/
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
/*用於統計一些數據*/
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
父親調度實體指針,如果是進程則指向其運行隊列的調度實體,如果是進程組則指向其上一個進程組的調度實體
在set_task_rq函數中設置
*/
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
/*實體所處紅黑樹運行隊列*/
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
/*實體的紅黑樹運行隊列,如果爲NULL表明其是一個進程,若非NULL表明其是調度組*/
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
/* Per-entity load-tracking */
struct sched_avg avg;
#endif
};
其中幾個重要的變量
每一個進程的 task_struct 中都嵌入了 sched_entry 對象,所以進程是可調度的實體,但是可調度的實體不一定是進程,也可能是進程組。
2.2、CFS 調度
Tcik 中斷,主要會更新調度信息,然後調整當前進程在紅黑樹中的位置。調整完成以後如果當前進程不再是最左邊的葉子,就標記爲 Need_resched 標誌,中斷返回時就會調用 scheduler() 完成切換、否則當前進程繼續佔用 CPU。從這裏可以看出 CFS 拋棄了傳統時間片概念。Tick 中斷只需要更新紅黑樹。
紅黑樹鍵值即爲 vruntime,該值通過調用 update_curr 函數進行更新。這個值爲 64 位的變量,會一直遞增,__enqueue_entity 中會將 vruntime 作爲鍵值將要入隊的實體插入到紅黑樹中。__pick_first_entity 會將紅黑樹中最左側即 vruntime 最小的實體取出。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/nsvLajVxLa9ZQJBTjW7G2Q