# 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，程式碼可以如何改寫？

if (CAS(tail, self)) {
    CAS(...) // for same tail and head.
} else {
    head = LOAD()
    while (...) {
        ...check if new head
    }
}

針對[第十五週的測驗](https://hackmd.io/@sysprog/linux2022-quiz15)

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 比較小就會停下，因此這個程式是有錯的。考慮以下情況：

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` 繼續往上檢查。如下：

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)