# 2024q1 Homework6 (integration)
contributed by < `yu-hsiennn` >

## 研讀教材 [The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/#acknowledgements)
### 筆記
#### init module & end module
核心模組必須要有兩個函式，分別為起始 `init_module()`，此函式會在 `insmod` 將此模組掛載到核心上，而另一個函式為結尾 `cleanup_module()`，會在模組卸載時被呼叫。在版本 `2.3.13` 後就沒有強制一定要取作這兩個名稱，可以利用巨集 `module_init`、`module_exit` 來做到自定義名稱的呼叫。
`cleanup_module()` 會還原掛載前的樣子，不管 `init_module()` 做了什麼更動。
#### moudle 傳入參數
使用以下巨集:
- `moudle_param(name of var, type of var, permissions)`
- `module_param_array(name of var, type of var, a pointer to count var, permissions)`
- `module_param_string(name of var, string, length, permissions)`

並且可以利用 `MODULE_PARM_DESC(name of param, description)`，來給使用者提供此參數的使用方式
#### device driver

$ ls -l /dev/hda[1-3]
brw-rw----  1 root  disk  3, 1 Jul  5  2000 /dev/hda1
brw-rw----  1 root  disk  3, 2 Jul  5  2000 /dev/hda2
brw-rw----  1 root  disk  3, 3 Jul  5  2000 /dev/hda3

第一個數字代表的是主設備號，每個驅動都有唯一的編號，第二個數字用於讓主設備去區分不同的硬體編號。

裝置被分成兩種類型:
- character devices: 以不定長度的字元傳送資料
- block devices: 以固定大小長度來傳送轉移資料

##### Registering a Device

int register_chrdev(unsigned int major, const char *name, struct file_operations *fops);

- major: 主設備的編號
- name: 裝置的名稱，會出現在 `/proc/devices`
- fops: 一個指向 `file_operations` 表的指標

如果回傳值回 `-1` 則代表註冊失敗。而若不想手動選擇一個主設備編號，我們可以利用將 major 設為 0 來產生一個動態的編號，由於是動態產生的，所以你無法得知它會是哪一個數字，我們可以藉由手動或是腳本的方式來存取目前它的編號。
然而，此函式會占用與主設備**關聯的一系列硬體編號**，導致浪費註冊時的浪費

於是可以利用

int register_chrdev_region(dev_t from, unsigned count, const char *name); 
int alloc_chrdev_region(dev_t *dev, unsigned baseminor, unsigned count, const char *name);

- register_chrdev_region: 用於知道主設備編號時
- alloc_chrdev_region: 主設備編號為動態產生

接著，我們需要初始化 `cdev` 可以利用 `cdev_init(struct cdev *cdev, const struct file_operations *fops)`，完成後再呼叫 `int cdev_add(struct cdev *p, dev_t dev, unsigned count);` 來將字元設備添加進系統中。

## [ksort](https://github.com/sysprog21/ksort/tree/master)
### What's workqueue / CMWQ?
#### workqueue
通過呼叫 workqueue 的介面就能建立核心執行緒。並且可以根據當前系統 CPU 的個數建立執行緒的數量，使得執行緒處理能夠並行化。

#include <linux/workqueue.h>
struct workqueue_struct *create_workqueue(const char *name);

所獲得的工作佇列，對系統上的每個處理器各有一個專屬執行緒。

DECLARE_WORK(name,void (*function)(void*),void *data);
INIT_WORK(struct work_struct *work,void (*function)(void*),void *data);

DECLARE_WORK 為靜態初始化，會在編譯時期做好 work_struct 的初始化。

#include <linux/workqueue.h>
#include <linux/init.h>
#include <linux/module.h>

void my_work_function(struct work_struct *work) {
    printk(KERN_INFO "Executing my_work_function\n");
}

DECLARE_WORK(my_work, my_work_function);

static int __init my_module_init(void) {
    printk(KERN_INFO "Module loaded, scheduling work\n");
    schedule_work(&my_work);
    return 0;
}

static void __exit my_module_exit(void) {
    printk(KERN_INFO "Module unloaded\n");
    flush_scheduled_work();
}

module_init(my_module_init);
module_exit(my_module_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("yu-hsien");
MODULE_DESCRIPTION("A simple example of using DECLARE_WORK");

INIT_WORK 為動態初始化，會在執行時期執行。

#include <linux/workqueue.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h>  // For dynamic memory allocation

struct work_struct *my_dynamic_work;

void my_dynamic_work_function(struct work_struct *work) {
    printk(KERN_INFO "Dynamic work executed\n");
}

static int __init my_module_init(void) {
    printk(KERN_INFO "Module loaded, initializing dynamic work\n");
    my_dynamic_work = kmalloc(sizeof(struct work_struct), GFP_KERNEL);
    if (!my_dynamic_work)
        return -ENOMEM;

    INIT_WORK(my_dynamic_work, my_dynamic_work_function);

    schedule_work(my_dynamic_work);
    return 0;
}

static void __exit my_module_exit(void) {
    printk(KERN_INFO "Cleaning up module\n");
    if (my_dynamic_work) {
        cancel_work_sync(my_dynamic_work);
        kfree(my_dynamic_work);
    }
}

module_init(my_module_init);
module_exit(my_module_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("yu-hsien");
MODULE_DESCRIPTION("An example of using INIT_WORK with dynamically allocated work_struct");

Makefile

obj-m += init_work_ex.o \
	  	 declare_work_ex.o
all:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

用 `make` 編譯後，將兩個核心模組掛載，再執行 `dmesg | tail` 可得輸出：

[261931.853758] Module loaded, initializing dynamic work
[261931.853896] Dynamic work executed
[262921.150709] Module loaded, scheduling work
[262921.150853] Executing my_work_function

確認掛載成功後，我們可以利用 `nm` 來觀察變數的宣告方式

$ nm init_work_ex.ko | grep 'my_dynamic_work'
0000000000000000 B my_dynamic_work
0000000000000010 T my_dynamic_work_function
0000000000000000 T __pfx_my_dynamic_work_function

$ nm declare_work_ex.ko | grep 'my_work'
0000000000000000 D my_work
0000000000000010 T my_work_function
0000000000000000 T __pfx_my_work_function

對於 `declare_work_ex.ko` 和 `init_work_ex.ko` 中的符號類型 `D` 和 `B` 的理解如下：
1. D (Data section)：表示該變數已經初始化，位於初始化資料段中。declare_work_ex.ko 中的 my_work 使用 D 標記，這表示這是一個在編譯時期就已經初始化的靜態 work_struct，這符合 `DECLARE_WORK` 的行為，即在宣告時就完成初始化。
3. B (BSS section)：表示該變數未初始化，位於 BSS 段，這是用來存放程序中未初始化的全域變數和靜態變數的區域。init_work_ex.ko 中的 my_dynamic_work 使用 B 標記，這表示它是一個在 BSS 段的變數（可能是一個指向 work_struct 的指針），這通常指向一塊動態分配的記憶體（即使該指針本身是靜態分配的）。

#### CMWQ

##### Why CMWQ?

在原先的 workqueue 實作中，`MT wq` 在每個 CPU 都會有一個 work thread，而 `ST wq` 是僅以單一的 work thread 來完成所有的工作。一個單獨的 MT wq 需要與 CPU 的數量一致地保持相同數量的 wq。隨著時間推移，越來越多的系統使用了 MT wq，加上 CPU 核心數的不斷增加，導致一些系統在啟動時就達到了預設的 32k PID 上限。

儘管 MT wq 消耗了大量資源，其提供的並行性，效果仍然未達到預期。無論是 ST wq 還是 MT wq，這種限制都存在，只不過在 MT wq 上表現較為緩和。每個工作隊列都有自己的獨立 worker pool；在 MT wq 中，每個 CPU 只分配到一個，而 ST wq 在整個系統中只有一個 context。這導致 work item 需要爭奪極為有限的執行 context，進而引發多種問題，例如在單一執行中 context 容易出現 deadlock。

並行性的提供與資源使用之間的矛盾迫使使用者作出不必要的妥協。例如，libata 選擇使用單線程工作隊列來輪詢 PIOs，從而接受了一個不必要的限制：無法同時處理兩個輪詢 PIOs。因為多線程工作隊列的並行性仍不足以滿足需求，需要更高並行性的用戶，如 async 或 fscache，最終不得不自行開發 thread pool。

每個綁定實際 CPU 的工作池通過與調度器的整合來管理並行性。當工作者喚醒或進入睡眠時，工作池會更新可運行工作者的數量，從而保持工作項目持續處理，避免CPU閒置。系統旨在**用最少的工作者維持必要的執行帶寬，且會暫時保留但最終終止不活動的工作者**。

對於不綁定CPU的工作隊列，其後台支援池的數量可以動態調整。使用者可以通過 `apply_workqueue_attrs()` 自訂工作隊列的屬性，系統將自動創建相應的工作池。此外，進展保證機制依賴於能夠在需要時創建新的工作者，特別是在內存壓力下，某些工作項目會被分配到有專門救援工作者的工作隊列上，以防止因執行上下文耗盡導致的 deadlock。

### [Engineering a Sort Function](https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf)
ksort 採用的 quicksort 即是從這篇論文中所實作出來的。
#### 動機
由於以往的 quicksort 的效能太差，故提出新的方法來改進其效能問題。

#### 思考過程
首先，使用 `Lomuto` 的切割方式，及選擇第 `1` 個元素當作 `pivot`，若陣列已經做好排序，會導致時間複雜度提升到 $O(n^2)$

void iqsort0(int *a, int n) {
    int i, j;
    
    if (n <= 1) return;
    for (i = 1, j = 0; i < n; i++) {
        if (a[i] < a[0])
            swap(++j, i, a);
    swap(0, j, a);
    iqsort0(a, j);
    iqsort0(a + j + 1, n - j - 1);
}

<!-- 再來，為了避免上述原陣列已經排序好(或接近排序好)的問題，改採取隨機的方式去找尋 `pivot` ，並且，將切割的方式改為，利用兩個數字分別指向陣列的第一個元素 (i)，以及最後一個元素 (j)，由底部往下早直到找到元素大於等於 `pivot` 值的停下來，另外一個則是從尾巴往前找小於等於的元素，若這兩個 `index` 沒有交叉 (i < j)，則將這兩個位置的值作交換，反之 (i > j)，將 `j` 與 `pivot` 作交換。 -->
為了解決快速排序在面對已經排序或接近排序的陣列時性能下降的問題，改良版快速排序採取了隨機選擇 pivot 的策略。透過隨機生成一個索引並與陣列的第一個元素交換來實現，這樣 pivot 就被放在了陣列的開始位置。
而分割則採取兩個指標 `i` 和 `j`，其中 `i` 指向陣列的第二個元素（因為第一個元素是 pivot ），而 `j` 指向陣列的最後一個元素
1. `i` 指標從底部開始，向上尋找直到找到一個大於或等於 pivot 值的元素停下來
2. `j` 指標從頂部開始，向下尋找直到找到一個小於或等於 pivot 值的元素停下來
3. 檢查這兩個指標 `i` 和 `j` 是否已經交叉。如果沒有交叉（即 `i < j`），則交換這兩個位置的值，然後繼續進行上述兩個搜索步驟；如果交叉了（即 `i > j`），則將 j 位置的元素與 pivot（陣列的第一個元素）交換。

// Program 3
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void iqsort1(int *a, int n) {
    int i, j, pivot_index, pivot;

    if (n <= 1) return;

    srand(time(NULL));
    pivot_index = rand() % n;
    swap(&a[0], &a[pivot_index]);
    pivot = a[0];

    i = 1;
    j = n - 1;

    // Partitioning step
    while (i <= j) {
        while (i <= j && a[i] <= pivot) i++;
        while (i <= j && a[j] > pivot) j--;
        if (i < j) {
            swap(&a[i], &a[j]);
        }
    }

    swap(&a[0], &a[j]);
    iqsort1(a, j);
    iqsort1(a + j + 1, n - j - 1);
}

切割完後如下圖所示:

<!-- 再來，他們修改了輸入的資料型態，讓其更具有彈性 -->
作者進一步增強了排序功能的通用性和靈活性。這個版本的快速排序不再僅僅針對整數資料，而是可以處理任何類型的資料。函式接受一個 `char *a` 參數，這是指向資料的指標，其中的元素可以是任何資料型態。
- `es` 表示陣列中每個元素的大小（以 Byte 為單位）
- `cmp` 允許用戶自定義比較的行為

// Program 4
void iqsort1(char *a, int n, int es, int (*cmp)())
{
    int j;
    char *pi, *pj, *pn;
    
    if (n <= 1) return;
    pi = a + (rand() % n) * es;
    swap(a, pi, es);
    pi = a;
    pj = pn = a + n * es;
    for (;;) {
        do pi += es; while (pi < pn && cmp(pi, a) < 0);
        do pj -= es; while (cmp(pj, a) > 0);
        if (pj < pi) break;
        swap(pi, pj, es);
    }
    swap(a, pj, es);
    j = (pj - a) / es;
    qsort1(a, j, es, cmp);
    qsort1(a + (j + 1) * es, n - j - 1, es, cmp);
}

<!-- 為了讓切割效果更好，作者採用了 Tukey's `ninther` 來找尋中位數，其是基於 `median of three` 的方式，雖然它比以往的 `median of three` 多了將近 12 次的比較次數，但對於大陣列來說成本不會很大，也能找到更加準確的中位數，不過對於小陣列可能就不是那麼友善了，所以作者經過實驗後來決定是否要用 `ninther` ，以下的數值是作者經過測試所統計出來的。 -->
為了進一步提升快速排序的效率並減少最壞情況下的性能下降，作者採用了 Tukey 的 `ninther` 方法來選擇中位數作為 pivot。這個方法是一個擴展的 **median of three** 技巧，它基於更大範圍的樣本來估計中位數，具體而言，是從三個不同的位置各取三個元素，再從這九個元素中選出中位數。雖然它比以往的 `median of three` 多了將近 12 次的比較次數，但對於大陣列來說成本不會很大，也能找到更加準確的中位數，不過對於小陣列可能就不是那麼友善了，所以作者經過實驗後來決定是否要用 `ninther` ，以下的數值是作者經過測試所統計出來的。
- [Ninther](https://en.wikipedia.org/wiki/Median#Ninther) 方法: 先將原先的陣列切分成 3 部分(這邊會切成左，中，右)，並在每個子陣列中找尋其 `median of three`，找到後再比較較這三個子陣列中位數的中位數，來避免選到最糟的 `pivot` 的情況。

static char *med3(char *a, char *b, char *c, int (*cmp)())
{    return cmp(a, b) < 0 ?
        (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
        : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
}

// ninther
pm = a + (n / 2) * es; /* Small arrays, middle element */
if (n > 7) {
    pl = a;
    pn = a + (n - 1) * es;
    if (n > 40) { /* Big arrays, pseudomedian of 9 */
        s = (n / 8) * es;
        pl = med3(pl, pl + s, pl + 2 * s, cmp);
        pm = med3(pm - s, pm, pm + s, cmp);
        pn = med3(pn - 2 * s, pn - s, pn, cmp);
    }
    pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */
}

`median of three` 示意圖如下 (平均比較次數: $\frac{8}{3}$)
在 `Program 3, 4` 中，當面對含有許多重複值的陣列時，其其分割方法導致效率顯著下降。這是因為這些方法在處理重複值時可能會引起不必要的比較和交換操作，特別是當這些重複值佔據了大部分陣列時。相比之下，第七版的 quicksort 採用了所謂的 **fat partition** 方法，這種方法有效地將陣列分割成三部分：
- 數值小於 `pivot`
- 數值等於 `pivot`
- 數值大於 `pivot`

void iqsort2(int *x, int n)
{
    int a, b, c, d, l, h, s, v;
    if (n <= 1) return;
    
    v = x[rand() % n];
    a = b = 0;
    c = d = n - 1;
    for (;;) {
        while (b <= c && x[b] <= v) {
            if (x[b] == v) iswap(a++, b, x);
            b++;
        }
        while (c >= b && x[c] >= v) {
            if (x[c] == v) iswap(d--, c, x);
            c--;
        }
        if (b > c) break;
        iswap(b++, c--, x);
    }
    s = min(a, b - a);
    for(l = 0, h = b - s; s; s--) iswap(l++, h++, x);
    s = min(d - c, n - 1 - d);
    for(l = b, h = n - s; s; s--) iswap(l++, h++, x);
    iqsort2(x, b - a);
    iqsort2(x + n - (d - c), d - c);
}

示意圖如下:

最後，來看 ksort 是怎麼運作的:
可以發現到 sort_impl.c 中的 `qsort_algo` 有用到兩個標籤:
- `top`: 會先判斷要排序的長度是否小於 `7`，是則直接做插入排序，反之則作上述的排序方式，其中

    if (swap_cnt == 0) { /* Switch to insertion sort */
        r = 1 + n / 4;   /* n >= 7, so r >= 2 */
        for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
            for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
                 pl -= es) {
                q_swap(pl, pl - es);
                if (++swap_cnt > r)
                    goto nevermind;
            }
        return;
    }

這個判斷式用於決定要不要提前使用插入排序，要進入有兩個條件:
1. 子序列不能有值與 `pivot` 相同
2. 子序列已經可以被切分成兩半不須經過交換
ex.

    digraph {
        node[shape=record];
        graph[pencolor=transparent];
        rankdir=LR;
        "Pivot"[shape=none];
        "pc"[shape=none];
        "pb"[shape=none];

        "Pivot" -> 5 -> 3 -> 1 -> 2 -> 4 -> 8 -> 9
        "pc" -> 9
        "pb" -> 3
    }

    digraph {
        node[shape=record];
        graph[pencolor=transparent];
        rankdir=LR;
        "Pivot"[shape=none];
        "pc"[shape=none];
        "pb"[shape=none];

        "Pivot" -> 5 -> 3 -> 1 -> 2 -> 4 -> 8 -> 9
        "pc" -> 8
        "pb" -> 9
    }

3. 但若交換次數太多會在切回原先的排序方式
- `nevermind`: 會先計算分段大小，若兩側的數量都大於 `100`，則會分配一個新的 `qsort` 結構，並將它排入對列進行並行處理，而若其小於 `100` 且大於 `0`，會將左側分段採取地回方式來排序，右側分段採取 goto 跳轉到 `top` 來處理。

### TODO: 強調 workqueue / CMWQ / kernel thread 對於任務分配的效率 (CPU utilization)

首先，我們再 sort_mod.c 上面加了以下的函式:

void start_measure(void)
{
    measure_start = ktime_get();
}

void end_measure(void)
{
    measure_end = ktime_get();
    printk(KERN_INFO "Duration on CPU: %llu ns\n", smp_processor_id(), ktime_to_ns(ktime_sub(measure_end, measure_start)));
}

來測量我們排序所花費的時間。
再來，使用了 3 種方式來測量其執行時間

// CMWQ does not use any flags
workqueue = alloc_workqueue("sortq", 0, WQ_MAX_ACTIVE);

// CMWQ uses WQ_CPU_INTENSIVE and WQ_MEM_RECLAIM
workqueue = alloc_workqueue("sortq", WQ_CPU_INTENSIVE | WQ_MEM_RECLAIM, WQ_MAX_ACTIVE);

// kernel threads
int thread_function(void *data)
{
    sort_data(data, 1024 / sizeof(int));
    return 0;
}
struct task_struct *task;
task = kthread_run(thread_function, sort_buffer, "sort_thread");
if (IS_ERR(task)) {
    kfree(sort_buffer);
    return PTR_ERR(task);
}

第一種 workqueue 的第二個參數是 `0` ，代表沒有對 CPU 有特定行為的指示。而第二種 work_queue 則會利用
- `WQ_CPU_INTENSIVE`: 被設置此 flag 的 workqueue 中的 work 是特別消耗 CPU 資源的。具體的影響是，這些 workqueue 中的 work item 將歸 scheduler 管理，相關的 work item 不會阻止同一 worker-pools 中的其他 work item 被執行。
- `WQ_MEM_RECLAIM`: kernel 將預先考慮此狀況讓建立的 workqueue 可以無視記憶體的壓力來建立 rescuer thread 以避免 deadlock 的發生。

第三種，我們利用 kernel threads 來執行排序，其中 `IS_ERR(task)` 用於，若創建失敗會回傳 `true` ，我們須將提前結束任務的分配，並通過 `PTR_ERR(task)` 來告知使用者錯誤原因為何。

:::spoiler
[Workqueue](https://docs.kernel.org/core-api/workqueue.html)
[Linux 核心設計: Concurrency Managed Workqueue(CMWQ)](https://hackmd.io/@RinHizakura/H1PKDev6h)
:::

接著，利用 python script 來產生資料

def generate_data(num_files, num_integers):
    for i in range(num_files):
        data = [random.randint(0, 10000) for _ in range(num_integers)]
        
        file_path = os.path.join(data_dir, f'data_{num_integers}_{i+1}.txt')
        with open(file_path, 'w') as f:
            f.write('\n'.join(map(str, data)))

有了資料後，我們還會用到 `perf` 來觀測，故需安裝 `perf`，安裝後，再利用批次檔來執行先前生成的資料

DEVICE="/dev/sort"
DATA_FILE_PREFIX="data/data_10000_"
RESULTS_FILE="kernel_threads_10000_results.txt"

echo "Performance Test Results" > $RESULTS_FILE

for i in $(seq 1 10); do
    DATA_FILE="${DATA_FILE_PREFIX}${i}.txt"

    echo "Running test for $DATA_FILE" >> $RESULTS_FILE
    sudo perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./user "$DEVICE" "$DATA_FILE" &>> $RESULTS_FILE
    
    if [ $? -ne 0 ]; then
        echo "Test failed for $DATA_FILE" >> $RESULTS_FILE
        exit 1
    fi

    echo "" >> $RESULTS_FILE
done

echo "All tests completed successfully." >> $RESULTS_FILE

並且修改 `user.c`

#define N_ELEMENTS 10000

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <device_path> <data_file>\n", argv[0]);
        return -1;
    }

    const char *device_path = argv[1];
    const char *data_file = argv[2];

    int fd = open(device_path, O_RDWR);
    ...

使其可以對應上先前的批次檔。
並依序執行以下命令

$ make insmod
$ gcc -o user user.c

# Clear the Kernel Message Buffer
$ sudo dmesg -c

$ chmod +x run_tests.sh
$ ./run_tests.sh

# Capture specific module output
$ sudo dmesg | grep "Duration on CPU"

$ make clean

#### 結果
100 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.2 ns | 3.2 ns | 3.8 ns |
| data2 | 4.2 ns | 4.2 ns | 4 ns |
| data3 | 0.4 ns | 5.2 ns | 3.6 ns |
| data4 | 3.6 ns | 4.4 ns | 4.4 ns |
| data5 | 6.2 ns | 5.2 ns | 2.2 ns |
| data6 | 7 ns | 6 ns | 2 ns |
| data7 | 3.2 ns | 5.2 ns | 3 ns |
| data8 | 4.8 ns | 4.6 ns | 4.4 ns |
| data9 | 7 ns | 4 ns | 3 ns |
| data10 | 7 ns | 2 ns | 3.8 ns |
| **Average** | 4.66 ns | 4.4 ns | 3.42 ns |

1000 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.6 ns | 2.8 ns | 3.8 ns |
| data2 | 6 ns | 4.4 ns | 3.8 ns |
| data3 | 4.6 ns | 3.6 ns | 4 ns |
| data4 | 4.2 ns | 0.6 ns | 3.2 ns |
| data5 | 3.6 ns | 6.2 ns | 2.2 ns |
| data6 | 2.4 ns | 0.4 ns | 4.6 ns |
| data7 | 3 ns | 6.2 ns | 4 ns |
| data8 | 3.4 ns | 5.4 ns | 3 ns |
| data9 | 3.2 ns | 5.6 ns | 2.4 ns |
| data10 | 1 ns | 0 ns | 1.8 ns |
| **Average** | 3.4 ns | 3.48 ns | 3.28 ns |

10000 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.4 ns | 3.4 ns | 4.4 ns |
| data2 | 0.6 ns | 4.2 ns | 4.6 ns |
| data3 | 2.6 ns | 4.6 ns | 3.4 ns |
| data4 | 3.2 ns | 5.8 ns | 4.8 ns |
| data5 | 5.2 ns | 3 ns | 3.6 ns |
| data6 | 2.6 ns | 3.6 ns | 5 ns |
| data7 | 3.6 ns | 4.4 ns | 4.4 ns |
| data8 | 2.6 ns | 3.6 ns | 4.6 ns |
| data9 | 3.2 ns | 3 ns | 4.6 ns |
| data10 | 4.4 ns | 3.2 ns | 3.4 ns |
| **Average** | 3.02 ns | 3.76 ns | 4.28 ns |

在處理不同規模的數據集時，kernel threads 在小到中等規模的數據集上表現良好，提供了最快的處理時間。然而，在更大的數據集上，不帶 flag 的 CMWQ 表現出更佳的效率

> [commit 336a10d](https://github.com/yu-hsiennn/ksort/commit/336a10dfbe3056e20770c7dee861604d5a841cd1)