深入解析Linux進程調(diào)度器-CPU負載
說明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
1. 概述
CPU負載（cpu load）指的是某個時間點進程對系統(tǒng)產(chǎn)生的壓力。來張圖來類比下（參考Understanding Linux CPU Load）
CPU的運行能力，就如大橋的通行能力，分別有滿負荷，非滿負荷，超負荷等狀態(tài)，這幾種狀態(tài)對應不同的cpu load值；
單CPU滿負荷運行時cpu_load為1，當多個CPU或多核時，相當于大橋有多個車道，滿負荷運行時cpu_load值為CPU數(shù)或多核數(shù)；
CPU負載的計算（以單CPU為例），假設(shè)一分鐘內(nèi)執(zhí)行10個任務(wù)代表滿負荷，當一分鐘給出30個任務(wù)時，CPU只能處理10個，剩余20個不能處理，cpu_load=3；
在實際系統(tǒng)中查看：
cat /proc/cpuinfo：查看CPU信息；cat /proc/loadavg：查看cpu最近1/5/15分鐘的平均負載：
計算CPU負載，可以讓調(diào)度器更好的進行負載均衡處理，以便提高系統(tǒng)的運行效率。此外，內(nèi)核中的其他子系統(tǒng)也可以參考這些CPU負載值來進行相應的調(diào)整，比如DVFS等。
目前內(nèi)核中，有以下幾種方式來跟蹤CPU負載：
全局CPU平均負載；
運行隊列CPU負載；
PELT（per entity load tracking）;
這也是本文需要探討的內(nèi)容，開始吧。
2. 全局CPU平均負載
2.1 基礎(chǔ)概念
先來明確兩個與CPU負載計算相關(guān)的概念：
active task（活動任務(wù)）：只有知道活動任務(wù)數(shù)量，才能計算CPU負載，而活動任務(wù)包括了TASK_RUNNING和TASK_UNINTERRUPTIBLE兩類任務(wù)。包含TASK_UNINTERRUPTIBLE任務(wù)的原因是，這類任務(wù)經(jīng)常是在等待I/O請求，將其包含在內(nèi)也合理；NO_HZ：我們都知道Linux內(nèi)核每隔固定時間發(fā)出timer interrupt，而HZ是用來定義1秒中的timer interrupts次數(shù)，HZ的倒數(shù)是tick，是系統(tǒng)的節(jié)拍器，每個tick會處理包括調(diào)度器、時間管理、定時器等事務(wù)。周期性的時鐘中斷帶來的問題是，不管CPU空閑或繁忙都會觸發(fā)，會帶來額外的系統(tǒng)損耗，因此引入了NO_HZ模式，可以在CPU空閑時將周期性時鐘關(guān)掉。在NO_HZ期間，活動任務(wù)數(shù)量的改變也需要考慮，而它的計算不如周期性時鐘模式下直觀。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?
2.2 流程
Linux內(nèi)核中定義了三個全局變量值avenrun[3]，用于存放最近1/5/15分鐘的平均CPU負載。
看一下計算流程：
計算活動任務(wù)數(shù)，這個包括兩部分：1）周期性調(diào)度中新增加的活動任務(wù)；2）在
NO_HZ期間增加的活動任務(wù)數(shù)；根據(jù)活動任務(wù)數(shù)值，再結(jié)合全局變量值
avenrun[]中的old value，來計算新的CPU負載值，并最終替換掉avenrun[]中的值；系統(tǒng)默認每隔5秒鐘會計算一次負載，如果由于
NO_HZ空閑而錯過了下一個CPU負載的計算周期，則需要再次進行更新。比如NO_HZ空閑20秒而無法更新CPU負載，前5秒負載已經(jīng)更新，需要計算剩余的3個計算周期的負載來繼續(xù)更新；
2.3 計算方法
Linux內(nèi)核中，采用11位精度的定點化計算，CPU負載1.0由整數(shù)2048表示，宏定義如下：
計算公式如下：
load值為舊的CPU負載值avenrun[]，整個計算完成后得到新的負載值，再更新avenrun[]；EXP_1/EXP_5/EXP_15，分別代表最近1/5/15分鐘的定點化值的指數(shù)因子；active值，根據(jù)讀取calc_load_tasks的值來判斷，大于0則乘以FIXED_1(2048)傳入；根據(jù)
active和load值的大小關(guān)系來決定是否需要加1，類似于四舍五入的機制；
關(guān)鍵代碼如下：
NO_HZ模式下活動任務(wù)數(shù)量更改的計算 由于NO_HZ空閑效應而更改的CPU活動任務(wù)數(shù)量，存放在全局變量calc_load_nohz[2]中，并且每5秒計算周期交替更換一次存儲位置(calc_load_read_idx/calc_load_write_idx)，其他程序可以去讀取最近5秒內(nèi)的活動任務(wù)變化的增量值。
計算示例 假設(shè)在某個CPU上，開始計算時
load=0.5，根據(jù)calc_load_tasks值獲取不同的active，中間進入NO_HZ模式空閑了20秒，整個計算的值如下圖：
3. 運行隊列CPU負載
Linux系統(tǒng)會計算每個tick的平均CPU負載，并將其存儲在運行隊列中
rq->cpu_load[5]，用于負載均衡；
下圖顯示了計算運行隊列的CPU負載的處理流程：
最終通過cpu_load_update來計算，邏輯如下：
其中傳入的
this_load值，為運行隊列現(xiàn)有的平均負載值。
上圖中的衰減因子，是在NO_HZ模式下去進行計算的。在沒有使用tick時，從預先計算的表中計算負載值。Linux內(nèi)核中定義了兩個全局變量：
衰減因子的計算主要是在delay_load_missed()函數(shù)中完成，該函數(shù)會返回load * 衰減因子的值，作為上圖中的old_load。計算方式如下：
4. PELT
PELT, Per-entity load tracking。在Linux引入PELT之前，CFS調(diào)度器在計算CPU負載時，通過跟蹤每個運行隊列上的負載來計算；在引入PELT之后，通過跟蹤每個調(diào)度實體的負載貢獻來計算。（其中，調(diào)度實體：指task或task_group）
4.1 PELT計算方法
總體的計算思路：將調(diào)度實體的可運行狀態(tài)時間（正在運行+等待CPU調(diào)度運行），按
1024us劃分成不同的周期，計算每個周期內(nèi)該調(diào)度實體對系統(tǒng)負載的貢獻，最后完成累加。其中，每個計算周期，隨著時間的推移，需要乘以衰減因子y進行一次衰減操作。
先來看一下每個調(diào)度實體的負載貢獻計算公式：
當前時間點的負載貢獻 = 當前時間點負載 + 上個周期負載貢獻 * 衰減因子；
假設(shè)一個調(diào)度實體被調(diào)度運行，運行時間段可以分成三個段
d1/d2/d3，這三個段是被1024us的計算周期分割而成，period_contrib是調(diào)度實體last_update_time時在計算周期間的貢獻值，；總體的貢獻值，也是根據(jù)
d1/d2/d3來分段計算，最終相加即可；y為衰減因子，每隔1024us就乘以y來衰減一次；
計算的調(diào)用流程如下圖：
函數(shù)主要是計算時間差，再分成d1/d2/d3來分段計算處理，最終更新相應的字段；
decay_load函數(shù)要計算val * y^n，內(nèi)核提供了一張表來避免浮點運算，值存儲在runnable_avg_yN_inv數(shù)組中；
Linux中使用struct sched_avg來記錄調(diào)度實體和CFS運行隊列的負載信息，因此struct sched_entity和struct cfs_rq結(jié)構(gòu)體中，都包含了struct sched_avg，字段介紹如下：
4.2 PELT計算調(diào)用
PELT計算的發(fā)生時機如下圖所示：
調(diào)度實體的相關(guān)操作，包括入列出列操作，都會進行負載貢獻的計算；
原文作者：LoyenWang
