# 2024-04-16 問答簡記
> 檢討[第五次作業](https://hackmd.io/@sysprog/linux2024-homework5)

## williamS
> [第五次作業](https://hackmd.io/@imNCNUwilliam/linux2024-homework5)
* EWMA 在 Linux Kernel 中哪邊有用到呢？
* 可做 CPU sched 的 estimated utilization。

## weihsinyeh
> [第五次作業](https://hackmd.io/@weihsinyeh/linux2024-homework5)
* weakly-ordered V.S. strongly-ordered
* 當 CPU 速度比 Main Memory 快上許多時，在硬體架構設計上，cache 設計讓 CPU load / store 省去每次存取 Main Memory 的成本，但還是受限於 instructions 的 execution orders。
* store buffer暫存 CPU store 指令，讓 CPU 不須等待 store instruction 完成即可進行下個 instruction ，==(帶來什麼優點呢？)== 允許 CPU 處理指令可不受限於 execution orders 。然而，在多核處理器系統中，需要處理 Cache Coherence 的問題。所以，還多了廣播給不同 CPU core 上的 cache 以及等待其他 CPU cache 完成對應 cacheline update 的 overhead。
* invalidate buffer 就沒有聽清楚了。
* rdtsc V.S. C STL gettime()
* C STL gettime() 量測精準度到 microsecond 等級，執行多次取平均又可能會涵蓋其他不易觀察的 operations，例如：timer interrupt。
* about magic number ==0xbfff978== ？
* debug Linux Kernel 的方式。
* 西元 2000 年時, 虛擬化 Virtualization 技術還未成熟，需要多一台機器，透過特殊的 cable 來連接要觀察的 Linux 系統。
* 後來可透過在 Linux Kernel 預先註冊 Exception Handler 來觀察特定事件被觸發時的 CPU 狀態。
* ...

## david965154
fork 仍需要時間成本，尤其是在遞迴期間才做 fork ，因此會不斷的進行 fork 直到 fork_count 到達設定值或者 partition 結束。不過剛剛有看到若設定值過大，執行時間會變很長的同時還會導致排序錯誤，但為什麼會導致排序錯誤 ?

invoke mmap(2) to share among forked processes.
sudo sysctl -w kernel.sched_child_runs_first=1，以便要求 Linux 排程器 (CFS) 讓 child process 優先於 parent process 執行

改進 concurrent (fork) merge sort:
1. 避免遞迴，降低 fork 的成本
2. 預先 fork (pre-forking)
3. 實作 workqueue // 參見 案例: Thread Pool 實作和改進

### millaker

ioctl
demand paging
page size: 4KB (trade-off)
Arm64: 4KB, 16KB, 64KB
CS:APP Chapter 9 (virtual memory)
https://docs.kernel.org/admin-guide/mm/hugetlbpage.html (HugeTLB)

KPTI dramatically increased this cost: directly, by switching the active page table at each context transition
=> ESCA: Effective System Call Aggregation for Event-Driven Servers

## jouae
> "The purpose of computing is insight, not numbers." by Richard Hamming, Numerical Methods for Scientists and Engineers (1962).

[第 9 週測驗](https://hackmd.io/@sysprog/linux2024-quiz9) 中提及的矩陣乘法，為何不同大小的方陣不能相乘？簡單歸納兩個結論：

* 矩陣表示式是根據線性轉換而來
* 矩陣相乘是線性轉換間的合成

線性代數(linear algebra) 字面意思是在討論**線性**性質與**代數**結構，與一般工程數學或是工程學中的線性代數不同，數學系相關的線性代數出發點是**向量空間(vector space)**，所謂向量空間其實就是代數中的體(field)的延伸，對於一個體$(F,+,\times)$ 與一個集合 $V$ 會滿足[十個公理](https://en.wikipedia.org/wiki/Vector_space#Definition_and_basic_properties)。

從向量空間開始接續會討論到線性相依、線性獨立、基底，再來到**線性**這個性質
* 對兩個體為 $F$ 的向量空間 $V,W$ ，函數 $T:V_1\rightarrow V_2$ 為線性轉換，對所有係數 $c\in F$ 和 $a,b\in V$ 滿足以下特性：
* 加法線性： $T(a+b)=T(a)+T(b)$
* 係數乘法： $T(ca)=cT(a)$

線性組合、基底等等這些概念都是息息相關。由有序基底 $\beta=\lbrace v_1,v_2,\dots,v_n\rbrace$ 生成的向量空間 $V$ ，藉由係數 $a_1,a_2,\dots,a_n$ 對基底元素的線性組合，組合出任意向量 $x\in V$ 表示為
$$
x = \sum^n_{i=1} a_iv_i
$$
且每個係數皆唯一。

而以 $\beta$ 為基底的 $x$ 座標向量表示為
$$
[x]_{\beta}=
\begin{bmatrix}
a_1 \\
a_2 \\
\vdots \\
a_n
\end{bmatrix}
$$

讓向量空間 $V$ 的有序基底為 $\beta=\lbrace v_1,v_2,\dots,v_n \rbrace$ 和向量空間 $W$ 的有序基底為 $\gamma=\lbrace w_1,w_2,\dots,w_m \rbrace$ ，以及一線性轉換 $T:T \rightarrow W$ 則對 $1\leq j\leq n$ 存在唯一係數 $a_{ij}\in F$ 對 $1\leq i \leq m$ 使得
$$
T(v_i) = \sum^m_{i=1}a_{ij}w_i,\quad \text{for }1\leq i \leq n.
$$

* 藉由上述的表示法，可以得到一藉由基底 $\beta$ 和 $\gamma$ 線性轉換 $T$ 的矩陣表示式 $A=[T]_{\beta}^{\gamma}$

舉[書本 p.81 例子 3](https://www.tenlong.com.tw/products/9781292026503)，對線性轉換 $T:\mathbb{R}^2\rightarrow \mathbb{R}^3$
$$
T(a_1,a_2) = (a_1+3a_2,0,2a_1-4a_2).
$$
讓 $\beta$ 和 $\gamma$ 為標準有序基底。則 $T$ 由基底 $\beta$ 和基底 $\gamma$ 構成的矩陣表示法為
$$
T(1,0) = 1e_1+0e_2+3e_3,\quad T(0,1)=3e_1+0e_2-4e_3
$$
$$
[T]_{\beta}^{\gamma} =
\begin{bmatrix}
1 & 3 \\
0 & 0 \\
3 & -4
\end{bmatrix}
$$

如果把有序基底的順序改一下變成 $\gamma'=\lbrace e_3,e_1,e_2\rbrace$ 則矩陣表示法為
$$
[T]_{\beta}^{\gamma'} =
\begin{bmatrix}
3 & -4\\
1 & 3 \\
0 & 0
\end{bmatrix}
$$
再來探討下矩陣乘向量這個操作的數學含意。令 $x=(1,-1)^T$ 則
$$
[T]_{\beta}^{\gamma}x =
1\begin{bmatrix}
1 \\
0 \\
3
\end{bmatrix}
-1
\begin{bmatrix}
3 \\
0 \\
-4
\end{bmatrix}=
\begin{bmatrix}
2 \\
0 \\
7
\end{bmatrix}
$$
可以看到 $[T]_{\beta}^{\gamma}$ 的行向量，藉由 $x$ 中的元素為係數做線性組合。

回到線性轉換以函數觀點來思考
$$
T(1,-1)=T(1,0)-T(0,1)= (1e_1+0e_2+3e_3)-(3e_1+0e_2-4e_3)
$$
其實就是先將基底 $\beta$ 中的元素線性組合出 $x$ 後以線性轉換得到函數映射至 $\mathbb{R}^3$ 基底元素的線性組合。

總結就是**矩陣是線性轉換的有序基底間的映射關係**，而矩陣乘向量是**將一空間的座標向量映射至另一個空間的座標向量**

接續討論矩陣乘矩陣是什麼？先講結論矩陣乘矩陣代表線性轉換的合成，**也因為是函數合成，除非特定情況下矩陣相乘不滿足交換律**。

* 令 $T:V\rightarrow W$ 和 $U:W\rightarrow Z$ 為線性轉換，其中 $UT:V\rightarrow Z$ 也為線性轉換。讓 $\alpha=\lbrace v_1, v_2, \dots, v_n\rbrace$ 、 $\beta=\lbrace w_1,w_2,\dots, w_m\rbrace$ 和 $\gamma=\lbrace z_1, z_2,\dots,z_p\rbrace$ 為向量空間 $V,W$ 和 $Z$ 各自的有序基底且矩陣表示式為 $A=[T]^{\beta}_{\alpha}$ 和 $B=[U]_{\beta}^{\gamma}$。則 $AB=[UT]_{\alpha}^{\gamma}$ 對 $1\leq j\leq n$
$$
\begin{align}
(UT)(v_j)
&= U(T(v_j))= U\left(\sum^m_{k=1}B_{kj}w_k\right) \\
&= \sum^m_{k=1}B_{kj}U(w_k) = \sum^m_{k=1}B_{kj}\left(\sum^p_{i=1}A_{ik}z_i\right) \\
&= \sum^p_{i=1} \left(\sum^m_{k=1} A_{ik}B_{kj}\right)z_i = \sum^p_{i=1}C_{ij}z_i.
\end{align}
$$

其中 $C=AB$ 為矩陣相乘的結果，也是線性轉換 $UT$ 的矩陣表示式。至此我們可以瞭解矩陣乘矩陣和線性轉換合成之間的關聯。

而關於行列式的部分，強烈建議看看 [行列式 | 線性代數的本質 第五章 by 3Blue1Brown](https://www.youtube.com/watch?v=Ip3X9LOh2dk) 從幾何座標的角度講解 $2\times 2$ 和 $3\times 3$ 行列式值在幾何上的意義。

其中很重要的一個部分 $\text{det}(A)=0$ 也就是矩陣 $A$ 中的行或列向量並非線性獨立，這告訴我們矩陣的 $\text{rank}(A)\neq \text{dim}(A)$。**換言之 $A$ 並非以有序基底映射的矩陣表示式，也因為並非基底所以無法生成(span)原本線性轉換定義域的全空間。**

在[影片 3:05 處](https://youtu.be/Ip3X9LOh2dk?si=VMF4wPOp61wkgfLp&t=185) 可以看到兩向量張開的面積被壓縮成一條線，就是在告訴我們這個矩陣中的行或是列向量有線性相依的情況，無法生成原本的全空間，並非一組基底形成的矩陣表示式。

最後討論下影片最後的問題：
行列式 $\text{det}(AB)$ 與 $\text{det} (A)$ 和 $\text{det} (B)$ 的關係，其中 $\text{det} (A)$ 和 $\text{det} (B)$ 不為零，且 $A$ 和 $B$ 為大小相同的方陣可以寫成
$$
\text{det}(AB)=\text{det} (A)\text{det} (B)
$$
從計算可以證明這件事情，但從線性轉換跟幾何的角度思考，這件事情解釋起來就很簡單。由於皆為方陣，定義域和對應域的向量空間大小皆相同，$AB=[UT]_{\alpha}^{\gamma}$ 以線性轉換角度來看只是把一個有序基底 $\alpha$ 換成另一個有序基底 $\gamma$。將上述行列式的等號改以基底變換呈現為
$$
\text{det}([UT]_{\alpha}^{\gamma})=\text{det} ([T]^{\beta}_{\alpha})\text{det} ([U]_{\beta}^{\gamma})
$$
等式右邊 $\text{det} ([T]^{\beta}_{\alpha})$ 是將面/體積從有序基底 $\alpha$ 映射至 $\beta$ 伸縮的係數，同理 $\text{det} ([T]^{\gamma}_{\beta})$。則兩個行列式相乘的過程就是，從 $\alpha$ 映射至 $\beta$ 做一次伸縮後得到的面/體積變化係數，乘上以基底 $\beta$ 為坐標系做一次映射至 $\gamma$ 坐標系的面/體積變化係數。

- [ ] 參考資料
* [Linear Algebra S. Friedberg A. Insel L. Spence Fourth Edition](https://www.tenlong.com.tw/products/9781292026503)
* [行列式 | 線性代數的本質 第五章 by 3Blue1Brown](https://www.youtube.com/watch?v=Ip3X9LOh2dk)