2025q1 Homework1 (lab0)

--- title: 2025q1 Homework1 (lab0) tags: - Linux 核心設計 --- # 2025q1 Homework1 (lab0) contributed by < `yuto0226` > ### Reviewed by `Denny0097` > commits title 格式不統一有時會加上 "function" 有時不會，建議統一。 ### Reviewed by `rota1001` 1. `q_free` 的[實作](https://github.com/yuto0226/lab0-c/commit/1ef5317636ec191bb8017e5748f189a26f14ec37#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923R32)中，`list_for_each_entry_safe` 下只有一行，大括號可以省略。 2. `q_delete_mid` 使用快慢指標進行實作無法充分發揮雙向鏈結串列的優勢，可以思考更有效率的實作。 ### Reviewed by `EricccTaiwan` > 善用 [Graphviz](https://graphviz.org/)。 [實作 shuffle 指令](https://hackmd.io/wrJ4p41cSdiWYqxSBcKIwA?both=#%E5%AF%A6%E4%BD%9C-shuffle-%E6%8C%87%E4%BB%A4)的流程實做圖，用 [Graphviz](https://graphviz.org/) 取代能更加美觀，且方便移植 (e.g., 複製到其他筆記中使用)。 {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 20 On-line CPU(s) list: 0-19 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i7-12700H CPU family: 6 Model: 154 Thread(s) per core: 2 Core(s) per socket: 10 Socket(s): 1 Stepping: 3 BogoMIPS: 5376.02 ``` ## 修改 queue.\[ch\] ### list.h 筆記 - `LIST_HEAD(head)`：直接初始化節點，下一行可以直接使用 `head` 節點 - `list_add`：將 `node` 插入 `head` 節點之後 - `list_add_tail`：將 `node` 插入 `head` 節點之前 - `list_cut_position(head_to, head_from, node)`：從第一個節點到 `node` 移到 `head_to` 串列 ![圖片](https://hackmd.io/_uploads/SJKIIg1s1g.png) - `list_move(node, head)`：將同一個串列上的 `node` 插入至 `head` 之後 - `list_move_tail(node, head)`：將同一個串列上的 `node` 插入至 `head` 之前 ### 實作注意事項 - [ ] 檢查傳入函式指標是否為 `NULL`，或是環狀佇列是否包含節點 - `!head || list_empty(head)` ### q_new 使用 `malloc` 配置記憶體後，應檢查是否配置成功，接著才初始化節點。 >Commit [8720df4](https://github.com/yuto0226/lab0-c/commit/8720df4caf0ed321c6f63ad655c6a60783008392) ### q_free 要釋出的節點有兩種：`struct list_head`、`element_t`，可以個別使用 `free`、`q_release_element` 釋放記憶體空間。提交時觸發了 `cppcheck` 的 `unusedLabel` 錯誤： ``` Following files need to be cleaned up: queue.c Running static analysis... queue.c:32:5: style: Label 'int' is not used. [unusedLabel] list_for_each_entry_safe (entry, safe, head, list) { ^ Fail to pass static analysis. ``` 原因還無法釐清，發現有可能是 Commit [1d68fae](https://github.com/sysprog21/lab0-c/commit/1d68faec1ffc912e7e5d1098a3d46fbf835fee49) 造成的問題，用 `git checkout` 回到 Commit [9cf7f12](https://github.com/sysprog21/lab0-c/commit/9cf7f12eb329aa73f0f78cd92305b40f00b4380d) 便可以通過 `scripts/pre-commit.hook`。在 [issue #211](https://github.com/sysprog21/lab0-c/pull/211#issuecomment-2690577631) 中，有同學回覆表示有相同問題，原因是 cppcheck 舊版本的程式錯誤，自己編譯 cppcheck 就可以解決這個問題了。 > Commit [1ef5317](https://github.com/yuto0226/lab0-c/commit/1ef5317636ec191bb8017e5748f189a26f14ec37) ### q_insert_head、 q_insert_tail 這兩個函式要做的事情幾乎一樣，配置節點的記憶體空間，接著插入佇列中，唯一的差別在於插入的位置。一開始的想法是使用 `list_add`、`list_add_tail` 去對應不同位置的情況，再參考 2023 年 [Eroiko 的開發紀錄](https://hackmd.io/@Eroiko/lab0-impl#q_descend-%E5%92%8C-q_ascend-%E7%9A%84%E5%AF%A6%E4%BD%9C%E8%88%87%E9%87%8D%E6%A7%8B) 中提到的巨集的方式定義這兩個函式。後來重新研讀 `list.h` ，發現 `list_add` 函式可以延伸為新增節點到 `head` 之後，也就是說 `list_add_tail` 甚至可以替換成 `list_add(head->prev)`。參考 2023 年 [yanjiew 的開發紀錄](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_remove_head-%E5%92%8C-q_remove_tail)，`q_[insert,remove]_tail` 可以重用 `q_[insert,remove]` 的程式碼。 >Commit [692d17e](https://github.com/yuto0226/lab0-c/commit/692d17e6a607ddd0bbfaba9013a9125b4cac1f62) 在使用 `strdup` 配置字串的記憶體空間時，若配置失敗就要回傳 `false`，同時也需要釋放先前配置給節點的記憶體空間。在測試後發現並修正。 >Commit [03e118e](https://github.com/yuto0226/lab0-c/commit/03e118ee40f6f4498989db07906916c502d03288) ### q_remove_head、q_remove_tail 這兩個函式會從佇列中移除頭或尾的節點，因此除了要檢查 `head` 外，也要檢查是否至少包含一個節點。複製字串時，除了考量 `sp` 是否為 `NULL`，檢查節點的 `value` 使否有配置記憶體，可以省去 `strncpy` 的執行。而 `q_remove_head` 不同於 `q_insert_head`，不是操作 `head`，而是操作 `head->next`，所以在 `q_remove_tail` 傳入參數時要改成 `head->prev->prev`。 >Commit [f303894](https://github.com/yuto0226/lab0-c/commit/f303894a9e588e3dbe7378d93d30bc733c9ebe22) ### q_size 考慮使否要使用 `list_empty()` 作為一開始檢查的條件。閱讀 `list.h` 可以看到 `list_empty()` 會回傳 `(head->next == head)`。而若放棄檢查，`list_for_each()` 巨集中的 `for` 迴圈一樣會檢查，只是換個結構而已。使用 `list_for_each()` 巨集則可以節省函式呼叫的棧空間，故不須搭配 `list_empty()` 檢查。 >Commit [0b7f422](https://github.com/yuto0226/lab0-c/commit/0b7f422284959110517389891a3903273a96323a) ### q_delete_mid 閱讀第二周的教材 [分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)，文中描述：相較於「單一指標」，「快慢指標」方式具有更好的時間局部性。 >Commit [f52ba78](https://github.com/yuto0226/lab0-c/commit/f52ba78d8bffc06767f021efa5dccbeb47991a1a) ### q_delete_dup `q_delete_dup` 會刪除已經排序佇列中具備重複內容的節點。初步的想法是使用兩個指標 `curr`、`next` 走訪佇列，判斷 `next`、`prev` 指向的節點的內容是否相同，若相同則刪除 `curr` 節點。但上述的流程會漏掉一個節點沒有刪除，因此可以使用一個變數判斷目前節點的內容是否重複，並刪除該值的最後一個節點。 ```diff diff --git a/queue.c b/queue.c index 6ccbaad..04128f6 100644 --- a/queue.c +++ b/queue.c @@ -135,12 +135,16 @@ bool q_delete_dup(struct list_head *head) if (!head || list_empty(head)) return false; + bool isdup = false; element_t *curr = NULL, *next = NULL; list_for_each_entry_safe (curr, next, head, list) { if (&next->list != head && !strcmp(curr->value, next->value)) { list_del(&curr->list); q_release_element(curr); + } else if (isdup) { + q_release_element(curr); + isdup = false; } } ``` >Commit [1add3c8](https://github.com/yuto0226/lab0-c/commit/1add3c8645d912a2f2d2f7e122b25f70318d9d97) 注意到上述更動包含不完整的實作，在測試的過程中遺漏了，更正如下： ```diff diff --git a/queue.c b/queue.c index f059b92..9174568 100644 --- a/queue.c +++ b/queue.c @@ -142,7 +142,9 @@ bool q_delete_dup(struct list_head *head) if (&next->list != head && !strcmp(curr->value, next->value)) { list_del(&curr->list); q_release_element(curr); + isdup = true; } else if (isdup) { + list_del(&curr->list); q_release_element(curr); isdup = false; } ``` > [!Note] > 提交程式碼應小心謹慎、步步為營 > Commit [628403f](https://github.com/yuto0226/lab0-c/commit/628403fac0b09d89d32ee313f6524e592604646a) ### q_swap 參考 [2025-02-25 第一次問答簡記](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg#Cheng5840)，`q_swap` 是 `q_reverseK` 的特例($k = 2$)。 >Commit [cbeec82](https://github.com/yuto0226/lab0-c/commit/cbeec829642eae574ac0acb33f5fe5ee7e14bfef) ### q_reverse 走訪整個佇列，使用 `list_move` 將所有節點移動到頭節點後。 ![圖片](https://hackmd.io/_uploads/S1iEsRboJx.png =300x) >Commit [c5bd310](https://github.com/yuto0226/lab0-c/commit/c5bd3100012395f1e7cc723b162a424d57e3d692) ### q_reverseK 參考 [2025-02-25 第一次問答簡記](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg#Cheng5840) >Commit [cbeec82](https://github.com/yuto0226/lab0-c/commit/cbeec829642eae574ac0acb33f5fe5ee7e14bfef) ### inorder 在後續的排序或是合併的實作中，都會透過 `descend` 來控制升序或降序排列。因此包裝一個 `strcmp` 函式的實作是必須的。參考 2024 年 [Eriko](https://hackmd.io/@Eroiko/lab0-impl#in_order-%E8%BC%94%E5%8A%A9%E5%87%BD%E5%BC%8F) 的實作，發現會導致 merge sort 無法穩定排序。 > Commit [ebd7667](https://github.com/yuto0226/lab0-c/commit/ebd76674a2c30d2859d76e19558d63a6539dadfd) ### q_merge_two 後續實作合併排序與 `merge` 函式，皆會需要合併兩個佇列。`q_merge_two` 會依照升序或降序合併 `sub` 到 `main` 上。 > Commit [67286be](https://github.com/yuto0226/lab0-c/commit/67286be6852f1cbe4710d8d0a0e6b3360c54974d) ### q_sort 搭配 `q_merge_two` 實作合併排序。 >Commit [d5a2440](https://github.com/yuto0226/lab0-c/commit/d5a24408341aa9ef2864bf965cf3854868e23305) ### q_ascend、q_descend `q_ascend` 是刪除所有節點 `curr` 右邊節點 `next` 的內容比 `curr` 小的函式，維持佇列節點內容遞增。`q_descend` 則相反。初步想法是倒著走訪佇列，記住最小內容的節點 `min`，若有節點的內容大於 `min` 就刪除該節點。 >Commit [22944d3](https://github.com/yuto0226/lab0-c/commit/22944d31fa1c30b3a07b760a6458859ec54913ad) ### q_merge 在 qtest.c 中，多個佇列會透過 `queue_context_t` 串在一起，這個實作採用最簡單的方式從第一個柱列合併到最後一個佇列。 >Commit [0e39489](https://github.com/yuto0226/lab0-c/commit/0e39489c73ffaafa20f36b6a1cbfbdb553446d18) ## Valgrind + 自動測試程式 :::warning TODO ::: ## 整合網頁伺服器 :::warning TODO ::: ## 亂數 + 論文閱讀 ### 實作 shuffle 指令新增 `shuffle` 指令參考[作業說明](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)和 `do_sort` 的實作。要添加 `do_shuffle` 函式並在 `console_init` 中使用 `ADD_COMMAND` 巨集新增指令。 ```diff @@ -1096,6 +1126,7 @@ static void console_init() ""); ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time", "[K]"); + ADD_COMMAND(shuffle, "Shuffle the queue", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); add_param("malloc", &fail_probability, "Malloc failure probability percent", ``` > Commit [6e795d6](https://github.com/yuto0226/lab0-c/commit/6e795d6c9547ecde7160fa1fe9254f2ed8a53f60) `q_shuffle` 函式先採用 [Pencil-and-paper method](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method) 實作。透過 `rand()` 選擇節點，並使用 `list_move_tail` 移到暫存佇列，最後剩下一個節點時再使用 `list_splice` 合併。 > Commit [daa29bd](https://github.com/yuto0226/lab0-c/commit/daa29bd199ec47dc85aec17ec26011fa806b08e5) 經過腳本測試後，發現實作有問題。執行腳本結果： ```shell Expectation: 41666 Observation: {'1234': 167322, '1243': 0, '1324': 165895, '1342': 0, '1423': 0, '1432': 0, '2134': 166635, '2143': 0, '2314': 166719, '2341': 0, '2413': 0, '2431': 0, '3124': 166820, '3142': 0, '3214': 166609, '3241': 0, '3412': 0, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0} chi square sum: 3000073.3336533387 ``` ![Figure_1](https://hackmd.io/_uploads/rk6ETHVi1l.png =400x) 上述的實驗結果嚴重分布不均，重新依照[作業說明](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle)的流程實作。 ![圖片](https://hackmd.io/_uploads/BysH8NBjyx.png) ```diff diff --git a/qtest.c b/qtest.c index 63b236e..794fbc8 100644 --- a/qtest.c +++ b/qtest.c @@ -1062,17 +1062,19 @@ void q_shuffle(struct list_head *head) return; int range = q_size(head) - 1; - LIST_HEAD(tmp); - for (; range > 1; range--) { - struct list_head *curr = head->next; + struct list_head *new = head->prev; + for (; range; range--) { int j = rand() % range; - + struct list_head *old = head->next; for (int i = 0; i < j; i++) - curr = curr->next; + old = old->next; - list_move_tail(curr, &tmp); + // swap old and new + struct list_head *tmp = old->prev; + list_move(old, new); + list_move(new, tmp); + new = old->prev; } - list_splice(&tmp, head); } ``` > Commit [d46fe78](https://github.com/yuto0226/lab0-c/commit/d46fe7866eeb8eef34fb7b6dbfc9527428fa8068) ### 統計方法驗證-shuffle - $H_0$：shuffle 的結果發生的機率相同，遵守均勻分布 - $H_1$：shuffle 的結果發生的機率至少有一個不同 ![Chi-Squared-Distribution](https://hackmd.io/_uploads/H1UNDNBoJx. =400x) #### 1. 先計算計算 chi-square statistic $X^2$ 參考 [rota1001](https://hackmd.io/@rota1001/linux2025-homework1#%E7%B5%B1%E8%A8%88%E6%96%B9%E5%BC%8F%E9%A9%97%E8%AD%89-shuffle) 的開發紀錄，將腳本中輸入的字串操作改成乘法，也新增了一些提示訊息。使用 `time.perf_counter` 計時，比較兩個方法的效能差異： ```python test_count = 1000000 start_time = time.perf_counter() input_str = "new\nit 1\nit 2\nit 3\nit 4\n" for i in range(test_count): input_str += "shuffle\n" input_str += "free\nquit\n" end_time = time.perf_counter() print(f"執行時間: {end_time - start_time:.6f} 秒") ``` | 使用 loop | 字串乘法 | | ------------ | -------- | | 452.90100 秒 | 0.00397 秒 | > Commit [4c858d3](https://github.com/yuto0226/lab0-c/commit/4c858d3f558601390df20b3aedc32aec762653d7) ```shell Expectation: 41666 Observation: {'1234': 41430, '1243': 41782, '1324': 41855, '1342': 41923, '1423': 41823, '1432': 41725, '2134': 41509, '2143': 41963, '2314': 41902, '2341': 42156, '2413': 41341, '2431': 41806, '3124': 41641, '3142': 41761, '3214': 41611, '3241': 41838, '3412': 41447, '3421': 41657, '4123': 41416, '4132': 41186, '4213': 41455, '4231': 41481, '4312': 41706, '4321': 41586} chi square sum: 28.869533912542597 ``` ![Figure_2](https://hackmd.io/_uploads/SySk37ri1x.png =400x) 後續進行 10 次計算，所有計算的結果如下： 28.86953391254259、25.4207747323957、23.952335237363798、 18.182786924590797、33.6160418566697、15.172274756396103、19.215955455287286、34.29611673786781、34.7917726683627、 17.876686026976433、21.46018336293381 結果大致介於 15~35 之間，但需要更多統計結果才能驗證其計算值的範圍。 #### 2. 決定自由度總共有 $4! = 24$ 種結果，其中可以自由變換的有 23 個，因此自由度為 23。 #### 3. 選擇顯著水準 $\alpha = P(拒絕H_0|H_0為真)$ 常見的 $\alpha$ 是 0.05 #### 4. 統計檢定的結果參考 [rota1001](https://hackmd.io/@rota1001/linux2025-homework1#3-%E9%81%B8%E6%93%87%E9%A1%AF%E8%91%97%E6%B0%B4%E6%BA%96) 同學開發紀錄的腳本計算 P-value： ```python from scipy.stats import chi2 # print(chi2.ppf(0.05, 23)) # 35.17246162690806 # 可以看出自由度為 23 時，卡方值要多大才能讓大於此卡方值出現的機率小於 0.05 print(1 - chi2.cdf(28.869533912542597, 23)) # 0.18467433647899123 ``` 計算出來的結果大於顯著水準 P value(0.1~0.2) > alpha(0.05)，因此不拒絕 $H_0$，也就是沒有足夠的證據推翻 shuffle 符合均勻分布。 ### Entropy ### 論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉 ## Linux 核心的鏈結串列排序 :::warning TODO :::