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
};

其中幾個重要的變量

5sCloJ

每一個進程的 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