2024q1 Homework2 (quiz1+2)

contributed by < Ken-LuWeiRu >

tags: linux2024

第 1 週測驗題
第 2 週測驗題

第 1 週測驗題

測驗 1

程式運作原理

測試

在編譯過程中出現以下訊息

$git commit -m "Test q1t1" 
Following files need to be cleaned up:
original_q1t1.c
queue.c
original_q1t1.c:124:11: style: Checking if unsigned expression 'n' is less than zero. [unsignedLessThanZero]
    if (n <= 0)
          ^
original_q1t1.c:78:25: style: Local variable 'n' shadows outer variable [shadowVariable]
                node_t *n = p;
                        ^
original_q1t1.c:59:9: note: Shadowed declaration
    int n = list_length(list);
        ^
original_q1t1.c:78:25: note: Shadow variable
                node_t *n = p;
                        ^

重寫 shuffle 和 quick_sort 函數

void shuffle(size_t *array, size_t n)
{
    // if (n <= 0) 移除這行，因為 size_t 類型的 n 永遠不會小於零
    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        size_t t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

void quick_sort(node_t **list)
{
    int length = list_length(list); // 更改這裡的變量名，避免與下方的 node_t 變量重名
    int value;
    int i = 0;
    int max_level = 2 * length; // 這裡使用修改後的變量名
    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 *node_ptr = p; // 修改變量名稱，避免重名
                p = p->next;
                list_add(node_ptr->value > value ? &right : &left, node_ptr); // 這裡也使用修改後的變量名
            }

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

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

測試

測試程式碼

int main(int argc, char **argv)
{
    node_t *list = NULL;
    const int sizes[] = {10000, 50000, 100000};  // 定義不同大小的測試案例
    const int num_sizes =
        sizeof(sizes) / sizeof(sizes[0]);  // 計算測試案例的數量
    double elapsed_times[num_sizes];  // 儲存每個測試案例的執行時間

    for (int s = 0; s < num_sizes; ++s) {
        size_t count = sizes[s];
        int *test_arr = malloc(sizeof(int) * count);

        // 產生隨機數據
        for (int i = 0; i < count; ++i)
            test_arr[i] = i;
        shuffle(test_arr, count);

        // 構建鏈表
        for (size_t i = 0; i < count; ++i)
            list = list_construct(list, test_arr[i]);

        clock_t start = clock();  // 開始計時
        quick_sort(&list);        // 執行快速排序
        clock_t end = clock();    // 結束計時

        elapsed_times[s] =
            (double) (end - start) / CLOCKS_PER_SEC;  // 計算經過時間

        assert(list_is_ordered(list));  // 驗證列表是否已排序
        list_free(&list);               // 釋放列表記憶體
        free(test_arr);                 // 釋放測試陣列記憶體
    }

    // 輸出每個測試案例的執行時間
    for (int i = 0; i < num_sizes; ++i) {
        printf("Size %d: %f seconds\n", sizes[i], elapsed_times[i]);
    }

    return 0;
}

輸出

Size 10000: 0.001226 seconds
Size 50000: 0.008770 seconds
Size 100000: 0.019222 seconds

改寫融入 lab0-c

採用 list.h 進行重構

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>  // 加入 time.h 以使用 clock()
#include "list.h"  // 匯入 Linux 風格的鏈結串列定義

typedef struct __node {
    struct list_head list;  // 用於雙向鏈結串列的節點
    long value;             // 節點存儲的數值
} node_t;

int list_length(struct list_head *head)
{
    struct list_head *pos;
    int n = 0;
    list_for_each (pos, head) {
        ++n;
    }
    return n;
}
node_t *list_construct(long n)
{
    node_t *node = malloc(sizeof(node_t));
    INIT_LIST_HEAD(&node->list);  // 初始化 list_head 結構
    node->value = n;
    return node;
}


void list_free(struct list_head *head)
{
    struct list_head *pos, *q;
    list_for_each_safe (pos, q, head) {
        // 確保 pos 不是指向 list_head 自身，否則將導致 list_entry
        // 返回不正確的指針
        if (pos != head) {
            node_t *tmp_node = list_entry(pos, node_t, list);
            list_del(pos);
            free(tmp_node);
        }
    }
}


void quick_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head)) {
        return;
    }

    struct list_head *pivot = head->next;
    struct list_head sorted;
    INIT_LIST_HEAD(&sorted);

    struct list_head *current = NULL, *temp = NULL;
    LIST_HEAD(less);
    LIST_HEAD(greater);

    list_for_each_safe (current, temp, head) {
        if (current != pivot) {  // 確保當前節點不是 pivot
            node_t *node = list_entry(current, node_t, list);
            node_t *pivot_node = list_entry(pivot, node_t, list);
            if (node->value < pivot_node->value) {
                list_move_tail(current, &less);
            } else {
                list_move_tail(current, &greater);
            }
        }
    }

    quick_sort(&less);
    quick_sort(&greater);

    list_splice(&less, head);
    list_splice_tail(&sorted, head);
    list_splice_tail(&greater, head);
}



static bool list_is_ordered(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head)) {
        return true;
    }

    node_t *current_node = NULL, *next_node = NULL;
    struct list_head *node;

    list_for_each (node, head) {
        if (node != head) {  // 確保節點不是 list_head 自身
            current_node = list_entry(node, node_t, list);
            if (node->next != head) {  // 確保下一個節點不是 list_head 自身
                next_node = list_entry(node->next, node_t, list);
                if (current_node->value > next_node->value) {
                    return false;
                }
            }
        }
    }
    return true;
}

void shuffle(int *array, size_t n)
{
    // if (n <= 0)
    //     return;
    // 移除這行，因為 size_t 類型的 n 永遠不會小於零
    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;
    INIT_LIST_HEAD(&list);

    const int sizes[] = {10000, 50000, 100000};
    const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
    double elapsed_times[num_sizes];

    for (int s = 0; s < num_sizes; ++s) {
        size_t count = sizes[s];
        int *test_arr = malloc(sizeof(int) * count);

        for (int i = 0; i < count; ++i) {
            test_arr[i] = rand() % count;
        }
        shuffle(test_arr, count);

        for (size_t i = 0; i < count; ++i) {
            node_t *new_node = list_construct(test_arr[i]);  // 使用构造函数
            list_add_tail(&(new_node->list), &list);
        }

        clock_t start = clock();
        quick_sort(&list);
        clock_t end = clock();

        elapsed_times[s] = (double) (end - start) / CLOCKS_PER_SEC;

        assert(list_is_ordered(&list));

        list_free(&list);  // 使用自定义的函数清理内存

        free(test_arr);
    }

    for (int i = 0; i < num_sizes; ++i) {
        printf("Size %d: %f seconds\n", sizes[i], elapsed_times[i]);
    }

    return 0;
}

輸出

Size 10000: 0.001075 seconds
Size 50000: 0.006973 seconds
Size 100000: 0.015436 seconds

測驗 2

解釋程式碼

改寫進去lab0-c

我想將 timsort 加進 qtest.c 中
在 qtest.c 加入

int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
    const element_t *elem_a = list_entry(a, element_t, list);
    const element_t *elem_b = list_entry(b, element_t, list);
    return strcmp(elem_a->value, elem_b->value);
}


static bool do_timsort(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q) {
        report(3, "Warning: Calling timsort on null or empty queue");
        return false;
    }

    if (exception_setup(true)) {
        timsort(NULL, current->q, compare);
    }
    exception_cancel();

    return q_show(0) && !error_check();
}

並且在 static void console_init() 中加入

    ADD_COMMAND(timsort, "Sort queue using timsort algorithm", "");

現在就可以在執行 qtest 後輸入 timsort 來排序

撰寫 traces 中的測試文件

改寫進去make test

進行效能比較分析

第 2 週測驗題

測驗 1

程式碼解釋

編譯並配置 cgroup

Control Group v2

linux/kernel/cgroup/cgroup.c

Resource Control in Embedded Linux Systems with cgroups

利用 buildroot 與 Qemu 建構簡易 Embedded Linux 環境

測驗 2

程式碼解釋

測驗 3

程式碼解釋

ref

https://port70.net/~nsz/c/c11/n1570.html#6.2.5

ISO/IEC 9899 (a.k.a C99 Standard)

C11 (ISO/IEC 9899:201x)
網頁版

The Linux Kernel Archives

cgroup.c