Linux 核心專題: 重作 lab0

執行人: LeoriumDev

Reviewed by `jserv`

LeoriumDev/lab0-c 應該要 rebase 到最新的 lab0-c，留意 git 的操作

好的 Leorium

使用 rebase，而非 git merge，注意二者的差別

已更正 Leorium

TODO: 重作 lab0

依據第一份作業指示，重新投入，並強化對於亂數、排序演算法和改進 (特別留意 cache 的影響)、常數時間判定的理論和實務、統計手法、網頁伺服器，以及程式碼品質的議題。

亂數、排序演算法和改進

Fisher–Yates shuffle

Fisher–Yates shuffle 是一種用來打亂有限序列的演算法。

其 (最初的) 演算法運作原理如下 (以打亂一串數字為例):

從
$1$ 到
$N$ 中選出任意一數字
$k$ (不能選到被放入序列
$S$ 當中的數字)
由小至大，把第
$k$ 個數字，放入序列
$S$ 當中
重複步驟
$1$ 直到所有數字都放入序列
$S$ 當中
序列
$S$ 最後會是被打亂 (shuffle) 的序列

之後有為電腦改進的演算法為 Algorithm P (Shuffling)。

提供更多細節和參照第一手材料

在教材當中有描述另一種實作方式：

先用 q_size 取得 queue 的大小 len。
隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。

在 qtest 提供新的命令 `shuffle`

/* 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)

依據課程教材，C preprocessor 翻譯為「前置處理器」。
# 和 ## 二者皆「不是」運算子，翻閱 C 語言規格書。
留意細節！

在 C99 - 6.10.3.1 Argument substitution 有提到 # 及 ## 被稱為 “preprocessing token”

在 console.h 中定義的 ADD_COMMAND 巨集，利用 C 的前置處理器符號 (preprocessing token) # 和 ##，提供了一個簡潔且一致的方式來新增命令。它讓每個命令都對應到自己的名稱字串及提供功能的函式指標。

例如，若要新增 shuffle 命令，只需使用：

ADD_COMMAND(shuffle, "Shuffle the queue", "");

這會展開為：

add_cmd("shuffle", do_shuffle, "Shuffle the queue", "");

接下來要實作 do_shuffle 函式，其中將 Fisher–Yates shuffle 的實作寫成獨立的 q_shuffle 函式。

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 函式實作：

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 來檢驗虛無假說 (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} \frac{(O_{i} - E_{i})^{2}}{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

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

亂度

What is random?
How to measure the randomness?

常數時間判定的理論和實務、統計手法

研讀論文〈Dude, is my code constant time?〉

這篇論文在介紹一項工具 dudect，這項工具能夠透過統計分析，評估一段程式碼的執行時間是否為 constant time

O (1)

，這項工具的特點是，dudect 是透過 timing leakeage detection tests 對執行時間的統計分析，沒有底層硬體的限制，不限於特定 CPU。

參考 willwillhi1 同學的說明，實作可分為以下步驟：

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.

不要只是張貼素材，而該解讀和討論

根據 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

select() 的定義：

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: 彙整其他學員的成果

紀錄你從其他學員成果獲得的啟發，應適度重現實驗並詳實標注