2025q1 第 1 週測驗題

目的: 檢驗學員對間接指標、鏈結串列及記憶體配置的認知

作答表單: 測驗 1 和測驗 2
作答表單: 測驗 3

測驗 `1`

以下程式碼運用〈你所不知道的 C 語言: linked list 和非連續記憶體〉提及的 "a pointer to a pointer" 技巧，撰寫鏈結串列的經典操作。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

考慮以下程式碼：

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

其關鍵操作 list_insert_before 函式的語意如下：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

對應的測試程式碼如下：

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

#include "list.h"

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)
#define my_run_test(test)       \
    do {                        \
        char *message = test(); \
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)

#define N 1000

static list_item_t items[N];
static list_t l;

static list_t *list_reset(void)
{
    for (size_t i = 0; i < N; i++) {
        items[i].value = i;
        items[i].next = NULL;
    }
    l.head = NULL;
    return &l;
}

static char *test_list(void)
{
    /* Test inserting at the beginning */
    list_reset();
    my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
    for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);
    my_assert(list_size(&l) == N, "Final list size should be N");
    size_t k = N - 1;
    list_item_t *cur = l.head;
    while (cur) {
        my_assert(cur->value == k, "Unexpected list item value");
        k--;
        cur = cur->next;
    }

    /* Test inserting at the end */
    list_reset();
    my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
    for (size_t i = 0; i < N; i++)
        list_insert_before(&l, NULL, &items[i]);
    my_assert(list_size(&l) == N, "Final list size should be N");
    k = 0;
    cur = l.head;
    while (cur) {
        my_assert(cur->value == k, "Unexpected list item value");
        k++;
        cur = cur->next;
    }

    /* Reset the list and insert elements in order (i.e. at the end) */
    list_reset();
    my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
    for (size_t i = 0; i < N; i++)
        list_insert_before(&l, NULL, &items[i]);
    my_assert(list_size(&l) == N, "list size should be N");

    return NULL;
}

int tests_run = 0;

static char *test_suite(void)
{
    my_run_test(test_list);
    return NULL;
}

int main(void)
{
    printf("---=[ List tests\n");
    char *result = test_suite();
    if (result)
        printf("ERROR: %s\n", result);
    else
        printf("ALL TESTS PASSED\n");
    printf("Tests run: %d\n", tests_run);
    return !!result;
}

預期執行時期不會遇到 assert 錯誤。參考執行輸出：

---=[ List tests
ALL TESTS PASSED
Tests run: 1

list_insert_before 函式

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

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

AAAA, BBBB, CCCC, DDDD 皆為 C 語言表示式，不含 ; 或 , 字元
以最精簡的方式撰寫，不包含空白

延伸問題:

解釋上方程式碼運作原理
在現有的程式碼基礎上，撰寫合併排序操作

測驗 `2`

下圖展示常見的虛擬記憶體架構，其中有些資料結構的大小（如陣列）是在程式執行期間動態決定的，所以必須有個可以動態成長的區域，稱作 heap。對於每一個行程（process），作業系統核心會維護一個指標 brk 用來指向 heap 的頂部。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

以下嘗試實作動態記憶體配置器，包含 malloc, free 及 realloc。這類配置器我們稱為顯式配置器（explicit allocator），程式必須明確呼叫 free 來釋放記憶體空間。顯式配置器必須符合以下條件：

處理任意請求序列
立即處理需求
只能使用 heap 空間
地址對齊：提高記憶體存取效率，例如 malloc 在 32 位元系統上為 8 Byte 對齊，64 位元系統則為 16 Byte 對齊 \(\to\) 你所不知道的 C 語言：記憶體管理、對齊及硬體特性
不得修改已配置的區塊

配置器的實作必須在這些限制條件下，盡可能地在吞吐率 (throughput) 與空間利用率 (ttilization) 之間找到平衡。

吞吐率 (Throughput)

單位時間內（通常為秒）可完成的配置 + 釋放請求數量。

空間利用率 (Utilization)

\[ U_k = \frac{\max_{i \leq k} P_i}{H_k} \]
其中：

\(\max_{i \leq k} P_i\)：過去 \(k\) 個請求中，最大的有效荷載(payload) 總和
\(H_k\)：目前 heap 的大小

要處理好吞吐率與空間利用率的平衡，配置器的實作必須考慮以下問題：

free block 結構：如何紀錄 free block
allocate：如何選擇合適的 free block 來放置新配置的 block
split：放置新配置的 block 後，如何處理剩餘的空間
coalesce：剛釋放的 block 前後是否有其他 free block 可合併成一個更大的 free block

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

以往的實作中，每種類別大小（size-class）的空間都有一個 Free list，。隨著程式的執行，相同大小的空間地址可能會分散在整個記憶體的各個位置，長期下來會導致空間區域性 (spatial locality) 變差。

以下是一個 8 Bytes 的 Free list 在程式執行一段時間後的狀況：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

此時，若配置（allocate）一個 8 Bytes 的鏈結串列，將會形成一個空間區域性很差的鏈結串列。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

於是，我們利用分頁 (paging) 特性，確保每個分頁僅存放特定大小類別 (size-class) 的空間，藉此提升空間區域性。

下圖為一個 8 Bytes 的 mimalloc Free list。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

下方程式碼嘗試管理樹狀結構的記憶體區塊： (部分遮蔽)

#include <assert.h>
#include <stddef.h>

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);

/*
 * Structure representing a free memory block in the memory allocator.
 * The free tree is a binary search tree that organizes free blocks (of type block_t)
 * to efficiently locate a block of appropriate size during memory allocation.
 */
void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, target);

    /* If the target node has two children, we need to find a replacement. */
    if ((*node_ptr)->l && (*node_ptr)->r) {
        /* Find the in-order predecessor:
         * This is the rightmost node in the left subtree.
         */
        block_t **pred_ptr = &(*node_ptr)->l;
        while (EEEE)
            pred_ptr = FFFF;

        /* Verify the found predecessor using a helper function (for debugging).
         */
        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *pred_ptr);

        /* If the predecessor is the immediate left child. */
        if (*pred_ptr == (*node_ptr)->l) {
            block_t *old_right = (*node_ptr)->r;
            *node_ptr = *pred_ptr; /* Replace target with its left child. */
            (*node_ptr)->r = old_right; /* Attach the original right subtree. */
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        } else {
            /* The predecessor is deeper in the left subtree. */
            block_t *old_left = (*node_ptr)->l;
            block_t *old_right = (*node_ptr)->r;
            block_t *pred_node = *pred_ptr;
            /* Remove the predecessor from its original location. */
            remove_free_tree(&old_left, *pred_ptr);
            /* Replace the target node with the predecessor. */
            *node_ptr = pred_node;
            (*node_ptr)->l = old_left;
            (*node_ptr)->r = old_right;
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

請依據程式碼註解，補完程式碼以符合預期。

作答規範:

EEEE 和 FFFF 為 C 語言表示式，不含 ; 或 , 字元
以最精簡的方式撰寫，不包含空白

測驗 `3`

〈Optimized QuickSort — C Implementation (Non-Recursive)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍。

假定下方是起始的陣列內容。採取 head 作為 pivot，並且 L 會從左邊開始掃，紀錄有多少值小於 pivot，R 從右邊開始，紀錄有多少值大於 pivot。(R 一開始會定義為陣列的 length，以減法的方式紀錄)

這裡的 L 就會是 3，而 R 就會是 5

於是會把 array[4] 放到 array[0]，array[3] 放到 array[4]，再把 pivot 放入 array[3]

再來就是利用 begin 與 end 作為堆疊，去儲存尚未排列好的序列，由於 pivot 目前在 array[3] 的位置，所以就會有一組 begin 跟 end 為 0~2、一組為 4~5。之後會重複上述的行為，一次會以 5 為 pivot，另一次則會以 2 為 pivot，就可以得到排序好的陣列。

用變數 i 紀錄現在的 stack 在什麼位置，每次迴圈的開始都進行 pop 的操作：

node_t *top = stk[i--];

依照相對於 pivot 大小整理節點的步驟沒有不同。而分類完 left 和 right 之後，本來應該各自遞迴計算的部分換成「放進堆疊中」，換言之，這份程式碼嘗試用堆疊模擬原本的遞迴呼叫。

考慮以下的鏈結串列結構體:

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

操作鏈結串列的圖解：

以下運用 Optimized QuickSort — C Implementation (Non-Recursive) 實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。

begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
left 用來存放小於等於 pivot 的節點
right 用來存放大於 pivot 的節點
result 用來存放排序完的分割

其流程為

以 L R 指向串列分割 i 之兩端，當 L R 尚未交會則進行內部排序
最左邊的數設為 pivot，p 則指向 pivot 隔壁的節點，pivot 的 next 指向 NULL
指標 p 會一直往右走，將大於 pivot 的節點存入 right ，小於的存入 left
接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2
下一回合將進行 串列分割 i+2 之內部排序（也就是先排右邊）
直到右邊都排序完成後，才會將排序完的分割存入 result，並開始進行左邊分割的排序。

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

操作鏈結串列的圖解：

接著我們使用 Linux 核心風格 List API 的簡化標頭檔 list.h 來改寫快速排序程式碼。首先是結構體：

#include "list.h"

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

快速排序實作的函式原型宣告:

void quick_sort(struct list_head *list);

以下是測試程式碼:

void list_construct(struct list_head *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->value = n;
    list_add(&node->list, list);
}

void list_free(const struct list_head *head)
{
    node_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        free(entry);
    }
}

/* Verify if list is order */
static bool list_is_ordered(const struct list_head *head)
{
    int value = list_entry(head->next, node_t, list)->value;
    node_t *entry;
    list_for_each_entry (entry, head, list) {
        if (entry->value < value)
            return false;
        value = entry->value;
    }

    return true;
}

/* shuffle array, only work if n < RAND_MAX */
void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

int main(int argc, char **argv)
{
    struct list_head *list = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(list);

    size_t count = 100000;
    int *test_arr = malloc(sizeof(int) * count);
    for (int i = 0; i < count; ++i)
        test_arr[i] = i;
    shuffle(test_arr, count);

    while (count--)
        list_construct(list, test_arr[count]);
    quick_sort(list);
    assert(list_is_ordered(list));
    list_free(list);
    free(test_arr);
    return 0;
}

為了便於實作，我們準備以下輔助函式：

struct list_head *list_tail(struct list_head *head)
{
    while (head && head->next)
        head = head->next;
    return head;
}

int list_length(struct list_head *left)
{
    int n = 0;
    struct list_head *node;
    list_for_each(node, left) n++;
    return n;
}

另一個輔助函式: (部分)

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    /* GGGG */;
}

接著是 quick_sort 主體:

{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = /* HHHH */
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = /* IIII */;
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = /* JJJJ */;
            begin[i + 2] = /* KKKK */;
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

預期執行時期不會遇到 assert 錯誤。補完程式碼，使其符合預期。

作答規範：

GGGG 為有效 C 語言表示式，不含 ; 或 , 字元
HHHH 和 IIII 包含 list_entry 巨集，不含 ; 字元
JJJJ 和 KKKK 為有效 C 語言表示式，不含 ; 或 , 字元
以最精簡的方式撰寫，不包含空白

延伸問題:

解釋上述程式碼運作原理
研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

2025q1 第 1 週測驗題

測驗 1

測驗 2

測驗 3

Read more

UNIX 作業系統 fork/exec 系統呼叫的前世今生

你所不知道的 C 語言: Stream I/O, EOF 和例外處理

KVM: Linux 虛擬化基礎建設

2025 年 Linux 核心設計課程作業 —— lab0 (C)

測驗 `1`

測驗 `2`

測驗 `3`