# 2026q1 Homework1 (warmup)
contributed by < wyattsheu >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 探討〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉
* "render" 在電腦圖學語境中為何應強調「如實呈現」？「渲染」一詞喪失什麼關鍵意涵？在 Linux 核心原始程式碼中，"render" 出現在哪些場景、語境又有哪些？翻閱詞典 (善用學校圖書館) 並考據詞源
* 說明 constant 與 immutable 的差異，並探討程式設計中的關鍵考量
* 比較 concurrent 與 parallel 的語意差異，並說明為何「並行」較貼近 concurrent 的本意
* 當我們撰寫 Linux 核心文件，應如何區分 process, thread, task, job 等術語，才能避免跨領域誤解又省去過多的中英並陳？
## 細讀〈[GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/)〉
* 確保 Linux 系統已正確安裝，且每天使用 (對比: 在游泳課買泳裝並下水)
* 學習 HackMD 的操作，並可正確使用 LaTeX。能夠在 HackMD 筆記中用 LaTeX 語法展現波函數和密度矩陣
* 學習 git 的操作，依據給定的教學錄影實際練習，並知曉 `git rebase` 一類命令的操作
## 探討〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉
* 為何計算機的加法在固定 $k$ 位元下，本質等價於 $\mathbb{Z}/2^k\mathbb{Z}$ 上的加法？
* 答：
若在 $k$ 位元下，只能表示 $2^k$ 種狀態。當加法運算結果超過 $2^k - 1$ 時，硬體電路會因為位元長度限制，捨棄最高的進位位元（即第 $k+1$ 位元），可以看成除以 $2^k$ 取餘數。所以本質等價於 $\mathbb{Z}/2^k\mathbb{Z}$ 上的加法。
其中：$\mathbb{Z}/2^k\mathbb{Z}$代表所有整數在模 $2^k$ 下的餘數集合
* 為何「允許溢位」反而保證封閉性？若不允許溢位，會破壞哪些群的性質？
* 答：若不允許溢位，會破壞阿貝爾群的性質：封閉性，因為「封閉性」要求運算結果必須存在於同一集合內，而允許溢位使得集合內的數列能夠成為一個首尾相連的圓環，滿足封閉性。
* 在質數模數 $p$ 下，可用 $a^{-1} \equiv a^{p-2} \pmod p$ 計算反元素，解釋該式如何來自有限群理論，並說明為何此性質僅在「非零元素形成群」時成立。從 Linux 核心實作角度分析: 1) 為何必須確保輸入元素為單位？2) 若傳入零因子會造成什麼風險？
* 答：
* 為何 $x \mod 2^n \equiv x \mod (2^n - 1)$ 僅對 unsigned 或非負整數安全？從 CVE/CWE 找到相關資訊安全的議題
* 為何 sign extension 僅在「跨圓環」搬移時才有意義？從數學觀點解釋，要一般化相關證明
* 為何 Linux 核心中 unsigned overflow 是 defined behavior，但 signed overflow 是 undefined behavior？
* 為何 Linux 核心大量使用 unsigned long 作為時間計數器？
* 若模數改為質數 $p$，是否可構成有限域？這和 AES 中 $GF(2^8)$ 有何關聯？
* 二補數構成環但非域，這對除法有何限制？找出 Linux 核心原始程式碼對應的案例
* 二補數的設計是否本質上是種 algebraic encoding？
* 若將系統時間設計於 $\mathbb{Z}/2^{64}$ 上，其安全極限為何？
* 證明 $(\mathbb{Z}/2^k\mathbb{Z}, +)$ 為阿貝爾群，但 $(\mathbb{Z}/2^k\mathbb{Z}, \times)$ 非群
## 探討〈[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉
* 根據 C99 對 object 的定義，請分析以下程式是否具有未定義行為，並說明理由 `int *foo(void) { int x = 10; return &x; }`
1. 若改成 `static int x = 10;` 結果是否改變？
2. 請用「storage duration」與「lifetime」兩個術語解釋差異。
3. 為何規格明確指出：
> The value of a pointer becomes indeterminate when the object it points to reaches the end of its lifetime.
* 以下程式的輸出為何？ `int a[3] = {1,2,3}; int *p = a; printf("%zu %zu\n", sizeof(a), sizeof(p));`
1. 為何 array 在 expression 中會 decay 成 pointer，但在 sizeof 中不會？
2. 為何 `&a` 與 `a` 的值相同但型態不同？
3. 用 Graphviz 繪製記憶體示意圖說明以上
* 分析： `double x[3]; int *p = (int *)&x[0]; printf("%d\n", *(p+1));`
1. 為何 pointer arithmetic 的單位取決於 type？
2. 這是否涉及 strict aliasing 問題？
3. 在 ARMv5 或 RISC-V 上可能出現什麼錯誤？
* 解釋為何以下程式不會改變 main 中的 ptrA： `void func(int *p) { p = &B; }` 並分析 `void func(int **p) { *p = &B; }`
1. 用 call-by-value 解釋
2. 用 Graphviz 繪製 stack frame 示意圖
3. 為何「雙指標」這個說法在語意上不精確？
* 解釋為何以下程式合法： `int main() { return (********puts)("Hello"); }`
1. 依據 C99 6.3.2.1 說明 function designator 的轉換規則。
2. 為何 `*` 的數量不影響結果？
3. 若對 function pointer 使用 `&` 會發生什麼？
* 從「儲存-執行模型」角度解釋 `int a = 10; char *p = (char *)&a;`
1. CPU 實際做哪些事？
2. 為何 C 語言可以被視為 assembly 的語法抽象？
* 考慮以下程式碼:
```c
struct opaque;
struct opaque *create(void);
void destroy(struct opaque *);
```
1. 為何可以只 forward declaration？
2. 這如何達成 binary compatibility？
3. 為何 incomplete type 只能搭配 pointer？
* 舉出一個程式碼案例，使得以下得以滿足，並用 C99 對 lifetime 的定義精確解釋
* object lifetime 結束
* storage 尚未被重用
* pointer 仍保留原數值
* 但 dereference 屬於 UB
* 以下程式在 -O2 下可能輸出什麼？
```c
float f = 1.0f;
int *p = (int *)&f;
*p = 0;
printf("%f\n", f);
```
分析：
1. 是否違反 strict aliasing？
2. 若使用 `memcpy` 是否等價？
3. 為何 C 規格允許 `unsigned char *` 例外？
4. 在不同架構下是否行為不同？
* 為何以下二者 ABI 不同？
```c
void f(int a[10]);
void f(int *a);
```
比較：
```c
void g(int (*a)[10]);
```
回答：
1. 為何 `sizeof` 結果不同？
2. 為何 `&a` 與 `a` 型別差異重大？
3. 若跨編譯單元宣告不一致會發生什麼？
## 探討〈[linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉
* 從〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉的角度，探討何以 linked list 翻譯為「鏈結串列」，而非「鏈表」或「連結串列」，而「串列」的詞源又在哪？翻閱詞典和二十世紀出版物來解說
* 教材中使用 `struct ListNode **indir = &head;`，描述以下:
1. `indir` 的型別語意
2. `*indir` 的語意
3. `&(*indir)->next` 的語意
並說明為何這不是「雙指標」，而是「指標的指標」
* 考慮 `prev->next = (*indir)->next; free(*indir);`，分析：
1. `*indir` 在哪一行失去 lifetime？
2. 若先 `free` 再改鏈結會發生什麼？
3. 為何 AddressSanitizer 能偵測？
4. 若在 `-O3` 下編譯器是否可能出現指令的 reorder？
* 為何針對鏈結串列的節點走訪 (linked list traversal) 難以被 hardware prefetcher 預測？若使用 `__builtin_prefetch(node->next);` 是否一定改善效能？請記憶體存取圖形角度解釋，並從 git log 探討 Linux 核心的 List API 一度採用 prefetcher 又棄置的考量。
* 針對 Linux 的 merge sort 設計，回答
1. 為何 list_sort 是 stable？
2. 為何不使用 quicksort？
3. 為何 merge sort 適合 linked list？
* Linux 核心的 `list_sort` 建構方式不同於 fully-eager bottom-up mergesort，回答
* 推導 worst-case comparison 次數
* 說明為何延遲合併可降低比較次數
* 建立數學上界
* 鏈結串列的新增節點的時間複雜度是 O(1)，而陣列 (array) 則是 O(n)，但在實際硬體上，陣列可能更快，解釋為何如此並充分量化分析
* 逐一分析[第一週教材列出](https://wiki.csie.ncku.edu.tw/linux/schedule)的**題目 1** 到**題目 7**，確認理解題目且充分作答，並指出參考題解的錯誤和待改進之處
## 細讀〈[Linux: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)〉
* 若若一個惡意應用程式成功觸發多次系統呼叫並頻繁進入核心態，是否等同於繞過 user/kernel 隔離？分析：
* CPU privilege level
* page table 權限位元
* 系統呼叫機制的作用和考量
* fork 作為並行流程的分岔點。假釋一個程式流程包含 $n$ 個 fork 點與 $m$ 個 join 點<推導在最理想無同步成本下，可產生的最大並行行程數上界。
* 若 fork-join 模型可抽象為 [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph)，請說明：
* critical path 長度如何決定 theoretical speedup
* 與 [Amdahl's law](https://en.wikipedia.org/wiki/Amdahl%27s_law) 的關係
* Mach microkernel 將 thread 與 task 分離為獨立物件。比較在 NPTL 之前的 Linux 核心 與 Mach 的設計，在 scheduling abstraction 上的本質差異，而引入 NPTL 之後又如何讓 Linux 具備現代作業系統的關鍵特徵？
* 若將 Linux 的 VFS 或 network stack 遷移至 userspace (類似 microkernel multi-server 模型，這在 hybrid kernel 不少見)，分析：
* context switch 數量變化
* cache locality
* fault isolation
* worst-case latency
* 若 page fault handler 的平均成本為 $T_{pf}$，page fault 發生機率為 $p$，建立整體存取延遲的期望值模型
* scalability 常來自 cache coherence 與 lock 競爭。給定全域計數器使用 spinlock 保護，
* 在 $N$ 核系統中，若每核每秒更新 $f$ 次，估算：
* coherence traffic
* lock contention 成長趨勢
* CPU 排程器是「一堆處理器」與「一堆行程」的多對多映射，在 time-sharing 下，$f : (P, t) \rightarrow C$ 是否應視為時間函數，翻閱經典論文來探討排程考量
* 教材以「卡比吸入能力」比喻 Linux 演化。從以下角度分析：
1. abstraction preservation
2. backward compatibility
3. scalability pressure
4. real-time requirement
討論：
* 為何 Linux 在 monolithic 架構下仍能持續擴展？
* 哪些 abstraction 是演化關鍵？
## 探討〈[從熱力學第二定律到系統軟體：機率、資訊熵與現代作業系統的大融通](https://hackmd.io/@sysprog/from-entropy-to-os)〉
> 本文致敬《[Consilience: The Unity of Knowledge](https://en.wikipedia.org/wiki/Consilience_(book))》(繁體中文版《知識大融通》)
* 將文中提出三項宏觀穩定條件 (尾部可重現、吞吐時間序列分段平穩、排程誤差無長期漂移) 改寫為可被拒絕的統計假說
* 明確寫出 $H_0, H_1$
* 指出檢定方法（例如 ADF test、KPSS、two-sample KS）
* 指出文中 i.i.d. 假設在 CPU 排程的追蹤，何時不成立
* 提供數學定義
* 給出 CI 與顯著水準
* 討論 Type I / Type II error
* 文件引用 M/G/1 的 P-K 公式
1. 嚴格推導 $E[W_q]$ 對 $E[S^2]$ 的敏感度
2. 證明當 $\rho \to 1$ 時的發散階數
3. 構造一個 lognormal 與 Pareto 分佈: 固定 $E[S]$、改變 $E[S^2]$，隨後比較 tail latency
* 針對 EEVDF 的 lag 有界性證明，即 $Lagi(t) = S_i(t) - s_i(t)$
1. 在流體模型下證明 $\sum_i Lagi(t) = 0$
2. 在離散 slice 條件下推導誤差界限
3. 推導當 request length 改變時界限如何縮放
4. 驗證 lag 分佈是否穩態
* 熵率優於單次熵
1. 對 `sched_wakeup` 和 `sched_switch` 事件序列，建立 n-gram 模型並計算 entropy rate
2. 設計一個負載 regime change，並比較前後熵率
* 改進數學嚴格性和書寫
1. 補充所有公式的前提條件
2. 區分「方法論類比」與「數學等價」
3. 明確說明適用範圍與失效條件
Sign in with Wallet
Connect another wallet