# 2022q1 第 13/14/15 週課程問答簡記 ## Kelvin [memory pool](https://en.wikipedia.org/wiki/Memory_pool) lab0: insert_head, remove (斷開節點間的連結), delete (真正釋放記憶體的操作) ## Uduru0522 circular buffer 程式碼如何確保 thread-safe? ## kdnvt 針對 mpscq 的 pop,若用 CAS,程式碼可以如何改寫? ```c= if (CAS(tail, self)) { CAS(...) // for same tail and head. } else { head = LOAD() while (...) { ...check if new head } } ``` 針對[第十五週的測驗](https://hackmd.io/@sysprog/linux2022-quiz15) ```graphviz digraph BST { node [fontname="Arial" ]; l1 [ label = "1" ]; l21 [ label = "2" ]; l22 [ label = "3" ]; l31 [ label = "4" ]; l32 [label = "5" ]; l33 [color=red shape=rect label = "6" ]; l34 [color=red shape=rect label = "7" ]; l41 [color=blue shape=rect label = "8" ]; l42 [color=blue shape=rect label = "9" ]; l43 [color=blue shape=rect label = "10" ]; l1 -> { l21 l22 }; l21 -> { l31 l32 }; l22 -> { l33 l34 }; l31 -> { l41 l42 }; l32 -> { l43} } ``` 我認為 `void minheap_init(unsigned long nr_items, struct heap_item *h)` 是想要對 leaf 做 `do_sift_up` 。第一個 for 迴圈是對最底層的藍色節點,第二個 for 迴圈則是對倒數第二層的紅色節點。因為 heap 的結構是 complete binary ,所以 leaf 一定在這兩層。但是因為 `do_sift_up` 只要遇到 parent 比較小就會停下,因此這個程式是有錯的。考慮以下情況: ```graphviz digraph BST { node [fontname="Arial" ]; l1 [ label = "100" ]; l21 [ label = "2" ]; l22 [ label = "3" ]; l31 [ label = "4" ]; l32 [label = "5" ]; l33 [color=red shape=rect label = "6" ]; l34 [color=red shape=rect label = "7" ]; l41 [color=blue shape=rect label = "8" ]; l42 [color=blue shape=rect label = "9" ]; l43 [color=blue shape=rect label = "10" ]; l1 -> { l21 l22 }; l21 -> { l31 l32 }; l22 -> { l33 l34 }; l31 -> { l41 l42 }; l32 -> { l43} } ``` 因為初始化的過程中所有 leaf 的 parent 都比較小,因此最上面的 100 不會被動到。 要修正程式其中一個辦法是讓 `do_sift_up` 繼續往上檢查。如下: ```c static void do_sift_up(unsigned long idx, unsigned long nr_items, struct heap_item *h) { assert(idx > 0); if (idx == 1) return; uint64_t v = h[idx].key; unsigned long pidx = parent(idx); uint64_t pv = h[pidx].key; if (pv < v){ do_sift_up(pidx, nr_items, h); return; } struct heap_item tmp = h[pidx]; h[pidx] = h[idx]; h[idx] = tmp; do_sift_up(pidx, nr_items, h); } ``` 但這樣會加重 heap 的操作成本,因此我認為較好的方法還是對第一個以外的所有節點都做原版的 `do_sift_up` 。或是寫兩個版本的 `do_sift_up` ,在初始化時使用沉重版本,並在一般操作時使用原版。 ## Kelvin [2022q1 quiz15](https://hackmd.io/@cantfindagoodname/linux2022-quiz15)