《Linux6.5源碼分析:進程管理與調度系列文章》
本系列文章將對進程管理與調度進行知識梳理與源碼分析,重點放在linux源碼分析上,并結合eBPF程序對內核中進程調度機制進行數據實時拿取與分析。
在進行正式介紹之前,有必要對文章引用進行提前說明。本系列文章參考了大量的博客、文章以及書籍:
-
《深入理解Linux內核》
-
《Linux操作系統原理與應用》
-
《奔跑吧Linux內核》
-
《深入理解Linux進程與內存》
-
《基于龍芯的Linux內核探索解析》
-
進程調度 - 標簽 - LoyenWang - 博客園 (cnblogs.com)
-
專欄文章目錄 - 知乎 (zhihu.com)
-
Linux進程調度:探索內核核心機制
Linux進程調度與管理:(五)進程的調度之調度節拍
在之前的文章中,我們介紹了進程是如何被創建出來的(我稱之為進程肉體重塑)、進程是如何加載并啟動的(我稱之為進程靈魂注入)、進程的調度時機(進程何時加入就緒隊列、何時被調度上CPU),以及進程調度時執行進程切換的細節,具體詳細信息請參考以下文章:
- Linux 進程管理與調度:(零)預備知識
- Linux 進程管理與調度:(一)進程的創建與銷毀
- Linux 進程調度與管理:(二)進程的加載與啟動
- Linux 進程調度與管理:(三)進程的調度之調度時機
- Linux 進程調度與管理:(四)進程的調度之schedule進程切換
我們在本系列第三篇文章中介紹了進程調度時機,其中涉及到了進程何時加入就緒隊列,何時觸發調度,在介紹被動調度時講到了調度時機中的何時觸發調度,我們用一張圖回憶一下,上一篇文章涉及到的調度時機(也就是何時調用schedule函數),其中涉及到調度節拍,每當調度節拍被觸發,都會判斷是否需要觸發搶占。本篇文章將接著Linux 進程調度與管理:(三)進程的調度之調度時機對調度節拍展開講講。
1. 調度節拍/周期調度 scheduler_tick()
在Linux中有一套時鐘節拍機制,計算機系統隨著時鐘節拍需要周期性地做很多事著,例如刷新屏幕、數據落盤、進程調度等。Linux每隔固定周期會發出timer interrupt
(IRQ0),HZ用來定義每一秒有多少次timer interrupt
。
對于任務調度器來說,定時器驅動的調度節拍是一個很重要的調度時機。時鐘節拍最終會調用調度類的task_tick
,完成調度相關的工作,會在這里判斷是否需要調度下一個任務來搶占當前CPU核。也會觸發多核之間任務隊列的負載均衡。保證不讓忙的核忙死,閑的核閑死。調度節拍的核心入口是scheduler_tick
。
每隔固定的時間, 時鐘中斷會被觸發一次,此時內核會依靠周期性的時鐘中斷來處理CPU的控制權,具體是Linux調度器的scheduler_tick()
函數被調用;
當時鐘中斷被觸發后,會經過如下的調用流程,最終調用scheduler_tick()函數;
我們看一下schedule_tick函數的執行流程, 其實就是在獲取完所在cpu的就緒隊列之后,調用當前調度類中的ops, task_tick函數執行, 最終再進行負載均衡操作;
其實scheduler_tick()函數主要是調用當前調度類中的task_tick函數執行相關操作;
void scheduler_tick(void)
{int cpu = smp_processor_id();//當前CPU號struct rq *rq = cpu_rq(cpu);//當前核的運行隊列struct task_struct *curr = rq->curr;//該cpu上運行的進程struct rq_flags rf;unsigned long thermal_pressure;/*熱壓*/u64 resched_latency;if (housekeeping_cpu(cpu, HK_TYPE_TICK))arch_scale_freq_tick();// 如果是管理CPU,更新CPU頻率縮放sched_clock_tick(); // 更新調度時鐘/*1.更新運行隊列的時鐘及負載信息*/rq_lock(rq, &rf);update_rq_clock(rq);///*1.更新運行隊列的時鐘計數*/thermal_pressure = arch_scale_thermal_pressure(cpu_of(rq)); // 獲取CPU熱壓力update_thermal_load_avg(rq_clock_thermal(rq), rq, thermal_pressure);// 更新熱負載平均值/*2.判斷是否需要調度下一個任務* 不同調度類使用對應的task_tick函數實現* 用于檢查當前進程是否已經運行足夠長時間,是否需要被調度出去;*/curr->sched_class->task_tick(rq, curr, 0);if (sched_feat(LATENCY_WARN))resched_latency = cpu_resched_latency(rq);/*3.更新運行隊列的cpu_load數組*/calc_global_load_tick(rq);sched_core_tick(rq);task_tick_mm_cid(rq, curr);
esched_latency_warn(cpu, resched_latency);perf_event_task_tick();/*5. 工作隊列線程,更新其狀態*/if (curr->flags & PF_WQ_WORKER)wq_worker_tick(curr);#ifdef CONFIG_SMP/*6.觸發SMP負載均衡*/rq->idle_balance = idle_cpu(cpu);trigger_load_balance(rq);//觸發一個軟中斷,讓ksoftirq線程處理真正地負載均衡過程
#endif
}
- 時鐘中斷處理程序中,調用
schedule_tick()
函數; - 時鐘中斷是調度器的脈搏,內核依靠周期性的時鐘來處理器CPU的控制權;
- 時鐘中斷處理程序,檢査當前進程的執行時間是否超額,如果超額則設置重新調度標志
TIF NEED RESCHED
- 時鐘中斷處理函數返回時,被中斷的進程如果在用戶模式下運行,需要檢查是否有重新調度標志,設置了則調用schedule()調度 (也就是我們再第三篇文章Linux 進程調度與管理:(三)進程的調度之調度時機中介紹的調度執行時機)
- 如果系統開啟了SMP,則會觸發負載均衡
load_balance()
這里的核心函數是task_tick(rq, curr, 0)
, 是調用當前調度類中的task_tick函數實現,不同調度類對應不同的task_tick實現方法;
2. task_tick_fair()
這里以cfs這個調度類為例子,分析該調度類對應的task_tick函數—>task_tick_fair()
:
//更新當前任務 及其 相關調度實體的狀態信息;
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{struct cfs_rq *cfs_rq;struct sched_entity *se = &curr->se;//curr為當前cpu上運行的進程/*1.遍歷當前任務所有調度實體;* (牽扯到組調度機制,需分情況)* 1.1如果系統實現了組調度機制,則遍歷當前進程調度實體以及上一級調度實體;* 1.2如果未開啟組調度機制,則僅遍歷當前進程調度實體*/for_each_sched_entity(se) {cfs_rq = cfs_rq_of(se);/*1.3 更新調度實體的狀態,檢查是否需要調度*/entity_tick(cfs_rq, se, queued);}/*2.執行NUMA負載均衡,嘗試將任務遷移到與其所需內存靠近的節點,通過調用task_tick_numa實現*/if (static_branch_unlikely(&sched_numa_balancing))/*觸發時,執行NUMA負載均衡邏輯*/task_tick_numa(rq, curr);update_misfit_status(curr, rq);update_overutilized_status(task_rq(curr));/*3.執行核心調度相關操作邏輯*/task_tick_core(rq, curr);
}
此處先是遍歷當前進程的所有調度實體==(如果開啟了組調度機制,則遍歷當前進程調度實體和上一級調度實體;如果沒開啟組調度機制,則僅遍歷當前進程調度實體)==,并通過核心函數entity_tick函數更新調度實體的狀態,并檢查當前進程是否需要調度;
這里可以通過查看對for_each_sched_entity()
的定義,來理解到底遍歷了哪些調度實體:
-
對于開啟了組調度機制的,
for_each_sched_entity()
的定義是:#ifdef CONFIG_FAIR_GROUP_SCHED //會從當前調度實體開始,持續遍歷其上一級的調度實體,直到se==NULL #define for_each_sched_entity(se) \for (; se; se = se->parent)
會從當前調度實體開始,持續遍歷其上一級的調度實體,直到se==NULL;
-
對于未開啟組調度機制的,for_each_sched_entity()`的定義是:
#else /* !CONFIG_FAIR_GROUP_SCHED */ //僅遍歷當前調度實體,隨后se==NULL #define for_each_sched_entity(se) \for (; se; se = NULL)
僅遍歷當前進程的調度實體;
此處的重點就是entity_tick(cfs_rq, se, queued);
,該函數會更新遍歷到的調度實體的狀態,并檢查是否需要調度;接下來將圍繞entity_tick
做進一步分析。
2.1 entity_tick()更新時間信息,檢查搶占
該函數主要就做了兩件事:①更新調度實體的各種時間信息;②檢查是否需要調度(搶占當前任務)
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{/** 1.更新當前任務的各種時間信息;(當前進程的vruntime以及該就緒隊列的min_vruntime)*/update_curr(cfs_rq);/** 2.更新當前進程的負載以及就緒隊列的負載信息load_avg;*/update_load_avg(cfs_rq, curr, UPDATE_TG);/* 3.更新調度組的負載信息*/update_cfs_group(curr);#ifdef CONFIG_SCHED_HRTICK/*關于高精度定時器的相關處理邏輯*/
#endif/*4.check_preempt_tick檢查是否需要搶占當前任務*/if (cfs_rq->nr_running > 1)//如果當前隊列只有一個任務,則不執行,因為搶占邏輯不適用check_preempt_tick(cfs_rq, curr);//比較當前任務的vruntime和其他任務的vruntime來判斷要不要搶占
}
梳理一下entity_tick的核心函數:
- 【重點】通過update_curr()函數更新當前任務的各種時間信息,后面會詳細分析這個函數;
- 通過update_load_avg()以及update_cfs_group()函數來更新進程負載以及調度組負載信息,為負載均衡做準備;
- 【重點】通過check_preempt_tick()判斷是否需要搶占當前任務,這個是核心實現函數,后面會詳細分析這個函數;
2.1.1 更新時間信息update_curr()
該函數主要用于更新計算進程的各種時間信息,主要進行了兩步計算:
- curr->sum_exec_runtime += delta_exec;計算出當前就緒隊列上運行的進程本次運行的時間;
- 通過
calc_delta_fair(delta_exec, curr);
計算出運行的虛擬時間;
除了以上的兩個核心計算步驟,還針對cfs隊列以及cgroup組進行了信息更新;
static void update_curr(struct cfs_rq *cfs_rq)
{/*1.計算當前進程運行了多少時間*/delta_exec = now - curr->exec_start;//自上次調度以來的時間curr->exec_start = now;//記錄本次調度的時間/*2.更新任務的最大執行時間片*//*3.累加當前進程的總執行時間*/curr->sum_exec_runtime += delta_exec;//自進程創建以來累計運行時間schedstat_add(cfs_rq->exec_clock, delta_exec);//當前cfs隊列總執行時間,所有任務的運行時間/*4.更新當前任務的虛擬運行時間* calc_delta_fair來計算虛擬時間的增量* update_min_vruntime更新CFS隊列的最小虛擬時間*/curr->vruntime += calc_delta_fair(delta_exec, curr);update_min_vruntime(cfs_rq);/*5.更新相關統計信息*/if (entity_is_task(curr)) {struct task_struct *curtask = task_of(curr);/*一個可以獲取的當前進程運行時間,運行虛擬時間的tracepoint*/trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);/*統計cgroup的相關信息*/cgroup_account_cputime(curtask, delta_exec);account_group_exec_runtime(curtask, delta_exec);}/*更新CFS隊列的運行時間*/account_cfs_rq_runtime(cfs_rq, delta_exec);
}
值得注意的是,trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
為我們提供了一個tracepoint,用于獲取當前進程運行的時間以及虛擬時間;
接下來對于calc_delta_fair()
函數如何計算虛擬時間的,進行進一步分析:
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{/*1.計算真正的虛擬時間* 1.1 nice = 0 時,權重為1024,即虛擬時間等于真實時間,直接跳過計算返回delta;* 1.2 nice!= 0 時,通過__calc_delta計算虛擬時間,并返回虛擬時間;*/if (unlikely(se->load.weight != NICE_0_LOAD))delta = __calc_delta(delta, NICE_0_LOAD, &se->load);return delta;
}
其中__calc_delta()
函數主要通過如下算法計算虛擬時間:
vruntime = (時間運行時間 * ((NICE__LOAD*2^32)/weight))>>32
2.1.2 檢查搶占check_preempt_tick()
該函數主要用于判斷是否需要搶占;主要通過以下幾個步驟實現判斷:
- 1.實際運行時間大于理想運行時間,則需重新調度
- 通過
sched_slice
函數計算出當前任務預期運行時間,具體實現方式會在后面提到; - 實際運行時間大于預期運行時間則重新調度
resched_curr
;
- 通過
- 2.避免當前任務運行時間太短,如果當前進程運行時間太短,則繼續運行該任務,跳出搶占判斷;
- 將當前任務實際運行時間與
sysctl_sched_min_granularity
(任務調度的最小時間粒度)作對比;
- 將當前任務實際運行時間與
- 3.當前進程虛擬運行時間與就緒隊列中最優先任務的虛擬時間做比較,若大出一定范圍,則需重新調度;
- 前面1步是保證當前任務實際運行時間不要太多;2步是當前任務實際運行時間不要太少;將實際運行時間限定在一定范圍內;
- 前面的1,2步均是拿當前進程的實際運行時間進行對比,而這里是對虛擬運行時間進行評判;
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{unsigned long ideal_runtime, delta_exec;struct sched_entity *se;s64 delta;/**1.當前進程實際運行的時間比預期時間長*1.1 通過sched_slice計算當前任務理想時間片長度,賦值給ideal_runtime;*1.2 檢查進程運行時間 是否超出 預期運行時間*/ideal_runtime = min_t(u64, sched_slice(cfs_rq, curr), sysctl_sched_latency);delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;//當前進程本次實際運行時間if (delta_exec > ideal_runtime) {//實際運行時間超出預期,則重新調度resched_currresched_curr(rq_of(cfs_rq));/** 清除調度器中的“親密任務”(buddy)信息,* 避免當前任務因調度優先級偏好被再次選中。*/clear_buddies(cfs_rq, curr);return;}/** 2.避免當前進程運行時間太短;* sysctl_sched_min_granularity是任務調度的最小時間粒度* 如果實際運行時間小于最小時間粒度,說明其運行時間不足,* 不滿足重新調度的要求,直接退出搶占判斷*/if (delta_exec < sysctl_sched_min_granularity)return;/** 3. 當前進程運行的時間比預期時間大一定幅度,則需搶占;* 3.1 先計算出 當前任務虛擬時間 與 cfs隊列中最優先任務(即紅黑樹左下角的任務)虛擬時間 之間的差;* 3.2 若 當前任務虛擬時間 < 最優先任務虛擬時間,則說明公平性未得到破壞,繼續運行當前任務;* 3.3 若 當前任務虛擬時間 > 最優先任務虛擬時間,但超出的時間在一定范圍內* (超出時間小于一個調度周期ideal_runtime),繼續運行當前任務;* 3.4 若 超出時間太多(即超出時間大于一個調度周期ideal_runtime),需要重新調度;*/se = __pick_first_entity(cfs_rq);//獲取cfs調度隊列中虛擬時間最小的任務delta = curr->vruntime - se->vruntime;//計算當前任務與最優先任務之間的虛擬運行時間差。if (delta < 0)//無需搶占,因為當前任務的虛擬時間比cfs隊列中最優先任務的虛擬時間還小return;//超出的時間 都大于 預期運行時間,則重新調度;if (delta > ideal_runtime)resched_curr(rq_of(cfs_rq));
}
不難看出,這里的核心函數是sched_slice()
與resched_curr()
,下面將詳細分析這兩個函數。
sched_slice():該函數根據當前系統的負載計算出一個調度周期,也即前面提到的預期運行時間,作為一個評判標準,以免當前任務運行時間過長;
首先是shced_slice()函數:調用__sched_period()
函數計算單個調度周期;再循環遍歷任務中的所有調度實體,計算slice預期運行時間;
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{/*1.計算出一個調度周期__sched_period()*/slice = __sched_period(nr_running + !se->on_rq);/*2.遍歷任務的所有調度實體,計算時間片*/for_each_sched_entity(se) {struct load_weight *load;struct load_weight lw;struct cfs_rq *qcfs_rq;/*獲取當前cfs隊列的總負載*/qcfs_rq = cfs_rq_of(se);load = &qcfs_rq->load;if (unlikely(!se->on_rq)) {lw = qcfs_rq->load;update_load_add(&lw, se->load.weight);load = &lw;}/*根據當前調度實體的權重,計算其分配到的時間片長度*/slice = __calc_delta(slice, se->load.weight, load);/* 當前調度實體權重 隊列總負載*/}return slice;
}
關于__sched_period()函數
是如何實現的,他通過將就緒隊列中的任務數與一個固定值sched_nr_latency作對比,來使用不同的策略,如果就緒隊列中的任務少于sched_nr_latency,則直接使用系統默認的sysctl_sched_latency作為一個調度周期,如果就緒隊列中的任務多于sched_nr_latency,則將nr_running * sysctl_sched_min_granularity
作為一個調度周期,其中sysctl_sched_min_granularity是最小時間片,也即就緒隊列中所有任務都運行最小時間片后作為一個調度周期。
/** This value is kept at sysctl_sched_latency/sysctl_sched_min_granularity*/
static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_min_granularity= 750000ULL;
unsigned int sysctl_sched_latency= 6000000ULL;static u64 __sched_period(unsigned long nr_running)
{ /*1.就緒隊列中進程較多,每個任務運行最小時間粒度*/if (unlikely(nr_running > sched_nr_latency))return nr_running * sysctl_sched_min_granularity;else/*2. 就緒隊列中進程較少,sysctl_sched_latency作為默認調度周期*/return sysctl_sched_latency;
}
**resched_curr()😗*該函數執行重新調度相關工作;
void resched_curr(struct rq *rq)
{struct task_struct *curr = rq->curr;//就緒隊列當前進程int cpu;lockdep_assert_rq_held(rq);//確保運行隊列被鎖定;/*1.檢查當前任務是否已經被標記為需要重新調度,防止重復標記*/if (test_tsk_need_resched(curr))return;/*2.重新調度相關工作:* 2.1運行隊列所屬cpu是當前cpu,即處理本地cpu情況:* set_tsk_need_resched(curr)更改 task_struct下面thread_info->flag為TIF_NEED_RESCHED;* set_preempt_need_resched()設置內核的搶占標志位,允許調度器在下一次中斷時觸發任務切換*/cpu = cpu_of(rq);if (cpu == smp_processor_id()) {set_tsk_need_resched(curr);set_preempt_need_resched();return;}/*2.重新調度相關工作:* 2.2處理遠程CPU情況:* set_nr_and_not_polling(curr)標記當前任務為TASK_RUNNING并判斷目標CPU是否是空閑輪詢狀態* smp_send_reschedule(cpu)發送信號,通知目標 CPU 觸發調度操作。*/if (set_nr_and_not_polling(curr))smp_send_reschedule(cpu);elsetrace_sched_wake_idle_without_ipi(cpu);
}
resched_curr()重新調度相關工作主要分以下兩個情況:
- 本地CPU:即目標運行隊列所屬CPU就是當前CPU
- 這種情況更改當前任務的thread_info標識符中的TIF_NEED_RESCHED;
- set_preempt_need_resched()設置內核的搶占標志位;
- 遠程CPU:即目標任務所屬cpu不是當前cpu;
- smp_send_reschedule(cpu)發送信號,通知目標 CPU 觸發調度操作;