2022q1 第 13/14/15 週課程問答簡記

Kelvin

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
    }
}

針對第十五週的測驗

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

因為初始化的過程中所有 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