2024q1 Homework2 (quiz1+2)

contributed by < yuyuan0625 >

第一週測驗

測驗一

鏈結串列結構體 node_t:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

補齊程式碼

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
       left = &(AAAA); 
    return *left;
}

此函式的目的是尋找鏈結串列的尾端，因此需要逐一走訪每個節點，node_t **left 為指標的指標，因此每一次迴圈都需要將 left 的值更新為指向下一個節點指標( next )的位址, 因此 AAAA 應為 (*left)->next

示意圖:

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
       left = &(BBBB);
    }
    return n;
}

此函式和 list_tail() 相同，每一次迴圈都需要往下一個節點走訪。
因此 BBBB 同為 (*left)->next)

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = CCCC;    
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = DDDD;
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = EEEE;
            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

在此段程式碼中，
內部迴圈會由 begin[i]->next 循序走訪至 end[i]，並和 pivot 比較，若大於 pivot 加入 right，反之則加入 left。
因此，和前兩題相同，都是要循序走訪鏈結串列，p = p->next。

外部迴圈：將鏈節串列分為三段：
1.小於等於 pivot
2.pivot
3.大於等於 pivot
並分別將其串列開頭分別存在 begin[i] , begin[i+1] , begin[i+2]，並使用 end[i] , end[i+1] , end[i+2] 儲存串列尾端。
因此 DDDD 就是 left 鏈結串列的尾端，使用 &list_tail(left) 來獲得其位址。同理，EEEE 即為 &list_tail(right) 。

延伸問題

解釋上述程式碼的運作原理，提出改進方案並予以實作。
以實際例子解釋：

選第一個節點 4 作為 pivot ，將 pivot 從串列移除，並比較後面所有節點和 pivot 的大小關係，將小於 pivot 的節點利用 list_add 加入 left ，大於 pivot 的節點加入 right 。

i += 2，此時 i=2，begin[2]==end[2]，因此利用 add_list 將 5 加入 result，i--。

i=1 ，begin[1]==end[1]，將 4 加入result，i--。

i=0 , 選 1 做 pivot，3 加入right, i+=2

i=2，begin[2]==end[2]，將 3 加入 result ，i--
i=1，begin[1]==end[1]，i--
i=0，begin[0]==end[0]，將 1 加入 result ，i--

問題與改進方案:
此程式每次都只挑選第一個節點作為pivot ,若剛好鏈結串列為遞增時,每次 left皆為 NULL , right 皆為為 pivot 以外的其他節點,這樣就會需要走訪每一個節點才會結束,時間複雜度為

O (n^{2})

若要解決此問題,可以使用median of three或更進一步使用median of median來避免此問題。
TODO

測驗二

merge() 會將 a , b 兩個已排序的鏈結串列合併成新的鏈結串列,一開始因為鏈結串列為空,要將 **tail 初始化為 &head。
接著利用迴圈比較 a , b 的第一個節點,將較小者加入新鏈結串列的尾部, 加入後要將 tail 指標向後移,下次加入節點時才能繼續加入鏈結串列尾端, 因此 BBBB 為 &a->next，CCCC 則為 &b->next。

程式碼改進
可將 for 迴圈替換成 while 迴圈,減少迴圈內 if 的判斷次數

-    for (;;) {
+    while(a && b){
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = BBBB;
            a = a->next;
-           if (!a) {
-               *tail = b;
-               break;
-           }
        } else {
            *tail = b;
            tail = CCCC;
            b = b->next;
-           if (!b) {
-               *tail = a;
-               break;
-           }
        }
+       tail = &(*tail)->next;
    }
+   *tail = (a) ? a : b;

build_prev_link() 會走訪每個節點,並且建立每個節點的 prev , 最後需要將頭尾相連。

-   DDDD = head;
+   tail->next = head;
-   EEEE = tail;
+   head->prev = tail;

在 timsort()　中，stk_size 表示 run 的個數,在合併的過程中 stk_size 會逐漸減少。因為是剩下最後一個 run 時才會需要用到 build_prev_link() 將鏈結串列的頭尾相接,所以可以推斷 FFFF 為 1。

問題與改進方案:
此程式沒有採用題幹介紹的Galloping mode方法, 後續可以加入Galloping mode進行實做,並且比較兩者的差異
TODO

第二週測驗

測驗一

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;    //藍箭頭
    n->next = AAAA;                    //紅箭頭
    n->pprev = &h->first;              //橘箭頭
    h->first = n;
}

此函式是要將新的節點加入串列的前端,所以 AAAA 應為 h->first

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, BBBB) {
        struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

此段程式是為了尋找 num 的位置,會先計算 hash 取得對應的 hlist_head ,接著逐一走訪該鏈結串列。由此可知 BBBB 為 &head[hash] , CCCC 為 list_entry 。

dfs()

本題的 input 為兩個 int 陣列 preorder 和 inorder。在此函式中會使用 *tn 存取前序第一個節點的值,因為前序的第一個節點即為根節點, 並利用 find() 尋找此數值在中序的位置,左側為左子樹,右側為右子樹,再對左/右子樹繼續遞迴。
在下圖範例中, 會先查看 preorder 的第一個節點的值 3 ,在中序的位置 idx ,可知idx = 1。 (idx - in_low) 可以算出中序第一個節點和 idx 之間的間隔, 也就是左子樹的長度。而右子樹是從 idx + 1 到 in_high , 因此右子樹的長度為 in_high - idx - 1 , 利用pre_high - (in_high - idx - 1) 即可獲得前序中左子樹的 head 位置。而中序內左子樹的範圍就是 in_low 到 idx - 1 , 右子樹為 idx + 1 到 in_high。

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, DDDD);
}

此函式目的是將新節點加入對應 hash 的串列中, 因此 DDDD 應為 &head[hash]

在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
在 /kernel/cgroup/cgroup.c 中

/* walk live descendants in pre order */
#define cgroup_for_each_live_descendant_pre(dsct, d_css, cgrp)		\
	css_for_each_descendant_pre((d_css), cgroup_css((cgrp), NULL))	\
		if (({ lockdep_assert_held(&cgroup_mutex);		\
		       (dsct) = (d_css)->cgroup;			\
		       cgroup_is_dead(dsct); }))			\
			;						\
		else

測驗二

LRUCache : LRU 緩存機制的主體結構。包含以下元素:
- capacity: cache 的最大容量
- count : cache 當前紀錄的資料筆數
- dhead : 儲存 LRU 快取中的節點，並按最近使用的順序排列。
- hhead[] : 一個型態為 hlist_head 的陣列, 儲存每個 hash 對應的串列 head 節點
LRUNode : 是緩存中每個項目的結構，包含以下資料:
- key : 鍵值
- value: 數值
- node : 用於將此 cache 項目連接到 hash 的結構
- link : 用於將此 cache 項目連接到雙向鏈結的結構

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;       //藍箭頭
    if (next)
        EEEE = pprev;    //紅箭頭
}

此函式目的為刪除節點, 假設要刪除 node2 ,要將 *pprev 也就是 node1->next 的值改為 next (node3), 並且因為 next 存在,也要將 next->pprev 改為 pprev (node1)。

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, FFFF);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}

此段程式碼目的為釋放 LRU 快取所占用的記憶體,
pos 的型態為 list_head, 由此可知其為 LRUNode 中的 link, FFFF = link。因為要將 list 刪除, 故 GGGG 應為 &cache->link。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, HHHH);
        if (cache->key == key) {
            list_move(IIII, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

此函式從快取中尋找給定 key 並獲取其對應的值，如果 key 存在於快取內則返回該值，並將該節點移動到鏈結串列的頭部 (表示最近使用)；如果不存在則返回 -1。
pos 的型態為 hlist_node, 因此可推論其為LRUNode 中的 node , 故 HHHH 為 node。而 IIII 是移動至另一串列的前端, 因此為 &cache->list。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, JJJJ);
        if (c->key == key) {
            list_move(KKKK, &obj->dhead);
            cache = c;
        }
    }

    if (!cache) {
        if (obj->count == obj->capacity) {
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead);
            hlist_del(&cache->node);
            hlist_add_head(&cache->node, &obj->hhead[hash]);
        } else {
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++;
        }
        cache->key = key;
    }
    cache->value = value;
}

此函式將給定的鍵-值對(key–value pair)加入快取中,有以下三種情況

如果 key 已存在，則更新對應的值
key 不存在會判斷容量是否已滿
- 若已滿則刪除鏈結串列尾部的節點(最久未使用)，然後將新的鍵-值對插入到鏈結串列的前端。
- 若未滿則配置新空間將節點加入串列前端以及加入 hash table 中，並將 count++ 。

因此不管 key 是新的還是已存在，對應的節點都會被移動到鏈結串列的前端。
KKKK 同樣為移動至另一串列的前端,故為 &c->list 。

TODO
在 Linux 核心找出 LRU 相關程式碼並探討

測驗三

__ffs

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & AAAA) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

__ffs() 是用來查詢一個 word 中最低位 1 的所在位置, 若 (word & 0xffffffff) == 0 即可知道較低的32位元內沒有任一位元為1, 因此將 word 右移 32 位元再進行檢查。

__clear_bit

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= BBBB;
}

此段程式碼是透過 BIT_MASK(nr) 產生出只有第 nr 位為 1 ，其他位皆為 0 的遮罩，並利用此遮罩將該 addr 的第 nr 位清除。故 BBBB 應為 ~mask ，利用 ~ 運算將 mask 反轉成只有 nr 位為 0 ，即可達到清除該位元的效果。

fns

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

此段程式碼目的為找到第 n 個被設為 1 的位置，它會不斷地呼叫 __ffs 找到最低被設為 1 的位元，若還不是第 n 個就會使用 __clear_bit 將目前的位元清除，再繼續找下一個被設為 1 的位元。

FIND_NTH_BIT

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

運作原理:
先利用 small_const_nbits 比較要找的位數是否超過限制的 size ，並利用 GENMASK(h, l) 將 h 到 l 間的位元變為 1和 addr 做 & 運算，若 val 有值代表 addr h 到 l 間有位元被設為1，因此再利用 fns 找到為第 n 個被設為 1 的位元並回傳其位置。若不符合 small_const_nbits 就利用 FIND_NTH_BIT 來處理。

FIND_NTH_BIT

#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz CCCC BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })

FIND_NTH_BIT 能夠搜尋超出單個 BITS_PER_LONG 長度的範圍。如果要查找的位元不在目前處理的字節中，能透過迴圈繼續在下一個 BITS_PER_LONG 長度的區塊中搜尋，直到找到該位為止。
因為 size 可能無法被 BITS_PER_LONG 整除，因此搜尋到最後一輪時應避免找到超出 size 範圍的字元，因此使用取餘數的方式找到最後一個字節所需要搜尋的字元數量，故 CCCC 應為 %。

2024q1 Homework2 (quiz1+2)

第一週測驗

測驗一

延伸問題

測驗二

第二週測驗

測驗一

測驗二

測驗三

Read more

2025 成大嵌入式作業系統分析與實作 Lab1

2024 年「資訊科技產業專案設計」作業 3

2024 年「資訊科技產業專案設計」課程作業 1

2024 年「資訊科技產業專案設計」課程作業 2