2024q1 Homework2 (quiz1+2)

contributed by < nosba0957 >

quiz1

測驗一

解釋程式碼

此 quick_sort() 函式是使用非遞迴的方式，所以需要用堆疊來紀錄每次迴圈需要的資料。而迴圈需要知道這次執行的子數列的起始位置和結束位置。所以使用 begin[] 和 end[] 來紀錄。i 則為目前堆疊位置索引。
進入迴圈後，兩指標 L 和 R 分別指向此次迴圈要執行的子串列的頭和尾，也就是紀錄在堆疊 begin[i] 和 end[i] 的值。pivot 的選擇是固定使用 L，所以比較下一步要比較節點和 pivot 大小時要從下一個開始，也就是 pivot->next。

我們使用 node_t *p 來迭代需要比大小的節點。比較的方式如下程式碼，value 是儲存 pivot->value。所以每個節點和 value 比大小後，大的值會加入到 right 串列，小的值加到 left 串列。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

結果會像這樣，left 上的值都小於 pivot，right 上的值都大於 pivot。

所以現在有三個子串列，會被加入到堆疊中。而因每次迴圈都會取出堆疊最上面的子串列來執行，所以加入堆疊的順序是有要求的。先將小於 pivot 的部份加入，再來加入 pivot，最後才放大於 pivot 的串列。如此一來，每次迴圈都會先執行數值較大的子串列。

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

以上情況是當 L 和 R 從堆疊取出的值不相同時的處理。當 L 和 R 從堆疊取出相同值時，表示子串列只剩單一元素，即可加入 result 串列中，即為排列好的串列。此處可以理解為何要依照大小將子串列放入堆疊，當先執行數值大的子串列，最後也會是數值大的節點最先加入 result。

if (L != R) {
    ...
} else {
    if (L)
        list_add(&result, L);
    i--;
}

使用 Linux 核心風格的 List API 改寫

首先要修改的就是 node_t 的內部元素，模仿 lab0-c 的 element_t。撰寫此處時曾犯錯誤，將 list 型態寫為 struct list_head *，會導致 container_of 無法執行。可以從 container_of 的巨集看出錯誤。

typedef struct node_t {
    struct list_head list;
    long value;
} node_t;

quick_sort 中需要的堆疊由 2 個減為一個，原本需要使用 begin[] 和 end[] 來紀錄本次遞迴所需要的子序列的起始和結束位置。但改為 Linux 風格的 List 後，原本單向鏈結串列改為雙向環狀鏈結串列，所以我將堆疊改為紀錄每個環狀鏈結串列的標頭節點。堆疊初始化的想法觀摩 var-x 的方式，原先我沒有選擇在初始化變數時，就將堆疊全部分配好記憶體，我是選擇在迴圈內要使用到的時候再分配記憶體，造成我在管理記憶體時遇到許多錯誤。

避免最差情況

原始方法中，每次 pivot 都是取子串列的第一個元素。當遇到最差情況，即陣列已經排序好的時候，所有的節點都會放在同一邊。如下所示，當 value 是最小值或最大值時，所有節點會被加進 right 或 left 其中一邊，會導致後面新增的三個堆疊中，會有其中一個堆疊是完全沒有節點。

while (p != begin[i]) {
    struct list_head *n = p;
    p = p->next;
    int n_value = list_entry(n, node_t, list)->value;
    list_del(n);
    list_add_tail(n, n_value > value ? right : left);
}

所以我採取的方法是 pivot 是隨機選取，如此一來即使是最差情況，也能保持堆疊內存放的串列長度不會太極端，但不能保證平均分配節點。
節點 100000 個，執行時間：

• 不採用 rand_pivot：
  • 未排序串列： 0.056040 (s)
  • 已排序串列： 57.969336(s)
• 採用 rand_pivot：
  • 未排序串列： 0.145577 (s)
  • 已排序串列： 0.102973 (s)

可以看到最差情況有較大的改善。但因為鏈結串列分配的結果並不是連續的記憶體，所以 rand_pivot 是使用迭代的方式找到算出來的隨機節點，需要想辦法快速的找到該節點。

測驗二

解釋程式碼

• find_run 函式每次會回傳一個 struct pair，strcut pair 的第一個成員是 head，儲存該次找到的 run 的串列的起始位置。另一個成員 next 指的是剩下的串列的起始位置。在 find_run 函式內會將找到的 run 和剩餘的串列切斷，並且保證最後找到的 run 是由小到大排列的。
• timsort 的堆疊是由 list_head *tp 實作，每次迴圈由 find_run 回傳的新一個 run 的起始位置 result.head 的 prev 來儲存堆疊的前一個元素。因為每次 find_run 回傳的 result.head 的 prev 必為 NULL。所以總結一下，tp 是當前堆疊的第一個元素，堆疊下一個元素為 tp->prev，以此類推。
• merge_collapse 函式會確保 run 長度相同，所以會檢查堆疊最頂端的 3 個 run 是否符合要求，否則需要合併。

找到改進之處

• 實作 minrun 並且透過插入排序排列所選擇的 run。
  1. 首先找到串列長度的 6 位 MSB(Most Significant bit)，此 6 位即為 minrun，而除了此 6 位以外，若有某位是 1，則將 minrun + 1。但若 data_size 不足 6 bits，則直接執行插入排序。
  ​​​​static int count_minrun(int data_size)
  ​​​​{
  ​​​​    if (data_size < 64)
  ​​​​        return data_size;
  ​​​​    int minrun = data_size >> (32 - __builtin_clz(data_size) - 6);
  ​​​​    return minrun + (((minrun << 6) ^ data_size) > 0);
  ​​​​}
  

  2. 接下來在 find_run 中直接改成將 minrun 個節點取出，然後執行插入排序
  ​​​​for(int i = 0; i < minrun && next; i++) {
  ​​​​    len++;
  ​​​​    list = next;
  ​​​​    next = list->next;
  ​​​​}
  ​​​​list->next = NULL;
  
  ​​​​head = insertion_sort(priv, head, cmp);
  

• 修改隨機資料的分佈
  • Timsort 適用的資料分布是模擬現實世界的資料，通常是部分已經有排序。所以在產生隨機資料時需要特別生成排序好的資料。num 用來決定連續資料的長度，start 用來決定連續資料的第一筆資料數值。接下來再透過 num % 2 決定資料是遞增還是遞減。
  ​​​​static void create_sample(struct list_head *head, element_t *space, int samples)
  ​​​​    {
  ​​​​        srand(time(0));
  ​​​​        printf("Creating sample\n");
  ​​​​        for (int i = 0; i < samples;) {
  ​​​​            int num = rand() % (samples - i) + 1;
  ​​​​            int start = rand() % samples;
  ​​​​            for (int j = 0; j < num; i++, j++) {
  ​​​​                element_t *elem = space + i;
  ​​​​                elem->val = start + j;
  ​​​​                if (num % 2)
  ​​​​                    list_add_tail(&elem->list, head);
  ​​​​                else
  ​​​​                    list_add(&elem->list, head);
  ​​​​            }
  ​​​​        }
  ​​​​    }
  

以上兩個修改最後的結果並沒有讓實際耗時更少，反而時間花費更久一點，比較次數也因插入排序增加許多。

quiz2

測驗一

解釋程式碼

Linux 核心的 hash table 實作是透過 hlist_node 的陣列，透過雜湊函數得到的雜湊值來決定該點要放在陣列的哪個位置。而 linux 在處理碰撞時是使用雙向鏈結串列來處理，鏈結串列的結構中使用指標的指標來減少移去節點時的不必要的操作。如下圖，當想要移去 hlist_node_1 時，將此節點的 next 指向的地址指派給 *pprev(也就是 list_head 的成員 first)，再將自己的 pprev 指派給下一個節點的 pprev，即可完成移去節點。

圖取自 Linux 核心的 hash table 實作
本題是透過前序和中序的走訪結果來重建二元樹，首先建立中序走訪的 hash table，儲存每個節點在中序走訪的陣列中的索引值和其儲存的值。透過 hash table 可以在稍後 dfs 過程中快速取得該節點在中序走訪陣列的索引值。
dfs 的函數參數如下，每次 dfs 的結果回傳的是其左下或右下的子樹，而 pre_low, pre_high, in_low, in_high 是表示該子樹在前序和中序的陣列的索引範圍。所以藉由 dfs 一次建立一個節點，再透過 dfs 遞迴解決左右子樹的問題。

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)

在 Linux 核心的 cgroups 相關原始程式碼

在 include/linux/cgroup.h 中，css_for_each_descendant_pre 函式。

#define css_for_each_descendant_pre(pos, css)				\
	for ((pos) = css_next_descendant_pre(NULL, (css)); (pos);	\
	     (pos) = css_next_descendant_pre((pos), (css)))

他是用來前序走訪 cgroup 的樹狀結構。在 kernel 文件中有提到，cgroup 會管理 process 的資源，其中 cgroups 內有 subsystem 成員，又稱為 "resource controller"，就是用來控制 process 的資源使用。

A subsystem is a module that makes use of the task grouping facilities provided by cgroups to treat groups of tasks in particular ways. A subsystem is typically a "resource controller" that schedules a resource or applies per-cgroup limits, but it may be anything that wants to act on a group of processes, e.g. a virtualization subsystem.

在 cgroup.h 中的 css 全名為 cgroup subsystem state，可以在 cgroup-defs.h 中看到結構體的內容，其中就有透過 struct list_head 建立樹狀結構的節點。

struct cgroup_subsys_state {
	/* PI: the cgroup that this css is attached to */
	struct cgroup *cgroup;

	/* PI: the cgroup subsystem that this css is attached to */
	struct cgroup_subsys *ss;

	/* reference count - access via css_[try]get() and css_put() */
	struct percpu_ref refcnt;

	/* siblings list anchored at the parent's ->children */
	struct list_head sibling;
	struct list_head children;
    ...