2023q1 Homework4 (quiz4)

--- title: 2023q1 Homework4 (quiz4) tags: Linux核心設計 --- # [2023q1 Homework4 (quiz4)](https://hackmd.io/@sysprog/linux2023-quiz4) ## [測驗一](https://hackmd.io/@sysprog/linux2023-quiz4#%E6%B8%AC%E9%A9%97-1) ### 程式碼原理 ### 答案 :::success * `AAAA = ` * `BBBB = ` * `CCCC = ` * `DDDD = ` * `EEEE = ` * `FFFF = ` * `GGGG = ` ::: --- ## [測驗二](https://hackmd.io/@sysprog/linux2023-quiz4#%E6%B8%AC%E9%A9%97-2) ### Timsort 原理 [原始程式碼](https://gist.github.com/jserv/2ef9c2c6c274ff738f928f4e5af493a3) [Timsort](https://zh.wikipedia.org/wiki/Timsort) 是混合 `insertion sort` 與 `merge sort` 的 stable 排序演算法，主要原理是將資料分割成小區塊 `runs`，將這些 `runs` 用 `insertion sort` 排序，最後將這些 `runs` 用 `merge sort` 合併。 ### merge_rule `Timsort` 會將 `runs` 放入堆疊中，為了達到 balanced merges，也就是合併時兩個 `runs` 大小差不多，所以限制當 `top-2` 的 `run` 比 `top` 的 `run` + `top-1` 的 `run` 的長度較大時，才能合併。 $i:|Z| > |Y| + |X|$ $ii:|Y| > |X|$ ![](https://i.imgur.com/tn8YC0o.png) ```c return run_length(stack[top]) > run_length(stack[top - 1]) || run_length(stack[top]) + run_length(stack[top - 1]) > run_length(stack[top - 2]); ``` ### next_partition 這裡主要是將資料分割成 `runs` ，去計算 `runs` 的數量，因為需要所有的 `runs` 都是遞增的，所以會判斷是否為遞增的序列，若不是，則將該 `runs` 反轉成遞增的序列。 ```c if (cmp(cur, next)) { while (next < last && cmp(cur, next)) { ++run_len; cur += size; next += size; } } else { while (next < last && !cmp(cur, next)) { ++run_len; cur += size; next += size; } __reverse(first, next, size); } ``` 若是 `run` 的長度小於 `MIN_RUN` ，則會用 `insertion sort` 去排序，當長度短且為排序過的序列，用 `insertion sort` 的效率會較好。 ```c if (next < last && run_len < MIN_RUN) { last = first + MIN_RUN * size < last ? DDDD : last; __insertion_sort(first, last, size, cmp); return (last - first) / size; } ``` ### merge * merge 這個函式就是將兩個 `runs` 進行合併。 * inplace_merge 會有多一個 `inplace_merge` 函式，主要是因為當一個 `run` 裡面包含兩個不同的 `run` 時，不需要額外的空間來儲存合併後的 `run` ，實作起來會較為簡單。首先初始狀態會宣告兩個變數 `cur1, cur2` 分別指向 `first1, first2` 。 ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> cur1/first1 | <f2> last1 | <f1> cur2/first2 | <f3> last2", color=white]; values [label="<f0> 1 | <f1> 3 | <f2> 6 | <f3> 7 | <f4> 2 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; } ``` 再來先將 `cur1` 右移，找出第一個 `> cur2` 的值，也就是找出小區塊 `1, 3`。 ```c while (cur_1 < last_2 && !cmp(cur_2, cur_1)) cur_1 += size; ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> first1 | <f4> cur1 | <f2> last1 | <f1> cur2/first2 | <f3> last2", color=white]; values [label="<f0> 1 | <f1> 3 | <f2> 6 | <f3> 7 | <f4> 2 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; } ``` 再將 `cur2` 右移，找出第一個 `> cur1` 的值，也就是找出小區塊 `2, 4`。 ```c while (cur_2 < last_2 && cmp(cur_2, cur_1)) cur_2 += size; ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> first1 | <f4> cur1 | <f2> last1 | <f1> first2 |<f5> cur2| <f3> last2", color=white]; values [label="<f0> 1 | <f1> 3 | <f2> 6 | <f3> 7 | <f4> 2 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; pointers:f5 -> values:f5; } ``` 最後進行 3 次 `reverse`，第一次做 `cur1` 到 `first_2 - 1` 的 `reverse` 。 ```c __reverse(cur_1, first_2, size); ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> first1 | <f4> cur1 | <f2> last1 | <f1> first2 |<f5> cur2| <f3> last2", color=white]; values [label="<f0> 1 | <f1> 7 | <f2> 6 | <f3> 3 | <f4> 2 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; pointers:f5 -> values:f5; } ``` 第二次做 `first_2` 到 `cur_2 - 1` 的 `reverse` 。 ```c __reverse(first_2, cur_2, size); ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> first1 | <f4> cur1 | <f2> last1 | <f1> first2 |<f5> cur2| <f3> last2", color=white]; values [label="<f0> 1 | <f1> 7 | <f2> 6 | <f3> 3 | <f4> 2 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; pointers:f5 -> values:f5; } ``` 第三次做 `cur_1` 到 `cur_2 - 1` 的 `reverse` 。 ```c __reverse(cur_1, cur_2, size); ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f0> first1 | <f4> cur1 | <f2> last1 | <f1> first2 |<f5> cur2| <f3> last2", color=white]; values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 6 | <f4> 7 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f0; pointers:f1 -> values:f4; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; pointers:f5 -> values:f5; } ``` 最後移動 `first_1, first_2` ，再開始新的一輪直到合併成一個 `run` 。 ```c first_1 = cur_1 + (cur_2 - first_2); first_2 = cur_2; ``` ```graphviz digraph { node [shape=plaintext, fontcolor=black, fontsize=16]; "Pointers:" -> "Values:" [color=white]; node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; pointers [label="<f4> cur1 | <f0> first1 | <f2> last1 | <f1> first2/cur2| <f3> last2", color=white]; values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 6 | <f4> 7 | <f5> 4 | <f6> 5 | <f7> 8"]; { rank=same; "Pointers:"; pointers } { rank=same; "Values:"; values } edge [color=black]; pointers:f0 -> values:f2; pointers:f1 -> values:f5; pointers:f2 -> values:f3; pointers:f3 -> values:f7; pointers:f4 -> values:f1; } ``` ### 答案 :::success * `AAAA = __reverse(cur_1, cur_2, size)` * `BBBB = top - 1` * `CCCC = top - 2` * `DDDD = first + MIN_RUN * size` * `EEEE = top--` * `FFFF = top++` * `GGGG = stack[top-1].last = stack[top].last` ::: --- ## [測驗三](https://hackmd.io/@sysprog/linux2023-quiz4#%E6%B8%AC%E9%A9%97-3) ### 程式碼原理 ### RB_LOG2_MAX_NODES 在 process 中，最多有 `1 << (sizeof(void *) << 3) / sizeof(rb_node(x_type)).` 個節點，所以 `RB_LOG2_MAX_NODES` 就是上式取 log ，也就是： $log$(1 << (sizeof(void *) << 3) / sizeof(rb_node(x_type))) = $log$(1 << (sizeof(void *) << 3) - $log$(sizeof(rb_node(x_type))) = RB_LOG2_MAX_MEM_BYTES - $log$(sizeof(rb_node(x_type))) 所以 $log$(sizeof(rb_node(x_type))) 就等於下式 ```c sizeof(void *) >= 8 ? 4 : sizeof(void *) >= 4 ? 3 : 2 - 1 ``` ### sum_subtree 範例輸入為：7, 11, 1, 99, 22, 33, 44, 9, 3, 5 ![](https://hackmd.io/_uploads/S1P2SKUV2.png) 判斷若是左節點沒有子節點，表示為最左節點，最左節點是最小的值，則印出。 ```c if (!rbtn_left_get(node_t, link, node)) goto do_print; ``` 這裡利用左節點的最右子節點來紀錄前一個較大的節點，於是下個迴圈會輸出最小的節點，然後進到 for 迴圈內就會判斷是否要透過剛剛紀錄的值回到最小節點的前一個節點，再將用來紀錄的最右子節點設成 `NULL`。 ```c for (pre = rbtn_left_get(node_t, link, node); rbtn_right_get(node_t, link, pre) && rbtn_right_get(node_t, link, pre) != node; pre = rbtn_right_get(node_t, link, pre)){} if (!rbtn_right_get(node_t, link, pre)) { rbtn_right_get(node_t, link, pre) = node; node = rbtn_left_get(node_t, link, node); } else { rbtn_right_get(node_t, link, pre) = NULL; do_print: result += node->value; printf("value: %d\n", node->value); node = rbtn_right_get(node_t, link, node); } ``` ### 答案 :::success * `HHHH = 3` * `IIII = 2` * `JJJJ = rbtn_left_get` * `KKKK = rbtn_right_get` * `LLLL = rbtn_right_get` :::

Read more

2023q1 Homework1 (lab0)

2023q1 Linux核心設計-問題紀錄

2023q1 Homework6 (quiz5)

2023q1 Homework5 (Assessment)