# Linux 核心專題: 重作 lab0 > 執行人: LeoriumDev ### Reviewed by `jserv` [LeoriumDev/lab0-c](https://github.com/LeoriumDev/lab0-c) 應該要 rebase 到最新的 [lab0-c](https://github.com/sysprog21/lab0-c),留意 git 的操作 > 好的 [name=Leorium] :::danger 使用 rebase,而非 git merge,注意二者的差別 ::: > 已更正 [name=Leorium] ## TODO: 重作 lab0 > 依據[第一份作業](https://hackmd.io/@sysprog/linux2025-lab0/)指示,重新投入,並強化對於亂數、排序演算法和改進 (特別留意 cache 的影響)、常數時間判定的理論和實務、統計手法、網頁伺服器,以及程式碼品質的議題。 ## 亂數、排序演算法和改進 ### [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle) Fisher–Yates shuffle 是一種用來打亂有限序列的演算法。 其 (最初的) 演算法運作原理如下 (以打亂一串數字為例): 1. 從 $1$ 到 $N$ 中選出任意一數字 $k$ (不能選到被放入序列 $S$ 當中的數字) 2. 由小至大,把第 $k$ 個數字,放入序列 $S$ 當中 3. 重複步驟 $1$ 直到所有數字都放入序列 $S$ 當中 4. 序列 $S$ 最後會是被打亂 (shuffle) 的序列 之後有為電腦改進的演算法為 Algorithm P (Shuffling)。 :::danger 提供更多細節和參照第一手材料 ::: 在[教材](https://hackmd.io/@sysprog/linux2025-lab0-d)當中有描述另一種實作方式: 1. 先用 `q_size` 取得 queue 的大小 `len`。 2. 隨機從 0 ~ (len - 1) 中抽出一個數字 `random`,然後 `old` 將指向從前面數來第 random 個節點,`new` 會指向最後一個未被抽到的節點,將 `old` 和 `new` 指向的節點的值交換,再將 len - 1。 3. 隨著 len 大小變小,已經被抽到過,並交換值到 queue 後面的會愈來愈多,直到所有的節點都已經被抽到過,shuffle 就結束。 ### 在 qtest 提供新的命令 `shuffle` ```c /* Add a new command */ void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter); #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` :::danger 依據課程教材,C preprocessor 翻譯為「前置處理器」。 `#` 和 `##` 二者皆「不是」運算子,翻閱 C 語言規格書。 留意細節! ::: > 在 C99 - 6.10.3.1 Argument substitution 有提到 `#` 及 `##` 被稱為 “preprocessing token” 在 console.h 中定義的 ADD_COMMAND 巨集,利用 C 的前置處理器符號 (preprocessing token) `#` 和 `##`,提供了一個簡潔且一致的方式來新增命令。它讓每個命令都對應到自己的名稱字串及提供功能的函式指標。 例如,若要新增 shuffle 命令,只需使用: ```c ADD_COMMAND(shuffle, "Shuffle the queue", ""); ``` 這會展開為: ```c add_cmd("shuffle", do_shuffle, "Shuffle the queue", ""); ``` 接下來要實作 `do_shuffle` 函式,其中將 Fisher–Yates shuffle 的實作寫成獨立的 `q_shuffle` 函式。 ```c static bool do_shuffle(int argc, char *argv[]) { if (!current || !current->q) report(3, "Warning: Calling shuffle on null queue"); error_check(); if (q_size(current->q) < 2) report(3, "Warning: Calling shuffle on single queue"); error_check(); if (exception_setup(true)) q_shuffle(current->q); exception_cancel(); q_show(3); return !error_check(); } ``` `q_shuffle` 函式實作: ```c void q_shuffle(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *last = head; int len = q_size(head); while (len > 0) { int index = rand() % len; struct list_head *new = last->prev; struct list_head *old = new; while (index--) old = old->prev; if (new->prev != old) list_move(old, new->prev); list_move(new, old->prev); last = last->prev; len--; } } ``` ### 利用統計方法研究 `shuffle` 的亂度 為確保 `shuffle` 的結果發生的機率相同,也就是其遵守 Uniform distribution,可以利用 [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 來檢驗虛無假說 (Null hypothesis)。 參考教材說明: 如果要 shuffle 三個不同的數字,會出現六種可能的結果,彼此是互斥的,且發生機率加起來為 1。那假設 shuffle 是公平的(六種結果發生的機率相同),並遵守 Uniform distribution,那虛無假說為: - $H_0$ (虛無假說): shuffle 的結果發生的機率相同,遵守 Uniform distribution - $H_1$ (對立假說): shuffle 的結果發生的機率至少有一個不同 #### Pearson's chi-squared test #### 計算 chi-squared test statistic $X^2$ 公式 $$ X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i} $$ + $X^2$: Pearson's cumulative test statistic + $O_i$: the number of observations of type i + $E_i$: the expected count of type i 利用教材當中測試程式跑出的結果 (大約跑了半小時): ``` Expectation: 41666 Observation: {'1234': 41749, '1243': 41852, '1324': 41766, '1342': 42140, '1423': 41513, '1432': 41512, '2134': 41689, '2143': 41734, '2314': 41677, '2341': 41631, '2413': 41405, '2431': 41839, '3124': 41844, '3142': 41215, '3214': 41698, '3241': 41447, '3412': 41501, '3421': 41390, '4123': 41839, '4132': 41872, '4213': 41796, '4231': 41707, '4312': 41477, '4321': 41707} chi square sum: 22.6480583689339 ``` ![shuffle_result](https://hackmd.io/_uploads/S1tlgzBHgg.png) ### 亂度 1. What is random? 2. How to measure the randomness? ## 常數時間判定的理論和實務、統計手法 ### 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉 這篇論文在介紹一項工具 dudect,這項工具能夠透過統計分析,評估一段程式碼的執行時間是否為 constant time $O(1)$,這項工具的特點是,dudect 是透過 timing leakeage detection tests 對執行時間的統計分析,沒有底層硬體的限制,不限於特定 CPU。 參考[ willwillhi1 同學的說明](https://hackmd.io/@willwillhi/lab0-2023),實作可分為以下步驟: * A. Step 1: Measure execution time - a) `Classes definition`: 給定兩種不同類別的輸入資料,重複對方法進行測量,最常見的就是 fix-vs-random tests - b) `Cycle counters`: 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。 - c) `Environmental conditions`: 為了減少環境的差異,每次測量都會對應隨機的輸入類別。 * B. Step 2: Apply post-processing - a) `Cropping`: 剪裁掉一些超過 threshold 的測量結果 - b) `Higher-order preprocessing`: Depending on the statistical test applied, it may be beneficial to apply some higherorder pre-processing * C. Step 3: Apply statistical test - a) `t-test`: Welch’s t-test,測試兩個平均數是否相同 - b) `Non-parametric tests`:(無母數統計分析): Kolmogorov-Smirnov ## 網頁伺服器 ### `select()` select(2) — Linux manual page > select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking. :::danger 不要只是張貼素材,而該解讀和討論 ::: 根據 manpage,`select()` 能讓程式監控多個 file descriptor 的,會等待其中一個或多個 file descriptor 直到就緒 (ready),而判斷「就緒」的條件是能否執行相對應的 I/O 操作而不會發生 blocking 的情況。 > sidenote: `select()` 僅能監控 number 低於 FD_SETSIZE (1024) 的 file descriptor,可用 `poll()` 或 `epoll()` 取而代之。 而 file descriptor 是一個底層 (low level) 且原始 (primitive) 的一種用來與 file I/O 溝通的介面 (interface),本身是 integer。值得注意的是,如果要在 nonblocking 的情況下必須使用 file descriptor 而非 file stream。 > 參考 [glibc manual - 11.1.1 Streams and File Descriptors](https://www.gnu.org/software/libc/manual/html_node/Streams-and-File-Descriptors.html) `select()` 的定義: ```c int select(int nfds, fd_set *_Nullable restrict readfds, fd_set *_Nullable restrict writefds, fd_set *_Nullable restrict exceptfds, struct timeval *_Nullable restrict timeout); ``` - nfds 要被設定為最大的 file descriptor number 並加一。 - `fd_set` 是一個 file descriptor 的集合的結構體。 - readfds 要放入欲監控是否「可讀」(ready for reading) 的 file descriptor set。 - writefds 要放入欲監控是否「可寫」(ready for writing) 的 file descriptor set。 - exceptfds 要放入欲監控「例外」(exceptional conditions) 的 file descriptor set。 - timeout 是一個 `timeval` 結構體,其成員用來描述 `select()` 函式等待 file descriptor 就緒時,最多阻塞(blocking)多久。如果 timeout 這個參數設為 `NULL`,則代表 `select()` 會無限期地 (indefinitely) 等。blocking 結束的情況有: 1. file descriptor 就緒 2. 在函式呼叫中被 signal handler 中斷 (interrupt) 3. timeout 結束 (expire) ## 程式碼品質 ## TODO: 彙整其他學員的成果 > 紀錄你從其他學員成果獲得的啟發,應適度重現實驗並詳實標注