Linux 進程管理完全解讀
原文鏈接:https://www.ebpf.top/post/linux_process_mgr/
本文是技術團隊內部分享的版本,目的是通過進程管理及調度器歷史對於 Linux 進程管理的演進過程起到一個總覽的作用,完整的 PDF 可以在這裏 下載。水平有限,本文內容僅供參考,有錯誤歡迎指正。
公衆號
基礎知識
進程類型
-
實時進程
-
非實時進程
CPU 資源佔用類型
-
CPU 消耗性 (CPU-Bound)
-
I/O 消耗性 (IO-Bound)
-
交互進程(對響應時間有要求)
進程優先級
靜態優先級 (static_prio)
-
實時進程 0 - 99
-
非實時進程 100 - 139
非實時進程靜態優先級可以通過 nice() 進行調整。範圍 (-20 - 19)
動態優先級 (prio) 保存進程的動態優先級,通常也是調度類使用的優先級,某些情況下在內核中會臨時調整該優先級,比如實時互斥量。
時間片 (time slice) 表示進程被調度進來和被調度出去所能持續的時間長度;
進程內核結構 進程在內核中數據結構 PCB(Process Control Block) 爲 task_struct 結構。
進程運行狀態
進程上下文切換 進程的上下文切換不僅包含了虛擬內存、棧、全局變量等用戶空間的資源,還包括了內核堆棧、寄存器等內核空間的資源。
參見 操作系統進程知識總結 [1]
Linux 調度器
調度器
調度器是整個系統的發動機,負責所有就緒進程的調度運行,設計良好的調度器需要從以下幾個方面進行考慮:
-
吞吐量
-
響應時間
-
公平性
-
功耗 (移動設備)
調度類型
-
主動放棄 CPU (由於需要等待或者主動進入 Sleep)
-
被動放棄 CPU (由於時間片消耗完或被更高優先級的任務搶佔 - 如支持搶佔)
Linux 調度器歷史
-
O(n) 2.4 內核
-
O(1) 2.6 內核
-
CFS 2.6.23+ (當前默認調度器)
O(n) 調度算法
調度數據結構
時間片分配
在運行時動態計算優先級,保證實時進程的優先級高於非實時任務的動態優先級,實時進程動態優先級 (1000 + p->rt_priority); 在計算動態優先級的時候會綜合考慮該任務的剩餘時間片、歷史執行情況等因素。
任務 Nice 越低,剩餘時間片越多,動態優先級越高,越有機會獲得運行;
任務運行的最大時間由動態優先級轉變爲固定 tick 數目,tick 的時間值由系統動態配置的 HZ 時鐘精度確定。
調度運行
調度器遍歷整個就緒隊列中全部的 n 個任務,選取 動態優先級 最高的任務進行調度運行。
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p, this_cpu)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
goodness 函數中找出優先級最高的一個進程。
調度運行
tick 中斷:tick 中斷函數中檢查檢查時間片是否使用完,使用完畢則進行進程切換;否則將剩餘時間片的 1/2 追加到動態優先級。
當系統無可運行任務或所有任務執行完時間片後,調度器需要將系統中(不是 runqueue 中)所有任務的重新設置默認時間片;如果等待隊列中的進程的時間片仍然有剩餘,則會折半計入到下一次的時間片中;
優點
實現邏輯簡單,在早期運行任務數量有限的情況下,運行良好。
缺點
-
時間複雜度爲 O(n),當所有調度任務完成後,需要對全部任務重新初始化,耗時高;
-
實時進程可能不能及時調度;
-
全局只有一個運行隊列,會導致 CPU 存在空閒;
-
SMP 系統中擴展問題,訪問運行隊列需要加鎖,特別是進程數量大時;
-
進程在不同 CPU 上進行跳轉,cache 缺失,性能受到影響;
Linux 內核中不確定性的 N 可能會帶來較大的風險影響。
O(1) 調度器
數據結構
每個 CPU 一個優先級隊列的方式。同時對於隊列設置一個按照進程優先級的數組。
分爲 active 和 expired 兩個數組,分別表示當前正常運行的隊列和已經過期的隊列。
當 active 隊列任務全部完成運行後,將 expired 與 active 互換。
爲了快速判斷優先級數組的列表中是否存在任務,使用 bitmap 索引。
時間片分配
靜態優先級爲 [-20 … 0 … 19] 的普通進程,其缺省時間片爲 [800ms … 100ms … 5ms]。
同時結合進程的實際運行情況,比如在 runqueue 中的等待時間、睡眠時間等因素,實時調整動態優先級,以期望更好識別出交互進程。
runqueue 中的進程優先級爲動態優先級。
動態優先級映射爲時間片。
調度運行
schedule 函數的主要功能是從該 CPU 的 runqueue 找到一個最合適的進程調度執行。其基本的思路就是從 active 優先級隊列中依次查找,代碼如下:
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
當 active 優先級隊列中沒有需要運行的任務,則交換 active 與 expired。
不再需要像 O(n) 那樣對系統中全部任務重新初始化時間片。
在 tick 函數中斷中判斷任務時間片是否使用完,如果時間片使用完畢,正常情況下將任務從移動到 expired 隊列中,但是如果判斷爲交互進程,依照交互進程指數 TASK_INTERACTIVE ,可能還是會放入到 actvie 隊列中;
如果 expired 隊列中的任務等待時間過長,說明調度其嚴重不公,這時候即使判斷出來時間片耗盡的進程是交互進程,仍然會被放入 expired 隊列,儘快完成本次調度;
優點
O(1) 調度器開銷比較小,大多數場景下都有不錯的表現;
重點關注交互進程,在交互進程的響應時間方面得到了很好的改善;
缺點
-
交互式任務的判定算法過於複雜,參數硬編碼,代碼可維護性變差;
-
靜態時間片,任務增加調度延時上升;
CFS 調度器
調度策略
進程調度依賴於調度策略,Linux 把相同調度策略抽象成了調度類(schedule class)。CFS 只負責非實時進程的處理。
優先級按照從高到低的方式進行調度, STOP 最高, IDLE 最低。
進程權重
CFS 調度器中使用靜態優先級對應的權重概念來對應。權重的對應關係 (-20 - 19)。進程每降低一個 nice 值,將多獲得 10% CPU 的時間。
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
vruntime(virtual runtime)
表示該進程已經在 CPU 上運行的時間,值越大被再次調度概率越低。將不同優先級的進程運行的時間作爲一個統一視圖來進程處理。
-
vruntime
虛擬運行時間 -
delta_exec
真實運行時間 -
nice_0_weight
表示nice
爲 0 的進程權重 -
weight
表示進程權重 -
進程的 vruntime 增長速度取決於其優先級
-
優先級越低,則 vruntime 增長越快,因而被再次調用的可能性就越小
-
優先級越高,則 vruntime 增長越慢,因而被再次調用的可能性就越大
動態時間片
調度週期 sched_period,保證一個調度週期內,運行隊列中的所有任務都會被調度一次,最壞情況下,任務的調度延時爲一個調度週期;
默認調度週期 sched_latency 默認爲 6 ms;任務平均時間片最小值 sched_min_granularity 爲 0.75 ms
8 個以內可運行時間設定爲 6ms,否則爲 N * sched_min_granularity;
if sched_latency/nr_running < sched_min_granularity
sched_period = nr_running * sched_min_granularity
確定好 sched_period 以後,每個任務的動態時間片爲:
調度數據結構
每個 CPU 對應一個運行隊列 runqueue,該運行隊列中包含 dl_rq/rt_rq/cfs_rq 等多個調度隊列。CFS 只處理普通進程。
使用 vruntime 作爲紅黑樹的索引鍵,使用 sched_entity 作爲值。
最小值在最左側,可以 O(1) 進行遍歷,插入 O(logN)
調度運行
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
struct task_struct *p;
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq, prev, rf);
}
again:
for_each_class(class) {
p = class->pick_next_task(rq, prev, rf);
}
}
pick_next_task_fair
static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
struct cfs_rq *cfs_rq = &rq->cfs;
struct sched_entity *se;
struct task_struct *p;
put_prev_task(rq, prev);
do {
se = pick_next_entity(cfs_rq, NULL);
set_next_entity(cfs_rq, se);
cfs_rq = group_cfs_rq(se);
} while (cfs_rq);
p = task_of(se);
return p;
}
pick_next_entity 從紅黑樹上讀取調度實體
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq);
struct sched_entity *se;
se = left; /* ideally we run the leftmost entity */
// .. 搶佔/喚醒或者其他判斷
return se;
}
調度函數在各自 CPU 上執行,依次運行 dl_rq/rt_rq/cfs_rq 隊列。
運行 cfs_rq 隊列時:
-
每次調度程序都選擇紅黑樹最左側的節點運行 (其 virtual runtime 最小),將其從紅黑樹中刪除,並調整紅黑樹
-
每隔一段時間,就更新正在運行的進程的 vruntime,並將更新後的值與當前紅黑樹中最左側節點的 vruntime 相比較
-
如果小於最左側節點的 virtual runtime,則繼續執行當前進程
-
如果大於最左側節點的 virtual runtime,則搶佔式地運行最左側的節點,並將當前正在運行的進程重新放到紅黑樹中
而且在每一個調度週期內調度器會不斷檢查公平性是否得到了滿足,通過修訂 vruntme 的值來進行平衡,比如新加入的進程和被喚醒的進程會在 vruntme 上進行補償。
新進程加入及睡眠進程喚醒
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
u64 vruntime = cfs_rq->min_vruntime;
if (initial && sched_feat(START_DEBIT)) // 如果是初始化
vruntime += sched_vslice(cfs_rq, se); // 計算新進程的 vruntime 添加到 min_vruntime,防止過度佔用
if (!initial) {
unsigned long thresh = sysctl_sched_latency; // 一個調度週期延時
if (sched_feat(GENTLE_FAIR_SLEEPERS))
thresh >>= 1; // 折半處理,防止過度佔用
vruntime -= thresh; // 減掉 thresh,讓進程獲得儘快調度
}
/* ensure we never gain time by being placed backwards. */
se->vruntime = max_vruntime(se->vruntime, vruntime);
}
優點
基於優先級,兼顧運行公平性,默認調度器,經受住了時間的考驗;
缺點
在 Android 等嵌入式設備上,仍然需要調整和優化;
調度器綜合對比
未來調度器
ARM 體系存在 big.LITTLE 模型,存在大小核數的結構。
-
HMP 調度器
-
EAS 綠色節省調度器 (HMP 的優化版)
-
NUMA 調度器
高階話題
搶佔
-
觸發搶佔:給正在 CPU 上運行的當前進程設置一個請求重新調度的標誌 (TIF_NEED_RESCHED),僅此而已,此時進程並沒有切換。
觸發時機:
-
週期性的時鐘中斷:scheduler_tick() 時間片耗盡
-
進程喚醒:當進程被喚醒的時候,優先級高於 CPU 當前進程
-
新進程創建
-
進程修改 nice 值
-
負載均衡
- 執行搶佔:在隨後的某個時刻,內核會檢查 TIF_NEED_RESCHED 標誌並調用 __schedule() 執行搶佔。
搶佔如果發生在進程處於用戶態的時候,稱爲 User Preemption(用戶態搶佔);如果發生在進程處於內核態的時候,則稱爲 Kernel Preemption(內核態搶佔)。
-
從系統調用 (syscall) 返回用戶態時
-
中斷處理程序返回內核空間之前會檢查 TIF_NEED_RESCHED 標誌,如果置位則調用 preempt_schedule_irq() 執行搶佔。preempt_schedule_irq() 是對 schedule() 的包裝。
搶佔只在某些特定的時機發生,這是內核的代碼決定的。
CPU 負載計算方式 PLET
爲了讓調度器更加高效,需要針對每個調度隊列和每個調度實體的負載進行衡量。(Per Entity Load Tracking)
時間(物理時間,不是虛擬時間)被分成了 1024us 的序列,在每一個週期中,一個 Entity 對系統負載的貢獻可以根據該實體處於 Runnable 狀態(正在 CPU 上運行或者等待 CPU 調度運行)的時間進行計算。如果在該週期內,Runnable 的時間是 x,那麼對系統負載的貢獻就是(x/1024)。
負載需要考慮歷史週期的影響 y^32 = 0.5, y = 0.97857206
L = L0 + L1 * y + L2 * y^2 + L3 * y^3 + ... + Ln * y^n
當前對於負載的計算 上個週期的負載貢獻值乘以衰減係數,加上當前時間點的負載即可。
經過 32 個週期,負載降低爲 0.5 倍, 經過 2016 個週期,全部負載衰減爲 0
更新時機:就緒隊列添加任務、刪除任務和週期性更新
就緒隊列的 load_avg(包含睡眠進程的貢獻) 與 runnable_load_avg(只統計可運行任務的負載) 。
負載均衡 SMP 和 NUMA
負載均衡遷移基於 runnable_load_avg 的值。
負載均衡流程:
-
判斷當前 CPU 是否需要負載均衡
-
負載均衡以當前 CPU 開始,由下至上調度域,從最底層的調度域開始做負載均衡
-
在調度域中查找最繁忙的調度組,更新調度域和調度組的相信統計信息,計算出該調度域的不均衡負載值;
-
在最繁忙的調度組中找出最繁忙的 CPU,然後把繁忙的 CPU 中的任務遷移到當前的 CPU,遷移負載量爲不均衡負載值。
NUMA 類似,更是更加複雜,需要處理跨 NUMA 內存和進程遷移。
調度任務組
Q & A
後記:今天早晨看到一篇文章 👉吐血整理 | 肝翻 Linux 進程調度所有知識點 對於調度的講述也非常全面建議閱讀。
另外 蝸窩科技 [2] 站點的很多文章也值得閱讀。
關於離在線任務混部的進程管理可以參見:混部之殤 - 論雲原生資源隔離技術之 CPU 隔離 [3] 和 Linux 內核調度器源碼分析 - 初始化 [4]
腳註
[1]
操作系統進程知識總結: https://segmentfault.com/a/1190000024423352
[2]
蝸窩科技: http://www.wowotech.net/
[3]
混部之殤 - 論雲原生資源隔離技術之 CPU 隔離: https://cloud.tencent.com/developer/article/1821725
[4]
Linux 內核調度器源碼分析 - 初始化: https://cloud.tencent.com/developer/article/1823195
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/dDittQWoAEzSAJkU1-eWyg