# 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
```
### 亂度
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: 彙整其他學員的成果
> 紀錄你從其他學員成果獲得的啟發，應適度重現實驗並詳實標注
Sign in with Wallet
Connect another wallet