2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < [tintinjian12999](https://github.com/tintinjian12999) > ### Reviewed by `Vincent550102` 1. 善用 HackMD 中 codeblock 的功能將程式碼片段標註起來，提高可讀性。 > 你的洞見呢？你逐一查閱過學員的 git commits 嗎？ :notes: jserv ### Reviewed by `vax-r` * commit message 撰寫有提升理解度與內容，不過仍存在可改進空間，例如精確說明 why v.s. how ，在 [commit a58d4bb](https://github.com/tintinjian12999/lab0-c/commit/a58d4bb546760d79886729c0f5a236a709e02fac) 沒有做到，僅僅提及你實現了該論文的做法，應當提及原本實作的缺陷與為何實作了 `percentile` 函式後能使程式碼通過測驗。 * [commit 35862e9](https://github.com/tintinjian12999/lab0-c/commit/35862e9a0d29e914bc6e2dcbc47a6f3577d0533e) 依舊沒有符合 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 提及之規定，沒有遵守每行 72 字元與清楚說明 why v.s. how 。 ### Reviewed by `vestata` 1. queue 功能的開發過程紀錄清楚，且有活用 LIST API 2. [commit e874115](https://github.com/tintinjian12999/lab0-c/commit/e874115cf049a77ec31a4c79706732d6f14dd121#comments), [commit d30401a](https://github.com/tintinjian12999/lab0-c/commit/d30401a2f283dcdb2164e1536a66654d3098dbbf), [commit a204d13](https://github.com/tintinjian12999/lab0-c/commit/a204d133cc8f684a8d4053327f9400de7f74cd99) , [commit 69b27a2](https://github.com/tintinjian12999/lab0-c/commit/69b27a20c43e6cffaaf6ff2942b71b32ca21150f) 應該使用祈使句 **Use the imperative mood in the subject line** 3. [commit a58d4bb](https://github.com/tintinjian12999/lab0-c/commit/a58d4bb546760d79886729c0f5a236a709e02fac) 關於 dudect 的實作對於缺失的修改敘述不精確，也要修改為祈使句。 ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0 $ export LC_ALL=C $ ls cpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 43 bits physical, 48 bits virtual CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: AuthenticAMD CPU family: 23 Model: 24 Model name: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx Stepping: 1 Frequency boost: enabled CPU MHz: 1400.000 CPU max MHz: 2300.0000 CPU min MHz: 1400.0000 BogoMIPS: 4591.41 Virtualization: AMD-V L1d cache: 128 KiB L1i cache: 256 KiB L2 cache: 2 MiB L3 cache: 4 MiB NUMA node0 CPU(s): 0-7 ``` ## 針對佇列操作的程式碼實作 ### `q_new` <s>分配</s> 配置記憶體空間給 head 並透過 list.h 的巨集將 prev 和 next 指向自身。 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(*head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ### `q_free` 利用 list_for_each_safe 走訪各個節點並釋放空間，在 list_for_each_safe 裡利用了額外的 safe 儲存了指向下個節點的位址 node->safe，因此可以在走訪的過程中修改節點。 ```c void q_free(struct list_head *head) { element_t *node, *safe; list_for_each_entry_safe (node, safe, head, list) q_release_element(node); free(head); } ``` 原先執行時會發生 `ERROR: Freed queue, but 1 blocks are still allocated` 這項錯誤，原因是在 list_for_each_safe 裡將節點全部釋放後，沒有將 head 的記憶體空間釋放。在參考 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1#q_free) 的作法後，改用 list_for_each_entry_safe 一併將節點內的資料釋放，如此才能達到完整的功能。 ``` diff - struct list_head *node, *safe; - list_for_each_safe (node, safe, head) - free(node); + element_t *node, *safe; + list_for_each_entry_safe (node, safe, head, list) + q_release_element(node); + free(head); ``` ### `q_insert_head` 利用 malloc 替 new_element 與其指向的 new_element->value 配置記憶體空間，接著使用 strncpy 複製 s 字串到 new_element->value 裡，最後使用 list_add 將 new_element 加到 head 指向的下一個 node 裡，也就是整個 list 的頭。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new_element = malloc(sizeof(*new_element)); if (!new_element) return false; new_element->value = malloc(sizeof(char) * (strlen(s) + 1)); if (!new_element->value) { free(new_element); return false; } strncpy(new_element->value, s, strlen(s) + 1); list_add(&new_element->list, head); return true; } ``` ### `q_insert_tail` 與 q_insert_head 類似，只須將 list_add 改為 list_add_tail。 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *new_element = malloc(sizeof(*new_element)); if (!new_element) return false; new_element->value = malloc(sizeof(char) * (strlen(s) + 1)); if (!new_element->value) { free(new_element); return false; } strncpy(new_element->value, s, strlen(s) + 1); list_add_tail(&new_element->list, head); return true; } ``` ### `q_remove_head`, `q_remove_tail` 兩者類似，利用 list_first_entry 或 list_last_entry 取出節點內的資料，並利用 strncpy 將資料複製到 sp 上。原先的程式碼直接使用 `strncpy(sp, temp->value, bufsize)` 會導致問題，根據 C99 規格書 7.21.2.4:3 > If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written. strncpy 不保證當 s2 (也就是要拷貝的字串) 比 bufsize 還大時會在字串結尾加上空字元。因此修改如下。 commit [947d03a](https://github.com/tintinjian12999/lab0-c/commit/947d03a3603522813a6c49262c67eae4dfb8d829) ```diff - if (sp != NULL && bufsize != 0) - strncpy(sp, temp->value, bufsize); + if (sp != NULL && bufsize != 0) { + strncpy(sp, temp->value, bufsize - 1); + sp[bufsize - 1] = '\0'; + } ``` ### `q_size` 利用 list_for_each 走訪整個串列並計數即可完成。 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *node; int count = 0; list_for_each(node, head) count++; return count; } ``` ### `q_delete_mid` 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94) ，利用快慢指標的方式找到中間的節點，利用 list_del 移出序列並使用 q_release_element 清除欲刪除節點內的資料。 ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *slow = head->next, *fast = head->next->next; while (fast != head && fast->next != head) { fast = fast->next->next; slow = slow->next; } list_del(slow); q_release_element(list_entry(slow, element_t, list)); return true; } ``` `fast` 的初始應設定為 head->next->next 以確保 fast 一定在 slow 前方。 ```diff - *fast = head->next + *fast = head->next->next ``` :::warning 能否針對環狀且雙向鏈結串列的特性，撰寫更快更精簡的程式碼？ ::: ### `q_delete_dup` > commit [f87096e](https://github.com/tintinjian12999/lab0-c/commit/f87096eea80810f86d07a0b00ada2324f03a27bd) 利用 `bool dup` 來檢查有否剩餘的重複的節點沒有被刪除，使用 `strcmp` 來確認節點是否重複。 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head) || list_is_singular(head)) return false; element_t *node, *safe; bool dup = false; list_for_each_entry_safe(node, safe, head, list) { if (node->list.next != head && strcmp(node->value, safe->value) == 0) { dup = true; list_del(&node->list); q_release_element(node); } else if (dup) { dup = false; list_del(&node->list); q_release_element(node); } } return true; } ``` 原先的程式碼會存取到已經刪除的節點，因此做改正，並且在這裡引入 Linux API。 ### `q_swap` 由於 list_move 的作用是將當前的節點 remove 並插入到所指定節點的後方，因此利用這個函式就能夠達到 swap 的目的 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if(!head || list_empty(head)) return; struct list_head *li; for(li = head->next;li != head && li->next != head;li = li->next) list_move(li, li->next); } ``` ### `q_reverse` 只需要將原本第一個節點前方的節點通過 list_move 移動到 head 後直到原本的第一個節點變為最後一個節點即可達成目的。 <s> ![圖片](https://hackmd.io/_uploads/B1fXrlbaT.png) </s> :::danger 使用 Graphviz (或其他 HackMD 支援的圖形標記語法) 重新繪製圖片，並嵌入到 HackMD ::: ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; { rank="same" head -> struct1 [dir = both] struct1 -> struct2 [dir = both] struct2 -> struct3 [dir = both] struct3 -> head [dir = both] } } ``` ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; { rank="same" head -> struct2 [dir = both] struct2 -> struct1 [dir = both] struct1 -> struct3 [dir = both] struct3 -> head [dir = both] } } ``` ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; { rank="same" head -> struct3 [dir = both] struct3 -> struct2 [dir = both] struct2 -> struct1 [dir = both] struct1 -> head [dir = both] } } ``` ```c void q_reverse(struct list_head *head) { if (!head|| list_empty(head)) return; struct list_head *node = head->next; while (node->next != head) list_move(node->next, head); } ``` ### `q_reverseK` > commit [f87096e](https://github.com/tintinjian12999/lab0-c/commit/f87096eea80810f86d07a0b00ada2324f03a27bd) 可以透過將原有的序列切為多個子序列分別做 reverse 後再接回達成 <s> ![圖片](https://hackmd.io/_uploads/r1zosgbpa.png) </s> :::danger 使用 Graphviz (或其他 HackMD 支援的圖形標記語法) 重新繪製圖片，並嵌入到 HackMD ::: ```graphviz digraph structs { node[shape=plaintext]; iter [label = "k = 2\l"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; { rank="same" head -> struct1 [dir = both] struct1 -> struct2 [dir = both] struct2 -> struct3 [dir = both] struct3 -> struct4 [dir = both] struct4 -> head [dir = both] } } ``` ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head1 [label= "head1"]; head2 [label= "head2"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; { rank="same" head1 -> struct1 [dir = both] struct1 -> struct2 [dir = both] struct2 -> head1[dir = both] head2 -> struct3 [dir = both] struct3 -> struct4 [dir = both] struct4 -> head2 [dir = both] } } ``` ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head1 [label= "head1"]; head2 [label= "head2"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; { rank="same" head1 -> struct2 [dir = both] struct2 -> struct1 [dir = both] struct1 -> head1[dir = both] head2 -> struct4 [dir = both] struct4 -> struct3 [dir = both] struct3 -> head2 [dir = both] } } ``` ```graphviz digraph structs { node[shape=plaintext]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "2"]; struct2 [label= "1"]; struct3 [label= "4"]; struct4 [label= "3"]; { rank="same" head -> struct1 [dir = both] struct1 -> struct2 [dir = both] struct2 -> struct3 [dir = both] struct3 -> struct4 [dir = both] struct4 -> head [dir = both] } } ``` ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head) || list_is_singular(head)) return; int count = 0; struct list_head *node, *safe, *head_from = head; LIST_HEAD(head_to); list_for_each_safe (node, safe, head) { count++; if (count == k) { list_cut_position(&head_to, head_from, node); q_reverse(&head_to); list_splice_init(&head_to, head_from); count = 0; head_from = safe->prev; } } } ``` 原先的程式碼使用了 `q_new()` ，這是不必要的 allocation ，因此做了修改。 ### `q_sort` 參考 [lintin528](https://hackmd.io/@lintin528/Bybi7wj3T#q_sort) 的作法，利用快慢指標將序列從中間分割成兩個子序列，再利用 mergeTwoLists 將兩個序列接回 head 。 ```c void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *slow = head->next, *fast = head->next->next; while (fast != head && fast->next != head) { fast = fast->next->next; slow = slow->next; } LIST_HEAD(left); LIST_HEAD(right); list_cut_position(&right, head, slow); list_splice_init(head, &left); q_sort(&left, descend); q_sort(&right, descend); mergeTwoLists(head, &left, &right, descend); } void mergeTwoLists(struct list_head *head, struct list_head *left, struct list_head *right, bool descend) { while (left->next != left && right->next != right) { element_t *left_node = list_entry(left->next, element_t, list); element_t *right_node = list_entry(right->next, element_t, list); if ((strcmp(left_node->value, right_node->value) >= 0 && descend) || (strcmp(left_node->value, right_node->value) <= 0 && !descend)) list_move(left->next, head->prev); else list_move(right->next, head->prev); } if (left->next == left) list_splice_tail(right, head); else list_splice_tail(left, head); } ``` :::danger 既然你選用合併排序演算法，該如何確保測試過程中，涵蓋合併排序的最差情況？ ::: ### `q_ascend` `q_descend` > commit [d654152](https://github.com/tintinjian12999/lab0-c/commit/d654152a3f3525c3bc8eb208bf35bfffb307e3bd) 兩者類似，從序列的尾端往回走訪，只要遇到比當前節點小或大的就刪除即可 ### `q_merge` > commit [79cf9ca](https://github.com/tintinjian12999/lab0-c/commit/79cf9ca6059f39f51dd74eb90a6d561a3c8f9768) 用 list_for_each_entry_safe 走訪儲存序列的 chain ，並透過 list_splice_tail 將各序列接在一起後排序再接回 chain 的第一個節點即可。 --- ## 研讀論文〈Dude, is my code constant time?〉 > [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) ### Student's T Distribution #### z 檢定(z-test)與 t 檢定(t-test) z 檢定與 t 檢定的主要差別有兩個，一個在使用的機率密度函數，z 檢定使用的為常態分配函數，而 t 檢定使用的是 t 分配，也就是 Student's T Distribution ，而另外一個差別在於是否知道母體的標準差，在已知標準差的情形下使用 z 檢定，未知的情形下使用 t 檢定，因此 t 檢定一般用於母體資訊未知的情況下。下圖示常態分配數與 t 分配函數的差別，可以看到當自由度(degree of freedom, df) 越大時， t 分配函數越接近常態分配函數。 ![圖片](https://hackmd.io/_uploads/SkybnMMR6.png) #### 假設檢定 (Hypothesis Testing) 當我們對母體的某個或某幾個參數感興趣時可以運用假設檢定的方法，我們會先定義一個感興趣的問題作為虛無假說(Null Hypothesis) `H0`，與與之相對的對立假說 (Alternative Hypothesis) `Ha`，例如將平均退休年齡 65 歲定義為`H0`，則 `Ha` 可以被定義為平均退休年齡不為 65 歲。 #### 單尾檢定(One-Tailed Test)與雙尾檢定(Two-Tailed Test) 兩者的差異在單尾檢定用來預測具有方向性的假設(如平均退休年齡等於 65 歲或大於 65 歲)，而雙尾檢定不預測方向性(如平均退休年齡等於 65 歲或不等於 65 歲)。 ![圖片](https://hackmd.io/_uploads/S1wQb7z0p.png) #### 顯著水準 (Significance level, $\alpha 為了避免偽陽性與偽陰性的產生 ![圖片](https://hackmd.io/_uploads/HkQlGQGAa.png) 需要定義顯著水準，當檢定統計量(Test statistic) 落在拒絕域時(如圖中藍色部份)則反對假設，反之則接受假設，通常顯著水準的預設值為 0.05。 ![圖片](https://hackmd.io/_uploads/HJXeQXz0p.png) #### 兩獨立樣本的 T 檢定用來檢測兩組獨立樣本之間平均的比較 (如是否相等) 當兩組樣本的變異數不同時檢定統計量為 $T = \frac{\bar{X_A} - \bar{X_B}}{\sqrt{\frac{s_A^2}{n_A} + \frac{s_B^2}{n_B}}}$ #### 論文裡用到的兩群樣本論文裡使用兩群樣本，分別為 fix class (佇列大為 0)，與 random class (n 個相同的隨機字串)，此檢定的 `H0` 為兩群的計算時間相等。 ### 解釋 simulation 做法在 `qtest.c` 裡，當 `simulation` 為 1 的時候，會針對 insert 和 remove 做測試，相關的程式碼被定義在 `fixture` 與 `constant` 中。比較 `fixture.c` 與 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的實作，發現在 `update_statistics` 裡原本的實作 for 迴圈是從 10 開始而 lab0-c 是從 0 開始，於是做了以下修改 ```diff - for (size_t i = 0; i < N_MEASURES; i++) + for (size_t i = 10; i < N_MEASURES; i++) ``` 另一方面，lab0-c 裡也少了關於 percentiles 的實作，在原文裡關於使用 percentiles 的理由如下 >We pre-process measurements prior to statistical processing. We discard measurements that are larger than the p percentile, for various values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise. This (heuristic) process gives good empirical results (makes detection faster); nevertheless we also process measurements without pre-processing. > commit [a58d4bb](https://github.com/tintinjian12999/lab0-c/commit/a58d4bb546760d79886729c0f5a236a709e02fac) ## 加入 Shuffle 命令 ### Fisher–Yates shuffle 首先先取得需要 shuffle 的序列長度 len ，接著隨機從 0 ~ len - 1 間取一個節點，將該節點與最後一個沒被選到的節點交換，再將 len - 1 直到所有節點都被選過。 ```graphviz digraph structs { node[shape=plaintext]; len [label = "len = 5"]; choose [label = "choose = 2"]; new [label = "new"]; old [label = "old"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; struct5 [label= "5"]; head -> struct1 [dir = both]; struct5 -> head [dir = both]; { rank="same" struct1 -> struct2 [dir = both] struct2 -> struct3 [dir = both] struct3 -> struct4[dir = both] struct4 -> struct5[dir = both] } new -> struct2 [color = "red"] old -> struct5 [color = "blue"] } ``` ```graphviz digraph structs { node[shape=plaintext]; len [label = "len = 4"]; choose [label = "choose = 3"]; new [label = "new"]; old [label = "old"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; struct5 [label= "5"]; head -> struct1 [dir = both]; struct2 -> head [dir = both]; { rank="same" struct1 -> struct5 [dir = both] struct5 -> struct3 [dir = both] struct3 -> struct4[dir = both] struct4 -> struct2[dir = both] } new -> struct3 [color = "red"] old -> struct4 [color = "blue"] } ``` ```graphviz digraph structs { node[shape=plaintext]; len [label = "len = 3"]; choose [label = "choose = 1"]; new [label = "new"]; old [label = "old"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; struct5 [label= "5"]; head -> struct1 [dir = both]; struct2 -> head [dir = both]; { rank="same" struct1 -> struct5 [dir = both] struct5 -> struct4 [dir = both] struct4 -> struct3[dir = both] struct3 -> struct2[dir = both] } new -> struct1 [color = "red"] old -> struct4 [color = "blue"] } ``` ```graphviz digraph structs { node[shape=plaintext]; len [label = "len = 2"]; choose [label = "choose = 1"]; new [label = "new"]; old [label = "old"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; struct5 [label= "5"]; head -> struct4 [dir = both]; struct2 -> head [dir = both]; { rank="same" struct4 -> struct5 [dir = both] struct5 -> struct1 [dir = both] struct1 -> struct3[dir = both] struct3 -> struct2[dir = both] } new -> struct4 [color = "red"] old -> struct5 [color = "blue"] } ``` ```graphviz digraph structs { node[shape=plaintext]; len [label = "len = 1"]; old [label = "old"]; nodesep=0.5; node[shape=box]; head [label= "head"]; struct1 [label= "1"]; struct2 [label= "2"]; struct3 [label= "3"]; struct4 [label= "4"]; struct5 [label= "5"]; head -> struct5 [dir = both]; struct2 -> head [dir = both]; { rank="same" struct5 -> struct4 [dir = both] struct4 -> struct1 [dir = both] struct1 -> struct3[dir = both] struct3 -> struct2[dir = both] } old -> struct5 [color = "blue"] } ``` ### 程式碼實作 ```clike int new = rand() % len; struct list_head *new_node = head->next; struct list_head *old_node = finished_node->prev; while (new--) new_node = new_node->next; swap(old_node, new_node); ``` 走訪節點直到遇到選定的節點 (上圖的 new)，接著將它與 old 交換。 >commit [1c28b06](https://github.com/tintinjian12999/lab0-c/commit/1c28b067630224f855ec76cb1c75399113638ee0) ### 統計方法驗證使用 [lab0](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d)的程式測試執行 1000000 次的直方圖如下 ![2024-03-26 18-46-52 的螢幕擷圖](https://hackmd.io/_uploads/S1VnP7gyA.png) 算得的 chi-square sum 為 24.69 ``` chi square sum: 24.68957903326453 ``` 本次測試的自由度為 23 ，在顯著水準為 0.05 的情況下，透過[卡方分佈表](https://passel2.unl.edu/view/lesson/9beaa382bf7e/8) 得到的 P-value 落於 0.5 ~ 0.25 之間，因此虛無假設(shuffle 的結果發生的機率相同，遵守 Uniform distribution)可以成立。 ![圖片](https://hackmd.io/_uploads/r1bVjQg10.png) ## 引入 lib/list_sort.c ### 建立測試環境使用 [perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 用來測試程式的執行時間在 makefile 新增以下指令 ``` measure_time: perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-eg.cmd ``` 以上是量測五次的平均值。輸出結果 ``` Performance counter stats for './qtest -f traces/trace-eg.cmd' (5 runs): 1,894,911 instructions # 0.76 insn per cycle ( +- 0.44% ) 2,545,010 cycles ( +- 7.53% ) 0.001747 +- 0.000172 seconds time elapsed ( +- 9.82% ) ``` 可以看到成功輸出了程式的執行時間與指令數等。 ### 測試 q_sort 透過新增 `trace/trace-measure.cmd` 為序列插入 N 個隨機的字串並排序 ``` new ih RAND N (Replace with any integer) sort ``` 可以將隨機的字串插入序列中並執行排序，因此可以量到以下的數據，以下為量測 20 次的平均值 | Data Size | Avg Time (Sec) | Instructions | Cycles | Cache-misses | | --------- | ------------------ | ------------ | ------ |----------| | 10000 | 0.0149 | 4599662| 33387929 |185,953 (15.695%)| | 50000 | 0.0931 | 230,649,700 | 246,788,232 | 1,211,368(18.744%) | 100000 | 0.2132 |465,927,885|677,900,290|2,998,449(20.672%) | 500000 | 1.1145| 2,381,688,106|3,501,155,212|18,711,535(22.064%) | 1000000 | 2.3273|4,829,427,212|7,797,419,747|41,933,333(23.327%) ### 引入 list_sort > [list_sort](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) #### list_sort.c list_sort.h 新增 likely, unlikely, 並更改函數形式 ```c //list_sort.h #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) struct list_head; typedef int __attribute__((nonnull(1, 2))) (*list_cmp_func_t)(const struct list_head *, const struct list_head *, bool); __attribute__((nonnull(1, 2))) void list_sort(struct list_head *head, list_cmp_func_t cmp, bool descend); __attribute__((nonnull(1, 2))) int cmp(const struct list_head *left, const struct list_head *right, bool descend); ``` 加入考慮 descend 的 cmp 實作 ```c // list_sort.c int cmp(const struct list_head *left, const struct list_head *right, bool descend) { element_t *l_entry = list_entry(left, element_t, list); element_t *r_entry = list_entry(right, element_t, list); if (!descend) return strcmp(l_entry->value, r_entry->value) <= 0 ? 0 : 1; else return strcmp(l_entry->value, r_entry->value) >= 0 ? 0 : 1; } ``` #### qtest.c 在 `qtest.c` 中加入 list_sort 這個指令 ```diff + ADD_COMMAND(list_sort, "Sort queue in ascending/descening order using list_sort", ""); ``` #### makefile ```diff - linenoise.o web.o + linenoise.o web.o \ + list_sort.o ``` >commit [35862e9](https://github.com/tintinjian12999/lab0-c/commit/35862e9a0d29e914bc6e2dcbc47a6f3577d0533e) ### 比較 list_sort 與 q_sort 這裡同樣使用隨機字串來檢測 list_sort 和 q_sort 的差別 #### q_sort | Data Size | Avg Time (Sec) | Instructions | Cycles | Cache-misses | | --------- | ------------------ | ------------ | ------ |----------| | 10000 | 0.0149 | 46,599,662| 33387929 |185,953 (15.695%)| | 50000 | 0.0931 | 230,649,700 | 246,788,232 | 1,211,368(18.744%) | 100000 | 0.2132 |465,927,885|677,900,290|2,998,449(20.672%) | 500000 | 1.1145| 2,381,688,106|3,501,155,212|18,711,535(22.064%) | 1000000 | 2.3273|4,829,427,212|7,797,419,747|41,933,333(23.327%) #### list_sort | Data Size | Avg Time (Sec) | Instructions | Cycles | Cache-misses | | --------- | ------------------ | ------------ | ------ |----------| | 10000 | 0.01467| 44,721,009| 35,772,145 |205,836 (17.746%)| | 50000 |0.0909|223,874,002 |298,621,981 | 1,342,111(22.705%) | 100000 |0.2082|450,904,447|668,628,413 |3,224,686 (25.630%) | 500000 |1.01472|2,309,174,784 |3,326,974,705|19,355,354 (28.073%) | 1000000 | 2.1600|4,662,032,772|7,207,388,913 |43,796,683 (30.023 目前觀察不到明顯的差異，需要回去琢磨 list_sort 的實作，並增加不同的資料分佈(如故意去測試最差狀況而非隨機生成字串)。 >TODO: 閱讀並理解 list_sort 程式碼 ## 整合網頁伺服器 ### 問題在 `console.c` 中，可以發現在呼叫 `do_web` 的時候會將 `use_linenoise` 設為 false。這會導致在使用 web 功能時會沒辦法執行 [linenoise](https://github.com/antirez/linenoise) 的功能，如 completion。此時如果強制將 ```c use_linenoise = false ``` 註解掉的話，會發現無法成功透過網頁發送命令，根據[作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c)，這是因為 linenoise 使用 read 讀取使用者輸入，當它被阻塞時就無法接收網頁傳送的資訊。 ### select >[select](https://man7.org/linux/man-pages/man2/select.2.html) 跟據 man 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. select 可以用來管理多個檔案描述子，可以用來避免阻塞。 * fd_set 一個用來存放多個檔案描述子的資料型態，其上限被 `FD_SETSIZE` 決定。 * FD_ZERO 用來對 fd_set 初始化。 * FD_SET 將新的檔案描述子加入 fd_set 之中。 * FD_CLR 將檔案描述子移出 fd_set。 * FD_ISSET 用來測試檔案描述子是否還在 fd_set 裡。 * 返回值：返回 fd_set 裡檔案描述子的數量，0 代表超過時間上限，-1 代表 error 發生。從 `web.c` 可以知道 `web_open` 會回傳檔案描述子 `listenfd` 到 `console.c` 裡的變數 `web_fd` 發現在 `cmd_select` 裡其實已經有針對 `stdin` 跟 `web socket` 做 select 的處理了，但觀察到在 `run_console` 裡如果 `use_linenoise` 為真的話，則會先呼叫 `linenoise` 的處理才會執行 `cmd_select`。推測阻塞是發生在 `linenoise` 相關的實作裡。觀察 `linenoise.c` 的程式碼會發現其只有針對 `stdin` 做處理，在 `line_raw` 的註解裡提到 ```c /* This function calls the line editing function line_edit() using * the STDIN file descriptor set in raw mode. */ ``` 並且在呼叫 `line_edit`裡的實作只有傳入 `stdin` 的檔案描述子 ```c int count = line_edit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt); ``` > TODO: 閱讀 CSAPP:11章 ## tic-tac-toe ### 決策方法 #### 蒙地卡羅樹 (MCTS) 蒙地卡羅樹會先進行事件(如遊戲)的模擬，並將模擬結果儲存在一個樹裡面，再根據模擬的結果進行決策。蒙地卡羅樹的過程大致有 Selection, Expansion, Simulation, Backpropagation. ##### Selection 在這個階段，會使用 Upper Confidence Bound(UCB) 公式來計算所有可能步驟的權重，並決定下一個步驟，UCB 的形式如下 $$ UCB = \frac{w_i}{n_i}+C\sqrt{\frac{lnN_i}{n_i}} $$ 其中 $w_i$ 為勝利獲得的分數，$n_i$為該步驟模擬的次數，$C$為常數，$N_i$為親代節點模擬的次數。 UCB 方法實際上是 exploitation 跟 exploration 之間權衡的結果，前半段 $\frac{w_i}{n_i}$ 代表的是勝率，後半段代表的是這個步驟被選擇的次數，我們希望選擇勝率高步驟的同時不要一直選擇同一個步驟，這樣做可以避免陷入局部最佳解的問題。 ##### Expansion 從現有步驟開始決定下一個步驟，並將其加入樹讓它變成子節點。 ##### Simulation 如果步驟是初次探索(選定的節點 $n_i$ = 0)，則透過隨機決策模擬遊戲直到終局，如此可以得到這條路徑的勝利分數。 ##### Backpropagation 從終局的成績開始往回更新 $w_i$ 直到回到樹的 root。 ##### 範例 ![圖片](https://hackmd.io/_uploads/rkRLo8nAT.png) 假設一個節點有兩項參數 ```graphviz digraph structs { node[shape=circle]; S_0 [label= "Si w_i/n_i"]; } ``` ```graphviz digraph structs { node[shape=plaintext]; iter [label = "i = 0"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 0/0"]; } ``` 首先進行 expansion(無須進行 selection 因為此時兩節點 UCB 的值皆為無限大) ```graphviz digraph structs { node[shape=plaintext]; oper [label = "expansion(假設有兩種可能步驟)"] iter [label = "i = 1"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 0/0"]; S_1 [label= "S1 0/0"]; S_2 [label= "S2 0/0"]; { S_0->S_1 S_0->S_2 } } ``` 接著對 S1 進行 simulation ```graphviz digraph structs { node[shape=plaintext]; oper [label = "simulation(假設勝利分數為 20)"] iter [label = "i = 1"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 20/1"]; S_1 [label= "S1 20/1"]; S_2 [label= "S2 0/0"]; { S_0->S_1 S_0->S_2 } } ``` 對 S2 進行 simulation ```graphviz digraph structs { node[shape=plaintext]; oper [label = "simulation(假設勝利分數為 10)"] iter [label = "i = 2"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 30/2"]; S_1 [label= "S1 20/1"]; S_2 [label= "S2 10/1"]; { S_0->S_1 S_0->S_2 } } ``` 接著計算兩者的 UCB(假設 C = 2) UCB(S1) = 21.67 UCB(S2) = 11.67 明顯 UCB(S1) > UCB(S2)，因此 select S1 進行 expansion ```graphviz digraph structs { node[shape=plaintext]; oper [label = "expansion"] iter [label = "i = 3"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 30/2"]; S_1 [label= "S1 20/1"]; S_2 [label= "S2 10/1"]; S_3 [label= "S3 0/0"]; S_4 [label= "S4 0/0"]; { S_0->S_1 S_0->S_2 S_1->S_3 S_1->S_4 } } ``` 對 S3 進行 simulation ```graphviz digraph structs { node[shape=plaintext]; oper [label = "simulation(假設勝利分數為0)"] iter [label = "i = 3"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 30/3"]; S_1 [label= "S1 20/2"]; S_2 [label= "S2 10/1"]; S_3 [label= "S3 0/1"]; S_4 [label= "S4 0/0"]; { S_0->S_1 S_0->S_2 S_1->S_3 S_1->S_4 } } ``` 計算 S1 和 S2 的 UCB UCB(S1) = 11.48 UCB(S2) = 12.10 明顯 UCB(S2) > UCB(S1)，因此 select S2 進行 expansion ```graphviz digraph structs { node[shape=plaintext]; oper [label = "expansion"] iter [label = "i = 4"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 30/3"]; S_1 [label= "S1 20/2"]; S_2 [label= "S2 10/1"]; S_3 [label= "S3 0/1"]; S_4 [label= "S4 0/0"]; S_5 [label= "S5 0/0"]; S_6 [label= "S6 0/0"]; { S_0->S_1 S_0->S_2 S_1->S_3 S_1->S_4 S_2->S_5 S_2->S_6 } } ``` 對 S5 進行 simulation ```graphviz digraph structs { node[shape=plaintext]; oper [label = "simulation(假設勝利分數為 15)"] iter [label = "i = 4"] nodesep=0.5; node[shape=circle]; S_0 [label= "S0 45/4"]; S_1 [label= "S1 20/2"]; S_2 [label= "S2 25/2"]; S_3 [label= "S3 0/1"]; S_4 [label= "S4 0/0"]; S_5 [label= "S5 15/1"]; S_6 [label= "S6 0/0"]; { S_0->S_1 S_0->S_2 S_1->S_3 S_1->S_4 S_2->S_5 S_2->S_6 } } ``` 如果我們將迭代止步於此的話，則會選擇 value 較大的路徑，也就是 S0 -> S2 -> S5 這條。 #### Negamax ### 引入 ttt 這裡要將 tic-tac-toe 引入 lab0-c ，並且使用的是 MCTS 的方法，將 ttt 裡的檔案複製過來並且在 qtest 中加入命令 ttt ，且 makefile 也要加入以下指令 ```diff + game.o mt19937-64.o zobrist.o agents/mcts.o ``` >commit [69b27a2](https://github.com/tintinjian12999/lab0-c/commit/69b27a20c43e6cffaaf6ff2942b71b32ca21150f) ### AI vs AI 利用 `add_param` 在 qtest 中加入新的 option ```c add_param("AI", &AI, "Let the computer play ttt with them self.", NULL); ``` 剩餘的實作在 >commit [5fb86be](https://github.com/tintinjian12999/lab0-c/commit/5fb86beeabe39373e178368a0f6f47b6bc680314) 並在 do_ttt 中加入判斷式 `if(!AI)` 在終端機使用 ``` ./qtest option AI 1 ``` 即可開啟 AI vs AI 模式，此時執行 `ttt` 就會是電腦 VS 電腦。並且可以透過 `rand()` 來隨機取得初始步驟增加遊戲的隨機性 ```c int move = rand() % N_GRIDS; ``` >commit [74d3bc7](https://github.com/tintinjian12999/lab0-c/commit/74d3bc774ad2c8b51d849667b4b5ac977cdbe7a5) ### 定點數數值系統 #### 什麼是定點數？顧名思義，相較於浮點數，定點數指的是小數點位置固定的數(如整數)，由於某些處理器可能沒有 FPU，且浮點數運算在某些情況下會慢於定點數運算(見[浮點數運算和定點數操作](https://hackmd.io/@NwaynhhKTK6joWHmoUxc7Q/H1SVhbETQ?type=view))，因此利用整數來表達浮點數運算，在 Linux 核心許多運算都使用定點數。以 16 位元為例，16位元的有號整數表示為 ```graphviz digraph { node [shape = record]; node0 [fontsize=13, label ="signed|2^14|2^13|2^12|2^11|2^10|2^9|2^8|2^7|2^6|2^5|2^4|2^3|2^2|2^1|<f0>2^0"]; head [label="Decimal"]; head -> node0:f0; } ``` 此時的小數點在 $2^0$以後，此時只能表示整數而不能表示小數。 ```graphviz digraph { node [shape = record]; node0 [fontsize=13, label ="signed|2^7|2^6|2^5|2^4|2^3|2^2|2^1|<f0>2^0|2^-1|2^-2|2^-3|2^-4|2^-5|2^-6|2^-7"]; head [label="Decimal"]; head -> node0:f0; } ``` 如果我們將小數點左移 7 個 bits，也就是用 8 個位元表示整數， 7 個位元表示小數，此時數值的最小解析度為 $2^-7$ ，因此可以用來表示小數。也因此，透過以下的巨集可以簡單的完成整數到定點數的轉換 ```c #define int2fix(a) ((fixed_point_t))((a) << FRACTION_BITS)) #define fix2int(a) ((int))((a >> FRACTION_BITS)) ``` 定義結構 fixed_point_t ```c typedef long fixed_point; ``` 如果想要取出定點樹的整數部分只要使用 `fix2int` 將數值右移 `FRACTION_BITS` 個位元即可。那如果要取出小數部分呢? 以 `0001 1100` 為例，也就是十進位的 1.75 ，我們可以透過 ```c #define extract_frac(a) (int)(a & (int2fix(1) - 1)) ``` 來取出小數部分，在用 8 個 bit 表示全部數值、而用 4 個 bit 表小數部分的情況下，`int2fix(1)` 得到的結果為 `0001 0000` 因此 `int2fix(1) - 1` 為 `0000 1111`，將其和數值 `0001 1100` 做且運算就能得到 `0000 1100` ，也就是定點數裡小數的部分。但如果我們把他直接以十進位表示的話，得到的答案會是 12，而我們想要的結果是 `0.75`，或者說 `75`。因此需要以下轉換式 ```c #define frac2int(a) (int)((a * 1000) >> FRACTION_BITS) ``` 其實想法很簡單，`1100` 視為定點數的小數部分的話其代表的值為 $$\frac{1}{2} + \frac{1}{2^2} = 0.75$$ 但實際電腦看到的是左移 `FRACTION_BITS`後的結果，也就是$$2^3 + 2^2 = 12$$因此只需要將 `12` 右移 `FRACTION_BITS` 個位元就可以得到 0.75，但因為這裡我們想要使用整數來表達他的數值，所以需要先乘以 100 (取整到小數第二位)，上述運算的結果會是 75。定點數的四則運算裡只有除法需要被特別注意，因為實際上在運算時是以整數型態運算，因此在作諸如 `2 / 3` 等的運算時會出現 0 ，因此在實作上需要先將分子作 Scaling，除完後再還原，如下 ```c fixed_point_t fixed_div(fixed_point_t a, fixed_point_t b) { fixed_point_t result = (a << FRACTION_BITS) / b; result = int2fix(result); result >>= FRACTION_BITS; return result; } ``` :::info 問題: 目前遇到小數第一位為 0 的數值會有問題，如 $\frac{1}{16}$的結果為 0.62 而非 0.062。此問題目前觀察發生於 (a * 1000) >> FRACTION_BITS 這個操作，以 $\frac{1}{8}$ 為例，$\frac{1 * 1000}{8} = 125$而 $\frac{1 * 1000}{16} = 62.5$，可預期此錯誤發生於 1000 除以除數小於 100 或 10 的時候發生，但此問題對於計算結果不會造成影響。 ::: #### MCTS 裡的浮點數運算觀察 `mcts.c` 與 `mcts.h` 我們需要替換所有 `double` 型態的變數和與之相關的操作，並且在 UCB 計算時需要用到 `sqrt` 與 `log`，以下需要探討相關的作法 ##### sqrt 從數學上來看，sqrt(a) 其實就是在求 $x^2 - a = 0$ 這個函數的根，因此可以考慮使用[牛頓法](https://en.wikipedia.org/wiki/Newton%27s_method)求根。先設定精確度為 ```c // 1 / 2 ^ 10 = 0.000976 #define eps int2fix(1) >> 10 ``` 接著使用牛頓法求根 ```c fixed_point_t fixed_sqrt(fixed_point_t a) { fixed_point_t value = a; fixed_point_t last; while (abs(value - last) > eps) { last = value; value = (value + fixed_div(a, value)) >> 1; } return value; } ``` 使用以下程式可以測試浮點數求出的方根與定點數求出方根的差別 ```c int main() { FILE *file; file = fopen("compare.txt", "w"); if (file == NULL) { printf("無法打開檔案。\n"); return 1; } for (int i = 1; i < 1001; i++) { fixed_point_t result = 0; result = fixed_sqrt(int2fix(i)); int frac = frac2int(extract_frac(result)); float result_float = 0; result_float = sqrt(i); fprintf(file, "%d %d.%d %.3f \n", i, fix2int(result), frac, result_float); } fclose(file); } ``` 結果如下 ![compare](https://hackmd.io/_uploads/HyQqtWVe0.png) 可以看到除了些許點的不同外，其他的部份都與浮點數一致，而造成部份值不同的原因是上述在 "問題" 裡提到的在擷取小數部份時如果 1000 除以除數小於 100 時會發生的問題，例如 `sqrt(26)` 的實際值為 5.099 ，而定點數計算的結果為 5.098，但因為在擷取小數時發生以上的錯誤導致紀錄的值為 5.98，此問題在作計算時不會造成影響。使用誤差可以更精確的看出定點數運算與浮點數運算的關係 ![compare](https://hackmd.io/_uploads/Hy0fabNl0.png) 可以看出最大的誤差約為 0.06 % 若進一部增加小數部份的位元數由 10 位元增加到 16 位元 ```diff - #define FRACTION_BITS 10 + #define FRACTION_BITS 16 ``` 能夠進一步將誤差縮小至 0.03 % 以下。 ![compare](https://hackmd.io/_uploads/SJSi0-NeA.png) commit [05b9a4e](https://github.com/tintinjian12999/lab0-c/commit/05b9a4ecd9fe3b335228a0c5e7457d5ed3eb463e) ##### log 這裡的 log 是以自然底數 $e$ 為底的對數，最直觀的作法是透過[泰勒展開式](https://en.wikipedia.org/wiki/Taylor_series)計算，但參考 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1#%E5%AE%9A%E9%BB%9E%E6%95%B8%E5%AF%A6%E4%BD%9C)的作法後發現有更簡潔的作法，參考論文 [A Fast Binary Logarithm Algorithm](http://www.claysturner.com/dsp/binarylogarithm.pdf) 將以二為底的對數求出來後再使用換底公式即可求出自然對數。得到的誤差如下 ![compare](https://hackmd.io/_uploads/BJOys8NgR.png) 可以看到會有大約 5% 左右的誤差 commit [34585a4](https://github.com/tintinjian12999/lab0-c/commit/34585a4510c46584333fd13641f1b144b499a816) >TODO: 待解決 ##### 將定點數整合進 mcts.c 將 `MCTS.c`, `game.c` 等檔案內有關浮點數運算的部份轉為使用定點數運算即可 commit [e8676a3](https://github.com/tintinjian12999/lab0-c/commit/e8676a300855926b16299187b5c8e17f9a4532c9) #### coroutine 參考 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) ，透過在 `task_switch` 裡面加入 ```c struct task *tt; printf("task_list is "); list_for_each_entry(tt, &tasklist, list) { printf("-> %s ", tt->task_name); } printf("\n"); ``` 可以更好的看出 `tasklist` 變化的過程 ``` Task 0: n = 70 Task 1: n = 70 Task 2: n = 70 task_list is -> Task 0 -> Task 1 -> Task 2 Task 0 fib(0) = 0 task_list is -> Task 1 -> Task 2 -> Task 0 Task 1 fib(1) = 1 task_list is -> Task 2 -> Task 0 -> Task 1 Task 2 0 task_list is -> Task 0 -> Task 1 -> Task 2 Task 0: resume Task 0 fib(2) = 1 task_list is -> Task 1 -> Task 2 -> Task 0 Task 1: resume Task 1 fib(3) = 2 task_list is -> Task 2 -> Task 0 -> Task 1 Task 2: resume ``` 的確是 FIFO。從 ```c if (!list_empty(&tasklist)) { struct task *t = list_first_entry(&tasklist, struct task, list); list_del(&t->list); cur_task = t; longjmp(t->env, 1); } ``` 與 ```c task = cur_task; for (; task->i < task->n; task->i += 2) { if (setjmp(task->env) == 0) { long long res = fib_sequence(task->i); printf("%s fib(%d) = %lld\n", task->task_name, task->i, res); task_add(task); task_switch(); } task = cur_task; printf("%s: resume\n", task->task_name); } ``` 可以看出 `cur_task` 的存在是為了用來儲存 `task` 的狀態。透過改寫以上的程式可以將 ttt 改寫成使用 coroutine 執行的版本 commit[1ac5a61](https://github.com/tintinjian12999/lab0-c/commit/1ac5a611cbbd53a3f80d5d5ac241bf69a2fa794d) ##### 鍵盤監聽事件參考 [Build Your Own Text Editor](https://viewsourcecode.org/snaptoken/kilo/) 監聽鍵盤的輸入，如果為 CTRL-Q 則跳至 `task_switch()` 並中止程式。 ```c c_read = editorReadKey(); if (c_read == CTRL_KEY('c')) task_switch(); ``` ```c static void task_switch() { if (c_read == CTRL_KEY('q')) { exit(0); } if (!list_empty(&tasklist)) { struct task *t = list_first_entry(&tasklist, struct task, list); list_del(&t->list); cur_task = t; longjmp(t->env, 1); } } ``` commit [0293387](https://github.com/tintinjian12999/lab0-c/commit/0293387b25b6358af4f966c4cf3f9ca5d24add63)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.