Linux 進程管理完全解讀

原文鏈接:https://www.ebpf.top/post/linux_process_mgr/

本文是技術團隊內部分享的版本,目的是通過進程管理及調度器歷史對於 Linux 進程管理的演進過程起到一個總覽的作用,完整的 PDF 可以在這裏 下載。水平有限,本文內容僅供參考,有錯誤歡迎指正。

公衆號

基礎知識

進程類型

CPU 資源佔用類型

進程優先級

靜態優先級 (static_prio)

非實時進程靜態優先級可以通過 nice() 進行調整。範圍 (-20 - 19)

動態優先級 (prio) 保存進程的動態優先級,通常也是調度類使用的優先級,某些情況下在內核中會臨時調整該優先級,比如實時互斥量。

時間片 (time slice) 表示進程被調度進來和被調度出去所能持續的時間長度;

進程內核結構 進程在內核中數據結構 PCB(Process Control Block) 爲 task_struct 結構。

進程運行狀態

進程上下文切換 進程的上下文切換不僅包含了虛擬內存、棧、全局變量等用戶空間的資源,還包括了內核堆棧、寄存器等內核空間的資源。

參見 操作系統進程知識總結 [1]

Linux 調度器

調度器

調度器是整個系統的發動機,負責所有就緒進程的調度運行,設計良好的調度器需要從以下幾個方面進行考慮:

調度類型

  1. 主動放棄 CPU (由於需要等待或者主動進入 Sleep)

  2. 被動放棄 CPU (由於時間片消耗完或被更高優先級的任務搶佔 - 如支持搶佔)

Linux 調度器歷史

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 中)所有任務的重新設置默認時間片;如果等待隊列中的進程的時間片仍然有剩餘,則會折半計入到下一次的時間片中;

優點

實現邏輯簡單,在早期運行任務數量有限的情況下,運行良好。

缺點

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 上運行的時間,值越大被再次調度概率越低。將不同優先級的進程運行的時間作爲一個統一視圖來進程處理。

動態時間片

調度週期 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 隊列時:

而且在每一個調度週期內調度器會不斷檢查公平性是否得到了滿足,通過修訂 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 模型,存在大小核數的結構。

高階話題

搶佔

  1. 觸發搶佔:給正在 CPU 上運行的當前進程設置一個請求重新調度的標誌 (TIF_NEED_RESCHED),僅此而已,此時進程並沒有切換。

    觸發時機:

  1. 執行搶佔:在隨後的某個時刻,內核會檢查 TIF_NEED_RESCHED 標誌並調用 __schedule() 執行搶佔。

搶佔如果發生在進程處於用戶態的時候,稱爲 User Preemption(用戶態搶佔);如果發生在進程處於內核態的時候,則稱爲 Kernel Preemption(內核態搶佔)。

搶佔只在某些特定的時機發生,這是內核的代碼決定的。

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 的值。

負載均衡流程:

  1. 判斷當前 CPU 是否需要負載均衡

  2. 負載均衡以當前 CPU 開始,由下至上調度域,從最底層的調度域開始做負載均衡

  3. 在調度域中查找最繁忙的調度組,更新調度域和調度組的相信統計信息,計算出該調度域的不均衡負載值;

  4. 在最繁忙的調度組中找出最繁忙的 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