Linux 核心設計: Load average

導讀

Load average 是業界經常用來評估負載的指標，例如在雲端的場景可以根據 load average 和其他指標來進行 cloud auto scaling container，自動的調整資源數量。在 Linux 系統中，我們可以透過以下幾個方式來取得相關的資訊:

$ uptime
18:40:03 up  8:37,  1 user,  load average: 0.42 0.70 1.13
    
$ top
top - 18:40:03 up  8:37,  1 user,  load average: 0.42 0.70 1.13
    
$ cat /proc/loadavg 
0.42 0.70 1.13 2/1224 67252

其中我們要關注的是 0.42 0.70 1.13 這三組數字，分別代表最近 1 分鐘，最近 5 分鐘，及最近 15 分鐘的 load average。而根據 wikipedia 對 load average 的解釋，該指標表示在一個時間週期中系統需要處理的工作量：

The load average represents the average system load over a period of time.

這個描述有點抽象。而如果我們在網路上搜尋，大多數會利用舉例的方式這麼解釋這些數字:

Reference to Load Average 負載解讀: 如果是 1 表示有一個 process 正在執行或等待 CPU 運算；5 表示有 5 個 process 正在執行或等待 CPU 運算

通過這個解釋，看似我們可以很好理解這些數字所代表的意涵了。不過這一解釋和 load average 所估算的指標其實有些許出入，實際的實現牽涉到更多細節。

比方說，Linux 中每個任務在某一時刻可以區分為 running / interruptible / uninterruptible 等狀態，參考 linux/sched.h:

/* Used in tsk->state: */
#define TASK_RUNNING			0x0000
#define TASK_INTERRUPTIBLE		0x0001
#define TASK_UNINTERRUPTIBLE		0x0002
#define __TASK_STOPPED			0x0004
#define __TASK_TRACED			0x0008

而你可知道 load balance 的計算實際上不僅包含 running，實際上還會包含進入睡眠的 uninterruptible 類型的任務嗎?

又或者，load balance 數值中所謂的 "平均" 到底是如何計算的呢? 是直接取樣每個時間點的任務數量加總取平均?或者需要對不同時間點的取樣加權處理?選用該種方法的考量為何? 此外，在沒辦法輕易支援浮點數運算的 kernel code 中，該怎麼計算出相關的數值? 本文將嘗試探討這些相對容易被忽略的細節，並直接閱讀核心的原始程式碼，以更精準的對 load average 有更具體的認識。

深入探討 Load average

• Linux Load Averages: Solving the Mystery
• Linux Load Averages: Solving the Mystery 譯文

神秘的三個數字

前面我們簡單的提到，透過 loadavg 相關命令所得到的三個數字分別代表最近 1 分鐘，最近 5 分鐘，及最近 15 分鐘的 load average。而更仔細的說，其計算的內容其實是以 5 秒為週期計算的 exponentially moving sums。由於是 exponentially moving sums，這個數字實際上不僅僅包含最近的 1 / 5 /15 分鐘時間段內的統計數據，1 / 5 / 15 分鐘所代表意義的只是對距今時間長短的任務數量抽樣結果權重。整個計算公式的計算如下所示:

$$\begin{gathered} load(t_k)=load(t_k-1)\alpha +n\ast (1-\alpha ) \\ \alpha =1-e^{-\text{count interval}/\text{60R}} \end{gathered}$$

R 代表的使用 t min load average 的 t 之秒數。loadavg.c 的註解中也有對應的描述:

 *   avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)

註解所說明的

avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)

看起來應該要修改成?

avenrun[n] = avenrun[n - 1] * exp_n + nr_active * (1 - exp_n)

或者應該修改成

avenrun[t] = avenrun[t - 1] * exp_n + nr_active * (1 - exp_n)

舉例來說，假設系統初始為 idle 狀態，接著運行持續給予一個 thread 的負載量，則 60 秒後後，對於 exponentially moving sums，其結果應該是 0.63 左右，以下是用 python 簡單測試的範例:

import numpy as np

count_interval = 5 # 5 sec per update for loadavg
sampling = 1 # 1 min load average
n = 1 # 1 task after t0
alpha = np.exp(-count_interval / (60 * sampling))

t_old = 0 # assume idle at t0

for i in range(1, int((sampling * 60)/ count_interval)+1):
    t_new = t_old * alpha + n * (1 - alpha)
    t_old = t_new
    print("t%d = %f" % (i, t_new))

每 5 秒計算一次，則第 60 秒是第 60 / 5 = 12 次的計算結果，對應輸出如下:

t1 = 0.079956
t2 = 0.153518
t3 = 0.221199
t4 = 0.283469
t5 = 0.340759
t6 = 0.393469
t7 = 0.441965
t8 = 0.486583
t9 = 0.527633
t10 = 0.565402
t11 = 0.600150
t12 = 0.632121

對於公式由來更詳細的介紹可以參考:

• UNIX Load Average Part 1: How It Works
• UNIX Load Average Part 2: Not Your Average Average

因為以前數學沒學好有一些不太肯定的內容QQ，待釐清或者尋求協助:

1. 這裡公式的 damping factor 和 exponentially moving sums 描述似乎有所不同，不確定兩者是不是在講相同的統計方法
2. 上面的 python 計算結果 0.63 和 Linux Load Averages: Solving the Mystery 所說的 0.62 有一點差異，我不是很確定這是某些，還是我的理解和作者所敘述的其實是不同的QQ

• 為什麼選擇 exponential moving sums?

• Why is Linux load average reported as the exponential moving average?
• Exponential smoothing

Uninterruptible task

當 load averages 最初出現在 Linux 中時，該指標僅僅用來反映對 CPU 的直接需求，也就是只考慮所謂的 runnable task。但隨著核心的演進而納入 TASK_UNINTERRUPTIBLE 類型的任務。在 Linux 中，屬於 TASK_UNINTERRUPTIBLE 類型的任務在進入睡眠狀態後，不會被 signal 中斷。我們可以在 sched/loadavg.c 找到對應的敘述:

/*
 * Global load-average calculations
 *
 * We take a distributed and async approach to calculating the global load-avg
 * in order to minimize overhead.
 *
 * The global load average is an exponentially decaying average of nr_running +
 * nr_uninterruptible.
 *
 * Once every LOAD_FREQ:
 *
 *   nr_active = 0;
 *   for_each_possible_cpu(cpu)
 *	nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
 * 
 * ......

關聯的程式碼是 calc_load_fold_active(我們會在後面章節深入相關程式碼):

long calc_load_fold_active(struct rq *this_rq, long adjust)
{
	long nr_active, delta = 0;

	nr_active = this_rq->nr_running - adjust;
	nr_active += (int)this_rq->nr_uninterruptible;

	if (nr_active != this_rq->calc_load_active) {
		delta = nr_active - this_rq->calc_load_active;
		this_rq->calc_load_active = nr_active;
	}

	return delta;
}

load average 包含 TASK_UNINTERRUPTIBLE，意味著該數值可能因為 disk I/O 而增加，而不僅僅是對 CPU 的需求，這與一般人直觀的認識可能有所差異。(註:根據 Brendan Gregg 文中所說，這種設計並非是普遍作法，許多其他作業系統並不會納入相似類型的任務進行統計)。

對於這個不是很直觀的設計，是否可以在 Linux 相關的文件找到對應的解釋呢?Brendan Gregg 尋尋覓覓，終於找到了下列的描述:(註: 從原本的敘述可以感覺到追本溯源的艱辛XD)

From: Matthias Urlichs <[e-mail]>
Subject: Load average broken ?
Date: Fri, 29 Oct 1993 11:37:23 +0200


The kernel only counts "runnable" processes when computing the load average.
I don't like that; the problem is that processes which are swapping or
waiting on "fast", i.e. noninterruptible, I/O, also consume resources.

It seems somewhat nonintuitive that the load average goes down when you
replace your fast swap disk with a slow swap disk...

Anyway, the following patch seems to make the load average much more
consistent WRT the subjective speed of the system. And, most important, the
load is still zero when nobody is doing anything. ;-)

--- kernel/sched.c.orig Fri Oct 29 10:31:11 1993
+++ kernel/sched.c  Fri Oct 29 10:32:51 1993
@@ -414,7 +414,9 @@
    unsigned long nr = 0;

    for(p = &LAST_TASK; p > &FIRST_TASK; --p)
-       if (*p && (*p)->state == TASK_RUNNING)
+       if (*p && ((*p)->state == TASK_RUNNING) ||
+                  (*p)->state == TASK_UNINTERRUPTIBLE) ||
+                  (*p)->state == TASK_SWAPPING))
            nr += FIXED_1;
    return nr;
 }
--
Matthias Urlichs        \ XLink-POP N|rnberg   | EMail: [e-mail]
Schleiermacherstra_e 12  \  Unix+Linux+Mac     | Phone: ...please use email.
90491 N|rnberg (Germany)  \   Consulting+Networking+Programming+etc'ing      42

由此，我們可以知道 Linux 的 load average 修改反映了系統資源的需求量，而不僅僅是 CPU。換句話說 Linux 從的統計並不是 cpu load average 而應該說成 system load average。

提交記錄中也提到了最初導致如此改動的場景: 對於一個速度較慢 swap disk 案例，理論上該導致對系統資源的需求增加，但該類型的任務會因此被歸類為 TASK_UNINTERRUPTIBLE，這導致 load average 數字下降，無法反映這類型的資源負載。而 Matthias 認為這樣不符合直觀判斷，所以將其進行了修正。

是否應該計算所有的 Uninterruptible task?

然而，Linux 的 load average 有時變得非常高，並非完全與 disk I/O 有高度相關。根據 Brendan Gregg 所述，在 linux 0.99.14 版本中，僅存在 13 行程式碼會直接進入 TASK_UNINTERRUPTIBLE 或 TASK_SWAPPING(後者後來被刪除)。而直到 Linux 4.12 版本，已經有超過 400 行程式碼路徑會進入TASK_UNINTERRUPTIBLE。意即，如今 TASK_UNITERRUPTIBLE 的含義可能隱含的事件比起從前有許多不同，而 load average 是否應只考慮 CPU 或者 disk 資源的需求？是否某些 TASK_UNITERRUPTIBLE 不應該被納入計算? Brendan Gregg 在原文中透過實驗敘述了他的看法，有興趣者可以自行參閱。

總結來說 Brendan Gregg 對 load average 的真實意義歸納為:

• 在 Linux 中，load average 展示的是以系統資源的角度，因此將包含正在工作以及等待工作（無論是 CPU / disk / uninterruptible lock）的任務
• 在其他作業系統裡，load average 通常僅指 CPU 資源的負載

到底哪一個是更好的指標呢? 大概不同的使用者對"資源"的涵蓋範圍會有不同的期待，不太能評價兩者好壞。也或者有一天我們會在 Linux 中增加不同類型的 load averages，並讓用戶選擇他們想要使用的：比方 CPU / disk / network，或者其他。

更多的細節可以參考上面所引用的 Brendan Gregg 之文章: Linux Load Averages: Solving the Mystery

Linux 核心中的原始程式碼

base 5.16.2

/proc/loadavg

首先，我們最初提到了獲取 load avg 的方法可以透過 cat /proc/loadavg。因此讓我們從 loadavg 這個 proc filesystem 開始。在 fs/proc/loadavg.c 裡，我們可以看到以下的內容，只有少少數行，而關鍵的函式顯而易見:

static int loadavg_proc_show(struct seq_file *m, void *v)
{
	unsigned long avnrun[3];

	get_avenrun(avnrun, FIXED_1/200, 0);

	seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %u/%d %d\n",
		LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
		LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
		LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
		nr_running(), nr_threads,
		idr_get_cursor(&task_active_pid_ns(current)->idr) - 1);
	return 0;
}

get_avenrun 獲取了 1 / 5 / 15 分鐘的 load avg 結果，而 cat /proc/loadavg 會顯示的結果包含以下，參見 man 5 proc:

• 前三個數字是 1 / 5 / 15 分鐘時間下的 load average
• nr_running: 處於 running 的任務數量
• nr_threads: kernel 可以排程的任務總數量(不包含結束)

根據 nr_running 的實作，這個數字只反映了 running state 的任務，但根據 calc_load_fold_active，在計算 load average 時會同時考慮 running 和 uninterruptible?

換句話說，也許我們有機會碰上 nr_running() 看起來僅占 nr_threads 的少部份，但是 load average 卻很高的情境?

• 最後一項是最近一次建立的 process 之 PID

這裡 load average 實際列印的內容值得我們關注，我們可以看到小數點和整數部份的是分開的(%lu.%02lu)，這是因為數字的表示實際上使用定點數的方式來儲存浮點數。可以參考 linux/sched/loadavg.h 的定義，從 LOAD_INT 的方式，我們得知除了 LSB 11 bits 以外的部份被用來要表示的浮點數;並從 LOAD_FRAC 的方式，以及 get_avenrun 對應的行為是將系統記錄的 global avenrun 加上 0.005，可知道小數點後位數是透過 LSB 11 位並四捨五入到 2 位的精準度(對應 format 時的 %02lu)。

void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
{
	loads[0] = (avenrun[0] + offset) << shift;
	loads[1] = (avenrun[1] + offset) << shift;
	loads[2] = (avenrun[2] + offset) << shift;
}

#define FSHIFT	11 /* nr of bits of precision */
#define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */
#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)

calc_load_tasks 的更新

首先，我們需要先認識關鍵的變數: atomic_long_t 類型的全域 calc_load_tasks。從 calc_global_load 與 calc_global_nohz 的使用方式來看，該變數應該是代表更新時刻的 running + uninterruptible 任務數量的總和。

calc_load_tasks 更新的主要路徑與 calc_global_load_tick 有所關聯，而 calc_global_load_tick 函式會在 scheduler_tick 中被呼叫。由於 Linux 的時鐘系統存在不同的類型，許多路徑都會經過 scheduler_tick。

簡單來說，Linux 的時鐘事件可以分為 periodic mode 和 tickless mode(同等的說法有 NO_HZ / dynamic tick)。後者相較於前者可以避免在 idle 狀態時仍然產生週期性的 timer interrupt，以降低功耗。而 tickless mode 根據時鐘精度又存在高低精度之分。

由於對 Linux 的 time subsystem 尚不熟悉，這裡先保留細節的深究，留待筆者有空時也許可以針對 timer 主題另外研究。這裡附上一些可參考的專欄:

• 蜗窝科技: Linux时间子系统之
• DroidPhone: Linux时间管理系统

若有比較清楚者也可以幫忙補充

註: 本文關於時間系統的討論不考慮 legacy_timer_tick 路徑

• periodic mode: event_handler -> tick_handle_periodic -> tick_periodic -> update_process_times -> scheduler_tick
• 低精度 NO_HZ: ?? -> tick_nohz_handler -> tick_sched_handle -> update_process_times -> scheduler_tick
• 高精度 NO_HZ: sched_timer.function -> tick_sched_timer -> tick_sched_handle -> update_process_times -> scheduler_tick

不管是哪種模式，總體來說，就是在 scheduler 被 tick 觸發時要順便更新 calc_load_tasks:

void calc_global_load_tick(struct rq *this_rq)
{
	long delta;

	if (time_before(jiffies, this_rq->calc_load_update))
		return;

	delta  = calc_load_fold_active(this_rq, 0);
	if (delta)
		atomic_long_add(delta, &calc_load_tasks);

	this_rq->calc_load_update += LOAD_FREQ;
}

每個 cpu 的 run queue 會維護一個獨立的 calc_load_update，當經過至少 5 sec(對應 LOAD_FREQ)，則呼叫 calc_load_fold_active，後者對每個 cpu 計算出與上個時間點的 active (running + uninterruptible)任務差異，更新到 calc_load_tasks。

long calc_load_fold_active(struct rq *this_rq, long adjust)
{
	long nr_active, delta = 0;

	nr_active = this_rq->nr_running - adjust;
	nr_active += (int)this_rq->nr_uninterruptible;

	if (nr_active != this_rq->calc_load_active) {
		delta = nr_active - this_rq->calc_load_active;
		this_rq->calc_load_active = nr_active;
	}

	return delta;
}

我們可以注意到，calc_load_tasks 的計算是考慮當前的 running + uninterruptible 減掉前一次的(this_rq->calc_load_active)，再把相差的結果加回 calc_load_tasks，這裡的計算看起來有點彆扭，留意到註解的說明:

/*    for_each_possible_cpu() is prohibitively expensive on machines with
 *    serious number of CPUs, therefore we need to take a distributed approach
 *    to calculating nr_active.
 *
 *        \Sum_i x_i(t) = \Sum_i x_i(t) - x_i(t_0) | x_i(t_0) := 0
 *                      = \Sum_i { \Sum_j=1 x_i(t_j) - x_i(t_j-1) }
 *
 *    So assuming nr_active := 0 when we start out -- true per definition, we
 *    can simply take per-CPU deltas and fold those into a global accumulate
 *    to obtain the same result. See calc_load_fold_active().
 *
 * ...

首先我們要注意的是，如果我們要在更新 load avg 的當下才去蒐集每個 cpu 的 nr_active(running + uninterruptible)，這在 CPU 數多的機器上會造成比較大的開銷。因此需要採取分散式的手段，讓每個 cpu 可以不必在同一時刻去更新 nr_active。

為了讓所有 cpu 可以正確的把數值更新到一個變數上(也就是 calc_load_tasks)，可以直接把兩時刻的 cpu 差值計算出來，再加到 calc_load_tasks 即可(即註解中使用的單字 fold)。

這個結果會等同於直接整合起來的 nr_active。可見下方式子，對於

$t_n$ 時刻、擁有 k 個 cpu(cpu_0 ~ cpu_k-1) 的機器，其 nr_active 為

$\sum _{i=0}^{k-1}{x}_i(t_n)$，則假設

$x_i(t_0)=0$，則

$$\sum _{i=0}^{k-1}{x}_i(t_n)=\sum _i{x}_i(t_n)-x_i(t_0)$$

該式子又會等同於:

$$=\sum _i\sum _{j=1}^n{x}_i(t_j)-x_i(t_{j-1})$$

而另一個對 calc_load_tasks 的更新是在計算 avenrun 的 calc_global_load 時才進行。該時刻的 delta 來自 calc_load_nohz_read。在非 NO_HZ config，該函數只是返回 0，而在 NO_HZ config(即 tickless kernel) 下，現在我們可以先認識到在 idle 狀態下，kernel 可能會錯過 sched_tick 而導致 nr_active 的計算不準確，因此需要額外的工作即可，後面我們會再追問其中更多的細節。

avenrun 的更新

由上所述，實際的 load avg 被紀錄在 avenrun 中，要了解 load avg 如何被計算，我們需要關注核心是如何使用這個全域的變數的。我們可以看到該變數被賦值發生在
calc_global_load 與 calc_global_nohz 兩個函式。後者又是被前者所呼叫的。因此，我們首先關心 calc_global_load。

calc_global_load 在兩個點被呼叫，分別是 tick_do_update_jiffies64 和 do_timer:

回朔 do_timer 的路徑，即 periodic mode 的 timer tick 會進入:

• event_handler -> tick_handle_periodic -> tick_periodic -> do_timer

回朔 tick_do_update_jiffies64 的路徑，即 tickless kernel：

• sched_timer.function -> tick_sched_timer -> tick_sched_do_timer -> tick_do_update_jiffies64

由於 tickless 要考慮的狀況比較複雜，上述的路徑並非唯一

邏輯上，就是在 tick 發生時會呼叫 calc_global_load。

void calc_global_load(void)
{
	unsigned long sample_window;
	long active, delta;

	sample_window = READ_ONCE(calc_load_update);
	if (time_before(jiffies, sample_window + 10))
		return;

從此(配合後面的 WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);
)可知，至少經過每 5 秒會進行更新，但不會在五秒週期內的前 10 個 tick 就直接工作。

為什麼需要進行 load average 時需要額外加 10 個 ticks 呢?

讓我們先回顧一下 load average 的計算機制，計算可以分為兩個步驟:

1. 對每個時間點的 active 任務採樣，詳細的流程就如上一章節
2. 透過採樣完的結果計算 1 / 5 / 15 mins 的 load avg

由於兩步驟不會在同一時間進行，我們需要確保每次步驟 2 的進行都是在所有的 cpu 採樣完成並把 delta 更新上 calc_load_tasks 後，雖然也可以選擇提供同步的機制確保這點(比如說增加一個 semaphore 之類的?)，但參見核心中的註解說明:

/*    Furthermore, in order to avoid synchronizing all per-CPU delta folding
 *    across the machine, we assume 10 ticks is sufficient time for every
 *    CPU to have completed this task.

為了避免同步的複雜性或者成本，計算上直接假設 10 個 ticks 是足夠的。因此，在到達下次更新 avenrun 週期時，先多等 10 個 ticks。

1. 假設的根據是…?
2. 不使用強烈的手段 sync 是否沒問題?如果假設不成立?

	/*
	 * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.
	 */
	delta = calc_load_nohz_read();
	if (delta)
		atomic_long_add(delta, &calc_load_tasks);

	active = atomic_long_read(&calc_load_tasks);
	active = active > 0 ? active * FIXED_1 : 0;

calc_load_nohz_read 如前所述，是為了修正 tickless 下 nr_active 的計算不準確問題，相關細節會在後續探討 NO_HZ 的考量點時一併研究。

active * FIXED_1 則是先把 active 變成相對應的定點數表示法，以便於後續的使用。

	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
	avenrun[2] = calc_load(avenrun[2], EXP_15, active);

	WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);

然後就是關鍵的 average load 更新了，這是透過 calc_load 來完成的:

#define EXP_1		1884		/* 1/exp(5sec/1min) as fixed-point */
#define EXP_5		2014		/* 1/exp(5sec/5min) */
#define EXP_15		2037		/* 1/exp(5sec/15min) */

/*
 * a1 = a0 * e + a * (1 - e)
 */
static inline unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
	unsigned long newload;

	newload = load * exp + active * (FIXED_1 - exp);
	if (active >= load)
		newload += FIXED_1-1;

	return newload / FIXED_1;
}

前面曾經討論過，每個 load average 是由 exponentially moving sums 的方式進行計算。回顧更新的公式為:

$$\begin{gathered} avenrun(t_k)=avenrun(t_{k-1})\alpha +n\ast (1-\alpha ) \\ \alpha =1-e^{-\text{count interval}/\text{60R}} \end{gathered}$$

以 1 分鐘的 load avg 為例(R=1)，且從前面我們知道抽樣頻率 LOAD_FREQ == 5Hz:

$$\begin{gathered} avenrun(t_k)=avenrun(t_{k-1})\alpha +n\ast (1-\alpha ) \\ \alpha =1-e^{-\text{5}/\text{60}} \end{gathered}$$

但因為實際上無法直接表示

$\alpha =e^{-\text{count interval}/\text{60R}}\approx 0.92$ 的小數點位數，需用定點數來計算。我們可以想像是先將 0.92 放大 2048 倍(2 進位表示小數點右移 11 位)，透過 Decimal to Floating-Point Converter 快速計算一下，取小數點後 11 位的 binary 是 111_0101_1100。亦即

${111}_{-}{0101}_{-}{1100}_2={1884}_{10}$。這就是 EXP_n 這些神秘數字的由來了。於是計算可以重寫為:

$$\begin{gathered} avenrun(t_k)=avenrun(t_k-1)\alpha +n\ast (1-\alpha ) \\ \alpha =1-e^{-\text{5}/\text{60}}=EX{P}_{-}1/FIXE{D}_{-}1 \end{gathered}$$

$$avenrun(t_k)=avenrun(t_{k-1})\frac{EX{P}_{-}1}{FIXE{D}_{-}1}+n\frac{FIXED1-EX{P}_{-}N}{FIXED1}$$

此外，如果本輪抽樣的 active 數量比起上一輪的 load avg 有提昇，需把新的 load average + 1?

	/*
	 * In case we went to NO_HZ for multiple LOAD_FREQ intervals
	 * catch up in bulk.
	 */
	calc_global_nohz();
}

在 NO_HZ config 下，我們可能會一次錯過多次的採樣，calc_global_nohz 會針對此情況進行修正，詳見下一章節。

NO_HZ config 下的考量點

在最初的 Linux 設計中，時鐘中斷會週期性的發生以觸發搶佔性排程(preemptive scheduling)等需要週期性處理的事件。然而在 idle 狀態時，實際上沒有需要週期性進行的任務，這些時鐘中斷只會導致不斷的進入 ISR(interrupt service routine) ，但卻沒有相應的任務要處理，進而產生大量無意義的時鐘中斷，造成不必要的電源消耗。

為此，核心中引入了 tickless 的技術。在這種技術下，CPU 進入 idle 之後會關閉對應的時鐘中斷，一直等到該 CPU 需要執行重新排程時，時鐘中斷才會在次被開啟。

然而這種設計影響了 load average 的計算，因為其造成 sched_tick 並非週期性的觸發。這使得 load avg 的計算不能在 LOAD_FREQ 頻率下進行採樣，因而導致不準確的問題發生。

為解決此問題，基本思想是在進入 NO_HZ 的當下就預先將 per-cpu nr_active 的 delta 保存下來，這樣我們就可以將其作為額外的 delta，以便之後更新到全域的 calc_load_tasks，避免在原本需要採樣的時間卻因為 idle 而錯過。

但需要考慮更複雜的問題: 回顧之前所說，我們假設 10 個 ticks 是足夠從 per-cpu 蒐集到新的 delta 的，因此每個 5s 的前 10 個 ticks 不會進行 load average 的更新。然而，假設有某個 cpu 是在這 10 個 tick 以外的時間進入 idle，這代表在更新 load avg 的時刻同時可能有 idle 產生的 delta，也一併被 fold 進來，這將會造成不均勻的採樣，進而會影響 load avg 計算的精準程度。照理來說，在 10 ticks 時進入 idle 的採樣應該在下次的 load avg 計算週期再更新上去。

而具體機制的實作機制如同下圖的時間軸展示。系統中會維護兩個數字的 slot，分別是在進入 idle 狀態時，需要寫入(write, w)的 nr_active 的 delta，以及在計算 load avg 時需要讀取(read, r)的 delta。兩者在時間軸上會被錯開。例如下圖標示星號的時間點，如果準備進入 idle(tickless) 狀態時，load average 還沒有被更新，則 write 會將 delta 更新到 slot 0，而此時計算 load average 還是會先讀取 slot 1。

對於 write 和 read 應該要對應哪個 slot，會透過對 calc_load_idx 的位元反轉(flip bit)來指定(可以想像成是一個 2 entry 的 ring buffer)。查看程式碼可以更清楚其中的邏輯，首先來看讀取的部份: 在 calc_global_load 時，會呼叫 calc_load_nohz_read 把進入 idle 產生的額外 delta fold 進來。其實就是放在 calc_load_idx & 1 slot 中的值。

static inline int calc_load_read_idx(void)
{
	return calc_load_idx & 1;
}

static long calc_load_nohz_read(void)
{
	int idx = calc_load_read_idx();
	long delta = 0;

	if (atomic_long_read(&calc_load_nohz[idx]))
		delta = atomic_long_xchg(&calc_load_nohz[idx], 0);

	return delta;
}

再來看寫入的部份: 進入 idle 狀態，準備停下 tick 時(tick_nohz_stop_tick)，呼叫 calc_load_nohz_start 進行相應的處理。後者呼叫 calc_load_nohz_fold ，calc_load_write_idx 得到應該寫入的 slot，並將 delta 更新到其中。

static void calc_load_nohz_fold(struct rq *rq)
{
	long delta;

	delta = calc_load_fold_active(rq, 0);
	if (delta) {
		int idx = calc_load_write_idx();

		atomic_long_add(delta, &calc_load_nohz[idx]);
	}
}

void calc_load_nohz_start(void)
{
	/*
	 * We're going into NO_HZ mode, if there's any pending delta, fold it
	 * into the pending NO_HZ delta.
	 */
	calc_load_nohz_fold(this_rq());
}

calc_load_write_idx 判斷如果 !time_before(jiffies, READ_ONCE(calc_load_update)，就表示 calc_load_update 還沒被更新到下個週期，即此次 load average 還沒計算，則此時段以前進入 idle 的 delta 需被推遲到下次計算 load average 再 fold。透過此種方式，read / write 可以被錯開。

static inline int calc_load_write_idx(void)
{
	int idx = calc_load_idx;

	/*
	 * See calc_global_nohz(), if we observe the new index, we also
	 * need to observe the new update time.
	 */
	smp_rmb();

	/*
	 * If the folding window started, make sure we start writing in the
	 * next NO_HZ-delta.
	 */
	if (!time_before(jiffies, READ_ONCE(calc_load_update)))
		idx++;

	return idx & 1;
}

在 tick 恢復時(tick_nohz_restart_sched_tick)，需要視情況更新 this_rq->calc_load_update: 這是因為如果在原本應該使用 calc_global_load_tick 更新 calc_load_tasks 前，我們已經因為 nohz 的關係先行採樣一次了，則需要跳過此次的採樣。該行為即對應 calc_load_nohz_stop。

void calc_load_nohz_stop(void)
{
	struct rq *this_rq = this_rq();

	/*
	 * If we're still before the pending sample window, we're done.
	 */
	this_rq->calc_load_update = READ_ONCE(calc_load_update);
	if (time_before(jiffies, this_rq->calc_load_update))
		return;

	/*
	 * We woke inside or after the sample window, this means we're already
	 * accounted through the nohz accounting, so skip the entire deal and
	 * sync up for the next window.
	 */
	if (time_before(jiffies, this_rq->calc_load_update + 10))
		this_rq->calc_load_update += LOAD_FREQ;
}

現在，我們已經確保 tickless 狀態下正確的更新 per-cpu 的任務總量(calc_load_tasks)。但另一個需要考量的點是 load average 的計算 calc_global_load 也同樣受到 tickless 的影響而不再週期性的進行，為此也必須進行相應的修正。

回顧一下如果週期性更新需要遵守的遞迴式:

$$\begin{gathered} avenrun(t_k)=avenrun(t_{k-1})\alpha +n\ast (1-\alpha ) \\ \alpha =1-e^{-\text{count interval}/\text{60R}} \end{gathered}$$

現在，假設我們錯過了 1 次的更新，意即要計算

$avenrun(t_{k+1})$:

$$avenrun(t_k)=avenrun(t_{k-1})\alpha +n\ast (1-\alpha )$$

$$\begin{array}{rl}avenrun(t_{k+1})& =avenrun(t_k)\alpha +n\ast (1-\alpha )\\ & =\alpha (avenrun(t_{k-1})\alpha +n\ast (1-\alpha ))+n\ast (1-\alpha )\\ & =(avenrun(t_{k-1}){\alpha }^2+n\ast (1-{\alpha }^2))\end{array}$$

我們可以從中看到規律，也就是，假設錯過 x 次:

$$avenrun(t_k+x)=avenrun(t_k){\alpha }^x+n\ast (1-{\alpha }^x)$$

calc_global_nohz 即實現此邏輯，但仍要記得我們所儲存的數字是定點數! 因此需要實現定點數的 n 次方計算 fixed_power_int。計算方式為，對於 n，我們可以先將其的 bit representation 拆解出來:

$$n=\sum n_i\ast 2^i$$

舉例來說，

$n=6_{10}={110}_2$

$$\begin{gathered} n=\sum _{i=0}^2=n_i\ast 2^i \\ {n}_0=0,n_1=1,n_2=1 \end{gathered}$$

透過此種方式，我們可以把

$x^n$ 表示成:

$$\begin{gathered} x^n=x^{(\sum n_i\ast 2^i)}:=\prod x^{(n_i\ast 2^i)} \\ {x}^6=x^4\ast x^2 \end{gathered}$$

對應 fixed_power_int 的程式碼，可以注意到以下這個 pattern:

x *= y;
x += 1UL << (frac_bits - 1);
x >>= frac_bits;

其實就是在算定點數的

$x\ast y$(但是額外加 0.5?)

1UL << frac_bits 其實就是 FIXED_1

static unsigned long
fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
{
	unsigned long result = 1UL << frac_bits;

	if (n) {
		for (;;) {
			if (n & 1) {
				result *= x;
				result += 1UL << (frac_bits - 1);
				result >>= frac_bits;
			}
			n >>= 1;
			if (!n)
				break;
			x *= x;
			x += 1UL << (frac_bits - 1);
			x >>= frac_bits;
		}
	}

	return result;
}

unsigned long
calc_load_n(unsigned long load, unsigned long exp,
	    unsigned long active, unsigned int n)
{
	return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
}

最後，還要記得將 calc_load_idx 加一，藉此我們可以讀到上次 calc_load_write_idx 使得寫入的 slot 的 delta 值，以達到如之前圖中顯示的時間軸對應的 slot 之效果。以下是整個 calc_global_nohz 的實作:

static void calc_global_nohz(void)
{
	unsigned long sample_window;
	long delta, active, n;

	sample_window = READ_ONCE(calc_load_update);
	if (!time_before(jiffies, sample_window + 10)) {
		/*
		 * Catch-up, fold however many we are behind still
		 */
		delta = jiffies - sample_window - 10;
		n = 1 + (delta / LOAD_FREQ);

		active = atomic_long_read(&calc_load_tasks);
		active = active > 0 ? active * FIXED_1 : 0;

		avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
		avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
		avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);

		WRITE_ONCE(calc_load_update, sample_window + n * LOAD_FREQ);
	}

	/*
	 * Flip the NO_HZ index...
	 *
	 * Make sure we first write the new time then flip the index, so that
	 * calc_load_write_idx() will see the new time when it reads the new
	 * index, this avoids a double flip messing things up.
	 */
	smp_wmb();
	calc_load_idx++;
}