---
tags: linux
---

# 2023q1 Homework1 (quiz1)
contributed by < `kata1219` >

> [第一週測驗題題目](https://hackmd.io/@sysprog/linux2023-quiz1)
> [實作程式碼](https://github.com/kata1219/linux2023_quiz/tree/main/quiz1-c)

### 測驗 `1`

#### 延伸問題
1. 解釋程式碼運作原理
* 使用 Quick sort 排序，在每一輪指定第一個元素做為標準，將 list 分為**小於標準的陣列**及**大於標準的陣列**，再分別對兩個陣列進行排序，完成後將排序完的陣列合併。

2. 針對 Quick sort 提出上述程式碼的改進方案並實作
* 目前程式碼會在每次遞迴都產生 `list_less` 和 `list_greater` 兩個 list，改成在原 list 內排序可減少記憶體消耗。

3. 引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
*

4. BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

---

### 測驗 `2`

#### 延伸問題
1. 解釋上方程式碼運作原理，指出設計和實作的缺失
2. 比較測驗 `1` 和測驗 `2` 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
3. 提出效能改進方案，特別是避免依賴 `MAX_DEPTH`
4. 引入 Introsort，也就是 quick sort 和 heap sort (或其他可避免前者 $O(n^2)$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 $2×log\ n$) 次後排序仍未完成，那就可能遭遇 $O(n^2)$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 $O(n\ log\ n)$

---

### 測驗 `3`
剛開始解讀程式碼，推測 `xorlist` 有兩種可能，一種是會連 head 一併循環的，另一種是不包含 head 形成 circle 的。

digraph structs {
    rankdir=LR;
    node[shape=record];
    struct0 [label="head"];
    struct1 [label="1"];
    struct2 [label="2"];
    struct3 [label="3"];
    struct4 [label="4"];
    struct0 -> struct1;
    struct1 -> struct2;
    struct2 -> struct3;
    struct3 -> struct4;
    struct4 -> struct1;
}

digraph structs {
    rankdir=LR;
    node[shape=record];
    struct0 [label="head"];
    struct1 [label="1"];
    struct2 [label="2"];
    struct3 [label="3"];
    struct4 [label="4"];
    struct0 -> struct1;
    struct1 -> struct2;
    struct2 -> struct3;
    struct3 -> struct4;
    struct4 -> struct0;
}

我嘗試藉由 xorlist 的操作找出節點的關係。首先，在 xorlist 初始化的方式與 list_head 就有比較大的差異，list_head 是把 next、prev 都指向自身，並在新增節點時會改變 next、prev；而在 xorlist 中是 head 指向 tail，tail 指向 head，且新增節點不會改變 tail。接著觀察 xorlist_add 這個函式，從 lab0 的命名規則推測函式的作用是在開頭新增一個 node。我們可以由程式碼推測出 real_prev 代表 list 的 head，real_next 代表 head 指向的位置，也就是 tail。

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;
    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = &list->tail;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    list->count++;

    return 0;
}

#### 延伸問題
1. 解釋上述程式碼運作原理，指出其實作缺陷並改進
2. 在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
3. 修改 xorlist_destroy，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放