2022q1 第 15 週測驗題

tags: linux2022

目的: 檢驗學員對 針對事件驅動的 I/O 模型演化 和 bitwise 操作 的認知

作答表單:

• 測驗 1 (Linux 核心設計)

測驗 1

在作業 seHTTPd 和 高效 Web 伺服器開發 論及 HTTP 連線管理時，Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下，遇到客戶端網路離線，通訊協定無法立刻知悉，所以僅能透過伺服器引入 timer 逾時事件來克服。timer 可透過 priority queue 實作，後者又常用 binary heap 實作。

Priority Queue：Binary Heap

以下是 min heap 的一個實作:

#include <assert.h>
#include <inttypes.h>
#include <stdint.h>

struct heap_item {
    uint64_t key;
};

#if __WORDSIZE == 64
#define clz64(x) __builtin_clzl(x)
#define clz32(x) __builtin_clz(x)
#define log2_floor(x) log2_floor64(x)
#elif __WORDSIZE == 32
#define clz64(x) __builtin_clzll(x)
#define clz32(x) __builtin_clzl(x)
#define log2_floor(x) log2_floor32(x)
#else
#error "Bad machine word size"
#endif

static inline unsigned int log2_floor64(uint64_t val)
{
    return 64 - (clz64(val) + 1);
}

static inline unsigned int log2_floor32(uint32_t val)
{
    return 32 - (clz32(val) + 1);
}

static inline unsigned long parent(unsigned long idx)
{
    return idx >> 1;
}

static inline unsigned long left(unsigned long idx)
{
    return idx << 1;
}

static inline unsigned long right(unsigned long idx)
{
    return (idx << 1) + 1;
}

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 (UUUU)
        return;

    struct heap_item tmp = h[pidx];
    h[pidx] = h[idx];
    h[idx] = tmp;
    do_sift_up(pidx, nr_items, h);
}

static void do_sift_down(unsigned long idx,
                         unsigned long nr_items,
                         struct heap_item *h)
{
    unsigned long l = left(idx);
    if (l > nr_items)
        return;

    unsigned long r = right(idx);
    unsigned long smallest;
    if (r > nr_items) {
        smallest = l;
    } else {
        smallest = h[l].key < h[r].key ? l : r;
    }

    if (DDDD)
        return;

    struct heap_item tmp = h[smallest];
    h[smallest] = h[idx];
    h[idx] = tmp;
    do_sift_down(smallest, nr_items, h);
}

void minheap_init(unsigned long nr_items, struct heap_item *h)
{
    unsigned long lf = log2_floor(nr_items);
    unsigned long f = (1 << lf) - 1, c = (1 << lf);

    for (unsigned long i = f; i < nr_items; i++)
        do_sift_up(i + 1, nr_items, h);

    c = (c - (nr_items - f)) >> 1;
    for (unsigned long i = parent(nr_items); i < parent(nr_items) + c; i++)
        do_sift_up(i + 1, nr_items, h);
}

void minheap_sift_down(unsigned long nr_items, struct heap_item *h)
{
    do_sift_down(1, nr_items, h);
}

void minheap_sift_up(unsigned long nr_items, struct heap_item *h)
{
    do_sift_up(nr_items, nr_items, h);
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void print_heap(unsigned long nr_items, struct heap_item *h)
{
    for (unsigned long i = 0; i < nr_items; i++)
        printf("%" PRId64 " ", h[i + 1].key);
    printf("\n");
}

static unsigned int xs;
/* 16-Bit Xorshift Pseudorandom Numbers.
 * http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html
 */
static inline unsigned int xorshift()
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}

int main(int argc, char **argv)
{
    unsigned long nr = atoi(argv[1]);
    struct heap_item *h = calloc(nr, sizeof(*h));
    h--;

    xs = getpid();
    for (unsigned long i = 0; i < nr; i++)
        h[i + 1].key = xorshift() & 127;
    printf("init: ");
    print_heap(nr, h);

    minheap_init(nr, h);
    printf("heapified: ");
    print_heap(nr, h);

    while (nr) {
        printf("%" PRId64 ": ", h[1].key);
        h[1] = h[nr--];
        minheap_sift_down(nr, h);
        print_heap(nr, h);
    }

    printf("\n");

    h[++nr].key = 100;
    minheap_sift_up(nr, h);

    h[++nr].key = 300;
    minheap_sift_up(nr, h);

    h[++nr].key = 200;
    minheap_sift_up(nr, h);

    while (nr) {
        printf("%" PRId64 ": ", h[1].key);
        h[1] = h[nr--];
        minheap_sift_down(nr, h);
        print_heap(nr, h);
    }
    return EXIT_SUCCESS;
}

參考執行輸出: (前 10 個數值可能會變化)

$ ./minheap 10
init: 95 62 66 71 36 34 67 30 72 82 
heapified: 30 95 34 62 36 66 67 71 72 82 
30: 34 95 66 62 36 82 67 71 72 
34: 66 95 67 62 36 82 72 71 
66: 67 95 71 62 36 82 72 
67: 71 95 72 62 36 82 
71: 72 95 82 62 36 
72: 36 95 82 62 
36: 62 95 82 
62: 82 95 
82: 95 
95: 

100: 200 300 
200: 300 
300: 

請補完程式碼，使其運作符合預期。作答規範:

• UUUU 和 DDDD 皆為表示式，且有 < 運算子，不包含小括號 (即 ( 和 ))
• 以合法且最精簡的 C99 語法撰寫

延伸問題:

1. 解釋上述程式碼運作原理
2. 將上述實作整合進 seHTTPd

---

修正

根據 kdnvt 同學的觀察，使用上述程式碼考慮以下情境:

原版程式在檢查後發現 8, 9, 10 的 parent 都比較小後就不會繼續遞迴往上 heapify。同理， 6, 7 的 parent 小於兩者，所以不會繼續往更上面的 node 做 heapify。但是除了 3, 4, 5，我們不能保證其他節點的位置是否正確，因此可以透過修改 do_sift_up 來確保正確性:

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
...
    if (pv < v){
        do_sift_up(pidx, nr_items, h);
        return;
    }
...
}

當 parent 小於 child 時不會中止遞迴，會繼續往 parent 上檢查。