# 2025-05-06 問答簡記

## 說好的 arctan(x) 的積分在哪？

:::spoiler arctan(x) 積分過程
求
$$
\int \arctan(x) dx
$$
運用[分部積分法](https://zh.wikipedia.org/zh-tw/%E5%88%86%E9%83%A8%E7%A9%8D%E5%88%86%E6%B3%95)
$$
\int u\ dv =u\times v-\int v\ du
$$
1. 令 $u= \arctan(x)$，
$$
\begin{aligned}
u &= \tan^{-1}(x) \\
x &= \tan(u) \\
\frac{d}{dx}x &= \frac{d}{dx} \tan(u) \\
1 &= \sec^2(u) \frac{d}{dx}u \\
\frac{du}{dx} &= \frac{1}{\sec^2(u)} \\
\frac{du}{dx} &= \frac{1}{1+x^2} \\
\therefore du &= \frac{1}{1+x^2}\ dx
\end{aligned}
$$

2. 令 $dv = dx \to v = x$

因此，
$$
\begin{aligned}
\int u\ dv &=u\times v-\int v\ du \\
&= x \arctan(x) - \int x\ \frac{1}{1+x^2} dx \\
\int \arctan(x) dx &= x \arctan(x) - \frac{1}{2} \ln(1 + x^2) + C
\end{aligned}
$$
:::

> [回應 Threads](https://www.threads.com/@wayne.hack.chiu/post/DJLaBFiyjrD): 本課程著重解決真實世界中遇到的問題，而非僅停留在概念或架構層面。絕對不只是「很多工程邏輯，懂底層就好，具體實作不用記」，我們要有能力從數學根基逐步驗證，並透過動手來解決真實世界的問題。

回顧課程討論:
* [2025-03-18](https://hackmd.io/@sysprog/SkHmfB831e)
* [統計物理學](https://simple.wikipedia.org/wiki/Statistical_physics) (statistical physics) 指根據物質微觀夠及微觀粒子相互作用的認知，藉由統計的方法，對大量粒子組成的物理特性和巨觀規律，做出微觀解釋的理論物理分支。如今，當我們想要「看到」context switch, interrupt latency, jitter 等等微觀事件，無一不透過統計學！
* $e$ 的出現反映自然界中普遍存在的指數型增長或衰減現象，這些現象無論在連續系統，抑或是離散事件中，都可藉由 $e$ 予以描述 $\to$ [歐拉數：描述連續變化的基石](https://hackmd.io/@sysprog/euler-number)
* [2025-03-25](https://hackmd.io/@sysprog/r1XZjdk6Jx)
* 雖然產生 ASLR 位移的 PRNG 本身輸出均勻分布的亂數，Linux 與 PaX 會對這些數值再做轉換，因此實際位移並非均勻分布：在 PaX 32 位環境中呈三角形分布，而 PaX 64 位環境則近似鐘形分布
* 窮舉猜測位址時，猜測三角分布或鐘形分布頂端的值，發生機率特別高的區域，猜中的機率較高，藉此降低攻擊成本
* [以統計觀點看電腦網路傳輸品質](https://hackmd.io/@sysprog/network-quality)
* [2025-04-01](https://hackmd.io/@sysprog/rkf7UCNpkg)
* 異質多核排程
* 遷移模型：泊松分布
* 遷移狀態模型：馬可夫鏈
* Linux 核心中的 Completely Fair Scheduler (CFS，已被 EEVDF 取代) 實作 [Weighted Fair Queueing](https://en.wikipedia.org/wiki/Weighted_fair_queueing) (WFQ，加權公平佇列) 排程策略，其主體理念是將處理器資源依照執行緒的權重分配，以達到加權 fairness
* [2025-04-08](https://hackmd.io/@sysprog/ByFRLr-Cyx)
* Linux 核心計算 load average 的公式是基於指數平滑運算 (Exponential Smoothing) 推導而來
* [2025-04-15](https://hackmd.io/@sysprog/HkbzPNO0yg) / [2025-04-22](https://hackmd.io/@sysprog/Bk6CLg4kll)
* schedsort
* 叢集 (cluster) 效應: 一般正規化縮放整個資料範圍，但如果本來資料分布就有偏態，在縮放後容易集中映射到少數 bucket，造成多執行緒對少數 bucket 的 atomic 操作競爭
* [2025-04-29](https://hackmd.io/@sysprog/B1kJjtTkll)
* 傳輸和驗證機制中的 cookie
> [Smart Cookie NVIDIA CEO Huang: build NVIDIA's technology all in US, very strong Trump encouragement](https://youtu.be/-Le5AauVzJI): "smart cookie" 是英語俚語，指機敏且具洞察力之人士，帶有明顯正面評價。此處作輕鬆而親切之稱呼，用以突顯對方的卓越智慧與應變能力，通常表示對其聰穎才智的肯定。

或許有人會好奇，為何與其他 Linux 核心課程相比，成功大學開設的「[Linux 核心設計](https://wiki.csie.ncku.edu.tw/linux/schedule)」特別重視數學 (例如要求學員證明級數收斂、解釋泊松分布)，甚至讓部分學員誤以為授課教師刻意刁難。然而，深入分析後就會發現，任何工程議題發展到極致，往往都需要借助數學工具，而 Linux 核心作為多種工程技術的複雜綜合體，自然也離不開數學的支撐。

在多核處理器普及的今日，尤其是在強調[大量租戶](https://en.wikipedia.org/wiki/Multitenancy) (multitenancy) 的雲端環境中，Linux CPU 排程器的效能至關重要：在這些環境裡，行程 (process) 的瞬時 CPU 需求常呈現[重尾分布](https://en.wikipedia.org/wiki/Heavy-tailed_distribution) (heavy-tailed distribution) 的特性：亦即，多數行程在大部分時間僅佔用少量 CPU 資源，但偶爾會爆發出持續、高強度的運算需求。該行為模式對排程器提出嚴峻的挑戰：排程器不僅要確保各行程能公平獲得 CPU 時間片段 (timeslice)，還需要透過有效的負載均衡 (load balancing) 將計算負載均勻分散到各個處理器核，同時也必須能夠實施必要的資源限制 (resource limits)。為了理解和應對這些挑戰，以下探討 Linux 排程器設計中所蘊含的幾個關鍵數學與統計概念，特別是與[柯西分布](https://en.wikipedia.org/wiki/Cauchy_distribution) (Cauchy Distribution)、PELT (Per-Entity Load Tracking)、EEVDF (Earliest Eligible Virtual Deadline First) 排程演算法，以及 [cgroup 頻寬控制](https://docs.kernel.org/scheduler/sched-bwc.html) (cgroup bandwidth control) 相關的原理。
> [SaaS 關鍵設計 - Multi-Tenancy - 探討真實世界的租賃關係](https://rickhw.github.io/2023/09/11/DistributedSystems/SaaS-KeyDesign_MultiTenancy-with-Isolation-Factor/)

### 柯西分布：為何用來比喻突發尖峰
> 「為什麼柯西分布格外清心寡慾？」/「因為它沒有期望」

> 圖片出處: [Searching for outliers](https://www.benkuhn.net/outliers/)

在描述隨機現象時，[重尾分布](https://en.wikipedia.org/wiki/Heavy-tailed_distribution) (Heavy-tailed distribution) 能夠貼切描述某些系統「常態平穩，但偶發極端事件」的特性。設隨機變數 $X$ 的尾分布函數為
$$
\overline F(x)=P(X> x)
$$

若對於所有 $\lambda > 0$，該函數皆滿足以下條件：
$$
\lim_{x\to\infty}e^{\lambda x}\,\overline F(x)=\infty
$$

則稱隨機變數 $X$ (或其機率分布) 為重尾 (heavy-tailed)。這個條件意味著，其尾部機率 $\overline F(x)$ 的衰減速度比任何指數函數 $e^{-\lambda x}$ (其中 $\lambda > 0$) 都還要慢。重尾的特性可以體現在分布的右尾 (對應極大值) 、左尾 (對應極小值) ，或同時體現在兩側。儘管定義涵蓋各種情況，但在實際應用 (如系統負載、網路流量分析) 中，通常更關注右尾重尾，因為它直接關聯到罕見但影響巨大的極端事件 (如：超長任務執行時間、突發的流量高峰)。常用子類型:

| 類型 | 數學定義 | 直觀解釋 |
| :------- | :------ | :------ |
| 長尾分布 <br> (Long-tailed) | 對於任何固定的 $y > 0$，條件機率 $P(X > x+y \mid X > x)$ 在 $x \to \infty$ 時趨近於 1： <br> $\displaystyle \forall y>0,\;\lim_{x\to\infty}\frac{P(X>x+y)}{P(X>x)}=1$ | 尾部機率衰減極其緩慢。當觀測到極大值 $x$ 後，觀測到稍微再大一點的值 $x+y$ 的可能性並未顯著降低。可說尾端「拖得很長」 |
| 次指數分布 <br> (Subexponential) | 令 $X_1, X_2$ 為獨立同分布於 $F$ 的隨機變數，則： <br> $\displaystyle \lim_{x\to\infty}\frac{P(X_1+X_2>x)}{P(X>x)}=2$ | 二個獨立同分布樣本之和超過一個極高閾值 $x$ 的事件，其機率約等於單一樣本超過 $x$ 的機率的二倍。意味著，總和的極端值幾乎完全由二個樣本中的最大值決定 (即 $\max(X_1, X_2)$) 。這稱為「單一巨大跳躍原理」(Principle of the single big jump) |

重尾 (heavy-tailed)、長尾 (long-tailed) 與次指數 (subexponential) 分布之間存在蘊含關係：次指數分布必為長尾分布，長尾分布必為重尾分布，但反之不一定成立。以下是幾個經典案例：
* [帕累托分布](https://en.wikipedia.org/wiki/Pareto_distribution) (Pareto distribution, shape parameter $\alpha > 0$)：其尾分布函數 $\overline F(x)$ 具有冪律 (power-law) 形式，例如 $\overline F(x) = \left(\frac{x}{x_{\min}}\right)^{-\alpha}$ (對於 $x \ge x_{\min}$)。此分布既是次指數分布，也是長尾分布
* [對數常態分布](https://en.wikipedia.org/wiki/Log-normal_distribution) (Log-normal distribution)：屬於重尾分布，但不是次指數分布
* [柯西分布](https://en.wikipedia.org/wiki/Cauchy_distribution) (Cauchy distribution)：其尾分布 $\overline F(x) \sim \frac{C}{x}$ (即尾部機率以 $x^{-1}$ 速度衰減，其中 C 為常數)。它既是重尾分布，也是長尾分布，但不滿足次指數分布的卷積性質要求

這些分類有助於我們理解，當多個獨立同分布的隨機需求疊加 (如多個任務的總執行時間) 時，其總和或極值的行為是否會不成比例被單一的極端事件所主導 (這是次指數分布的重要特徵)。標準柯西分布便是一個探討重尾現象的經典範例，其機率密度函數 (PDF)
$$
f(x) = \frac{1}{\pi (1 + x^2)}
$$

該函數形式與反正切函數 ($\arctan x$) 的導數密切相關：
$$
\frac{d}{dx} \arctan(x) = \frac{1}{1 + x^2}
$$

二者僅相差一個確保總機率積分為 $1$ 的正規化常數 $\frac{1}{\pi}$。其 PDF 尾部僅以 $x^{-2}$ 的冪律速度衰減，這遠比常態分布 (Normal distribution) 的指數級衰減 ($e^{-x^2/2}$) 慢得多；其直接後果就是：「極端值^遠離中心的數值^不罕見」。由於積分 $\int_{-\infty}^{\infty} |x| f(x) dx$ (絕對一階動差) 和 $\int_{-\infty}^{\infty} x^2 f(x) dx$ (二階動差) 均發散，柯西分布不存在定義明確的期望值 (mean) 與變異數 (variance)。這意味著，即使從柯西分布中抽取大量樣本，其樣本平均值 (sample mean) 也不會像常態分布那樣根據大數法則收斂到一個穩定的值，而是會持續劇烈波動。

我們將這種重尾特性類比到 CPU 排程場景：假設某個行程在極短時間 (如 1 ms) 內，其實際需求的 CPU 運算時間 (或資源量) 可用具有類似柯西分布重尾特性的隨機變數 $X$ 來描述，這將意味著：
* 在絕大多數時間間隔內，行程的 CPU 需求量 $X$ 非常小 (對應系統相對空閒或該行程不活躍)
* 然而，系統會以不可忽視的機率遭遇到 $X$ 值極大 (遠超平均水準) 的情況，對應行程突然產生飽和級別的 CPU 運算需求 (即尖峰負載)
* 這些偶發的極端尖峰負載，會對基於歷史資料的統計指標 (如平均負載) 產生不成比例的巨大影響 (類似柯西分布樣本均值不穩定的情況)，這正是 CPU 排程器在進行負載預測和保證 fairness 時，最難處理的負載模式

PDF 的重尾特性意味著「出現極高尖峰負載的機率，相較於常態分布等指數衰減的分布要高得多」。若 CPU 排程器僅依賴傳統的歷史平均方法 (如 CFS 中 PELT 使用的[指數加權移動平均](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) [EWMA])，其對行程未來負載的預測容易被這些數量稀少但強度極高的尖峰負載所扭曲。這種重尾分布現象在現實世界的網路流量、雲端計算資源使用模式、甚至金融市場波動中都屢見不鮮。因此，Linux 核心開發者在設計其 CPU 排程機制時，例如在其最新的 EEVDF 排程演算法、cgroups 的頻寬控制 (BWC) 及 PELT 負載追蹤的動態半衰期調整策略中，都要設法應對這種由重尾負載帶來的高度不確定性和對系統穩定性、fairness 的挑戰。
> 參見[微積分: 所有反三角函數的導數](https://youtu.be/iXrl_NY-lVs)

#### 回顧定義
設 $X$ 與 $Y$ 為二個獨立、同分佈且以零為對稱中心的連續隨機變數。考慮其比值
$$
Z=\frac{X}{Y}
$$

比值的 PDF 可由轉換公式得到
$$
f_{Z}(z)=\int_{-\infty}^{\infty}\!|x|\,
f_{X}(x)\,
f_{Y}(xz)\,
dx,
\qquad z\in\mathbb{R}.
$$

若 $X$ 和 $Y$ 皆服從標準常態 $N(0,1)$，上式積分可顯式化簡為
$$
f_{Z}(z)=\frac{1}{\pi\,(1+z^{2})},
$$

即位置參數 $0$、尺度參數 $1$ 的標準柯西分布。只要 $X$、$Y$ 獨立且同屬任何零對稱分布，其比值仍是柯西分布，但尺度參數取決於原始分布的「伸縮」常數；若 $X,Y\sim\mathcal N(\mu,\sigma^{2})$，則 $Z$ 的 PDF 為
$$
f_{Z}(z)=\frac{\sigma}{\pi\bigl[(z\mu-\sigma)^{2}+\sigma^{2}\bigr]}
$$

仍保持 $1+z^{2}$ 型式，只是平移／伸縮。

柯西分布的尾機率為
$$
P(|Z|>x)=\frac{1}{\pi}\int_{x}^{\infty}\!\frac{2}{1+t^{2}}\,dt
=\frac{2}{\pi}\arctan\!\Bigl(\frac{1}{x}\Bigr)\xrightarrow[x\to\infty]{}\frac{2}{\pi x}
$$

僅以 $x^{-1}$ 衰減。因而
$$
\int_{-\infty}^{\infty}\!|z|\,f_{Z}(z)\,dz
=\infty,\qquad
\int_{-\infty}^{\infty}\!z^{2}\,f_{Z}(z)\,dz
=\infty
$$

致使期望值與變異數皆不存在。統計時便以「位置參數」(取代均值) 與「尺度參數」(取代標準差) 描述集中趨勢與離散程度。

應用與背景:
* 極端事件建模：地震強度、山體滑坡規模、金融資產單日暴跌等現象的尾部常遠重於常態假設；若使用常態模型，所估風險會嚴重低估。柯西分布 (或更高階的帕累托、α-穩態分布) 能提供上限不存在、尾巴厚重的替代選項，使罕見大損失的機率估計更貼近實際
* 演算法測試：在測試排序、最佳化或機器學習模型時，柯西樣本常被用來檢驗演算法對「無均值資料」的穩健性

#### 應用案例: [TCP-RT](https://help.aliyun.com/zh/alinux/user-guide/tcp-rt-configurations)
中國最大的雲端資料庫供應商阿里巴巴，其 RDS (Relational Database Service，關聯式資料庫服務) 團隊長期專注於提供穩定、高效的雲端資料庫服務。RDS 本質是多租戶的 DBaaS 平台，藉由輕量級 [KVM](https://hackmd.io/@sysprog/linux-kvm) 與 Docker 等資源隔離技術，將使用者購買的資料庫實例動態部署至實體主機，並達成資源的彈性配置與自動升降級，以達成全自動且智慧的管理。

雲端資料庫服務的穩定性直接關係到企業業務的連續性，因此，快速偵測並準確定位效能異常成為技術上的關鍵挑戰。TCP-RT 作為阿里雲資料庫體系中負責監控與診斷服務品質的基礎設施，透過主機 TCP/IP 通訊堆疊的壅塞控制模組擷取追蹤資料，計算資料庫延遲與網路異常指標。這些資料經由後端流式計算平台進行大規模即時分析與彙總，並運用柯西分布模型比對歷史統計指標，偵測潛在異常；同時，透過分析同主機、交換器與 proxy 下多實例的趨勢一致性，量化不同元件異常的可能。

〈[TCP-RT: Instrument and Diagnostic Analysis System for Service Quality of Cloud Databases at Massive Scale in Real-time](https://dl.acm.org/doi/abs/10.1145/3183713.3190659)〉(SIGMOD 2018) 的主要貢獻包括：可在低開銷、非侵入的前提，針對關聯式資料庫進行每個連線層級的延遲與頻寬量測，辨識短連接與長連接模式，並能端對端量化基礎網路品質對資料庫服務品質的影響，如封包遺失率與重傳率；建構具備水平擴展能力、容錯性、即時性與 Exactly Once 語意的運算系統，支援與其他大資料平台如 EMR 與 MaxCompute 的資料交換；及設計全新演算法，專為 TCP-RT 資料進行異常檢測與根因分析所用，進一步提升雲端資料庫服務品質保障的能力。
> [解讀](https://zhuanlan.zhihu.com/p/37112986)

#### 為何不能用「頻率的極限」來定義機率？
在數學分析中，函數的 [ε–δ 極限](https://en.wikipedia.org/wiki/Limit_of_a_function)定義是建立在確定性 (determinism) 基礎之上：對於一個確定的函數 $f$ 和點 $x_0$，若其極限為 $A$，則對於任意指定的誤差範圍 $\varepsilon > 0$，總能找到一個對應的鄰域半徑 $\delta > 0$，使得只要 $x$ 足夠接近 $x_0$ (滿足 $0 < |x-x_0| < \delta$) ，函數值 $f(x)$ 就必定落在目標值 $A$ 的 $\varepsilon$ 範圍內：
$$
|x-x_0|<\delta\;\Longrightarrow\;|f(x)-A|<\varepsilon .
$$

一旦 $x$ 進入 $\delta$-鄰域，$f(x)$ 必然停留在 $A$ 的 $\varepsilon$-鄰域內。極限值 $A$ 若存在，則是唯一確定。

我們想將事件 A 發生的機率 $P(A)$ 定義為在大量重複獨立試驗中，事件 A 出現的相對頻率 $m(n)/n$ (其中 $m(n)$ 為前 $n$ 次試驗中 A 出現的次數) 的極限：
$$
P(A) \stackrel{?}{=} \lim_{n\to\infty} \frac{m(n)}{n}
$$

然而，將這個極限作為機率的基礎定義，會遇到至少三個障礙：
1. 隨機性 vs. 確定性：相對頻率 $\frac{m(n)}{n}$ 本身是個隨機變數 (對於固定的試驗次數 $n$) 或者說是個隨機序列 (當 $n$ 遞增時) 。對於同一個 $n$，重複進行 $n$ 次試驗，得到的 $\frac{m(n)}{n}$ 的值會因每次試驗結果 (樣本路徑) 的不同而變化。這與 ε–δ 定義中的 $f(x)$ 不同，對於給定的 $x$，$f(x)$ 的值是唯一確定
2. 收斂模式差異
描述相對頻率趨近於理論機率的是[大數法則](https://en.wikipedia.org/wiki/Law_of_large_numbers) (Law of Large Numbers)。它保證的收斂不是上述 ε–δ 意義的確定性收斂，而是機率意義的收斂，例如幾乎必然收斂 (almost sure convergence)：
$$
\frac{m(n)}{n} \xrightarrow{\text{a.s.}} P(A)
$$
該收斂 (幾乎必然收斂) 僅保證那些不收斂到 $P(A)$ 的樣本路徑所構成的事件集合，其總機率為零。它不保證對於每個可能的樣本路徑，都存在一個 $N$ 使得當 $n > N$ 時，$\frac{m(n)}{n}$ 永遠落在 $(P(A)-\varepsilon, P(A)+\varepsilon)$ 區間內。實際的樣本路徑總會存在隨機漲落，可能在收斂過程中暫時偏離目標值。收斂過程也不保證是單調的
3. 邏輯循環問題 (Circularity)
要嚴謹討論 $\frac{m(n)}{n}$ 「以機率 1 收斂」(即幾乎必然收斂) ，必須預先存在一個定義好的機率空間和機率測度 $P$。若我們試圖反過來，用這個極限行為來定義機率測度 $P$ 本身，就會陷入邏輯循環：定義依賴於需要被定義的概念。正是為了解決這些根本問題，Andrey N. Kolmogorov 於 1933 年提出基於測度論的機率公理化體系，將機率定義為定義在樣本空間 $\Omega$ 的某個事件域 (σ-代數) $\mathcal{F}$ 上的，滿足以下條件的測度 (measure) $P$：
* 非負性：對任意事件 $A \in \mathcal{F}$，有 $P(A) \ge 0$
* 正規性：$P(\Omega) = 1$
* 可列可加性：對於 $\mathcal{F}$ 中任意一列**互不相容**的事件 $A_1, A_2, \dots$ (即 $A_i \cap A_j = \emptyset$ 對於 $i \neq j$) ，有：
$$
P\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i)
$$
在這個公理化框架下，大數法則 (如弱大數法則和強大數法則) 不再是機率的定義，而是可嚴格證明的定理，它們描述在公理體系下相對頻率的收斂行為

以公平硬幣拋擲為例，說明上述證明路徑：設 $X_i$ 為第 $i$ 次拋擲結果的指示隨機變數 (indicator random variable)，正面朝上時 $X_i=1$，反面朝上時 $X_i=0$。由於硬幣公平，$P(X_i=1) = P(X_i=0) = 1/2$，因此期望值 $E[X_i] = 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} = \frac{1}{2}$。我們觀察前 $n$ 次拋擲結果的樣本均值 (即正面出現的相對頻率) ：
$$
\overline{X}_n = \frac{1}{n} \sum_{i=1}^{n} X_i
$$
1. [Markov 不等式](https://en.wikipedia.org/wiki/Markov%27s_inequality)：對於任意非負隨機變數 $Y$ 和任意常數 $a > 0$，有：
$$
P(Y \ge a) \le \frac{E[Y]}{a}
$$
2. [Chebyshev 不等式](https://en.wikipedia.org/wiki/Chebyshev%27s_inequality)：令 $Y = (\overline{X}_n - E[\overline{X}_n])^2 = (\overline{X}_n - 1/2)^2$ (注意 $E[\overline{X}_n] = E[X_i] = 1/2$) ，並取 $a = \varepsilon^2$ (其中 $\varepsilon > 0$) ，運用 Markov 不等式於 $Y$：
$$
P\left((\overline{X}_n - 1/2)^2 \ge \varepsilon^2\right) \le \frac{E[(\overline{X}_n - 1/2)^2]}{\varepsilon^2} = \frac{\operatorname{Var}(\overline{X}_n)}{\varepsilon^2}
$$
由於 $X_i$ 獨立同分布，$\operatorname{Var}(\overline{X}_n) = \frac{\operatorname{Var}(X_i)}{n}$。對於 $X_i$，$\operatorname{Var}(X_i) = E[X_i^2] - (E[X_i])^2 = E[X_i] - (1/2)^2 = 1/2 - 1/4 = 1/4$。因此： $$
P\left(|\overline{X}_n - 1/2| \ge \varepsilon\right) \le \frac{\operatorname{Var}(X_i)}{n \varepsilon^2} = \frac{1/4}{n \varepsilon^2}
$$
結果表明，當 $n \to \infty$ 時，$P(|\overline{X}_n - 1/2| \ge \varepsilon) \to 0$，亦即 Bernoulli 弱大數法則 (Bernoulli's Weak Law of Large Numbers)
3. 強大數法則 (Strong Law of Large Numbers)：要證明更強的幾乎必然收斂，即 $\overline{X}_n \xrightarrow{\text{a.s.}} 1/2$，需要更精細的工具，例如 Borel-Cantelli Lemma。雖然直接將 Chebyshev 不等式代入 Borel-Cantelli Lemma 的條件 ($\sum P(A_n) < \infty$) 在此例中，不直接滿足 (因為 $\sum_n \frac{1}{4n\varepsilon^2}$ 發散) ，但可透過更強的機率不等式 (如涉及四階動差) 或對子序列應用該引理等技巧來證明，從而得知：對於任意 $\varepsilon > 0$，事件「$|\overline{X}_n - 1/2| \ge \varepsilon$ 無窮多次發生」的機率為 0
$$
P\left( \limsup_{n\to\infty} \{|\overline{X}_n - 1/2| \ge \varepsilon\} \right) = 0
$$
這等價於強大數法則的表述：
$$
\overline{X}_n \xrightarrow{\text{a.s.}} \frac{1}{2}
$$

從 Markov 不等式到 Chebyshev 不等式 (得到弱大數法則)，再到利用 Borel-Cantelli Lemma 證明強大數法則，該論證指出，在 Kolmogorov 公理體系下，可嚴格證明相對頻率幾乎必然收斂於理論機率。然而，這種收斂的隨機本質意味著，任何單一的觀測序列 (樣本路徑) 都可能出現暫時偏離理論值的漲落 (fluctuations)，無法像確定性極限那樣保證在某個 $N$ 之後永久維持在任意小的 $\varepsilon$ 範圍內。

例如，即使硬幣絕對公平，也完全可能在某次實驗的第 6001 次到第 6200 次拋擲中連續出現 200 次正面 (儘管機率極低)，這會導致 $\overline{X}_{6200}$ 暫時顯著偏離 0.5，這就是典型的隨機漲落。
> [執行 35 萬次的丟硬幣實驗，證明即使硬幣沒有作弊，這個遊戲的機率依然不公平](https://www.threads.com/@scientists543/post/DAD3-w8vDfX)

函數極限的 ε–δ 定義描述的是種確定的收斂行為，而相對頻率的收斂本質是隨機，其路徑包含不可避免的漲落。因此，儘管大數定律確立相對頻率與理論機率的聯繫，但不能直接將頻率的極限作為機率公理化的基礎定義。

### 以 PELT 追蹤 CPU 負載
Linux 核心採用 [PELT](https://docs.kernel.org/scheduler/schedutil.html) (Per-Entity Load Tracking) 機制，來追蹤個別行程或 cgroups 近期的 CPU 使用率。該機制通常以固定的時間間隔 (例如每 1ms，一個 [scheduler tick](https://wiki.linuxfoundation.org/realtime/documentation/howto/tools/ticklesskernel))測量實體 (行程或 cgroups) 在該週期內的即時 CPU 佔用比例 $r_n$ ($0 \le r_n \le 1$) ，然後藉由[指數加權移動平均](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) (Exponential Weighted Moving Average, EWMA) 的方式來更新其負載估計值 $u_n$：
$$
u_{n} = k \cdot u_{n-1} + (1-k) \cdot r_{n}
$$
其中衰減因子 $k = \exp\left(-\frac{\Delta t}{\tau}\right)$，而 $\Delta t$ 是更新週期 (例如 1 ms) 。PELT 預設的半衰期 (half-life) $t_{1/2}$ 為 32 ms，對應的時間常數 $\tau = \frac{t_{1/2}}{\ln 2} \approx 46.16$ ms。這意味著，歷史負載資料的影響力大約每經過 32 ms 就會衰減一半 (即權重變為原來的 50%) 。對應的衰減因子 $k \approx e^{-1/46.16} \approx 0.9785$。將此離散時間的遞迴更新過程推廣到連續時間，其數學形式等價於一個指數衰減核函數的[卷積](https://en.wikipedia.org/wiki/Convolution) (convolution，亦譯作疊積、褶積或旋積)：
$$
u(t) = \frac{1}{\tau} \int_{-\infty}^{t} r(s) e^{-(t-s)/\tau} ds
$$

其直觀意義是：目前的負載估計值 $u(t)$ 是對過去所有時刻的即時使用率 $r(s)$ 進行加權積分，其中權重因子 $e^{-(t-s)/\tau}$ 隨時間差 $(t-s)$ 的增加而指數衰減，即越久遠的歷史資料影響越小。

考慮這樣的情境：某個行程經歷一段持續時間為 $T$ 的滿載尖峰 (即 $r(s) \approx 1$ 在該時段內)，PELT 負載估計值 $u(t)$ 會在此期間快速累積並趨近於飽和值 $1$。然而，一旦尖峰結束 ($r(s)$ 驟降為 0 或一個較小值)，$u(t)$ 將會以固定的指數速率開始衰減，其衰減行為完全由預設的時間常數 $\tau$ (或等價由衰減因子 $k \approx 0.9785$) 決定。該衰減速率與觸發它的尖峰的實際持續時間 $T$ 或其總量 (尖峰面積) 無關。

這正是 PELT 機制在面對具有重尾 (heavy-tailed) 特徵的工作負載 (即包含短暫但強度極高的計算尖峰) 時所暴露出的問題：它會「過度記憶」這些短暫尖峰的影響，使得負載估計值 $u(t)$ 在尖峰過後仍長時間維持在較高水平，從而可能導致不準確的負載均衡決策 (例如，不必要的任務遷移)或 CPU 頻率調節失當。

從數學角度，我們可將 PELT 的這種「快上慢下」 (快速響應尖峰的開始，但以固定速率緩慢遺忘) 的行為，與反正切函數的積分進行概念層面的類比 (非嚴格的數學等價關係，借其函數形式)：
$$
\int \arctan(x) dx = x \arctan(x) - \frac{1}{2} \ln(1 + x^2) + C
$$

作概念類比：
* 反正切函數 $\arctan(x)$ 作為被積函數：其函數圖像呈現出快速上升然後趨於飽和的 S 型曲線 ($\lim_{x\to\infty} \arctan x = \pi/2$) 。可類比於 PELT 負載值 $u(t)$ 在持續滿載尖峰期間，從 0 快速累積，並逐漸趨近於飽和值 1 的動態過程
* 積分結果中的對數項 $-\frac{1}{2}\ln(1+x^2)$：此項對積分值的貢獻隨 $x$ 增大而緩慢增長 (其導數為 $-x/(1+x^2)$，衰減速率類似 $1/x$)。雖然這與 PELT 的指數衰減 $e^{-t/\tau}$ 在數學形式不同，但我們可將這種緩慢變化的特性，類比為 PELT 在尖峰過後，其衰減行為被固定的時間常數 $\tau$ 所主導，呈現出一種與尖峰本身特性 (如持續時間 $T$) 脫鉤的、記憶時間較長的「殘留效應」 (residual decay)

$\arctan(x)$ 的導數 $\frac{d}{dx}\arctan(x) = \frac{1}{1+x^2}$，其形式恰好正比於標準柯西分布的 PDF。鑑於柯西分布是典型的重尾分布，這恰好點明討論的背景：PELT 需要有效應對的，正是這種包含機率不可忽視的極端 (重尾) 負載尖峰的輸入信號。

為了解決 PELT 固定半衰期在重尾負載下可能引發的問題，來自 Google 和 Arm 等公司的開發者提出核心修改 "[sched/pelt: Change PELT halflife at runtime](https://lore.kernel.org/lkml/6281126b-3b93-86fa-25d6-d637b6c7dd87%40arm.com/t/)"，其目標是允許系統在運行時動態調整 PELT 的半衰期，例如可將其從預設的 32 ms 縮短至 16 ms 或 8 ms。如此可加快負載估計值 $u(t)$ 在尖峰結束後的回落速度 —— 對於同樣幅度的尖峰，其影響的「殘留時間」大致會按半衰期的比例縮短，這有助於顯著減少因負載估計滯後而引發的不必要的任務遷移 (遷移抖動，migration churn) 及 CPU 頻率的劇烈震盪 (frequency scaling oscillations)。

此外，也存在一些更具實驗性的探索，例如嘗試在偵測到顯著的負載尖峰時，暫時縮短時間常數 $\tau$ (即提高系統對變化的敏感度並加速衰減)，並在尖峰過後恢復到預設值，以此在負載估計的穩定與對負載變化的響應靈敏度之間，尋求更好的動態平衡。

| 概念 | 數學形式 | 在排程器的作用 |
| ------------- | ------------------------------------- | ----------------------- |
| EWMA | $u_n=k\,u_{n-1}+(1-k)r_n$ | 低成本、易疊加 (可直接搬遷行程而不重算歷史) |
| 指數卷積 | $\tau^{-1}\!\int r(s)e^{-(t-s)/\tau}$ | 與離散 EWMA 等價；便於理論分析 |
| 柯西 PDF | $f(x)=1/[\pi(1+x^{2})]$ | 描述重尾尖峰的機率結構 |
| 半衰期 ↔ $\tau$ | $\tau=t_{1/2}/\ln2$ | 決定 PELT 殘留長度；過大則決策滯後 |
| $\arctan$ 積分 | 線性 + 對數項 | 類比尖峰累積與殘留衰減 |

藉助對指數加權移動平均 (EWMA) 特性、重尾分布影響及與柯西分布相關概念的理解等數學視角，我們不僅可解釋現有 PELT 機制的行為模式，例如，在系統主要處理符合輕尾特性 (如接近常態分布) 的常態負載時，PELT 較大的預設半衰期 (如 32 ms) 能有效平滑掉短時的微小波動，提供更穩定的負載估計；然而，當系統面臨包含顯著重尾尖峰的負載時，則可能需要採用更具適應性的策略，如動態縮短 PELT 的半衰期，或探索像是以分位數 (quantile-based) 為基礎的平滑方法，以避免 CPU 排程決策 (如任務遷移) 和 CPU [動態頻率調節](https://en.wikipedia.org/wiki/Dynamic_frequency_scaling) (DVFS) 長時間被過往、現已不再活躍的歷史負載高峰所「誤導」或「挾持」。

### EEVDF 精確控制微觀 fairness 與 latency
從 Linux v6.6 起，[EEVDF](https://docs.kernel.org/scheduler/sched-eevdf.html) (Earliest Eligible Virtual Deadline First) 取代 CFS 成為預設的 CPU 排程器。在 CFS 與 EEVDF 排程機制中，任務 $i$ 的權重 $w_i$ 確立其在任何特定時刻應獲得的 CPU 服務速率。此服務速率 $f_i(t)$ 通常定義為該任務的權重 $w_i$ 占當時所有可執行任務 (以集合 $\mathcal{A}(t)$ 表示) 總權重 $\sum_{j \in \mathcal{A}(t)} w_j$ 的比例：
$$
f_i(t) = \frac{w_i}{\sum_{j \in \mathcal{A}(t)} w_j}
$$

在一個理想化的連續時間模型中，任務 $i$ 在時間區間 $[t_0, t_1]$ 內應獲得的理想服務量 $S_i(t_0, t_1)$，即為其瞬時服務速率 $f_i(\tau)$ 在該區間的積分：
$$
S_i(t_0, t_1) = \int_{t_0}^{t_1} f_i(\tau) \, d\tau
$$
若將任務 $i$ 在同一時間區間實際獲得的 CPU 執行時間記為 $s_i(t_0, t_1)$，則二者之間的差額，即延遲量 (lag) $\operatorname{lag}_i(t_0, t) = S_i(t_0, t) - s_i(t_0, t)$，便量化任務 $i$ 相對於其理想公平份額是處於落後 ($\operatorname{lag}_i > 0$) 還是超前 ($\operatorname{lag}_i < 0$) 的狀態。

CFS 為每個任務 $i$ 維護獨立的虛擬執行時間 (virtual runtime，或 vruntime) $v_i(t)$，其增長速率 (僅當任務 $i$ 實際執行時) 定義為 $\frac{dv_i}{dt} = \frac{w_0}{w_i}$，此處 $w_0$ 代表基準參考權重。CPU 排程器總是從所有處於可運行 (runnable) 狀態的任務中，選擇具有全局最小 $v_i(t)$ 值的任務投入運行。此設計雖能確保各任務的長期平均服務比例趨近於其權重所決定的比例，但由於缺乏統一的全局 vruntime 參考座標，導致剛被喚醒且對延遲高度敏感的任務，若其自身的 $v_i$ 未能顯著小於其他已在運行的任務，則可能需要等待一個完整的系統目標延遲週期 (如由核心參數 `sched_latency_ns` 參數定義)，方可獲得[搶佔 CPU](https://hackmd.io/@sysprog/linux-preempt) 的機會。此外，CFS 動態調整的時間片長度以及其複雜的搶佔條件，使得對任務的最壞情況反應時間 (Worst-Case Reaction Time, WCRT) 進行精確的封閉形式數學分析，變得極為困難。

為應對上述挑戰，EEVDF 引入全局共享的系統虛擬時鐘 $V(t)$，其推進速率與當時所有可執行任務總權重的倒數 (並經基準權重 $w_0$ 進行調整) 成正比，可表示為
$$
\frac{dV(t)}{dt} = \frac{w_0}{\sum_{j \in \mathcal{A}(t)} w_j}
$$
基於此系統虛擬時鐘，任務 $i$ 在虛擬執行時間增量 $\Delta V = V(t_1) - V(t_0)$ 內應獲得的理想服務量 $S_i$ 可表達為 $S_i = \frac{w_i}{w_0} \Delta V$ (此處假設 $w_i$ 為絕對權重；若 $w_i$ 指的是相對份額，或者 $V(t)$ 的定義中已內含 $w_0^{-1}$ 這一縮放因子，則表達式可簡化為 $S_i = w_i \Delta V$)。因此，當 $V(t)$ 準確反映系統整體的理想服務進度時，$\operatorname{lag}_i(t_0, t) = \frac{w_i}{w_0}[V(t) - V(t_0)] - s_i(t_0, t)$ 便清晰記錄任務 $i$ 實際服務量相對於其應得服務量的「欠帳」(正值) 或「預支」(負值)。

為了同時控制公平性誤差 (lag) 與任務延遲，EEVDF 為每個任務 $i$ 設定一個虛擬截止時間 (virtual deadline) $\mathrm{VD}_i$，其計算公式為
$$\mathrm{VD}_i = v_{elig_i} + \frac{\text{slice_request}_i \cdot w_0}{w_i}
$$
這裡 $v_{elig_i}$ 代表任務 $i$ 的合格虛擬執行時間 (如取其上次執行結束時的 $v_i$ 或被喚醒時系統的 $V(t)$ 之中的較大值)，而 $\text{slice_request}_i$ 則是根據系統參數 (如目標延遲 `sched_latency_ns`、可執行任務數 $N$ 以及最小執行粒度 `min_granularity_ns`，通常取 $r \approx \max(\text{sched_latency_ns}/N, \text{min_granularity_ns})$) 計算得出的理想服務請求量。CPU 排程器僅將那些滿足 $v_i \le V(t)$ 條件 (即 $\operatorname{lag}_i(t_0,t) \ge 0$，表示任務未超前其公平份額) 的任務視為合格的執行候選者，並從這些合格者中選擇具有最小 $\mathrm{VD}_i$ 值的任務來執行。藉由此機制，任務的延遲量 $\operatorname{lag}_i(t_0, t)$ 得以嚴格限制在 $0 \le \operatorname{lag}_i(t_0, t) \le \frac{\text{slice_request}_i \cdot w_0}{w_i}$ 的範圍之內，這意味著任何任務即便經歷中央處理器使用的突然爆發，其能夠「超前」其應得公平份額的量，也有效限制在單個時間片段的額度內。

當可運行任務集合 $\mathcal{A}(t)$ 發生變化時，為保持系統的整體 fairness，系統虛擬時鐘 $V(t)$ 可能需進行即時調整。例如，若一個任務 $i$ 帶著其累積的延遲量 $\operatorname{lag}_i$ 離開系統 (或進入睡眠狀態)，而更新後的可執行任務集合變為 $\mathcal{A}^+$, 則系統虛擬時鐘 $V(t)$ 可能會依據 $V_{\text{new}} = V_{\text{old}} + \frac{\operatorname{lag}_i \cdot w_0}{\sum_{j \in \mathcal{A}^+} w_j}$ 進行更新 (在此情況下，若 $\operatorname{lag}_i$ 為正，表示該任務「欠下」服務量，調整會使 $V(t)$ 增加，從而讓其他任務相對更快到達其截止時間)，其目的是將該任務的延遲量重新分配給剩餘的活動任務，以維持某种形式的 lag 守恆。

對於具有重尾特性的工作負載，例如其 CPU 突發需求的持續時間或計算強度之分布，呈現出類似柯西分布的特徵，即存在不可忽略的機率發生極端長時或高強度 CPU 佔用事件，CFS 機制可能導致此類任務在其 $v_i$ 顯著超前之前，持續佔用 CPU 資源。相較之下，EEVDF 對延遲量 lag 的嚴格數學上界以及其基於獨立時間片段的排程決策，意味著即使是此類因重尾行為引發的單次計算爆發所造成的干擾，也被局限在其目前時間片段的影響範圍之內，從而使系統能夠更快對其他任務的需求做出響應。EEVDF 關於選擇哪個任務執行及分配時間片的決策，其核心演算法複雜度通常是對數級或均攤常數級。與此同時，既有的 PELT 機制依然獨立運作，它藉由對各實體歷史 CPU 使用率 $r(\sigma)$ 進行 EWMA —— 這在數學上等效於與指數衰減核函數 $e^{-(t-\sigma)/\tau}$ 的卷積運算，其中時間常數 $\tau \approx 46.2$ 毫秒 (對應約 32 毫秒的半衰期) —— 來估算其累積負載 $u(t) = \frac{1}{\tau} \int_{-\infty}^{t} r(\sigma) e^{-(t-\sigma)/\tau} \, d\sigma$。此負載估計值為跨越處理器核的負載均衡和 DVFS 提供基於較長時間窗口的統計資訊。

EEVDF 和 PELT 因此在 Linux 核心中形成功能的互補：EEVDF 專注於管理微觀時間尺度 (亦即時間片段級別) 的執行 fairness 和延遲 (latency) 控制，而 PELT 則為宏觀層面 (基於更長歷史資料) 的全局系統吞吐量改善與能源效率管理提供決策依據。因此，EEVDF 的引入並非對 CFS 公平原則的否定，而是在既有的權重比例公平框架之上，通過整合共享的系統虛擬時鐘、嚴格的任務合格性篩選機制，以及基於虛擬截止時間的優先級排程策略，為任務的服務延遲量設定明確的數學上界。這系列精心設計的增強，使得 Linux 核心得以有效平衡 fairness、顯著降低任務延遲，並強化系統對於具有重尾特性之工作負載與響應的能力。

在排程理論中，latency (延遲時間) 與 lag (延遲量) 雖均與「延遲」概念相關，但其指涉的重點有所不同：Latency 通常指實際經過的時間間隔，Lag 則是指實際服務量與理想公平基準之間的差距。

Latency 指事件從觸發到系統產生預期回應之間所經過的時間，可再細分為
* 喚醒延遲 (wakeup latency)：指行程從被喚醒狀態 (如等待的 I/O 操作完成) 轉變到首次實際獲得 CPU 執行權的時間
* 排程延遲 (scheduling latency)：泛指行程在可運行佇列中等待排程器選中並分配 CPU 的時間
*  周轉時間 (turnaround time)：行程從提交給系統開始，到其執行完成並退出為止的總體時間
*  回應時間 (response time)：指從使用者發出一個請求，到系統首次對該請求作出可感知回應 (如，開始顯示輸出或執行動作) 的時間

這些量直接以 ms 或 us 衡量，CPU 排程器的設計常致力於降低特定類型的延遲 (尤其是喚醒延遲與回應時間)，以改善系統的互動體驗或滿足即時應用的嚴格時限需求。

Lag 用於衡量每個行程在一段時間內實際獲得的 CPU 服務量，與其基於理想比例公平原則應獲得的服務量之間的差異：
* 若 $\operatorname{lag}_i > 0$，表示行程 $i$ 所獲得的服務量少於其應得的公平份額，即處於「落後」狀態
* 若 $\operatorname{lag}_i < 0$，表示行程 $i$ 所獲得的服務量已超過其應得的公平份額，即處於「超前」狀態

Lag 的量綱與服務時間相同 (如可以是虛擬服務時間或等效的實際執行時間)，它精確地反映行程在 CPU 資源分配上相對於理想公平基準的偏差程度。CFS 與 EEVDF 皆力求把各行程的 lag 約束在小範圍內，以達成比例公平。

EEVDF 之所以選擇以 lag (或與其緊密相關的虛擬時間及截止時間概念) 作為其主要的內部控制與排程依據，是基於以下原因：
1. Lag 與公平性的直接關聯：行程的權重決定其應得的 CPU 份額，而 lag 能直接且即時地量化實際分配與此理想份額之間的偏差。相較之下，latency 通常是資源公平分配後的衍生或結果指標
2. Lag 的可操作與動態修正能力：CPU 排程器可藉由調控任務的 vruntime、虛擬截止時間以及分配的時間片段長度等機制，有效抑制超前執行的行程、優先服務落後的行程，從而促使各任務的 lag 收斂至平衡狀態。直接控制 latency 則要複雜得多，因為它會受到系統總負載、任務間的 I/O 依賴關係及其他多種外部因素的共同影響與牽制
3. EEVDF 建構於虛擬時間和服務量的概念，任務的虛擬截止時間 $\mathrm{VD}_i$ 標記其完成目前應得服務份額的預期虛擬時刻；任務的執行進度是否符合此預期 (亦即是否能在 $\mathrm{VD}_i$ 前完成服務)，本質是對其 lag 狀態的評估。於是，排程決策必然要考量 lag
4. Lag 的有界性是改善延遲的基礎：EEVDF 的設計確保每個任務的 lag 被嚴格限制在一個已知的範圍內 (如 $0 \le \operatorname{lag}_i \le \text{slice_value}$，其中 $\text{slice_value}$ 與分配的時間片相關)。這種有界的 lag 特性，使得即便在系統高負載的情況下，任務的延遲 (尤其是喚醒延遲) 也能保持在相對可預測的水準，從而有效彌補 CFS 在這方面的不足

latency 描述使用者可感知的實際時間延遲；lag 描述相對於理想公平的服務量偏差。EEVDF 藉由對 lag 進行精細的量化與控制來嚴格維持系統的比例 fairness，並以此為基礎，間接改善和各種延遲指標。在一個並行的環境中，穩定且受到嚴格約束的 lag 分布，是達成良好且可預測延遲表現的關鍵條件。

### cgroup 頻寬控制與 CPU Burst
在 EEVDF 保證微觀 fairness 的基礎上，Linux 的 cgroups 機制提供宏觀層面的 CPU 資源控制。傳統的 CPU 頻寬控制 (Bandwidth Control, BWC) 透過 `cpu.max` (或舊式的 `cpu.cfs_quota_us` 和 `cpu.cfs_period_us`) 參數設定確定性的上限：一個 cgroup 在每個 `period` 內最多只能使用 `quota` 微秒的 CPU 時間。一旦用光配額，該 cgroup 下的所有行程就會被節流 (throttled)，直到下一個週期開始。

然而，在雲端等場景下，負載通常遠低於[最差情況執行時間](https://en.wikipedia.org/wiki/Worst-case_execution_time) (Worst-Case Execution Time, WCET) 。如果直接用 WCET 或較高的固定值作為 `quota`，會導致大量 CPU 資源在大部分時間內被閒置浪費。若基於平均負載或較低分位數設置 `quota`，則偶爾的合法尖峰需求會被不必要節流。

Linux 核心為滿足雲端多租戶場域的需求，在 CFS 之上發展出 CPU 頻寬控制 (bandwidth control, BWC) 。Linux 核心以二個參數 `cpu.cfs_period_us` 與 `cpu.cfs_quota_us` 為每個 cgroup 建立明確的上限：在一個週期內只要配額用盡，該 cgroup 裡所有行程立刻被節流到下個週期。如此雖能嚴格執行資源約束，卻也常留下可觀的「未使用空隙」，特別當行程執行時間擺盪幅度很大時，整體 CPU 效能難免被鎖死在最壞情境。

CFS 原始設計就內建統計推論：CPU 排程器蒐集歷史執行紀錄，以指數加權移動平均 (EWMA) 估算未來負載，並在長期觀察中檢查 fairness ── 即各 runnable 行程累積的 CPU 時間是否逼近其權重占比。然而系統充斥 I/O 完成、中斷等隨機事件，若只靠 BWC，遇到高變異工作負載仍會過度保守。於是在 Linux v5.14 加入 CPU Burst 機制：為每個 cgroup 額外配置 burst buffer，允許行程在用盡配額後「預支」至多 `quota × b` 的額度，等下個週期若實際用量低於 quota，就自動歸還。

這項機制背後是機率統計與排隊理論的思考。[CFS Bandwidth Control](https://docs.kernel.org/scheduler/sched-bwc.html) 舉例：
> That is, suppose we have 2 tasks, both specify a p(95) value, then we have a p(95)\*p(95) = 90.25% chance both tasks are within their quota and everything is good. At the same time we have a p(5)p(5) = 0.25% chance both tasks will exceed their quota at the same time (guaranteed deadline fail). Somewhere in between there’s a threshold where one exceeds and the other doesn’t underrun enough to compensate; this depends on the specific CDFs.

若所有租戶均以第 95 百分位 $p_{95}$ 作為常態配額，二個租戶同時超標的機率僅 $(1-0.95)^2 = 0.0025%$；租戶愈多，尖峰互補效果愈明顯，整體過載風險迅速下降。這與傳統即時系統以最壞情況執行時間 (WCET) 保守預留形成對比：把 WCET 切換為統計分位可顯著提高總利用率 $\sum x_i/\text{Period}_i$，同時用 burst buffer 限制短期超額，令延遲 (tardiness) 受限於總彈性額度 $\sum e_i$。

CPU Burst 的設計利用[統計時分多工](https://en.wikipedia.org/wiki/Statistical_time-division_multiplexing) (statistical multiplexing) 的原理：在多租戶環境下，雖然單個租戶可能偶爾爆發尖峰，但多個租戶同時爆發尖峰的機率通常很低。例如，如果每個租戶的 `quota` 基於其需求的第 95 百分位數 $p_{95}$ 設定，那麼二個獨立租戶同時超標的機率約為 $(1 - 0.95)^2 = 0.0025\%$。隨著租戶數量的增加，這種尖峰需求在時間上相互錯開、相互補償的效果會更強，系統整體過載的風險會快速下降。

Linux 核心開發者使用蒙地卡羅模擬評估 burst 對其他租戶的干擾。設定 $m$ 個 cgroup 共享 CPU，各自需求為獨立同分布隨機變數 (含指數、泊松與帕累托) 。量測單週期違約機率 $P(\text{WCET}>1)$ 及連續違約週期期望值 $E(\text{WCET})$。結果顯示干擾對平均利用率 $u\_{\text{avg}}$ 及 $m$ 最為敏感：在 $u\_{\text{avg}}\le0.6$, $m\ge8$ 時，即使 $b=1$ 也能把違約機率壓到 $10^{-4}$ 以下；反之，負載高且租戶少時應將 $b$ 嚴格收斂，以免單一尖峰拖垮系統。帕累托 (重尾) 負載在高利用率下最易觸發連鎖節流，說明重尾行為對 BWC/PELT 組合的衝擊最大。
> 參見: [CPU Throttling: Unbundled. Overview](https://medium.com/%40ramandumcs/cpu-throttling-unbundled-eae883e7e494)

### 因應複雜的工作負載
柯西分布與 $\arctan(x)$ 之間的關係，即 $\mathrm{d}(\arctan x)/\mathrm{d}x = 1/(1+x^2)$ 與柯西 PDF 成正比，為理解重尾負載提供數學視角，它指出極端 CPU 尖峰並非罕見。PELT 的 EWMA 正是將這些具備高發生機率的隨機尖峰，藉由帶權重的積分 (累積) 方式納入負載歷史，從而產生尖峰過後的長尾殘留效應。為了應對這種情況並提高資源利用率，CPU Burst 機制在 BWC 的確定性配額之外，於更長的週期尺度上引入了統計性的彈性：它允許以歷史分位數的短期超額使用，其有效性建立在多個負載尖峰同時出現的機率較低的統計假設 (尖峰互補效應) 之上，以此維持整體系統穩定。

現代 Linux 系統透過至少三項機制來應對具有重尾特性的複雜工作負載：
1. PELT (估算)：在近因時間窗口內 (由 $\tau$ 定義) 累積歷史負載信息。易受柯西式尖峰影響而被短時拉高，並留下衰減較慢的殘留
2. EEVDF (微觀)：透過虛擬截止時間和 slice 機制，在毫秒級時間尺度上限制單一行程偏離其 fairness 份額的程度，防止尖峰行程長期獨佔 CPU
3. BWC 與 Burst (宏觀控制)：在 cgroups 層面，於較長週期 (如 100ms) 內提供確定性 (quota) 或統計性 (burst) 的 CPU 使用上限，管理資源分配和防止濫用

對這些機制的調校策略，可從它們的數學和統計特性入手：
* 針對 PELT：考慮縮短半衰期 $\tau$，或對單週期輸入 $r_n$ 進行限幅 (clipping)，以減輕極端尖峰的直接影響和殘留
* 針對 EEVDF：研究是否可根據行程的 lag 或行為模式動態調整其 slice 大小
* 針對 BWC/Burst：根據租戶數量、預期平均負載和可接受的違約風險，來合理配置 `quota` 和 `burst` 容量。在租戶多、平均負載低的場景下可適度放寬 burst buffer，以提升性能和降低延遲

:information_source: 許多人一看到台灣科技業的職缺，就誤以為學習 Linux 僅限於撰寫裝置驅動程式；其實這只是整體開發的一小部分。授課教師在課程中刻意聚焦 CPU 排程器、並行處理、高度擴展性 (scalability) 與雲端運算，藉此打破上述偏見，讓學生把握翻轉職涯的契機。

---

## 新台幣升值與匯率市場變動
在台灣這類「淺碟型、出口導向」經濟體中，若央行完全放任匯市波動，受害最深的是實體出口商，原因如下：
* 報價與生產週期錯位，匯損直侵利潤：台灣電子業從接單到出貨約需 3 至 6 個月，期間匯率若於短期內大幅波動，例如一週內變動 10%，即可吞噬原本不到 5% 的淨利潤
> 台幣自 4 月 29 日收盤價 32.229 元，三個交易日內升值至 29.650 元，升幅近 9%
* 避險成本上升，削弱競爭力：匯市波動加劇使遠期與期權等避險工具成本線性上揚，企業為維持匯率穩定須付出更高代價，最終轉嫁至產品成本，影響國際競爭力
* 匯率偏離基本面，出口商無力因應：當匯價劇烈偏離基本面，出口商既無時間反應，也無成本轉嫁空間，只能被動承擔匯兌損失

對台灣這樣的淺碟市場而言，央行若完全不干預，匯價極易受情緒與投機資金操縱；但若將匯率固定，又可能觸犯美國對匯率干預的敏感紅線。

理想政策應為：匯率反映基本面、避免劇烈波動、干預合乎國際規範。

以下摘錄[央行聲明](https://www.ftvnews.com.tw/news/detail/2025505W0453):
1. 台灣經濟基本面穩健，資金回流與股市上揚屬正常現象
2. 台灣非匯率操控國，央行不會干預長期趨勢
3. 針對炒作匯率的虛假資訊及投機性台幣持有行為 (如無實質投資意圖) ，央行將調查、抑制並澄清
4. 台美貿易談判中無匯率議題，央行亦未參與，美方未將台灣列為匯率操控國
5. 「海湖協議」為虛構，美國財政部與被影射當事人均已澄清，無任何政策異動
6. 股市有明確虛假資訊規範，惟匯市法律規制不足，導致炒作空間
7. 「廣場協議」乃歷史背景下之特定協議，當時外匯以貿易為主，今僅占約 5%，無法類比

$\to$ [從統計學的觀點看美元台幣匯率議題](https://www.facebook.com/mingipeng/posts/pfbid05gwpx3WCAmwvDah8R5tHseoSyhr5RzjHsSoqeeysisV8RYeUKFEtpWB9NdUn67kAl)

## 年收入之統計分析
> [來源](https://www.facebook.com/magic.panda.engineer/posts/pfbid02JiTfisruCUPD9cuVHEdA6ESdqyLn3agtPmaWyShQZfPQkTfo39gPVVk5fH9EMmu4l)

探討所得稅的統計分析前，有個基礎認知至關重要：高所得個體的收入結構常具多樣性，涵蓋薪資、[資本利得](https://en.wikipedia.org/wiki/Capital_gain) (capital gains)、股息及企業盈餘分配，其[有效稅率](https://en.wikipedia.org/wiki/Effective_marginal_tax_rate) (effective tax rate) 往往因合法的租稅規劃而顯著低於法定邊際稅率 (statutory marginal tax rate) 或名目平均稅率。這些高所得者可運用專業的稅務諮詢、複雜的金融工具與法律架構 (如信託、控股公司) 及特定的稅收抵減 (deductions)、免稅額 (exemptions) 與稅額扣抵 (credits)，這些手段的專業門檻與執行成本，使其具有高度排他性，非典型受薪者所能普遍運用。此現象導致官方發布的薪資統計資料，在描繪社會整體[所得分配](https://en.wikipedia.org/wiki/Income_distribution) (overall income distribution) 時，可能存在顯著的系統性偏差 (systematic bias)。

現行官方薪資統計的[抽樣框](https://en.wikipedia.org/wiki/Sampling_frame) (sampling frame) 主要針對具有明確雇傭關係的受薪人員，因此常未能充分涵蓋自營作業者 (self-employed individuals)、零工經濟參與者 (gig economy workers)、非典型就業型態，以及地下經濟 (informal economy) 的所得；更關鍵的是，大量的非薪資所得，如租賃收入、股利、證券交易利得及不動產增值等資本利得，通常不包含在「薪資」統計範疇內。這些未被薪資分位數 (wage quantiles) 統計充分捕捉的現金流，卻是驅動資產價格 (如房地產市場)、一般物價水平以及家庭部門負債積累的重要因素。[原文](https://www.facebook.com/magic.panda.engineer/posts/pfbid02JiTfisruCUPD9cuVHEdA6ESdqyLn3agtPmaWyShQZfPQkTfo39gPVVk5fH9EMmu4l)提及的年薪 208 萬元「異常高薪」，應當理解為在受薪階級此特定子樣本 (sub-sample) 內的統計離群值 (statistical outlier)，而非能代表社會總體 (entire population) 的收入分配極端情況。此抽樣框的內在局限性，是進行後續任何基於薪資的統計推斷 (statistical inference) 時必須審慎考量的前提。

薪資與更廣義的所得分佈，經驗上常呈現顯著的右偏態 (right-skewness)，形成所謂的長尾 (long-tail) 或甚至重尾 (heavy-tail) 現象。在此類分佈中，少數極端高所得觀測值會將算術平均數向右拉抬，使其高於中位數，同時標準差也會因這些極端值的平方離差貢獻而被不成比例地放大。若仍依賴基於平均數與標準差的傳統離群值偵測方法 (如 [Z-score 檢定法](https://en.wikipedia.org/wiki/Standard_score))，將可能導致對「典型」薪資水平的誤判，且使離群值判定閾值被拉高，降低對真正極端高薪的偵測敏感度。

[四分位距](https://en.wikipedia.org/wiki/Interquartile_range) (Interquartile Range, IQR) 的定義是第三四分位數 ($Q_3$, 75th percentile) 與第一四分位數 ($Q_1$, 25th percentile) 之差，即 $IQR = Q_3 - Q_1$，是種基於[秩次](https://en.wikipedia.org/wiki/Order_statistic) (order statistics) 的穩健離散度量，其計算不直接受資料二端極端值的影響。[Tukey's fences](https://en.wikipedia.org/wiki/Outlier#Tukey's_fences) 方法是基於 IQR 的常用離群值識別規則，其上界通常設為 $Q_3 + k \cdot IQR$。由於薪資的非負性 (non-negativity)，下界 $Q_1 - k \cdot IQR$ 在薪資資料分析中往往小於零，因此在實際應用中通常不予考慮或以零為界。參數 $k$ 的取值決定離群點的判定標準：$k=1.5$ 通常用於界定溫和離群點 (mild outliers)，而 $k=3$ 則用於界定極端離群點(extreme outliers)。當官方發布的分位數資料點較為稀疏時，可基於相鄰已知分位點間所得的對數值呈線性變化的假設，採用對數內插法來估計更為平滑連續的分位數函數。例如，若經此法估算得 $Q_1 \approx 94$ 萬元、$Q_3 \approx 145$ 萬元，則 $IQR \approx 51$ 萬元。據此，溫和離群點的門檻約為 $145 + 1.5 \times 51 \approx 220$ 萬元，極端離群點的門檻約為 $145 + 3 \times 51 \approx 300$ 萬元。相較之下，若直接採用未經平滑處理的原始樣本分位數 (假設其直接給出 $Q_3=145$ 萬，而特定高百分位如 P99 對應薪資為 208 萬元)，則門檻的設定會有所不同。此差異凸顯任何統計閾值的設定，皆須透明化其資料來源、所採用的估計方法 (如內插法) 及其背後的假設。

雖然百分位排名 (Percentile Rank, PR) 直觀易懂，但在長尾分佈的尾端，其辨識度或區分能力 (resolution or discriminatory power) 顯著下降。例如，年薪 330 萬元可能對應 $PR \approx 99$，而年薪 500 萬元可能對應 $PR \approx 99.7$。二者在 PR 值上差異微小，同屬頂端百分之一的群體，但其絕對薪資差距高達 170 萬元，此差距可能已超過從 $PR=0$ 到 $PR=90$ 的整個薪資跨度 (span)。相較之下，以 IQR 的倍數作為度量，能更直接描述特定薪資相對於典型所得區間 (即 $[Q_1, Q_3]$) 的相對距離，從而更靈敏刻畫尾端薪資的延展程度與差異性。

為了更精確描述所得分佈，常採用參數分佈模型，或針對不同所得區間進行分段擬合 (piecewise fitting)。例如，常見的策略是以對數常態分佈 (Log-normal distribution, $X \sim \text{LogNormal}(\mu, \sigma^2)$) 來描述所得分佈的主體部分 (通常是中低所得段)，並以帕雷托分佈來擬合高端所得的尾部。若所得 $X$ 的自然對數 $\ln X$ 服從均值為 $\mu$、標準差為 $\sigma$ 的常態分佈 $\mathcal{N}(\mu, \sigma^2)$，則其 $p$-分位數可表示為 $Q_p = \exp(\mu + \sigma \Phi^{-1}(p))$，其中 $\Phi^{-1}(p)$ 是標準常態分佈 $\mathcal{N}(0,1)$ 的 CDF 之反函數，亦稱為分位點函數 (quantile function) 或 probit 函數。基於此模型，可理論推導 IQR，並利用樣本資料對參數 $\mu$ 和 $\sigma$ 進行估計。對於高端所得 $x > x_m$ (其中 $x_m$ 為帕雷托分佈的尺度參數或最小閾值，表示高端所得的起始點），其存活函數 (survival function) 或互補累積分佈函數 (complementary cumulative distribution function, CCDF) 常表示為 $P(X>x) = S(x) = (x_m/x)^\alpha$。此處的尾指數 (tail index) $\alpha$ 是關鍵參數：$\alpha$ 越小，表明所得分佈的尾部越「厚」(fatter tail)，即極端高所得的出現機率相對更高，所得不均程度也更嚴重。$\alpha$ 值的估計對於理解所得頂層的集中度以及設計累進稅制 (如頂層邊際稅率) 具有重要參考價值。

所得不均程度可透過[羅倫茲曲線](https://en.wikipedia.org/wiki/Lorenz_curve) (Lorenz curve) $L(p)$ 進行視覺化呈現，該曲線描繪累積人口百分比 $p$ (按所得從低到高排序) 擁有的累積總所得百分比。[吉尼係數](https://en.wikipedia.org/wiki/Gini_coefficient) (Gini coefficient) $G$ 是基於羅倫茲曲線的常用不均度量，其計算公式為 $G = 1 - 2\int_0^1 L(p) dp$。在實務中，若僅有分位數資料，可利用這些資料點繪製羅倫茲曲線的折線近似，並透過數值積分方法 (如梯形法則) 估算積分值。結合帕雷托模型對尾部分佈進行外推 (extrapolation)，可提高 $G$ 值估計的準確性，尤其是在頂端所得資料稀疏或存在上層截碼 (top-coding) 時。

現代所得稅制中的累進稅率結構，其應納稅額函數 $T(x)$ 通常設計為分段線性 (piecewise linear) 且連續的函數，其[邊際稅率](https://en.wikipedia.org/wiki/Tax_rate#Marginal) (Marginal Tax Rate, MTR) 則呈現分段常數 (piecewise constant) 的形態。該稅額函數可表示為：
$$
T(x) = \sum_{i=1}^{n} a_i \cdot \max(0, \min(x, b_i) - b_{i-1})
$$

其中 $b_0=0 < b_1 < \dots < b_n$ 代表各稅收級距 (tax brackets) 的所得上限 ($b_i$) 與下限 ($b_{i-1}$)，而 $a_i$ 則為第 $i$ 個級距所對應的邊際稅率。從稅制設計角度抑制所得過度集中時，其考量是，稅後所得 $x_{\text{net}} = x - T(x)$ 相對於稅前所得 $x$ 的彈性 (elasticity)，即 $\frac{d\ln(x - T(x))}{d\ln x}$ (可理解為「稅後所得保留率的對數變化率」)，其在高所得區間的行為應與該社會所得分佈的帕雷托尾指數 $\alpha$ 相協調，以確保稅制對頂層所得具有足夠的調節能力。對於描述所得分佈中低段的變異程度，除了 IQR 外，亦可採用[中位數絕對離差](https://en.wikipedia.org/wiki/Median_absolute_deviation) (Median Absolute Deviation, MAD)，其定義為 $MAD = c \cdot \text{median}(|X_i - \text{median}(X)|)$，其中常數 $c \approx 1.4826$ 是校準因子，使得在常態分佈假設下 MAD 是標準差 $\sigma$ 的一致估計量。此外，如 $\tau$-scale estimator 等其他更高效的穩健尺度估計量也可被考慮。

在處理尾部樣本點較為稀疏 (sparse tail data) 的情況時，[溫莎化](https://en.wikipedia.org/wiki/Winsorizing) (Winsorization) 是種常用的資料預處理技術。該方法將資料集中超出某個預設分位點 (如，第 $p$ 百分位數和第 $100-p$ 百分位數) 的極端觀測值，替換 (或稱「拉回」) 為該分位點上的值。此舉有助於提高後續統計模型參數估計的穩定性，但其代價是可能人為壓縮資料的變異性，並可能低估真實分佈尾部的厚度。

任何純粹的統計指標，無論多精巧，都難以完全捕捉個體在特定社會經濟環境下面臨的主觀生活壓力與福祉感受。例如，即便某受薪者年薪達到 300 萬元，在基於薪資的統計分佈中可能已處於極高端 (如前述估計的 $PR \approx 99.7\%$)，然而在特定地區的高昂房價、育兒支出以及總體稅負 (包括間接稅) 等多重壓力下，其「主觀貧窮線」或「財務安全感閾值」仍可能顯著提升。更重要的是，這些受薪階級中的統計離群者，其在總體經濟中的議價能力以及財富的長期積累潛力，與那些能嫻熟運用複雜金融工具、跨國資本流動及租稅規避策略，以獲取並保全巨額資本的頂層資本擁有者之間，往往存在本質的巨大差距。

---

## 為何不同大小的方陣無法相乘？
> [第 12 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz12)

設有二個方陣
$$
A\in F^{m\times m},\qquad B\in F^{n\times n},\qquad m\neq n,
$$

若試圖計算其乘積（如 $BA$ 或 $AB$），會發現此運算無法定義。其根本原因可歸納如下：
1. 矩陣是線性轉換在指定有序基底下的座標表示
2. 矩陣乘法對應於線性轉換的合成，此合成要求前一轉換的對應域 (codomain) 與後一轉換的定義域在維度上必須一致

### 向量空間、線性轉換與矩陣
令 $F$ 為一個體 (field)，$V$ 與 $W$ 為定義在 $F$ 上的向量空間（$F$-vector spaces）。一個映射 (或函數) $T: V \to W$ 稱為線性轉換 (linear transformation)，若
$$
T(a+b)=T(a)+T(b),\qquad T(c\,a)=c\,T(a)
\quad(\forall a,b\in V,\; c\in F).
$$

為 $V$ 選取一組有序基底 $\mathcal{B}=(v_1, \dots, v_n)$ (因此 $\dim(V)=n$)，並為 $W$ 選取一組有序基底 $\mathcal{C}=(w_1, \dots, w_m)$ (因此 $\dim(W)=m$)。對於 $\mathcal{B}$ 中的每個基底向量 $v_j$，其像 $T(v_j) \in W$ 可唯一表示為 $\mathcal{C}$ 中基底向量的線性組合，即存在唯一的純量係數 $A_{ij} \in F$ 使得：
$$
T(v_j)=\sum_{i=1}^{m}A_{ij}\,w_i.
$$

將這些係數 $A_{ij}$ 組成一個 $m \times n$ 矩陣 $A$ (具有 $m$ 個 row 和 $n$ 個 column)，其中第 $j$ 個 column 的元素即為 $T(v_j)$ 在基底 $\mathcal{C}$ 下的座標向量 $[T(v_j)]_{\mathcal{C}}$：
$$
A=[T]_{\mathcal B}^{\mathcal C}=
\begin{bmatrix}
A_{11}&\dots&A_{1n}\\
\vdots &\ddots&\vdots\\
A_{m1}&\dots&A_{mn}
\end{bmatrix}\in F^{m\times n},
$$

此即線性轉換 $T$ 相對於基底 $\mathcal{B}$ 與 $\mathcal{C}$ 的矩陣表示。此矩陣有 $m$ 個 row (對應 $\dim(W)$) 和 $n$ 個 column (對應 $\dim(V)$)。若 $[x]_{\mathcal{B}} \in F^{n \times 1}$ 代表向量 $x \in V$ 相對於基底 $\mathcal{B}$ 的座標向量 (一個具有 $n$ 個 row 和 $1$ 個 column 的向量)，則有：
$$
[T]_{\mathcal B}^{\mathcal C}[x]_{\mathcal B}=[T(x)]_{\mathcal C}
$$

### 矩陣乘法與轉換合成
現考慮另一線性轉換 $U: W \to Z$，其中 $Z$ 是個 $F$-向量空間，具有有序基底 $\mathcal{D}=(z_1, \dots, z_p)$ (因此 $\dim(Z)=p$)。$U$ 相對於基底 $\mathcal{C}$ 和 $\mathcal{D}$ 的矩陣表示為 $B \in F^{p \times m}$ (具有 $p$ 個 row 和 $m$ 個 column)：
$$
B=[U]_{\mathcal C}^{\mathcal D}\in F^{p\times m}.
$$

這二個線性轉換可進行合成，得到新的線性轉換 $(U \circ T): V \to Z$，其定義為 $(U \circ T)(x) = U(T(x))$。此合成轉換的矩陣表示為 $BA \in F^{p \times n}$ (具有 $p$ 個 row 和 $n$ 個 column)：
$$
[U\circ T]_{\mathcal B}^{\mathcal D}=B\,A\in F^{p\times n},
$$

其中
$$
(BA)_{ij}=\sum_{k=1}^{m}B_{ik}A_{kj}.
$$

此式的求和指標 $k$ 的範圍 (從 $1$ 到 $m$) 極為關鍵：它對應於中間空間 $W$ 的維度。這要求矩陣 $A$ 的 row 數量 ($m = \dim(W)$) 必須等於矩陣 $B$ 的 column 數量 ($m = \dim(W)$)。這正是所謂「內維度必須一致」的要求。對於矩陣乘積 $BA$，$B$ 的 column 數量必須等於 $A$ 的 row 數量。若此條件不滿足（如，若 $B$ 是 $n \times n$，$A$ 是 $m \times m$，則 $B$ 的 $n$ 個 column 必須等於 $A$ 的 $m$ 個 row，即 $n=m$），則對應的線性轉換無法有效「接續」，矩陣乘積也因此失去其作為轉換合成的基礎而無定義。

### 方陣維度不匹配導致的不可乘性

* $A$ 表示 $T_A:V_A\to V_A$ 且 $\dim V_A=m$
* $B$ 表示 $T_B:V_B\to V_B$ 且 $\dim V_B=n$

設方陣 $A \in F^{m \times m}$ (有 $m$ 個 row 及 $m$ 個 column) 代表線性轉換 $T_A: V_A \to V'_A$，其中 $\dim(V_A) = m$ (domain) 且 $\dim(V'_A) = m$ (codomain)。
設方陣 $B \in F^{n \times n}$ (有 $n$ 個 row 及 $n$ 個 column) 代表線性轉換 $T_B: V_B \to V'_B$，其中 $\dim(V_B) = n$ (domain) 且 $\dim(V'_B) = n$ (codomain)。
考慮乘積 $BA$（$B$ 左乘 $A$），這對應於合成轉換 $T_B \circ T_A$。矩陣乘法 $BA$ 要求 $B$ 的 column 數量 ($n$) 等於 $A$ 的 row 數量 ($m$)。因此，必須 $n=m$。
然而根據題目的設定，$m \neq n$，此條件不滿足。從線性轉換角度看， $T_A$ 的對應域 $V'_A$ 維度為 $m$，而 $T_B$ 的定義域 $V_B$ 維度為 $n$。因為 $m \neq n$，所以 $T_A$ 的輸出空間維度與 $T_B$ 的輸入空間維度不一致，導致合成 $T_B \circ T_A$ 無法定義，而矩陣乘積 $BA$ 亦無定義。

從幾何直觀來看，一個 $m \times m$ 的方陣 $A$ 可視為對 $m$ 維空間中的 $m$ 維「體積」(或更一般的測度) 進行的變換，而 $n \times n$ 的方陣 $B$ 作用於 $n$ 維空間。若 $m \neq n$，則一個轉換輸出的 $m$-維 (或 $n$-維) 幾何標的，無法直接作為另一個轉換作用於不同維度空間的合法輸入，因為它們的維度基礎根本不同，乘法運算因此失去幾何上的可解釋性。

### 範例：$\mathbb R^{2}\to\mathbb R^{3}$
考慮
$$
T:\mathbb R^{2}\to\mathbb R^{3},\quad T(a_1,a_2)=(a_1+3a_2,\;0,\;2a_1-4a_2).
$$

相對於 $\mathbb{R}^2$ 和 $\mathbb{R}^3$ 的標準有序基底，此轉換 $T$ 的矩陣表示為一個 $3 \times 2$ 矩陣 (3 個 row 及 2 個 column)：
$$
[T]_{\mathrm{std}}=
\begin{bmatrix}
1&3\\
0&0\\
2&-4
\end{bmatrix}_{3\times2}.
$$

若取向量 $x = (1, -1)^T \in \mathbb{R}^2$ (其標準座標向量為一個 $2 \times 1$ column vector $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$)，則其像 $T(x)$ 的標準座標向量為一個 $3 \times 1$ 向量：
$$
[T]_{\mathrm{std}}x=
\begin{bmatrix}
-2\\0\\6
\end{bmatrix}\in\mathbb R^{3}.
$$

若另有一方陣 $C \in F^{3 \times 3}$ (3 個 rows 及 3 個column)（代表某 $U: \mathbb{R}^3 \to \mathbb{R}^3$），則乘積 $C [T]_{\mathrm{std}}$ 是合法的（因為 $C$ 的 column 數量 (即 3) 等於 $[T]_{\mathrm{std}}$ 的 row 數量 (即 3)），結果是個 $3 \times 2$ 矩陣（代表 $U \circ T: \mathbb{R}^2 \to \mathbb{R}^3$）。然而，乘積 $[T]_{\mathrm{std}} C$ 則無法定義，因為 $[T]_{\mathrm{std}}$ 的 column 數量 (即 2) 與 $C$ 的 row 數量 (即 3) 不匹配。

### 行列式與方陣特性
對於一個 $n \times n$ 的方陣 $M$，其行列式 $\det(M) = 0$ 的重要推論是矩陣的秩 $\operatorname{rank}(M) < n$。這意味著 $M$ 的向量線性相依，無法張成整個 $n$ 維空間。因此，由 $M$ 代表的線性轉換 $T_M: F^n \to F^n$ 不是一個同構 (isomorphism)，故矩陣 $M$ 不可逆。關於行列式的乘法定理：
$$
\det(BA)=\det B\,\det A
$$

此定理僅在 $A, B$ 均為相同大小的 $n \times n$ 方陣時（即它們可相乘形成另一個 $n \times n$ 方陣）成立。它在幾何上可解釋為：依次施加二個線性轉換（先 $A$ 後 $B$）所造成的總 $n$ 維體積縮放比例，等於各自轉換的體積縮放比例之積。

### 小結
矩陣乘法的維度匹配規則並非任意設定，而是反映線性轉換能否進行有效合成的根本條件：乘積 $BA$ 要求 $B$ 的 column 數量等於 $A$ 的 row 數量。當二個方陣的維度不同時（如 $A$ 為 $m \times m$，$B$ 為 $n \times n$，且 $m \neq n$），此匹配條件無法同時對 $BA$ 和 $AB$ 滿足。這意味著它們所代表的線性轉換作用於維度相異的向量空間，導致在嘗試合成這些轉換時，前一轉換的對應域維度與後一轉換的定義域維度無法匹配，使得函數合成在邏輯上不可行。因此，其對應的矩陣乘積也自然失去數學上的意義。

參考資料
* [Linear Algebra 4/e](https://www.amazon.com/Linear-Algebra-4th-Stephen-Friedberg/dp/0130084514)
* [The determinant | Chapter 6, Essence of linear algebra](https://www.youtube.com/watch?v=Ip3X9LOh2dk)

---

## [sched\_ext](https://github.com/sched-ext/scx) (簡稱 scx)
> EricccTaiwan / charliechiou

1. [討論紀錄](https://hackmd.io/@cce-underdogs/meet_jserv)
2. [環境架設](https://hackmd.io/EEKDV97aRFKCaJbCsz6UJg): sched_ext 針對 Linux v6.12+
3. [FIFO/RR scheduler](https://hackmd.io/nXputIWIRCuGpXtiwTN2ug): 實作 FIFO/RR 排程器

> I'm also not a believer in the argument that has been used (multiple times) that the BPF scheduler would keep people from participating in scheduler development. -- Linus Torvalds on [11 Jun 2024](https://lore.kernel.org/bpf/CAHk-=[e-mail]/)

$\to$ Linus Torvalds 反駁以 eBPF 開發 CPU 排程器會阻礙社群參與的觀點。真正的挑戰在於開發者的能力與學習意願及 CPU 排程設計的複雜程度，至於技術選擇 (如 eBPF) 的影響則相對次要。

Linux v6.12 引入的 sched_ext (scx) 允許開發者藉由 eBPF，在使用者空間動態載入或抽換 CPU 排程器。本議程嘗試結合機器學習，利用 BPF map 彙整 CPU 排程相關事件資料，依據推論動態調整 time slice、CPU affinity 與 task migration。

從客製化的 FIFO/RR 排程器到機器學習，並引入負載預測機制。


- 觀察右半部，各 CPU 頻率不同。因此就算執行同一個指令在不同的 CPU 跑所需時間會不同。

Combination logic 輸入啥就輸出啥，沒有記憶功能。
Sequential logic 會紀錄過去的結果，有時序關係。

降頻除了會影響時間也會影響到 propagation delay ， CPU 會需要更多時間來達到穩態。

---

## Andrushika

### 用 fixed point 計算 EWMA
在 [include/linux/average.h](https://github.com/torvalds/linux/blob/0d8d44db295ccad20052d6301ef49ff01fb8ae2d/include/linux/average.h) 下，有定義 EWMA 的 macro。呼叫者可自行定義精度、weight 等等。

因為 PELT 的計算涉及自然對數，所以會用到浮點數；為了符合 linux kernel 不使用浮點數的限制，改用定點數。然而，在查閱原始程式碼 [kernel/sched/pelt.c](https://github.com/torvalds/linux/blob/0d8d44db295ccad20052d6301ef49ff01fb8ae2d/kernel/sched/pelt.c#L31) 時，我發現它並沒有使用 `average.h` 裡面所定義的 EWMA，而是另外實作了查表法：

static u64 decay_load(u64 val, u64 n)
{
	unsigned int local_n;

	if (unlikely(n > LOAD_AVG_PERIOD * 63))
		return 0;

	/* after bounds checking we can collapse to 32-bit */
	local_n = n;

	/*
	 * As y^PERIOD = 1/2, we can combine
	 *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
	 * With a look-up table which covers y^n (n<PERIOD)
	 *
	 * To achieve constant time decay_load.
	 */
	if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
		val >>= local_n / LOAD_AVG_PERIOD;
		local_n %= LOAD_AVG_PERIOD;
	}

        // 計算完畢後向右位移 32 bits，可知 static factor 為 32
	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
	return val;
}

此實作中定點數的 scaling factor 選擇使用 32，代表誤差可以縮小到 $2^{-32}$ 以內。但開發者為何這樣選，我目前找不到原因。 (用 Q23.8 可以嗎？)

$\to$ PELT 機制與負載衰減計算採用的定點數表示法
Linux 核心在 CFS 排程器中導入 PELT 來量化各個排程實體 (scheduling entity) 的「可執行負載」，自 Linux v6.6 起改用 EEVDF 排程策略後，PELT 仍是統計與公平分配的基礎，並延伸到 [schedutil](https://docs.kernel.org/scheduler/schedutil.html) 和[CPUIdle](https://docs.kernel.org/driver-api/pm/cpuidle.html) 等子系統。

PELT 的所有負載欄位（`load_avg`, `runnable_load_avg`, `util_avg` 等，通常定義在 `struct sched_avg` 結構體內）均以定點數 (fixed-point number) 形式存儲於整數類型變數內。其數值是將真實負載值乘以一個固定的放大係數 (scaling factor)，該係數定義為：
$$
\text{scale} = 1 \ll \text{LOAD_AVG_SHIFT}
$$

目前 `LOAD_AVG_SHIFT` 設為 `10` (過往或特定核心組態中，可能為 `11`），因此放大係數為：
$$
\text{scale}=2^{10}=1024
$$

意即「單核處理器完全被佔用」的理想化負載值，在 PELT 內部表示為 1024 個單位。如此可在純整數運算下取得約 $1/1024\approx0.1\%$ 的解析度 (granularity)，足以描述 CPU 時間片的細微變化，又可避免使用浮點數。若日後演算法需要更精細的解析度，只要調整 `LOAD_AVG_SHIFT` 即可套用，程式碼本身無須改動。

$\to$負載衰減 (`decay_load`) 的分段計算策略
PELT 將半衰期常數 `LOAD_AVG_PERIOD` 設為 32 個取樣週期 (常見設定每週期 1 ms)，並令單位週期的衰減因子 $y$ 使得 $y^{32}\approx\frac12$。因此，經過 $n$ 個週期的總衰減可拆解為
$$
\begin{aligned}
y^{n}
&= \bigl(y^{\text{LOAD_AVG_PERIOD}}\bigr)^{\lfloor n/\text{LOAD_AVG_PERIOD}\rfloor}\,
y^{\,n\bmod\text{LOAD_AVG_PERIOD}} \\[4pt]
&\approx
\bigl(\tfrac12\bigr)^{\lfloor n/32\rfloor}\,
y^{\,n\bmod 32}
\end{aligned}
$$

在 `decay_load()` 內:

val >>= local_n / LOAD_AVG_PERIOD;

相當於乘上 $(\frac{1}{2})^{\lfloor n/32\rfloor}$，以位移方式近似整數個半衰期的衰減。

接著再乘表格常數

val = mul_u64_u32_shr(val,
                      runnable_avg_yN_inv[local_n % LOAD_AVG_PERIOD],
                      32);

該表格 `runnable_avg_yN_inv[k]` 儲存 $y^{k}$（$0\le k<32$）的 Q0.32 定點值：
$$
Y_{\text{tbl}}
= \Bigl\lfloor y^{k}\cdot2^{32}\Bigr\rfloor
$$

巨集 `mul_u64_u32_shr(a,b,32)` 完成

((u128)a * b) >> 32

* `val` 原為 Q$_{X}$.`LOAD_AVG_SHIFT`（目前 `LOAD_AVG_SHIFT` = 10）
* 乘上 Q0.32 之後，小數位變為 `LOAD_AVG_SHIFT + 32`
* 再右移 32 位，將格式恢復成原先的 Q$_{X}$.`LOAD_AVG_SHIFT`，僅「消化」乘數帶來的 32 位小數精度。 :warning: 不意謂 `val` 本身使用 32 位元小數

如此即可在 $O(1)$ 時間完成任意 $n$ 的衰減，同時保持與全域負載欄位一致的定點格式與精度。

$\to$ 32 位元小數查表因子的設計考量
* 精度: 衰減因子 $y$ 極接近 1；以 $\Delta t = 1\ \text{ms}$, $t_{1/2}=32\ \text{ms}$ 為例，$y \approx (1/2)^{1/32}\approx0.9785$。對 $k\le31$ 的冪而言，$y^k$ 間差異微小但累積效果顯著 ($y^{31}\approx0.507$)。若僅用 8 位元小數 (解析度 $2^{-8}\approx0.0039$) 表示，量化誤差會在連乘中放大。
* 採 Q0.32 格式 (解析度$2^{-32}\approx2.3\times10^{-10}$) 即可讓衰減曲線幾乎與理論值重合，誤差可忽略
* 記憶體與執行效率: 32 個 `u32` 表格僅佔 128 個位元組，穩定駐留 L1 快取。`mul_u64_u32_shr` 把 64×32 位元整數乘法與右移合併，在 64 位元處理器通常對應 2–3 道指令，延遲固定。相較通用 EWMA 巨集需迴圈與多次加／移，查表法更快且時間可預測
* 熱點最佳化: PELT 更新在每次 scheduler tick 或`update_rq_clock()` 後執行，屬於核心最熱路徑。專用查表省去條件分支與除法，顯著降低 CPU 排程器自身開銷，維持延遲與能耗的穩定性

$\to$ 為何不直接使用 `average.h` 的 EWMA 巨集？
`DECLARE_EWMA()` 屬於通用寫法：固定右移位數，再於每次更新時進行乘法與加法。PELT 的情境則有下列特點與需求，專用實作具備以下優勢：
* 半衰期已鎖定為 32 個取樣單位，可拆成「整數右移一次」加「查表常數乘法一次」，運算路徑最短
* 每次遞減的 $n$ 不一定是 1；排程器在 idle-balance 或 [CPU hot-plug](https://docs.kernel.org/core-api/cpu_hotplug.html) 回復時，可能需要一次衰減多個 tick。查表法仍能在 $O(1)$ 時間處理任意 $n$
* PELT 同時追蹤多個欄位 (load, util, runnable, `sleep_avg` 等)，專用函式共用同一套運算路徑，能確保所有統計值的定點格式與精度保持一致

$\to$ 誤差來源與界限:
* 表格量化誤差小於 $2^{-32}$
* 每次衰減後，核心透過 `round_clamp()`（或位移捨入）維持整數格式，最多引入 $\pm\frac12$ 個最小單位（即 $\pm2^{-11}$）
* 長期累積的偏差僅來自離散化與量化，可視為隨機誤差相加；對負載平衡與容量預估的閉環控制影響遠低於 CPU 排程本身的抖動。

相關實作細節:
* PELT 數值在 `struct cfs_rq` 與 `struct sched_entity` 之間逐層傳遞，最終經 `scale_load_down()` 還原為實際 CPU 百分比
* 啟用 CPUFreq 的 schedutil governor 時，`util_avg` 透過 `sched_cpu_util()` 直接驅動 DVFS；32 位元乘子確保在臨界點依然具備足夠解析度，避免電壓／頻率振盪
* cgroup v2 的 `cpu.weight` 藉由`propagate_entity_load_avg()` 對各層 runnable 負載加權，所有層級共用同一定點基底，省去額外轉換成本
* 在 [NO-HZ Full](https://docs.kernel.org/timers/no_hz.html)（模式下，遠端 CPU 可能長時間不觸發排程器；`decay_load()` 的批次衰減避免統計值過期，維持整個系統的 fairness

### Linux 核心原始程式碼中還有哪裡會用到 EWMA？
關於 EWMA 的更多應用，在 `mm/ksm.c` 下，可以看見其的身影。KSM 全名為 Kernel Samepage Merging，以下為 [LWN.net](https://lwn.net/Articles/330589/) 上的相關說明：
> The kernel generally goes out of its way to share identical memory pages between processes. Program text is always shared, for example. But writable pages will also be shared between processes when the kernel knows that the contents of the memory are the same for all processes involved. When a process calls fork(), all writable pages are turned into copy-on-write (COW) pages and shared between the parent and child. As long as neither process modified the contents of any given page, that sharing can continue, with a corresponding reduction in memory use.

也就是說，如果多個記憶體頁面內容完全相同，就可以讓它們共用同一份實體記憶體的 page，並將原本的 page 標記為 copy on write。
而上方提到的 `ksm.c` 會運行一個 daemon，持續掃描可以合併的 page。
這樣就出現一個問題：掃描的頻率應該如何決定？太頻繁的話會過度占用系統資源，太少的話沒辦法最大程度節省記憶體的使用。
在 `ksm.c` 中，有一個函式 [scan_time_advisor()](https://github.com/torvalds/linux/blob/01f95500a162fca88cefab9ed64ceded5afabc12/mm/ksm.c#L402) 專門用來計算最佳的掃描時間間隔，實際掃描使用的時間應該貼近所設定的 `target_time`。且為了避免掃描速度的波動，此處就使用了 EWMA 做調整：

/* Calculate scan time as percentage of target scan time */
factor = ksm_advisor_target_scan_time * 100 / scan_time;
factor = factor ? factor : 1;

/*
 * Calculate scan time as percentage of last scan time and use
 * exponentially weighted average to smooth it
 */
change = scan_time * 100 / last_scan_time;
change = change ? change : 1;
change = ewma(advisor_ctx.change, change);

/* Calculate new scan rate based on target scan rate. */
pages = ksm_thread_pages_to_scan * 100 / factor;
/* Update pages_to_scan by weighted change percentage. */
pages = pages * change / 100;

此外，在 `drivers/net/virtio_net.c` 之下也可以看到 EWMA，其用途是動態調整 RX packet buffer 的大小。

### EWMA 的衰變因子 k 要怎麼選？
衰變因子的選擇是在「保留歷史記憶的能力」以及「對於新決策的敏感度」間做取捨，需要根據需求選擇。以老師上課所提到的 PELT 為例，選用 32 ms 為半衰期，因為其較關注「最近的歷史」，太久以前的負載值資料對其影響不大。

在 PELT 中，k 的選用是先決定了半衰期，才去回推時間常數。
已知 $k = e^{-t/\tau}$，再複習一次 EWMA 定義：
$$
u_{n} = k \cdot u_{n-1} + (1-k) \cdot r_{n}
$$
由遞迴式可知 $u_{n}$ 會對之後的估算值造成影響。假設系統的更新 ticks 是 1 ms，我想讓 $u_{n}$ 在 32 ms 過後 (剛好是 32 次更新) 的影響力只剩下一半，可以列式：
$$
k^{32} = (e^{-1/\tau})^{32} = 1/2
$$
回推時間常數可得：
$$
\tau = \frac{-32}{ln(\frac{1}{2})} = 46.167
$$

---

### ?
半衰期對於 Task migration 的影響是什麼？
* 螢幕更新率

### rota1001
假設打開網站，網站使用 Cookie，為什麼需要 cookie
* 不用每次都輸入密碼。

有可能會有三種狀況
1. 亂填數值
2. 有人不小心寫錯
3. 填入的數值過時了

### yy214123
分享 [jserv ttt #43](https://github.com/jserv/ttt/pull/43) 此貢獻過程中的心得。

- 要用數字說服人 -> 所以實驗是必要的，不能只基於理論提出。
- cache misses rate 僅能參考，以這次的案例來說，雖改善後的 cache misses rate 上升，但實際上 Cache misses 減少了約 30 %、Cache references 減少了約 40%。